Linear Feedback Shift Registers for Dummies

For the past several years, I've been interested in "correlation orthogonal" sequences, such as maximal length sequences (MLS, or M-sequences), Gold and Kasami sequences, Zadoff-Chu sequences, and so forth, for applications like measuring the impulse response of audio systems and room acoustics---what is broadly thought of as system identification. 

M-sequences are generated by linear feedback shift registers (LFSR). Gold and Kasami sequences are generated by XOR'ing multiple M-sequences in various phases. Gold sequences are used in spread-spectrum radio applications such as GPS, where they are known as Gold Codes. 

Because the transfer function (the frequency and phase response of a system, such as a loudspeaker) is the Fourier Transform of the impulse response, MLS became the dominant method for audio transfer function measurements starting in the late-80 [1].  In the early 00s, sine sweep methods were were rediscovered and popularized by Angelo Farina [2] and have become the dominant method, although MLS is still used in certain applications. 

My first exposure to this was from Schroeder's JASA paper [3]. Schroeder was interested in the impulse response of rooms because he had shown earlier that one could derive an ensemble estimate of the sound decay curves of a room---broadly speaking, the reverberation---via reverse integration of the room impulse response [4].  This led to a set of room acoustics characterization parameters and methods that are specified in ISO 3382.

The math behind LFSR's is based on Finite Field theory, in particular finite fields of integers mod p, where p is prime [5].  This was originally investigated by Évariste Galois in the early 1800's, and often referred to as Galois Field Theory. In our case, p=2, and hence is known as GF (2). 

Jason Sach has been writing a wonderful series of tutorials on Linear Feedback Shift Registers, applications, and the math behind them in his blog on the site Embedded Related.  Unfortunately, there's no index to the tutorials, so I decided to rectify that.

1. Linear Feedback Shift Registers for the Uninitiated, Part I: Ex-Pralite Monks and Finite Fields (July 3, 2017)
2. Linear Feedback Shift Registers for the Uninitiated, Part II: libgf2 and Primitive Polynomials (July 17, 2017)
3. Linear Feedback Shift Registers for the Uninitiated, Part III: Multiplicative Inverse, and Blankinship's Algorithm (September 9, 2017)
4. Linear Feedback Shift Registers for the Uninitiated, Part IV: Easy Discrete Logarithms and the Silver-Pohlig-Hellman Algorithm (September 16, 2017)
5. Linear Feedback Shift Registers for the Uninitiated, Part V: Difficult Discrete Logarithms and Pollard's Kangaroo Method (October 1, 2017)
6. Linear Feedback Shift Registers for the Uninitiated, Part VI: Sing Along with the Berlekamp-Massey Algorithm (October 18, 2017)
7. Linear Feedback Shift Registers for the Uninitiated, Part VII: LFSR Implementations, Idiomatic C, and Compiler Explorer (November 13, 2017)
8. Linear Feedback Shift Registers for the Uninitiated, Part VIII: Matrix Methods and State Recovery (November 21, 2017)
9. Linear Feedback Shift Registers for the Uninitiated, Part IX: Decimation, Trace Parity, and Cyclotomic Cosets (December 3, 2017)
10. Linear Feedback Shift Registers for the Uninitiated, Part X: Counters and Encoders (December 9, 2017)
11. Linear Feedback Shift Registers for the Uninitiated, Part XI: Pseudorandom Number Generation (December 20, 2017)
12. Linear Feedback Shift Registers for the Uninitiated, Part XII: Spread-Spectrum Fundamentals (December 29, 2017)
13. Linear Feedback Shift Registers for the Uninitiated, Part XIII: System Identification (March 12, 2018)
14. Linear Feedback Shift Registers for the Uninitiated, Part XIV: Gold Codes (April 18, 2018)
15. Linear Feedback Shift Registers for the Uninitiated, Part XV: Error Detection and Correction (June 12, 2018)
16. Linear Feedback Shift Registers for the Uninitiated, Part XVI: Reed-Solomon Error Correction (June 19, 2018)
17. Linear Feedback Shift Registers for the Uninitiated, Part XVII: Reverse-Engineering the CRC (July, 7, 2018)
18. Linear Feedback Shift Registers for the Uninitiated, Part XVIII: Primitive Polynomial Generation (August 6, 2018)

I will update this list if he writes anything further in this series.

1. Rife, D. D. & Vanderkooy, J. Transfer-Function Measurement with Maximum-Length Sequences. JAES 37, 419–444 (1989).
2. Farina, A. Simultaneous measurement of impulse response and distortion with a swept-sine technique. In (AES 108th Convention, 2000).
3. Schroeder, M. R. Integrated-impulse method measuring sound decay without using impulses. The Journal of the Acoustical Society of America 66, 497–500 (1979).
4. Schroeder, M. R. New Method of Measuring Reverberation Time. The Journal of the Acoustical Society of America 37, 409–412 (1965).
5. McEliece, R. J. Finite Fields for Computer Scientists and Engineers. (Springer Science & Business Media, 1987). doi:10.1007/978-1-4613-1983-2.