Computer Networks and Data Communication-LEC6 PDF

Chapter 10 Error Detection and Correction Types of Errors Detection Correction  Basic concepts  Networks must be able to transfer data from one device to another with complete accuracy.  Data can be corrupted during transmission.  For reliable communicat...

Chapter 10 Error Detection and Correction Types of Errors Detection Correction  Basic concepts  Networks must be able to transfer data from one device to another with complete accuracy.  Data can be corrupted during transmission.  For reliable communication, errors must be detected and corrected.  Error detection and correction are implemented either at the data link layer or the transport layer of the OSI model. Types of Errors Single-bit error  Single bit errors are the least likely type of errors in serial data transmission because the noise must have a very short duration which is very rare. However this kind of errors can happen in parallel transmission. Example: If data is sent at 1Mbps then each bit lasts only 1/1,000,000 sec. or 1 μs. For a single-bit error to occur, the noise must have a duration of only 1 μs, which is very rare.  Note A burst error means that 2 or more bits in the data unit have changed. 10.6 The term burst error means that two or more bits in the data unit have changed from 1 to 0 or from 0 to 1. Burst errors does not necessarily mean that the errors occur in consecutive bits, the length of the burst is measured from the first corrupted bit to the last corrupted bit. Some bits in between may not have been corrupted. Burst error is most likely to happen in serial transmission since the duration of noise is normally longer than the duration of a bit. The number of bits affected depends on the data rate and duration of noise.  Figure 10.2 Burst error of length 8 10.9  Note To detect or correct errors, we need to send extra (redundant) bits with data. 10.10  Redundancy Error detection uses the concept of redundancy, which means adding extra bits for detecting errors at the destination. These redundant bits are added by the sender and removed by the receiver. Their presence allows the receiver to detect or correct corrupted bits.  Detection Versus Correction In Error detection, we are looking only to see if any error has occurred. The answer is a simple yes or no. We are not even interested in the number of errors. A single-bit error is the same for us as a burst error.  Detection Versus Correction In error correction, we need to know the exact number of bits that are corrupted and more importantly, their location in the message. The number of the errors and the size of the message are important factors. If we need to correct one single error in an 8-bit data unit, we need to consider eight possible error locations; if we need to correct two errors in a data unit of the same size, we need to consider 28 possibilities. You can imagine the receiver's difficulty in finding 10 errors in a data unit of 1000 bits.  Forward Error Correction Versus Retransmission Forward error correction is the process in which the receiver tries to guess the message by using redundant bits. This is possible, as we see later, if the number of errors is small. Correction by retransmission is a technique in which the receiver detects the occurrence of an error and asks the sender to resend the message. Resending is repeated until a message arrives that the receiver believes is error-free (usually, not all errors can be detected)  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 or correct the errors. The ratio of redundant bits to the data bits and the robustness of the process are important factors in any coding scheme. Figure 10.3 shows the general idea of coding  Figure 10.3 The structure of encoder and decoder 10.16 Four types of redundancy checks are used in data communications  Performance It can detect single bit error It can detect burst errors only if the total number of errors is odd. Longitudinal Redundancy Check LRC(2-D parity check)  Performance Advantage LCR increases the likelihood of detecting burst errors. Disadvantage:  If two bits in one data units are damaged and two bits in exactly the same positions in another data unit are also damaged, the LRC checker will not detect an error. VRC and LRC Example step1 add L-1 0 to data Use XoR for division Append the reminder to message that will be transmit Cyclic Redundancy Check CRC  Cyclic Redundancy Check Given a k-bit frame or message, the transmitter generates an n-bit sequence, known as a frame check sequence (FCS), so that the resulting frame, consisting of (k+n) bits, is exactly divisible by some predetermined number. The receiver then divides the incoming frame by the same number and, if there is no remainder, assumes that there was no error. Binary Division Polynomial Polynomial and Divisor Standard Polynomials  At the sender The unit is divided into k sections, each of n bits. All sections are added together The sum is one’s complement and becomes the checksum. The checksum is sent with the data 1. Divide the data to 4 blocks 2. Add the four blocks 3. Add the carry to the data 4. one’s complement of the sum 5. Apend the CHEKSUM to the data  At the receiver The unit is divided into k sections, each of n bits. All sections are added together using one’s complement to get the sum. The sum is complemented. If the result is zero, the data are accepted: otherwise, they are rejected. Checksum  Performance The checksum detects all errors involving an odd number of bits. It detects most errors involving an even number of bits. If 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, the sums of those columns will not change and the receiver will not detect a problem.  Error Correction It can be handled in two ways: 1) receiver can have the sender retransmit the entire data unit. 2) The receiver can use an error-correcting code, which automatically corrects certain errors. 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  Example If we need to send data 1011  Data will sent P1=1, p2=0, and p4=0 Hamming Code Hamming Code Hamming Code Example of Hamming Code Single-bit error Error Detection  https://www.youtube.com/watch?v=A9g6rT Mblz4 https://www.youtube.com/watch?v=AtVWn yDDaDI