Error Detection And Correction Methods-Cont

ƒ     Performance of Checksum o    Detects all errors involving an odd number of bits o    Detects most errors involving an even number of bits o    One pattern remains elusive Examples Example 9.7     Suppose a block of 16 bits need to be sent:   10101001 00111001 10101001 00111001 ---------------- 11100010    Sum 00011101    Checksum     Sent pattern: 10101001 00111001 00011101 checksum Example 9.8    Examples of no error and a burst error

Segment 1 Segment 2 Checksum

10101001 Segment1 00111001 Segment2 00011101 Checksum

----------------- ---------------- Sum                  11111111 Sum Complement  00000000 Complement

10101111 11111001 00011101 11000110 00111001

Error is invisible if a bit inversion is balanced by an opposite bit inversion in the corresponding digit of another segment Segment1         10111101 Segment2 Checksum Sum 00101001 00011001 ---------------------- 11111111 ®     The error is undetected ERROR CORRECTION o    Mechanisms that we have studied all detect errors but do not correct them o    Error correction can be done in two ways: -Receiver can ask Sender for  Re- TX -Receiver  can  use  an  error-detecting  code,  which  automatically  correct  certain errors o    Error correcting code are more sophisticated than error detecting codes o    They require more redundancy bits o    The  number  of  bits  required  to  correct  multiple  -bit  or  burst  error  is  so  high that in most cases it is inefficient o    Error correction is limited to 1, 2 or 3 bit ™   Single-bit Error Correction Simplest case of error correction o    Error   correction   requires   more   redundancy   bits   than   error detection o    One additional bit can detect single-bit errors Š    Parity bit in VRC Š    One bit for two states: error or no error o    To correct the error, more bits are required     Error correction locates the invalid bit or bits 8 states for 7-bit data: no error, error in bit 1, and so on     Looks like three bits of redundancy is adequate     What if an error occurs in the redundancy bits? Hamming Code Redundancy Bits (r) o    r must be able to indicate at least m+r+1 states o    m+r+1 states must be discoverable by r bits o    Therefore, 2r ³ m+r+1 o    If m=7, r=4 as 24 ³ 7+4+1 Hamming Code Š    Each r bit is the VRC bit for one combination of data bits     r1(r2) bit is calculated using all bit positions whose binary representation includes a 1 in the first(second) position, and so on