Hubbry Logo
Error correction codeError correction codeMain
Open search
Error correction code
Community hub
Error correction code
logo
7 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Contribute something
Error correction code
Error correction code
Error correction code
View on Wikipedia
from Wikipedia

In computing, telecommunication, information theory, and coding theory, forward error correction (FEC) or channel coding[1][2][3] is a technique used for controlling errors in data transmission over unreliable or noisy communication channels.

The central idea is that the sender encodes the message in a redundant way, most often by using an error correction code, or error correcting code (ECC).[4][5] The redundancy allows the receiver not only to detect errors that may occur anywhere in the message, but often to correct a limited number of errors. Therefore a reverse channel to request re-transmission may not be needed. The cost is a fixed, higher forward channel bandwidth.

The American mathematician Richard Hamming pioneered this field in the 1940s and invented the first error-correcting code in 1950: the Hamming (7,4) code.[5]

FEC can be applied in situations where re-transmissions are costly or impossible, such as one-way communication links or when transmitting to multiple receivers in multicast.

Long-latency connections also benefit; in the case of satellites orbiting distant planets, retransmission due to errors would create a delay of several hours. FEC is also widely used in modems and in cellular networks.

FEC processing in a receiver may be applied to a digital bit stream or in the demodulation of a digitally modulated carrier. For the latter, FEC is an integral part of the initial analog-to-digital conversion in the receiver. The Viterbi decoder implements a soft-decision algorithm to demodulate digital data from an analog signal corrupted by noise. Many FEC decoders can also generate a bit-error rate (BER) signal which can be used as feedback to fine-tune the analog receiving electronics.

FEC information is added to mass storage (magnetic, optical and solid state/flash based) devices to enable recovery of corrupted data, and is used as ECC computer memory on systems that require special provisions for reliability.

The maximum proportion of errors or missing bits that can be corrected is determined by the design of the ECC, so different forward error correcting codes are suitable for different conditions. In general, a stronger code induces more redundancy that needs to be transmitted using the available bandwidth, which reduces the effective bit-rate while improving the received effective signal-to-noise ratio. The noisy-channel coding theorem of Claude Shannon can be used to compute the maximum achievable communication bandwidth for a given maximum acceptable error probability. This establishes bounds on the theoretical maximum information transfer rate of a channel with some given base noise level. However, the proof is not constructive, and hence gives no insight of how to build a capacity achieving code. After years of research, some advanced FEC systems like polar code[3] come very close to the theoretical maximum given by the Shannon channel capacity under the hypothesis of an infinite length frame.

Method

[edit]

ECC is accomplished by adding redundancy to the transmitted information using an algorithm. A redundant bit may be a complicated function of many original information bits. The original information may or may not appear literally in the encoded output; codes that include the unmodified input in the output are systematic, while those that do not are non-systematic.

A simplistic example of ECC is to transmit each data bit three times, which is known as a (3,1) repetition code. Through a noisy channel, a receiver might see eight versions of the output, see table below.

Triplet received Interpreted as
000 0 (error-free)
001 0
010 0
100 0
111 1 (error-free)
110 1
101 1
011 1

This allows an error in any one of the three samples to be corrected by "majority vote", or "democratic voting". The correcting ability of this ECC is:

  • Up to one bit of triplet in error, or
  • up to two bits of triplet omitted (cases not shown in table).

Though simple to implement and widely used, this triple modular redundancy is a relatively inefficient ECC. Better ECC codes typically examine the last several tens or even the last several hundreds of previously received bits to determine how to decode the current small handful of bits (typically in groups of two to eight bits).

Averaging noise to reduce errors

[edit]

ECC could be said to work by "averaging noise"; since each data bit affects many transmitted symbols, the corruption of some symbols by noise usually allows the original user data to be extracted from the other, uncorrupted received symbols that also depend on the same user data.

  • Because of this "risk-pooling" effect, digital communication systems that use ECC tend to work well above a certain minimum signal-to-noise ratio and not at all below it.
  • This all-or-nothing tendency – the cliff effect – becomes more pronounced as stronger codes are used that more closely approach the theoretical Shannon limit.
  • Interleaving ECC coded data can reduce the all or nothing properties of transmitted ECC codes when the channel errors tend to occur in bursts. However, this method has limits; it is best used on narrowband data.

Most telecommunication systems use a fixed channel code designed to tolerate the expected worst-case bit error rate, and then fail to work at all if the bit error rate is ever worse. However, some systems adapt to the given channel error conditions: some instances of hybrid automatic repeat-request use a fixed ECC method as long as the ECC can handle the error rate, then switch to ARQ when the error rate gets too high; adaptive modulation and coding uses a variety of ECC rates, adding more error-correction bits per packet when there are higher error rates in the channel, or taking them out when they are not needed.

Types

[edit]
Main articles: Block code and Convolutional code
A block code (specifically a Hamming code) where redundant bits are added as a block to the end of the initial message
A continuous convolutional code where redundant bits are added continuously into the structure of the code word

The two main categories of ECC codes are block codes and convolutional codes.

  • Block codes work on fixed-size blocks (packets) of bits or symbols of predetermined size. Practical block codes can generally be hard-decoded in polynomial time to their block length.
  • Convolutional codes work on bit or symbol streams of arbitrary length. They are most often soft decoded with the Viterbi algorithm, though other algorithms are sometimes used. Viterbi decoding allows asymptotically optimal decoding efficiency with increasing constraint length of the convolutional code, but at the expense of exponentially increasing complexity. A convolutional code that is terminated is also a 'block code' in that it encodes a block of input data, but the block size of a convolutional code is generally arbitrary, while block codes have a fixed size dictated by their algebraic characteristics. Types of termination for convolutional codes include "tail-biting" and "bit-flushing".

