Error Detection and Correction

During transmission, physical electromagnetic signals are vulnerable to interference, noise, and attenuation. These impairments can change the logical values of bits, leading to data corruption that must be systematically managed.

1. Fundamentals of Error Control and Redundancy

In physical transmission media, thermal noise, transient electromagnetic interference, and signal attenuation can alter the state of transmitted bits. Error control represents a suite of protocols and mathematical techniques designed to preserve data integrity across unreliable channels.

Types of Errors

Errors are classified into two primary categories based on the distribution and alignment of corrupted bits:

Single-Bit Errors: A single-bit error is a state where only $1\text{ bit}$ within a given data unit (e.g., a byte or packet) is modified (from $0$ to $1$ or from $1$ to $0$ ).

text

Original Data:  [ 1 ] [ 0 ] [ 1 ] [ 1 ] [ 0 ] [ 1 ] [ 1 ] [ 0 ]
                                 | (Noisy Spike)
                                 v
Corrupted Data: [ 1 ] [ 0 ] [ 1 ] [ 0 ] [ 0 ] [ 1 ] [ 1 ] [ 0 ]
                                  ^ (Only 1 bit altered)

Burst Errors: A burst error occurs when $2\text{ or more bits}$ in the data unit have changed. The length of the burst error ( $L$ ) is measured from the first corrupted bit to the last corrupted bit, inclusive. The intermediate bits within this range may or may not be corrupted.

text

Original:  [ 1 ] [ 0 ] [ 1 ] [ 1 ] [ 0 ] [ 1 ] [ 1 ] [ 0 ] [ 1 ] [ 0 ]
                  |                                     |
                  +---------------+                     | (Electromagnetic Burst)
                                  v                     v
Corrupted: [ 1 ] [ 1 ] [ 1 ] [ 1 ] [ 1 ] [ 1 ] [ 1 ] [ 1 ] [ 1 ] [ 0 ]
                  ^                                     ^
                  |<------------ Burst Length L = 8 ----------->|

The Concept of Redundancy

To detect or correct errors, additional, non-payload bits must be transmitted alongside the raw data. These are referred to as redundant bits. The mapping process is executed by an encoder at the sender site, and the validation/extraction is performed by a decoder at the receiver site.

text

                  Sender Site                             Receiver Site
             +------------------+                    +--------------------+
             |     Dataword     |                    |  Decoded Dataword  |
             +--------+---------+                    +---------^----------+
                      |                                        |
                      v                                        | (If no error
             +--------+---------+                              |  or corrected)
             |     Encoder      |                              |
             +--------+---------+                    +---------+----------+
                      |                                        |
                      v (Codeword)                             | (Syndrome
             +--------+---------+                              |  Calculation)
             |   Transmitter    |                    +---------+----------+
             +--------+---------+                    |     Decoder      |
                      |                               +---------^----------+
                      |                                        |
                      v                                        |
             ~~~~~~~~~~~~~~~~~ Noisy Physical Link ~~~~~~~~~~~~~
                      |                                        |
                      +----------------------------------------+ (Received Codeword)

Block Coding

In block coding, the continuous bitstream is partitioned into blocks of $k$ bits, designated as datawords. The encoder appends $r$ redundant bits to each dataword, producing an $n$ -bit block called a codeword, where:

$n = k + r$

The total number of possible datawords is $2^k$ . The total number of possible codewords is $2^n$ . Because $n > k$ , only $2^k$ of the possible codewords are codewords. The remaining bit patterns represent codewords.

If a receiver receives an invalid codeword, it immediately knows an error occurred. If the corrupted codeword maps to a different, valid codeword, the error remains undetected.

2. Hamming Distance and Detection/Correction Boundaries

The robust mathematical foundation of block coding rests upon the metric of distance between distinct binary sequences.

Hamming Distance Definition

The Hamming distance $d(x, y)$ between two binary words $x$ and $y$ of equal length is defined as the number of positions at which the corresponding bits differ. Mathematically, this is equivalent to the number of $1$ s (Hamming weight) in the bitwise exclusive-OR ( $\text{XOR}$ ) of the two words:

