Error-control questions are mechanical once the conventions are fixed. Most wrong answers come from appending the wrong number of zeros in CRC, forgetting the checksum's end-around carry, or reading a Hamming syndrome in the wrong order.
Run each procedure in a fixed sequence, and keep every intermediate value visible.
Detection, correction, and minimum distance
Single-bit parity, the Internet checksum, and CRC are error-detection schemes. A parity bit is weak because some multi-bit changes preserve parity. A checksum combines fixed-width words using one's-complement arithmetic. CRC treats a bit string as a polynomial and divides it by a generator polynomial using XOR.
A generator of degree r detects every burst error of length at most r, along with other error patterns determined by the chosen polynomial. CRC detects corruption but does not locate and repair the damaged bit.
Hamming code can correct a single-bit error by identifying its position. More generally, a code with minimum Hamming distance d can detect up to d minus 1 errors and correct up to floor((d minus 1) / 2) errors.
For m data bits, choose the smallest number r of parity bits satisfying:
2^r >= m + r + 1
The right side counts m data positions, r parity positions, and one no-error state.
CRC numerical with mod-2 division
Let the message M be 1001 and the generator G be 1011. The generator has degree 3, so r = 3. Append exactly three zeros to the message:
1001 000
Now divide 1001000 by 1011. Mod-2 subtraction is XOR, so there are no borrows or carries.
Align
1011with the leftmost 1. The first four active bits are1001. Compute1001 XOR 1011 = 0010.Continue bringing down bits until the leading 1 starts the next four-bit group,
1000. Compute1000 XOR 1011 = 0011.The remaining significant part is
110. It is only three bits, shorter than the four-bit divisor, so division stops.
The r-bit remainder is 110. Append it to the original message, replacing the three temporary zeros:
Transmitted codeword = 1001 110 = 1001110.
The receiver divides 1001110 by 1011. The first XOR leaves a shifted 1011, and the second XOR is 1011 XOR 1011 = 0000. The final remainder is 000, so this codeword passes the CRC check. A zero remainder means no error was detected, not that an error is mathematically impossible.
Internet checksum with end-around carry
Take two 8-bit words:
10011001
11100010
Their ordinary binary sum is:
10011001 + 11100010 = 1 01111011
The leftmost 1 is a carry beyond the 8-bit word. In one's-complement addition, wrap it around and add it to the low eight bits:
01111011 + 1 = 01111100
Complement every bit to produce the checksum:
Checksum = 10000011
The sender transmits both data words and this checksum. The receiver's data-word sum after end-around carry is still 01111100. Adding the checksum gives:
01111100 + 10000011 = 11111111
An all-ones result means the receiver detected no error. The classic mistake is to discard the carry from 1 01111011; it must return at the right end.
Hamming(7,4): encode and correct
For m = 4 data bits, r = 3 is enough because 2^3 = 8 and m + r + 1 = 4 + 3 + 1 = 8. The seven codeword positions use parity bits at powers of two, positions 1, 2, and 4. Data occupies positions 3, 5, 6, and 7.
Use data 1011 and even parity. Place it in order:
Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
Role | P1 | P2 | D1 | P4 | D2 | D3 | D4 |
Value before parity | ? | ? | 1 | ? | 0 | 1 | 1 |
Now calculate each parity bit.
P1 covers positions 1, 3, 5, 7. The data values are 1, 0, 1, containing two ones. They are already even, so P1 = 0.
P2 covers positions 2, 3, 6, 7. The data values are 1, 1, 1, containing three ones. Set P2 = 1 to make the total even.
P4 covers positions 4, 5, 6, 7. The data values are 0, 1, 1, containing two ones. Set P4 = 0.
The codeword from position 1 through 7 is 0 1 1 0 0 1 1, or 0110011.
Suppose position 5 flips from 0 to 1. The received word is 0110111. Recheck the parity groups, including their parity bits:
C1 over positions 1, 3, 5, 7 sees
0, 1, 1, 1, an odd count, so C1 = 1.C2 over positions 2, 3, 6, 7 sees
1, 1, 1, 1, an even count, so C2 = 0.C4 over positions 4, 5, 6, 7 sees
0, 1, 1, 1, an odd count, so C4 = 1.
Read the syndrome from the highest check bit to the lowest: C4 C2 C1 = 101, which is binary 5. The error is at position 5. Flip it back to recover 0110011 and then read data positions 3, 5, 6, 7 to recover 1011.
The traps GATE plants
For CRC, append r zeros where r is the generator's degree, not r minus 1. Keep the remainder at r bits by preserving leading zeros when needed.
For a checksum, use fixed-width one's-complement addition and add every carry back into the low-order end. For Hamming code, state the parity convention, put parity bits only at positions 1, 2, 4, 8, and so on, and read the syndrome high bit first.
Do not confuse parity-bit count with minimum distance. The inequality 2^r >= m + r + 1 sizes a single-error-correcting Hamming word. Minimum distance separately determines how many errors a code can detect and correct.
How these numericals appear in GATE
Typical questions ask for a CRC remainder, whether a received frame passes, the number of check bits for m data bits, the position named by a syndrome, or the detection and correction capacity from minimum distance. The subnetting arithmetic in Computer Networks Subnetting MCQs builds the same habit of keeping bit positions explicit, while Computer Networks Transport Layer MCQs extends practice across the syllabus.
For the current Computer Networks scope, confirm the syllabus on the official GATE portal of the organising IIT.
A 30-second recap
CRC: append r zeros, XOR-divide by G, and send the message followed by the remainder. The receiver accepts when its remainder is zero.
Checksum: add using one's-complement arithmetic with end-around carry, send the complement, and expect all ones at the receiver.
Hamming: place parity at power-of-two positions. Recomputed check bits form a binary syndrome whose value is the faulty position.
The short version and next step
Write those three procedures before doing any arithmetic. They prevent the convention slips that create most wrong answers.
Drill error-control numericals in the GATE Test Series, and build their data-link context with GATE Guidance by Sanchit Sir. Use the GATE preparation category to continue through the subject.
