Q7(b) · Block coding

A transmission error changes one or more bits. A single-bit error flips one bit. A burst error affects a span from the first corrupted bit to the last; the bits in between need not all change. Detection identifies an invalid received pattern; correction identifies the intended pattern within the code’s guaranteed capability.

Block coding

1. Divide data into fixed k-bit datawords. Map each one to an n-bit codeword, with n greater than k.
2. The n−k redundant bits create separation between valid codewords. There are 2^k valid codewords, a subset of the 2ⁿ possible n-bit patterns, for an injective binary block code.
3. A receiver can reject patterns that are not valid codewords. Nearest-codeword decoding can correct errors only if the received pattern has an unambiguous nearest intended codeword under the error bound.
4. Error-control protocols may combine detection with retransmission (ARQ), or use sufficient coding redundancy for forward error correction (FEC).

LaTeX: R_c=k/n,\quad r=n-k

Hamming distance d(a,b) is the number of positions where two equal-length bit strings differ. XOR the strings and count the 1s. Minimum distance d_min is the smallest distance between distinct valid codewords; do not use the largest pairwise distance.

LaTeX: d(a,b)=\mathrm{weight}(a\oplus b)

LaTeX: s_{\max}=d_{\min}-1,\qquad t_{\max}=\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor

1. Detection: fewer than dmin flips cannot transform one valid codeword into another, so all such errors are detected.
2. Correction: radius-t error regions around different codewords must not overlap. Therefore 2t < dmin, or dmin ≥ 2t+1.
3. These are separate maximum guaranteed capabilities. A code with dmin=3 detects up to two errors in detection mode and corrects one in correction mode; that statement does not promise simultaneous correction of one and reliable identification of every two-error event under the same nearest-codeword decoder.