Hubbry Logo
Coding theoryCoding theoryMain
Open search
Coding theory
Community hub
Coding theory
logo
8 pages, 0 posts
0 subscribers
Be the first to start a discussion here.
Be the first to start a discussion here.
Coding theory
Coding theory
Coding theory
View on Wikipedia
from Wikipedia
A two-dimensional visualisation of the Hamming distance, a critical measure in coding theory

Coding theory is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods. This typically involves the removal of redundancy and the correction or detection of errors in the transmitted data.

There are four types of coding:[1]

  1. Data compression (or source coding)
  2. Error control (or channel coding)
  3. Cryptographic coding
  4. Line coding

Data compression attempts to remove unwanted redundancy from the data from a source in order to transmit it more efficiently. For example, DEFLATE data compression makes files smaller, for purposes such as to reduce Internet traffic. Data compression and error correction may be studied in combination.

Error correction adds useful redundancy to the data from a source to make the transmission more robust to disturbances present on the transmission channel. The ordinary user may not be aware of many applications using error correction. A typical music compact disc (CD) uses the Reed–Solomon code to correct for scratches and dust. In this application the transmission channel is the CD itself. Cell phones also use coding techniques to correct for the fading and noise of high frequency radio transmission. Data modems, telephone transmissions, and the NASA Deep Space Network all employ channel coding techniques to get the bits through, for example the turbo code and LDPC codes.

History of coding theory

[edit]
This section is an excerpt from History of information theory.[edit]

The decisive event which established the discipline of information theory, and brought it to immediate worldwide attention, was the publication of Claude E. Shannon's classic paper "A Mathematical Theory of Communication" in the Bell System Technical Journal in July and October 1948.

In this revolutionary and groundbreaking paper, the work for which Shannon had substantially completed at Bell Labs by the end of 1944, Shannon for the first time introduced the qualitative and quantitative model of communication as a statistical process underlying information theory, opening with the assertion that

"The fundamental problem of communication is that of reproducing at one point, either exactly or approximately, a message selected at another point."

With it came the ideas of

Shannon’s paper focuses on the problem of how to best encode the information a sender wants to transmit. In this fundamental work he used tools in probability theory, developed by Norbert Wiener, which were in their nascent stages of being applied to communication theory at that time. Shannon developed information entropy as a measure for the uncertainty in a message while essentially inventing the field of information theory.

The binary Golay code was developed in 1949. It is an error-correcting code capable of correcting up to three errors in each 24-bit word, and detecting a fourth.

Richard Hamming won the Turing Award in 1968 for his work at Bell Labs in numerical methods, automatic coding systems, and error-detecting and error-correcting codes. He invented the concepts known as Hamming codes, Hamming windows, Hamming numbers, and Hamming distance.

In 1972, Nasir Ahmed proposed the discrete cosine transform (DCT), which he developed with T. Natarajan and K. R. Rao in 1973.[2] The DCT is the most widely used lossy compression algorithm, the basis for multimedia formats such as JPEG, MPEG and MP3.

Source coding

[edit]
Main article: Data compression

The aim of source coding is to take the source data and make it smaller.

Definition

[edit]

Data can be seen as a random variable , where appears with probability .

Data are encoded by strings (words) over an alphabet .

A code is a function

(or if the empty string is not part of the alphabet).

is the code word associated with .

Length of the code word is written as

Expected length of a code is

The concatenation of code words .

The code word of the empty string is the empty string itself:

Properties

[edit]
  1. is non-singular if injective.
  2. is uniquely decodable if injective.
  3. is instantaneous if is not a proper prefix of (and vice versa).

Principle

[edit]

Entropy of a source is the measure of information. Basically, source codes try to reduce the redundancy present in the source, and represent the source with fewer bits that carry more information.

Data compression which explicitly tries to minimize the average length of messages according to a particular assumed probability model is called entropy encoding.

Various techniques used by source coding schemes try to achieve the limit of entropy of the source. C(x) ≥ H(x), where H(x) is entropy of source (bitrate), and C(x) is the bitrate after compression. In particular, no source coding scheme can be better than the entropy of the source.

Example

[edit]

Facsimile transmission uses a simple run length code. Source coding removes all data superfluous to the need of the transmitter, decreasing the bandwidth required for transmission.

Channel coding

[edit]
Main article: Error detection and correction

The purpose of channel coding theory is to find codes which transmit quickly, contain many valid code words and can correct or at least detect many errors. While not mutually exclusive, performance in these areas is a trade-off. So, different codes are optimal for different applications. The needed properties of this code mainly depend on the probability of errors happening during transmission. In a typical CD, the impairment is mainly dust or scratches.

CDs use cross-interleaved Reed–Solomon coding to spread the data out over the disk.[3]

Although not a very good code, a simple repeat code can serve as an understandable example. Suppose we take a block of data bits (representing sound) and send it three times. At the receiver we will examine the three repetitions bit by bit and take a majority vote. The twist on this is that we do not merely send the bits in order. We interleave them. The block of data bits is first divided into 4 smaller blocks. Then we cycle through the block and send one bit from the first, then the second, etc. This is done three times to spread the data out over the surface of the disk. In the context of the simple repeat code, this may not appear effective. However, there are more powerful codes known which are very effective at correcting the "burst" error of a scratch or a dust spot when this interleaving technique is used.

Other codes are more appropriate for different applications. Deep space communications are limited by the thermal noise of the receiver which is more of a continuous nature than a bursty nature. Likewise, narrowband modems are limited by the noise, present in the telephone network and also modeled better as a continuous disturbance.[citation needed] Cell phones are subject to rapid fading. The high frequencies used can cause rapid fading of the signal even if the receiver is moved a few inches. Again there are a class of channel codes that are designed to combat fading.[citation needed]

Linear codes

[edit]
Main article: Linear code

The term algebraic coding theory denotes the sub-field of coding theory where the properties of codes are expressed in algebraic terms and then further researched.[citation needed]

Algebraic coding theory is basically divided into two major types of codes:[citation needed]

  • Linear block codes
  • Convolutional codes

It analyzes the following three properties of a code – mainly:[citation needed]

  • Code word length
  • Total number of valid code words
  • The minimum distance between two valid code words, using mainly the Hamming distance, sometimes also other distances like the Lee distance

Linear block codes

[edit]
Main article: Block code

Linear block codes have the property of linearity, i.e. the sum of any two codewords is also a code word, and they are applied to the source bits in blocks, hence the name linear block codes. There are block codes that are not linear, but it is difficult to prove that a code is a good one without this property.[4]

Linear block codes are summarized by their symbol alphabets (e.g., binary or ternary) and parameters (n,m,dmin)[5] where

  1. n is the length of the codeword, in symbols,
  2. m is the number of source symbols that will be used for encoding at once,
  3. dmin is the minimum hamming distance for the code.

There are many types of linear block codes, such as

  1. Cyclic codes (e.g., Hamming codes)
  2. Repetition codes
  3. Parity codes
  4. Polynomial codes (e.g., BCH codes)
  5. Reed–Solomon codes
  6. Algebraic geometric codes
  7. Reed–Muller codes
  8. Perfect codes
  9. Locally recoverable code

Block codes are tied to the sphere packing problem, which has received some attention over the years. In two dimensions, it is easy to visualize. Take a bunch of pennies flat on the table and push them together. The result is a hexagon pattern like a bee's nest. But block codes rely on more dimensions which cannot easily be visualized. The powerful (24,12) Golay code used in deep space communications uses 24 dimensions. If used as a binary code (which it usually is) the dimensions refer to the length of the codeword as defined above.

