Singleton
d ≤ n − k + 1
n = 7, k = 4 gives d ≤ 4.
For a binary code of length , dimension and minimum distance : the Singleton bound is , and a code correcting errors satisfies the Hamming (sphere-packing) bound .
This page is easier if you are comfortable with:
Balls of radius around the codewords must not overlap, and each contains words; all fit in the possible words. This gives the Hamming bound after dividing by . For the Hamming (7,4) code, : , equality, so it is a perfect code; its distance is below the Singleton limit . The binomial counts are those of sums of binomial coefficients.
The Golay code (23,12) with : , another perfect code. For a (5,2) code with : , with room to spare. The Singleton bound follows from the pigeonhole principle: deleting positions must leave the codewords distinct.
Together the bounds limit how much information a code can carry for a given error-correcting power, the practical counterpart of channel capacity and of the binary symmetric channel; the code-length counting is related to Kraft's inequality.
The bounds limit how far apart codewords can be for a given length and number of information bits.
More information bits k means a smaller possible distance.
These examples are worked by hand, step by step, so you can compare your own working.
Check the Hamming bound for , , .
Check the Hamming bound for , , .
Find the largest possible distance for , .
A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.
d ≤ n − k + 1
n = 7, k = 4 gives d ≤ 4.
M ≤ 2⁷/(1 + 7) = 16
Sphere-packing.
16 × 8 = 128 = 2⁷
Hamming(7,4) is perfect.
t = ⌊(d − 1)/2⌋
d = 3 gives t = 1.
Singleton bound: d ≤ n − k + 1 for an [n, k, d] code. Hamming (sphere-packing) bound: M·Σ_{i=0}^t C(n, i) ≤ 2ⁿ with t = ⌊(d − 1)/2⌋. A code meeting the Hamming bound is perfect.
Largest d for an [7, 4] code.
A code has d = 3. Find t.
Find the volume of a radius-1 ball in n = 7 binary space.
Largest M for n = 7, t = 1.
d ≤ n − M + 1 ✗
d ≤ n − k + 1 ✓
k is the dimension.
balls of radius d ✗
radius t = ⌊(d − 1)/2⌋ ✓
Balls must be disjoint.
sphere size 7 ✗
sphere size 1 + 7 ✓
Include the codeword.
always ✗
only perfect codes meet it ✓
Often just an upper limit.
Try each one on paper, then open the answer. Use the solver above to see the full working.
5
2
29
16
16
2048
Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.
Solve: …
d ≤ n − k + 1.
M·Σ_{i≤t} C(n, i) ≤ 2ⁿ.
One meeting the Hamming bound with equality.
⌊(d − 1)/2⌋ errors corrected.
binary symmetric channel.
Kraft inequality.
More in Advanced statistics and stochastic processes and the formula sheets.