Chapter 4Cyclic Codes, Rings, and Polynomials

4.1 Introduction

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 images, the vector


is said to be a cyclic shift of images to the right. A shift by images places to the right produces the vector .

Get Error Correction Coding, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.