Tutorial 6.2: Error Detection and Error Correction Techniques

(b) It can only detect an odd number of bit errors. Single-bit parity cannot detect errors where an even number of bits are flipped.

(c) It can correct single-bit errors. Two-dimensional parity allows the receiver to identify the exact row and column where a single-bit error occurred, enabling correction.

(b) A polynomial agreed upon by sender and receiver used for division. The generator polynomial G is agreed upon; the sender appends CRC bits so that the resulting polynomial is divisible by G.

(a) r bits. A CRC with generator polynomial of degree r can detect all burst errors of length ≤ r bits.

(d) CRC-32. Ethernet uses a 32-bit Cyclic Redundancy Check (CRC-32) for error detection.

(c) Signals for retransmission or drops the frame. Depending on the protocol, the receiver may request retransmission or simply discard the corrupted frame.

(c) To correct d errors, Hamming distance must be ≥ 2d + 1. This ensures that the erroneous codeword is closer to the original than to any other codeword.

(b) Some error patterns can produce the same EDC as the correct data. Certain error patterns may transform the data plus EDC into another valid codeword, leading to undetected errors.

(b) Transport-layer error detection in TCP and UDP. The Internet checksum is used at the transport layer (and network layer) for error detection, not typically at the link layer.

(b) 2^(-r). A CRC with r bits will miss a longer burst error with probability approximately 2^(-r) because there are 2^r possible remainders.

(b) 3. Hamming(7,4) has 3 parity bits and 4 data bits, totaling 7 bits.

(b) 4. To detect d errors, minimum distance must be at least d+1, so for d=3, distance ≥ 4.

(b) It detects all single-bit and two-bit errors. CRC-32 with a properly chosen polynomial can detect all single-bit and two-bit errors, and all burst errors up to 32 bits.

(b) Selective Repeat retransmits only lost frames, Go-Back-N retransmits all frames from the lost one onward. This is the key efficiency difference.

(b) To detect all odd numbers of errors. A polynomial with factor (x+1) has the property that any error polynomial with an odd number of terms is not divisible by G, thus odd errors are detected.

(a) To detect errors in the TCP segment. The TCP checksum covers the header and data to detect corruption.

(b) It is the CRC for error detection. The FCS (Frame Check Sequence) is a 32-bit CRC that allows the receiver to detect errors.

(a) m + n. One parity bit per row and one per column, so m + n parity bits are added.

(b) To avoid retransmission due to long propagation delay. Satellite links have high latency, so retransmission is costly; FEC allows errors to be corrected immediately.

(c) CRC using LFSR. CRC can be implemented efficiently in hardware using a Linear Feedback Shift Register, making it suitable for high-speed links.

(b) It may increase the probability of undetected errors. A non-primitive polynomial may have weaker detection properties for certain error patterns.

(d) Both (b) and (c) are correct. CRC-32 adds 32 bits (4 bytes) of overhead, which is about 0.2% of 1500 bytes.

(c) 7. The error position is the sum of the parity bit positions that indicate an error: 1+2+4 = 7.

(c) Higher overhead and complexity. Error correction codes require more redundant bits and more complex encoding/decoding, but they eliminate the need for retransmission.

(c) All odd-numbered errors. Single-bit parity detects any odd number of bit errors; it misses even-numbered errors.

1. 1011010 has four 1s (even) → parity bit = 0.
2. 1100111 has five 1s (odd) → parity bit = 1 (to make even).
3. 0001111 has four 1s (even) → parity bit = 0.
4. 11110000 has four 1s (even) → parity bit = 0.

Step 1: Append 3 zeros: 101001000

Step 2: Modulo-2 division:

         110101
        --------
1101 ) 101001000
        1101
        ----
         1110
         1101
         ----
           110
           000
           ---
            1100
            1101
            ----
               100
        

Remainder = 100 (3 bits).

Transmitted frame = 101001 100.

Verification: 101001100 divided by 1101 yields remainder 0.

Row parities:

• Row 1: 1+0+1+0 = 2 (even) → 0
• Row 2: 0+1+1+1 = 3 (odd) → 1
• Row 3: 1+1+0+0 = 2 (even) → 0
• Row 4: 0+0+1+1 = 2 (even) → 0