Classical block codes are usually decoded using hard-decision algorithms,[6] which means that for every input and output signal a hard decision is made whether it corresponds to a one or a zero bit. In contrast, convolutional codes are typically decoded using soft-decision algorithms like the Viterbi, MAP or BCJR algorithms, which process (discretized) analog signals, and which allow for much higher error-correction performance than hard-decision decoding.

Nearly all classical block codes apply the algebraic properties of finite fields. Hence classical block codes are often referred to as algebraic codes.

Block codes

[edit]

There are many types of block codes; Reed–Solomon coding is noteworthy for its widespread use in compact discs, DVDs, and hard disk drives. Other examples of classical block codes include Golay, BCH, Multidimensional parity, and Hamming codes.

Hamming ECC is commonly used to correct ECC memory and early SLC NAND flash memory errors.[7] This provides single-bit error correction and 2-bit error detection. Hamming codes are only suitable for more reliable single-level cell (SLC) NAND. Denser multi-level cell (MLC) NAND may use multi-bit correcting ECC such as BCH, Reed–Solomon, or LDPC.[8][9][10] NOR flash typically does not use any error correction.[8]

Soft codes

[edit]

Low-density parity-check (LDPC)

[edit]
Main article: Low-density parity-check code

Low-density parity-check (LDPC) codes are a class of highly efficient linear block codes made from many single parity check (SPC) codes. They can provide performance very close to the channel capacity (the theoretical maximum) using an iterated soft-decision decoding approach, at linear time complexity in terms of their block length. Practical implementations rely heavily on decoding the constituent SPC codes in parallel.

LDPC codes were first introduced by Robert G. Gallager in his PhD thesis in 1960, but due to the computational effort in implementing encoder and decoder and the introduction of Reed–Solomon codes, they were mostly ignored until the 1990s.

LDPC codes are now used in many recent high-speed communication standards, such as DVB-S2 (Digital Video Broadcasting – Satellite – Second Generation), WiMAX (IEEE 802.16e standard for microwave communications), High-Speed Wireless LAN (IEEE 802.11n),[11] 10GBase-T Ethernet (802.3an) and G.hn/G.9960 (ITU-T Standard for networking over power lines, phone lines and coaxial cable). Other LDPC codes are standardized for wireless communication standards within 3GPP MBMS (see fountain codes).

Turbo code

[edit]
Main article: Turbo code

Turbo coding is an iterated soft-decoding scheme that combines two or more relatively simple convolutional codes and an interleaver to produce a block code that can perform to within a fraction of a decibel of the Shannon limit. Predating LDPC codes in terms of practical application, they now provide similar performance.

One of the earliest commercial applications of turbo coding was the CDMA2000 1x (TIA IS-2000) digital cellular technology developed by Qualcomm and sold by Verizon Wireless, Sprint, and other carriers. It is also used for the evolution of CDMA2000 1x specifically for Internet access, 1xEV-DO (TIA IS-856). Like 1x, EV-DO was developed by Qualcomm, and is sold by Verizon Wireless, Sprint, and other carriers (Verizon's marketing name for 1xEV-DO is Broadband Access, Sprint's consumer and business marketing names for 1xEV-DO are Power Vision and Mobile Broadband, respectively).

Describing the performance of an ECC

[edit]

In contrast to classical block codes that often specify an error-detecting or error-correcting ability, many modern block codes such as LDPC codes lack such guarantees. Instead, modern codes are evaluated in terms of their bit error rates.

Most forward error correction codes correct only bit-flips, but not bit-insertions or bit-deletions. In this setting, the Hamming distance is the appropriate way to measure the bit error rate. A few forward error correction codes are designed to correct bit-insertions and bit-deletions, such as Marker Codes and Watermark Codes. The Levenshtein distance is a more appropriate way to measure the bit error rate when using such codes. [12]

Code-rate and the tradeoff between reliability and data rate

[edit]
See also: Bit rate § Information rate

The fundamental principle of ECC is to add redundant bits in order to help the decoder to find out the true message that was encoded by the transmitter. The code-rate of a given ECC system is defined as the ratio between the number of information bits and the total number of bits (i.e., information plus redundancy bits) in a given communication package. The code-rate is hence a real number. A low code-rate close to zero implies a strong code that uses many redundant bits to achieve a good performance, while a large code-rate close to 1 implies a weak code.

The redundant bits that protect the information have to be transferred using the same communication resources that they are trying to protect. This causes a fundamental tradeoff between reliability and data rate.[13] In one extreme, a strong code (with low code-rate) can induce an important increase in the receiver SNR (signal-to-noise-ratio) decreasing the bit error rate, at the cost of reducing the effective data rate. On the other extreme, not using any ECC (i.e., a code-rate equal to 1) uses the full channel for information transfer purposes, at the cost of leaving the bits without any additional protection.

One interesting question is the following: how efficient in terms of information transfer can an ECC be that has a negligible decoding error rate? This question was answered by Claude Shannon with his second theorem, which says that the channel capacity is the maximum bit rate achievable by any ECC whose error rate tends to zero:[14] His proof relies on Gaussian random coding, which is not suitable to real-world applications. The upper bound given by Shannon's work inspired a long journey in designing ECCs that can come close to the ultimate performance boundary. Various codes today can attain almost the Shannon limit. However, capacity achieving ECCs are usually extremely complex to implement.

