Error Detection And Correction
The transmission media is not 100% reliable. It introduces modification of the signal such as distortion, attenuation noise and interference. This introduces errors in transmitted data, in the form of bit errors.
The bigger the frame size and the higher the probability of single-bit error, the lower the probability of receiving an error-free frame. → we need an error detection and correction scheme
Errors can be :
- single-bit error: only one bit is corrupted. They are common in parallel communications
- 2-bit errors
- burst error: more than one bit is corrupted, because the duration of the noise is longer than the duration of the transmission of one bit. Burst errors are common in serial communication. A burst error is a sequence of bits between two error bits. The sequence in between may or may not contain error bits.
– Commonly used error detection schemes: Checksum, CRC and Message Authentication Code (MAC)
Some Error detection and correction techniques are based on adding redundancy to the frame. The redundancy is a function of the message in the frame: R = f(M)
Error detection with the Checksum method
- provides the sole guarantee of detecting one-bit errors.
- used in IP, TCP and UDP checksum fields, in the header.
- principle: at a receiving end: to determine if the received checksum is correct or not, the host calculates the checksum as follows: it is the one’s complement of the sum of all 16-bit words (excluding the checksum field) with “end-around carry”. If this value is equal to the checksum value in the frame, then the frame is error-free.
- a good example in calculating IP header checksum: http://www.thegeekstuff.com/2012/05/ip-header-checksum/
- Another way to verify the checksum of a received frame:
- set the checksum field to 0
- add all 16-bit words, with end-around carry
- do one’s complement of the result
- add all 16-bits words of the packet to the result
- if you find 0xFFFF, then the checksum is correct and the frame is correct
- one side note: if the checksum value of the received frame is 0xFFFF, then we must include the checksum value in the addition of the 16-bit words.
Error detection with CRC
- is an advanced form of the checksum function
- provides the guarantee of detecting
- any odd number of errors,
- 2-bit errors
- single burst errors, as long as the burst error size <= the CRC size (c)
- the message M is written in polynomial arithmetic: each bit of the message is the coefficient of the corresponding term. For example: if M = 0110101, then it can be written in the following polynomial format: x5 + x4 + x2 + 1
- At the sender side: the value of the CRC checksum is the remainder of the division (the Modulo) of M (the polynomial) by a chosen divisor (the generator polynomial). The CRC checksum is appended to the message and the frame is sent
- the generator polynomial is determined by the CRC algorithm
- at the receiver side, the receiver takes the message plus the CRC and divides them by the divisor (the generator polynomial). If the remainder = 0, then there is no error.
- the CRC checksum is stored in a checksum register. The checksum register can have different widths: 1 byte, 2 bytes, 4 bytes,…
- if the size of the CRC is c, then there is 1/2c chance of having a packet with the same CRC value as another packet.
- works good, as long as the width of the divisor is close to the checksum register width
Error detection with Message Authentication Codes
- the MAC algorithm takes a message “M” and a secret “s” to generate a MAC “c”
- the secret “s” is known from both the sender and the receiver
- Having “M” and “c”, it is almost impossible to determine “s”
- If the receiver receives a packet with correct MAC, then it is assumed that the sender holds the secret “s”
- If you flip one bit in “M”, this leads to a completely different “c”. Likewise, sometimes flipping one bit in “M” will lead to the same MAC!
- MAC provides no error detection guarantees. The only guarantee this scheme provides is in terms of probability of detecting errors. For example, if we have a MAC of 16-bit long, then the only guarantee is that we have a probability of 99.9998% of detecting one error
- used in TLS mainly as a security mechanism
A note on binary math
- decimal division:
- binary division:
- binary addition basic rules:
- 0 + 0 = 0
- 0+ 1 = 1
- 1 + 1 = 10 (there is a carry)
- 1 + 1 + 1 = 11 (there is a carry)
- binary subtraction rules:
- 0 – 0 = 0
- 1 – 0 = 1
- 10 – 1 = 1
- 1 – 1 = 0
- 0 – 1: borrow 1 to make it 10, then put it back in the next row.