4.18.8 What Are Cyclic Codes, BCH Codes, and Reed–Solomon Codes?
- What Is a Cyclic Code?
- Why Are Cyclic Codes Useful?
- How Are Cyclic Codes Represented?
- Why Use Polynomials?
- What Is a Generator Polynomial?
- What Is a Systematic Codeword?
- What Is a Non-Systematic Codeword?
- How Are Cyclic Codes Generated?
- How Are Errors Detected?
- What Is a BCH Code?
- Why Were BCH Codes Important?
- How Are BCH Codes Specified?
- How Do BCH Codes Correct Errors?
- What Is a Reed–Solomon Code?
- What Is the Difference Between Bits and Symbols?
- Why Are Reed–Solomon Codes Good for Burst Errors?
- How Are Reed–Solomon Codes Specified?
- Where Have Reed–Solomon Codes Been Used?
- What Is Concatenated Coding?
- How Do BCH and Reed–Solomon Codes Compare?
- Are BCH and Reed–Solomon Codes Still Used?
- Why Are Cyclic Codes Important?
As communication systems evolved, engineers sought coding techniques that could provide stronger error protection than simple parity checks and Hamming codes while remaining practical to implement. Although Hamming codes were a major breakthrough, their ability to correct only a single error limited their usefulness in many real-world applications.
Many communication channels suffer from burst errors, where several adjacent bits or symbols are corrupted simultaneously. Such errors are common in radio communications, satellite links, magnetic storage devices, optical disks, and digital broadcasting systems. Protecting against these errors requires more powerful coding techniques.
One of the most important developments in coding theory was the creation of cyclic codes, a family of block codes with particularly elegant mathematical properties. From cyclic codes emerged two of the most successful error-control coding techniques ever developed: BCH codes and Reed–Solomon codes. These codes have been used extensively in communications, storage systems, satellite networks, deep-space missions, compact discs, DVDs, and countless other applications.
Today, although newer coding methods such as LDPC and polar codes are widely used, BCH and Reed–Solomon codes remain among the most important and successful error-correcting codes ever developed.
What Is a Cyclic Code?
A cyclic code is a special type of linear block code with an additional property:
If a codeword belongs to the code, any cyclic shift of that codeword is also a valid codeword.
For example, suppose 1011000 is a valid codeword. Then: 0101100 , 0010110, 0001011 and all other cyclic shifts are also valid codewords.
This property gives cyclic codes their name and provides important mathematical advantages.
Why Are Cyclic Codes Useful?
The cyclic property allows encoding and decoding operations to be implemented efficiently using simple shift registers and logic circuits.
Advantages include:
- Efficient hardware implementation.
- Efficient software implementation.
- Strong mathematical structure.
- Excellent error-detection capability.
- Foundation for more advanced codes.
Because of these advantages, cyclic codes became extremely popular in practical communication systems.
How Are Cyclic Codes Represented?
Unlike many block codes, cyclic codes are often represented using polynomials.
A binary sequence such as:
1011
may be represented as:
x3 + x + 1
Each bit corresponds to a coefficient of the polynomial.
This representation greatly simplifies the mathematics of cyclic coding.
Why Use Polynomials?
The polynomial representation transforms coding operations into algebraic operations.
Instead of manipulating bits directly, engineers can perform:
- Polynomial multiplication.
- Polynomial division.
- Modular arithmetic.
These operations are particularly well suited to digital hardware and provide powerful analytical tools.
What Is a Generator Polynomial?
Every cyclic code is defined by a generator polynomial g(x).
The generator polynomial determines:
- Which codewords are valid.
- The code structure.
- The error-detection capability.
To generate a codeword c(x) the information polynomial d(x) is multiplied by g(x) or processed using equivalent systematic encoding procedures.
The generator polynomial is therefore the heart of the cyclic code.
What Is a Systematic Codeword?
In a systematic code:
- The original data appears unchanged.
- Additional parity bits are appended.
For example data 1011 might become 1011 100. The receiver can immediately identify the information portion of the codeword.
Most practical cyclic codes are implemented in systematic form.
What Is a Non-Systematic Codeword?
In a non-systematic code:
- Information bits are mixed with parity bits.
- The original data is not directly visible.
Although mathematically equivalent, systematic codes are generally easier to interpret and are therefore more commonly used.
How Are Cyclic Codes Generated?
The general procedure is:
- Represent the data as a polynomial.
- Multiply by xr, where r is the number of parity bits.
- Divide by the generator polynomial.
- Determine the remainder.
- Append the remainder to the data.
The resulting sequence forms a valid codeword.
This procedure is closely related to the generation of cyclic redundancy checks (CRCs).
How Are Errors Detected?
At the receiver:
- The received codeword is divided by the generator polynomial.
- The remainder is examined.
If remainder = 0 the codeword is valid. If remainder ≠ 0 an error has occurred.
This simple test provides powerful error-detection capability.
What Is a BCH Code?
BCH stands for Bose–Chaudhuri–Hocquenghem after the researchers who developed the code during the late 1950s.
BCH codes are a family of cyclic block codes that provide multiple-error correction capability. Unlike Hamming codes, which typically correct only one error, BCH codes can be designed to correct one, two, five, ten or many errors. The designer can select the desired level of protection.
This flexibility made BCH codes extremely attractive in practical systems.
Why Were BCH Codes Important?
Prior to BCH codes, many practical codes had relatively limited correction capability.
BCH codes demonstrated that:
- Powerful multiple-error correction was possible.
- Efficient algebraic decoding algorithms could be developed.
- Practical implementations could be achieved.
For many years BCH codes represented some of the most powerful error-correcting codes available.
How Are BCH Codes Specified?
BCH codes are commonly described by (n, k, t) where:
- n = codeword length.
- k = information length.
- t = number of correctable errors.
For example (31, 16, 3) indicates:
- 31-bit codeword.
- 16 information bits.
- Correction of up to 3 errors.
This notation immediately describes the code's capability.
How Do BCH Codes Correct Errors?
BCH decoders use algebraic techniques based on finite-field arithmetic.
The decoder:
- Calculates syndromes.
- Determines an error-locator polynomial.
- Identifies error positions.
- Corrects the errors.
Although the mathematics can be complex, the resulting decoding process is remarkably efficient.
What Is a Reed–Solomon Code?
Reed–Solomon codes are among the most important error-correcting codes ever developed.
They were introduced in 1960 by:
Like BCH codes, Reed–Solomon codes belong to the cyclic-code family. However, they operate on symbols rather than individual bits.
This distinction gives them unique advantages.
What Is the Difference Between Bits and Symbols?
Most binary codes operate on single bits.
Reed–Solomon codes operate on groups of bits called symbols. For example: one symbol may consist of 8 bits. A single symbol error may therefore represent corruption of multiple bits.
Because the decoder works at the symbol level, Reed–Solomon codes are particularly effective against burst errors.
Why Are Reed–Solomon Codes Good for Burst Errors?
Suppose a burst error corrupts: 16 consecutive bits. A binary code may interpret this as: 16 separate bit errors.
A Reed–Solomon code using 8-bit symbols sees only 2 symbol errors. The decoder can therefore correct the problem much more easily.
This capability made Reed–Solomon codes enormously successful in practical applications.
How Are Reed–Solomon Codes Specified?
Reed–Solomon codes are commonly written as (n, k) where:
- n = total symbols.
- k = information symbols.
The code can correct: t = (n − k) / 2 symbol errors.
For example: RS(255, 223) contains 255 symbols, 223 information symbols, and 32 parity symbols. It can correct 16 symbol errors.
Where Have Reed–Solomon Codes Been Used?
Few codes have enjoyed such widespread adoption.
Applications include:
- Compact discs (CDs). Reed–Solomon coding protects audio data from scratches and defects.
- DVDs and Blu-ray discs. Optical-storage systems rely heavily on Reed–Solomon coding.
- Deep-space communications. NASA spacecraft have employed Reed–Solomon codes extensively.
- Satellite communications. Many satellite links use Reed–Solomon coding as part of concatenated coding systems.
- Digital television. Broadcast systems often employ Reed–Solomon protection.
- Data storage. Numerous storage devices use Reed–Solomon error correction.
What Is Concatenated Coding?
Sometimes two different coding techniques are combined.
For example: Outer code: Reed–Solomon. Inner code: Convolutional code.
The Reed–Solomon code corrects burst errors. The convolutional code corrects random errors.
This combination was widely used in satellite and deep-space communication systems.
How Do BCH and Reed–Solomon Codes Compare?
| Feature | BCH | Reed–Solomon |
|---|---|---|
| Operates on | Bits | Symbols |
| Burst-error performance | Good | Excellent |
| Random-error performance | Excellent | Good |
| Complexity | Moderate | Moderate |
| Flexibility | High | High |
| Storage applications | Common | Extensive |
Both remain highly important coding techniques.
Are BCH and Reed–Solomon Codes Still Used?
Yes.
Although modern systems increasingly employ:
- Turbo codes.
- LDPC codes.
- Polar codes.
BCH and Reed–Solomon codes remain widely used. They continue to appear in:
- Storage systems.
- Broadcasting.
- Satellite communications.
- Optical media.
- Data transmission systems.
Their robustness and simplicity ensure their ongoing relevance.
Why Are Cyclic Codes Important?
Cyclic codes introduced a powerful algebraic approach to coding theory. Their polynomial structure enables efficient encoding and decoding while providing excellent error-detection capability.
BCH and Reed–Solomon codes extended these ideas into powerful multiple-error-correcting systems that have protected billions of communications and storage devices. Few coding techniques have had a greater practical impact on modern technology.
Summary
Cyclic codes are linear block codes possessing the property that cyclic shifts of valid codewords are also valid codewords. Their algebraic structure allows efficient implementation using generator polynomials and polynomial arithmetic.
Among the most important cyclic codes are BCH codes and Reed–Solomon codes. BCH codes provide powerful multiple-bit error correction, while Reed–Solomon codes operate on symbols and are particularly effective against burst errors. Together, these codes have played a major role in communications, broadcasting, storage systems, satellite networks, and deep-space missions, making them among the most successful error-control codes ever developed.
Back to reading