Fact-checked by Grok 2 weeks ago

Block code

A block code is a type of error-correcting code in coding theory that encodes a fixed-length block of information symbols from a finite alphabet into a longer codeword, incorporating redundancy to detect and correct errors introduced during transmission or storage over noisy channels.^[1] These codes process data in discrete blocks of length n, where each block is encoded independently, enabling reliable communication by allowing the recovery of the original message even if up to t symbols are corrupted, with the error-correcting capability determined by the code's minimum distance d (where t = ⌊(d-1)/2⌋).^[2] Linear block codes, a prominent subclass defined over finite fields (often the binary field GF(2)), represent codewords as linear combinations of basis vectors via a k × n generator matrix G, where k is the number of information symbols and the code rate is k/n.^[3] Encoding involves multiplying a message vector by G to produce the codeword, while decoding often uses the parity-check matrix H (satisfying G H^T = 0) to compute a syndrome that identifies and corrects errors, as in syndrome decoding algorithms.^[2] The minimum distance d not only bounds error correction but also error detection up to d-1 errors, making these codes essential for applications requiring high reliability with bounded complexity.^[3] The development of block codes traces back to Claude Shannon's 1948 foundational work on information theory, which established the theoretical limits of error-free communication, inspiring the construction of practical codes like the Hamming code (1950) for single-error correction.^[4] Subsequent advancements include Reed-Solomon codes (1960), widely used in digital storage (e.g., CDs and DVDs) for burst-error correction, and BCH codes (1960s) for multiple-error correction in cyclic structures.^[3] Modern block codes, such as low-density parity-check (LDPC) codes from the 1960s (rediscovered in the 1990s), approach Shannon's capacity limits and underpin technologies like wireless communications, satellite transmission, and data storage systems.^[4]

Fundamentals

Definition

A block code over an alphabet \Sigma is formally defined as a subset C \subseteq \Sigma^n, consisting of codewords each of fixed length n, where the encoding process maps messages composed of k symbols from \Sigma to corresponding n-symbol codewords in C.^[5] This structure ensures that the code operates on discrete blocks of data, distinguishing it from codes that process variable-length or streaming inputs.^[1] Encoding can be systematic or nonsystematic: in systematic encoding, the original k message symbols appear explicitly as a contiguous portion of the n-symbol codeword, with the remaining n-k symbols serving as redundancy; in nonsystematic encoding, the message symbols are transformed and intermixed with redundancy without direct embedding.^[6] Block codes play a crucial role in discrete memoryless channels by introducing controlled redundancy into the transmitted signal, enabling the detection and correction of errors introduced by noise while preserving reliable communication up to the channel's capacity.^[7] The foundational concept of block codes originates from Claude Shannon's 1948 paper "A Mathematical Theory of Communication," which established the theoretical framework for error-correcting codes as a means to achieve reliable transmission over noisy channels, positioning block codes as a core model in information theory.^[7]

Parameters

The parameters of a block code quantify its structural properties and error-handling capabilities, providing essential metrics for evaluating efficiency and reliability in communication systems. The block length n denotes the fixed total number of symbols comprising each codeword, which establishes the overall size of the encoded block and directly influences the level of redundancy incorporated to combat transmission errors. In binary block codes, where the alphabet \Sigma = \{0, 1\}, the symbols are bits, and n represents the total bit length of the codeword.^[8] The message length k specifies the number of information-carrying symbols within each codeword, determining the code's capacity to represent distinct messages; for an alphabet of size q, this yields q^k possible messages.^[9] By design, n \geq k holds for all block codes, as the additional n - k symbols serve as redundancy to enable error detection and correction without expanding the message space. The rate R = k/n measures the code's efficiency as the fraction of symbols dedicated to information rather than redundancy, with higher rates approaching the theoretical channel capacity for reliable communication as established in foundational information theory.^[7] For instance, rates close to but below the capacity ensure arbitrarily low error probabilities for sufficiently large n.^[7] The minimum distance d is the smallest Hamming distance—the number of symbol positions differing—between any two distinct codewords, serving as the primary determinant of the code's robustness against errors.^[10] A block code with minimum distance d can detect up to d-1 errors, as any such alteration cannot transform one valid codeword into another.^[11] Furthermore, it can correct up to t = \lfloor (d-1)/2 \rfloor errors, since spheres of radius t around codewords remain disjoint, allowing unique decoding within those regions.^[10]

Notation and Conventions

Alphabet and Fields

