Cyclic Linear Codes, Shift Registers, and CRC

This chapter presents some basic material concerning linear cyclic codes from a very elementary point of view while covering all the main ideas. It then develops some more advanced results on linear cyclic codes. The chapter shows how linear feedback shift registers dovetail beautifully with linear cyclic codes using our approach to generators. The algebraic theory of shift registers is related to a cyclic redundancy check (CRC) protocol which is frequently used on the Internet and elsewhere. The CRC is used to detect link-level transmission errors while the Internet checksum, used by most Internet protocols, is designed to detect higher level transmission errors. CRCs use polynomial arithmetic.