研究 | LFSR (Linear Feedback Shift Registers)

LFSR (Linear Feedback Shift Registers)

分兩種
1. Fibonacci (又稱 Many-to-one 或 External feedback)
2. Galois (又稱 One-to-many 或 Internal feedback)

圖片連結自 
https://www.ctimes.com.tw/DispArt/tw/16123011119R.shtml

設計良好的 LFSR 產生出來的 sequence 可以涵蓋所有可能的值減 1 種的 sequence，也就是maximal-length，例如：4-bit LFSR 可以產生 (2^4-1) = 15 種 sequence。而設計不良可能會發生 loop 導致產生的 sequence 的值只會在一個範圍內。

參考
https://www.eetimes.com/document.asp?doc_id=1274550
https://www.eetimes.com/document.asp?doc_id=1274551
https://www.eetimes.com/document.asp?doc_id=1274552
https://en.wikipedia.org/wiki/Linear-feedback_shift_register
http://www.ti.com/lit/an/scta036a/scta036a.pdf
http://www.eng.auburn.edu/~strouce/class/elec6250/LFSRs.pdf
https://www.ctimes.com.tw/DispArt/tw/16123011119R.shtml

應用
1. 加密解密 (Encryption and Decryption)
    a. 串流加密法 (Stream Ciphers)
        http://security.nknu.edu.tw/textbook1ed/CHAP2-Cipher.pdf
    b. Scrambling
        http://epaper.gotop.com.tw/pdf/ach014500.pdf
2. CRC (Cyclic redundancy check)
    a. http://www.ciphersbyritter.com/ARTS/CRCMYST.HTM
    b. http://blog.sina.com.cn/s/blog_62d9edac01015lsd.html
3. 資料壓縮 (Data compression)
4. BIST (Built-in self-test)
5. 隨機亂數序列 PRBS (Pseudo Random Bit Sequence)
6. 假亂數 (Pseudo-random number)