IN THE EC SYLLABUS

Error detection and correction

Error detection and correction adds controlled redundancy to the data so that the receiver can notice, and sometimes repair, bits flipped by the channel. For GATE you need the distance rules (detect d_min - 1, correct floor((d_min - 1)/2)), the matrix tools of linear block codes (generator matrix, parity-check matrix, syndrome), the Hamming bound, the (7,4) Hamming code in both its systematic and positional forms, block-error probability on a binary symmetric channel, and the CRC computed by polynomial division over GF(2).

5 previous-year questions · 5 solved · 5 practice questions

Redundancy, code rate and distance

A block code maps $k$ message bits to an $n$ -bit codeword, with $n > k$ . The extra $n - k$ bits are redundancy. Only $2^{k}$ of the $2^{n}$ possible words are valid codewords, so a received word that is not a codeword tells the receiver that bits were flipped.

CODE RATE

R = \frac{k}{n}

Fraction of transmitted bits that carry message information; $0 < R < 1$ for an $(n, k)$ block code, since $n > k$ .

The Hamming distance between two words of equal length is the number of positions in which they differ. The minimum distance $d_{min}$ of a code is the smallest Hamming distance between any two distinct codewords. The Hamming weight of a word is its number of 1s. Any pattern of between $1$ and $d_{min} - 1$ flipped bits always turns a codeword into a word that is not a codeword.

DETECTION CAPABILITY

s_{ma x} = d_{min} - 1

A code with minimum distance $d_{min}$ is guaranteed to detect every pattern of up to $d_{min} - 1$ bit errors, when it is used for detection only.

CORRECTION CAPABILITY

t = ⌊ \frac{d _{min} - 1}{2} ⌋

Guaranteed number of correctable errors when the receiver decodes to the nearest codeword (the spheres of radius $t$ around codewords do not overlap).

SIMULTANEOUS CORRECTION AND DETECTION

d_{min} \geq t + s + 1 (s \geq t)

With this distance the decoder corrects every pattern of up to $t$ errors and, at the same time, detects (flags without miscorrecting) every pattern of $t + 1$ up to $s$ errors. Here $s$ is a total number of errors, not extra errors.

For a linear code the minimum distance equals the smallest Hamming weight among the nonzero codewords, because the sum of two codewords is again a codeword.

EXAM TIP

Detection and correction rules are guarantees. A code may do better on particular error patterns, but the formulas above count only what is certain for every pattern. Also note that correcting $t$ errors and detecting $d_{min} - 1$ errors are alternatives, not both at once: use $d_{min} \geq t + s + 1$ for a mix.

Parity checks and linear block codes

A single even-parity bit is appended so that the total number of 1s in the codeword is even (odd parity makes it odd). The result is an $(n, n - 1)$ code with $d_{min} = 2$ . It detects every odd number of bit errors and misses every even number of errors. It cannot correct anything, because it does not say which bit is wrong.

The repetition code $(n, 1)$ sends each bit $n$ times. Its two codewords are all-0s and all-1s, so $d_{min} = n$ . For odd $n$ , a majority vote corrects up to $(n - 1) /2$ errors; the rate is only $1/ n$ .

A linear block code is one where the sum (modulo 2, bitwise XOR) of any two codewords is a codeword. It is described by a $k \times n$ generator matrix $G$ . All arithmetic is over GF(2): $1 + 1 = 0$ .

ENCODING

c = m G

Row vector $m$ (length $k$ ) times $G$ gives the codeword $c$ (length $n$ ), all operations modulo 2.

SYSTEMATIC FORM

G = [I_{k} P], H = [P^{T} I_{n - k}]

Message bits appear unchanged in the first $k$ positions of the codeword; $P$ is $k \times (n - k)$ . Over GF(2), $- P^{T} = P^{T}$ .

PARITY-CHECK CONDITION

H c^{T} = 0, G H^{T} = 0

$H$ is $(n - k) \times n$ . A word is a codeword exactly when every parity check is satisfied.

DISTANCE FROM H

d_{min} = smallest number of columns of H that add to 0

For a linear code. Equivalently, $d_{min} \geq 3$ exactly when all columns of $H$ are nonzero and distinct.

Syndrome decoding

Let $r = c + e$ be the received word, where $e$ is the error pattern (1 in each flipped position). The receiver computes the syndrome, which depends on the error pattern only, not on which codeword was sent.

SYNDROME

s = H r^{T} = H e^{T}

$s = 0$ means $r$ is a valid codeword (no detectable error). A nonzero $s$ means an error occurred.

