Error Detection and Correction

Tip

Exam Focus

High-yield items: single-bit vs. burst errors and code rate $R_c=k/n$; parity (detects any odd count), 2-D parity/LRC and one’s-complement checksum; the full CRC recipe $T(x)=D(x)x^{r}+R(x)$ with the worked division of $1101011011$ by $10011$ (remainder $1110$); Hamming distance rules $d_{\min}\ge s+1$ (detect) and $d_{\min}\ge 2t+1$ (correct); the $(7,4)$ Hamming encode/syndrome decode; and the FEC-vs-ARQ comparison with stop-and-wait, go-back-N and selective-repeat.

Error Fundamentals

A digital channel may change transmitted bits because of thermal noise, impulse noise, interference, fading, attenuation, timing error or intersymbol interference. A channel encoder maps $k$ information bits to an $n$-bit codeword; the added $n-k$ bits are redundancy used to identify or repair invalid received patterns.

Error-control taxonomy: detection identifies corruption, FEC adds redundancy for local correction, and ARQ uses feedback and retransmission.

Error detection decides only that the received word is invalid, so the receiver discards, flags or requests retransmission. Error correction locates the most likely error pattern and rebuilds a valid codeword locally. No finite code corrects an unlimited number of arbitrary errors.

Error Types

A single-bit error flips exactly one bit, e.g. $10110110\to10100110$. Multiple random errors corrupt several separated positions. A burst error spans from the first to the last corrupted bit; its burst length counts any correct bits in between:

$$\underbrace{110101001011}_{\text{sent}}\ \to\ \underbrace{110011111011}_{\text{received}},\qquad \text{burst length}=5.$$

Burst errors dominate on channels with impulse noise, deep fades and sync loss; CRC and interleaved block codes defend against them.

Redundancy and Code Rate

Caution

Key Formula — Code rate of an $(n,k)$ block code

$$R_c=\frac{k}{n}.$$

A lower code rate means more redundancy and potentially stronger protection, but more bandwidth or lower net information rate. The receiver exploits the algebraic structure of valid codewords to decide plausibility and, for a correcting code, the nearest valid word.

Parity and LRC

Caution

Key Formula — Even/odd parity bit

$$P_e=D_0\oplus D_1\oplus\cdots\oplus D_{m-1},\qquad P_o=\overline{P_e}.$$

At the receiver the XOR of all bits is the parity syndrome.

Note

Law — Single-parity capability

Detects every odd number of bit errors (including any single error); misses every even-count pattern; cannot locate or correct; costs one bit. It is wrong to say parity detects only one-bit errors — it detects any odd count.

Two-Dimensional Parity / LRC

Data is arranged in rows and columns; a parity bit is added to each row and a parity row across columns (the column set is the Longitudinal Redundancy Check, LRC). A single flipped data bit fails exactly one row and one column, and their intersection locates — hence corrects — the bit.

	$C_1$	$C_2$	$C_3$	$C_4$	Row parity
$R_1$
$R_2$
$R_3$
Col. parity

Two-dimensional (row/column) even parity; the LRC is the bottom row.

Some rectangular patterns with an even number of changes in every affected row and column remain undetected.

Checksum

A checksum treats data as fixed-width words. Internet-style checksums use one’s-complement arithmetic with end-around carry.

Note

Law — Checksum procedure

Tx: split into $n$-bit words $\to$ add in one’s complement $\to$ wrap any carry beyond bit $n$ back into the LSB $\to$ complement the sum and send it.
Rx: add all data words and the checksum with the same rule; an all-ones result means no error was detected.

[!NOTE]

Example — Worked 8-bit checksum

Words $\mathtt{AA},\mathtt{66},\mathtt{3C}$ (hex):

$$\begin{aligned} \mathtt{10101010}+\mathtt{01100110}&=\mathtt{1\,00010000}\ \Rightarrow\ \text{end-around}\ \mathtt{00010001}=\mathtt{11},\\ \mathtt{00010001}+\mathtt{00111100}&=\mathtt{01001101}=\mathtt{4D},\\ \text{checksum}&=\overline{\mathtt{4D}}=\mathtt{10110010}=\mathtt{B2}. \end{aligned}$$

Receiver test: $\mathtt{AA}+\mathtt{66}+\mathtt{3C}+\mathtt{B2}=\mathtt{FF}$ (all ones) $\Rightarrow$ OK.

Checksums are simple to implement in software and detect many common error patterns, but a well-designed CRC provides stronger guaranteed burst-error detection.

Cyclic Redundancy Check (CRC)

CRC interprets a bit string as a polynomial over $GF(2)$, where addition and subtraction are both XOR. Let $D(x)$ be the data, $G(x)$ the agreed generator of degree $r$, $R(x)$ the remainder ($\deg R<r$) and $T(x)$ the codeword.

