4.18.9 What Are Convolutional Codes, Turbo Codes, LDPC Codes, and Polar Codes?
- What Is a Convolutional Code?
- Why Are They Called Convolutional Codes?
- How Does a Convolutional Encoder Work?
- What Is Constraint Length?
- What Is Code Rate?
- What Is a Trellis Diagram?
- What Is Viterbi Decoding?
- Why Was the Viterbi Algorithm Important?
- Where Were Convolutional Codes Used?
- What Are the Limitations of Convolutional Codes?
- What Are Turbo Codes?
- Why Are They Called Turbo Codes?
- How Does a Turbo Encoder Work?
- What Is an Interleaver?
- How Does Turbo Decoding Work?
- How Close Do Turbo Codes Come to Capacity?
- What Are LDPC Codes?
- Why Are They Called Low-Density Parity-Check Codes?
- How Are LDPC Codes Decoded?
- Why Are LDPC Codes Important?
- Where Are LDPC Codes Used?
- What Are Polar Codes?
- What Is Channel Polarization?
- Why Are Polar Codes Important?
- Where Are Polar Codes Used?
- How Do These Codes Compare?
- Which Performs Best?
- How Close Do Modern Codes Come to the Shannon Limit?
- Why Are Convolutional, Turbo, LDPC, and Polar Codes Important?
One of the greatest challenges in communications engineering is transmitting information reliably through channels affected by noise, interference, fading, and distortion. Claude Shannon's Channel Coding Theorem demonstrated that reliable communication is theoretically possible at rates approaching channel capacity, but for many years practical coding schemes remained far from these theoretical limits.
During the second half of the twentieth century, researchers developed increasingly sophisticated coding techniques that dramatically improved performance. Beginning with convolutional codes, progressing through turbo codes, and later advancing to low-density parity-check (LDPC) codes and polar codes, coding technology evolved from relatively simple algebraic structures to powerful capacity-approaching systems.
Today, these codes form the foundation of modern digital communications. They are used in satellite systems, mobile-phone networks, Wi-Fi systems, deep-space communications, fiber-optic networks, and many other technologies. Together they represent some of the most important achievements in communications engineering.
What Is a Convolutional Code?
A convolutional code is an error-correcting code that processes information continuously rather than in fixed-length blocks.
Instead of accepting a block of information bits and producing a block of coded bits, the encoder operates on a continuous stream of data. Each output depends not only on the current input bit but also on previous input bits stored in memory.
The encoder therefore possesses memory, unlike a simple block code.
Why Are They Called Convolutional Codes?
The name originates from the mathematical operation known as convolution.
The output sequence is generated by combining the current input with previous inputs according to predetermined rules. Although practical implementations use shift registers and modulo-2 arithmetic, the underlying mathematics resembles convolution operations.
The name has remained in use since the 1950s.
How Does a Convolutional Encoder Work?
A typical convolutional encoder consists of:
- Shift registers.
- Modulo-2 adders.
- Generator connections.
As each input bit enters the encoder:
- Existing bits shift through the registers.
- Several register outputs are combined.
- One or more coded bits are generated.
The process repeats continuously.
Consequently, every output bit depends upon both present and past input bits.
What Is Constraint Length?
The constraint length represents the amount of memory in a convolutional encoder.
It is usually denoted K and corresponds to the number of stages influencing the encoder output. Larger constraint lengths generally provide:
- Better error-correction capability.
- Greater coding gain.
However, they also increase decoder complexity.
What Is Code Rate?
Like block codes, convolutional codes have a coding rate.
For example:
- Rate-1/2 code: One information bit produces two coded bits.
- Rate-1/3 code: One information bit produces three coded bits.
Lower rates provide stronger protection but require greater bandwidth.
Higher rates provide better efficiency but less protection.
What Is a Trellis Diagram?
The operation of a convolutional code is often represented using a trellis diagram.
The trellis shows:
- Encoder states.
- Possible transitions.
- Corresponding outputs.
Each path through the trellis represents a possible transmitted sequence. The decoder uses the trellis to determine the most likely transmitted data.
Trellis diagrams form the foundation of convolutional decoding.
What Is Viterbi Decoding?
The most famous convolutional decoding technique is the Viterbi algorithm, developed by Andrew Viterbi in 1967.
The Viterbi decoder examines possible paths through the trellis and identifies the path most likely to have generated the received sequence. Rather than considering every possible message, the algorithm efficiently eliminates unlikely candidates.
This allows powerful error correction with manageable computational complexity.
Why Was the Viterbi Algorithm Important?
Before the Viterbi algorithm, practical decoding of powerful convolutional codes was difficult. The algorithm provided:
- Near-optimum performance.
- Efficient implementation.
- Practical decoding for real systems.
For several decades, convolutional coding combined with Viterbi decoding became the dominant form of forward error correction in many communications systems.
Where Were Convolutional Codes Used?
Convolutional codes became widely used in:
- Satellite communications. Many satellite links employed convolutional coding.
- Deep-space communications. NASA missions relied heavily on convolutional codes.
- Digital radio systems. Numerous radio networks adopted convolutional coding.
- Early cellular networks. Many second-generation systems incorporated convolutional codes.
- For many years they represented the state of the art in error correction.
What Are the Limitations of Convolutional Codes?
Although highly successful, convolutional codes have limitations.
As performance approaches the Shannon limit:
- Decoder complexity increases rapidly.
- Memory requirements increase.
- Implementation becomes difficult.
Researchers therefore continued searching for more powerful coding techniques.
What Are Turbo Codes?
Turbo codes were introduced in 1993 by French researchers: Claude Berrou, Alain Glavieux and Punya Thitimajshima.
Their announcement shocked the communications community because turbo codes performed much closer to Shannon capacity than previously thought possible. Many engineers initially believed the reported results were incorrect. However, subsequent verification confirmed the breakthrough.
Turbo codes rapidly became one of the most important developments in coding theory.
Why Are They Called Turbo Codes?
The name derives from the iterative exchange of information between multiple decoders. Information circulates repeatedly through the decoding process, somewhat analogous to feedback mechanisms in turbocharged engines.
Although the analogy is imperfect, the name became widely accepted.
How Does a Turbo Encoder Work?
A turbo encoder typically consists of two convolutional encoders and an interleaver.
The interleaver rearranges the order of information bits before they enter the second encoder. This arrangement creates multiple independent representations of the same information.
The resulting redundancy provides powerful error-correction capability.
What Is an Interleaver?
An interleaver rearranges the order of transmitted bits.
For example: Original: 1 2 3 4 5 6 Interleaved: 3 6 1 5 2 4. Interleaving spreads errors and improves decoder performance.
It is a critical component of turbo coding.
How Does Turbo Decoding Work?
Turbo decoding uses:
- Multiple decoders.
- Iterative processing.
Each decoder generates probability estimates. These estimates are exchanged repeatedly. With each iteration the reliability of the decisions improves. After several iterations, the decoder converges toward the most likely transmitted message.
This iterative approach enables performance remarkably close to the Shannon limit.
How Close Do Turbo Codes Come to Capacity?
Turbo codes can operate within approximately 0.5–1 dB of theoretical capacity under suitable conditions.
This performance represented a revolutionary advance in communications engineering.
What Are LDPC Codes?
Low-density parity-check (LDPC) codes were originally proposed by Robert Gallager in 1962.
At the time, available computers were insufficient to implement practical decoders. The codes were largely forgotten until their rediscovery during the 1990s.
Today, LDPC codes are among the most important coding techniques in modern communications.
Why Are They Called Low-Density Parity-Check Codes?
LDPC codes use parity-check matrices containing relatively few ones.
Most entries are zero. This sparse structure:
- Reduces complexity.
- Enables efficient decoding.
- Supports long codewords.
The low density of non-zero elements gives the code its name.
How Are LDPC Codes Decoded?
LDPC codes employ iterative decoding algorithms based on probability propagation.
The decoder repeatedly exchanges information between:
- Variable nodes.
- Check nodes.
These exchanges gradually improve the estimated values of transmitted bits.
The process continues until convergence occurs or a maximum number of iterations is reached.
Why Are LDPC Codes Important?
LDPC codes offer:
- Excellent performance.
- Long code lengths.
- High spectral efficiency.
- Near-capacity operation.
For many applications they outperform turbo codes. Consequently, LDPC codes became widely adopted.
Where Are LDPC Codes Used?
Applications include:
- Satellite communications. Modern satellite systems frequently use LDPC coding.
- DVB-S2 and DVB-S2X. These standards rely heavily on LDPC codes.
- Wi-Fi. Recent Wi-Fi standards employ LDPC coding.
- Optical communications. High-capacity fiber systems use LDPC codes extensively.
- 5G Data channels. Many 5G data services utilize LDPC coding.
Their widespread adoption reflects their outstanding performance.
What Are Polar Codes?
Polar codes were introduced in 2008 by Erdal Arikan.
They are significant because they were the first family of codes mathematically proven to achieve channel capacity for certain classes of communication channels.
This achievement represented a major theoretical breakthrough.
What Is Channel Polarization?
Polar codes rely on a concept known as channel polarization.
The encoding process transforms a collection of channels into:
- Highly reliable channels.
- Highly unreliable channels.
Information bits are transmitted through the reliable channels. Known values are inserted into the unreliable channels.
This strategy enables highly efficient communication.
Why Are Polar Codes Important?
Polar codes combine:
- Strong theoretical foundations.
- Excellent practical performance.
- Efficient implementation.
Their capacity-achieving properties make them particularly attractive for modern communications systems.
Where Are Polar Codes Used?
The most prominent application is:
5G Control Channels
The 5G New Radio standard employs polar codes for many control-channel applications.
This adoption brought polar coding into widespread commercial deployment.
How Do These Codes Compare?
| Code Type | Era | Typical Decoding |
|---|---|---|
| Convolutional | 1950s | Viterbi |
| Turbo | 1990s | Iterative |
| LDPC | 1990s resurgence | Iterative |
| Polar | 2008 onward | Successive cancellation / list decoding |
Each generation moved progressively closer to Shannon capacity.
Which Performs Best?
The answer depends on the application.
- Convolutional codes. Advantages: simplicity and mature technology.
- Turbo codes. Advantages: excellent performance and proven practical success.
- LDPC codes. Advantages: outstanding performance, scalability, and high throughput.
- Polar codes. Advantages: strong theoretical foundation and excellent control-channel performance.
Modern systems often employ different codes for different purposes.
How Close Do Modern Codes Come to the Shannon Limit?
The most advanced coding systems routinely operate within less than 1 dB (sometimes less than 0.5 dB) of theoretical capacity.
This achievement would have seemed extraordinary when Shannon first published his work in 1948.
Why Are Convolutional, Turbo, LDPC, and Polar Codes Important?
These coding techniques represent successive generations in the quest to approach Shannon capacity. Each introduced new concepts and decoding strategies that dramatically improved communication reliability and efficiency.
Together they transformed communications engineering by enabling reliable transmission under conditions that would previously have been considered impossible. Modern satellite systems, mobile-phone networks, Wi-Fi systems, optical-fiber networks, and deep-space missions all depend upon these coding techniques.
Summary
Convolutional codes, turbo codes, LDPC codes, and polar codes represent some of the most important developments in modern error-control coding. Convolutional codes introduced continuous encoding and Viterbi decoding, turbo codes demonstrated near-capacity performance through iterative decoding, LDPC codes combined sparse parity-check matrices with excellent practical performance, and polar codes became the first family of codes proven to achieve channel capacity.
These techniques allow modern communication systems to operate remarkably close to the theoretical limits established by Shannon, making reliable high-speed digital communication possible across a vast range of applications.
Back to reading