Syndrome decoding procedure

Compute $s = H r^{T}$ .
If $s = 0$ , accept $r$ .
Otherwise find the lowest-weight error pattern $e$ whose syndrome equals $s$ ; on a binary symmetric channel with bit-error probability $p < 1/2$ this is the most likely pattern (for a single error, the column of $H$ that equals $s$ tells the position).
Correct by $\hat{c} = r + e$ and read off the message bits.

For a single error in position $i$ , the syndrome is the $i$ -th column of $H$ . So to correct every single error the columns must be nonzero (otherwise an error would be invisible) and distinct (otherwise two error positions would give the same syndrome).

HAMMING (SPHERE-PACKING) BOUND

2^{n - k} \geq i = 0 \sum t (i n)

Any binary $(n, k)$ code that corrects every pattern of up to $t$ errors must satisfy this: the $2^{n - k}$ syndromes must label every correctable error pattern, including the no-error pattern. A code that meets it with equality is called perfect.

Hamming codes

A Hamming code is a single-error-correcting linear code with $d_{min} = 3$ . Its parity-check matrix has, as columns, all the nonzero binary vectors of length $r$ , each used once.

NUMBER OF PARITY BITS

2^{r} \geq m + r + 1

Smallest $r$ that lets $m$ data bits be protected against any single error: the $r$ check bits must label the $m + r$ error positions plus the no-error case.

HAMMING CODE PARAMETERS

n = 2^{r} - 1, k = n - r = 2^{r} - 1 - r, d_{min} = 3

Full-length Hamming code, $r \geq 2$ . Correct one error, or detect two (not both together). Since $1 + n = 2^{r}$ , it meets the Hamming bound with $t = 1$ exactly, so Hamming codes are perfect.

r	n	k	Code	Rate k/n
3	7	4	(7,4)	4/7
4	15	11	(15,11)	11/15
5	31	26	(31,26)	26/31

The (7,4) code used in this chapter has, in systematic form, the matrices below.

(7,4) HAMMING CODE MATRICES

G = 1000010000100001101111100111, H = 110011111101100010001

Codeword is (d1 d2 d3 d4 p1 p2 p3). The seven columns of $H$ are the seven distinct nonzero 3-bit vectors, so the code corrects any single error.

An extended Hamming code adds one overall parity bit to a Hamming code. This raises $d_{min}$ to 4, so it corrects one error and detects two at the same time.

WORKED EXAMPLE

For the (7,4) code with the $G$ and $H$ above, encode the message $1011$ . The word $1001100$ is then received. Find the syndrome and the corrected codeword.

Solution

Parity bits: $p = d P$ . With $d = 1011$ , add rows 1, 3 and 4 of $P$ : $110 + 111 + 101 = 100$ (mod 2).
Codeword: $1011100$ . Check: $H c^{T} = 0$ (row 1 uses bits 1, 3, 4, 5: $1 + 1 + 1 + 1 = 0$ ).
Received $r = 1001100$ differs from $c$ in position 3.
Syndrome: row 1 (bits 1, 3, 4, 5) gives $1 + 0 + 1 + 1 = 1$ ; row 2 (bits 1, 2, 3, 6) gives $1 + 0 + 0 + 0 = 1$ ; row 3 (bits 2, 3, 4, 7) gives $0 + 0 + 1 + 0 = 1$ . So $s = (1, 1, 1)^{T}$ .
Column 3 of $H$ is $(1, 1, 1)^{T}$ , so the error is in bit 3. Flip it: corrected word $1011100$ , message $1011$ .

Answer: Codeword 1011100; syndrome 111 points to bit 3; corrected word 1011100.

Positional form. The same Hamming code is often written with its bit positions reordered: number the positions $1$ to $n$ , put the parity bits at the positions that are powers of 2 ( $1, 2, 4, 8, \dots$ ) and the data bits in the remaining positions in order. Column $i$ of $H$ is then the binary number $i$ , so the syndrome, read as a binary number, is the position of a single error directly.

Positional Hamming code rules (even parity)

The parity bit at position $2^{j}$ checks every position whose binary index has a 1 in bit $j$ (for $n = 7$ : $p_{1}$ checks 1, 3, 5, 7; $p_{2}$ checks 2, 3, 6, 7; $p_{4}$ checks 4, 5, 6, 7).
Each parity bit is set so that its group has an even number of 1s.
At the receiver, recompute each check ( $c_{1}, c_{2}, c_{4}, \dots$ ; 1 = failed). The number $c_{4} c_{2} c_{1}$ in binary is the error position; $000$ means no error.

