We have seen that linear block codes can be corrected using the standard array, but that for long codes the storage and computation time can be prohibitive. Furthermore, we have not yet seen any mechanism by which the generator or parity check matrix can be designed to achieve a specified minimum distance or other criteria. In this chapter, we introduce cyclic codes, which have additional algebraic structure to make encoding and decoding more efficient. Following the introduction in this chapter, additional algebraic tools and concepts are presented in Chapter 5, which will provide for design specifications and lead to efficient algebraic decoding algorithms.
Cyclic codes are based on polynomial operations. A natural algebraic setting for the operations on polynomials is the algebraic structure of a ring.
4.2 Basic Definitions
Given a vector , the vector
is said to be a cyclic shift of to the right. A shift by places to the right produces the vector .