Understanding Cell Phone Technology: Convolutional Codes
Today we’re going to talk about convolutional codes. Like block codes, convolutional codes are used in our cell phones to detect and correct errors introduced by noise on the transmission channel. Unlike block codes, these error correcting codes have memory. An (n, k, m) convolutional code depends on m previous message blocks, taking in a k-bit block and producing a sequence of n-symbol blocks.
A couple of weeks ago, we talked about a (2, 1, 2) convolutional code. You can go back and look at the picture of the encoder in the 28 December blog post. Today we’re going to talk about another way that engineers look at these codes using something called a state diagram. The state diagram for our (2, 1, 2) example is shown in the attachment below.
A state diagram is a quick graphical summary of what is going on in a convolutional coder. The graph is made up of nodes and edges. The nodes (the big circles) represent all the values that the memory cells can take on. Since there are only two memory cells in this coder, there are only four possible states: 00, 01, 10, and 11. The edges are the lines that join the nodes. Note that every edge only flows in one direction, denoted by an arrowhead. This combination of nodes and directed edges is called a directed graph. What’s interesting about a state diagram is that it shows all the possible ways in which the coder is allowed to transition from one state to another.
We assume that the state of the coder in the cell phone is all zeros (or “zeroized”) when we start feeding the input stream into it. This corresponds to starting in the state 00. If we input a 0, then the output of the coder is going to be 00. We signify this with the symbols on the edge of the curve from state 00 to state 00 (feeding back on itself). Starting with state 00, if we input a 0, we end up with the output bits 00, and return to state 00. We label this edge as input bit / output bits or 0/00.
What if we input a 1 into state 00 instead? We will now end up in the state 10 (remember, the coder gets filled from left to right). When we input a 1, the coder outputs 11, so we label the edge 1/11.
Let’s try one more. Suppose we start in the state 10. If we input a 0, we end up in state 01, and the edge is labelled 0/01. If we input a 1, we end up in state 11, and we label the edge as 1/10. Easy!
We already know that noise can introduce errors into the transmitted bits. The convolutional coder is designed to compensate (at least partially!) for this noise. It adds some redundancy to the message and sends an encoded stream instead.
The decoder in your cell phone knows what the original encoder looked like, and uses the ideas from the state diagram to come up with the best estimate of the original message sent. The decoder performs the decoding using something called the Viterbi algorithm, which was invented in 1967 by the engineer Andrew Viterbi. The Viterbi algorithm was a remarkable breakthrough which, along with the Fast Fourier Transform (invented in 1965, see my 22 June 2020 blog), helped make the cellular communications revolution possible.
Next week, we will take up our last topic in this series of blogs on cell phone technology. We’ll be diving into modulation and demodulation in order to understand a little bit about how messages get transmitted on electromagnetic waves and get recovered at the receiver.
