835-3291-1-PB | Error Detection And Correction

Please download to get full document.

View again

of 8
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Documents

Published:

Views: 4 | Pages: 8

Extension: PDF | Download: 0

Share
Related documents
Description
speech recognition in matlab
Transcript
  International Journal of Management & Information Systems  –   Second Quarter 2010 Volume 14, Number 2    105 Analysis Of The Effectiveness Of Error Detection In Data Transmission Using Polynomial Code Method Daniel N. Owunwanne, Howard University, USA ABSTRACT  Data transmitted from one location to the other has to be transferred reliably. Usually, error control coding algorithm provides the means to protect data from errors. Unfortunately, in many cases the physical link can not guarantee that all bits will be transferred without errors. It is then the responsibility of the error control algorithm to detect those errors and in some cases correct them so that upper layers will receive error free data. The polynomial code, also known as Cyclic  Redundancy Code (CRC) is a very powerful and easily implemented technique to obtain data reliability. As data transfer rates and the amount of data stored increase, the need for simple and robust error detection codes should increase as well. Thus, it is important to be sure that the CRCs in use are as effective as possible. Unfortunately, standardized CRC polynomials such as the CRC-32 polynomial used in the Ethernet network standard are known to be grossly suboptimal  for important applications, (Koopman, 2002). This research investigates the effectiveness of error detection methods in data transmission used several years ago when we had to do with small amount of data transfer and data storages compared with the huge amount of data we deal with nowadays. A demonstration of erroneous bits in data frames that may not be detected by the CRC method will be shown. A corrective method to detect errors when dealing with humongous data transmission will also be given. Keywords: Data Transmission, Error Detection, Polynomial Code, Cyclic Redundancy Code, CRC Method, Checksum 1. INTRODUCTION  he Cyclic Redundancy Code, or CRC, is a technique for detecting errors in digital data, but not for making corrections when errors are detected. It is used primarily in data transmission. In the CRC method, a certain number of check bits, often called a checksum, are appended to the message being transmitted. The receiver can determine whether or not the check bits agree with the data, to ascertain with a certain degree of probability if an error occurred or not in the transmission. If an error occurred, the receiver sends a “negative acknowledgement” (NAK) back to the sender, requesting that the message be retransmitted.  The technique is also sometimes applied to data storage devices, such as in a disk drive. In this situation each block on the disk would have check bits, and the hardware might automatically initiate a reread of the block when an error is detected, or it might report the error to software. The material that follows speaks in terms of a “sender” and a “receiver” of a “message,” but it should be understood that it applies to  storage writing and reading as well. The aim of an error detection technique is to enable the receiver of a message transmitted through a noisy (error-introducing) channel to determine whether the message has been corrupted. To do this, the transmitter constructs a checksum which is a function of the message, and appends it to the message. The receiver can then use the same function to calculate the checksum of the received message and compare it with the appended checksum to see if the message was correctly received. For example, if we chose a checksum function which was simply the sum T  International Journal of Management & Information Systems  –   Second Quarter 2010 Volume 14, Number 2    106 of the bytes (numbers) in the message modulo 256 i.e., 2 8  (8-bit register), then it might go as follows (all numbers are in decimal): Message: 6 23 4 Message with checksum: 6 23 4 33 Message after transmission: 6 27 4 33 In the above, the second byte of the transmitted message was corrupted from 23 to 27 by the communications channel. However, the receiver can detect this by comparing the transmitted checksum (33) with the computer checksum of 37 (6 + 27 + 4). If the checksum itself is corrupted, a correctly transmitted message might  be incorrectly identified as a corrupted one. However, this is a safe-side failure. A dangerous-side failure occurs where the message and/or checksum is corrupted in a manner that results in a transmission that is internally consistent. Unfortunately, this possibility is completely unavoidable and the best that can be done is to minimize its  probability by increasing the amount of information in the checksum, that is, by widening the checksum from one  byte to two bytes, (Williams, 1993). There are several techniques for generating check bits that can be added to a message. Perhaps the simplest is to append a single bit, called the “parity bit,” which makes the total number of 1 bits in the code vector (message with parity bit appended) even or odd. If a single bit gets altered in transmission, this will change the parity from even to odd (or vice versa). The sender generates the parity bit by simply summing the message bits in modulo 2 arithmetic, that is, by using  XOR   method  . It then appends the parity bit (or its complement) to the message. The receiver can check the message by summing all the message bits in modulo 2 and checking that the sum agrees with the parity bit. Equivalently, the receiver can sum all the bits (message and parity) and check that the result is 0 (if even parity is being used). This simple parity technique is often said to detect 1 bit error. Actually it detects errors in any odd number of bits, including the parity bit. The CRC algorithms were srcinally developed for detection of line transmission errors. They were designed to be fast and easy to implement in hardware. The selection of generator polynomial is the most important  part of implementing the CRC algorithm. The polynomial is chosen to maximize the error detecting capabilities (minimizing collision probability). The most important attribute of the polynomial is its length (the number of the highest nonzero coefficient), because of its direct influence of the length of the computed checksum. There are also communication standards approved by IEEE or ITU organizations, which define CRC  polynomials used in various communication protocols. When creating a new polynomial, the general advice is to use an irreducible polynomial, which means that the polynomial cannot be divided by any polynomial, except itself with zero reminder, (Petr Hlávka et al, 2005). 2. BACKGROUND  Cyclic Redundancy Codes (also known as Cyclic Redundancy Checks) have a long history of use for error detection in computing. W. Peterson (Peterson72) and Shu Lin (Lin83) as well as Andrew Tanenbaum (Tanenbaum2003) are among the commonly cited standard reference works in CRCs. Actually, CRCs can be used to detect medium induced errors in messages transferred over communication channels. They are also commonly used to protect the integrity of data stored in memory. In practice CRCs have been found to be an adequate protection mechanism for deployment in everyday communication systems for medium induced errors. But, this experience is insufficient to assure ultra-dependable operation (Paulitsch et al, 2005). A CRC can be thought of as a (non-secure) digest function for a data word that can be used to detect data corruption. Mathematically, a CRC can be described as treating a binary data word as a polynomial over GF(2), that is, with each polynomial coefficient being zero or one and performing polynomial division by a  generator  polynomial   G(x). CRC polynomials are also known as feedback polynomials which is in reference to the feedback taps of hardware-based shift register implementations. The remainder of that division operation provides an error detection value that is sent as a Frame Check Sequence (FCS) within a network message or stored as a data integrity check.  International Journal of Management & Information Systems  –   Second Quarter 2010 Volume 14, Number 2    107 Whether implemented in hardware or software, the CRC computation takes the form of a bitwise convolution of a data word against a binary version of the CRC polynomial, (Koopman, 2002). Error detection is  performed by comparing a FCS computed on a piece of retrieved or received data against the FCS value srcinally computed and either sent or stored with the srcinal data. An error is declared to have occurred if the stored FCS and computed FCS values are not equal. However, as with all digital signature schemes, there is a small, but finite,  probability that a data corruption that inverts a sufficient number of bits in just the right pattern will occur and lead to an undetectable error. The minimum number of bit inversions required to achieve such undetected errors - the Hamming Distance (HD) value is a central issue in the design of CRC polynomials. HD is discussed in the next section. The essence of implementing a good CRC-based error detection scheme is picking the right polynomial. The prime factorization of the generator polynomial brings with it certain potential characteristics, and in particular gives a tradeoff between maximum number of possible detected errors versus data word length for which the  polynomial is effective. Many polynomials are good for short words but poor at long words. There are relatively few  polynomials that are excellent for medium-length data words while still being good for relatively long data words. Unfortunately, prime factorization of a polynomial is not sufficient to determine the achieved HD value for any  particular message length. While many previous results for CRC effectiveness have been published, no previous work has attempted to achieve complete screening of all possible 32-bit polynomials. 3. HAMMING DISTANCE   The Hamming Distance (HD) between two strings or codewords of equal length is the number of positions for which the corresponding symbols are different. That is, it measures the minimum number of substitutions required to change one into the other, or the number of errors  that transformed one string into the other. Another way to define HD is that, it is the number of bit positions in which two codewords differ. See the following examples: Codeword1   Codeword2   HD  i. 1011101  and 1001001  is 2. ii. 2173896  and 2233796  is 3. iii. toned  and roses  is 3. This is a cube HD: 110 111 010 011 100 101 000 001 Figure 1: Determining Hamming Distance As seen in Figure 1 above, following the red path, from 100 to 011, it has distance 3. This is quite obvious if you count the total number of the paths. Also, following the blue path, from 010 to 111, the distance is 2.  International Journal of Management & Information Systems  –   Second Quarter 2010 Volume 14, Number 2    108 The following C++ code computes the Hamming Distance (HD) between two strings of equal distance. const int m, n; int Hd; char S1[m]; char S2[n]; --- if (m == n) { for (int i = 0; i < m; i ++) { if (S1[i] != S2[i]) Hd += 1; sum = Hd; } return sum; } The significance of HD is that if two codewords are a Hamming distance d   apart, it will require d   single-bit errors to convert one into the other. The error detecting properties of a code depend on its Hamming distance  because to detect d errors, you need a distance of d+1 code. 4. POLYNOMIAL CODES IN DETECTING ERRORS   In data transmission, a simplex channel is not preferred if an error is detected, but most often, error detection followed by retransmission is preferred because it is more efficient to handle. A polynomial code is a widespread means of detecting errors in data transmission. Polynomial coding treats each message as a polynomial equation with each bit in the message representing a coefficient in the equation. Polynomial codes are based on treating bit strings as representations of polynomial with coefficients of 0 and 1 only. For instance, a k-bit frame is regarded as the coefficient list for a polynomial with k terms, ranging from x k-1 to x 0 . Such a polynomial is said to  be of degree k  –   1. The higher order (leftmost) bit is the coefficient of x k-1 ; the next bit is the coefficient of x k-2 , and so on. For example, 110001 has 6 bits and thus represents a six term polynomial with coefficients 1, 1, 0, 0, 0, and 1 as x 5  + x 4  + x 0 . When the polynomial code method is used, the sender and the receiver must agree upon a generator polynomial  , G( x  )  in advance, (Tanenbaum, 1989). Both the high order and low order bits of the generator must be 1. To compute the checksum for some frames with m   bits, corresponding to the polynomial M( x  ),  the frame must be longer than the generator polynomial, G( x  ). The basic idea is to append a checksum to the end of the frame in such a way that the polynomial represented by the checksummed frame is divisible by G( x  ).  If there is a remainder, there has been a transmission error, otherwise, there is no error if there is no remainder. The following algorithm was used in Andrew Tanenbaum’s book (Tanenbaum, 2003) in computing the checksum: a. Let  r  be the degree of G(x). Append r zero bits to the low order end of the frame so that it now contains m + r bits, which corresponds to the polynomial  x r   M(x).   b. Divide the bit string corresponding to G(x) into the bit string corresponding to  x r   M(x) using modulo 2 division arithmetic. c. Subtract the remainder (which is always r   or fewer bits) from the bit string corresponding to  x r   M(x) using modulo 2 subtraction arithmetic. The result is the checksummed frame to be transmitted, called T(x). For example, calculate the checksum of this frame: 1101011011 with G(x) = x 4  + x + 1.
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks