What Is Linear Code?

Linear code is a class of error-correcting code in which the set of all valid codewords forms a linear subspace over a finite field: the sum of any two codewords is also a valid codeword, and any scalar multiple of a codeword is a valid codeword. This algebraic closure property distinguishes linear codes from arbitrary block codes and makes them far more tractable to analyze and implement. A linear code over the binary field is characterized by three parameters written as [n, k, d], where n is the block length, k is the number of information bits, and d is the minimum Hamming distance between any two distinct codewords.

Linear codes are the dominant framework for channel coding in digital communications and storage systems. Their structure enables efficient encoding using matrix multiplication and efficient decoding using syndrome computation, without requiring lookup tables over an exponentially large codebook. The field draws on coding theory, abstract algebra, and information theory, with foundational contributions from Richard Hamming, Claude Shannon, Irving Reed, and Gustave Solomon in the 1940s through 1960s.

Generator and Parity Check Matrices

Every linear code over the binary field can be described by a generator matrix G, a k-by-n matrix whose rows form a basis for the k-dimensional codeword subspace. Encoding is the operation of multiplying a length-k message vector by G to produce the length-n codeword. A systematic generator matrix is arranged so that the first k columns form an identity matrix, meaning the encoded codeword begins with the original message bits followed by n-k redundancy bits. This systematic form is preferred in practice because it allows direct recovery of the message from a received codeword that contains no errors.

The parity check matrix H is an (n-k)-by-n matrix orthogonal to G, satisfying GH^T = 0 modulo 2. For any valid codeword c, the product Hc^T equals the zero vector. A received word that has been corrupted by channel errors will produce a nonzero syndrome Hc^T, and the pattern of the syndrome identifies which bit positions were flipped. The MIT Linear Algebra for EECS course materials on linear block codes provide a complete treatment of generator matrices, parity checks, and syndrome decoding as taught in practice.

Distance Properties and Error Correction

The minimum distance d of a linear code is the smallest Hamming weight among all nonzero codewords, a property that follows from linearity because the distance between two codewords equals the weight of their difference, which is itself a codeword. A code with minimum distance d can detect up to d-1 errors and correct up to floor((d-1)/2) errors per codeword. The rate of the code, k/n, measures the fraction of transmitted bits that carry information, and there is a fundamental tradeoff between rate and error-correction capability.

The binary linear code entry in the Error Correction Zoo documents the hierarchy of linear code families, their distance properties, and their relationships to quantum error-correcting codes. Finding the minimum distance of an arbitrary linear code is NP-complete in general, but structured families such as cyclic codes, Reed-Solomon codes, and LDPC codes have algebraic or graphical properties that make distance computation and decoding tractable.

Families of Linear Codes

The most widely deployed linear codes include Hamming codes, which achieve the Hamming bound for single-error correction and are used in memory error correction; Reed-Solomon codes, which operate over non-binary fields and correct burst errors in compact disc storage, digital video broadcast, and QR codes; and low-density parity check (LDPC) codes, which are defined by sparse parity check matrices and approach the Shannon capacity on a range of channel models. CMU notes on coding theory provide a formal treatment of linear codes, distance bounds including the Singleton and Plotkin bounds, and the structure of specific code families.

Applications

Linear code has applications in a range of fields, including:

• Digital communications, where turbo codes and LDPC codes enable near-capacity transmission over wireless and satellite channels
• Data storage, where Reed-Solomon codes protect against burst errors on optical discs, flash memory, and hard drives
• Deep-space communications, where concatenated Reed-Solomon and convolutional codes are specified by CCSDS standards for spacecraft telemetry
• Quantum error correction, where CSS codes and other quantum linear codes are constructed from classical linear codes over finite fields
• Network coding, where linear codes over finite fields enable efficient multicast and distributed storage in communication networks