MZOWA
MZOWA
MZOWA
Burst error two or more bits in the data unit have changed.
7.2 Detection
Error detection uses the concepts of redundancy, which means adding extra bits detecting errors at the destination.
Checksum
(used primarily by upper layers)
VRC Vertical Redundancy Check LRC Longitudanal Redundancy Check Redundancy ????
Parity : 2 type
Parity Check
Simplest technique. A redundant bit (parity bit), is appended to every data unit. Even parity - the total number of 1's in the data plus parity bit must be an even number.
example
Example 1
Even Parity
Suppose the sender wants to send the word world. In ASCII the five characters are coded as 1110111 1101111 1110010 1101100 1100100
Example 2
Even Parity
Now suppose the word world in Example 1 is received by the receiver without being corrupted in transmission. 11101110 11011110 11100100 11011000 11001001
The receiver counts the 1s in each character and comes up with even numbers (6, 6, 4, 4, 4). The data are accepted.
Example 3
Even Parity
Now suppose the word world in Example 1 is corrupted during transmission. 11111110 11011110 11101100 11011000 11001001
The receiver counts the 1s in each character and comes up with even and odd numbers (7, 6, 5, 4, 4). The receiver knows that the data are corrupted, discards them, and asks for retransmission.
VRC Performance
VRC can detect all single-bit errors. It can also detect burst errors as long as the total number of bits changed is odd (1,3,5etc) How bout if the total number of bit changed is even ??? Yea.. There is problem !!! In short VRC can detect all single-bit errors. It can detect burst errors only if the total number of errors in each data unit is odd.
Original data
11100111 11011101 00111001 10101001
11100111
11011101 00111001 10101001 ----------------1 0 1 0 1 0 1 0 LRC 11100111 11011101 00111001 10101001 10101010
Performance of LRC
LRC increases the likelihood of detecting burst errors. As we showed in the previous e.g. an LRC of n bits can easily detect a burst error of n bits. A burst error of more than n bits is also detected by LRC with a very high probability.
-note for Jabatan Tanah daerah Temerloh Mr. Hakim (2004 co)
7.5 CRC
The most powerful of the redundancy checking technique. Based on binary division. The redundancy bits used by CRC are derived by dividing the data unit by a predetermined divisor; the remainder is the CRC. A CRC must: have exactly one less bit than the divisor appending it to the end of the data string must make the resulting bit sequence exactly divisible by the divisor.
7.9
1. 2. 3.
1. 2. 3. 4.
Get the raw frame. Left shift the raw frame by n bits and divide it by divisor. The remainder is the CRC bit. Append the CRC bit to the frame and transmit.
7.5 CRC
CRC generator at the sending node. CRC checker at the receiving node. Polynomial: The CRC generator (the divisor) is most often represented as an algebraic polynomial. e.g.
7.13
ITU-16
ITU-32
x16 + x12 + x5 + 1
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
HDLC
LANs
7.6 Checksum
The error detection used by the higher-layer protocols. Check generator in the sending node Checksum checker at receiving node
Ethernet frame
Checksum generator
In the sender, the checksum generator subdivides the data unit into equal segments of n bits (usually 16). These segments are added together using ones complement arithmetic in such a way that the total is also n bits long. The total(sum) is then complemented and appended to the end of the original data unit as redundancy bits, called checksum field. The extended data unit is transmitted across the network. So if the sum of the data segment is T, the checksum will be -T
7.15
Checksum checker
The receiver subdivides the data unit as above and adds all segments together and complements the result. If the extended data unit is intact, the total value found by adding the data segments and the checksum field shud be zero. If the result is not zero, the packet contains an error and the receiver rejects it.
The unit is divided into k sections, each of n bits All sections are added together using ones complement to get the sum. The sum is complemented and becomes the checksum. The checksum is sent with the data.
The unit is divided into k sections, each of n bits. All sections are added together using ones complement to get the sum. The sum is complemented. If the result is zero, the data are accepted. Otherwise, they are rejected.
Example 6
Suppose the following block of 16 bits is to be sent using a checksum of 8 bits.
10101001 00111001
Sum Checksum
Example 7
Now suppose the receiver receives the pattern sent in Example 6 and there is no error.
10101001 00111001 00011101
When the receiver adds the three sections, it will get all 1s, which, after complementing, is all 0s and shows that there is no error.
10101001
00111001
00011101 ------------
Sum
Complement
11111111
00000000 means that the pattern is OK.
Example 8
Now suppose there is a burst error of length 5 that affects 4 bits. Original data 10101001 00111001 00011101
Corrupted data
11111001
00011101 Partial Sum 1 11000101
Carry
Sum Complement
1
11000110 00111001 the pattern is corrupted.
Focus on Correction
simple
case:
Single-Bit
Error
between
data
and
1
2 3 4 5 6 7
2
3 3 3 4 4 4
3
5 6 7 9 10 11
* Check bits occupy positions that are powers of 2 In the Hamming code, each r bit is the VRC bit for one combination of data bits: r1 is the VRC bit for one combination of data bits, r2 is the VRC bit for another combination of data bits, and so on. The combinations used to calculate each of the four r values for a seven-bit data sequence are as follows: r1 : bits 1, 3, 5, 7, 9, 11 r2 : bits 2, 3, 6, 7, 10, 11 r4 : bits 4, 5, 6, 7 r5 : bits 8, 9, 10, 11
All bit positions that are powers of 2 are used as parity bits. (positions 1, 2, 4, 8) All other bit positions are for the data to be encoded. (positions 3, 5, 6, 7, 9, 10, 11) Each parity bit calculates the parity for some of the bits in the code word. The position of the parity bit determines the sequence of bits that it alternately checks and skips. General rule for position n: skip n1 bits, check n bits, skip n bits, check n bits...
Position 1 (n=1): skip 0 bit (0=n1), check 1 bit (n), skip 1 bit (n), check 1 bit (n), skip 1 bit (n), etc. (1,3,5,7,9,11...) Position 2 (n=2): skip 1 bit (1=n1), check 2 bits (n), skip 2 bits (n), check 2 bits (n), skip 2 bits (n), etc. (2,3,6,7,10,11...) Position 4 (n=4): skip 3 bits (3=n1), check 4 bits (n), skip 4 bits (n), check 4 bits (n), skip 4 bits (n), etc. (4,5,6,7,12...) Position 8 (n=8): skip 7 bits (7=n1), check 8 bits (n), skip 8 bits (n), check 8 bits (n), skip 8 bits (n), etc. (8-15,24-31,40-47,...)
7.18
1011 11
1001 9
0111 7
0101 5
0011 3
0001 1
r8
r4
r2
r1
1011
1010
0111
0110
0011
0010
11
d
10
d d r8
7 d
6 d d r4
3 d
2 r2 r1
0111
0110
0101
0100
7 d d d r8 d
6 d
5 d
4 r4 d r2 r1
1011
1010
1001
1000
11
d
10
d
9 d
8
r8 d d d r4 d r2 r1
7.19
7.20
Single-Bit Error
Error Detection
Example Question
Consider the transmitted data to be 00101010111. Show how the error bit position is determined ???????????????
answer
10101010111
2. Consider the transmitted data to be 00101010111. Show how the error bit position is determined.
1011 = 11
THANK YOU