Error detection and correction
The error caused by the physical process is usually burst in some media rather than a single. Network designers have studied two basic strategies to handle errors. One method is to attach enough redundant information on each data block to be sent to enable the recipient to derive what the characters have been issued. Another method is to only add enough redundant bits, so that the recipient knows the error, but I don't know what error, and then ask the recipient to re-transfer. The former's strategy is to use the error-correcting code, while the latter uses an error-detecting code.
Error correction code
Before you understand the error correction code, you know a basic concept: Have a distance. Usually one frame includes M data (packet) bits and R redundant bits or check digits. When the entire length is N (ie n = m r), the unit of this length is normally referred to as N-bit Codeword.
Any two codewords are given, such as 10001001 and 10110001, you can determine how many of them are different. There are 3 digits in this example. In order to determine how many bits are different, only two codewords are different or calculated, and then the number of 1 in the results is calculated. The number of different bits in the two codewords is called Hamming Distance. Its importance is that if the two codewords have sea Distance D, D bit error is required to convert one of the codewords into another.
A coded calibration and error correction capability depends on its sea distance. To detect D bit error, you need to use D 1 encoding; because D single bits are not possible to convert an effective codeword into another valid codeword. When the recipient sees invalid codeword, it is modified to understand the transmission error. Similarly, in order to correct the D bit error, you must use a distance of 2D 1. This is because the distance of the effective codeword is far to even if D changes, this changed codeword is still close to the original code than other codes. word. As a simple example of the error correction code, consider only 4 effective codeword code:
0000000000, 200011111, 11111100000 and 1111111111
The distance between this code is 5, that is, it can correct double bit error. If the codeword 000000111 arrives, the receiver knows that the original codeword should be 000011111. However, if there is a three-bit fault, the 0000000000 becomes 0000000111, the error will not correct correctly.
2. Error code
The error detection code is sometimes used for data transmission. For example, when the channel is a single mode, most of the way mostly adopts the error detection code.
Suppose the error of the channel is isolated, the bit error rate of the channel is 10-6 per person. The size of the data block is 100. For a 1000-bit data block error correction, 10 calibration blocks are required; 1 megabytes will take 10,000 checklocks. If you only need to detect one error of a data block, it is enough for each odd bit. An additional data block is required for each delivery of 1000 data blocks. Error error detection retransmission method's entire overhead, only 2001 per megabytes, and Haiming code is 10,000.
If only one parity is added on one block, the detection rate of the long burst error of the block will be very bad, and the probability of error can be detected is only 0.5, which is unacceptable. Improved measures can be transmitted to form a rectangular matrix that makes each data block in the N-bit wide K row. The parity bits of each column are calculated, respectively, on the matrix, as the last row of the matrix, and then transmitted by row. When the block arrives, the recipient detects all the parity bits. If any of these errors, you need to re-transfer the entire block.
This method can detect a burst error of a single degree of N, because there is only one change in each column. However, if the first bit changes, the last bit is reversed, and all other bits are correct, and the burst error of the length N 1 will not be detected. If a block is broken by a long burst or short burst error, the parity value of each column in the n column happens to be 0.5, then the probability of this error block should not be 2-n. Although the above method is sometimes sufficient, in practice, another method is being widely used, ie polynomial encoding (also called cycle redundancy, or CRC code). Polynomial coding is based on a polynomial of the bit string as a coefficient of 0 or 1, and a k-bit frame can be regarded as a coefficient sequence from the K-1 multiplicity of XK-1 to X0. If a polynomial encoding is employed, the sender and the receiver must agree to generate a polynomial G (X) in advance, and the high and low position of the generated polynomial must be 1. To calculate the checksum of the frame M (x) of the M bit, the generation polynomial must be shorter than this polynomial. Basic ideas are: the calibration and adding the frame of the frame, so that the polynomial of the frame of the checksum can be removed by G (x). When the recipient receives a frame with a verification and a g (x), it is removed if there is a remainder, then the error is transmitted.
The algorithm for calculating the checksum is as follows:
1. G (x) is a R-order, and R zo is attached at the end of the frame, so that the frame is m R bit, the corresponding polynomial is XRM (X).
2. The bit string corresponding to the XRM (X) is removed by a bit string corresponding to the G (X) in addition to the method.
3. The remainder is subtracted from a bit string corresponding to XRM (X) in a bit string of XRM (X). The result is the frame to convey the frame, called polynomial T (x).
The following three polynomials have become an international standard:
CRC -12 = x ^ 12 x ^ 11 x ^ 3 x ^ 2 x 1 CRC -16 = x ^ 16 x ^ 15 x ^ 2 1 crc -citt = x ^ 16 x ^ 12 x ^ 5 1
These three polynomials contain x 1 as a basic factor. When the string length is 6 bits, use CRC-12; the remaining two polytes are used in the case where the string length is 8 bits. A 16-bit checksum, such as CRC-16 or CRC-CCIT, can capture all unit errors and dual error, all the errors of all odd digits, all lengths of sudden errors, 99.997% The length of 17 bits of burst errors, and 99.998% length of 18 or more burst errors.
Although the calculation method of calculating the checksum looks quite complex, Peterson and Brown have given a simple shift register circuit for calculation, and use hardware to complete the checksum. In practical applications, this hardware is almost used.