Caution

Key Formula — CRC encoding

$$R(x)=\operatorname{rem}\!\left[\frac{D(x)\,x^{r}}{G(x)}\right],\qquad T(x)=D(x)\,x^{r}+R(x).$$

Because subtraction equals addition in $GF(2)$, $T(x)$ is exactly divisible by $G(x)$.

CRC flow: the message is shifted by $x^{r}$, divided mod-2 by the generator $g(x)$, and the remainder is appended as the frame-check sequence; the receiver re-divides and a zero remainder indicates no detected error.

Note

Law — Receiver rule

Divide the received word by the same $G(x)$: zero remainder $\Rightarrow$ no error detected; nonzero $\Rightarrow$ corruption. A zero remainder does not prove an error-free frame — an error pattern that is a multiple of $G(x)$ is undetected.

[!NOTE]

Example — CRC division: $D=1101011011$, $G=10011$ ([10] marks)

Generator degree $r=4$, so append four zeros: dividend $=1101011011\,0000$. Modulo-2 long division XORs $10011$ only under a leading $1$:

Lead pos.	Window	XOR $10011$	Result
	11010	10011	01001
1	10011	10011	00000
6	10110	10011	00101
8	10100	10011	00111

The four low-order bits give the remainder, hence the transmitted codeword:

$$R=1110,\qquad T=1101011011\,1110.$$

Receiver: $11010110111110\div10011\to$ remainder $0000$ (OK). If one bit flips, the received polynomial is $T(x)+E(x)$ and the syndrome is $\operatorname{rem}[E(x)/G(x)]$.

Practice tip: write the polynomial rule, show every nonzero XOR window, box $R$ and $T$, then state the qualified detection properties.

[!NOTE]

Key Point — CRC detection properties

• Every burst of length $\le r$ is detected.

• If $G(x)$ has $>1$ nonzero term, all single-bit errors are detected.

• A suitably chosen generator detects all two-bit errors within its specified frame-length limit; for primitive degree-$r$ $G(x)$, $n\le 2^r-1$ suffices.

• If $(x+1)\mid G(x)$, every odd number of bit errors is detected.

• For random longer bursts the undetected fraction is $\approx 2^{-r}$.

Degree alone does not guarantee every property — generator choice matters.

Hamming Distance and Code Capability

The Hamming distance between equal-length words is the number of positions in which they differ (the weight of their XOR); e.g. $d(101100,100110)=2$. The minimum distance $d_{\min}$ is the smallest distance between any two distinct codewords.

Caution

Key Formula — Detection and correction capability

$$d_{\min}\ge s+1\ \Rightarrow\ \text{detect } s \text{ errors},\qquad s_{\max}=d_{\min}-1,$$$$d_{\min}\ge 2t+1\ \Rightarrow\ \text{correct } t \text{ errors},\qquad t_{\max}=\left\lfloor\frac{d_{\min}-1}{2}\right\rfloor.$$

Turning one valid codeword into another needs $\ge d_{\min}$ changes; for correction the radius-$t$ decoding spheres must not overlap. Hamming $(7,4)$ has $d_{\min}=3$, so it corrects one error (or detects up to two if used only for detection). Reliable simultaneous double-error detection needs an added overall parity bit (SECDED).

Hamming (7,4) Code

Hamming code is a linear block code for single-error correction.

Caution

Key Formula — Parity-bit count

$$2^{r}\ge m+r+1.$$

An $r$-bit syndrome has $2^r$ possible values. The all-zero value represents the no-error state, and a distinct nonzero value must identify each of the $m+r$ possible single-bit error positions. Thus at least $m+r+1$ syndrome states are required.

For $m=4$, $r=3$ suffices since $2^{3}=8\ge 4+3+1$. Parity bits occupy power-of-two positions $1,2,4$; data occupy $3,5,6,7$.

Hamming $(7,4)$ bit layout: parity $P_1,P_2,P_4$ at power-of-two positions $1,2,4$; data $D_1$ – $D_4$ at $3,5,6,7$. Each parity bit covers the positions whose binary index includes its weight.

Caution

Key Formula — Even-parity equations

$$P_1\oplus D_1\oplus D_2\oplus D_4=0,\quad P_2\oplus D_1\oplus D_3\oplus D_4=0,\quad P_4\oplus D_2\oplus D_3\oplus D_4=0.$$

[!NOTE]

Example — Hamming (7,4) encode and correct ([10] marks)

Encode $D_1D_2D_3D_4=1011$ (positions $3,5,6,7=1,0,1,1$):