In block codes, the alphabet \Sigma is a finite set of symbols from which codewords are constructed, typically denoted by its cardinality q = |\Sigma|, where q \geq 2. Common examples include the binary alphabet \Sigma = \{0, 1\} with q = 2, used in many practical systems for its simplicity, and q-ary alphabets where symbols are elements of a larger set, such as \{0, 1, \dots, q-1\}.^[12] The choice of \Sigma forms the foundational symbol set for encoding messages into fixed-length blocks of length n, influencing the overall code structure and error-handling capabilities.^[13] For algebraic constructions, particularly linear block codes, the alphabet is often a finite field, known as a Galois field \mathrm{GF}(q), where q = p^m for a prime p and positive integer m. These fields provide the necessary arithmetic operations—addition and multiplication—that enable vector space structures over \Sigma, facilitating efficient encoding and decoding. Binary codes specifically employ \mathrm{GF}(2), where addition is modulo-2 (XOR) and multiplication is AND, simplifying hardware implementations. Reed-Solomon codes, a prominent class of algebraic codes, require \mathrm{GF}(2^m) to represent symbols as polynomials of degree less than m, allowing correction of multiple symbol errors in applications like data storage.^[12]^[13] Nonlinear block codes may use non-field alphabets, such as sets of integers without field properties, to achieve specific performance in non-standard metrics. For instance, permutation codes operate over the symmetric group S_n of permutations of \{1, 2, \dots, n\}, treating codewords as ordered lists where each integer from 1 to n appears exactly once, and distance is measured by the number of mismatched positions. These differ from field-based codes by lacking a linear vector space, instead relying on group operations for structure, which can be advantageous in channels with permutation errors like storage devices.^[14] Larger alphabet sizes q enable higher code rates by packing more information per symbol while maintaining desired minimum distances, approaching bounds like the Singleton bound for certain constructions. However, this comes at the cost of increased computational complexity, as operations in larger \mathrm{GF}(q) (e.g., multiplication in \mathrm{GF}(2^m)) require more resources than binary XOR, and decoding algorithms scale with q.^[15]^[13]

Dimensions and Rate

In coding theory, block codes are standardly denoted using the parameters (n, k, d)_q, where n represents the code length (number of symbols per codeword), k the dimension (number of independent information symbols), d the minimum Hamming distance, and q the alphabet size over the finite field \mathrm{GF}(q). This notation encapsulates the core structural properties of the code in a compact form. For binary codes where q = 2, the subscript q is typically omitted, yielding the simplified (n, k, d) notation, which has become ubiquitous in the literature on binary linear codes. The evolution of this notation traces back to Richard W. Hamming's seminal 1950 paper on error-detecting and error-correcting codes, where he introduced the binary Hamming code using the (7, 4) parameters to denote length and dimension; subsequent developments in the 1950s and 1960s extended it to general q-ary settings as algebraic coding theory incorporated finite fields beyond \mathrm{GF}(2).^[16]^[9]^[10]^[16] For linear block codes, the dimension k serves as a logarithmic measure of the code's size: the total number of codewords |C| equals q^[k](/page/K), reflecting the k-dimensional subspace structure over \mathrm{GF}(q). This parameterization allows for systematic encoding via a [k](/page/K) \times n generator matrix, where the rows form a basis for the code. In practice, [k](/page/K) determines the information throughput, with redundancy introduced through the n - [k](/page/K) parity symbols to achieve error control. The choice of [k](/page/K) directly influences the code's capability to balance reliability and efficiency.^[9]^[16] The rate R of a block code, defined as R = k/n, quantifies the proportion of information symbols in each codeword and thus the code's efficiency; values closer to 1 indicate less overhead from redundancy. For families of codes designed for varying block lengths, the asymptotic rate R = \lim_{n \to \infty} k/n provides a normalized metric for evaluating performance in high-rate regimes, such as those approaching channel capacity limits. A key interrelation among parameters is previewed by the Singleton bound, which asserts that any block code satisfies d \leq n - k + 1, establishing an upper limit on distance relative to dimension and length. This bound highlights inherent trade-offs in code design, though achieving equality (in maximum distance separable codes) remains challenging beyond specific constructions.^[17]^[18]^[17]

Minimum Distance

The Hamming distance between two codewords is the number of positions at which they differ.^[10] This metric, introduced by Richard Hamming, serves as the foundational measure of dissimilarity in coding theory.^[10] The minimum distance d of a block code \mathcal{C} is defined as the smallest Hamming distance between any two distinct codewords, given by