The most popular ECCs have a trade-off between performance and computational complexity. Usually, their parameters give a range of possible code rates, which can be optimized depending on the scenario. Usually, this optimization is done in order to achieve a low decoding error probability while minimizing the impact to the data rate. Another criterion for optimizing the code rate is to balance low error rate and retransmissions number in order to the energy cost of the communication.[15]

Local decoding and testing of codes

[edit]
Main articles: Locally decodable code and Locally testable code

Sometimes it is only necessary to decode single bits of the message, or to check whether a given signal is a codeword, and do so without looking at the entire signal. This can make sense in a streaming setting, where codewords are too large to be classically decoded fast enough and where only a few bits of the message are of interest for now. Also such codes have become an important tool in computational complexity theory, e.g., for the design of probabilistically checkable proofs.

Locally decodable codes are error-correcting codes for which single bits of the message can be probabilistically recovered by only looking at a small (say constant) number of positions of a codeword, even after the codeword has been corrupted at some constant fraction of positions. Locally testable codes are error-correcting codes for which it can be checked probabilistically whether a signal is close to a codeword by only looking at a small number of positions of the signal.

Not all locally decodable codes (LDCs) are locally testable codes (LTCs)[16] neither locally correctable codes (LCCs),[17] q-query LCCs are bounded exponentially[18][19] while LDCs can have subexponential lengths.[20][21]


Improving performance

[edit]

Concatenation (combination)

[edit]
Main article: Concatenated error correction codes

Classical (algebraic) block codes and convolutional codes are frequently combined in concatenated coding schemes in which a short constraint-length Viterbi-decoded convolutional code does most of the work and a block code (usually Reed–Solomon) with larger symbol size and block length "mops up" any errors made by the convolutional decoder. Single pass decoding with this family of error correction codes can yield very low error rates, but for long range transmission conditions (like deep space) iterative decoding is recommended.

Concatenated codes have been standard practice in satellite and deep space communications since Voyager 2 first used the technique in its 1986 encounter with Uranus. The Galileo craft used iterative concatenated codes to compensate for the very high error rate conditions caused by having a failed antenna.

Interleaving

[edit]
"Interleaver" redirects here. For the fiber-optic device, see optical interleaver.
A short illustration of the interleaving idea

Interleaving is frequently used in digital communication and storage systems to improve the performance of forward error correcting codes. Many communication channels are not memoryless: errors typically occur in bursts rather than independently. If the number of errors within a code word exceeds the error-correcting code's capability, it fails to recover the original code word. Interleaving alleviates this problem by shuffling source symbols across several code words, thereby creating a more uniform distribution of errors.[22] Therefore, interleaving is widely used for burst error-correction.

The analysis of modern iterated codes, like turbo codes and LDPC codes, typically assumes an independent distribution of errors.[23] Systems using LDPC codes therefore typically employ additional interleaving across the symbols within a code word.[24]

For turbo codes, an interleaver is an integral component and its proper design is crucial for good performance.[22][25] The iterative decoding algorithm works best when there are not short cycles in the factor graph that represents the decoder; the interleaver is chosen to avoid short cycles.

Interleaver designs include:

  • rectangular (or uniform) interleavers (similar to the method using skip factors described above)
  • convolutional interleavers
  • random interleavers (where the interleaver is a known random permutation)
  • S-random interleaver (where the interleaver is a known random permutation with the constraint that no input symbols within distance S appear within a distance of S in the output).[26]
  • a contention-free quadratic permutation polynomial (QPP).[27] An example of use is in the 3GPP Long Term Evolution mobile telecommunication standard.[28]

In multi-carrier communication systems, interleaving across carriers may be employed to provide frequency diversity, e.g., to mitigate frequency-selective fading or narrowband interference.[29]

Interleaving example

[edit]

Transmission without interleaving: 

Error-free message:                                 aaaabbbbccccddddeeeeffffgggg
Transmission with a burst error:                    aaaabbbbccc____deeeeffffgggg

Here, each group of the same letter represents a 4-bit one-bit error-correcting codeword. The codeword cccc is altered in one bit and can be corrected, but the codeword dddd is altered in three bits, so either it cannot be decoded at all or it might be decoded incorrectly.

With interleaving: 

Error-free code words:                              aaaabbbbccccddddeeeeffffgggg
Interleaved:                                        abcdefgabcdefgabcdefgabcdefg
Transmission with a burst error:                    abcdefgabcd____bcdefgabcdefg
Received code words after deinterleaving:           aa_abbbbccccdddde_eef_ffg_gg

In each of the codewords "aaaa", "eeee", "ffff", and "gggg", only one bit is altered, so one-bit error-correcting code will decode everything correctly.

Transmission without interleaving: 

Original transmitted sentence:                      ThisIsAnExampleOfInterleaving
Received sentence with a burst error:               ThisIs______pleOfInterleaving

The term "AnExample" ends up mostly unintelligible and difficult to correct.

With interleaving: 

Transmitted sentence:                               ThisIsAnExampleOfInterleaving...
Error-free transmission:                            TIEpfeaghsxlIrv.iAaenli.snmOten.
Received sentence with a burst error:               TIEpfe______Irv.iAaenli.snmOten.
Received sentence after deinterleaving:             T_isI_AnE_amp_eOfInterle_vin_...

No word is completely lost and the missing letters can be recovered with minimal guesswork.

Disadvantages of interleaving