The theory of coding uses the N-dimensional sphere model. For example, how many pennies can be packed into a circle on a tabletop, or in 3 dimensions, how many marbles can be packed into a globe. Other considerations enter the choice of a code. For example, hexagon packing into the constraint of a rectangular box will leave empty space at the corners. As the dimensions get larger, the percentage of empty space grows smaller. But at certain dimensions, the packing uses all the space and these codes are the so-called "perfect" codes. The only nontrivial and useful perfect codes are the distance-3 Hamming codes with parameters satisfying (2r – 1, 2r – 1 – r, 3), and the [23,12,7] binary and [11,6,5] ternary Golay codes.[4][5]

Another code property is the number of neighbors that a single codeword may have.[6] Again, consider pennies as an example. First we pack the pennies in a rectangular grid. Each penny will have 4 near neighbors (and 4 at the corners which are farther away). In a hexagon, each penny will have 6 near neighbors. When we increase the dimensions, the number of near neighbors increases very rapidly. The result is the number of ways for noise to make the receiver choose a neighbor (hence an error) grows as well. This is a fundamental limitation of block codes, and indeed all codes. It may be harder to cause an error to a single neighbor, but the number of neighbors can be large enough so the total error probability actually suffers.[6]

Properties of linear block codes are used in many applications. For example, the syndrome-coset uniqueness property of linear block codes is used in trellis shaping,[7] one of the best-known shaping codes.

Convolutional codes

[edit]
Main article: Convolutional code

The idea behind a convolutional code is to make every codeword symbol be the weighted sum of the various input message symbols. This is like convolution used in LTI systems to find the output of a system, when you know the input and impulse response.

So we generally find the output of the system convolutional encoder, which is the convolution of the input bit, against the states of the convolution encoder, registers.

Fundamentally, convolutional codes do not offer more protection against noise than an equivalent block code. In many cases, they generally offer greater simplicity of implementation over a block code of equal power. The encoder is usually a simple circuit which has state memory and some feedback logic, normally XOR gates. The decoder can be implemented in software or firmware.

The Viterbi algorithm is the optimum algorithm used to decode convolutional codes. There are simplifications to reduce the computational load. They rely on searching only the most likely paths. Although not optimum, they have generally been found to give good results in low noise environments.

Convolutional codes are used in voiceband modems (V.32, V.17, V.34) and in GSM mobile phones, as well as satellite and military communication devices.

Cryptographic coding

[edit]
Main article: Cryptography

Cryptography or cryptographic coding is the practice and study of techniques for secure communication in the presence of third parties (called adversaries).[8] More generally, it is about constructing and analyzing protocols that block adversaries;[9] various aspects in information security such as data confidentiality, data integrity, authentication, and non-repudiation[10] are central to modern cryptography. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, and electrical engineering. Applications of cryptography include ATM cards, computer passwords, and electronic commerce.

Cryptography prior to the modern age was effectively synonymous with encryption, the conversion of information from a readable state to apparent nonsense. The originator of an encrypted message shared the decoding technique needed to recover the original information only with intended recipients, thereby precluding unwanted persons from doing the same. Since World War I and the advent of the computer, the methods used to carry out cryptology have become increasingly complex and its application more widespread.

Modern cryptography is heavily based on mathematical theory and computer science practice; cryptographic algorithms are designed around computational hardness assumptions, making such algorithms hard to break in practice by any adversary. It is theoretically possible to break such a system, but it is infeasible to do so by any known practical means. These schemes are therefore termed computationally secure; theoretical advances, e.g., improvements in integer factorization algorithms, and faster computing technology require these solutions to be continually adapted. There exist information-theoretically secure schemes that provably cannot be broken even with unlimited computing power—an example is the one-time pad—but these schemes are more difficult to implement than the best theoretically breakable but computationally secure mechanisms.

Line coding

[edit]
Main article: Line code

A line code (also called digital baseband modulation or digital baseband transmission method) is a code chosen for use within a communications system for baseband transmission purposes.

Line coding is often used for digital data transport. It consists of representing the digital signal to be transported by an amplitude- and time-discrete signal that is optimally tuned for the specific properties of the physical channel (and of the receiving equipment). The waveform pattern of voltage or current used to represent the 1s and 0s of a digital data on a transmission link is called line encoding. The common types of line encoding are unipolar, polar, bipolar, and Manchester encoding.

Other applications of coding theory

[edit]

Another concern of coding theory is designing codes that help synchronization. A code may be designed so that a phase shift can be easily detected and corrected and that multiple signals can be sent on the same channel.[citation needed]

Another application of codes, used in some mobile phone systems, is code-division multiple access (CDMA). Each phone is assigned a code sequence that is approximately uncorrelated with the codes of other phones.[citation needed] When transmitting, the code word is used to modulate the data bits representing the voice message. At the receiver, a demodulation process is performed to recover the data. The properties of this class of codes allow many users (with different codes) to use the same radio channel at the same time. To the receiver, the signals of other users will appear to the demodulator only as a low-level noise.[citation needed]

Another general class of codes are the automatic repeat-request (ARQ) codes. In these codes the sender adds redundancy to each message for error checking, usually by adding check bits. If the check bits are not consistent with the rest of the message when it arrives, the receiver will ask the sender to retransmit the message. All but the simplest wide area network protocols use ARQ. Common protocols include SDLC (IBM), TCP (Internet), X.25 (International) and many others. There is an extensive field of research on this topic because of the problem of matching a rejected packet against a new packet. Is it a new one or is it a retransmission? Typically numbering schemes are used, as in TCP."RFC793". RFCS. Internet Engineering Task Force (IETF). September 1981.

Group testing

[edit]

Group testing uses codes in a different way. Consider a large group of items in which a very few are different in a particular way (e.g., defective products or infected test subjects). The idea of group testing is to determine which items are "different" by using as few tests as possible. The origin of the problem has its roots in the Second World War when the United States Army Air Forces needed to test its soldiers for syphilis.[11]

Analog coding

[edit]

Information is encoded analogously in the neural networks of brains, in analog signal processing, and analog electronics. Aspects of analog coding include analog error correction,[12] analog data compression[13] and analog encryption.[14]

Neural coding

[edit]

Neural coding is a neuroscience-related field concerned with how sensory and other information is represented in the brain by networks of neurons. The main goal of studying neural coding is to characterize the relationship between the stimulus and the individual or ensemble neuronal responses and the relationship among electrical activity of the neurons in the ensemble.[15] It is thought that neurons can encode both digital and analog information,[16] and that neurons follow the principles of information theory and compress information,[17] and detect and correct[18] errors in the signals that are sent throughout the brain and wider nervous system.

See also

[edit]

Notes

[edit]

References

[edit]
Revisions and contributorsEdit on WikipediaRead on Wikipedia

Coding theory