Column parities:

• Col 1: 1+0+1+0 = 2 (even) → 0
• Col 2: 0+1+1+0 = 2 (even) → 0
• Col 3: 1+1+0+1 = 3 (odd) → 1
• Col 4: 0+1+0+1 = 2 (even) → 0

Complete matrix:

1 0 1 0 | 0
0 1 1 1 | 1
1 1 0 0 | 0
0 0 1 1 | 0
---------
0 0 1 0 | 1 (overall parity)
        

Step 1: Sum (one's complement addition):

10011001 + 01010101 = 11101110

11101110 + 00110011 = 100100001 → wrap carry: 00100001 + 00000001 = 00100010

Step 2: One's complement: ~00100010 = 11011101

Checksum = 11011101.

Verification: receiver sums all words + checksum: 10011001+01010101+00110011+11011101 = 11111111 (all ones) → error-free.

Divide 101001101 by 1011:

         100101
        --------
1011 ) 101001101
        1011
        ----
         0001
         0000
         ----
           0010
           0000
           ----
             0101
             0000
             ----
               1011
               1011
               ----
                  0
        

Remainder = 0 → no error detected (frame accepted as error-free).

Data bits: d1=1, d2=0, d3=1, d4=1 (positions 3,5,6,7).

• p1 (pos 1) = d1 ⊕ d2 ⊕ d4 = 1⊕0⊕1 = 0
• p2 (pos 2) = d1 ⊕ d3 ⊕ d4 = 1⊕1⊕1 = 1
• p3 (pos 4) = d2 ⊕ d3 ⊕ d4 = 0⊕1⊕1 = 0

Codeword = p1 p2 d1 p3 d2 d3 d4 = 0 1 1 0 0 1 1 → 0110011.

Received: 0 1 1 0 0 1 0 (positions 1..7).

• p1 (pos1) = 0, check group: positions 1,3,5,7 = 0,1,0,0 → XOR = 1 → error in group1.
• p2 (pos2) = 1, check group: positions 2,3,6,7 = 1,1,1,0 → XOR = 1 → error in group2.
• p3 (pos4) = 0, check group: positions 4,5,6,7 = 0,0,1,0 → XOR = 1 → error in group3.

Error position = 1+2+4 = 7. Flip bit 7: 0 becomes 1 → corrected codeword = 0110011.

G(x)=x+1 (i.e., 11 in binary) has degree 1, so it can only generate a 1-bit CRC. It detects all odd numbers of errors but cannot detect any even number of errors. Moreover, it cannot detect burst errors of length >1. For modern links, we need robust detection of multi-bit and burst errors, hence higher-degree polynomials like CRC-16 or CRC-32 are used.

Frame size = 1000 + 4 = 1004 bytes = 8032 bits.

Transmission time = 8032 / 1e6 = 0.008032 s = 8.032 ms.

RTT = 50 ms. Utilization U = T_frame / (T_frame + RTT) = 8.032 / (8.032 + 50) ≈ 0.1384.

Effective throughput = U × data rate = 0.1384 × 1 Mbps = 138.4 kbps.

Note: This is the throughput of the link layer; the actual useful data throughput would be lower due to retransmissions if errors occur.

For G=1011 (degree 3), the LFSR has 3 shift registers (flip-flops) for the remainder. The polynomial is x^3 + x + 1 (since 1011 corresponds to coefficients for x^3, x^2, x^1, x^0: 1,0,1,1). The feedback taps are at positions 0 (x^0) and 1 (x^1) (and also the x^3 term which is the feedback from the last register). The LFSR uses XOR gates at the feedback path. Specifically, the input to the first register is the XOR of the incoming data bit and the feedback from the last register, and the feedback also XORed with the taps. The number of XOR gates is equal to the number of nonzero terms in the polynomial minus 1 (for degree>0). Here we have three nonzero terms (x^3, x, 1) so two XOR gates are needed.

Probability ≈ 2^(-16) = 1 / 65536 ≈ 0.00001526, which is about 0.001526%.

Frame size in bits = 1000*8 = 8000 bits.

Probability of no error = (1 - BER)^8000 ≈ (0.99999)^8000 ≈ exp(-0.08) ≈ 0.9231.

