Error Detection and Error Correction

Error detection just identifies that a bit (or bits) has been received in error. Error correction corrects errors at a far-end receiver. Both require a certain amount of redundancy to carry out the respective function. Redundancy, in this context, means those added bits or symbols that carry out no other function than as an aid in the error-detection or error-correction process.

One of the earliest methods of error detection was the parity check. With the 7-bit ASCII code, a bit was added for parity, making it an 8-bit code. This is character parity. It is also referred to as vertical redundancy checking (VRC).

We speak of even parity and odd parity. One system or the other may be used. Either system is based on the number of marks or 1s in a 7-bit character, and the eighth bit is appended accordingly, either a 0 or a 1. Let us assume even parity and we transmit the ASCII bit sequence 1010010. There are three 1s, an odd number. Thus a 1 is appended as the eighth bit to make it an even number.

Suppose we use odd parity and transmit the same character. There is an odd number of 1s (marks), so we append a 0 to leave the total number of 1s an odd number. With odd parity, try 1000111. If you added a 1 as the eighth bit, you'd be correct.

Character parity has the weakness that a lot of errors can go undetected. Suppose two bits are changed in various combinations and locations. Suppose a 10 became a 01; a 0 became a 1, and a 1 became a 0; and two 1s became two 0s. All would get by the system undetected.

To strengthen this type of parity checking, the longitudinal redundancy check (LRC) was included as well as the VRC. This is a summing of the 1s in a vertical column of all characters, including the 1s or 0s in each eighth bit location. The sum is now appended at the end of a message frame or packet. Earlier this bit sequence representing the sum was called the block check count (BCC). Today it may consist of two or four 8-bit sequences and we call it the FCS (frame check sequence), or sometimes the CRC (cyclic redundancy check). At the distant-end receiver, the same addition is carried out and if the sum agrees with the value received, the block is accepted as error-free. If not, it then contains at least one bit error, and a request is sent to the transmit end to retransmit the block (or frame).

Even with the addition of LRC, errors can slip through. In fact, no error-detection system is completely foolproof. There is another method, though, that has superior error detection properties. This is the CRC. It comes in a number of varieties. Cyclic Redundancy Check (CRC). In very simple terms the CRC error detection technique works as follows: A data block or frame is placed in memory. We can call the frame a k-bit sequence and it can be represented by a polynomial which is called G(x). Various modulo-2 arithmetic operations are carried out on G(x) and the result is divided by a known generator polynomial called P(x).3 This results in a quotient Q(x) and a remainder R(x). The remainder is appended to the frame as an FCS, and the total frame with FCS is transmitted to the distant-end receiver where the frame is stored, then divided by the same generating polynomial P(x). The calculated remainder is compared to the received remainder (i.e., the FCS). If the values are the same, the frame is error-free. If they are not, there is at least one bit in error in the frame.

For many WAN applications the FCS is 16 bits long; on LANs it is often 32 bits long. Generally speaking, the greater the number of bits, the more powerful the CRC is for catching errors.

The following are two common generating polynomials:

producing a 16-bit FCS.

CRC-16 provides error detection of error bursts up to 16 bits in length. Additionally, 99.955% of error bursts greater than 16 bits can be detected (Ref.4). Forward-Acting Error Correction (FEC). Forward-acting error correction (FEC) uses certain binary codes that are designed to be self-correcting for errors introduced by the intervening transmission media. In this form of error correction the receiving station has the ability to reconstitute messages containing errors.

The codes used in FEC can be divided into two broad classes: (1) block codes and (2) convolutional codes. In block codes information bits are taken k at a time, and c parity bits are added, checking combinations of the k information bits. A block consists of n = k + c digits. When used for the transmission of data, block codes may be systematic. A systematic code is one in which the information bits occupy the first k positions in a block and are followed by the (n — k) check digits.

A convolution(al) code is another form of coding used for error correction. As the word "convolution" implies, this is one code wrapped around or convoluted on another. It is the convolution of an input-data stream and the response function of an encoder. The encoder is usually made up of shift registers. Modulo-2 adders3 are used to form check

3Note that modulo-2 addition is the same as binary addition but without the "carry," or 1 + 1 = 0 and we do not carry the 1. Summing 10011 and 11001 in modulo-2, we get 01010.

digits, each of which is a binary function of a particular subset of the information digits in the shift register. Error Correction with a Feedback Channel. Two-way or feedback error correction is used widely today on data circuits. Such a form of error correction is called ARQ. The letter sequence ARQ derives from the old Morse and telegraph signal, "automatic repeat request." There are three varieties of ARQ:

1. Stop-and-wait ARQ

2. Selective or continuous ARQ

Stop-and-wait ARQ is simple to implement and may be the most economic in the short run. It works on a frame-by-frame basis. A frame is generated; it goes through CRC processing and an FCS is appended. It is transmitted to the distant end, where the frame runs through CRC processing. If no errors are found, an acknowledgment signal (ACK) is sent to the transmitter, which now proceeds to send the next frame—and so forth. If a bit error is found, a negative acknowledgment (NACK) is sent to the transmitter, which then proceeds to repeat that frame. It is the waiting time of the transmitter as it waits for either acknowledgment or negative acknowledgment signals. Many point to this wait time as wasted time. It could be costly on high-speed circuits. However, the control software is simple and the storage requirements are minimal (i.e., only one frame).

Selective ARQ, sometimes called continuous ARQ, eliminates the waiting. The transmit side pours out a continuous stream of contiguous frames. The receive side stores and CRC processes as before, but it is processing a continuous stream of frames. When a frame is found in error, it informs the transmit side on the return channel. The transmit side then picks that frame out of storage and places it in the transmission queue. Several points become obvious to the reader. First, there must be some way to identify frames. Second, there must be a better way to acknowledge or "negative-acknowledge." The two problems are combined and solved by the use of send sequence numbers and receive sequence numbers. The header of a frame has bit positions for a send sequence number and a receive sequence number. The send sequence number is inserted by the transmit side, whereas the receive sequence number is inserted by the receive side. The receive sequence numbers forwarded back to the transmit side are the send sequence numbers of frames acknowledged by the receive side. When the receive side detects an errored frame, it repeats the send sequence number of the frame in error. Of course, the receiver side has to put the corrected frame back in its proper sequence before the frame can go onwards to the end user.

Continuous or selective ARQ is more costly in the short run, compared with stop-and-wait ARQ. It requires more complex software and notably more storage on both sides of the link. However, there are no gaps in transmission and no time is wasted waiting for the ACK or NACK.

Go-back-n ARQ is a compromise. In this case, the receiver does not have to insert the corrected frame in its proper sequence, thus less storage is required. It works this way: When a frame is received in error, the receiver informs the transmitter to "go-back-n," n being the number of frames back to where the errored frame was. The transmitter then repeats all n frames, from the errored frame forward. Meanwhile, the receiver has thrown out all frames from the errored frame forward. It replaces this group with the new set of n frames it received, all in proper order.

Was this article helpful?

0 0

Post a comment