Coding Theory Glossary

A class of cyclic error-correcting codes parameterized by their designed distance, decoded using the Berlekamp-Massey algorithm.

An iterative message-passing algorithm used to decode LDPC codes by exchanging probability estimates on a Tanner graph.

A channel model where each transmitted bit is independently flipped with a fixed probability p.

A code that divides the data stream into fixed-length blocks and encodes each block independently into a codeword.

A contiguous sequence of erroneous bits or symbols caused by a single noise event, common in wireless and storage channels.

The theoretical maximum rate of reliable information transfer over a communication channel, measured in bits per channel use.

The ratio k/n of information symbols to total codeword symbols, indicating the proportion of transmitted data that carries useful information.

A valid output of an encoder; one of the allowed sequences in a code, consisting of information bits plus redundancy.

A code that encodes data continuously by convolving the input stream with the encoder's impulse response using shift registers.

A linear block code where every cyclic shift of a codeword produces another codeword, enabling efficient polynomial-based operations.

A code for channels where symbols are lost rather than corrupted, used extensively in distributed storage and cloud systems.

A code that adds redundancy to data so that certain types and numbers of errors can be corrected by the receiver without retransmission.

An algebraic structure with a finite number of elements supporting addition, subtraction, multiplication, and division, fundamental to code construction.

A matrix G whose rows span the code space; encoding is performed by multiplying the message vector by G.

A polynomial g(x) that defines a cyclic code; every codeword polynomial is a multiple of g(x).

A family of single-error-correcting, double-error-detecting perfect linear codes with parameters [2^r - 1, 2^r - 1 - r, 3].

The number of positions at which two equal-length strings of symbols differ.

Rearranging symbol order before transmission so that burst errors are spread across multiple codewords after de-interleaving.

A linear block code with a sparse parity-check matrix, decoded iteratively and capable of near-Shannon-limit performance.

Selecting the codeword that maximizes the probability of the received observation; the optimal but often computationally expensive decoding approach.

The smallest Hamming distance between any two distinct codewords in a code, determining its error-correcting power.

A matrix H defining the null space of a linear code, used in syndrome-based error detection and correction.

A capacity-achieving code based on channel polarization, invented by Arikan in 2009, used in 5G control channels.

A non-binary MDS cyclic code operating on finite field symbols, highly effective against burst errors.

The result s = Hr^T of multiplying a received word by the parity-check matrix; a zero syndrome indicates no detectable error.