Parity rules and 2^r are easy to recall but harder to apply across bit placement, XOR closure and syndrome decoding. Work each item on paper before checking its solution. Nine of the twelve are previous-year questions from GATE, UGC NET, KVS, NVS and TPSC.
Linear Block Codes in 90 Seconds: The Minimum Toolkit
A binary linear code contains the all-zero codeword and is closed under bitwise XOR. In a Hamming (n,k) code, n is the total number of bits, k is the number of message bits and r = n - k is the number of parity bits. A full Hamming code has n = 2^r - 1, so k = 2^r - r - 1.
For Hamming (7,4), positions 1 2 3 4 5 6 7 hold p1 p2 d1 p4 d2 d3 d4. Parity bits occupy powers of two. Even parity makes every covered group contain an even number of ones, odd parity makes it odd, and for a single-bit error, a non-zero syndrome identifies the erroneous codeword position.
Under the single-error model, a four-bit syndrome names a codeword position counted from 1: 0000 means no error, 0011 means position 3 and 1010 means position 10. It is never an index into the message on its own. More worked items on this topic sit in the Linear Block Codes module hub.
Questions 1-3: Code Length and Single-Parity Foundations
Q1
What is the message length 'k' of a Hamming (7,4) code?
(A)
2^r − 1(B)
2^r − r + 1(C)
2^r − r − 1(D)
2^(r+1) − r
Answer: (C). Here n = 7, k = 4 and r = 3. Thus k = n - r = (2^r - 1) - r = 2^r - r - 1, and substitution confirms 8 - 3 - 1 = 4.
Q2
UGC NET 2015
In a binary Hamming Code the number of check digits is r then number of message digits is equal to:
(A)
2^r−1(B)
2^r−r−1(C)
2^r−r+1(D)
2^r+r−1
Answer: (B). The 2^r syndromes cover one no-error state and all n single-bit error positions, giving n = 2^r - 1 for a full Hamming code. Subtracting r check digits gives k = 2^r - r - 1; for r = 3, the check is k = 8 - 3 - 1 = 4.
Q3
Which of the following is the advantage of Single parity check method?
(A) If even number of bits flip during transmission, then receiver can detect by counting the number of 1’s.
(B) Can detect an odd number of bit errors
(C) If even number of bits flip during transmission, then receiver can catch the error.
(D) A simple parity-check code is a multiple-bit error-detecting code
Answer: (B). The even-parity word 10111 has four ones, and one flip makes that count odd. Every odd number of flips is therefore detected, while two flips can leave the count even and are not guaranteed to be detected.
Questions 4-6: Parity Generation and Two-Dimensional Block Parity
Q4
NVS 2019
A parity generator is a ______ logic system that generates the parity bit at the ______ side.
(A) Sequential, receiving
(B) Combinational, transmitting
(C) Sequential, transmitting
(D) Combinational, receiving
Answer: (B). A parity generator computes an extra bit directly from the current data bits, so it is combinational and works at the transmitting side. The receiving side instead uses a parity checker.
Q5
TPSC 2026
BLOCK PARITY is a
(A) 1-bit error detection code
(B) 1-bit error correction code
(C) MULTI-bit error detection code
(D) MULTI-bit error correction code
Answer: (C). Two-dimensional parity adds row and column checks, so many multi-bit patterns still cause mismatches. It neither detects every multi-bit pattern nor provides multi-bit correction.
Q6
GATE 2008
Data transmitted on a link uses the following 2D parity scheme for error detection: Each sequence of 28 bits is arranged in a 4×7 matrix (rows r0 through r3, and columns d7 through d1) and is padded with a column d0 and row r4 of parity bits computed using the Even parity scheme. Each bit of column d0 (respectively, row r4) gives the parity of the corresponding row (respectively, column). These 40 bits are transmitted over the data link. The table shows data received by a receiver and has n corrupted bits. What is the minimum possible value of n?
d7 | d6 | d5 | d4 | d3 | d2 | d1 | d0 | |
r0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
r1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 0 |
r2 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
r3 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
r4 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
(A) 1
(B) 2
(C) 3
(D) 4
Answer: (C). Rows r0-r3 show only r1 with odd parity; columns including r4 show d5, d2 and d0 with odd parity. One flip can repair at most one of the three bad columns, so at least three flips are needed. Flipping (r1,d0), (r4,d5) and (r4,d2) makes every row and column even, proving that the minimum is exactly 3.
The second figure uses different bits but the same signature: one failed data row and three failed columns.
Questions 7-9: Build Hamming (7,4) Codewords
Q7
UGC NET 2022
The representation of 4 bit code 1101 into 7 bit, even parity Hamming code is
(A) (1010101)
(B) (1111001)
(C) (1011101)
(D) (1110000)
Answer: (A). Put 1,1,0,1 at positions 3,5,6,7 to get _ _ 1 _ 1 0 1. Even parity gives p1 = 1, p2 = 0 and p4 = 0, so the completed word is 1010101.
Q8
Let M = 1000 be the message to be transmitted using the Hamming code with odd parity. Which of the following is the valid 7-bit codeword corresponding to the message M?
(A) 0011000
(B) 0110011
(C) 1111011
(D) 1010011
Answer: (A). Insert 1000 at positions 3,5,6,7 to get _ _ 1 _ 0 0 0. The p1 and p2 groups already have one 1, so both parity bits are 0; the p4 group has no ones, so p4 = 1, producing 0011000.
Q9
KVS 2013
The Hamming (7,4) code for 0000 using even parity is
(A) 0000000
(B) 1111111
(C) 2222222
(D) 121212
Answer: (A). All four data bits are 0. Even parity therefore makes every parity bit 0, giving 0000000.
Questions 10-12: Linearity, Unknown Bits and Syndrome Decoding
Q10
GATE 2004
Consider a parity check code with three data bits and four parity check bits. Three of the code words are 0101011, 1001101 and 1110001. Which of the following are also code words? I. 0010111, II. 0110110, III. 1011010, IV. 0111010
(A) I and III
(B) I, II and III
(C) II and IV
(D) I, II, III and IV
Answer: (A). Three data bits give the code dimension three. The supplied codewords are independent, so they form a basis. Their eight XOR combinations are 0000000, 0101011, 1001101, 1110001, 1100110, 1011010, 0111100 and 0010111. Thus I and III are codewords, while II and IV are not.
Q11
GATE 2021
Assume that a 12-bit Hamming codeword holding 8 data bits and 4 check bits is laid out, from position 12 down to position 1, as d8 d7 d6 d5 c8 d4 d3 d2 c4 d1 c2 c1. The data bits and the check bits are:
Data bits | d8 | d7 | d6 | d5 | d4 | d3 | d2 | d1 |
Value | 1 | 1 | 0 | x | 0 | 1 | 0 | 1 |
Check bits | c8 | c4 | c2 | c1 |
Value | y | 0 | 1 | 0 |
Which one of the following choices gives the correct values of x and y?
(A) x is 0 and y is 0
(B) x is 0 and y is 1
(C) x is 1 and y is 0
(D) x is 1 and y is 1
Answer: (A). Map the layout onto positions 1 to 12: 1 = c1, 2 = c2, 3 = d1, 4 = c4, 5 = d2, 6 = d3, 7 = d4, 8 = c8, 9 = d5, 10 = d6, 11 = d7, 12 = d8. The c1 group covers positions 1, 3, 5, 7, 9 and 11, which hold 0, 1, 0, 0, x and 1, so even parity forces x = 0. The c8 group covers positions 8 to 12, which hold y, 0, 0, 1 and 1, so y = 0.
Q12
UGC NET 2015
For the 8 bit word 00111001, the check bits stored with it are 0111. Suppose when the word is read from memory, the check bits are calculated to be 1101. What is the data word that was read from memory?
(A) 10011001
(B) 00011001
(C) 00111000
(D) 11000110
Answer: (B). The syndrome is 0111 XOR 1101 = 1010, which is codeword position 10. With parity positions 1,2,4,8, position 10 is the sixth data bit from the right; flipping that bit changes 00111001 to 00011001.
What the Distractors Are Testing
The wrong answers target four common slips:
confusing total length
n = 2^r - 1with message lengthk = 2^r - r - 1;applying even-parity logic when the question specifies odd parity;
treating a linear code as closed under ordinary addition instead of XOR;
reading syndrome
1010as the tenth bit of the data word instead of codeword position 10, which is the sixth data bit from the right.
Before choosing an answer, write the convention, reserve power-of-two positions, compute parity or XOR, then verify every covered group. For 2D parity, count failed rows and columns directly. For more arithmetic-heavy practice, continue with the Subnetting and IP Addressing MCQs.
Linear Block Codes Scorecard and What to Practise Next
Score the set group by group rather than by total, because each group fails for its own reason:
Code length, Q1 and Q2. A miss here means
n = 2^r - 1andk = 2^r - r - 1are still blurring into each other.Parity construction, Q3, Q4, Q7, Q8 and Q9. A miss here means the even and odd conventions are not yet automatic.
Two-dimensional parity, Q5 and Q6. A miss here means you are estimating rather than counting failed rows and columns.
Linearity and decoding, Q10, Q11 and Q12. A miss here means XOR closure or the syndrome-to-position map needs another pass.
Wait one day, then retry only the questions you missed.
Use GATE Guidance by Sanchit Sir for the full Computer Networks sequence, GATE Test Series, Mocks and Topic-wise Tests for timed practice, or the GATE category for other course routes. Then redo Q6, Q10, Q11 and Q12 on blank paper; together they test parity auditing, XOR closure, unknown-bit recovery and syndrome decoding.
