Convolutional Coding is a form of error correction code that is fairly popular because of the fairly low decoding complexity, and because there are popular algorithms that accept soft inputs. The encoding complexity for convolutional codes is extremely low as well.
The key concept of convolutional codes is that an input bit will have some effect on several output bits. Secondly, unlike block codes, a convolutional code can continually stream. In fact, terminating the transmission has issues of its own!
Convolutional Encoder
This set of articles focuses on a convolutional code that looks at 8 message bits in order to generate two coded output bits. The encoder looks at the current input bit, and the last seven inputs (the constraint length), and from this decides which two coded bits to send. The decision method is based on simple xor’s. This is what makes the encode complexity so low — just a few registers and a few xor’s.
Trellis
Often, the “trellis” is shown for convolutional codes. This shows all of the states in the code, as well as the transitions allowed between states. The trellis is somewhat independent of the code. This isn’t always the case, but for encoders without feedback it is. Notice that in this example, the coded bits transmitted from each state can’t be determined by looking at the trellis — only the state transitions are.
The diagram here shows an example for a smaller four state code that starts in state 0, and transmits “1011”. Each of the four states has a different mapping of input bit to coded symbol. Thus the symbol transmitted for “1” is different each time it was transmitted in the example.
The decoder’s task is ultimately to determine the message bits. Most algorithms also try to estimate what state the transmitter was in during each bit interval. The classic decoder is the Viterbi decoder. This gives a ML solution to the problem. The downside is that it doesn’t scale well with long constraint lengths. “M-Decoding” keeps a list of the best M paths. This can work well for long codes, but is a sub-optimal algorithm. The need to find the best M out of 2M paths is also very difficult to do in a single cycle.
The results from my Virtex-6 targeted design were fairly good. Xilinx does offer a core for Viterbi decoding. Their core has more features, and is generally better. At the same time, they’ve most likely spent a lot more time refining the design than I have. Overall, I am happy with my results. It is fairly clear that the ACS is the main issue, as there are 128 of them. Any additional logic will need to be replicated 128 times. The end design uses around 1000 registers, but uses 2500 LUTs. Currently, the design has a longest path that is correctable but requires significant changes to the design. At this time, I’m using a hamming distance metric for my branch metric. A better decoder would use a distance metric more closely tied to the modulation scheme.
The files for the encoder/decoder are:
- viterbi_pkg.vhd — the top level package.
- vit_top.vhd — the top of the design.
- vit_metric.vhd — branch metrics.
- vit_acs.vhd — ACS array. Uses the most resources.
- vit_trace.vhd — traceback unit. Has the longest path.
- vit_ram.vhd — Virtex-6 implementation of RAM for vit_trace.vhd.
- vit_reorder.vhd — corrects the output order from the traceback unit.
- conv_encode_pkg.vhd — package for convolutional encoder.
- conv_encode.vhd — actual encoder.