FLOW AND ERROR CONTROL The most important responsibilities of the data link layer are flow control and error control. Collectively, these functions are known as data link control. Flow Control Error Control Flow control refers to a set of procedures used to restrict the amount of data that the sender can send before waiting for acknowledgment. Error control in the data link layer is based on automatic repeat request, which is the retransmission of data,when an error is detected.@ Data can be corrupted during transmission. Some applications require that errors be detected and corrected. Types of Errors Redundancy Detection Versus Correction Forward Error Correction Versus Retransmission Coding Modular Arithmetic In a single-bit error, only 1 bit in the data unit has changed. A burst error means that 2 or more bits in the data unit have changed@ To detect or correct errors, we need to send extra (redundant) bits with data. Redundancy can be achieved thro’ coding schemes. Broad categories are: 1. Block Coding 2. Convolution coding We concentrate on block codes and leave convolution codes to advanced texts.The structure of encoder and decoder Sender Receiver Decoder Message Message K correct or discard [eee] Unreliable transmission Message and redundancy >| Received information In modulo-N arithmetic, we use only the integers in the range 0 to N -1, inclusive.In block coding, we divide our message into blocks, each of k bits, called datawords. We add r redundant bits to each block to make the length n =k + r. The resulting n-bit blocks are called codewords. Error Detection Error Correction Hamming Distance Minimum Hamming DistanceDatawords and codewords in block coding k bits kbits cee k bits 2 Datawords, each of k bits n bits n bits eee n bits 2 Codewords, each of n bits (only 2 of them are valid)Process of error detection in block coding k bits Sender Dataword Generator Unreliable transmission Receiver k bits Extract Checker Discard Codeword n bits‘Structure of encoder and decoder in error correction Sender Receiver Encoder Dataword K k bits Correct Checker Generator | Unreliable transmissionExample Let us add more redundant bits to Example 10.2 to see if the receiver can correct an error without knowing what was actually sent. We add 3 redundant bits to the 2-bit dataword to make 5-bit codewords. Table 10.2 shows the datawords and codewords. Assume the dataword is 01. The sender creates the codeword 01011. The codeword is corrupted during transmission, and 01001 is received. First, the receiver finds that the received codeword is not in the table. This means an error has occurred. The receiver, assuming that there is only 1 bit corrupted, uses the following strategy to guess the correct dataword.Example @ 1. Comparing the received codeword with the first codeword in the table (01001 versus 00000), the receiver decides that the first codeword is not the one that was sent because there are two different bits. 2. By the same reasoning, the original codeword cannot be the third or fourth one in the table. 3. The original codeword must be the second one in the table because this is the only one that differs from the received codeword by 1 bit. The receiver replaces 01001 with 01011 and consults the table to find the dataword 01.A code for error correction [ Dataword Codeword 00 00000. 01 01011 10 10101 Tal 11110Example _ Find the minimum Hamming distance of the coding scheme in table above Solution We first find all the Hamming distances. 00000, 11110) d0101, 11110) The dpi, in this case is 3.@) Example _ @ Our block code scheme has d,,;, = 3. This code can detect up to two errors. Again, we see that when any of the valid codewords is sent, two errors create a codeword which is not in the table of valid codewords. The receiver cannot be fooled. However, some combinations of three errors change a valid codeword to another valid codeword. The receiver accepts the received codeword and the errors are undetected.An error-detecting code can detect only the types of errors for which designed; other types of errors may remain undetected. The Hamming distance between two words is the number of differences between corresponding bits. The minimum Hamming distance is the smallest Hamming distance between all possible pairs in a set of words. To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in a block code must be dmin = S + 1. To guarantee correction of up to terrors in all cases, the minimum Hamming distance in a block code must be min = 2t+ 1.LINEAR BLOCK CODES Almost all block codes used today belong to a subset called linear block codes. A linear block code is a code in which the exclusive OR (addition modulo-2) of two valid codewords creates another valid codeword. Minimum Distance for Linear Block Codes Some Linear Block CodesQD A simple parity-check code is a single-bit error- detecting code in which a k-bit dataword is changed to n-bit codeword where n = k + 1 with dpi, = 2. Extra bit is called parity bit, selected to make total no of 1s even in the codeword.Simple parity-check code C(5, 4) Datawords Codewords Datawords Codewords 0000 00000 1000 10001 0001 OOOLL 1001 10010 0010 00101 1010 10100 OO11 00110 1011 foul 0100 O1001 1100 11000 O101 O1010 1101 11011 O10 01100. 110 11101 Ol OUI 1111 1110r0 = a3+a2+a1+a0 (modulo-2) s0 = b3+b2+b1+b0+q0 (modulo-2) If sO=0 no error and s0=1 then error present.Encoder and decoder for simple parity-check code Sender Receiver Dataword Dataword 23] 22]21] 20] a3]2] a 20] Accept Decision logic Syndromeg Generator Checker Parity bit t Unreliable transmission as]@2]21]0]%0 bsfba|bs bofao Codeword CodewordExample Let us look at some transmission scenarios. Assume the sender sends the dataword 1011. The codeword created from this dataword is 10111, which is sent to the receiver. We examine five cases: 1. No error occurs; the received codeword is 10111. The syndrome is 0. The dataword 1011 is created. 2. One single-bit error changes a;. The received codeword is 10011. The syndrome is 1. No dataword is created. 3. One single-bit error changes ry. The received codeword is 10110. The syndrome is 1. No dataword is created.Example (continued) 4. An error changes rg and a second error changes a3. The received codeword is 00110. The syndrome is 0. The dataword 0011 is created at the receiver, Note that here the dataword is wrongly created due to the syndrome value. 5. Three bits—a3, az, and a;—are changed by errors. The received codeword is 01011. The syndrome is 1. The dataword is not created. This shows that the simple parity check, guaranteed to detect one single error, can also find any odd number of errors. A simple parity-check code can detect an odd number of errors ®‘CYCLIC CODES Cyclic codes are special linear block codes with one extra property. In a cyclic code, if a codeword is cyclically shifted (rotated), the result is another codeword. We discuss cyclic code called Cyclic Redundancy Check(CR©) used in LANs and WANs. Cyclic Redundancy Check Polynomials Cyclic Code Analysis Advantages of Cyclic Codes Other Cyclic CodesA CRC code with C(7, 4) Dataword “odeword Dataword Codeword 0000 0000000, 1000 1000101 0001 OOO1011 1001 1001110 0010 0010110 1010 1010011 OO11 0011101 1011 1011000. 0100 O100111 1100 1100010, O101 0101100. 1101 1101001 O10 0110001 1110 1110100 Ou OII010 Wi WHCRC encoder and decoder Sender Receiver Divisor enerator Pc Checker Remainder Unreliable transmissionPEAhH bE Division, Dataword 1001 Quotient 1 Leftmost bit 0: use 0000 divisor o10 Leftmost bit 0: use 0000 divisor Codeword| 100 i/) Ho Dataword Remainder Dividend: ‘augmented dataword Remainder Division in CRC encoderDivision in the CRC decoder for two Codeword [10-0 1[1 10 Division | 1010 1011)1001 110 <~Codeword vont 0101 oo00 101d 1oit 0000 oo00 ooo Dataword, cepted OO cases Codeword [1 0 0 0[1 10 oi | 1010 1011)1 00011 0 <~Codeword Dataword discardedA polynomial to represent a binary word Ce ee ea ours wae Gee. 1 0 ° o ° 1 1 Le Tt + On Gee Ox & somes IRM IEe 430 Rie Gok oD ¥ @ a. Binary pattern and polynomial b Short form Fig above shows one immediate benefit; a 7 bit pattern can be replaced by three terms.Polynomial with 3 terms as x?3+x+1 has 24 bits in length (three 1s and 21 zeros.CRC division using polynomials Dataword) x3 +1 Divisor ERE Dividend: Wet pee e augmente ett oe evan a xt to + x x2 + x | Remainder t Codeword] x6 + x3 | x2 + x Dataword Remainder The divisor in a cyclic code is normally called the generator polynomial or simply the generator.In a cyclic code s(x) representing syndrome, If s(x) # 0, one or more bits is corrupted. If s(x) = 0, either a. No bit is corrupted. or b. Some bits are corrupted, but the decoder failed to detect them. If the generator has more than one term and the coefficient of x° is 1, all single errors can be caught.