[edit]

Use of interleaving techniques increases total delay. This is because the entire interleaved block must be received before the packets can be decoded.[30] Also interleavers hide the structure of errors; without an interleaver, more advanced decoding algorithms can take advantage of the error structure and achieve more reliable communication than a simpler decoder combined with an interleaver[citation needed]. An example of such an algorithm is based on neural network[31] structures.

Software for error-correcting codes

[edit]

Simulating the behaviour of error-correcting codes (ECCs) in software is a common practice to design, validate and improve ECCs. The upcoming wireless 5G standard raises a new range of applications for the software ECCs: the Cloud Radio Access Networks (C-RAN) in a Software-defined radio (SDR) context. The idea is to directly use software ECCs in the communications. For instance in the 5G, the software ECCs could be located in the cloud and the antennas connected to this computing resources: improving this way the flexibility of the communication network and eventually increasing the energy efficiency of the system.

In this context, there are various available Open-source software listed below (non exhaustive).

  • AFF3CT(A Fast Forward Error Correction Toolbox): a full communication chain in C++ (many supported codes like Turbo, LDPC, Polar codes, etc.), very fast and specialized on channel coding (can be used as a program for simulations or as a library for the SDR).
  • IT++: a C++ library of classes and functions for linear algebra, numerical optimization, signal processing, communications, and statistics.
  • OpenAir: implementation (in C) of the 3GPP specifications concerning the Evolved Packet Core Networks.

List of error-correcting codes

[edit]
Hard codes
Distance Detects up to (bits) Corrects up to (bits) Code
2 1 0 Parity (guess needed on error)
3 1 1 Triple modular redundancy
3 1 1 Perfect Hamming such as Hamming(7,4)
4 2 1 SECDED: extended Hamming such as (39,32), (72,64)
5 2 2
6 3 2 DECTED: Nordstrom-Robinson code
7 3 3 Perfect binary Golay code
8 4 3 TECFED: Extended binary Golay code

See also

[edit]

References

[edit]

Further reading

[edit]
[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Error correction code

View on Grokipedia
from Grokipedia
An error-correcting code (ECC) is a technique for controlling errors in data transmission or storage by adding redundant information to the original message, enabling the receiver to detect and correct errors without needing to request retransmission. The theoretical foundations of error-correcting codes were established by in his 1948 paper "," which proved that reliable data transmission is achievable over noisy channels as long as the information rate remains below the channel's capacity limit. This work highlighted the potential for codes to combat noise through redundancy, setting the stage for practical implementations. In 1950, Richard W. Hamming developed the first explicit single-error-correcting code, known as the Hamming (7,4) code, while working at Bell Laboratories to address errors in early computer calculations caused by unreliable circuits. Hamming's innovation introduced parity-check bits positioned to pinpoint the location of a single bit error, marking a pivotal advancement in applied . Error-correcting codes are broadly classified into , which process data in fixed-length segments, and convolutional codes, which handle continuous streams with overlapping dependencies. Linear , a major subcategory, include binary codes like Hamming codes for single-error correction and more advanced cyclic codes such as BCH and Reed-Solomon codes, which can correct multiple errors and are widely used in applications requiring high reliability. Performance is typically measured by parameters including code rate (the ratio of message bits to total encoded bits), minimum distance (the smallest between any two codewords, determining error-correcting capability), and decoding complexity. Modern ECCs, such as low-density parity-check (LDPC) codes invented by in 1960 and rediscovered in the 1990s, along with introduced in 1993, achieve near-optimal performance close to Shannon's limit through iterative decoding algorithms. These advancements have enabled error rates as low as 10^{-15} in practical systems. ECCs are indispensable in diverse fields, including digital communications (e.g., , ), data storage (e.g., SSDs, QR codes), and (e.g., Voyager missions using Reed-Solomon codes for image transmission). Ongoing research focuses on adapting ECCs for emerging technologies like and high-speed optical networks, where error rates remain a critical challenge.

Fundamentals

Definition and Purpose

An error-correcting code (ECC) is a technique that adds redundant information to a , transforming it into a codeword that allows the receiver to detect and correct errors introduced during transmission or storage over unreliable channels. This redundancy enables reliable recovery of the original even when or interference alters some bits, distinguishing ECC from simpler error-detection methods. The theoretical foundation of ECCs traces back to Claude Shannon's seminal 1948 work on , which demonstrated that arbitrarily reliable communication is achievable at rates below the channel's capacity despite noise, by cleverly encoding messages with sufficient redundancy. This proof established the possibility of error-free data transfer in noisy environments, inspiring the development of practical coding schemes. The primary purpose of ECCs is to ensure and reliability in applications prone to errors, such as for signals and links, and for and storage systems. Unlike error-detection codes, such as that merely flag the presence of errors (e.g., a single can detect but not correct a flipped bit), ECCs actively repair errors without retransmission, reducing latency and bandwidth overhead in high-stakes scenarios. A basic example is the repetition code, where each bit of the message is transmitted multiple times—say, three times—and the receiver uses majority voting to decode the most frequent bit as the original, correcting single-bit errors within each group./06%3A_Information_Communication/6.25%3A_Repetition_Codes) This simple approach illustrates how redundancy combats noise but highlights the need for more efficient codes in real-world use, as it significantly increases transmission length./06%3A_Information_Communication/6.25%3A_Repetition_Codes)

Error Models and Detection vs. Correction