View on Grokipedia
from Grokipedia
Coding theory is a branch of and focused on the , , and of codes, including source codes for efficient data compression and error-detecting and error-correcting codes to ensure reliable transmission and storage of digital information in the presence of , interference, or other distortions. These codes introduce controlled into messages, allowing the detection and correction of errors without retransmission, thereby optimizing the balance between data efficiency and robustness in communication systems. The field traces its origins to Claude Shannon's seminal 1948 paper, "," which introduced the —proving that arbitrarily reliable communication is achievable over noisy channels at rates approaching the channel's capacity, provided sufficient redundancy is added. Practical advancements followed in 1950 with Richard Hamming's invention of the binary , a single-error-correcting linear code that addressed error issues in early computers at Bell Laboratories. Subsequent milestones include the 1959–1960 development of BCH codes by Hocquenghem, Bose, and Ray-Chaudhuri for multiple-error correction, and the 1960 introduction of Reed-Solomon codes by Reed and Solomon, which exploit finite field algebra for efficient implementation. At its core, coding theory revolves around and linear codes defined over finite fields Fq\mathbb{F}_q, parameterized by length nn, dimension kk (information symbols), and minimum dd, where the error-correcting capability tt satisfies t=⌊(d−1)/2⌋t = \lfloor (d-1)/2 \rfloor. Linear codes, generated by k×nk \times n matrices, enable efficient encoding and decoding via syndrome computations, with subclasses like cyclic codes (invariant under cyclic shifts) facilitating hardware implementation through polynomials dividing xn−1x^n - 1. Advanced constructions, such as low-density parity-check (LDPC) codes and , approach Shannon's limits in practice, supported by iterative decoding algorithms. Coding theory's principles are integral to modern technologies, underpinning error correction in wireless communications (e.g., and standards), deep-space telemetry (e.g., missions), and data storage systems including hard drives, , and emerging DNA-based storage. In cryptography, code-based schemes like the (1978) leverage the hardness of decoding general linear codes for post-quantum secure public-key , resistant to quantum attacks despite large key sizes. Recent extensions apply to for fault-tolerant and resilient deep neural networks against adversarial noise.

Fundamentals

Definition and Basic Concepts

Coding theory is the study of mathematical techniques for the efficient and reliable representation, transmission, and storage of information through the use of codes. These techniques introduce controlled into data to mitigate issues such as , errors, or inefficiencies in communication systems. At its core, coding theory draws from , , and probability to design codes that optimize performance metrics like efficiency and robustness. A fundamental concept in coding theory is the itself, defined as a mapping from a set of source symbols (messages) to a set of codewords, where each codeword consists of symbols drawn from a finite of size qq (e.g., binary with q=2q = 2). The size determines the symbol set, while the code length nn specifies the number of symbols in each codeword. For , which process in fixed blocks, the number of symbols is denoted by kk, and the code rate RR, measuring the efficiency of transmission, is given by R=kn.R = \frac{k}{n}. More generally, for any code, the rate can be expressed as R=log⁡2∣M∣n,R = \frac{\log_2 |M|}{n}, where ∣M∣|M| is the size of the message set. Higher rates indicate less redundancy and greater compression, but often at the cost of reduced error resilience. Codes are distinguished by their length structure: fixed-length codes assign the same number of symbols to every codeword, simplifying encoding and decoding processes, whereas variable-length codes allow codewords of differing lengths, enabling more efficient representation of sources with uneven symbol probabilities (e.g., in text compression). Fixed-length codes are prevalent in block-based error control, while variable-length codes are key to lossless data compression. Coding theory encompasses four primary types, each addressing distinct aspects of handling: source coding, which focuses on compression to remove and minimize storage or bandwidth needs; channel coding, which adds for during transmission over noisy media; line coding, which formats signals for physical transmission channels to ensure and compatibility (e.g., converting to electrical pulses); and cryptographic coding, which employs codes to secure against unauthorized access through and related mechanisms. These types often intersect, as in systems combining channel and cryptographic elements. Coding theory is foundational to , with Shannon's establishing fundamental limits on reliable transmission rates over noisy channels.

Information Theory Foundations

Coding theory is fundamentally rooted in , which provides the mathematical limits on data compression and reliable communication over noisy channels. Claude Shannon's seminal work established these foundations, demonstrating that can be quantified and transmitted efficiently under constraints. Specifically, , also known as the noiseless coding theorem, asserts that the minimum average number of bits required to represent the output of a discrete memoryless source is equal to its , providing the fundamental limit for lossless data compression. In parallel, the channel coding theorem specifies that reliable communication is possible over a noisy channel at rates approaching the , with arbitrarily low error probability, as long as the code rate does not exceed this capacity. These theorems underscore the theoretical boundaries that guide the design of practical coding schemes. Central to these limits is the concept of , which measures the uncertainty or average of a . For a discrete XX with p(x)p(x), the H(X)H(X) is defined as H(X)=−∑xp(x)log⁡2p(x),H(X) = -\sum_{x} p(x) \log_2 p(x), where the sum is over the possible values of XX, and the logarithm is base 2 to yield bits as the unit of . This quantity sets the lower bound for the average codeword length in lossless source coding: no uniquely decodable code can achieve an average length less than H(X)H(X) bits per symbol in the limit of long sequences. Entropy thus quantifies the inherent redundancy in a source, enabling compression ratios that approach this bound for large blocks. For communication over noisy channels, the channel capacity CC represents the supreme achievable rate for reliable transmission. Formally, CC is the maximum of the I(X;Y)I(X; Y) over all possible input distributions to the channel, where XX is the input and YY the output: C=max⁡p(x)I(X;Y)=max⁡p(x)[H(Y)−H(Y∣X)].C = \max_{p(x)} I(X; Y) = \max_{p(x)} \left[ H(Y) - H(Y|X) \right]. I(X;Y)I(X; Y) captures the reduction in uncertainty about YY given knowledge of XX, or vice versa. A canonical example is the binary symmetric channel (BSC), a discrete memoryless channel that flips each input bit with crossover probability pp (where 0<p<0.50 < p < 0.5), independently. The capacity of the BSC is given by C=1−H2(p),C = 1 - H_2(p), with the binary entropy function H2(p)=−plog⁡2p−(1−p)log⁡2(1−p)H_2(p) = -p \log_2 p - (1-p) \log_2 (1-p). This formula illustrates how noise degrades the effective rate, approaching 1 bit per channel use as p→0p \to 0 (noiseless case) and 0 as p→0.5p \to 0.5 (pure noise). In code design, these information-theoretic limits impose a fundamental trade-off between rate (information efficiency), reliability (error performance), and complexity (computational resources for encoding and decoding). Codes operating near capacity achieve high reliability but often require increased complexity, such as longer codewords or sophisticated algorithms, to approach the theoretical bounds without exceeding them. This interplay drives ongoing research in coding theory to balance these factors for practical systems.

Historical Development

Early Contributions

The foundations of coding theory emerged in the mid-20th century amid efforts to improve reliable data transmission over noisy channels, particularly influenced by World War II cryptanalysis. During the war, contributed to cryptographic research at Bell Laboratories and for U.S. military intelligence, analyzing secure communication systems and the effects of noise on signals, which directly informed his later theoretical work on error-resistant coding. These wartime activities highlighted the need for systematic methods to detect and mitigate transmission errors, bridging cryptography and early communication engineering. In the 1940s, initial applications of error handling appeared in telegraphy and nascent computing. Telegraph systems, reliant on long-distance wire transmission, used rudimentary techniques such as mutilation tables—lookup systems to identify garbled characters—and check letters or parity-like sums appended to messages for basic error detection. These methods addressed common issues like signal distortion from atmospheric interference or line faults, though they offered only detection, not correction, and required operator intervention. Early electronic computers, such as the ENIAC developed in 1945, lacked built-in error-correcting mechanisms; instead, programmers and operators performed manual checks on outputs and reran calculations to handle vacuum tube failures or wiring errors, underscoring the era's reliance on human oversight for reliability. The pivotal theoretical advancement occurred in 1948 when Claude Shannon published "A Mathematical Theory of Communication" in the Bell System Technical Journal, laying the groundwork for modern coding theory by proving that reliable communication is possible up to a channel's capacity despite noise, provided the data rate stays below this limit. Shannon introduced entropy as a measure of information uncertainty, enabling the quantification of source efficiency, and derived the channel coding theorem, which established fundamental bounds on error-free transmission. This work shifted coding from ad hoc practices to a rigorous mathematical framework, influencing all subsequent developments in the field. Shortly thereafter, in 1949, Swiss mathematician Marcel J. E. Golay introduced the binary Golay code in his seminal note "Notes on Digital Coding," published in the Proceedings of the IRE. This [23,12] linear code, with a minimum distance of 7, represents one of the earliest known perfect error-correcting codes, capable of correcting up to 3 errors in 23-bit blocks while achieving the theoretical for single-error correction extended to multiple errors. Golay's discovery, derived intuitively through geometric and combinatorial insights, demonstrated practical attainment of Shannon's limits for specific parameters and inspired further exploration of nonlinear and perfect codes in noisy environments like early digital telephony.

