Viterbi decoder
"Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm".
A hardware Viterbi decoder for basic (not punctured) code usually consists of the following major blocks: A branch metric unit's function is to calculate branch metrics, which are normed distances between every possible symbol in the code alphabet, and the received symbol.
A hard decision Viterbi decoder receives a simple bitstream on its input, and a Hamming distance is used as a metric.
, there must be an additional circuit (not shown on the image) preventing metric counters from overflow.
A simpler way to do this is to monitor a single location or "state" and watch it pass "upward" through say four discrete levels within the range of the accumulator.
As it passes upward through each of these thresholds, a counter is incremented that reflects the "noise" present on the incoming signal.
Back-trace unit restores an (almost) maximum-likelihood path from the decisions made by PMU.
Since it does it in inverse direction, a viterbi decoder comprises a FILO (first-in-last-out) buffer to reconstruct a correct order.
In order to fully exploit benefits of soft decision decoding, one needs to quantize the input signal properly.
is a noise power spectral density, and k is a number of bits for soft decision.
) distance between the received and the actual symbols in the code alphabet may be further simplified into a linear sum/difference form, which makes it less computationally intensive.
[1] However, computing the node which has accumulated the largest cost (either the largest or smallest integral path metric) involves finding the maxima or minima of several (usually 2K-1) numbers, which may be time consuming when implemented on embedded hardware systems.
By using the known bit/byte pattern as reference, the start node may be set to a fixed value, thereby obtaining a perfect Maximum Likelihood Path during traceback.
A physical implementation of a Viterbi decoder will not yield an exact maximum-likelihood stream due to quantization of the input signal, branch and path metrics, and finite traceback length.
A hardware viterbi decoder of punctured codes is commonly implemented in such a way: One of the most time-consuming operations is an ACS butterfly, which is usually implemented using assembly language and an appropriate instruction set extensions (such as SSE2) to speed up the decoding time.