Error models in describe the patterns of noise or interference that can corrupt transmitted data. The binary symmetric channel (BSC) is a basic discrete memoryless channel where each transmitted bit is received correctly with probability 1-p and flipped with crossover probability p, assuming independent errors across bits. This model, foundational to , assumes symmetric error probabilities for 0 and 1, making it suitable for analyzing random bit errors in digital communication systems. Burst errors represent another common pattern, occurring as a contiguous of erroneous bits within a codeword, often due to noise bursts in transmission media like channels or storage devices. Unlike random errors, burst errors affect multiple consecutive symbols, with the length of the burst defining its severity; for instance, codes designed for burst correction must handle fixed or variable burst lengths up to a specified maximum. Erasure channels model scenarios where the receiver identifies unreliable symbols (erasures) but does not know their correct values, such as in networks; here, erasures occur with probability ε, and the channel outputs the symbol, an erasure flag, or nothing, allowing simpler correction than unknown errors. This model was introduced as a tractable case for studying and coding bounds. Error detection and correction differ fundamentally in their goals and mechanisms. Detection schemes identify the presence of errors without repairing them, typically using minimal like checksums or cyclic redundancy checks (CRC); for example, a single appended to a word ensures even or odd parity, detecting any odd number of bit errors but failing for even numbers. CRC, based on division over finite fields, excels at detecting burst errors up to its degree and is widely used in protocols for its efficiency in flagging multi-bit corruptions. In contrast, correction requires greater to not only detect but also locate and repair errors, relying on the code's structure to map received words to the nearest valid codeword, often measured by —the number of positions differing between two codewords. The choice between detection and correction involves key tradeoffs in complexity, overhead, and application suitability. Detection methods are simpler and impose less redundancy (e.g., 1 bit for parity versus multiple for correction), enabling reliable error flagging but often necessitating retransmission via (ARQ) protocols, which can introduce latency in high-error environments. Correction, through forward error correction (FEC), avoids retransmissions by fixing errors on the first pass, making it ideal for real-time systems like satellite links or where delays are intolerable, though at the cost of higher computational demands and bandwidth overhead. Combining both in hybrid ARQ-FEC schemes balances these, using FEC for most errors and ARQ for residuals. A code's error-handling capability is quantified by its minimum d, the smallest distance between any two distinct codewords. Such a code can detect up to d-1 errors, as any change fewer than d positions cannot transform one codeword into another, and correct up to t = \lfloor (d-1)/2 \rfloor errors, since spheres of radius t around codewords are disjoint, allowing unique nearest-codeword decoding. This bound ensures reliable operation below the channel's error rate threshold.

Basic Encoding and Decoding Principles

Error-correcting codes introduce into the original to enable the detection and correction of errors introduced during transmission or storage. In the encoding process, a of kk symbols over a finite is transformed into a longer codeword of n>kn > k symbols, where the additional n−kn - k symbols, known as parity or check bits, are computed based on the message bits to satisfy specific parity-check conditions. The rate R=k/nR = k/n quantifies the efficiency of this , with lower rates indicating more protection against errors at the cost of increased transmission overhead. Encoding can be systematic or non-systematic. In systematic encoding, the codeword consists of the original kk message symbols followed (or preceded) by the n−kn - k parity bits, allowing direct extraction of the message without full decoding if no errors occur. For example, a simple even-parity scheme for error detection appends a parity bit to make the total number of 1s even, though this only detects single errors and requires more bits for correction. Non-systematic encoding mixes the message and parity information across all nn positions, potentially offering better error-correcting performance but complicating message recovery. A basic illustration is the repetition code, where a single bit message "0" is encoded as "000" and "1" as "111" (k=1k=1, n=3n=3, R=1/3R=1/3), repeating the bit to tolerate noise through redundancy rather than complex parity computation. Decoding recovers the original message from the potentially erroneous received vector rr of length nn by identifying and correcting , typically by finding the nearest valid codeword in . For linear codes over fields like the binary field, syndrome decoding computes the s=Hrs = H r, where HH is the (n−k)×n(n-k) \times n parity-check matrix whose rows are orthogonal to the codewords; if s=0s = 0, no is assumed, while a nonzero ss corresponds to a unique pattern for correctable , enabling efficient correction without exhaustive search. Decoding strategies differ in decision-making: hard-decision decoding treats each received symbol as a hard 0 or 1 based on a threshold (e.g., for binary signals), simplifying computation but discarding information. In contrast, soft-decision decoding incorporates reliability metrics, such as received signal strength or likelihood probabilities, to weigh symbols and achieve superior performance, often improving rates by 2-3 dB over hard decisions. For the repetition code, decoding uses majority vote: in "101", two 1s indicate the message "1", correcting the single flip and demonstrating how repetition reduces via averaging over multiple transmissions.

Classical Linear Block Codes

Hamming Codes

