Understanding Cell Phone Technology: Error Correcting Codes
Error correcting codes came along after Claude Shannon proved that the use of suitable codes permitted reliable information transmission across a noisy channel at rates approaching the channel capacity. By “codes”, Shannon actually meant codes for data compression and codes for error correction.
We’re already spent several weeks talking about compression algorithms, available in lossless and lossy variants. Data compression codes squeeze out redundant (and sometimes less significant) information from the original message. This frees up some space so the transmitter can add some “useful” redundancy back into the data. This redundancy can be used at the receive end to correct bits that got corrupted by a noisy channel.
This useful redundancy is introduced by using error correcting codes. These are also known as channel codes, because they are designed to compensate for the noise which occurs on the communications channel. Error correcting codes come in two flavors: block codes and convolutional codes.
A block code parses a stream of bits into blocks which are k bits long. It uses a single k-bit block of information to generate a single n-bit codeword. So, for example, the first k-bit input block will determine the first n-bit output codeword. Then the second input block determines the second output codeword, the third the third, and so on and so on. Because of this design feature, we say that say block codes are memoryless. The ith output block depends only on the ith input block and no others.
Since there are only 2^k possible input blocks, there are only 2^k possible codewords. The extra n-k bits are redundant bits that add back in some extra information. If channel noise introduces some errors during transmission, the receiver’s decoder can use the redundant bits to identify and correct (at least some of) them. The ratio k/n is called the code rate, and the set of n-bit codewords is called an (n, k) block code.
A convolutional code takes in a k-bit block and produces a sequence of n-symbol blocks. Unlike block codes, convolutional codes are not memoryless. In fact, the code depends on m previous message blocks, and we say it is an (n, k, m) convolutional code.
Convolutional encoders use mod 2 arithmetic. In mod 2 arithmetic, the only numbers to be added are 0 and 1, and the only answers are 0 and 1. Here’s what mod 2 arithmetic looks like:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 0
OK, now we’re ready to look at an example of a convolutional coder. Suppose I have a stream of bits coming into my convolutional coder that look like 1101000…. The first bit to go into the coder is the 1 on the left-hand side. Since English readers are accustomed to seeing things flow from left to right, we’ll reverse the order of the stream to be … 0001011. The 1 at the rightmost end of the stream flows into the left-hand side of the encoder. This encoder has two memory cells. As each new bit flows in, the two preceding bits progress to the right through the memory cells and out. A diagram is attached below.
The encoder’s output alternates between two mod 2 sums. The first sum will be the content of the rightmost memory cell plus the new bit taken into the encoder. The second sum will the sum of both memory cells plus the new bit taken into the encoder. This is a (n, k, m) = (2, 1, 2) convolutional code. An input stream like our 0001011 will generate an output stream of 11, 10, 10, 00, 01, 11, 00. Using a convolutional coder introduces some redundancy into the information so that corrections can be made at the receiver.
Don’t worry if these examples are not yet crystal clear. We talked about them briefly today so we could see how block and convolutional coders are the same and how they differ. Next week, we will begin looking at error correcting codes in more detail.
