Module-III(1).pdf

Data Communications and Computer Networks Assistant Professor Department of Computer Science & Engineering IIIT Naya Raipur  Module III Data Link Layer Introduction The data link layer is the second layer from the bottom in the OSI (Open System I...

Data Communications and Computer Networks Assistant Professor Department of Computer Science & Engineering IIIT Naya Raipur  Module III Data Link Layer Introduction The data link layer is the second layer from the bottom in the OSI (Open System Interconnection) network architecture model. It is responsible for the node-to-node delivery of data. Its major role is to e n s u re e r ror - f re e t ra nsm i s s i on of information. DLL is also responsible for encoding, decode and organizing the outgoing and incoming data. Error Detection and Correction Types of Errors Redundancy Detection Vs Correction In case of error detection one has to check whether an error has occurred or not the answer lies in a yes or no. Whereas in case of error correction one needs to know the number of errors, location of errors, location from which the message has been received and also the error has to be fixed. Forward error correction Vs Retransmission Modular arithmetic Coding Redundancy is achieved through various coding schemes. The sender adds redundant bits through a process that creates a relationship between the redundant bits and the actual data bits. The receiver checks the relationships between the two sets of bits to detect errors. The ratio of redundant bits to data bits and the robustness of the process are important factors in any coding scheme. Coding schemes divided into two broad categories: Block coding and convolution coding. Block coding In case of block coding message is divided 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 The detec t ion of the error through the block coding can be done if and only if the following conditions can be achieved-: The receiver is able to find the list of all the valid code word. The original code word has been converted to an invalid code word. Process of error detection in block coding  Example Let us assume that k = 2 and n = 3. Table shows the list of datawords and codewords. Assume the sender encodes the dataword 01 as 011 and sends it to the receiver. Consider the following cases: 1. The receiver receives 011. It is a valid codeword. The receiver extracts the dataword 01 from it. 2.The codeword is corrupted during transmission, and 111 is received. This is not a valid codeword and is discarded. 3.The codeword is corrupted during transmission, and 000 is received. This is a valid codeword. The receiver incorrectly extracts the dataword 00. Two corrupted bits have made the error undetectable. 10.26  Note An error-detecting code can detect only the types of errors for which it is designed; other types of errors may remain undetected. Hamming Distance One of the central concepts in coding for error control is the idea of the Hamming dis. tance. The Hamming distance between two words (of the same size) is the number of differences between the corresponding bits. Hamming distance between two words x and y is shown by as d(x, y). Hamming distance between the received codeword and the sent codeword is the number of bits that are corrupted during transmission. For example, if the codeword 00000 is sent and 01101 is received, 3 bits are in error and the Hamming distance between the two is d(00000, 01101) = 3. In other words, if the Hamming distance between the sent and the received codeword is not zero, the codeword has been corrupted during transmission. The Hamming distance can easily be found if we apply the XOR operation on the two words and count the number of Is in the result. Note that the Hamming distance is a value greater than 10.o2r8equal to zero. Example Let us find the Hamming distance between two pairs of words. 1. The Hamming distance d(000, 011) is 2 because 2. The Hamming distance d(10101, 11110) is 3 because  Note 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. Linear Block Code 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 The scheme in Table (previous example) is a linear block code because the result of XORing any codeword with any other codeword is a valid codeword. For example, the XORing of the second and third codewords creates the fourth one. 10.31 Parity Check Code In this code, a k-bit dataword is changed to an -bit codeword where n = k + 1. The extra bit, called the parity bit, is selected to make the total number of 1s in the codeword even. The minimum Hamming distance for this category is dmin = 2, which means that the code is a single-bit error-detecting code. Our first code (Example Table) is a parity-check code (k = 2 and n = 3). A simple parity-check code is a single-bit error-detecting code in which n = k + 1 with dmin = 2. 10.32  Figure Encoder and decoder for simple parity-check code 10.33 Table Simple parity-check code C(5, 4) Task: 1. What is the Hamming distance for each of the following codewords? a. d (10000, 00000) b. d (10101, 10000) c. d (00000, 11111) d. d (00000, 00000) 2. Prove that the code represented by the following codewords is not linear. You need to find only one case that violates the linearity. ((00000), (01011), (10111), (11111)] 3. Assuming even parity, find the parity bit for each of the following data units. a. 1001011 b. 0001100 c. 1000000 d. 1110111