Probability that a frame is corrupted = 1 - 0.9231 = 0.0769.

With CRC-32, the probability of undetected error = P(corrupted) × 2^-32 ≈ 0.0769 × 2.33e-10 ≈ 1.79e-11. Very small.

If we have two words A and B such that B = ~A (bitwise NOT). For example, A = 0xFFFF, B = 0x0000. The sum A + B = 0xFFFF, which has ones complement 0x0000. The checksum for both would be 0x0000? Actually, the checksum is the ones complement of the sum. For a single word, the checksum is ~A. If we send A and checksum ~A, the receiver sums A + ~A = 0xFFFF, which is correct. However, if two words are complements, they cancel, and the checksum may be the same as for other combinations. For example, with words A and B, the sum A+B could be the same as C+D, so errors could be undetected.

Any error pattern with an odd number of errors is guaranteed to be detected because (x+1) divides E(x) only if E(1)=0, which means the number of terms in E(x) is even. Thus, odd number of errors yields E(1)=1, so not divisible by (x+1), hence detected.

The minimum Hamming distance of Hamming(7,4) is 3. Therefore, it can detect up to 2 errors (d-1 = 2) and correct 1 error (floor((d-1)/2) = 1).

Similarities: Both are error-detection techniques that add redundant information.

Differences:

Preferred scenarios: CRC is preferred when high reliability is required and hardware is available. Checksum is preferred in software-based protocols where simplicity and speed are more important than ultimate detection power.

Division steps:

         1100001010
        ------------
10011 ) 11010110110000
         10011
         -----
          10011
          10011
          -----
             10110
             10011
             -----
              10100
              10011
              -----
               1110
        

Remainder = 1110. Transmitted = 1101011011 1110.

Verification: Divide 11010110111110 by 10011 → remainder 0.

If received is 1101011011 1111 (last bit flipped), divide 11010110111111 by 10011. We can compute remainder: (previous remainder 1110) XOR (error pattern 0001) modulo G? Actually, the error pattern E=0001 at the end. The remainder would be E mod G = 0001 mod 10011 = 0001 (since degree <4). So remainder=0001, indicating error detected.

The probability is 2^(-r) because there are 2^r possible remainders when dividing by G (degree r). For a random error pattern, all remainders are equally likely. The error is undetected iff the remainder is 0, which occurs with probability 1/2^r.

Assumptions: The error pattern is random and uniformly distributed over all possible error patterns. Also assumes the data length is large enough.

In practice: For a well-chosen generator polynomial (e.g., primitive polynomials), the actual probability may be even lower than 2^(-r) for many common error patterns. However, the theoretical upper bound is 2^(-r), and it is a good approximation for random errors.

Hamming(7,4) code:

• Data bits: d1,d2,d3,d4 (positions 3,5,6,7).
• Parity bits:
  • p1 = d1 ⊕ d2 ⊕ d4
  • p2 = d1 ⊕ d3 ⊕ d4
  • p3 = d2 ⊕ d3 ⊕ d4
• Codeword: p1 p2 d1 p3 d2 d3 d4.

Encoding example: data = 1011 → d1=1,d2=0,d3=1,d4=1 → p1=1⊕0⊕1=0, p2=1⊕1⊕1=1, p3=0⊕1⊕1=0 → codeword = 0110011.

Decoding: Compute syndromes: s1 = p1 ⊕ d1 ⊕ d2 ⊕ d4, s2 = p2 ⊕ d1 ⊕ d3 ⊕ d4, s3 = p3 ⊕ d2 ⊕ d3 ⊕ d4. If all zero, no error. Otherwise, error position = s1 + 2*s2 + 4*s3 (1-indexed). Correct the bit.