Key Advances and Milestones

In 1950, Richard Hamming developed the first practical error-correcting codes capable of single-error correction, known as , which were designed to address errors in early computing systems like punched card readers at Bell Labs. These binary linear codes, with parity bits added to detect and correct single-bit errors, marked a shift from theoretical error detection to actionable correction in digital systems. Cyclic codes, first studied by E. Prange in 1957, form a class of linear block codes where any cyclic shift of a codeword remains a codeword, providing efficient encoding and decoding structures. Building on this, Alexis Hocquenghem proposed in 1959 a family of cyclic codes capable of correcting multiple errors, later named BCH codes after independent work by Raj Chandra Bose and Dwijendra K. Ray-Chaudhuri in 1960. These BCH codes, defined over finite fields, could correct up to t errors with designed distance, enabling robust error control in communications. In 1960, Irving S. Reed and Gustave Solomon introduced Reed-Solomon codes, a subclass of non-binary BCH codes based on polynomial evaluation over finite fields, which are particularly effective for correcting burst errors and erasures. These codes, with length equal to the field size and minimum distance determined by the number of parity symbols, found immediate applications in storage and satellite communications due to their optimal distance properties. By the 1990s, Reed-Solomon codes were widely adopted in consumer technologies, such as cross-interleaved Reed-Solomon coding in compact discs (CDs) for error correction during audio playback and in digital versatile discs (DVDs) for reliable data retrieval. For convolutional codes, introduced earlier in the 1950s, Andrew J. Viterbi proposed in 1967 an efficient maximum-likelihood decoding algorithm using dynamic programming, now known as the , which computes the most likely sequence by minimizing a path metric over a trellis structure. This advancement enabled practical implementation of convolutional codes in real-time systems like space communications, reducing computational complexity from exponential to linear in sequence length. Low-density parity-check (LDPC) codes, originally proposed by Robert G. Gallager in 1962 as sparse parity-check matrices allowing iterative decoding via message passing, initially faced implementation challenges due to decoding complexity. Their revival in the 1990s, led by David J.C. MacKay and Radford M. Neal, demonstrated through simulations that LDPC codes could achieve performance near the Shannon limit for binary channels using belief propagation decoding, sparking renewed interest and adoption in standards like Wi-Fi and DVB-S2. In 1993, Claude Berrou, Alain Glavieux, and Punya Thitimajshima introduced turbo codes, parallel concatenated convolutional codes with iterative decoding that exchanged soft information between component decoders, achieving bit error rates within 0.5 dB of the Shannon limit for moderate block lengths. This breakthrough demonstrated that practical codes could approach theoretical limits established by Claude Shannon in 1948, influencing subsequent code designs. A significant milestone in source coding occurred in 1974 with the development of the discrete cosine transform (DCT) by Nasir Ahmed, T. Natarajan, and K.R. Rao, which provided an efficient method for compressing images and signals by concentrating energy in low-frequency coefficients. The DCT, approximating the optimal Karhunen-Loève transform for correlated data, became foundational for standards like in the 1990s, enabling widespread digital image storage and transmission. Finally, in 2009, Erdal Arikan introduced polar codes, constructed via channel polarization where synthetic channels evolve to perfect or noisy states under recursive transformations, provably achieving capacity for any symmetric binary-input discrete memoryless channel with low encoding and decoding complexity. These codes, decoded using successive cancellation, represented the first explicit capacity-achieving construction for such channels, leading to their adoption in 5G wireless standards.

Source Coding

Principles and Properties

Source coding aims to represent the output of a discrete information source using a minimal number of symbols, thereby minimizing the average codeword length by exploiting and removing redundancy in the source data. This process maps source symbols or sequences to codewords in a way that preserves the information content while reducing the total bits required for storage or transmission. A key property of effective source codes is unique decodability, ensuring that every possible sequence of codewords corresponds to exactly one sequence of source symbols, preventing ambiguity during decoding. For uniquely decodable codes over a binary alphabet with codeword lengths lil_i, the Kraft inequality states that ∑2−li≤1\sum 2^{-l_i} \leq 1, providing a necessary and sufficient condition for the existence of such codes. Prefix codes, a subset of uniquely decodable codes, possess the additional property that no codeword is a prefix of another, enabling instantaneous decoding without lookahead. The principle of entropy coding establishes that the average codeword length LL for any uniquely decodable code satisfies L≥H(X)L \geq H(X), where H(X)=−∑p(xi)log⁡2p(xi)H(X) = -\sum p(x_i) \log_2 p(x_i) is the entropy of the source random variable XX; optimal codes achieve equality in the limit of block coding over long sequences. Source coding typically involves fixed-to-variable length mappings, where fixed-length source symbols are encoded into variable-length codewords to match symbol probabilities, or variable-to-fixed length mappings, where variable-length source sequences are encoded into fixed-length codewords for efficient block processing. Source coding is distinguished as lossless or lossy: lossless coding reconstructs the exact source output, bounded by the source coding theorem at the entropy rate, while lossy coding allows controlled distortion to achieve lower rates via the rate-distortion function R(D)R(D), the minimum rate for average distortion at most DD.

Common Techniques and Examples

Huffman coding constructs optimal prefix codes for a set of symbols with known probabilities by building a variable-length binary tree, where more frequent symbols receive shorter codewords to minimize the average code length. Introduced by David A. Huffman in 1952, this method generates uniquely decodable codes without prefix ambiguities. For example, consider four symbols A, B, C, and D with probabilities 0.4, 0.3, 0.2, and 0.1, respectively. The resulting Huffman tree assigns codewords 0 to A, 10 to B, 110 to C, and 111 to D, yielding an average length of 1.9 bits per symbol, close to the entropy of approximately 1.85 bits. Arithmetic coding represents an entire sequence of symbols as a single fractional number within the unit interval [0, 1), subdividing the interval based on cumulative probabilities to encode messages more efficiently than fixed-length or Huffman codes. Popularized by Witten, Neal, and Cleary in 1987, it overcomes the limitations of integer-length codewords, allowing fractional bit allocations and achieving compression ratios nearer to the theoretical entropy limit. Run-length encoding (RLE) compresses data by replacing consecutive repeats of the same symbol with a single instance and a count of the run length, making it ideal for sources with high redundancy like binary images. This simple technique is employed in fax machines under the CCITT Group 3 standard, where runs of white or black pixels are encoded to reduce transmission bandwidth. For instance, the sequence "AAAAAABBBBC" becomes (A,5), (B,4), (C,1), significantly shortening repetitive patterns. The Lempel-Ziv-Welch (LZW) algorithm performs dictionary-based compression by incrementally building a codebook of frequently occurring substrings during encoding, replacing matches with short dictionary indices. Developed by Terry Welch in 1984 as an adaptation of earlier Lempel-Ziv work, LZW is lossless and adaptive, requiring no prior knowledge of symbol probabilities. It powers formats such as GIF for images and ZIP for general files, where dictionary entries grow dynamically to capture repeating patterns. In practice, the baseline JPEG standard applies the discrete cosine transform (DCT) to image blocks for energy compaction, followed by quantization and Huffman coding to achieve lossy compression suitable for photographic data. As a precursor to Huffman coding, Shannon-Fano coding divides symbols into groups of roughly equal probability in a top-down manner to assign code lengths. These techniques satisfy the Kraft inequality for prefix-free decodability. Huffman coding typically yields average lengths within 1 bit of the source entropy, while arithmetic coding approaches the entropy bound more closely, often outperforming Huffman by 5-10% in efficiency for many sources.

