4.5.10 Major Families Of Cyclic Codes

The cyclic code described in the preceding sections illustrates the fundamental principles of polynomial-based error-control coding. In practice, however, there is no single cyclic code that is optimal for every application. Over many decades, researchers have developed numerous families of cyclic codes, each designed to provide an appropriate balance between redundancy, error-correction capability, implementation complexity, decoding speed, and computational requirements. Although these codes differ in their mathematical construction, they all exploit the same underlying cyclic properties to enable efficient encoding and decoding.

Different communication and storage systems impose different design requirements. Some applications require only simple error detection, where any corrupted data can be discarded or retransmitted. Others demand powerful error correction because retransmission is impossible, undesirable, or would introduce unacceptable delay. Similarly, some channels are dominated by isolated random bit errors, whereas others produce long bursts of consecutive errors. No single coding technique performs optimally under all of these conditions, and different cyclic code families have therefore evolved to address different classes of error mechanisms.

One of the principal advantages of cyclic codes is that their algebraic structure allows both encoding and decoding to be implemented efficiently using simple shift registers, feedback networks, and polynomial arithmetic over finite fields. This efficiency has made cyclic codes attractive for an enormous range of applications, including computer memories, data-storage devices, optical media, digital broadcasting, wireless communication systems, computer networks, deep-space communications, and many other digital systems where reliable transmission or storage of information is essential.

In the following sections we examine several of the most important families of cyclic codes. We begin with Hamming codes, which introduced the first practical single-error-correcting block code and established many of the principles of modern coding theory. We then consider more powerful codes such as Bose–Chaudhuri–Hocquenghem (BCH) codes and Reed–Solomon codes, which provide substantially greater error-correction capability. Finally, we examine cyclic redundancy checks (CRCs), which sacrifice error correction in favor of extremely reliable error detection and consequently remain among the most widely used error-detection techniques in modern digital communication and computer systems.

4.5.10.1 Hamming Code

For a codeword of length n bits, a single bit error can occur in n different ways. Including the possibility of no error, the decoder must be capable of recognizing n+1 distinct states (the n single-error states plus the error-free state). Hamming showed that, to uniquely identify these possible error patterns, the number of redundant bits r must satisfy:

2^{r} \geq n + 1

(4.35)

single-error-correcting code—one that uses the minimum number of redundant bits necessary to detect and correct all single-bit errors—this becomes 2^r= n+1 so that Hamming codes are defined by the following relationships:

Number of parity bits: r=n–k.
Block length: n = 2^r–1.
Number of message bits: k = n–r.

In a Hamming code, the minimum distance is d_min =3, which enables the code to detect up to two errors and correct one error. For n=7, k=4 and r=3, the (7,4) Hamming code illustrated in Section 4.5.5 is generated by the polynomial g(X)=1+X+X³.

The complete set of sixteen codewords for this (7,4) cyclic Hamming code is summarized in Figure 4.15

Figure 4.15. Systematic and non-systematic codewords generated from g(X)=1+X+X³ for a (7,4) cyclic code.

Other Hamming codes are (15,11), (31,26), (63,57), and so on. Hamming codes form the foundation of more advanced cyclic codes such as BCH and R-S codes, which extend the concept to multiple-error correction and non-binary symbol alphabets—topics discussed in following sections.

4.5.10.2 CRC Codes

CRC codes are a subclass of cyclic block codes used primarily for error detection rather than correction. They are particularly effective at detecting burst errors, which are common in data transmission and storage systems. CRC codes can detect all error bursts of length up to (n–k) bits and all combinations of up to (d_min–1) bit errors. Their strength lies in the mathematical properties of their generator polynomial, g(X), which defines how parity bits are appended to the message sequence.

Figure 4.16 lists the generator polynomials for three standard CRC codes that have become widely adopted in communication protocols and digital interfaces. Each polynomial includes the factor (1+X), ensuring that all odd numbers of bit errors are detectable.

Figure 4.16. Generator polynomials for three standard CRC codes.

CRC-12 is commonly used for 6-bit data bytes, for example in legacy X.25 and MIL-STD-188-114 serial link protocols. CRC-16 and CRC-CCITT (X.25) are designed for 8-bit bytes and are employed in High-level Data Link Control (HDLC), USB, Bluetooth, and many satellite telemetry and telecommand frames.

4.5.10.3 BCH Codes

BCH codes were invented in 1959 by Hocquenghem and then independently in 1960 by Bose and Chaudhuri. They form a powerful and flexible subclass of cyclic block codes capable of correcting multiple random bit errors per codeword. BCH codes are widely used in modern communication and storage systems—including satellite links, optical and magnetic storage, and deep-space telemetry—where robust forward FEC is required.

BCH codes generalize the Hamming code by encoding k data bits into n code bits by adding (n–k) parity bits. A binary t-error-correcting BCH code is defined for a block length n=2^m–1, where m and t are integers such that 1≤ t ≤ 2^m^–1–1 The code is constructed over a Galois field GF(2^m)—see Appendix F. Its generator polynomial, g(X), is the least common multiple (LCM) of the minimal polynomials corresponding to α, α² ,…, α²^t, where α is a primitive element of the field.

BCH codes have the following properties:

Number of parity bits: r = n–k ≤ mt.
Block length: n = 2^m–l.
Minimum distance: d_min ≥ 2t+1