WORKED EXAMPLE

Using the positional (7,4) Hamming code with even parity, encode the data $1011$ (placed in positions 3, 5, 6, 7 in that order). Bit 6 is then flipped by the channel. Show that the receiver finds the error.

Solution

Data: position 3 = 1, position 5 = 0, position 6 = 1, position 7 = 1.
$p_{1}$ (positions 3, 5, 7): $1 + 0 + 1 = 0$ , so $p_{1} = 0$ . $p_{2}$ (positions 3, 6, 7): $1 + 1 + 1 = 1$ , so $p_{2} = 1$ . $p_{4}$ (positions 5, 6, 7): $0 + 1 + 1 = 0$ , so $p_{4} = 0$ .
Codeword (positions 1 to 7): $0110011$ .
Received after bit 6 flips: $0110001$ .
Checks: $c_{1}$ (1, 3, 5, 7) $= 0 + 1 + 0 + 1 = 0$ ; $c_{2}$ (2, 3, 6, 7) $= 1 + 1 + 0 + 1 = 1$ ; $c_{4}$ (4, 5, 6, 7) $= 0 + 0 + 0 + 1 = 1$ .
$c_{4} c_{2} c_{1} = 11 0_{2} = 6$ : the error is in position 6. Flipping it gives back $0110011$ .

Answer: Codeword 0110011; the checks read 110 = 6, the flipped position.

EXAM TIP

Check the data-bit requirement with the inequality before building anything: for $m = 11$ , $r = 4$ gives $16 \geq 16$ , so it just fits, and 11 data bits need 4 parity bits. For $m = 12$ , $r = 4$ gives $16 \geq 17$ , which fails, so $r = 5$ .

Error probability on a binary symmetric channel

Assume each bit is flipped independently with probability $p$ (a binary symmetric channel). The number of errors in an $n$ -bit block is then binomial.

BLOCK DECODING-ERROR PROBABILITY

P_{E} = i = t + 1 \sum n (i n) p^{i} (1 - p)^{n - i} = 1 - i = 0 \sum t (i n) p^{i} (1 - p)^{n - i}

Probability that a block has more than $t$ errors. It is exactly the probability of not decoding the block correctly for a decoder that corrects every pattern of up to $t$ errors and no other (for example a Hamming code, $t = 1$ ); for a decoder that also corrects some heavier patterns it is an upper bound.

UNDETECTED-ERROR PROBABILITY

P_{u} = i = d_{min} \sum n A_{i} p^{i} (1 - p)^{n - i}

For a linear code used for detection only: an error goes undetected exactly when the error pattern is itself a nonzero codeword. $A_{i}$ is the number of codewords of weight $i$ .

Cyclic redundancy check (CRC)

A CRC treats the message bits as the coefficients of a polynomial $M (x)$ over GF(2), with the leftmost bit as the coefficient of the highest power. It uses an agreed generator polynomial $g (x)$ of degree $r$ . The $r$ check bits are the remainder of a division, appended to the message, so every transmitted word is a multiple of $g (x)$ (a CRC code is a cyclic linear code). The receiver divides the whole received word by $g (x)$ and accepts it if the remainder is zero.

CRC COMPUTATION

R (x) = [x^{r} M (x)] mod g (x), T (x) = x^{r} M (x) + R (x)

Append $r$ zeros to the message, divide by $g (x)$ using XOR (no borrow), and the remainder $R (x)$ replaces the zeros. The transmitted word $T (x)$ is exactly divisible by $g (x)$ .

Computing a CRC by long division

Write $g (x)$ as a bit string of length $r + 1$ (a missing power gives a 0).
Append $r$ zeros to the message bits.
Bring down bits; whenever the leading bit of the current window is 1, XOR it with $g$ ; if it is 0, XOR with all zeros (just shift).
Continue until all bits are used. The last $r$ bits left are the CRC.
Send the message followed by the CRC; the receiver divides the received bits by $g$ and expects remainder 0.

WORKED EXAMPLE

The message is $1101011$ and the generator is $g (x) = x^{3} + x + 1$ . Find the transmitted word.

Solution

$g = 1011$ , $r = 3$ . Append three zeros: $1101011000$ .
Divide: $1101 \oplus 1011 = 0110$ , bring down 0: $1100 \oplus 1011 = 0111$ , bring down 1: $1111 \oplus 1011 = 0100$ , bring down 1: $1001 \oplus 1011 = 0010$ , bring down 0: $0100$ (leading 0, shift), bring down 0: $1000 \oplus 1011 = 0011$ , bring down 0: $0110$ (leading 0, shift) leaves remainder $110$ .
CRC bits $= 110$ . Transmitted word $= 1101011110$ .
Check: dividing $1101011110$ by $1011$ in the same way leaves remainder $000$ .