Channel Coding

Fundamentals of Error Control

Error control in channel coding addresses the challenge of transmitting data reliably over noisy communication channels, where errors can occur due to interference, distortion, or other impairments. The primary goal is to add controlled redundancy to the transmitted signal, enabling the receiver to detect and potentially correct errors without requiring retransmission. This contrasts with source coding, which focuses on efficient representation, by introducing redundancy specifically to combat channel-induced errors. Fundamental to this process is the modeling of errors, typically assuming discrete channels like the , where bits flip with a certain probability. Error detection identifies the presence of errors in a received codeword, while error correction goes further by recovering the original message from the erroneous version. A code's capability depends on its minimum dd, the smallest number of positions in which any two distinct codewords differ. For detection, a code with minimum distance dd can detect up to d−1d-1 errors, as any change fewer than dd positions cannot transform one valid codeword into another. For correction, it can correct up to t=⌊(d−1)/2⌋t = \lfloor (d-1)/2 \rfloor errors, since spheres of radius tt around codewords are disjoint, allowing unique decoding to the nearest codeword. These principles were established in early work on error-correcting codes. A key theoretical limit on code performance is the Hamming bound, also known as the sphere-packing bound, which provides an upper bound on the size of a code. For a binary code of length nn, minimum distance d=2t+1d = 2t+1, and MM codewords, the bound states: M≤2n∑k=0t(nk),M \leq \frac{2^n}{\sum_{k=0}^{t} \binom{n}{k}}, where the denominator represents the volume of a Hamming sphere of radius tt. This bound arises from the non-overlapping packing of such spheres in the space of all possible nn-bit vectors, limiting how many codewords can fit while ensuring error correction up to tt errors. Codes achieving this bound are called perfect codes, such as the Hamming codes for t=1t=1. The bound highlights the trade-off between code rate (information bits per total bits) and error-correcting capability, approaching channel capacity limits for reliable communication. Simple parity-check codes illustrate basic error detection. In a single parity-check code, an extra bit is appended to a block of data bits to make the total number of 1s even (even parity) or odd (odd parity). This achieves minimum distance d=2d=2, detecting any single error since it flips the parity. For example, transmitting 101 with even parity adds a 1, yielding 1011; a single flip to 1111 changes the parity to odd, signaling an error. Such codes are widely used for basic integrity checks but cannot correct errors. Repetition codes provide a straightforward approach to error correction by repeating each data bit multiple times. In a triple repetition code (n=3kn=3k for kk data bits), each bit is sent three times, yielding d=3d=3 and correcting t=1t=1 error via majority voting at the receiver. For instance, sending 000 for bit 0 or 111 for bit 1 allows correction if at most one repetition is erroneous. While effective for low error rates, repetition codes have low efficiency (rate 1/31/3) due to high redundancy, making them suitable only for very noisy channels or as pedagogical examples. Error control strategies differ in their mechanisms: forward error correction (FEC) embeds redundancy in the initial transmission for direct correction, while automatic repeat request (ARQ) detects errors and requests retransmission of the erroneous block. FEC offers low latency and works well in high-delay or broadcast scenarios but requires higher bandwidth due to redundancy; ARQ is bandwidth-efficient for low error rates but introduces variable delay from retransmissions and feedback overhead. Hybrid schemes combine both for optimized performance, such as using FEC for correction and ARQ for residual errors. These trade-offs are central to practical system design. Channel coding distinguishes between block and stream approaches. Block codes process fixed-length segments independently, mapping kk information bits to n>kn > k code bits, as in parity or repetition examples, enabling straightforward parallel decoding but potential burst error sensitivity. Stream codes, in contrast, encode data continuously without fixed boundaries, often using convolutional structures for sequential processing, which better handles but requires more complex decoding. The choice depends on application constraints like delay and error patterns.

Linear Block Codes

Linear block codes constitute a fundamental class of error-correcting codes in coding theory, defined as k-dimensional subspaces of the n-dimensional over a GF(q), denoted as an [n, k, d]_q code where d is the minimum . The codewords are all possible linear combinations of k linearly independent vectors in GF(q)^n, and the entire code forms a closed under addition and . A G, of size k × n and full rank k, has rows that form a basis for the code, such that any codeword c can be expressed as c = m G for a message vector m ∈ GF(q)^k. Dually, the parity-check matrix H, of size (n - k) × n and full rank (n - k), satisfies H G^T = 0, ensuring that c H^T = 0 for all codewords c, which enforces the parity checks defining the code. A convenient representation for encoding and analysis is the systematic form of the , where G = [I_k | P] with I_k the k × k and P a k × (n - k) matrix containing the parity submatrix. In this form, the first k positions of a codeword directly correspond to the message bits m, while the remaining n - k positions are parity symbols computed as m P, yielding the codeword c = [m | m P]. Not all linear codes admit a systematic without , but row operations on G can achieve this form while preserving the code's properties. This structure simplifies encoding, as the message appears unaltered in the codeword, facilitating applications in digital communications and storage. Decoding linear block codes often relies on syndrome decoding, which leverages the parity-check matrix to detect and correct s without exhaustive search. For a received vector r = c + e, where e is the vector, the s = r H^T = e H^T ∈ GF(q)^{n-k} is computed and depends solely on e, independent of the transmitted codeword c. If the patterns are limited (e.g., weight at most t = ⌊(d-1)/2⌋), a lookup table or algebraic solver can identify e by matching s to known s, enabling correction by subtracting e from r. This method is efficient for codes with structured H, reducing complexity from O(q^n) to operations in n. A prominent example of linear block codes is the binary , specifically the (7,4) code with minimum distance d=3, capable of correcting any single error in 7-bit blocks. Its parity-check matrix H consists of all 7 nonzero binary vectors of 3 as columns, ensuring that each possible single-error position produces a unique nonzero syndrome corresponding to that column. Introduced by in 1950, this code detects up to two errors and corrects one, serving as a foundational single-error-correcting mechanism in early and systems. Generalizations to higher dimensions yield the family, with 2^m - 1, dimension 2^m - 1 - m, and d=3 over GF(2). Cyclic codes form an important subclass of linear , characterized by the property that any cyclic shift of a remains a , enabling efficient implementation via shift registers. Represented algebraically, correspond to of degree less than n over GF(q), and the is the ideal generated by a monic generator polynomial g(x) of degree n - k that divides x^n - 1 in GF(q). The roots of g(x) determine the code's error-correcting capability, as the parity-check h(x) = (x^n - 1)/g(x) defines the dual code. First studied systematically in the late , cyclic codes facilitate algebraic decoding and are widely used due to their convolutional-like hardware efficiency despite fixed block structure. Among cyclic codes, BCH codes are designed for multiple-error correction by specifying consecutive roots of the generator polynomial as powers of a primitive nth root of unity in an extension field. Introduced independently by Alexis Hocquenghem in 1959 and by and Dinesh K. Ray-Chaudhuri in 1960, binary BCH codes of designed distance δ can correct up to t = ⌊(δ-1)/2⌋ errors, with length n = 2^m - 1 and dimension k ≥ n - m t. The generator polynomial g(x) is the of minimal polynomials of α^j for j = 1 to δ-1, where α is a primitive element of GF(2^m). These codes achieve near-optimal parameters for practical error correction in channels with burst errors. Reed-Solomon codes, a non-binary subclass of cyclic BCH codes, operate over GF(q) with length n = q - 1 (or shortened), using evaluation points as powers of a primitive element for maximum distance separable (MDS) properties. Developed by Irving S. Reed and Gustave Solomon in , these codes have dimension k, minimum distance d = n - k + 1, and correct up to t = ⌊(n - k)/2⌋ symbol errors by choosing g(x) with δ - 1 consecutive roots starting from a fixed primitive element. As cyclic codes, codewords are multiples of g(x) x^n - 1, but their MDS nature ensures optimal trade-off between rate and error correction, making them essential in applications like QR codes, satellite communications, and digital video broadcasting. The algebraic structure allows efficient decoding via Berlekamp-Massey algorithm for error locations and Forney's formula for magnitudes.