Hamming codes form a family of binary linear capable of correcting single-bit errors and detecting double-bit errors in their extended form. Developed by Richard W. Hamming in 1950 at Bell Laboratories, these codes addressed the frequent single-bit errors encountered in early computing machines, which relied on punched cards and vacuum tubes prone to failures without automatic correction mechanisms. Hamming's motivation stemmed from frustration with manual restarts due to undetected errors, leading to the of a systematic method using redundant parity bits to enable self-correction. The construction of a places parity bits at bit positions that are powers of 2 (i.e., 1, 2, 4, ..., 2^{m-1}) within the codeword, while bits occupy the remaining positions. The parity-check matrix HH is an m×nm \times n matrix over the binary field F2\mathbb{F}_2, where n=2m−1n = 2^m - 1 is the code length, and its columns consist of all distinct nonzero binary vectors of length mm, typically ordered to correspond to the binary representation of the column indices from 1 to nn. Each parity bit is computed as the even parity (modulo-2 sum) over the bits in positions whose binary representations have a 1 in the corresponding parity bit's position. The code dimension is k=n−m=2m−1−mk = n - m = 2^m - 1 - m, yielding a minimum of d=3d = 3, which suffices for single-error correction via the sphere-packing bound. For example, the (7,4) uses m=3m = 3 parity bits to encode 4 bits into a 7-bit codeword. Decoding relies on syndrome computation: for a received vector r\mathbf{r}, the syndrome s=HrT\mathbf{s} = H \mathbf{r}^T (computed modulo 2) equals zero if no occurred, confirming r\mathbf{r} as a valid codeword. If s≠0\mathbf{s} \neq \mathbf{0}, the binary value of s\mathbf{s} directly indicates the position of the single erroneous bit, which is then flipped to recover the original codeword. This process corrects any single-bit and detects (but does not correct) double-bit errors, as a two-bit produces a nonzero not matching any single column of HH. An extended augments the standard code by adding an overall , increasing the length to n′=2mn' = 2^m while maintaining dimension k=2m−1−mk = 2^m - 1 - m, resulting in d=4d = 4. This extra bit enables single-error correction alongside double-error detection, as the overall parity check flags discrepancies from even parity in the extended codeword. However, Hamming codes are limited to single-error correction per block, rendering them inefficient for environments with multiple errors, where more advanced codes like BCH or LDPC are preferred for higher correction capability without proportional redundancy increases. The code rate R=k/nR = k/n starts low for small mm (e.g., 4/7≈0.5714/7 \approx 0.571 for m=3m=3) but approaches 1 as mm grows, though the fixed single-error limit reduces overall efficiency for longer blocks prone to multiple faults.

Reed-Solomon Codes

Reed-Solomon codes, a class of non-binary cyclic error-correcting codes, were invented by Irving S. Reed and Gustave Solomon in 1960. These codes operate over finite fields of the form GF(2^m), where symbols are elements of the field rather than binary bits, enabling efficient correction of multi-symbol errors, particularly burst errors. As a subclass of BCH codes, Reed-Solomon codes evaluate low-degree polynomials at distinct field elements to generate codewords, providing robust performance in applications requiring symbol-level reliability. The construction of a Reed-Solomon code begins with selecting a GF(q) where q = 2^m, and defining the code length n ≤ q - 1 as the number of nonzero elements in the field. A of k symbols is represented as a f(x) of degree less than k over GF(q). The codeword is then formed by evaluating f(x) at n distinct nonzero elements α_1, α_2, ..., α_n of the field, yielding the codeword (f(α_1), f(α_2), ..., f(α_n)). For non-systematic encoding, a generator g(x) of degree 2t is used, defined as g(x) = ∏_{i=1}^{2t} (x - β^i), where β is a primitive element of GF(q) and t is the error-correcting capability; the codeword is then c(x) = f(x) · g(x) modulo x^n - 1. Systematic encoding is achieved by placing the symbols in the first k positions and computing the remaining n - k parity symbols to satisfy the parity-check conditions. The parameters of a Reed-Solomon code are defined by its length n, dimension k (number of information symbols), and minimum d = n - k + 1, allowing correction of up to t = (n - k)/2 symbol errors. These parameters ensure that any two distinct codewords differ in at least d positions, providing a guaranteed error-correcting capability that scales with the n - k. Reed-Solomon codes achieve the , d ≤ n - k + 1, making them maximum distance separable (MDS) codes; this optimality is expressed as: d=n−k+1d = n - k + 1 where equality holds for all valid n and k with 1 ≤ k < n ≤ q - 1. Decoding Reed-Solomon codes involves computing syndromes from the received word to identify errors, followed by algebraic methods to locate and correct them. The Berlekamp-Massey algorithm processes the 2t syndromes to find the error-locator polynomial σ(x), whose roots indicate the positions of the errors; this algorithm runs in O(t^2) time over GF(q). Once locations are found using the Chien search (evaluating σ(x) at the field elements), the Forney algorithm computes the error magnitudes by relating them to the error-evaluator polynomial and the formal derivative of the error-locator, enabling correction via subtraction from the received symbols. These codes handle erasures (known error positions) more effectively than random errors, correcting up to n - k erasures or a combination of e erasures and s errors where 2s + e ≤ n - k. Reed-Solomon codes are widely applied in storage media like compact discs (CDs), where cross-interleaved variants correct scratches and defects, and in two-dimensional barcodes such as QR codes for robust data recovery under partial occlusion.

BCH Codes