The generator polynomial must therefore be at least of degree mt, and the resulting code can correct up to t random bit errors per codeword. Further, a BCH code that can correct t random bit errors can detect up to 2t errors, provided its minimum distance is exactly 2t+1. The encoder and decoder structures are typically implemented using linear feedback shift registers for polynomial division and syndrome computation.

Tables of valid BCH codes for specific values of m and t are widely available in the literature and in standards. Figure 4.17 lists example primitive binary BCH codes used in modern communications. These examples illustrate how BCH codes can be configured to balance redundancy, error-correction capability, and bandwidth efficiency according to system requirements.

Figure 4.17. Example parameters of typical BCH codes.

Example: (15,7, t=2) BCH Code

Consider a binary BCH code constructed over GF(2⁴) (so m = 4) capable of correcting t = 2 errors.

From n=2^m–1=15, the code length is 15 bits.

The number of parity bits is r = n – k = 4×2 = 8, so k = 7 data bits are encoded into 15-bit codewords.

The designed minimum distance is d_min ≥ 2t + 1 = 5.

Let α be a primitive element of GF(2⁴) satisfying the primitive polynomial:

The generator polynomial g(X) is obtained as the least common multiple of the minimal polynomials of α and α³, the consecutive roots corresponding to t = 2:

g (X) = (X^{4} + X + 1) (X^{4} + X^{3} + X^{2} + X + 1) = X^{8} + X^{7} + X^{6} + X^{4} + 1

Thus, any 7-bit data sequence m(X) is encoded as:

c (X) = m (X) X^{8} + r e m a i n d e r [m (X) X^{8} / g (X)]

For example, if the message is m(X) = X ⁶ + X ³ + X + 1 (binary = 1001011), then:

m (X) X^{8} = X^{14} + X^{11} + X^{9} + X^{8}

\frac{m (X) X^{8}}{g (X)} \Rightarrow q (X) = X^{6} + X^{5} + X^{2} + X + 1 a n d r (X) = X^{6} + X^{4} + X^{2} + X + 1

So:

c (X) = X^{14} + X^{11} + X^{9} + X^{8} + X^{6} + X^{4} + X^{2} + X + 1

For the 7-bit input message 1001011, the 15-bit codeword is therefore c = 100101101010111.

With a minimum distance of 5, this code can detect up to four errors and correct up to two of them (although, of course, this comes at the cost of slightly more than double the required bandwidth—or equivalently, a throughput slightly less than half the available data rate). This illustrates the fundamental trade-off in coding: increased error protection reduces the net information rate, and the choice of code must therefore balance reliability, bandwidth, and system efficiency according to mission requirements.

4.5.10.4 Golay Codes

The Golay code is one of the most famous linear block codes and remains of historical and practical significance in communications and error control. It is a (23,12) cyclic code with a minimum distance of 7, meaning that it can detect all combinations of up to six-bit errors and correct all errors involving three or fewer bits.

The generator polynomials for the (23,12) Golay code are:

g_{1} (X) = X^{11} + X^{10} + X^{6} + X^{5} + X^{4} + X^{2} + 1

g_{2} (X) = X^{11} + X^{9} + X^{7} + X^{6} + X^{5} + X + 1

(4.36)

The extended Golay code, denoted as (24,12), is obtained by adding an overall parity bit to the (23,12) code. This increases the minimum distance to 8, improving error detection and correction capabilities. The extended code can therefore detect all combinations of 7-bit errors and correct all 3-bit errors.

Although the (24,12) code has a slightly higher bandwidth requirement and a somewhat more complex decoder, it is often preferred in practice. The addition of the parity bit makes the code systematic and simplifies clock synchronization between input and output data streams.

Golay codes, and particularly the extended (24,12) version, are used in several high-reliability applications such as deep-space communications, NASA telemetry systems, and digital radio links, where robust performance is required with moderate code complexity.

4.5.10.5 R-S Codes

R-S codes are an important subclass of non-binary BCH codes. They can correct any combination of t or fewer symbol errors using no more than 2t parity symbols.

Unlike binary codes that operate on single bits, R-S codes operate on multi-bit symbols of m bits each, defined over a finite field GF(2ᵐ)—see Appendix F. Because they process symbols rather than bits, R-S codes are particularly well-suited to systems employing m-ary modulation schemes or digital systems where data are naturally organized in bytes or words.

Number of parity symbols: r=2t.
Block length (symbols): n = 2^m–l.
Minimum distance: d_min = 2t+1 symbols.

R-S codes are widely used, particularly in applications that are sensitive to errors, because they:

Make efficient use of redundancy, achieving strong error correction with modest parity overhead.
Provide a flexible range of code rates, allowing optimization for different performance requirements.
Perform exceptionally well in channels dominated by burst errors, such as magnetic storage, optical media, and satellite links experiencing deep fades, because burst errors typically affect many bits within only a few adjacent symbols.
Have efficient algebraic encoders and decoders, including the Berlekamp–Massey algorithm and Euclidean decoders.

R-S coding has been widely adopted in systems such as NASA deep-space telemetry, CCSDS space communications standards, digital television, CD and DVD data storage, and forward-error correction in modern satellite modems (e.g., DVB-S2 and DVB-S2X).

R-S codes are often concatenated (see Section 4.9) with binary convolutional or turbo codes to combine burst-error correction with random-error protection. This concatenated approach has been adopted in several space communication standards, including the NASA/CCSDS and DVB families.