$d(x, y) = \text{weight}(x \oplus y)$

For example, to find the Hamming distance between $x = 10101$ and $y = 11110$ :

$x \oplus y = 10101 \oplus 11110 = 01011$

The number of $1$ s in $01011$ is $3$ , meaning $d(10101, 11110) = 3$ .

Minimum Hamming Distance ( $d_{\min}$ )

The minimum Hamming distance ( $d_{\min}$ ) of a block code is the smallest Hamming distance between all possible pairs of valid codewords in the code set:

$d_{\min} = \min \{ d(C_i, C_j) \mid C_i \ne C_j \}$

where $C_i$ and $C_j$ are valid codewords in the code.

Error Detection Guarantees

To guarantee the detection of up to $s$ errors in any transmission, the minimum Hamming distance of the code must satisfy:

$d_{\min} \ge s + 1$

Proof Sketch (Geometric Concept)

If the minimum distance between any two valid codewords is $s+1$ , changing up to $s$ bits in a valid codeword $C_1$ will yield an invalid codeword $C'$ . It is geometrically impossible for errors to shift far enough to reach another valid codeword , since the closest valid codeword is at least steps away. Thus, the invalid codeword will fall in the "empty space" between valid codewords and will be detected by the decoder.

text

    [ Valid Codeword C_1 ] <------- Distance d_min >= s + 1 -------> [ Valid Codeword C_2 ]
              |
              | (s bit errors occur)
              v
       [ Received Word C' ] (Guaranteed to be Invalid)

Error Correction Guarantees

To guarantee the correction of up to $t$ errors in any transmission, the minimum Hamming distance of the code must satisfy:

$d_{\min} \ge 2t + 1$

Geometric Concept

If we construct a "sphere of correction" with a radius of $t$ around each valid codeword, any received word containing up to $t$ errors will fall uniquely within the sphere of its original codeword. To prevent these spheres of radius $t$ from overlapping, the distance between any two valid codewords (the centers of the spheres) must be strictly greater than the sum of their radii:

$d_{\min} \ge t + t + 1 = 2t + 1$

If $d_{\min}$ were less than $2t + 1$ , a word with $t$ errors could fall within the overlapping region of two spheres, making unique correction impossible.

text

           Sphere of Radius t                       Sphere of Radius t
      /-------------------------\              /-------------------------\
     /                           \            /                           \
    |     * Valid Codeword C_1    |          |     * Valid Codeword C_2    |
    |            \                |          |                            |
     \            \ t errors     /            \                          /
      \------------v------------/              \------------------------/
              Received Word C'

3. Linear Block Codes

A block code is classified as a linear block code if and only if the exclusive OR (addition modulo-2) of any two valid codewords in the code yields another valid codeword.

Mathematical Properties

Let $\mathcal{C}$ be a linear block code. Then:

$\forall C_1, C_2 \in \mathcal{C}, \quad C_1 \oplus C_2 \in \mathcal{C}$

A critical consequence of this linearity is that the minimum Hamming distance of a linear block code is equal to the minimum Hamming weight (the number of non-zero bits) among all non-zero codewords:

$d_{\min} = \min \{ \text{weight}(C_i) \mid C_i \in \mathcal{C}, C_i \ne \mathbf{0} \}$

The Simple Parity-Check Code

The simplest linear block code is the simple parity-check code $C(k+1, k)$ , which appends a single redundant bit ( $r=1$ ) to a $k$ -bit dataword.

Even Parity Scheme: The redundant bit is chosen such that the total number of $1$ s in the codeword is even.
Modulo-2 Implementation: The parity bit $p_0$ is computed as:

$p_0 = d_{k-1} \oplus d_{k-2} \oplus \dots \oplus d_0$

The syndrome $S$ computed at the receiver is:

$S = c_{k} \oplus c_{k-1} \oplus \dots \oplus c_0$

If $S = 0$ , the transmission is assumed to be error-free. If $S = 1$ , an odd number of errors has occurred.

$d_{\min} = 2 \implies \text{detects } s = d_{\min}-1 = 1 \text{ error.}$

Hamming Codes

Hamming codes are a highly structured class of linear block codes designed with a minimum Hamming distance $d_{\min} = 3$ . This allows them to guarantee the correction of any single-bit error ( $t=1$ ) or the detection of up to double-bit errors ( $s=2$ ).

The structural parameters of Hamming codes are governed by the number of parity bits $m$ :

Codeword length: $n = 2^m - 1$
Dataword length: $k = 2^m - 1 - m$
Redundant/Parity bits:

The Hamming $C(7, 4)$ Code

Let us analyze the standard $C(7,4)$ code where $m=3$ . Here, $n=7$ and $k=4$ . The bits of the codeword are labeled from left to right as $c_{6}, c_{5},$ (corresponding to positions ).

The redundant bits $p_0, p_1, p_2$ are placed at positions that are powers of two:

$c_0$ (position 1) $\rightarrow p_0$
$c_1$ (position 2)

The data bits $d_0, d_1, d_2, d_3$ are mapped to the remaining positions:

$c_2$ (position 3) $\rightarrow d_0$
$c_4$ (position 5)

The parity generator equations (using even parity) are:

$p_0 = d_0 \oplus d_1 \oplus d_3$

$p_1 = d_0 \oplus d_2 \oplus d_3$

$p_2 = d_1 \oplus d_2 \oplus d_3$

Syndrome Analysis in $C(7,4)$

At the receiver, the decoder calculates a 3-bit syndrome $\mathbf{S} = [s_2, s_1, s_0]$ using the received bits $r_i$ :

$s_0 = r_0 \oplus r_2 \oplus r_4 \oplus r_6 \quad (\text{Check positions } 1, 3, 5, 7)$

$s_1 = r_1 \oplus r_2 \oplus r_5 \oplus r_6 \quad (\text{Check positions } 2, 3, 6, 7)$

$s_2 = r_3 \oplus r_4 \oplus r_5 \oplus r_6 \quad (\text{Check positions } 4, 5, 6, 7)$

If $\mathbf{S} = [0, 0, 0]$ , no single-bit error is present. If $\mathbf{S} \ne \mathbf{0}$ , the binary value of the syndrome directly indicates the decimal index of the corrupted bit position (1 to 7).

| Syndrome $[s_2, s_1, s_0]$ | Corrupted Position | Error Type | | :---: | :---: | :---: | | $000$ | None | No Error | | $001$ | 1 | Parity bit | | | 2 | Parity bit | | | 3 | Data bit | | | 4 | Parity bit | | | 5 | Data bit | | | 6 | Data bit | | | 7 | Data bit |

4. Cyclic Codes (Cyclic Redundancy Check - CRC)

Cyclic codes are a specialized category of linear block codes that possess an additional structural property: if a codeword is cyclically shifted (rotated), the resulting sequence is also a valid codeword.

Polynomial Representation of Binary Sequences

In cyclic code analysis, binary bit patterns are represented as polynomials in a single dummy variable $x$ . The powers of $x$ correspond to the positional indices of the bits, and the coefficients ( $0$ or $1$ ) represent the bit values.

For example, the binary sequence $1001101$ contains $7$ bits. It is represented as:

$f(x) = 1\cdot x^6 + 0\cdot x^5 + 0\cdot x^4 + 1\cdot x^3 + 1\cdot x^2 + 0\cdot x^1 + 1\cdot x^0$

$f(x) = x^6 + x^3 + x^2 + 1$

All mathematical operations on these polynomials are executed using modulo-2 arithmetic:

Addition and subtraction are identical to bitwise $\text{XOR}$ :

$(x^2 + x + 1) + (x + 1) = x^2 + (1 \oplus 1)x + (1 \oplus 1) = x^2$

The CRC Encoder and Decoder

The most common application of cyclic codes is the Cyclic Redundancy Check (CRC).

Let the $k$ -bit dataword be represented by the polynomial $d(x)$ .
Let the generator polynomial of degree $r$ be represented by $g(x)$ .
The dataword is shifted left by $r$ bits, which mathematically equates to multiplying $d(x)$ by .

$\frac{d(x) \cdot x^r}{g(x)} = q(x) + \frac{s(x)}{g(x)}$

where $q(x)$ is the quotient and $s(x)$ is the remainder of degree less than $r$ . 5. The remainder $s(x)$ represents the cyclic redundant bits. The transmitted codeword polynomial $c(x)$ is constructed as:

$c(x) = d(x) \cdot x^r \oplus s(x)$

Because $c(x)$ is constructed by subtracting (or $\text{XOR}$ ing) the remainder from the dividend, $c(x)$ is guaranteed to be perfectly divisible by $g(x)$ without remainder.

text

                                Sender CRC Encoder Division
                                      1101   (Quotient q(x))
                             ----------------
     Generator g(x) -> 1011 | 1001000        (Dataword appended with r = 3 zeros)
     (x^3 + x + 1)            1011
                             ----
                              0100
                              0000
                              ----
                               1000
                               1011
                               ----
                                0110
                                0000
                                ----
                                 110  (Remainder s(x) = 3 redundant bits)

The computed remainder $110$ is appended to the dataword $1001$ , yielding the transmitted codeword: $1001110$ .

Receiver Validation

The receiver gets a sequence represented by the polynomial $r(x)$ . The validation process involves dividing $r(x)$ by the known generator polynomial $g(x)$ :

$\frac{r(x)}{g(x)} = q'(x) + \frac{S(x)}{g(x)}$

The remainder polynomial $S(x)$ is the syndrome.

If $S(x) = 0$ : No errors are detected; the dataword is extracted by stripping the last $r$ bits.
If $S(x) \ne 0$ : One or more bits have been corrupted during transmission; the frame is discarded.

Error Analysis of Cyclic Codes

An error pattern can be represented as an error polynomial $e(x)$ , such that:

$r(x) = c(x) \oplus e(x)$

The syndrome division yields:

$\frac{r(x)}{g(x)} = \frac{c(x) \oplus e(x)}{g(x)} = \frac{c(x)}{g(x)} \oplus \frac{e(x)}{g(x)}$

Since $c(x)$ is perfectly divisible by $g(x)$ , the syndrome is determined entirely by the error polynomial:

$\text{Remainder}\left[\frac{r(x)}{g(x)}\right] = \text{Remainder}\left[\frac{e(x)}{g(x)}\right]$

An error goes undetected if and only if $e(x)$ is perfectly divisible by $g(x)$ . This mathematical property allows us to design generator polynomials with highly specific detection capabilities:

Single-Bit Errors: A single-bit error is represented by $e(x) = x^i$ . If the generator polynomial $g(x)$ contains more than one term and the coefficient of $x^0$ is $1$ , it can never divide . Thus, .

5. Checksum

The checksum is a low-overhead, software-friendly error detection method primarily employed at the network and transport layers of the TCP/IP suite (e.g., in IPv4, UDP, and TCP headers), rather than at the hardware-centric data link layer.

One's Complement Arithmetic

In $m$ -bit one's complement arithmetic:

Unsigned values are kept within the range $[0, 2^m - 1]$ .
When adding two numbers, any carry-out from the most significant bit ( $2^m$ position) cannot be ignored. It must be wrapped around and added to the least significant bit. This is known as the end-around carry.

Addition Example ( $m=4$ )

Let us add $11$ ( $1011_2$ ) and $12$ ( $1100_2$ ) in a 4-bit one's complement system:

$1011_2 + 1100_2 = 10111_2 \quad (\text{a 5-bit result})$

Wrap the leftmost carry bit ( $1$ ) to the least significant position:

$0111_2 + 1_2 = 1000_2 \quad (\text{decimal } 8)$

Alternatively, subtracting $15$ ( $2^4 - 1$ ) from the normal sum ( $23 - 15 = 8$ ) yields the same result.

The negative of a number in one's complement is found by bitwise inversion (notting every bit):

$-x = \sim x = (2^m - 1) - x$

The Internet Checksum Algorithm

The sender and receiver apply a structured process to calculate and verify the checksum.

text

                        Sender Site                            Receiver Site
            +---------------------------------+    +---------------------------------+
            |  Split data into k-bit words    |    |  Split data into k-bit words    |
            |   (checksum field set to 0)     |    |    (includes received checksum) |
            +----------------+----------------+    +----------------+----------------+
                             |                                      |
                             v                                      v
            +---------------------------------+    +---------------------------------+
            | Add all words using 1's comp.   |    | Add all words using 1's comp.   |
            +----------------+----------------+    +----------------+----------------+
                             |                                      |
                             v                                      v
            +---------------------------------+    +---------------------------------+
            |  Complement the resulting sum   |    |  Complement the resulting sum   |
            |     (This is the Checksum)      |    |       (The Syndrome value)      |
            +----------------+----------------+    +----------------+----------------+
                             |                                      |
                             v                                      v
            +---------------------------------+    +---------------------------------+
            | Transmit packet with checksum   |    | If 0: Accept data               |
            +---------------------------------+    | Else: Discard packet            |
                                                   +---------------------------------+

Complete Mathematical Tracing

Suppose our payload data consists of four 8-bit blocks ( $m=8$ ): 0xF0, 0x34, 0x12, and 0xAB.

Sender Calculation

Sum the values using one's complement addition:

$\text{Word}_1: \quad 1111\ 0000_2 \quad (0\text{xF0})$

$\text{Word}_2: \quad 0011\ 0100_2 \quad (0\text{x34})$

$\text{Partial Sum 1}: \quad 1111\ 0000_2 + 0011\ 0100_2 = 1\ 0010\ 0100_2$

Apply end-around carry:

$\text{Partial Sum 1} = 0010\ 0100_2 + 1_2 = 0010\ 0101_2 \quad (0\text{x25})$

Add $\text{Word}_3$ :

$\text{Partial Sum 1}: \quad 0010\ 0105_2 \quad (0\text{x25})$

$\text{Word}_3: \quad 0001\ 0010_2 \quad (0\text{x12})$

$\text{Partial Sum 2}: \quad 0010\ 0101_2 + 0001\ 0010_2 = 0011\ 0111_2 \quad (0\text{x37})$

Add $\text{Word}_4$ :

$\text{Partial Sum 2}: \quad 0011\ 0111_2 \quad (0\text{x37})$

$\text{Word}_4: \quad 1010\ 1011_2 \quad (0\text{xAB})$

$\text{Raw Sum}: \quad 0011\ 0111_2 + 1010\ 1011_2 = 1110\ 0010_2 \quad (0\text{xE2, no carry})$

The final one's complement sum is 1110 0010. 2. Invert the sum to compute the checksum:

$\text{Checksum} = \sim(1110\ 0010_2) = 0001\ 1101_2 \quad (0\text{x1D})$

The sender transmits the data words along with the checksum 0x1D.

Receiver Verification

The receiver sums all five received bytes (0xF0, 0x34, 0x12, 0xAB, and the checksum 0x1D):

$\text{Data Sum}: \quad 1110\ 0010_2 \quad (0\text{xE2})$

$\text{Checksum}: \quad 0001\ 1101_2 \quad (0\text{x1D})$

$\text{Total Sum}: \quad 1110\ 0010_2 + 0001\ 1101_2 = 1111\ 1111_2 \quad (0\text{xFF})$

Complement the total sum to find the syndrome:

$\text{Syndrome} = \sim(1111\ 1111_2) = 0000\ 0000_2 \quad (0\text{x00})$

Since the syndrome is 0x00, the receiver confirms that no errors were detected and accepts the packet.

Summary

Error Classifications: Single-bit errors affect one bit; burst errors span across multiple bits. Redundant bits must be sent alongside payload data to enable detection and correction.
Hamming Distance Boundaries:
- To detect $s$ errors: $d_{\min} \ge s + 1$ .
- To correct $t$ errors: $d_{\min} \ge 2t + 1$ .

Assessed progress

Error Detection and Correction

Key Concepts

Single-Bit vs. Burst Errors

Hamming Distance & Minimum Distance

Linear Block Codes

Cyclic Redundancy Check (CRC)

One's Complement Checksum

Quick Check

Computer Networks

Computer Networks