Module-III(2).pdf

Data Communications and Computer Networks Assistant Professor Department of Computer Science & Engineering IIIT Naya Raipur  Module III Data Link Layer Note To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in...

Data Communications and Computer Networks Assistant Professor Department of Computer Science & Engineering IIIT Naya Raipur  Module III Data Link Layer Note 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 t errors in all cases, the minimum Hamming distance in a block code must be dmin = 2t + 1. In a linear block code, the exclusive OR (XOR) of any two valid codewords creates another valid codeword. A simple parity-check code is a single-bit error-detecting code in which n = k + 1 with dmin = 2. Longitudinal Redundancy Check (2D-parity check) In this method, data which the user want to send is organised into tables of rows and columns. A block of bit is divided into table or matrix of rows and columns. In order to detect an error, a redundant bit is added to the whole block and this block is transmitted to receiver. The receiver uses this redundant row to detect error. After checking the data for errors, receiver accepts the data and discards the redundant row of bits.  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. For example, if 1011000 is a code word and we cyclically left-shift, then 0110001 is also a code word. In this case, if we call the bits in the first word a0 to a6 and the bits in the second word b0 to b6, we can shift the bits by using the following: b1=a0 b2=a1 b3=a2 b4=a3 b5=a4 b6=a5 b0=a6 One of the categories of cyclic codes called the cyclic redundancy check (CRC) that is used in networks such as LANs and WANs. Table A CRC code with C(7, 4) Cyclic Redundancy Check (CRC) Figure CRC encoder and decoder  Figure A polynomial to represent a binary word 10.8 Figure CRC division using polynomials Figure Division in CRC encoder  Figure 10.16 Division in the CRC decoder for two cases 10.11 Task: 1. The message 11001001 is to be transmitted using CRC polynomial x 3 +1 protect it from errors. what is the message that should be transmitted? 2. Suppose we want to transmit the message 11001001 and protect it from errors using the CRC polynomial x+1. Use polynomial long division to determine the message that should be transmitted. Corrupt the left-most third bit of the transmitted message and show that the error is detected by the receiver using CRC technique. Table Standard polynomials Checksum In checksum error detection scheme, the data is initially divided into k segments each of m bits. In the sender’s end, the segments are added using 1’s complement arithmetic to get the sum. The sum is complemented to get the checksum. The checksum segment is sent along with the data segments. At the receiver’s end, all received segments are added using 1’s complement arithmetic to get the sum. The sum is complemented. If the result is zero, the received data is accepted; otherwise, it gets discarded.. Example  Forward Error Correction Forward Error Correction (FEC) is a technique used to minimize errors in data transmission over communication channels. In real-time multimedia transmission, re-transmission of corrupted and lost packets is not useful because it creates an unacceptable delay in reproducing : one needs to wait until the lost or corrupted packet is resent. Thus, there must be some technique which could correct the error or reproduce the packet immediately and give the receiver the ability to correct errors without needing a reverse channel to request re-transmission of data. Forward Error Correction Techniques Using Hamming Distance Chunk Interleaving Single-bit error correction To correct an error, the receiver reverses the value of the altered bit. To do so, it must know which bit is in error. Number of redundancy bits needed Let data bits = m Redundancy bits = r Total message sent = m+r The value of r must satisfy the following relation: 2r ≥ m+r+1 Error Correction Hamming Code HAMMING CODE : is constructed by adding a no. of parity bits to each group of n-bit information, or message in such a way so as to be able to locate the bit position in which error occurs. Values (0 or 1) are assigned to the parity bits so as to make the hamming code have either even parity or odd parity & when an error occurs, the position no. will take on the value assigned to the location of the erroneous bit. Hamming Code Hamming Codes Construction for 1-bit error-correcting codes Minimal number of check bits required Construction number bits from 1 upward powers of 2 are check bits all others are data bits Check bit j is XOR of all bits k such that (j AND k) = j Example: 4 bits of data, 3 check bits Hamming Codes: Example  Hamming Codes: Example For example A hamming code 0110001 is being received. Find the correct code which is being transmitted. SOLUTION: 001 010 011 100 101 110 111 1 2 3 4 5 6 7 P1 P2 D1 P3 D2 D3 D4 0 1 1 0 0 0 1 P1 = 1 , 3 , 5, 7 P2 = 2 , 3 ,6 , 7 P3 = 4 , 5 , 6 ,7 Checksum Bits: C1 = 0 C2 = 1 C3 = 1 In reverse order, 110. Therefore, error has occurred at position 6. Hence, the exact code transmitted is: 0110011. Chunk Interleaving Another way to achieve Forward Error Correction in multimedia is to allow some small chunks to be missing at the receiver. We cannot afford to let all the chunks belonging to the same packet be missing; however, we can afford to let one chunk be missing in each packet. We achieve this through chunk interleaving by producing interleaved code. Task 1. Assume the usage of Hamming Distance for Forward. Error Correction. Codebook agreed between the sender and receiver is given below: What is the dataword, if the codeword 11101 is received?