Answer: Transmitted word 1101011110 (CRC = 110).

Property of g(x) (degree r)	Errors guaranteed to be detected
Nonzero constant term ( $x^{0}$ coefficient 1)	Every burst of length $\leq r$ (a burst of length $L$ is a run from the first to the last flipped bit)
$x + 1$ is a factor	Every error pattern with an odd number of flipped bits
Nonzero constant term, and $g (x)$ does not divide $x^{k} + 1$ for any $k$ with $1 \leq k \leq n - 1$ ( $n$ = codeword length)	Every double error within the codeword (its error polynomial is $x^{i} (x^{k} + 1)$ )
Any $g (x)$ of degree $r$ with nonzero constant term	A burst of length $r + 1$ is missed with probability $2^{- (r - 1)}$ ; a longer burst with probability $2^{- r}$ (for equally likely patterns)

An error pattern $E (x)$ is missed exactly when $g (x)$ divides $E (x)$ , since the received polynomial is $T (x) + E (x)$ and $g (x)$ already divides $T (x)$ . This is why every guarantee in the table is a statement about which $E (x)$ $g (x)$ cannot divide.

EXAM TIP

Do not confuse the CRC with Hamming codes: in this chapter a CRC is used only to detect errors (a frame that fails the check is discarded or sent again), while a Hamming code locates and corrects a single error. In the long division you XOR bits only (no carries), and the quotient is never needed, only the remainder.

PREVIOUS-YEAR QUESTIONS

5 questions from the EC papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE ECE 2026 · GATE ECE 2025 · GATE ECE 2024 · GATE ECE 2022 · GATE ECE 2018

GATE 2026 EC Q.63

GATE 2026 · ECQ.63 · 2 marks · NAT

The average bit error rate at the input of a (7, 4, 1) Hamming decoder is 0.10. The probability that the decoder will fail to decode a received word correctly is __. (rounded off to two decimal places)

Answer and solution

GATE 2026 EC Q.63: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 EC Q.63: answer and solution

GATE 2025 EC Q.33

GATE 2025 · ECQ.33 · 1 mark · NAT

The generator matrix of a (6,3) binary linear block code is given by G = [[1,0,0,1,0,1],[0,1,0,0,1,1],[0,0,1,1,1,0]]. The minimum Hamming distance d_min between codewords equals _____ (answer in integer).

Answer and solution

GATE 2025 EC Q.33: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 EC Q.33: answer and solution

GATE 2024 EC Q.47

GATE 2024 · ECQ.47 · 2 marks · MCQ

The information bit sequence {1 1 1 0 1 0 1 0 1} is to be transmitted by encoding with Cyclic Redundancy Check 4 (CRC-4) code, for which the generator polynomial is $C (x) = x^{4} + x + 1$ . The encoded sequence of bits is ________.

(A)
{1 1 1 0 1 0 1 0 1 1 1 0 0}
(B)
{1 1 1 0 1 0 1 0 1 1 1 0 1}
(C)
{1 1 1 0 1 0 1 0 1 1 1 1 0}
(D)
{1 1 1 0 1 0 1 0 1 0 1 0 0}

Answer and solution

GATE 2024 EC Q.47: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 EC Q.47: answer and solution

GATE 2022 EC Q.62

GATE 2022 · ECQ.62 · 2 marks · NAT

Consider communication over a memoryless binary symmetric channel using a (7, 4) Hamming code. Each transmitted bit is received correctly with probability $(1 - ϵ)$ , and flipped with probability $ϵ$ . For each codeword transmission, the receiver performs minimum Hamming distance decoding, and correctly decodes the message bits if and only if the channel introduces at most one bit error. For $ϵ = 0.1$ , the probability that a transmitted codeword is decoded correctly is ________ (rounded off to two decimal places).

Answer and solution

GATE 2022 EC Q.62: answer and solution

See the question in the paper

Tap to open full size

GATE 2022 EC Q.62: answer and solution

GATE 2018 EC Q.16

GATE 2018 · ECQ.16 · 1 mark · NAT

Consider a binary channel code in which each codeword has a fixed length of 5 bits. The Hamming distance between any pair of distinct codewords in this code is at least 2. The maximum number of codewords such a code can contain is ______.

Answer and solution

GATE 2018 EC Q.16: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 EC Q.16: answer and solution