$$P_1\oplus1\oplus0\oplus1=0\Rightarrow P_1=0,\quad P_2\oplus1\oplus1\oplus1=0\Rightarrow P_2=1,\quad P_4\oplus0\oplus1\oplus1=0\Rightarrow P_4=0.$$

Codeword $\mathbf{c}=0110011$.

Correct: bit $5$ flips, so $\mathbf{r}=0110111$. Recompute checks:

$$S_1=b_1\oplus b_3\oplus b_5\oplus b_7=0\oplus1\oplus1\oplus1=1,$$$$S_2=b_2\oplus b_3\oplus b_6\oplus b_7=1\oplus1\oplus1\oplus1=0,\quad S_4=b_4\oplus b_5\oplus b_6\oplus b_7=0\oplus1\oplus1\oplus1=1.$$

Syndrome $S_4S_2S_1=101_2=5_{10}$ names the erroneous bit. Flip bit $5$ to restore $0110011$; extract positions $3,5,6,7\Rightarrow 1011$. Syndrome $000$ means no error. The code rate is $4/7$.

Practice tip: derive $2^{r}\ge m+r+1$, fill the seven positions, compute all three parity bits and decode a nonzero syndrome.

Adding one overall parity bit yields SECDED (Single-Error Correction, Double-Error Detection): the ordinary syndrome locates a single error while the overall parity separates single from double errors.

Forward Error Correction and ARQ

Forward Error Correction (FEC)

The transmitter sends structured redundancy so the receiver corrects errors without asking for a resend. Examples: Hamming/BCH block codes, Reed–Solomon, convolutional, turbo and LDPC codes. FEC suits large round-trip delay, absent feedback and continuous real-time delivery (satellite, broadcast, deep-space).

Automatic Repeat Request (ARQ)

ARQ combines error detection (usually CRC) with feedback, sequence numbers, ACK/NAK and timeout; damaged or missing frames are retransmitted.

Method	Operation	Trade-off
Stop-and-Wait	Send one frame, wait for ACK; timeout/NAK resends it	Simple; link idle each round trip
Go-Back-N	Pipeline a window; on error resend the failed frame and all later unacked frames	Simple receiver; repeats correct frames
Selective Repeat	Buffer a window; resend only missing/damaged frames	Highest efficiency; more buffering/control

The three classic ARQ schemes.

Caution

Key Formula — Stop-and-wait utilisation

$$\eta\approx\frac{T_f}{T_f+2T_p}=\frac{1}{1+2a},\qquad a=\frac{T_p}{T_f},$$

with $T_f$ the frame time and $T_p$ the one-way propagation delay — which is why pipelined GBN/SR win on long-delay links.

Feature	FEC	ARQ
Feedback	Not required	Required
Added redundancy	Usually greater (every codeword)	Detection bits $+$ retransmitted frames
Delay	Predictable decoding delay	Variable; large after retransmission
Best channel	Broadcast, real-time, high-delay	Reliable two-way, moderate delay
Residual errors	Possible beyond capability	Very low after valid delivery

FEC versus ARQ. Modern systems often use Hybrid ARQ, combining FEC with selective retransmission.

Note

Example — FEC vs ARQ with a lost frame ([10] marks)

Frames $0,1,2,3$ are sent in a window and frame $1$ is lost. Stop-and-Wait would not yet have sent $2$ or $3$. In Go-Back-N the receiver discards out-of-order $2,3$ and the sender resends $1,2,3$ after timeout/cumulative ACK. In Selective Repeat the receiver buffers $2,3$ and the sender resends only frame $1$; in-order delivery resumes when $1$ arrives. With $m$ sequence bits, GBN allows a window $\le 2^{m}-1$ while SR limits each window to $\le 2^{m-1}$ to avoid wrap-around ambiguity.

Practice tip: draw the feedback path, compare all three windows on one lost-frame example, and state the sequence-number limits.

[!NOTE]

Key Point — Revision — Error Control

• Single parity detects any odd error count; misses even counts.

• 2-D parity/LRC locates one bit from the failed row/column intersection.

• Checksum uses word addition; CRC uses polynomial division over $GF(2)$.

• CRC codeword $T(x)=D(x)x^{r}+R(x)$; valid receiver remainder $=0$.

• $D=1101011011$, $G=10011\Rightarrow R=1110$.

• Detect: $d_{\min}\ge s+1$; correct: $d_{\min}\ge 2t+1$, $t_{\max}=\lfloor(d_{\min}-1)/2\rfloor$.

• Hamming parity at powers of two; $2^{r}\ge m+r+1$; syndrome $S_4S_2S_1$ names the bad bit.

• FEC corrects locally (no feedback); ARQ detects and retransmits; Hybrid ARQ combines both.