Convolutional Codes

Convolutional codes form a class of error-correcting codes tailored for encoding continuous streams of data, where the output depends not only on the current input but also on a finite number of previous inputs, providing robustness against errors in noisy channels like those in and communications. Introduced by Peter Elias in 1955, these codes are linear over finite fields and differ from by processing data in a streaming fashion without fixed block boundaries. Their structure enables efficient hardware implementation and powerful decoding algorithms, making them foundational in standards for deep-space and mobile networks. The encoder for a convolutional code is typically realized using a shift-register , where the state is defined by the contents of K−1K-1 elements, and KK denotes the constraint , representing the number of shifts over which an input bit influences the output. The code rate is given by k/nk/n, where kk input bits produce nn output bits per time step, often with k=1k=1 and n=2n=2 for rate 1/21/2 codes. This setup can be represented by a trellis diagram, a depicting states as nodes and transitions as edges labeled with input-output pairs, which visualizes the code's evolution over time and facilitates decoding. Encoding proceeds by convolving the input bit stream with generator sequences gig_i, which are binary sequences or polynomials defining linear combinations of current and past inputs to form the output bits; for a rate 1/21/2 code, two such generators produce the parity bits. For instance, if the input is x=(x0,x1,… )x = (x_0, x_1, \dots), the first output stream is v(1)(t)=∑j=0K−1x(t−j)g1(j)mod  2v^{(1)}(t) = \sum_{j=0}^{K-1} x(t-j) g_1(j) \mod 2. The free distance dfreed_{\text{free}}, analogous to the minimum distance in , is the minimum of any nonzero code sequence, determining the code's error-detection and correction capability. Decoding convolutional codes often employs the , a maximum-likelihood method introduced by in 1967, which uses dynamic programming to find the most probable input sequence by tracing the lowest-metric path through the trellis based on branch metrics like to the received symbols. The algorithm's complexity is O(2K)O(2^K) operations per decoded bit, scaling exponentially with the constraint length due to the 2K−12^{K-1} states and two branches per state, though practical implementations prune unlikely paths for efficiency. A prominent example is the standard rate 1/21/2, constraint length 7 , widely adopted for deep-space communications under CCSDS recommendations, with generator polynomials g1=1718g_1 = 171_8 (1111001 in binary) and g2=1338g_2 = 133_8 (1011011 in binary), achieving a free distance of 10 for robust error correction over power-limited links. This code processes data streams, often concatenated with outer codes for enhanced performance in missions like Voyager. To adapt the rate for bandwidth-constrained scenarios, puncturing selectively deletes bits from the encoded stream according to a predefined pattern, yielding higher-rate codes (e.g., from 1/21/2 to 3/43/4) while retaining the same encoder and depuncturing during Viterbi decoding, though at the of reduced free . This technique, balancing coding gain and , is integral to standards like those in satellite broadcasting.

Modern Error-Correcting Codes

Modern error-correcting codes, developed primarily from the onward, represent a significant advancement in achieving performance close to the theoretical Shannon limits for reliable communication over noisy channels. These codes leverage iterative decoding techniques and sophisticated constructions to enable near-capacity error correction with practical complexity, surpassing the capabilities of earlier linear block and convolutional codes. Key examples include low-density parity-check (LDPC) codes, , and polar codes, each optimized for specific regimes of code length, rate, and channel conditions. Their adoption in standards like and has driven widespread deployment in high-speed wireless systems. Low-density parity-check (LDPC) codes are defined by sparse parity-check matrices, where each column and row contains only a small number of 1s, resulting in a graph-based structure that facilitates efficient decoding. Introduced by , these codes use iterative decoding, an algorithm that passes messages between variable and check nodes on a Tanner graph representation of the parity-check matrix, converging to near-maximum-likelihood for high-rate codes. This sparsity ensures low decoding , scaling linearly with code length, making LDPC codes suitable for hardware implementations in real-time applications. For binary symmetric channels, LDPC codes with rates above 0.8 can achieve bit error rates below 10^{-5} at signal-to-noise ratios within 0.3 dB of capacity. Turbo codes, introduced by Claude Berrou, Alain Glavieux, and Punya Thitimajshima in 1993, consist of parallel concatenated convolutional codes, where information bits are encoded by two or more systematic convolutional encoders separated by a pseudo-random interleaver to decorrelate the inputs. This structure exploits the interleaving to create redundancy that iterative decoding can exploit effectively. Decoding employs iterative maximum (MAP) probability estimation, often using the log-MAP algorithm to compute branch metrics in the log domain, avoiding underflow issues in probabilistic computations. The interleaver size and constituent code polynomials are tuned to minimize correlation, enabling to approach the Shannon limit with bit error rates near 10^{-5} at 0.5 dB from capacity for code rates around 1/3. Polar codes, introduced by Erdal Arikan in 2009, achieve capacity through a recursive channel polarization process, where a block of N synthetic channels is constructed from N independent uses of a binary-input discrete memoryless channel, polarizing them into nearly perfect (low-error) and noisy (high-error) subchannels as N grows large. Information bits are placed on the reliable subchannels, while frozen bits (set to constants) occupy the unreliable ones, with the selection based on channel reliability measures like Bhattacharyya parameters. Decoding uses successive cancellation, processing bits sequentially and feeding back decisions to refine subsequent estimates, though list-based variants improve performance for finite lengths. For short block lengths up to 1024 bits, polar codes provide reliable error correction in the waterfall region of the error-rate curve, with complexity O(N log N). In terms of performance, both turbo and LDPC codes routinely operate within less than 1 dB of the Shannon capacity for moderate to long block lengths (thousands of bits) and rates from 1/3 to 8/9, demonstrating frame error rates below 10^{-3} in additive white Gaussian noise channels. Polar codes, while asymptotically capacity-achieving, excel for shorter blocks (under 512 bits), offering lower latency decoding suitable for control signaling, though they may require CRC-aided list decoding to match turbo/LDPC in the error floor region. These metrics establish their superiority over non-iterative methods, with LDPC and turbo codes providing throughput gains of up to 20% in capacity-limited scenarios. Applications of these codes span modern wireless standards: LDPC codes are employed in the data channels of New Radio (NR) for enhanced (eMBB) and in (IEEE 802.11ax) for high-throughput links, leveraging their parallelizable decoding for multi-gigabit rates. Polar codes are standardized for NR control channels and broadcast signaling in eMBB and massive machine-type communications (mMTC), where short payloads demand low-latency reliability. , while largely succeeded by LDPC in , remain in use for legacy LTE systems and satellite communications.