PRACTICE

5 questions to test yourself

PRACTICE 12 marks · MSQ

A block code has minimum distance $d_{min} = 5$ . Which of the following statements are guaranteed to be true?

(A)
It can detect every pattern of up to 4 bit errors when used for detection only.
(B)
It can correct every pattern of up to 2 bit errors when used for correction only.
(C)
It can correct every single-bit error and, at the same time, detect every pattern of up to 3 bit errors.
(D)
It can correct every pattern of up to 2 bit errors and, at the same time, detect every pattern of up to 3 bit errors.

Answer and solution

Answer: (A), (B), (C)

Detection only: $d_{min} - 1 = 4$ errors, so A is true.
Correction only: $⌊(5 - 1) /2 ⌋ = 2$ , so B is true.
Combined correction of $t$ and detection of $s$ needs $d_{min} \geq t + s + 1$ .
C: $t = 1$ , $s = 3$ gives $1 + 3 + 1 = 5 \leq 5$ , true.
D: $t = 2$ , $s = 3$ gives $6 > 5$ , not guaranteed.

PRACTICE 21 mark · NAT

A single-error-correcting Hamming-type code must protect $m = 26$ data bits. What is the minimum number of parity bits $r$ required, using $2^{r} \geq m + r + 1$ ?

Answer and solution

Answer: $5$

Try $r = 4$ : $2^{4} = 16$ versus $26 + 4 + 1 = 31$ , fails.
Try $r = 5$ : $2^{5} = 32$ versus $26 + 5 + 1 = 32$ , holds.
So the minimum is $r = 5$ (this is the (31,26) Hamming code).

PRACTICE 32 marks · NAT

A (7,4) linear code has the parity-check matrix $H$ with rows $1011100$ , $1110010$ and $0111001$ (bit positions 1 to 7 left to right). A word $r = 1110011$ is received and it is known that at most one bit is in error. Find the position (1 to 7) of the erroneous bit.

Answer and solution

Answer: $7$

Row 1 uses bits 1, 3, 4, 5: $1 + 1 + 0 + 0 = 0$ .
Row 2 uses bits 1, 2, 3, 6: $1 + 1 + 1 + 1 = 0$ .
Row 3 uses bits 2, 3, 4, 7: $1 + 1 + 0 + 1 = 1$ .
Syndrome $= (0, 0, 1)^{T}$ , which is column 7 of $H$ (column 7 is $(0, 0, 1)^{T}$ ).
The error is in bit position 7.

PRACTICE 42 marks · NAT

A CRC uses the generator polynomial $g (x) = x^{3} + x^{2} + 1$ and the 4-bit message $1001$ . The three CRC bits are appended after the message. Interpreting the three CRC bits as a binary number, what is its decimal value?

Answer and solution

Answer: $3$

$g = 1101$ , $r = 3$ . Append three zeros: $1001000$ .
$1001 \oplus 1101 = 0100$ , bring down 0: $1000 \oplus 1101 = 0101$ , bring down 0: $1010 \oplus 1101 = 0111$ , bring down 0: $1110 \oplus 1101 = 0011$ .
Remainder $= 011$ , which is 3 in decimal.
Check with polynomials: $x^{6} + x^{3} mod (x^{3} + x^{2} + 1) = x + 1$ , i.e. $011$ .

PRACTICE 51 mark · MCQ

A CRC uses $g (x) = x^{4} + x^{3} + x + 1$ , which factors as $(x + 1) (x^{3} + 1)$ . The codewords are 15 bits long. Which one of the following error types is guaranteed to be detected?

(A)
Every error pattern with an odd number of flipped bits.
(B)
Every error pattern with exactly two flipped bits.
(C)
Every burst error of length 5.
(D)
Every error pattern whatsoever.

Answer and solution

Answer: (A)

$g (x)$ has the factor $(x + 1)$ , so $g (x)$ divides $E (x)$ only if $E (1) = 0$ , which means an even number of terms. Hence every odd-weight error is detected: A is true.
B: $g (x) = (x + 1)^{2} (x^{2} + x + 1)$ divides $x^{6} + 1 = (x^{3} + 1)^{2}$ , so two flipped bits 6 positions apart (for example bits 1 and 7, which fit in a 15-bit codeword) are missed. B is false.
C: a burst of length 5 can equal $g (x)$ itself (pattern $11011$ ), which is divisible by $g$ and missed. C is false.
D is false because of B and C.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE EC

Fundamentals of error correction, Hamming codes, CRC

Preparing in Kolkata? IAE Academy's course for GATE ECE.