L14 - Data communication, Error detection, Hamming Flashcards
Define Error Correction Coding…
Adding redundancy to data to improve reliability during transmission.
What is a Codeword in ECC?
An element of a standardised protocol.
What is Forward Error Correction? When is it used?
A technique used by the transmitter when transmitting a message. It’s done to improve transmission reliability when channels are noisy and unreliable.
What is the Repetition Code process? Why is it used? What is an issue with it? What is the solution to this issue?
The process of repeatedly transmitting data in order to compensate for data error caused by noise.
Issue -> Poor code rate: Each data bit gets encoded into multiple transmitted bits, causing redundancy.
Solution -> Hamming Code.
What type of algorithm is Hamming Code? What algorithmic theory is it based on?
An error correction algorithm based on block coding.
What is the bit-size of the standard Hamming Code? What are the associated input data bit and output parity bit sizes?
Hamming Code is 7-bits.
Input Bits are 4 bits.
Parity Bits are 3 bits.
In Hamming Coding, what is the Input and Output?
Input -> 4 data bits
Output -> 3 parity bits
What is the problem definition for a 7-bit Hamming Code?
Input -> Series of 4 data bits.
Output -> Series of 3 parity bits combined with the 4 data bits.
Input-output relation -> The 3 parity bits can correct a 1 bit error of the input.
Give the process steps of sending data using Hamming Code of 7 bits…
- Hamming Code is 7 bits, Input data is 4 bits, Parity is 3 bits
- HC = [d7, d6, d5, p4, d3, p2, p1]
- Input = [1,0,1,1]
- Substitute Input data into Hamming Code
- [ 1, 0, 1, p4, 1, p2, p1 ]
- For p1, if we want even parity
- p1 depends on d3, d5, d7
- d3,d5,d7 = 1,1,1 -> Odd parity
- Thus, p1 = 1 for even parity
- p1,D3,D5,D7 = 1,1,1,1
- For p2, if we want even parity
- p2 depends on D3,D6,D7 -> [ 1, 0, 1 ]
- P2 flips to 0 to sustain even parity
- P2,D3,D6,D7 = [ 0,1,0,1 ]
- p4 -> D5,D6,D7 -> [p4, 1,0,1] -> [0,1,0,1]
- Thus, parity bits are
- p1,p2,p3 = 1, 0, 0
- Sub into Hamming Code to establish data to send….
- [d7, d6, d5, p4, d3, p2, p1] = [1, 0, 1, 0, 1, 0, 1]
Explain how error detection using Hamming Code is used for the data 1010101 that due to noise during transmission has been converted to 1110101.
- If noise has been added to the data stream such that it becomes -> 1110101
- Check P1,P2,P4 in received data stream to ensure received parity of each matches the sending parity.
- P1 depends on D3, D5, D7.
- P1 = 1
- D3,D5,D7 = 1, 1, 1
- 1,1,1,1 -> Even parity as before. No error detected.
- P2 depends on D3, D6, D7
- P2 = 0
- D3,D6,D7 = 1, 1, 1
- P2, D3, D6, D7 = 0,1,1,1 -> Odd parity
- Error has been detected since sending parity for P2 is different to receiving parity.
- P4 depends on D5, D6, D7
- P4 = 0
- D5, D6, D7 = 111
- = 0111 -> Odd Parity -> Error detected.
Which data bits do the Parity-bits P1, P2, P4 depend on?
P1 -> D3,D5,D7
P2 -> D3,D6,D7
P4 -> D5,D6,D7
Write the Hamming Code of. Ignore parity bits.
HC = [d7, d6, d5, p4, d3, p2, p1]
Input = [1,0,1,1]
HC = [1,0,1,P4,1,P2,P1]
Given the Hamming Code [ 1, 0, 1, p4, 1, p2, p1 ], if we want even Parity, calculate P1, P2, P4.
P1 -> D3,D5,D7 -> 1,1,1 -> P1 = 1
P1,D3,D5,D7 = 1111
P2 -> D3,D6,D7 -> 101 -> P2 = 0
P2,D3,D6,D7 = 0101
P4 -> D5,D6,D7 = 0101
P1 = 1
P2 = 0
P4 = 0
When performing error detection using Hamming Code, how do we know if an error has occurred in the transmitted data?
If the parity of the corresponding
P1,D3,D5,D7
P2,D3,D6,D7
P4,D5,D6,D7
is different.
What are issues with Hamming Code?
Can only correct 1 bit errors
Can detect 2 bit errors, but can’t correct them.