Line Coding

Basic Methods

Line coding techniques convert binary streams into analog signals suitable for transmission over channels, primarily to maintain DC balance (zero average voltage to prevent signal distortion over long distances), enable through detectable transitions, and optimize bandwidth usage by shaping the signal . These methods address challenges in transmission, such as and timing recovery, without relying on higher-layer error correction mechanisms. Unipolar non-return-to-zero (NRZ) encoding represents binary 0 as a level (typically 0 V) and binary 1 as a level (positive ), with the signal maintaining its level throughout the bit period without returning to zero between bits. This scheme is simple to implement and requires minimal bandwidth, as the continuous part of the power (PSD) is proportional to Tb2\sinc2(πTbf)T_b^2 \sinc^2(\pi T_b f), where TbT_b is the bit duration, concentrating most energy around low frequencies but introducing a significant DC component that can cause baseline wander in AC-coupled systems. However, long sequences of identical bits lead to synchronization issues, as no transitions occur for . Bipolar alternate mark inversion (AMI) improves on unipolar schemes by using three voltage levels: binary 0 is represented as 0 V, while binary 1 alternates between positive (+V) and negative (-V) pulses, ensuring no two consecutive 1s have the same polarity. This alternation achieves perfect DC balance with zero average voltage, making it suitable for long-distance transmission, and its PSD is ∣P(f)∣2/Tbsin⁡2(πTbf)|P(f)|^2 / T_b \sin^2(\pi T_b f), which eliminates low-frequency components and provides a narrower bandwidth than return-to-zero variants. Additionally, AMI aids error detection, as a single polarity error violates the alternation rule, and it was commonly used in early () systems for its properties via pulse transitions. Drawbacks include potential synchronization loss during long runs of 0s, often mitigated by variants like bipolar with 8-zero substitution (B8ZS). Manchester encoding, also known as biphase or phase encoding, embeds clock information directly into the by creating a transition at the of each period: a binary is low-to-high, and a binary 1 is high-to-low (or vice versa, depending on convention). This self-clocking property ensures reliable synchronization without external clock signals, while the mid-bit transitions and equal high/low durations provide DC balance, with a PSD of ∣P(f)∣2/Tb|P(f)|^2 / T_b showing no DC content but requiring twice the bandwidth of NRZ (first null at twice the ). It is widely adopted in 10 Mbps Ethernet standards (), where it supports robust timing recovery over twisted-pair cabling. The guaranteed transition per bit reduces the impact of noise but increases transmission overhead. Multilevel transmit-3 (MLT-3) encoding uses three voltage levels (-V, 0, +V) in a cyclic manner: for a binary 1, the signal cycles through the levels in sequence (e.g., 0 to +V to 0 to -V), while a binary 0 holds the current level, resulting in fewer transitions and a more compact spectrum resembling a . This reduces bandwidth requirements to about 31 MHz for a 100 Mbps , minimizing (EMI) and enabling higher data rates over limited cabling. MLT-3 achieves DC balance through its balanced level transitions and is specified in the IEEE 802.3u standard for 100BASE-TX , where it combines with 4B/5B block coding to transmit 100 Mbps over Category 5 twisted-pair wires. Its PSD features reduced high-frequency content compared to binary schemes, though decoding requires tracking state cycles. Spectral properties are critical for selecting line codes, as they determine compatibility with channel bandwidth and filtering requirements; for instance, unipolar NRZ's DC-heavy PSD suits short-distance applications but not AC-coupled lines, while bipolar AMI and Manchester shift energy away from DC to improve transmission over transformers, and MLT-3 further compresses the spectrum for efficiency. These considerations ensure minimal and optimal in systems.

Applications in Transmission

Line coding plays a crucial role in the of wired communication systems, ensuring reliable data transmission over various media by addressing issues such as , DC balance, and . In local area networks (LANs), particularly Ethernet, line coding schemes are standardized to support high-speed data transfer while mitigating transmission impairments like and . One prominent application is in 10 Mbps Ethernet (10BASE-T), where encoding is employed to embed clock information within the , enabling self-clocking at the receiver without a separate clock line. This approach guarantees transitions in every bit period, facilitating reliable in twisted-pair cabling. However, encoding doubles the required bandwidth compared to simpler schemes, as each data bit is represented by two signal levels, limiting its use to lower-speed links. For faster Ethernet variants, such as 100 Mbps 100BASE-TX (twisted-pair), 4B/5B encoding is combined with MLT-3 signaling, while 100BASE-FX (fiber) uses 4B/5B with NRZI; here, groups of four data bits are mapped to five-bit code words that ensure sufficient transitions for while maintaining DC balance. These techniques are defined in the standard, which governs specifications for LANs. In traditional telephone networks, alternate mark inversion (AMI), a bipolar line coding method, is widely used in T1 (North America) and E1 (Europe) carrier systems to transmit digitized voice and data at rates of 1.544 Mbps and 2.048 Mbps, respectively. AMI alternates the polarity of pulses for binary 1s while representing 0s with no pulse, which helps maintain DC balance and reduces in or twisted-pair lines. This scheme is particularly effective for long-haul transmission in public switched telephone networks (PSTN), where it supports multiple voice channels. For optical fiber communications, NRZ remains a dominant line coding format due to its simplicity and ability to support high data rates exceeding 10 Gbps in single-mode fibers. To prevent DC wander and baseline distortion caused by long sequences of identical bits, NRZ signals are often passed through scramblers that pseudo-randomize the before transmission, ensuring an average zero DC component without altering the information content. This combination is integral to standards like those in for optical Ethernet links. In modern high-speed systems, line coding integrates with (FEC) to enhance reliability; for instance, FEC parity bits are added post-line coding to detect and correct s introduced by fiber or dispersion, achieving post-FEC bit error rates below 10^{-12} in links up to several kilometers.

Cryptographic Applications

Coding in Cryptography

