Hamming bound
E488680
The Hamming bound is a fundamental limit in coding theory that specifies the maximum number of codewords a block code can have for a given length and minimum distance while still allowing reliable error detection and correction.
Statements (48)
| Predicate | Object |
|---|---|
| instanceOf |
bound in coding theory
ⓘ
sphere-packing bound ⓘ |
| alsoKnownAs | sphere-packing bound in Hamming space ⓘ |
| appliesTo |
binary codes
ⓘ
block codes ⓘ q-ary codes ⓘ |
| assumes |
Hamming balls around codewords are disjoint
ⓘ
memoryless symmetric channel model in typical applications ⓘ |
| assumesMetric | Hamming distance ⓘ |
| characterizes | maximum number of codewords for given length and minimum distance ⓘ |
| comparedWith |
Gilbert–Varshamov bound
NERFINISHED
ⓘ
Plotkin bound NERFINISHED ⓘ Singleton bound NERFINISHED ⓘ |
| constrains |
maximum achievable code rate for fixed minimum distance
ⓘ
maximum minimum distance for fixed code rate ⓘ |
| definedOn | Hamming space ⓘ |
| describes | packing of Hamming spheres around codewords ⓘ |
| field |
coding theory
ⓘ
information theory ⓘ |
| generalizedTo | q-ary Hamming bound NERFINISHED ⓘ |
| holdsFor |
linear codes
ⓘ
nonlinear codes ⓘ |
| implies |
code cannot exceed certain rate for given minimum distance
ⓘ
trade-off between code rate and minimum distance ⓘ |
| involvesFunction | V_q(n,t) = Σ_{i=0}^t (n choose i)(q-1)^i ⓘ |
| involvesParameter | t = ⌊(d-1)/2⌋ ⓘ |
| isInequality | M * V_q(n,t) ≤ q^n ⓘ |
| mathematicalDomain |
combinatorics
ⓘ
discrete mathematics ⓘ |
| namedAfter | Richard Hamming NERFINISHED ⓘ |
| originatedIn | mid-20th century coding theory ⓘ |
| relatedConcept |
covering radius
ⓘ
error-correcting capability t ⓘ minimum distance decoding ⓘ perfect code ⓘ |
| relatesQuantity |
alphabet size q
ⓘ
code length n ⓘ minimum distance d ⓘ number of codewords M ⓘ |
| satisfiedWithEqualityBy |
Golay codes
NERFINISHED
ⓘ
Hamming codes NERFINISHED ⓘ |
| tightFor | perfect codes ⓘ |
| upperBounds | size of a code with given parameters ⓘ |
| usedFor |
design of error-correcting codes
ⓘ
error correction analysis ⓘ error detection analysis ⓘ |
| usedIn |
performance limits of communication systems
ⓘ
proofs of nonexistence of certain codes ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.