Error Detection and Correction¶

Exam-ready answer

A channel code maps \(k\) information bits into an \(n\)-bit codeword. The extra \(n-k\) redundant bits create structure by which a receiver can recognize or repair corrupted words; its code rate is \(R_c=k/n\).

Error detection decides that a received word/frame is invalid or inconsistent, but need not identify the changed bit. The receiver then flags or discards it, or requests retransmission. Parity, checksum and CRC are common examples. Error correction uses enough redundancy to locate the most likely error pattern and recover a valid codeword locally, as in Hamming, BCH or LDPC coding. Correction is limited by the code's minimum distance; no finite code corrects arbitrarily many changes.

A single-bit error changes exactly one position. For example, \(10110110\rightarrow10100110\) changes bit 4 under left-to-right numbering. It may arise from an isolated noise impulse or a wrong threshold decision.

A burst error extends from the first corrupted bit through the last corrupted bit; correct bits lying between them still count in the burst length. For example,

The first and last changes span five positions, so the burst length is 5 even if not all five bits changed. Bursts are typical of impulse noise, fading, synchronization loss and intersymbol interference. Interleaving converts adjacent channel errors into separated codeword errors; CRC is strong for burst detection, while FEC or ARQ supplies recovery. The selected remedy depends on delay, feedback availability and required residual error rate.

Practice target: 8 minutes; define codeword/redundancy, contrast receiver action, and give one indexed example of each error type.

Exam-ready answer

These methods add redundant check information but differ in whether they operate on individual bits, a bit matrix or fixed-width words.

Single parity: for data \(D_0,\ldots,D_{m-1}\), an even-parity bit is

and odd parity uses \(P_o=\overline{P_e}\). The receiver XORs all data and parity bits. Even parity expects syndrome 0. It detects every odd number of flips, including one bit, but misses every even-count pattern and cannot locate/correct an error by itself. For data \(1011\), three ones require \(P_e=1\), giving code \(10111\) with four ones.

Two-dimensional parity/LRC: arrange words as rows, append one parity bit per row, then append a parity row across columns; column parity is the longitudinal redundancy check. One changed data bit makes exactly one row and one column fail, so their intersection locates and can correct that bit. It detects many bursts, but a rectangular four-bit pattern with an even number of changes in every affected row/column can pass all checks.

Checksum: divide data into \(n\)-bit words, add them using one's-complement arithmetic, wrap each carry beyond bit \(n\) back into the LSB, complement the final sum, and transmit it. The receiver adds all words including the checksum; an all-ones result means no error was detected. With 8-bit words \(AA_{16},66_{16},3C_{16}\), end-around-carry addition gives \(4D_{16}\), so the checksum is \(\overline{4D}_{16}=B2_{16}\) and the receiver sum is \(FF_{16}\). A checksum is efficient in software and detects many patterns, but lacks the strong generator-dependent burst guarantees of a well-chosen CRC.

Practice target: 9 minutes; write the XOR law, show the failed-row/column intersection, and complete one end-around-carry checksum.

Exam-ready answer

A cyclic redundancy check (CRC) treats a bit string as polynomial coefficients over \(GF(2)\). Addition and subtraction are XOR, so there are no carries or borrows. Let data be \(D(x)\), generator \(G(x)\) of degree \(r\), and remainder \(R(x)\) with degree below \(r\).

The transmitter appends \(r\) zeros, divides \(D(x)x^r\) by \(G(x)\) and appends the \(r\)-bit remainder:

Because plus and minus are identical in \(GF(2)\), \(T(x)\) is divisible by \(G(x)\). The receiver divides the entire received word by the same generator: nonzero remainder means detected error; zero means only that no detectable error pattern was found.

Given \(D=1101011011\) and \(G=10011\). The generator has five bits, so \(r=4\) and the augmented dividend is

Modulo-2 long division XORs \(10011\) only under a current leading 1:

Positions with leading 0 require only a shift. After the final allowable shift, the four unprocessed low-order bits are

Thus the transmitted systematic codeword is

A receiver division gives

confirming that the uncorrupted codeword is a multiple of the generator. If one channel bit flips, the received polynomial becomes \(T(x)+E(x)\); the syndrome is the remainder of \(E(x)/G(x)\).

For a suitably chosen degree-\(r\) generator, every burst of length at most \(r\) is detected and the undetected fraction of random longer bursts is approximately \(2^{-r}\). All single-bit errors are detected when \(G(x)\) has more than one nonzero term; all odd-count errors are detected if \((x+1)\) is a factor. Guaranteed two-bit capability also depends on generator order and frame length. Therefore degree alone does not justify every CRC claim, and a zero remainder does not prove an error-free frame: an error polynomial that is a multiple of \(G(x)\) is undetected.

Practice target: 18–20 minutes; write the polynomial rule, show every nonzero XOR window, box remainder/codeword, and finish with qualified detection properties.

