LFSR (Linear Feedback Shift Registers) 的用途很多, 最常用到的有 CRC (Cyclic
Redundancy
Check) 的計算, PRBS (Pseudo Random Bit Sequence) 的產生, 及 Scrambler /
Descrambler 等。
LFSR 的實作方法有兩種, 一是 Galois, 因為 XOR 置於 shift register 中間, 因此又稱為
in-line type 或
Modular type。
另一種是 Fibonacci, 因為 XOR 置於 feedback path, 又稱為 out-of-line type 或
Simple
type。目前看來, 大部分的實作都以 Galois 為主, 這也是我建議的作法。
# PRBS generator: 如附圖 1+X4+X17, 可以產生 2^17-1 個循環位元。唯一要注意的是初始值,
如果每一個暫存器的初始值為
0, 那輸出就永遠為 0, 無法循環變化。
# Scrambler: 將 data input 和 LFSR 的最後一級暫存器輸出作 XOR, 可以達到編碼的效果, 產生的
data
output 送給接收端後, 接收端用同樣的 LFSR 即可解出原始的 data input。當然送收雙方要有一個對齊的機制,
必須從同一個位置開始作 XOR
運算。
# CRC: 如果 data input 參與 feedback, 如附圖 CRC-4, 那運算完最後一個 data input
即可得到 CRC
的結果。但如果 data input 不參與 feedback, 那運算完最後一個 data input 之後, 仍必須額外送入 N 個 0,
才可得到 CRC
的結果。
以上的運算除了一次處理一個位元之外, 也可以一次處理 8 位元、16 位元或 32 位元。只要推導出 8 個 clock
之後每個暫存器的輸入為何, 即可作出 8 位元運算的電路。16 位元及 32 位元的推導過程也是如此。
by louis lin
參考資料:
* The great CRC mystery
* Linear feedback shift register
* 52 209 211 217
請先 登入 以發表留言。