Singleton and Hamming Bounds Explained with Worked Examples

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 .

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Singleton and Hamming bounds means

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.

What is it used for?

The bounds limit how far apart codewords can be for a given length and number of information bits.

How to use singleton and hamming bounds

  1. Identify , and the number of errors to correct.
  2. Check .
  3. Compute .
  4. Compare with : equality means a perfect code.

Graph

Singleton bound: largest distance d = n − k + 1 for n = 7k = 4: d ≤ 41234567012345678Singleton bound: largest distance d = n − k + 1 for n = 7kdd ≤ 8 − kGraph with x from 1 to 7 and y from 0 to 8. Shows the curve d ≤ 8 − k; point k = 4: d ≤ 4 at (4, 4).

More information bits k means a smaller possible distance.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: Hamming (7,4)

Check the Hamming bound for , , .

Worked example
Answer
8=8 (perfect)8=8\ \text{(perfect)}
  1. Left
  2. Right

Example 2: Golay (23,12)

Check the Hamming bound for , , .

Worked example
Answer
2048=20482048=2048
  1. Left
  2. Right

Example 3: Singleton bound

Find the largest possible distance for , .

Worked example
Answer
44
  1. Formula

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

Singleton

d ≤ n − k + 1

n = 7, k = 4 gives d ≤ 4.

Hamming (t = 1, n = 7)

M ≤ 2⁷/(1 + 7) = 16

Sphere-packing.

Perfect code

16 × 8 = 128 = 2⁷

Hamming(7,4) is perfect.

t from d

t = ⌊(d − 1)/2⌋

d = 3 gives t = 1.

Word problems

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.

Singleton

Largest d for an [7, 4] code.

  1. n − k + 1
  2. Check: 4 ✓4.

Error-correcting power

A code has d = 3. Find t.

  1. ⌊(3 − 1)/2⌋
  2. Check: ✓1.

Sphere size Higher

Find the volume of a radius-1 ball in n = 7 binary space.

  1. 1 + 7
  2. Check: ✓8.

Hamming bound Higher

Largest M for n = 7, t = 1.

  1. 2⁷ ÷ 8
  2. Check: 16 (perfect) ✓16.

Common mistakes

Mixing k and M

d ≤ n − M + 1 ✗

d ≤ n − k + 1 ✓

k is the dimension.

Using d instead of t

balls of radius d ✗

radius t = ⌊(d − 1)/2⌋ ✓

Balls must be disjoint.

Forgetting the centre

sphere size 7 ✗

sphere size 1 + 7 ✓

Include the codeword.

Assuming the bound is attained

always ✗

only perfect codes meet it ✓

Often just an upper limit.

Exam tips

  1. Singleton: d ≤ n − k + 1.
  2. t = ⌊(d − 1)/2⌋.
  3. Sphere: Σ C(n, i).
  4. Hamming: M·V ≤ 2ⁿ.
  5. Perfect = equality.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Singleton d for [10, 6] Foundation

5

2. t for d = 5 Foundation

2

3. Ball volume n = 7, t = 2 Foundation

29

4. Hamming M bound n = 7, t = 1 Higher

16

5. Ball volume n = 15, t = 1 Higher

16

6. Hamming M bound n = 15, t = 1 Higher

2048

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Singleton bound
d ≤ n − k + 1.
Hamming bound
Sphere-packing upper bound on M.
Perfect code
Spheres tile the space.
Minimum distance (d)
Smallest distance between codewords.
Hamming ball
All words within distance t.
MDS code
Meets the Singleton bound.

Frequently asked questions

What is the Singleton bound?

d ≤ n − k + 1.

What is the Hamming bound?

M·Σ_{i≤t} C(n, i) ≤ 2ⁿ.

What is a perfect code?

One meeting the Hamming bound with equality.

What is t?

⌊(d − 1)/2⌋ errors corrected.

Which page covers the BSC?

binary symmetric channel.

Which page covers the Kraft inequality?

Kraft inequality.

More in Advanced statistics and stochastic processes and the formula sheets.