Exam-ready answer

The Hamming distance \(d(\mathbf{x},\mathbf{y})\) between equal-length binary words is the number of positions in which they differ, equivalently the Hamming weight of \(\mathbf{x}\oplus\mathbf{y}\). For example,

The minimum distance \(d_{min}\) of a block code is the smallest distance between any two distinct valid codewords. It determines how close the codewords are in the \(n\)-dimensional binary space.

To turn one valid codeword into another requires at least \(d_{min}\) bit changes. Hence every pattern of at most \(s\) errors is guaranteed detectable provided it cannot reach another valid word:

For correction, decode to the nearest codeword. Radius-\(t\) error spheres around different codewords must not overlap. Since their centers are \(d_{min}\) apart,

Thus a repetition code with valid words \(000\) and \(111\) has \(d_{min}=3\): it detects up to two flips or corrects one by majority decision. Hamming \((7,4)\) also has \(d_{min}=3\), so it is a single-error-correcting code. Although distance three permits double-error detection when used only as a detector, an ordinary decoder that assumes at most one error may miscorrect a double error; adding overall parity gives SECDED for reliable single correction plus double detection.

Practice target: 8–9 minutes; define distance by XOR, derive both inequalities geometrically, and test them on one distance-three code.

Exam-ready answer

Hamming \((7,4)\) is a linear block code carrying \(m=4\) data bits and \(r=3\) parity bits. To identify the no-error case plus each of \(m+r\) possible single-bit positions, parity bits must satisfy

Here \(2^3=8=4+3+1\). Parity bits occupy power-of-two positions 1, 2 and 4; data occupy 3, 5, 6 and 7.

For even parity, \(P_1\) checks positions \(1,3,5,7\) (binary index LSB 1), \(P_2\) checks \(2,3,6,7\), and \(P_4\) checks \(4,5,6,7\).

Encode data \(D_1D_2D_3D_4=1011\). Place it as

The even-parity equations give

Therefore

Single-error example: suppose position 5 changes from 0 to 1, so the receiver gets \(\mathbf{r}=0110111\). Recalculate the parity checks:

Read the syndrome in order \(S_4S_2S_1\):

The binary syndrome directly names the erroneous position. Flip bit 5 to restore \(0110011\), then extract positions \(3,5,6,7\) to recover \(1011\). Syndrome \(000\) means no error detected under the assumed model.

Hamming \((7,4)\) has \(d_{min}=3\) and corrects one arbitrary bit error. A plain single-error decoder can miscorrect two errors, so an eighth overall parity bit is added for SECDED when simultaneous single correction and guaranteed double-error detection are required. The code rate is \(4/7\), illustrating the bandwidth/redundancy cost of local correction.

Practice target: 18–20 minutes; derive the parity-bit count, fill the seven positions, calculate all three parity bits and decode a nonzero syndrome.

Exam-ready answer

Error control either adds enough redundancy for local repair or retransmits a frame that fails an error-detection check.

Forward Error Correction (FEC): the transmitter sends a structured \((n,k)\) code of rate \(R_c=k/n\). The decoder uses syndrome, distance or soft information to correct errors without feedback. Hamming, Reed-Solomon, convolutional, turbo and LDPC codes are examples. FEC gives predictable latency and is essential for broadcast, real-time, satellite/deep-space and links with unavailable/slow feedback. Its costs are continuous redundancy, decoder complexity and residual errors beyond code capability.

Automatic Repeat Request (ARQ): each frame carries a detection code, normally CRC, plus a sequence number. The receiver sends ACK for accepted data or NAK for detected damage; loss is inferred by timeout. Retransmission can make residual error very low on a two-way channel, but delay and throughput vary with errors and round-trip time.

With \(m\) sequence bits, a conventional GBN sender window is at most \(2^m-1\) frames. Selective Repeat normally limits sender/receiver windows to at most \(2^{m-1}\) so an old frame cannot be confused with a new one after sequence-number wrap.

Worked protocol example: frames 0, 1, 2 and 3 are sent in a window and frame 1 is lost. Stop-and-Wait could not have sent 2 or 3 yet. In GBN, the receiver rejects/out-of-order-handles 2 and 3 according to the protocol and the sender retransmits 1, 2 and 3 after timeout/cumulative feedback. In SR, the receiver buffers 2 and 3 and the sender retransmits only frame 1; delivery resumes in order when 1 arrives.

Ignoring ACK transmission time and errors, Stop-and-Wait utilization is approximately

where \(T_f\) is frame transmission time and \(T_p\) one-way propagation delay. This assumption-dependent equation shows why pipelined GBN/SR are valuable on long-delay links.

Hybrid ARQ combines both: FEC corrects typical errors and retransmission handles blocks that still fail CRC.

Practice target: 18–20 minutes; draw the feedback path, compare all three windows with one lost-frame example, and state sequence-number limits.