CH3 Error Detection and Correction Lec1-2
Concise Version
Hamming Code
Hamming Distance
Definition: Minimum number of bit flips to change one valid code word into another valid code word.
Significance: Indicates how many errors can occur before the original information is unrecoverable.
Example:
10-bit code words.
n = 2 (values of 0 or 1).
Hamming distance = 5.
Code words: A (0000000000), B (1100011111), C, D.
Changing A to B requires flipping 5 bits.
Error Detection and Correction
Process:
Receive a possibly corrupted code word.
Calculate the Hamming distance to all valid code words.
Assign the received word to the closest valid code word (minimum distance).
Example:
Received: 0000000001.
Distance to A: 1.
Distance to B: 4.
Distance to C: 6.
Distance to D: 9.
Correct to A.
Error Correction Limitations
Bounds: The number of errors that can be corrected depends on the Hamming distance.
Example:
Original: 0000000000 (A).
One error: 0000000011. Correctable to A.
Two errors: 0000000110. Still correctable to A.
Three errors: 0000001110.
Distance to A: 3.
Distance to B: 2. Incorrectly corrected to B.
Correction Limit: d+1 errors cannot be corrected
Error Detection Limit
Detection Limit: d+1 = Number of errors that we can detect.
Four errors can be detected because it doesn't match any of our code words.
Hamming Codes
Purpose: Simple error checking and correction for single-bit errors.
Capabilities: Correct single-bit errors and detect multi-bit errors.
Method: Adding parity bits at every power of two position.
Hamming Code Calculation
Message: The data to be encoded.
Parity Bits: Extra bits inserted at positions that are powers of 2 (1, 2, 4, 8, etc.).
Syndromes: Used to set parity bits such that the sum is zero; errors cause non-zero syndromes.
Example Hamming Code Calculation
Data: 11010111 (8 bits).
Positions: Write out positions, inserting question marks at powers of 2:
1 2 3 4 5 6 7 8 9 10 11 12? ? 1 ? 1 0 1 ? 0 1 1 1Fill in data: insert given message in order, skipping question marks
? ? 1 ? 1 0 1 ? 0 1 1 1
Calculating Parity Bits
Parity bit 1 (P1):
Take bit 1, skip one, take one, skip one and XOR them together.
Bits: 1, 3, 5, 7, 9, 11.
? 1 1 1 0 1. Parity bit = 0 if there is an even number and 1 if there is an odd number of ones.P1 = 0 (even number of ones).
Parity bit 2 (P2):
Take two, skip two, take two, skip two and XOR them together.
Bits: 2, 3, 6, 7, 10, 11.
? 1 0 1 1 1.P2 = 0 (even number of ones).
Parity bit 4 (P4):
Take four, skip four, take 4 and XOR them together.
Bits: 4, 5, 6, 7, 12
? 1 0 1 1P4 = 1 (odd number of ones).
Parity bit 8 (P8):
Take eight then take the rest
Bits: 8, 9, 10, 11, 12
? 0 1 1 1P8 = 1 (odd number of ones).
Completed Hamming Code: 001110110111.
Error Detection and Correction Example
Hamming Code: 001110110111.
Calculate parity bits again:
P1: 011011 = 0
P2: 010111 = 0
P4: 11011 = 0
P8: 10111 = 0
All zeros indicate no error.
Introducing an Error
Introduce an error at position 6: 001111110111.
Recalculate parity bits:
P1: 011101 = 0
P2: 011111 = 1
P4: 11111 = 1
P8: 10111 = 0
Error Detection: The parity bits are not all zeros, indicating an error.
Error Correction: Add the positions of the parity bits that are errors:
2 + 4 = 6. Error at position 6.
Flip the bit at position 6 to correct the error.
Detecting Two Bit Errors
With two errors we can detect it, but not correct it.
Introduce errors at positions 6 and 10: 001111110011.
Recalculate parity bits:
P1: 011101 = 0
P2: 011101 = 0
P4: 11111 = 1
P8: 10011 = 1
The positions, 4 + 8 = 12 does not say anything about where the errors occur.
Convolutional codes
Used for error correction.
Used in NASA and Wi-Fi.
Employs a stream of data and state machine with registers.
Output is generated by summing different registers.
Half Rate Code
NASA uses a convolutional half rate code by transmitting twice as many bits.
Error detection
Parity Bit
Simple error detection method.
Detects whether there is an even or odd number of ones in a string.
A one is added at the end if there is an odd number of ones, and a zero otherwise.
Detects all odd number of errors.
Does not detect even number of errors.
Detects errors with half probability.
Interleaving
Involves sending small chunks of information structured in a matrix.
Parity is checked for each column.
Used to detect burst errors (several errors in a row).
Can detect errors within a chunk of data, but may not pinpoint the exact location.
Checksum
Involves a module of two of the word.
Employs a sum, modules sum, but using a specific length of words.
Error detection is improved over parity bits.
Internet uses 16-bit one's complement checksum; detects the burst errors up to n-bit errors.
Vulnerable to systematic errors to adding zeros causes the sum to remain the same, fooling the checksum.
Four-Bit Checksum Example
Data: 1100 1101 0111 1001 1111.
Split data into four-bit words.
Add words together using one's complement addition.
1100 + 1101 = 11001 -> 11010 (add overflow back in).
1001 + 0111 = 10000 -> 0001 (add overflow back in).
10000 (previous) + 1001 = 10001.
10001 (previous) + 1111= 11110 -> 10000 (add overflow back in).
Take one's complement of the sum to get the checksum: 0010.
Add checksum to the end of the data for transmission.
Receiver Calculation
To check for errors, the receiver performs the same checksum calculation on the received data (including the checksum).
If the result is all zeros, there are no errors.
If the result is non-zero, there is an error.
Cyclic Redundancy Check
It is the strongest of the error detection methods.
Involves the division of two polynomials: a frame of data and generator function.
Binary long division.
The remainder of the division becomes the CRC result. If the receiver implementation of the same calculation is zero than there is n error.
Calculation of CRC
Append zeros. To generate a four-bit we can add four bits of zeros to the end of our data.
This will compute our data and our generator function.
Divide the data by the generator function using XOR division.
Replace the appended zeros with the remainder.
CRC Example
Three-bit CRC calculation.
Data: 1011110111.
Generator Function: 1011.
Append Three Zeros: Add 3 zeros to the data: 1011110111000.
In the next division take the last three bits for the remainder, and use the top bits just to keep track of where the remainder is.
The CRC has double bit error detection that is not vulnerable to systematic errors.
Detailed Version
Hamming Distance
Definition: Minimum number of bit flips required to change one valid code word into another valid code word. This distance is crucial for determining the error detection and correction capabilities of the code.
Significance: Indicates the number of errors that can occur before the original information becomes unrecoverable. A larger Hamming distance allows for the correction of more errors.
Example:
10-bit code words.
n = 2 (values of 0 or 1).
Hamming distance = 5.
Code words: A (0000000000), B (1100011111), C, D.
Changing A to B requires flipping 5 bits. This illustrates that five single-bit errors must occur to transform code word A into code word B, ensuring a certain level of robustness against errors.
Error Detection and Correction
Process:
Receive a possibly corrupted code word.
Calculate the Hamming distance to all valid code words. This involves comparing the received word with each valid code word to find the number of differing bits.
Assign the received word to the closest valid code word (minimum distance). The assumption is that the received word is most likely a corrupted version of the closest valid code word.
Example:
Received: 0000000001.
Distance to A: 1.
Distance to B: 4.
Distance to C: 6.
Distance to D: 9.
Correct to A, as it has the smallest Hamming distance, indicating it is the most likely original code word.
Error Correction Limitations
Bounds: The number of errors that can be corrected depends on the Hamming distance. Specifically, a code with Hamming distance d can correct up to \lfloor \frac{d-1}{2} \rfloor errors.
Example:
Original: 0000000000 (A).
One error: 0000000011. Correctable to A.
Two errors: 0000000110. Still correctable to A.
Three errors: 0000001110.
Distance to A: 3.
Distance to B: 2. Incorrectly corrected to B. This demonstrates that exceeding the error correction capability leads to miscorrection.
Correction Limit: d+1 errors cannot be corrected. This limitation is because with d+1 errors, the received word might be closer to another valid code word, leading to incorrect correction.
Error Detection Limit
Detection Limit: d+1 = Number of errors that we can detect without correcting. Error detection is possible as long as the number of errors does not turn one valid code word into another.
Four errors can be detected because it doesn't match any of our code words. If the Hamming distance between valid code words is 5, up to 4 errors can be detected because the received word will not be a valid code word.
Hamming Codes
Purpose: Simple error checking and correction for single-bit errors in data transmission and storage. Hamming codes are widely used due to their simplicity and efficiency.
Capabilities: Correct single-bit errors and detect multi-bit errors. While primarily designed for single-bit error correction, Hamming codes can also detect double-bit errors but cannot correct them.
Method: Adding parity bits at every power of two position. Parity bits are inserted at positions 1, 2, 4, 8, 16, etc., to cover different subsets of the data bits.
Hamming Code Calculation
Message: The data to be encoded. This is the original data that needs to be protected against errors.
Parity Bits: Extra bits inserted at positions that are powers of 2 (1, 2, 4, 8, etc.). These bits are calculated based on the data bits and are used for error detection and correction.
Syndromes: Used to set parity bits such that the sum is zero; errors cause non-zero syndromes. Syndromes are calculated by XORing the parity bits with the data bits they are meant to cover. A non-zero syndrome indicates an error, and the syndrome value can identify the location of the error.
Example Hamming Code Calculation
Data: 11010111 (8 bits). This is the 8-bit data that we want to encode using a Hamming code.
Positions: Write out positions, inserting question marks at powers of 2:
1 2 3 4 5 6 7 8 9 10 11 12``? ? 1 ? 1 0 1 ? 0 1 1 1- Fill in data: insert given message in order, skipping question marks? ? 1 ? 1 0 1 ? 0 1 1 1
Calculating Parity Bits
Parity bit 1 (P1):
Take bit 1, skip one, take one, skip one and XOR them together. This means P1 covers bits 1, 3, 5, 7, 9, and 11.
Bits: 1, 3, 5, 7, 9, 11.
? 1 1 1 0 1. Parity bit = 0 if there is an even number and 1 if there is an odd number of ones. This ensures that the total number of ones in the covered bits, including the parity bit, is even (even parity).P1 = 0 (even number of ones).
Parity bit 2 (P2):
Take two, skip two, take two, skip two and XOR them together. P2 covers bits 2, 3, 6, 7, 10, and 11.
Bits: 2, 3, 6, 7, 10, 11.
? 1 0 1 1 1.P2 = 0 (even number of ones).
Parity bit 4 (P4):
Take four, skip four, take 4 and XOR them together. P4 covers bits 4, 5, 6, 7, and 12.
Bits: 4, 5, 6, 7, 12
? 1 0 1 1P4 = 1 (odd number of ones).
Parity bit 8 (P8):
Take eight then take the rest. P8 covers bits 8, 9, 10, 11, and 12.
Bits: 8, 9, 10, 11, 12
? 0 1 1 1P8 = 1 (odd number of ones).
Completed Hamming Code: 001110110111. This is the final encoded message with parity bits inserted at the appropriate positions.
Error Detection and Correction Example
Hamming Code: 001110110111.
Calculate parity bits again:
P1: 011011 = 0
P2: 010111 = 0
P4: 11011 = 0
P8: 10111 = 0
All zeros indicate no error. This means that the received message is error-free according to the parity checks.
Introducing an Error
Introduce an error at position 6: 001111110111. This simulates a single-bit error occurring during transmission or storage.
Recalculate parity bits:
P1: 011101 = 0
P2: 011111 = 1
P4: 11111 = 1
P8: 10111 = 0
Error Detection: The parity bits are not all zeros, indicating an error. The non-zero parity bits reveal the presence of an error in the received message.
Error Correction: Add the positions of the parity bits that are errors:
2 + 4 = 6. Error at position 6. The sum of the positions of the incorrect parity bits points to the location of the error.
Flip the bit at position 6 to correct the error, restoring the original message.
Detecting Two Bit Errors
With two errors we can detect it, but not correct it. Hamming codes can detect up to two errors but can only correct one.
Introduce errors at positions 6 and 10: 001111110011. This simulates a scenario where two bits are corrupted during transmission or storage.
Recalculate parity bits:
P1: 011101 = 0
P2: 011101 = 0
P4: 11111 = 1
P8: 10011 = 1
The positions, 4 + 8 = 12 does not say anything about where the errors occur. When multiple errors occur that the positions you get will point to an error that doesn't exist.
Convolutional codes
Used for error correction. Convolutional codes are more complex compared to block codes like Hamming codes, and they operate on a continuous stream of data.
Used in NASA and Wi-Fi. Due to their strong error correction capabilities, convolutional codes are employed in critical applications like satellite communication (NASA) and wireless communication (Wi-Fi).
Employs a stream of data and state machine with registers. Convolutional codes work by passing the input data stream through a series of shift registers, and the output is a function of the current and previous input bits.
Output is generated by summing different registers. The output bits are typically generated by XORing different combinations of the register contents, creating a coded output.
Half Rate Code
NASA uses a convolutional half rate code by transmitting twice as many bits. This means that for every bit of data, two bits are transmitted, providing significant redundancy for error correction.
Error detection
Parity Bit
Simple error detection method. Parity bits are the most basic form of error detection, adding a single bit to a data block to indicate whether the number of ones is even or odd.
Detects whether there is an even or odd number of ones in a string. The parity bit is set to 0 or 1 to make the total count of ones (including the parity bit) either even or odd, depending on the parity scheme used.
A one is added at the end if there is an odd number of ones, and a zero otherwise. This ensures that the total number of ones is even (for even parity) or odd (for odd parity).
Detects all odd number of errors. If an odd number of bits are flipped during transmission, the parity will be incorrect, indicating an error.
Does not detect even number of errors. If an even number of bits are flipped, the parity will remain correct, and the error will go undetected.
Detects errors with half probability. Because it can only detect odd numbers of errors and not even, the probability of detecting an error is 50%.
Interleaving
Involves sending small chunks of information structured in a matrix. Interleaving rearranges the data sequence to spread out consecutive bits across different blocks, making it more resilient to burst errors.
Parity is checked for each column. After interleaving, parity bits are calculated for each column of the matrix, providing error detection capability.
Used to detect burst errors (several errors in a row). By spreading out the bits, a burst error will affect multiple columns, each of which can be detected by the parity check.
Can detect errors within a chunk of data, but may not pinpoint the exact location. Interleaving helps detect errors but does not provide precise error localization.
Checksum
Involves a module of two of the word. Checksums provide a more robust error detection method than simple parity bits by calculating a sum based on the data.
Employs a sum, modules sum, but using a specific length of words. The data is divided into fixed-size words, and these words are added together, often using modular arithmetic to keep the result within a manageable size.
Error detection is improved over parity bits. Checksums can detect a wider range of errors compared to parity bits, including some even numbers of bit flips.
Internet uses 16-bit one's complement checksum; detects the burst errors up to n-bit errors. The Internet checksum algorithm uses 16-bit words and one's complement addition to detect errors in data packets.
Vulnerable to systematic errors to adding zeros causes the sum to remain the same, fooling the checksum. If specific patterns of errors occur that cancel each other out in the checksum calculation, the errors can go undetected.
Four-Bit Checksum Example
Data: 1100 1101 0111 1001 1111.
Split data into four-bit words. The data is divided into 4-bit segments for checksum calculation.
Add words together using one's complement addition.
1100 + 1101 = 11001 -> 11010 (add overflow back in). If the addition results in a carry, the carry is added back into the least significant bit.
1001 + 0111 = 10000 -> 0001 (add overflow back in).
10000 (previous) + 1001 = 10001.
10001 (previous) + 1111= 11110 -> 10000 (add overflow back in).
Take one's complement of the sum to get the checksum: 0010. The one's complement is obtained by inverting all the bits.
Add checksum to the end of the data for transmission. The calculated checksum is appended to the original data before transmission.
Receiver Calculation
To check for errors, the receiver performs the same checksum calculation on the received data (including the checksum).
If the result is all zeros, there are no errors. A zero result indicates that the data was received without errors.
If the result is non-zero, there is an error. A non-zero result indicates that the received data contains errors.
Cyclic Redundancy Check
It is the strongest of the error detection methods. CRC is widely used for its high accuracy in detecting errors and is more complex than parity bits and checksums.
Involves the division of two polynomials: a frame of data and generator function. CRC treats the data as a large binary polynomial and divides it by another fixed polynomial called the generator polynomial.
Binary long division. The division is performed using XOR operations, similar to binary long division.
The remainder of the division becomes the CRC result. The remainder is appended to the original data and transmitted.
If the receiver implementation of the same calculation is zero than there is n error. On the receiving end, the same division is performed, and if the remainder is zero, it indicates that there are no errors.
Calculation of CRC
Append zeros. To generate a four-bit we can add four bits of zeros to the end of our data.
This will compute our data and our generator function.
Divide the data by the generator function using XOR division. The data with appended zeros is divided by the generator polynomial using XOR operations.
Replace the appended zeros with the remainder. After the division, the remainder replaces the appended zeros, forming the CRC code.
CRC Example
Three-bit CRC calculation.
Data: 1011110111.
Generator Function: 1011.
Append Three Zeros: Add 3 zeros to the data: 1011110111000. This prepares the data for polynomial division.
In the next division take the last three bits for the remainder, and use the top bits just to keep track of where the remainder is. The XOR division is performed to compute the remainder.
The CRC has double bit error detection that is not vulnerable to systematic errors. CRC is capable of detecting burst errors, single-bit errors, and double-bit errors with high reliability.