Singleton bound

The Singleton bound states that a code of length n and minimum distance d over an alphabet of size q contains at most q^(n−d+1) codewords.

Puncturing (coding theory): Puncturing deletes selected coordinates from every word in a code. Deleting d−1 coordinates leaves distinct codewords of length n−d+1.
Block code: A block code maps fixed-length messages to fixed-length strings over a finite alphabet. The Singleton bound applies to finite-length codewords in this setting.
Hamming bound: The Hamming bound limits code size by counting disjoint error-correction balls around codewords. It can be stricter than the Singleton bound for codes correcting errors.
Reed–Solomon code: A Reed–Solomon code evaluates low-degree polynomials at distinct field elements to form codewords. Its parameters attain the Singleton bound when the evaluation points are distinct.
Minimum distance (coding theory): The minimum distance of a code is the smallest Hamming distance between distinct codewords. The bound’s exponent depends directly on this separation between codewords.
Code rate: Code rate is the ratio of information symbols to transmitted symbols in a code. The size limit implies a corresponding upper bound on achievable rate.
Gilbert–Varshamov bound: The Gilbert–Varshamov bound guarantees the existence of codes above a specified size for a given distance. It is a lower existence bound, unlike the Singleton upper bound.
Reed–Solomon bound: The Reed–Solomon bound limits the number of rational points on an algebraic curve over a finite field. It extends the Singleton-bound perspective to algebraic-geometric codes.
MDS code: A maximum-distance separable code attains the Singleton bound for its length and dimension. Equality identifies codes whose size is as large as the bound permits.
Redundancy (coding theory): Redundancy is the number of code symbols beyond those carrying the message information. The bound requires enough redundancy to support a specified minimum distance.

Linked from 2 pages