Recipe

Find a code's correction radius and decode by nearest codeword

Use when: you have a code's minimum distance (or the codewords needed to find it) and a received word, and need the guaranteed correction radius, the decoded codeword, or both

Goal: the correction radius $t=\lfloor(d_{min}-1)/2\rfloor$ , and the nearest codeword to the received word

Taught in Hamming distance and minimum distance

Quick recipe

Compute $d_H$ between two bit-strings by comparing position by position
Find (or confirm) the code's minimum distance $d_{min}$
Compute the correction radius $t=\lfloor(d_{min}-1)/2\rfloor$
If a specific received word is given, decode it to the nearest codeword

1
Line the two strings up and count the positions where they disagree.

Example

For $x=100000$ and $y=111000$ : positions 1 and 4-6 agree, positions 2 and 3 disagree, so $d_H(x,y)=2$ .

Why: this single count is the raw ingredient behind both the correction radius and nearest-codeword decoding.
2
If not already given, compute $d_H$ between every pair of distinct codewords and take the smallest.

Example

For codewords $000000$ , $111000$ , $000111$ : the pairwise distances are $3$ , $3$ , and $6$ , so $d_{min}=3$ .

Why: the correction and detection guarantees both depend on the smallest gap between any two codewords, not just the specific pair a message happens to land near.
3
Apply the floor formula to $d_{min}$ from Step 2.

Example

$t=\lfloor(3-1)/2\rfloor=1$ .

Why: this is the largest number of bit flips nearest-codeword decoding is guaranteed to correct, derived from requiring the true codeword to be strictly closer than every other one.
4
Compute $d_H$ from the received word to every codeword and pick the smallest.

Example

Received $100000$ : distances to $000000$ , $111000$ , $000111$ are $1$ , $2$ , and $4$ . Nearest codeword is $000000$ , and since only $1\le t=1$ bit actually flipped, this decoding is guaranteed correct.
- the actual number of flips is within the correction radius $t$ — decoding is guaranteed correct.
- the actual number of flips exceeds $t$ — nearest-codeword decoding might still land on the right answer, but there's no guarantee either way.
Why: the correction radius is a worst-case guarantee, not a claim that decoding always fails beyond it; it's simply where the guarantee stops holding.

Common mistakes

Computing $d_{min}$ from only one pair of codewords instead of checking every pair, missing a smaller gap elsewhere in the code.
Rounding $\lfloor(d_{min}-1)/2\rfloor$ up instead of down, especially when $d_{min}$ is even, which overstates how many errors are actually guaranteed correctable.
Concluding decoding must be wrong just because the actual number of flips exceeds $t$ ; beyond $t$ there's simply no guarantee, not a guaranteed failure.
Decoding to the codeword with the smallest index or the first one checked, instead of genuinely comparing distances to every codeword.