The first part of the Viterbi Decoder is simply tracking the best path to each possible state. This is the main complex part of the viterbi decoder, as it requires several accumulators. Each ACS unit is fairly simple, but there are a lot of them.
The ACS operation is “add-compare-select”. The operation is intended to find the best path to each state. For the convolutional codes, there are only two (for rate 1/2) ways to get to any given state. This is easy to show — a state “0101010” (2A) can be reached from “0010101” (15) or “1010101” (55) if the input bit is a 0. The msb will be shifted out, and the input bit will be shifted in. The rest of the state bits do not change. Notice that an input of 0 would result in a transmitted codeword of “00” from state 15, and a codeword of “11” from state 55.
The simple method to determine the best path to a given state is to simply look at these two possible previous states and the number of errors required to have reached each. The input is considered, and the number of errors required to transition to the state under examination is added. The best path will be the one that requires the lowest number of errors.
Example of ACS
In this example, the decoder has received the codeword “11”. This image shows one of the 128 ACS units, the one for state 2A. This state can be reached from state 15, and state 55. If the previous state was 15, then a 00 would be be the correct codeword to transition to this state. From state 55, the correct codeword would be 55. It currently is more likely that the encoder is in state 15 than in state 55. A 11 is received, meaning that, to get to state 2A through state 15, five errors would have occurred. To get to state 2A through state 55, only four errors would have occurred.
Keep in mind that this process is performed for all 128 states. It will be more likely that the correct state will be 2B (not shown), as the “11” input would be the correct input to transition to that state, and would require only 3 errors. Even though 2B is the more likely state given the recent input, the path to state 2A is retained, as the path through it might eventually emerge as the most likely path after more input is considered.
Generating the ACS stages is actually easier then expected, and can be done inside of a VHDL generate statement. Looking at the above, it is easy to see that the previous states are formed by shifting the examined state, then prepending a 0 or 1. In this example I have also merged the branch metrics into the ACS, but in an actual design these will probably be inputs to the ACS array.
Comparison in ACS
The sizing of the adders can be done by realizing that a given state can reach any other state in N steps, with at most 2N errors. This means that the worst surviving path is at most 2N greater than the current best path, after N steps. This is for the case of hard decisions. If the comparison is done using a “more/less clockwise” approach, the system will not need additional logic for normalization. Note that for other branch metrics, the sizing might need to be different but will still be bound in the same manner.
The output of the ACS in this design is the decision of which path is the best path. In the example above, there would be 128 output bits, and the bit associated with state 2A would be a 1. Notice that this corresponds to the msb of the previous state. Using this mapping allows a downstream module to re-form the input data directly from the ACS decisions.
The ACS stages are the largest part of the decoder. Not really the most complex, just the largest. This is because there are 128 of them in the design. Each also contains two adders and a comparator. This quickly uses up a lot of LUT’s.