美国麻省理工大学：《Communication Systems Engineering（通讯系统工程）》Lectures 14: Cyclic Codes and error detection

16.36: Communication Systems Engineering Lectures 14: Cyclic Codes and error detection Eytan Modiano

16.36: Communication Systems Engineering Lectures 14: Cyclic Codes and error detection Eytan Modiano

Cyclic Codes a cyclic code is a linear block code where if c is a codeword, so are all cyclic shifts of c E.g., 1000, 110, 101,011 is a cyclic code Cyclic codes can be dealt with in the very same way as all other lbc s Generator and parity check matrix can be found a cyclic code can be completely described by a generator string G All codewords are multiples of the generator string In practice, cyclic codes are often used for error detection(CRc) Used for packet networks When an error is detected by the received, it requests retransmission

Cyclic Codes • A cyclic code is a linear block code where if c is a codeword, so are all cyclic shifts of c – E.g., {000,110,101,011} is a cyclic code • Cyclic codes can be dealt with in the very same way as all other LBC’s – Generator and parity check matrix can be found • A cyclic code can be completely described by a generator string G – All codewords are multiples of the generator string • In practice, cyclic codes are often used for error detection (CRC) – Used for packet networks – When an error is detected by the received, it requests retransmission

Error detection techniques Used by the receiver to determine if a packet contains errors If a packet is found to contain errors the receiver requests the transmitter to re-send the packet Error detection techniques Parity check E.g, single bit Cyclic redundancy check(CRC)

Error detection techniques • Used by the receiver to determine if a packet contains errors • If a packet is found to contain errors the receiver requests the transmitter to re-send the packet • Error detection techniques – Parity check E.g., single bit – Cyclic redundancy check (CRC)

Parity check codes k Data bits r Check bits Each parity check is a modulo 2 sum of some of the data bits Example: X1 +++ t x t x

Parity check codes k Data bits r Check bits • Each parity check is a modulo 2 sum of some of the data bits Example: c1 = x1 + x 2 + x3 c 2 = x 2 + x 3 + x4 c 3 = x1 + x 2 + x4

Single Parity Check Code The check bit is 1 if frame contains odd number of 1s otherwise it is o 1011011->10110111 1100110->11001100 Thus, encoded frame contains even number of 1's Receiver counts number of ones in frame An even number of 1s is interpreted as no errors An odd number of 1's means that an error must have occured a single error ( or an odd number of errors)can be detected An even number of errors cannot be detected Nothing can be corrected Probability of undetected error(independent errors) N acket size i even p=error prob

Single Parity Check Code • The check bit is 1 if frame contains odd number of 1's; otherwise it is 0 1011011 -> 1011011 1 1100110 -> 1100110 0 • Thus, encoded frame contains even number of 1's • Receiver counts number of ones in frame – An even number of 1’s is interpreted as no errors – An odd number of 1’s means that an error must have occured A single error (or an odd number of errors) can be detected An even number of errors cannot be detected Nothing can be corrected • Probability of undetected error (independent errors) P u ndet ected) = ∑   N  pi (1 − p ) N −i N = packet size ( i even  i  p = error prob

Cyclic Redundancy Checks(CRC) R M=info bits k Data bits r Check bits R=check bits T codeword T=M2+R A CRC is implemented using a feedback shift register Bits in e Bits out

Cyclic Redundancy Checks (CRC) k Data bits r Check bits M R T T = M 2 r + R M = info bits R = check bits T = codeword • A CRC is implemented using a feedback shift register Bits in Bits out

Cyclic redundancy checks T=M2+R How do we computer the check bits)? Choose a generator string G of length [+1 bits Choose R such that T is a multiple ofG (T=AG, for some A Now when T is divided by g there will be no remainder = no errors All done using mod 2 arithmetic T=M2+R=AG=>M2=AG+r(mod 2 arithmetic) Let r= remainder of m 2/g and t will be a multiple of g Choice of G is a critical parameter for the performance of a crc

Cyclic redundancy checks T = M 2 r + R • How do we compute R (the check bits)? – Choose a generator string G of length r+1 bits – Choose R such that T is a multiple of G (T = A*G, for some A) – Now when T is divided by G there will be no remainder => no errors – All done using mod 2 arithmetic T = M 2r + R = A*G => M 2r = A*G + R (mod 2 arithmetic) Let R = remainder of M 2r/G and T will be a multiple of G • Choice of G is a critical parameter for the performance of a CRC

Example r=3.G=1001 M=110101=>M2r=110101000 110011 1001110101000 1001 Modulo 2 01000 DiⅤ sion 1001 0001100 1001 01010 1001 01l=r(3 bits)

Example r = 3, G = 1001 M = 110101 => M2r = 110101000 110011 1001 110101000 1001 01000 1001 0001100 1001 01010 1001 011 = R (3 bits) Modulo 2 Division

Checking for errors Let T be the received sequence Divide T by G If remainder =0 assume no errors If remainder is non zero errors must have occurred Example 1001|110101011 Send t=110l01011 1001 Receive t=110101011 (no errors) 01000 0001101 No way of knowing how many errors occurred or which bits are 01001 In error 1001 000=> No errors

Checking for errors • Let T’ be the received sequence • Divide T’ by G – If remainder = 0 assume no errors – If remainder is non zero errors must have occurred Example: 1001 Send T = 110101011 110101011 Receive T’ = 110101011 (no errors) No way of knowing how many errors occurred or which bits are In error 1001 01000 1001 0001101 1001 01001 1001 000 => No errors

Mod 2 division as polynomial division

Mod 2 division as polynomial division