Bose–Chaudhuri–Hocquenghem (BCH) codes are a class of cyclic linear block codes over finite fields, designed to correct multiple random errors in data transmission or storage. They generalize the single-error-correcting Hamming codes to handle up to tt errors, where t>1t > 1, by specifying a set of consecutive roots for the generator polynomial in an extension field. These codes are particularly effective for binary alphabets and find applications in communications systems requiring reliable error correction with algebraic decoding efficiency. The BCH codes were independently invented by French mathematician Alexis Hocquenghem in 1959 and by Indian mathematicians and Dinesh K. Ray-Chaudhuri in 1960. Hocquenghem's work focused on error-correcting codes using properties, while Bose and Ray-Chaudhuri's contributions emphasized binary group codes with multiple error correction capabilities. Primitive BCH codes are constructed over the F2m\mathbb{F}_{2^m}, with code length n=2m−1n = 2^m - 1, dimension k≥n−mtk \geq n - m t, and capability to correct tt errors. The generator polynomial g(x)g(x) is the of least degree whose roots include 2t2t consecutive powers of a primitive element α\alpha of F2m\mathbb{F}_{2^m}, specifically α,α2,…,α2t\alpha, \alpha^2, \dots, \alpha^{2t}; it is formed as the of the minimal polynomials of these roots. A key parameter of BCH codes is the designed distance δ=2t+1\delta = 2t + 1, which guarantees a minimum d≥δd \geq \delta via the BCH bound. This bound states that for a of length nn over F2\mathbb{F}_2 whose generator polynomial has δ−1\delta - 1 consecutive αb,αb+1,…,αb+δ−2\alpha^b, \alpha^{b+1}, \dots, \alpha^{b+\delta-2} (with b=1b = 1 for narrow-sense primitive codes), the minimum satisfies d≥δ.d \geq \delta. The actual minimum distance may exceed δ\delta, providing better error-correcting performance than designed. For example, the primitive binary BCH code with m=4m = 4, n=15n = 15, and t=2t = 2 (δ=5\delta = 5) has d=7>5d = 7 > 5. Decoding of BCH codes typically proceeds in steps: compute the syndrome vector from the received word using the parity-check matrix, determine the error-locator via the Peterson–Gorenstein–Zierler (PGZ) algorithm, find its roots to locate errors, and compute error values for correction. The PGZ algorithm solves for the error-locator coefficients using determinants of syndrome matrices and is effective for t≤(d−1)/2t \leq (d-1)/2, with O(t2n)O(t^2 n). Alternatively, the can compute the error-locator by finding the of the polynomial and x2t−1x^{2t} - 1, offering similar efficiency. These methods enable bounded-distance decoding up to tt errors. Binary Hamming codes correspond to the special case of s with t=1t = 1 (δ=3\delta = 3), where the generator polynomial is the minimal polynomial of α\alpha. The binary Golay code, a perfect code with parameters (23,12,7)(23, 12, 7), is also a primitive BCH code with designed distance δ=7\delta = 7 (thus t=3t = 3). These relations highlight BCH codes' role in unifying simpler algebraic constructions while extending their error-correcting power.

Advanced Classical Codes

Low-Density Parity-Check Codes

Low-density parity-check (LDPC) codes are a class of linear block error-correcting codes characterized by a sparse parity-check matrix HH, where each column contains a small, fixed number j≥3j \geq 3 of 1s, and each row has at most a small, fixed number kk of 1s, ensuring low density of nonzero entries. These codes were invented by in his 1960 PhD thesis at MIT, with the foundational analysis published in 1963, demonstrating their potential for efficient decoding through iterative methods on sparse graphs. Largely overlooked initially due to computational limitations, LDPC codes were rediscovered in the late by and , who showed through simulations that randomly constructed sparse codes could achieve bit error rates approaching the Shannon limit, rivaling the performance of emerging . The construction of LDPC codes relies on a known as the Tanner graph, introduced by Michael Tanner in 1981, which represents the parity-check matrix HH with two sets of nodes: variable nodes corresponding to codeword bits and check nodes corresponding to parity-check equations, connected by edges where HH has 1s. Regular LDPC codes maintain constant degrees jj for all variable nodes and kk for all check nodes, while irregular variants allow varying degrees across nodes to optimize performance, as analyzed in ensemble methods that average over constructions. Ensemble analysis evaluates the typical behavior of code families, revealing that irregular degree distributions enable thresholds closer to by balancing message flow in the graph. Key parameters for effective LDPC codes include high code rates (close to 1 for efficient bandwidth use) and large girth—the of the shortest cycle in the Tanner graph—to minimize decoding errors from short loops that correlate messages. Well-designed LDPC codes with block nn can correct a number of errors dd that grows as log⁡n\log n, approaching the theoretical limits for large nn while maintaining low decoding complexity. Decoding of LDPC codes employs iterative on the Tanner graph, specifically the sum-product algorithm, which uses soft-decision inputs (log-likelihood ratios) to exchange probabilistic messages between variable and check nodes until convergence or a maximum iteration limit. In the sum-product algorithm, variable-to-check messages update as the product of incoming check messages and channel evidence, while check-to-variable messages compute marginal probabilities via box-plus operations on incoming distributions, enabling near-maximum-likelihood performance with polynomial-time for sparse graphs. Density evolution provides a rigorous tool for analyzing and optimizing LDPC ensembles by tracking the evolution of average message distributions over in the large-block-length limit. For the (BEC) with erasure probability ϵ\epsilon, the density evolution recursion for the average erasure probability xlx_l at ll is xl=ϵλ(1−ρ(1−xl−1)),x_l = \epsilon \lambda \left( 1 - \rho \left( 1 - x_{l-1} \right) \right), where λ(x)=∑λixi−1\lambda(x) = \sum \lambda_i x^{i-1} and ρ(x)=∑ρixi−1\rho(x) = \sum \rho_i x^{i-1} are the variable and check node degree distributions (polynomials encoding the fractions of nodes of each degree), respectively. The decoding threshold ϵ∗\epsilon^* is the supremum of ϵ\epsilon values for which xl→0x_l \to 0 as l→∞l \to \infty, ensuring successful decoding with high probability; ensembles are designed to maximize ϵ∗\epsilon^* close to the Shannon limit. LDPC codes have been widely adopted in modern standards, including the specification for satellite broadcasting, where irregular repeat-accumulate LDPC codes with rates from 1/4 to 9/10 provide robust error correction paired with BCH outer codes. In New Radio (NR), LDPC codes serve as the primary channel coding for data channels (PDSCH and PUSCH), supporting high-throughput rates up to 9/10 with quasi-cyclic structures for efficient hardware implementation. Recent advancements from 2023 to 2025 focus on protograph-based LDPC constructions, which lift small base graphs (protographs) to larger codes while preserving structure; for instance, introducing local irregularity in protographs enhances decoding thresholds for higher rates and reduces latency in beyond-5G applications.

