ITT400 Ch6 Error Detection and Correction PDF

ITT400 Introduction To Data Communication and Networking Chapter 6 Error Detection and Correction Mazlan Osman, FSKM, UiTM (Terengganu) 2014  8-1 INTRODUCTION Network must be able to transfer data with complete...

ITT400 Introduction To Data Communication and Networking Chapter 6 Error Detection and Correction Mazlan Osman, FSKM, UiTM (Terengganu) 2014  8-1 INTRODUCTION Network must be able to transfer data with complete accuracy. But data can be corrupted during transmission. Some mechanism required to detect and correct errors. 8.2  TYPES OF ERROR Single-Bit Error Only 1 bit in the data unit has changed from 1 to 0 or from 0 to 1. Figure 8.1 Single-bit error 8.3  Burst Error 2 or more bits in the data unit have changed from 1 to 0 or from 0 to 1 8.4 Figure 8.2 Burst error of length 8  REDUNDANCY CONCEPT Redundancy concept – adding extra bits to original data by the sender in order to detect or correct errors. DETECTION VS CORRECTION In error detection, just to see if any error has occurred. Numbers of error is not important While in error correction, need to know the exact number of bits that are corrupted. Number of the errors are important 8.5  MODULAR-2 ARITHMETIC Use XOR (exclusive OR) operation for both addition and subtraction. Adding : 0+0=0 0+1=1 1+0=1 1+1=0 Subtracting : 0 – 0 = 0 0–1=1 1–0=1 1–1=0 8.6 Figure 8.4 XORing of two single bits or two words  HAMMING DISTANCE The Hamming distance between two words (of the same size) is the number of differences between corresponding bits. Example 8.4 Let us find the Hamming distance between two pairs of words. 1. The Hamming distance d(000, 011) is 2 because 1. The Hamming distance d(10101, 11110) is 3 because What is minimum Hamming distance? (reading yourself). 8.7  8-2 BLOCK CODING 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. Figure 8.5 Datawords and codewords in block coding 8.8  ERROR DETECTION Figure 8.6 Process of error detection in block coding 8.9  8-3 LINEAR BLOCK CODES Almost all block codes used today belong to a subset called linear block codes. In a linear block code, the exclusive OR (XOR) of any two valid codewords creates another valid codeword. 8.10  Figure 8.10 Encoder and decoder for simple parity-check code 8.11  TYPES OF LINEAR BLOCK CODES Simple Parity-Check Code A simple parity-check code is a single-bit error- detecting code in which n = k + 1 with dmin = 2 The extra bit, called the parity bit, is selected to make the total number of 1s in the codeword even or odd. A simple parity-check code can detect either an even or odd number of errors 8.12  Example 8.2 Let us assume that k = 2 and n = 3. Table 8.1 shows the list of datawords and codewords. Later, we will see how to derive a codeword from a dataword Datawords Codewords 00 000 01 011 Table 8.1 A code C(3,2) 10 101 for error detection 11 110 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 syndrome is 0. The receiver extracts the dataword 01 from it 2.The codeword is corrupted during transmission, and 111 is received. The syndrome is 1. 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. It means burst error can not be detected. 8.13  Table 10.3 Simple parity-check code C(5, 4) 10.14  Example 8.12 This example refer to Table 10.3. 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 a1. The received codeword is 10011. The syndrome is 1. No dataword is created. 3. One single-bit error changes r0. The received codeword is 10110. The syndrome is 1. No dataword is created 4. An error changes r0 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, a2, and a1—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 and also find any odd number of errors 8.15  A better approach is the two-dimensional parity check A block of bits is organized in a table (rows and columns). At first, the parity bit is calculated for each data unit. Second, the parity bit is organized into a table. This method increases the likelihood of detecting burst errors. 8.16 8.17 Figure 8.11 Two-dimensional parity-check code  Hamming Codes Originally designed with dmin = 3, which means that they can detect up to two errors or correct one single error The relationship between m and n in these codes is n = 2m − 1 and k = n – m. the number of check bits r = m. For example, if m = 3, then n = 7 and k = 4. This is Hamming code C(7,4) with dmin = 3 8.18 Table 8.4 Hamming code C(7, 4)  Figure 8.12 The structure of the encoder and decoder for a Hamming code 8.19  Table 8.5 Logical decision made by the correction logic analyzer Example 8.13 Let us trace the path of three datawords from the sender to the destination: 1. The dataword 0100 becomes the codeword 0100011. The codeword 0100011 is received. The syndrome is 000, the final dataword is 0100. 2. The dataword 0111 becomes the codeword 0011001. The syndrome is 011. After flipping b2 (changing the 0 to 1), the final dataword is 0111. 3. The dataword 1101 becomes the codeword 1101000. The syndrome is 101. After flipping b0, we get 1100, the wrong dataword. This shows that our code cannot correct two errors 8.20  8-4 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. 8.21  CYCLIC REDUNDANCY CHECK Used in networks such as LANs and WANs Table 8.6 A CRC code with C(7, 4) 8.22  Figure 8.14 CRC encoder and decoder 8.23  Encoder Figure 8.15 Division in CRC encoder 8.24  Decoder 1011 Figure 8.16 Division in the CRC decoder for two cases 8.25  Advantages CRC can detect all burst errors that affect an odd number of bits CRC can detect all burst errors of length less than or equal to the degree of the polynomial 1000 = X^3 1010 = X^3 + X 8.26  8-5 CHECKSUM The checksum is used in the Internet by several protocols although not at the data link layer. Like linear and cyclic codes, the checksum is based on the concept of redundancy 8.27  ONE’S COMPLEMENT Example 8.20 How can we represent the number 21 in one’s complement arithmetic using only four bits? Solution The number 21 in binary is 10101 (it needs five bits). We can wrap the leftmost bit and add it to the four rightmost bits. We have (0101 + 1) = 0110 or 6 Example 8.21 How can we represent the number −6 in one’s complement arithmetic using only four bits? Solution In one’s complement arithmetic, the negative or complement of a number is found by inverting all bits. Positive 6 is 0110; negative 6 is 1001. If we consider only unsigned numbers, this is 9. In other words, the complement of 6 is 9. Another way to find the complement of a number in one’s complement arithmetic is to subtract the number from 2n − 1 (16 − 1 in this case). 8.28  1111 1001 0000 Figure 8.24 Example 8.22 8.29  INTERNET CHECKSUM Sender site: 1. The message is divided into 16-bit words. 2. The value of the checksum word is set to 0. 3. All words including the checksum are added using one’s complement addition. 4. The sum is complemented and becomes the checksum. 5. The checksum is sent with the data. Receiver site: 1. The message (including checksum) is divided into 16-bit words. 2. All words are added using one’s complement addition. 3. The sum is complemented and becomes the new checksum. 4. If the value of checksum is 0, the message is accepted; otherwise, it is rejected. 8.30  Example 8.23 Let us calculate the checksum for a text of 8 characters (“Forouzan”). The text needs to be divided into 2-byte (16-bit) words. We use ASCII (see Appendix A) to change each byte to a 2-digit hexadecimal number. For example, F is represented as 0x46 and o is represented as 0x6F. Figure 8.25 shows how the checksum is calculated at the sender and receiver sites. In part a of the figure, the value of partial sum for the first column is 0x36. We keep the rightmost digit (6) and insert the leftmost digit (3) as the carry in the second column. The process is repeated for each column. Note that if there is any corruption, the checksum recalculated by the receiver is not all 0s. We leave this an exercise. 8.31  Figure 8.25 Example 8.23 8.32  Advantages Vs Disadvantage Advantages Checksum can detects all errors involving an odd number of bits as well as most errors involving an even number of bits Disadvantages The checksum cannot detect errors when one or more bits of a segment are damaged and the corresponding bit or bits of opposite value in a second segment are also damaged 8.33