Coding theory plays a pivotal role in by leveraging the computational hardness of decoding problems to construct secure primitives resistant to both classical and quantum attacks. Error-correcting codes, particularly linear codes, form the foundation for these systems, where the difficulty of recovering a codeword from a noisy version underpins . One of the earliest and most influential applications is public-key , exemplified by the introduced in 1978, which uses Goppa codes to enable secure key exchange without relying on factoring or discrete logarithms. In this scheme, the public key consists of a disguised of a Goppa code, and adds errors to the message; decryption exploits the efficient decoding algorithm for the specific code structure, while attackers face the general decoding problem. The security of code-based cryptography stems fundamentally from the NP-hardness of decoding general linear codes, a property established in 1978, which demonstrates that finding the closest codeword to a received vector is computationally intractable for arbitrary codes. This hardness assumption resists quantum algorithms like Grover's, making code-based schemes promising candidates for . Beyond encryption, coding principles extend to hash functions, such as the Fast Syndrome Based (FSB) family, which computes a using a derived from a to produce collision-resistant digests, relying on the syndrome decoding problem for preimage resistance. Code-based digital signatures also draw on these principles, with modern post-quantum variants employing quasi-cyclic low-density parity-check (QC-LDPC) codes to achieve efficiency and . For instance, signature schemes based on QC-LDPC codes use the Fiat-Shamir paradigm with decoding challenges, where the signer proves knowledge of a low-weight error vector without revealing it, providing existential unforgeability under the hardness of decoding QC-LDPC codes. These signatures offer compact sizes and fast verification, positioning them as viable alternatives in post-quantum settings, though they require careful parameter selection to mitigate reaction attacks. In stream ciphers, convolutional codes contribute to keystream generation by encoding a seed key through a convolutional encoder, producing a pseudorandom with good linear and resistance to attacks when combined with nonlinear filters. This approach enhances the keystream's statistical properties, as the recursive nature of convolutional encoding diffuses the initial state effectively, though practical implementations often hybridize it with other generators for added . Furthermore, coding theory supports privacy-preserving protocols, particularly in (MPC), where error-correcting codes enable robust and fault-tolerant evaluation of functions among distributed parties. In MPC frameworks, linear codes facilitate the distribution of shares such that errors or malicious corruptions can be detected and corrected, ensuring correctness without revealing private inputs, as demonstrated in protocols that integrate random linear codes for secure arithmetic operations. This integration provides against adaptive adversaries, enhancing the reliability of MPC in noisy or untrusted environments. In March 2025, NIST selected the HQC algorithm, based on quasi-cyclic moderate-density parity-check codes, for as an additional post-quantum .

Secure Communication Protocols

Secure communication protocols leverage coding theory to enhance and over potentially adversarial or noisy channels, integrating correction with cryptographic mechanisms to protect against both transmission and unauthorized access. These protocols often combine (FEC) with to maintain reliability without excessive retransmissions that could leak information, ensuring that legitimate parties can decode messages while adversaries face insurmountable computational barriers. By embedding coding structures into the protocol layers, such systems achieve robust security in environments like networks or quantum channels, where channel noise could otherwise compromise key exchanges or streams. A key integration involves coded modulation schemes, such as trellis-coded modulation (TCM), which fuse convolutional coding with modulation to provide error correction while supporting secure wireless transmission. In TCM, redundancy is introduced via trellis structures that allow Viterbi decoding to correct errors, and when oriented toward security, these codes exploit channel asymmetries—better signal quality for legitimate receivers than eavesdroppers—to amplify secrecy rates without bandwidth expansion. For instance, security-oriented TCM designs for map coded bits to antenna activations and symbols, achieving security by ensuring that decoding failures at unauthorized receivers preserve message confidentiality. This approach is particularly effective in fading channels, where it outperforms uncoded schemes by 3-5 dB in secrecy capacity. Privacy amplification protocols use error-correcting codes to distill secure keys from noisy quantum or classical channels, reducing partial information leakage to an adversary to negligible levels. In quantum key distribution (QKD), low-density parity-check (LDPC) codes perform information reconciliation by correcting quantum bit errors and subsequent privacy amplification via universal hashing, ensuring the final key is uniform and secret despite eavesdropping attempts. LDPC codes are favored for their near-Shannon-limit performance and low overhead, enabling practical key rates over fiber optics. These codes iteratively exchange parity bits over an authenticated classical channel, reconciling sifted keys while bounding Eve's knowledge. Automatic repeat request (ARQ) protocols enhanced with encryption combine FEC and retransmissions to secure communications, where failed decodings trigger encrypted re-sends only for authorized parties. Hybrid ARQ (HARQ) schemes encode packets with rateless or incremental redundancy codes, such as punctured LDPC, and encrypt the payloads using symmetric keys; retransmissions accumulate parity to aid correction while the encryption prevents information gain by interceptors. In cognitive radio networks, secured HARQ protocols adapt coding rates based on channel state and threat models, achieving throughput gains of 20-30% over basic ARQ while maintaining perfect secrecy. The McEliece system, relying on code-based encryption, can encapsulate keys in such ARQ flows for post-quantum security. Practical examples include code-based authentication in (IoT) deployments, where lightweight protocols use quasi-cyclic moderate-density parity-check (QC-MDPC) codes for without heavy public-key computations. In these schemes, devices generate authentication tags from code syndromes, verifying identities over constrained channels while resisting forgery attacks with negligible false acceptance rates below 2^{-80}. For broader secure channels, protocols like SSL/TLS operate over coded physical layers in unreliable media, such as satellite links employing Reed-Solomon FEC beneath the TLS record layer to correct burst errors without decrypting the . Challenges in these protocols include side-channel attacks targeting the decoding process, where timing or power variations during error correction leak information about codewords or keys. For example, in lattice-based or code-based cryptosystems integrated into secure protocols, attackers exploit differential execution times in computation or decoding to recover secrets, potentially reducing security margins by orders of magnitude. Mitigations involve constant-time implementations and masking, though they increase computational overhead by 2-5 times.

Other Applications

Group Testing

Group testing is a combinatorial problem that applies coding theory principles to identify a small number of defective items among a large set by performing tests on subsets (pools) of the items, rather than testing each individually. This approach originated in the context of efficient screening for rare defects, such as diseases in populations, and has since been formalized using binary matrices where rows represent tests and columns correspond to items. In coding theory terms, the problem can be viewed as designing a matrix that allows decoding the sparse "error" vector indicating defectives from the pooled test outcomes. Adaptive involves sequential testing, where the choice of each subsequent test depends on the results of previous ones, enabling potentially fewer tests overall through binary search-like strategies. In contrast, non-adaptive designs all tests in advance, represented by a fixed binary testing matrix A∈{0,1}t×nA \in \{0,1\}^{t \times n}, where tt is the number of tests, nn the number of items, and the outcome of test ii is the logical OR (or sum modulo 2 in some variants) of the entries in the selected items for that row. Non-adaptive schemes are particularly valuable in parallelizable or time-constrained applications, as all pools can be tested simultaneously. In non-adaptive , the testing matrix corresponds to a disjunctive , where each column serves as a codeword representing the tests that include a particular item, and the observed test results form the disjunction (bitwise OR) of the codewords for the defective items. Decoding identifies the defective set SS (with ∣S∣≤[d](/page/D∗)|S| \leq [d](/page/D*)) such that the union of their supports matches the positive tests exactly, often using combinatorial properties like dd-disjunct matrices, which ensure no column is contained in the union of any dd others, guaranteeing unique recovery. This decoding can leverage the covering of the , defined as the smallest rr such that every possible binary vector of length tt is within rr of some codeword union, allowing efficient search for the closest matching defective set in approximate recovery scenarios. Information-theoretically, for identifying up to dd defectives among nn items, the minimal number of tests satisfies t≥dlog⁡2(n/d)t \geq d \log_2 (n/d) asymptotically, derived from the need to distinguish (nd)\binom{n}{d} possible defective sets, which requires at least log⁡2(nd)≈dlog⁡2(n/d)\log_2 \binom{n}{d} \approx d \log_2 (n/d) bits of information. This bound is achievable in the adaptive setting with binary splitting but requires Θ(d2log⁡n)\Theta(d^2 \log n) tests in the non-adaptive case for exact recovery using disjunct constructions. A seminal example is Dorfman's 1943 scheme for blood testing during syphilis screening, where blood from groups of size n/p\sqrt{n/p}
Add your contribution
Related Hubs
User Avatar
No comments yet.