Example with error: Received 0110010 (bit 7 flipped). Compute: s1 = 0⊕1⊕0⊕1=0? Wait, recalc: p1=0, d1=1,d2=0,d4=1 → s1=0⊕1⊕0⊕1=0; s2=1⊕1⊕1⊕1=0? Actually 1⊕1=0, 0⊕1=1, 1⊕1=0 → s2=0; s3=0⊕0⊕1⊕1=0? 0⊕0=0, 0⊕1=1, 1⊕1=0 → s3=0. That would indicate no error, but there is an error? Let's recalc carefully. Received: positions: 1:p1=0, 2:p2=1, 3:d1=1, 4:p3=0, 5:d2=0, 6:d3=1, 7:d4=0 (since error). s1 = p1 ⊕ d1 ⊕ d2 ⊕ d4 = 0⊕1⊕0⊕0 = 1. s2 = p2 ⊕ d1 ⊕ d3 ⊕ d4 = 1⊕1⊕1⊕0 = 1 (since 1⊕1=0, 0⊕1=1, 1⊕0=1). s3 = p3 ⊕ d2 ⊕ d3 ⊕ d4 = 0⊕0⊕1⊕0 = 1. So error position = 1+2+4 = 7, correct bit 7 to 1 → original.

CRC-32 polynomial (standard Ethernet, FDDI, PNG, ZIP, etc.):

G(x) = x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1

Hexadecimal representation: 0x04C11DB7 (with reversed bit order for some implementations).

Why chosen:

• It is a primitive polynomial, ensuring good error detection properties.
• It has factor (x+1), so it detects all odd numbers of errors.
• It has a high degree (32) to detect burst errors up to 32 bits.
• It is extensively tested and standardized, with known performance.
• Efficient hardware implementation (LFSR).

Properties: detects all single-bit, two-bit, odd-numbered errors, and burst errors up to 32 bits. Probability of undetected error for longer bursts is about 2^-32.

Frame size = 1500 + 2 = 1502 bytes = 12016 bits.

Probability that a frame has at least one bit error = 1 - (1 - 10^-6)^12016 ≈ 1 - exp(-0.012016) ≈ 0.01194.

Probability of undetected error = P(frame has error) × 2^-16 ≈ 0.01194 × 1.5259e-5 ≈ 1.82e-7.

So about 1 in 5.5 million frames would have an undetected error.

The Hamming distance between two codewords is the number of positions in which they differ. The minimum Hamming distance of a code is the smallest distance between any two distinct codewords.

If the minimum distance is d, then:

• To detect up to t errors, we need d ≥ t+1.
• To correct up to t errors, we need d ≥ 2t+1.

Example: A code with distance 2 can detect single-bit errors (t=1, d≥2) but cannot correct them. A simple parity check code has distance 2.

An LFSR consists of a shift register with feedback taps that are XORed with the input. For CRC, the shift register holds the current remainder. The data bits are shifted in one by one. At each step, the leftmost bit (MSB) is XORed with the incoming data bit, and the result determines the feedback. The shift register is updated.

For G(x) = x^3 + x + 1 (binary 1011), the LFSR has 3 registers (r2, r1, r0). The feedback is the XOR of the input bit, the current r0 (x^0 tap), and the current r1 (x^1 tap). The new r2 = feedback, new r1 = old r2, new r0 = old r1. The XOR gates are at the taps.

Diagram: [r2] ← [r1] ← [r0] ← (input ⊕ r0 ⊕ r1) and shift.

Code rate = k/n, where k is data bits and n is total bits (data + parity). A lower code rate means more redundancy, which provides stronger error correction but reduces throughput. For example, a rate 1/2 convolutional code can correct more errors than a rate 3/4 code.

Lower code rate is preferable in environments with very high error rates or when retransmission is expensive, such as deep-space communication, satellite links, or underwater acoustic channels. In such cases, the extra redundancy is justified to avoid retransmission.

For a low-speed link with rare errors, CRC-16 might be sufficient because the probability of undetected error is already very low, and the overhead (2 bytes) is smaller than CRC-32 (4 bytes). This saves bandwidth. For a high-speed link, especially if the frame error rate is higher, CRC-32 provides better protection with minimal relative overhead (e.g., 4 bytes vs 1500 bytes is 0.27%). In modern networks, CRC-32 is preferred for robustness, and the overhead is negligible.

A burst error is a contiguous sequence of bits in which the first and last bits are in error, and the intervening bits may or may not be in error. CRC is effective because it detects all burst errors of length ≤ r (where r is the degree of the generator polynomial). This is because any burst of length ≤ r can be represented as E(x) = x^i · B(x) where B(x) has degree < r. If G has degree r, it cannot divide such an E(x) unless B(x)=0, which would mean no error. So CRC guarantees detection of these bursts.