5.3 ERROR CORRECTION

< Day Day Up >

If the error rate is high in transmission media such as satellite channels, error- correcting codes are used that have the capability to correct errors. Error correcting codes introduce additional bits, resulting in higher data rate and bandwidth requirements. However, the advantage is that retransmissions can be reduced. Error correcting codes are also called forward-acting error correction (FEC) codes.

Convolutional codes are widely used as error correction codes. The procedure for convolutional coding is shown in Figure 5.3. The convolutional coder takes a block of information (of n bits) and generates some additional bits (k bits). The additional k bits are derived from the information bits. The output is (n + k) bits. The additional k bits can be used to correct the errors that occurred in the original n bits. n/(n+k) is called rate of the code. For instance, if 2 bits are sent for every 1 information bit, the rate is 1/2. Then the coding technique is called Rate 1/2 FEC. If 3 bits are sent for every 2 information bits, the coding technique is called Rate 2/3 FEC. The additional bits are derived from the information bits, and hence redundancy is introduced in the error correcting codes.

click to expand
Figure 5.3: Convolutional coder.

For example, in many radio systems, error rate is very high, and so FEC is used. In Bluetooth radio systems, Rate 1/3 FEC is used. In this scheme, each bit is transmitted three times. To transmit bits b0b1b2b3, the actual bits transmitted using Rate 1/3 FEC are

 b0b0b0b1b1b1b2b2b2b3b3b3

At the receiver, error correction is possible. If the received bit stream is

 101000111000111

it is very easy for the receiver to know that the second bit is received in error, and it can be corrected.

In error correcting codes such as convolutional codes, in addition to the information bits, additional redundant bits are transmitted that can be used for error correction at the receiving end. Error correcting codes increase the bandwidth requirement, but they are useful in noisy channels.

A number of FEC coding schemes have been proposed that increase the delay in processing and also the bandwidth requirement but help in error correction. Shannon laid the foundation for channel coding, and during the last five decades, hundreds of error-correcting codes have been developed.

Note

It needs to be noted that in source coding techniques, removing the redundancy in the signal reduces the data rate. For instance, in voice coding, low-bit rate coding techniques reduce the redundancy. In contrast, in error correcting codes, redundancy is introduced to facilitate error correction at the receiver.

Summary

In a communication system, transmission impairments cause errors. In many data applications, errors cannot be tolerated, and error detection and correction are required. Error detection techniques use parity, checksum, or cyclic redundancy check (CRC). Additional bits are added to the information bit stream at the transmitting end. At the receiving end, the additional bits are used to check whether the information bits are received correctly or not. CRC is the most effective way of detecting errors and is used extensively in data communication. If the receiver detects that there are errors in the received bit stream, the receiver will ask the sender to retransmit the data.

Error correction techniques add additional redundancy bits to the information bits so that at the receiver, the errors can be corrected. Error correcting codes increase the data rate and hence the bandwidth requirement, but they are needed if the channel is noisy and if retransmissions have to be avoided.

References

Dreamtech Software Team. Programming for Embedded Systems. Wiley-Dreamtech India Pvt. Ltd., 2002. This book contains the source code for calculation of CRC as well as serial programming.
J. Campbell. C Programmer's Guide to Serial Communications. Prentice-Hall Inc., 1994.

Questions

Explain the need for error detection and correction.
What is parity? Explain with examples.
What is checksum? Explain with an example.
What is CRC? What are the different standards for CRC calculation?
Explain the principles of error correcting codes with an example.

Exercises

1.	Connect two PCs using an RS232 cable. Using serial communication software, experiment with parity bits by setting even parity and odd parity.
2.	"Parity can detect errors only if there is an odd number of errors". Prove this statement with an example.
3.	Calculate the even parity bit and the odd parity bit if the information bits are 1101101.
4.	If the information bits are 110110110, what will be the bit stream when Rate 1/3 FEC is used for error correction? Explain how errors are corrected using the received bit stream. What will be the impact of bit errors introduced in the channel?

Answers

1.	You can experiment with various parameters for serial communication using the Hyper Terminal program on Windows. You need to connect two PCs using an RS232 cable. Figure C.4 shows the screenshot to set the serial communication parameters. Figure C.4: Screenshot to set the serial communication parameters. To get this screen, you need do the following: Click on Start Go to Programs Go to Accessories Go to Hyper Terminal Double click on `HYPERTERM.EXE` Enter a name for New Connection "xxxx" and Click OK You will get a screen with the title Connect To. Select COM1 or COM2 from the Connect Using listbox and click OK.
2.	"Parity can detect errors only if there are odd number of errors". To prove this statement, consider the bit stream 1010101. If we add an even parity bit, the bit stream would be 10101010. If there is one error, the bit stream may become 11101010. Now the number of ones is 5, but the parity bit is 0. Hence, you can detect that there is an error. If there are two errors, the corrupted bit stream is 11111010. However, in this case, the calculated parity bit is 0, the received parity bit is also 0, and the even number of errors cannot be detected.
3.	If the information bits are 1101101, the even parity bit is 1, and the odd parity bit is 0.
4.	If the information bits are 110110110, when Rate 1/3 FEC is used for error correction, the transmitted bit stream will be 111111000111111000111111000 Suppose the received bit stream is 101011100011110001110110100 There is one bit error for every three bits. Even then at the receiver, the correct bit stream can be obtained. However, suppose the first three bits received are 001, then the receiver will decode it as 0 though the actual information bit is 1.

Projects

Write C programs to calculate CRC for the standard CRC algorithms, CRC-16 and CRC-32.
Write a program for error correction using Rate 1/3 FEC.
Studies indicate that even if 20% of the characters are received in error in a communication system for transmitting English text messages, the message can be understood. Develop software to prove this study. You need to simulate errors using a random number generation program.

< Day Day Up >