d = \min \{ \mathrm{wt}(c - c') \mid c \neq c' \in \mathcal{C} \},

where \mathrm{wt}(\cdot) denotes the Hamming weight, or number of nonzero symbols in a vector.^[11] This parameter quantifies the code's robustness against errors, as it determines the radius for unique nearest-neighbor decoding, ensuring that codewords are sufficiently separated to distinguish error patterns within that sphere.^[19] For linear block codes over a field, which form a vector subspace containing the all-zero codeword, the minimum distance simplifies to the minimum weight of any nonzero codeword:

d = \min \{ \mathrm{wt}(c) \mid c \in \mathcal{C}, c \neq 0 \}.

^[11] This equivalence holds because the difference of two codewords is itself a codeword under vector addition.^[19] The weight distribution provides further insight into the code's structure, captured by the weight enumerator coefficients A_i, where A_i is the number of codewords of weight i, with A_0 = 1 and A_d > 0.^[19] Computing the minimum distance for linear codes involves analyzing the generator matrix G (a k \times n matrix whose rows span the code) to find the lowest-weight linear combination of its rows, or equivalently, the parity-check matrix H (an (n-k) \times n matrix satisfying H c^T = 0 for codewords c). Specifically, d is the smallest integer such that some d columns of H are linearly dependent over the field.^[11]^[19]

Constructions and Examples

Linear Block Codes

Linear block codes form a fundamental subclass of block codes in coding theory, characterized by their algebraic structure as vector subspaces over finite fields. A linear block code C of length n over the finite field \mathrm{GF}(q) is defined as a k-dimensional subspace of the vector space \mathrm{GF}(q)^n, meaning it is closed under addition and scalar multiplication, with |C| = q^k codewords.^[20] This linearity enables efficient encoding and decoding via matrix operations, distinguishing them from nonlinear codes.^[2] The code can be generated using a generator matrix \mathbf{G}, which is a k \times n matrix whose rows form a basis for C. Any codeword \mathbf{c} \in C is obtained as \mathbf{c} = \mathbf{m} \mathbf{G}, where \mathbf{m} is a k-tuple message vector in \mathrm{GF}(q)^k. Often, \mathbf{G} is put into systematic form \mathbf{G} = [\mathbf{I}_k \mid \mathbf{P}], where \mathbf{I}_k is the k \times k identity matrix and \mathbf{P} is a k \times (n-k) parity submatrix; this form directly appends k message symbols followed by n-k parity symbols to form the codeword.^[21]^[2] Dually, the code is defined by a parity-check matrix \mathbf{H}, an (n-k) \times n matrix whose rows span the dual space C^\perp, such that \mathbf{c} \in C if and only if \mathbf{H} \mathbf{c}^T = \mathbf{0}. For a systematic generator \mathbf{G} = [\mathbf{I}_k \mid \mathbf{P}], the corresponding \mathbf{H} takes the form \mathbf{H} = [-\mathbf{P}^T \mid \mathbf{I}_{n-k}] (or equivalently over \mathrm{GF}(2), \mathbf{H} = [\mathbf{P}^T \mid \mathbf{I}_{n-k}]). This matrix facilitates error detection, as a received vector \mathbf{r} is a codeword precisely when the syndrome \mathbf{H} \mathbf{r}^T = \mathbf{0}.^[20]^[2] Encoding a message \mathbf{m} into a codeword \mathbf{c} is performed by the linear map \mathbf{c} = \mathbf{m} \mathbf{G}, which requires O(nk) operations over \mathrm{GF}(q) and preserves the subspace structure. In systematic form, the first k positions of \mathbf{c} are simply the message symbols, with the remaining positions computed as linear combinations specified by \mathbf{P}.^[21] Prominent examples include the binary Hamming code, a perfect single-error-correcting (7,4,3)_2 linear code whose parity-check matrix \mathbf{H} has columns that are all nonzero vectors in \mathrm{GF}(2)^3. In its systematic form, parity checks are placed on positions 1, 2, and 4. The extended Hamming code adds an overall parity bit, yielding a (8,4,4)_2 code capable of single-error correction and double-error detection; its generator matrix appends a column of all ones to the original \mathbf{G}.^[20]^[22] Reed–Solomon codes are another important class of linear block codes, defined over \mathrm{GF}(q) with length n \leq q, dimension k, and minimum distance d = n - k + 1. They are cyclic and particularly effective for correcting burst errors, widely used in digital storage such as CDs, DVDs, and QR codes. BCH codes generalize Hamming codes to multiple-error correction, constructed as cyclic codes over \mathrm{GF}(q) capable of correcting up to t errors with designed distance d = 2t + 1. Binary BCH codes of length n = 2^m - 1 include the Hamming code as the single-error case and are used in applications like satellite communications. Linear codes can be modified to derive new codes via standard operations that preserve linearity. Shortening reduces length by fixing certain message symbols to zero and puncturing the corresponding code positions, transforming an (n,k,d)_q code into an (n-1,k-1,d)_q code with at least the original minimum distance. Puncturing shortens the code by deleting specific coordinate positions from all codewords, yielding an (n-1,k,d-1)_q code (or better), which sacrifices some distance for reduced length. Extending increases length by appending a new parity-check symbol (e.g., an overall parity bit in binary cases), producing an (n+1,k,d+1)_q or (n+1,k,d)_q code, as in the extended Hamming example, to enhance error-detection capability. These operations allow construction of families of codes from smaller base codes.^[23]^[24]^[25]

Nonlinear Block Codes

Nonlinear block codes are defined as arbitrary subsets C \subseteq \Sigma^n, where \Sigma is a finite alphabet of size q, such that the minimum Hamming distance between any two distinct codewords is at least d. This general formulation encompasses all block codes, including linear ones as a special case where C forms a vector subspace over the field \mathbb{F}_q, but nonlinear codes lack this linearity and thus do not require the sum of any two codewords to be in C.^[26]^[27] A key advantage of nonlinear codes is their potential to achieve larger cardinalities |C| for fixed length n and minimum distance d compared to linear codes, enabling better rates in certain parameter regimes. The Plotkin construction exemplifies this by combining two codes of length n to form a nonlinear code of length $2n, often yielding improved distance properties without the constraints of linearity. For binary alphabets, nonlinear constructions frequently attain the optimal value A(n,d), the maximum possible |C|, particularly for small n, as evidenced by comprehensive tables of best-known codes that include nonlinear examples surpassing linear bounds.^[28]^[29] Prominent constructions include the Nordstrom-Robinson code, a binary nonlinear code with parameters (16, 256, 6), which achieves A(16,6) = 256 and exceeds the size of the best linear binary code for these parameters—a [16,5,8] Reed-Muller code with only 32 codewords and distance exceeding 6, but no linear code reaches 256 codewords at distance 6.^[30] In comparison to linear codes, nonlinear codes share parameters n, d, and effective rate but allow |C| to be any integer rather than a power of q, facilitating optimizations for specific applications where algebraic simplicity is secondary to maximal code size. Tables of A(n,d) for binary codes up to moderate n demonstrate that nonlinear codes are optimal in numerous cases, underscoring their role in pushing theoretical limits.^[31]

Error Handling Properties

Detection Capabilities

Block codes enable error detection by leveraging the minimum distance d between codewords, ensuring that certain error patterns cannot transform one valid codeword into another. Specifically, a block code can detect up to e = d-1 errors, as any error pattern of weight at most d-1 will result in a received word that is not a codeword, since the spheres of radius d-1 around distinct codewords do not overlap.^[12] This detection capability holds for both linear and nonlinear block codes, relying solely on the code's distance property without attempting to identify the exact error locations. For linear block codes, error detection is efficiently performed using syndrome decoding with the parity-check matrix H. Upon receiving a vector r = c + e, where c is the transmitted codeword and e is the error vector, the syndrome s = H r^T = H e^T is computed. If s = 0, the received vector is deemed a valid codeword (no error detected); otherwise, a nonzero syndrome indicates the presence of errors, allowing detection without correction.^[2] This method is particularly effective for detecting low-weight errors, as syndromes distinguish erroneous receptions from codewords. A simple example of a detection-oriented block code is the parity-check code, which has d = 2 and appends a single parity bit to ensure an even (or odd) number of 1s in the codeword. Such codes reliably detect any single error, as it would alter the parity and produce a nonzero syndrome, though they fail to detect even numbers of errors.^[32] More advanced cyclic block codes, like the cyclic redundancy check (CRC), enhance detection for burst errors—consecutive bit flips common in transmission channels—by using a generator polynomial to append check bits that detect all bursts of length up to the degree of the polynomial, making CRC widely used in data links and storage systems.^[33] The performance of block codes in detection is often quantified by the probability of undetected error, which occurs when an error pattern coincides with a nonzero codeword, mapping the received vector to another valid codeword. For a linear block code over an alphabet of size q = |\Sigma| on a memoryless channel with random errors, this probability approximates q^{-(n-k)} for low error rates, reflecting the fraction of nonzero syndromes that correspond to undetectable errors.^[34] This bound underscores the trade-off: higher redundancy (n-k larger) improves detection reliability by reducing the likelihood of undetectable errors.

Correction Capabilities

Block codes enable the correction of errors in transmitted data by leveraging the minimum distance d between codewords. Specifically, a block code can correct up to t = \lfloor (d-1)/2 \rfloor errors per codeword, as this ensures that the spheres of radius t centered at each codeword in the Hamming space are disjoint, preventing overlap that could lead to ambiguous decoding.^[10] The standard approach to error correction is maximum likelihood decoding, which selects the codeword closest to the received vector in Hamming distance, assuming errors occur independently with equal probability. This method guarantees correct decoding for up to t errors, as any received vector within the decoding sphere of a codeword will be assigned to that codeword. For linear block codes, decoding often relies on syndrome computation, where the syndrome of the received vector is calculated as \mathbf{s} = \mathbf{H} \mathbf{r} (with \mathbf{H} the parity-check matrix and \mathbf{r} the received vector); if \mathbf{s} = \mathbf{0}, no correction is needed, otherwise, the syndrome identifies the error pattern.^[10] For small codes like the Hamming code, precomputed syndrome lookup tables map each nonzero syndrome directly to the corresponding single-error pattern, enabling efficient correction. Algebraic decoding methods extend this capability for more complex linear codes. For example, Reed-Solomon codes, which are nonbinary linear block codes, use the Berlekamp-Massey algorithm to solve for the error-locator polynomial from the syndrome sequence, allowing correction of up to t errors in a bounded algebraic manner.^[35] Similarly, BCH codes, a class of cyclic binary codes designed to correct multiple random errors, employ related algebraic techniques to achieve their correction capability, with parameters chosen such that the designed distance ensures up to t errors are correctable.^[36] Beyond t errors, decoding may fail entirely (if the received vector falls outside all decoding spheres) or result in miscorrection (assigning to an incorrect codeword), potentially introducing more errors than present, which underscores the importance of the minimum distance in limiting reliable correction.

Theoretical Bounds

Upper Bounds

The Singleton bound establishes a fundamental limit on the size of a block code, stating that for a code C of length n over an alphabet of size q with minimum distance d, the number of codewords satisfies |C| \leq q^{n-d+1}. Equivalently, in terms of the dimension k = \log_q |C|, the bound implies d \leq n - k + 1. This result is derived by projecting the code onto any n - d + 1 coordinates; to preserve the minimum distance, this projection must be injective, limiting the code size to at most q^{n-d+1}. Codes achieving equality in the Singleton bound are known as maximum distance separable (MDS) codes, a class exemplified by Reed-Solomon codes. The Hamming bound, also called the sphere-packing bound, provides another key upper bound on |C|, given by

|C| \leq \frac{q^n}{\sum_{i=0}^t \binom{n}{i} (q-1)^i},

where t = \lfloor (d-1)/2 \rfloor is the largest integer such that the code can correct t errors. This bound follows from the observation that the spheres of radius t centered at each codeword are disjoint and contained within the entire space of q^n possible words, leading to the volume constraint. Codes achieving equality are termed perfect, meaning their spheres exactly partition the space; notable examples include the Hamming codes over finite fields.^[37] When the minimum distance d exceeds (1 - 1/[q](/page/Q))n, the Plotkin bound yields a tighter restriction: |C| \leq [q](/page/Q) d / ([q](/page/Q) d - ([q](/page/Q)-1) n). This construction relies on a double-counting argument over pairwise distances in the code, showing that large d forces the codewords to be sufficiently separated, capping the size in high-distance regimes. The bound is especially relevant for codes with rates R = k/n approaching the capacity limit in noisy channels with high relative distance \delta = d/n > 1 - 1/[q](/page/Q). The original formulation was for binary codes, but it generalizes directly to q-ary alphabets via similar averaging techniques.^[38] The Elias-Bassalygo bound refines the Plotkin bound for q-ary codes by optimizing the underlying distance averaging, resulting in a stricter upper limit on |C| for parameters where the simple Plotkin is loose. Specifically, it improves the constant factors in the denominator, providing better performance for non-binary alphabets in the regime d > (1 - 1/q)n. This tightening combines Elias's early random coding arguments with Bassalygo's combinatorial refinements, influencing subsequent asymptotic analyses of code families.

Lower Bounds

Lower bounds in coding theory provide guarantees on the minimum size of a block code achieving given parameters, ensuring the existence of codes with desirable rate and error-correcting capabilities. These bounds are typically derived using probabilistic or constructive arguments that demonstrate the non-emptiness of certain code spaces.^[39] The Gilbert-Varshamov (GV) bound is a fundamental lower bound on the maximum number of codewords A_q(n, d) in a q-ary code of length n and minimum distance d. It states that there exists a code \mathcal{C} with |\mathcal{C}| \geq q^n / \sum_{i=0}^{d-1} \binom{n}{i} (q-1)^i. This bound arises from a greedy construction: start with an empty code and iteratively add a codeword that is at distance at least d from all existing codewords, which is always possible until the codewords' Hamming balls of radius d-1 cover the entire space. The total volume of these balls provides the denominator, ensuring the bound holds. Independently discovered by Edgar Gilbert in 1952 and Rom Varshamov in 1957, the GV bound uses a random coding argument for the linear case, where a random linear code over \mathbb{F}_q achieves the stated size with high probability.^[40]^[39]^[41] The GV bound plays a central role in asymptotic coding theory, where the normalized rate R = (1/n) \log_q |\mathcal{C}| satisfies R \geq 1 - H_q(\delta) for relative distance \delta = d/n, with H_q the q-ary entropy function; this limit is often superior to the Hamming bound (an upper bound) for large n in regimes where the Hamming bound is loose.^[39]

Geometric and Advanced Perspectives

Sphere Packing

In coding theory, the Hamming space refers to the set of all q-ary sequences of length n, denoted \mathbb{F}_q^n, equipped with the Hamming metric, where the distance between two vectors is the number of coordinate positions in which they differ.^[42] A sphere of radius t centered at a vector c \in \mathbb{F}_q^n consists of all vectors within Hamming distance at most t from c. The volume (cardinality) of such a sphere is given by

V(n, t, q) = \sum_{i=0}^t \binom{n}{i} (q-1)^i,

which counts the number of possible error patterns of weight at most t.^[43] Geometrically, a block code with minimum distance d = 2t + 1 corresponds to a packing of M disjoint spheres of radius t centered at the codewords, where these spheres collectively cover the error-correctable portion of the Hamming space. Since the spheres do not overlap and are contained within the total space of volume q^n, the size M of the code satisfies M \cdot V(n, t, q) \leq q^n, yielding the sphere-packing bound (also known as the Hamming bound) on the maximum number of codewords.^[43] A perfect packing arises when the spheres tile the entire Hamming space without gaps or overlaps, so M \cdot V(n, t, q) = q^n; codes achieving this equality are termed perfect codes.^[44] Notable examples include the Hamming codes and Golay codes, which saturate the sphere-packing bound.^[44] The binary Golay code, a [23, 12, 7] linear code capable of correcting up to t=3 errors, is perfect, as its 4096 spheres of radius 3 exactly partition the $2^{23} vectors in the space. q-ary generalizations of Hamming codes, constructed using parity-check matrices whose columns represent all nonzero points in the projective geometry PG(m-1, q), are perfect 1-error-correcting codes with parameters [n = (q^m - 1)/(q - 1), k = n - m, d = 3] for any prime power q and integer m ≥ 2.^[42]

Lattices and Continuous Analogues

In coding theory, lattices provide a continuous analogue to discrete block codes by extending concepts from finite fields to the Euclidean space \mathbb{R}^n. A lattice \Lambda is defined as a discrete subgroup of \mathbb{R}^n, consisting of all integer linear combinations of a basis of n linearly independent vectors, such as the integer lattice \mathbb{Z}^n formed by the standard basis vectors.^[45] These structures generalize block codes by allowing infinite point sets that tile the space periodically, enabling error correction and modulation in continuous channels like the additive white Gaussian noise (AWGN) channel.^[46] Block codes over finite fields can be viewed as finite projections of lattices onto discrete subsets, with constructions like Construction A embedding binary linear codes into \mathbb{R}^n to form lattices; for instance, the 24-dimensional Leech lattice \Lambda_{24} arises from the binary Golay code via such a projection, yielding one of the densest known sphere packings.^[47] In this analogy, the Voronoi region of a lattice point—the set of points in \mathbb{R}^n closer to that lattice point than to any other—serves as a continuous counterpart to the decoding spheres in discrete block codes, partitioning the space for nearest-neighbor decoding.^[48] Lattices like the E_8 in 8 dimensions and the Leech lattice in 24 dimensions achieve near-optimal packing densities, minimizing the volume of Voronoi regions relative to inscribed spheres, which enhances signal efficiency in high-dimensional spaces.^[49] Lattice-based codes facilitate modulation schemes for AWGN channels by selecting codewords from finite cosets of a lattice, combined with shaping techniques to approximate the uniform distribution over a fundamental region and approach the Gaussian capacity limit.^[47] G. David Forney's 1988 work on coset codes established this framework, linking binary lattices to multilevel modulation and error correction.^[47] In modern wireless systems, such as those explored for 5G, lattice codes enable efficient multi-user access and interference management through structured signal constellations, offering improved spectral efficiency over traditional discrete codes.^[50]

References

[1]
Block code - Error Correction Zoo
A code intended to encode a piece, or block, of a data stream on a block of n symbols, with each symbol taking values from a fixed alphabet.
[2]
[PDF] Linear Block Codes: Encoding and Syndrome Decoding - MIT
Feb 28, 2012 · The rate of the code is k/n. The conversion in a linear block code involves only linear operations over the message bits to produce codewords.
[3]
[PDF] The ABCs of linear block codes - Signal Processing Magazine, IEEE
Jul 14, 2004 · Ever since 1948, research in error-correction coding has focused on constructing good codes and finding easy-to-implement encoding/decoding ...
[4]
[PDF] The Art of Signaling: Fifty Years of Coding Theory - Computer Science
The coding theorem asserts that there are block codes with code rates arbitrarily close to channel capacity and probabilities of error arbitrarily close to zero ...
[5]
[PDF] Introduction to Coding Theory Lecture Notes∗ | Yehuda Lindell
Definition 1.1 Let A = {a1,...,aq} be an alphabet; we call the ai values symbols. A block code C of length n over A is a subset of An. A vector c ∈ C is called ...
[6]
Systematic Code - an overview | ScienceDirect Topics
A systematic code is a linear block code where the original data is followed by parity digits, with the first k digits being the dataword.
[7]
[PDF] A Mathematical Theory of Communication
This idea is carried still further in certain commercial codes where common words and phrases are represented by four- or five-letter code groups with a ...
[8]
[PDF] Coding Theory: Math 454 Lecture 19 (7/31/2017)
Dec 17, 2017 · Definition 1.1 (code). A code is a subset of the binary strings of length n. The parameter n is called the block-length of the code.
[9]
[PDF] Linear Codes
A linear code of length n over the field F is a subspace of Fn. An [n, k] linear code has dimension k, and its rate is k/n.
[10]
[PDF] The Bell System Technical Journal - Zoo | Yale University
Error Detecting and Error Correcting Codes. By R. W. HAMMING. 1. INTRODUCTION. T HE author was led to the study given in this paper from a considera- tion of ...Missing: free | Show results with:free
[11]
[PDF] Lecture 2 2.1 General model 2.2 Block codes 2.3 Role of minimum ...
Sep 5, 2019 · In these codes, each message and codeword is of fixed size. More precisely, k = |m| denotes the size of each message m and n = |c| denotes the ...
[12]
[PDF] Chapter 4 Linear Block Codes - Bernd Friedrichs
Jul 4, 2010 · According to Definition 1.4, the information symbols ui and the encoded symbols ai in an (n, k, dmin)q block code are q-ary with ui,ai ∈ Fq, ...
[13]
[PDF] Reed-Solomon Codes - CORE
A finite field, or Galois Field, is a field with a finite number of elements ... Given a finite alphabet A of q symbols, a block code is a function that.
[14]
[PDF] Permutation codes - Queen Mary University of London
This paper is a survey of old and new results about sets (and groups) of permutations, concentrating on the analogies and on the relations to coding theory.
[15]
[PDF] High-rate locally-correctable and locally-testable codes with sub ...
May 4, 2016 · Over the binary alphabet, our codes meet the Zyablov bound. Such trade-offs between the rate and the relative distance were previously not known ...
[16]
[PDF] Notes 1: Introduction, linear codes
The noisy coding theorem states that every such channel has a precisely defined real number called capacity that quantifies the maximum rate at which reliable ...
[17]
[PDF] Bounds on Code Parameters - Henry D. Pfister
Jan 16, 2025 · The family of codes that meet the Singleton bound is called maximum dis- tance separable (MDS) codes. We will later see an algebraic family of ...
[18]
Bounds on the Asymptotic Coding Gain of Long Binary Block Codes
r = k/n for hard decision decoding. A closed form analytical expression for the upper and lower bounds on block code performance is derived for large code ...
[19]
[PDF] The Theory of Error-Correcting Codes - Semantic Scholar
The Theory of Error-Correcting Codes · F. MacWilliams, N. Sloane · Published 1977 · Mathematics, Computer Science.
[20]
[PDF] 3. Linear Block Codes
4. 3.2 Basic Definitions. Definition 1 A linear block code is a k−dimensional vector subspace of the n−tuples over a field. D. For now,Missing: coding | Show results with:coding
[21]
[PDF] 6.02 Lecture 4: Linear block codes, parity relations
Block code: k message bits encoded to n code bits. i.e., each of 2k messages encoded into a unique n-bit codeword via a linear transformation. Key property: Sum ...
[22]
[PDF] Hamming Codes
Choose a generator matrix G for a Hamming code Hamr(q) of length n over. F. Each n-tuple x from Fn is at distance at most 1 from a unique codeword c of Hamr(q).
[23]
[PDF] Modifying Codes
To extend a linear code we add columns to its generator matrix, and to puncture the code we delete columns from its generator. Let us call the [n + 1,k] linear ...
[24]
https://www.math.clemson.edu/~keyj/Key/applicN.pdf
[25]
[PDF] Shortened Linear Codes over Finite Fields - arXiv
Jul 12, 2020 · This means that in theory shortening a linear code can be obtained by first performing the dual operation, then the puncturing operation ...
[26]
[PDF] An introduction of the theory of nonlinear error-correcting codes
Oct 8, 1987 · codes was one of the earliest problems that arose in coding theory. In addition to being the best codes for their n and d, perfect codes are ...
[27]
[PDF] An Introduction to Coding Theory: Lecture Notes
May 16, 2009 · We refer to the elements of C as words, codewords, or vectors. A code over. Fq is called a q-ary code. A code is binary if q = 2, ...
[28]
[PDF] Plotkin construction: Rank and Kernel - arXiv
Jul 26, 2007 · The construction works for linear and nonlinear codes. For the linear case, it is straightforward to see that the dimension of the final code ...
[29]
2 Nonlinear codes, Hadarnard matrices, designs and the Golay code
Non-linear codes are used to obtain the largest possible number of codewords with a given minimum distance. In this chapter all codes are binary.
[30]
Nordstrom-Robinson (NR) code - Error Correction Zoo
A nonlinear binary code that is the smallest Kerdock and the smallest Preparata code. The size of this code is larger than the largest possible linear code.
[31]
Erik Agrell's tables of binary block codes
It contains tables of bounds on the size of binary unrestricted codes, constant-weight codes, doubly-bounded-weight codes, and doubly-constant-weight codes.
[32]
[PDF] TCOM 370 NOTES 99-8 ERROR CONTROL: BLOCK CODES
Useful techniques for adding redundancy to data bits to enable error detection or error correction are often based on the ideas of block coding. (Another type ...
[33]
[PDF] notes 99-9 cyclic codes, and the crc (cyclic redundancy check) code
Cyclic codes are linear block codes effective for error detection. CRC codes are a type of linear block code used for error detection in data transmission.
[34]
[PDF] Error Control Coding by Shu Lin.pdf - WordPress.com
LIN and COSTELLO, Error Control Coding: Fundamentals and Applications. NAGLE ... 3.6 Probability of an Undetected Error for Linear Codes over a BSC. 3.7 ...
[35]
https://www-users.cse.umn.edu/~garrett/students/reu/MB_algorithm.pdf
[36]
Binary codes with specified minimum distance - IEEE Xplore
Binary codes with specified minimum distance | IEEE Journals & Magazine | IEEE Xplore ... Date of Publication: 30 September 1960. ISSN Information: Print ...
[37]
[PDF] Notes 2: Gilbert-Varshamov bound 1 Asymptotically good codes and ...
This volume turns out to be very well approximated by the exponential qhq(p)n where hq() is the “entropy function” defined below.
[38]
A comparison of signalling alphabets - Nokia Bell Labs - IEEE Xplore
The performance of a large number of simple signalling alphabets is computed and it is concluded that one cannot signal at rates near the channel capacity ...
[39]
[PDF] Hamming codes
We give a construction of a q-ary Hamming code and prove that it is perfect with minimum distance 3. We show that syndrome decoding works for Hamming codes in ...
[40]
[PDF] Chapter 2. Sphere Packing and Shannon's Theorem
The [7, 4] Hamming code has rate 4/7, and its extension rate 4/8=1/2. The [4, 2] ternary Hamming code has rate 2/4 = 1/2.
[41]
A survey of perfect codes - ResearchGate
Aug 10, 2025 · The first examples of perfect e-error correcting q-ary codes were given in the 1940s by Hamming and Golay.<|separator|>
[42]
[PDF] Chapter 18: Lattice Codes (by O. Ordentlich) - MIT OpenCourseWare
Our construction is based on starting with a linear code over a prime finite field, and embedding it periodically in Rn to form a lattice. Definition 18.6 (p- ...
[43]
[PDF] A Brief Introduction to Lattice Coding Theory (in two parts)
Definition 6.1 An n-dimensional lattice Λ is an additive subgroup of Rn. Since Rn is a vector space, and Λ is a subgroup, Λ is also vector subspace. Page 34 ...
[44]
https://www.researchgate.net/publication/238883225_A_survey_of_perfect_codes
[45]
[PDF] Coset Codes-Part 11: Binary Lattices and Related Codes
The family of Barnes-Wall lattices and their principal sublattices, which are useful in con- structing coset codes, are generated by iteration of a simple ...
[46]
Universal optimality of the E8 and Leech lattices and interpolation ...
We prove that the E8 root lattice and the Leech lattice are universally optimal among point configurations in Euclidean spaces of dimensions eight and twenty- ...Missing: survey | Show results with:survey
[47]
https://ieeexplore.ieee.org/document/21246