Error Detection and Correction

Introduction
Block Coding
Linear Block Codes
Cyclic Codes
Checksum
Hamming Codes



Type of Errors

An electromagnetic signal is subject to interference from heat, magnetism, and other forms of electricity
Single-bit error: 0  1 or 1  0
Burst error: 2 or more bits have changed

Sender site:
1. The message is divided into 16-bit words.
2. The value of the checksum word is set to 0.
3. All words including the checksum are added using one’s complement
addition.
4. The sum is complemented and becomes the checksum.
5. The checksum is sent with the data.


Receiver site:
1. The message (including checksum) is divided into 16-bit words.
2. All words are added using one’s complement addition.
3. The sum is complemented and becomes the new checksum.
4. If the value of checksum is 0, the message is accepted; otherwise, it is
rejected.
Forward Error Correction

Purpose: An FEC (n, m) encoder
Take m-bit original data as input
Add r=n-k check bits to the original data to produce a n-bit codeword
The receiver can fix any error

Hamming Distance

Code: set of codewords
Hamming distance between 2 codewords is the number of bit positions where the 2 codewords differ
HammingDist(10001001, 10110001) = 3
Hamming distance of a code is the minimum Hamming distance between any two codewords in the code
HammingDist({0000000000,0000011111,1111100000,1111111111}) = 5

Interesting Findings

To detect d single-bit errors
Need a distance-(d+1) code
Appling d single-bit errors to a codeword must result in an invalid codeword. (WHY?)
To correct d single-bit errors
Need a distance-(2d+1) code
Given an incorrect codeword, the corresponding correct one must be the codeword closest in Hamming distance (WHY?)

Linear Block Code: Hamming Code

All Hamming codes discussed in our textbook have dmin = 3.
The relationship between k and n in these codes is n = 2k − 1





Single-Bit Error

Only one bit of a given data unit is changed
The least likely type of error in serial transmission
Single-bit error can happen in parallel transmission

Burst Error

Two or more bits in the data unit have changed
Burst error does not necessarily mean that the errors occur in consecutive bits
Most likely to happen in a serial transmission
Number of bits affected depends on the data rate and duration of noise


Single Bit Error vs. Burst Error

Error Detection
Error detection uses the concept of redundancy, which means adding extra bits for detecting errors at the destination.

Redundancy for Error Detection
Parity Check
Modular Arithmetic

In modulo-N arithmetic, we use only the integers in the range 0 to N-1, inclusive.
Adding: 0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0
Subtracting: 0 – 0 = 0 0 – 1 = 1 1 – 0 = 1 1 – 1 = 0
XORing of two single bits or two words

Block Coding

Divide the message into blocks, each of k bits, called datawords.
Add r redundant bits to each block to make the length n = k + r. The resulting n-bit blocks are called codewords
Example: 4B/5B block coding
k = 4 and n = 5.
2k = 16 datawords and 2n = 32 codewords.

Error Detection in Block Coding

Assume the sender encodes the dataword 01 as 011 and sends it to the receiver. Consider the following cases:

1. The receiver receives 011 which is a valid codeword. The receiver extracts the dataword 01 from it.
2. The codeword is corrupted during transmission, and 111 is received. This is not a valid codeword and is discarded.
3. The codeword is corrupted during transmission, and 000 is received. This is a valid codeword. The receiver incorrectly extracts the dataword 00. Two corrupted bits have made the error undetectable.
 An error-detecting code can detect only the types of errors for which it is designed; other types of errors may remain undetected

Linear Block Code: Parity-Check Code

A simple parity-check code is a single-bit error-detecting code in which n = k + 1 with dmin = 2.


Encoder and Decoder for Parity-Check Code

The result of addition over all 5 bits: syndrome

2-d Parity Check
2 Dimensional Parity-Check Code
2 Dimensional Parity-Check Code
Cyclic Code: CRC

Cyclic codes are special linear block codes with one extra property.
Cyclic Redundancy Check (CRC)


Checksum

Tendency is to replace the checksum with a CRC
Not as strong as CRC in error-checking capability
One’s complement arithmetic
We can represent unsigned numbers between 0 and 2n – 1 using only n bits
If the number has more than n bits, the extra leftmost bits need to be added to the n rightmost bits (wrapping)
A negative number can be represented by inverting all bits. It is the same as subtracting the number from 2n – 1

Internet Checksum