Error Detection And Correction Methods-Cont

Error Detection And Correction Methods ™  Longitudinal Red Check(LRC) o    In LRC, a block of bits is organized in a table (rows and columns) o    For example instead of sending 32 bits, we organize them in a table made of 4 rows and 8 columns

o    We then calculate the Parity bit for each column and create a new row of 8 bits which are the parity bits for the whole block th o    Note  that  the  first  parity bit  in  the  5    row  is  calculated  based  on  all  the  first bits o    The second parity bit is calculated based on all the second bits and so on o    We  then  attach  the  8  parity  bits  to  the  original  data  and  send  them  to  the receiver Example 9.4 Suppose the following block is sent: 10101001 00111001 11011101 11100111 __________ 10101010   (LRC) Š    It is hit by a burst of length 8 and some bits are corrupted: 10100011 10001001 11011101 11100111 __________ 10101010   (LRC) Š    Receiver  checks  LRC,  some  of  bits  do  not  follow  even  parity  rule  and  whole block is discarded 10100011 10001001 11011101 11100111 __________ 1  0101010   (LRC) ƒ     Performance of LRC o    Burst errors can be detected more often o    As shown in the last example, an LRC of 'n; bits can easily detect a burst error of 'n' bits o    A burst error of more than 'n' bits is  also detected by LRC with a very high probability o    One pattern of errors remain elusive o    If two bits in one data unit are changed and two bits in exactly the same place in another data unit are also damaged For Example: -    Original data units 11110000 11000011 -    Changed data units 01110001 01000010 ™   Cyclic Redundancy Check (CRC) o    Most powerful of checking techniques o    VRC and LRC are based on  Addition o    CRC is based on Binary Division o    A  sequence  of  redundant  bits  called  CRC  or  CRC  remainder  is  appended  to the  end  of  the  data  unit,  so  that  the  resulting  data  unit  becomes  exactly divisible by a second predetermined binary number o    At its destination, the data unit is divided by the same number o    If at this step, there is no remainder, the incoming data unit is assumed to be intact and is therefore accepted o    A remainder indicates that a data unit has been damaged and therefore must be rejected Qualities of CRC ŠTo be valid the CRC must have two qualities: -It must have exactly one less bit than the divisor -Appending  it  to  the  end  of  the  data  must  make  the  resulting  bit  sequence  exactly divisible by the divisor