Turbo Codes

Turbo codes, introduced in 1993 by Claude Berrou, Alain Glavieux, and Punya Thitimajshima, represent a class of parallel concatenated convolutional codes that achieve error correction performance remarkably close to the Shannon limit for a wide range of channel conditions. The name "turbo" originates from the iterative nature of the decoding process, which involves feedback loops between decoders, akin to the turbocharging mechanism in engines that boosts efficiency through successive enhancements. These codes marked a breakthrough by demonstrating bit error rates below 10−510^{-5} at signal-to-noise ratios only 0.5 dB above the theoretical limit for rate-1/2 codes over channels. The construction of turbo codes involves parallel concatenation of two identical recursive systematic convolutional (RSC) encoders, with the input systematically fed to the first encoder and an interleaved version to the second. A key component is the pseudo-random interleaver placed between the encoders, which permutes the input bits to decorrelate the parity outputs and enhance correction against burst errors. To achieve desired rates, puncturing is applied by selectively removing certain parity bits from the combined output, allowing flexibility in trading off rate against . Typical turbo code configurations operate at a code rate of 1/3, producing one systematic bit and two parity bits per input bit, though higher rates like 1/2 are common via puncturing. The size of the interleaver is a critical , as larger interleavers (e.g., thousands of bits) improve asymptotic by reducing but increase latency and ; suboptimal designs can lead to an error floor, where bit error rates plateau at low values (around 10−610^{-6} to 10−710^{-7}) due to low-weight codewords. Careful interleaver design, such as S-random or quadratic polynomials, mitigates this floor while maintaining near-capacity operation. Decoding of turbo codes relies on iterative message-passing between two soft-in soft-out decoders, one for each constituent code, using algorithms that compute probabilities (APPs). The Log-MAP algorithm, a logarithmic-domain of the maximum a posteriori decoder, efficiently calculates APPs by maximizing log-likelihood ratios while avoiding underflow issues through normalization. Alternatively, the Soft Output (SOVA) provides approximations of these APPs via path metric differences in the Viterbi trellis, offering lower complexity at the cost of slightly reduced performance. In each iteration, extrinsic information—refined probabilities excluding prior inputs—is exchanged, progressively improving reliability until convergence or a fixed number of iterations (typically 6-8) is reached. The impact of has been profound, revolutionizing forward error correction by enabling practical implementations that approach theoretical limits, thus inspiring iterative decoding paradigms across . They were standardized in third-generation () mobile systems like for uplink and downlink channels, and in fourth-generation () LTE for control channels, significantly enhancing and reliability in communications. In the 2020s, extensions of have been proposed and analyzed for massive systems, incorporating and joint detection to exploit while maintaining low error rates in high-antenna regimes. To analyze convergence in iterative decoding, metrics quantify the between decoders across iterations. The extrinsic IEI_E at the output of a component decoder, given a priori IAI_A at its input, characterizes decoding reliability, where full reliability corresponds to I=1I = 1 bit (no uncertainty). EXIT (extrinsic information transfer) charts visualize this by plotting IEI_E versus IAI_A curves for each decoder under fixed channel conditions; the area between the component curves forms a "" whose openness predicts successful convergence to low error rates after sufficient iterations. For a rate-1/3 over AWGN, the decoding trajectory traces a path through this , with increasing stepwise until it reaches the (1,1) point, typically after 10-15 iterations for interleaver sizes around 16,384 bits.

Polar Codes

Polar codes, introduced by Erdal Arıkan in 2009, represent the first explicit family of block codes proven to achieve the capacity of symmetric binary-input discrete memoryless channels under low-complexity decoding. This breakthrough relies on the channel polarization phenomenon, in which a recursive transformation of the original channel into N synthetic subchannels occurs, with N=2^n; as n grows large, a fraction approaching the channel capacity becomes nearly error-free (good subchannels), while the remainder approaches complete unreliability (bad subchannels). Due to their capacity-achieving properties and efficient implementation, polar codes were adopted by the 3GPP for coding the enhanced mobile broadband (eMBB) control channels in 5G New Radio standards. The encoding process begins with the generator matrix formed by the n-fold Kronecker power of a 2×2 kernel, typically G2=(1011),G_2 = \begin{pmatrix} 1 & 0 \\ 1 & 1 \end{pmatrix}, yielding a code of length N with rate R = k/N, where k information bits are transmitted. To construct the codeword, the k most reliable subchannels—identified via metrics like mutual information or the Bhattacharyya parameter—are assigned the information bits, while the remaining N-k positions receive frozen bits fixed to zero. The Bhattacharyya parameter Z(W) for a binary-input channel W, defined as Z(W)=∑yW(y∣0)W(y∣1)Z(W) = \sum_y \sqrt{W(y|0)W(y|1)}
Add your contribution
Related Hubs
Contribute something
User Avatar
No comments yet.