The BMG generates the branch metrics for each symbol of the input sequence by calculating the hamming distance between the input symbol and the expected symbol for each connection of the trellis (state). For example, for a 1/2 rate code, there are four possible symbol combinations in the encoded sequence: 00, 01, 10, and 11.

In the Viterbi decoding scheme described here, a 5-b soft decision could be used so that the transmitted bits in a symbol could be represented as 32 possible signal levels. The inverted MSB of the 5-b words would then give the logical value of 0 and 1. It's important to note that it is not practical to use more than 32 levels of quantization for each bit of the symbol. Going beyond the 32 levels would provide a fine quantization but would only achieve an loss in the SNR of less than 0.25 dB. Thus, the cost of using more bits is not justified.

While the 5-b approach, can be used, it was not chosen for the proposed 1/2 rate Viterbi decoder described here. The 5-b scheme is complex and requires more silicon area. Therefore in the example described in this article, a 3-b approach was employed.

A branch metric unit (BMU) was also implemented as a look up table and Euclidean distances are used for comparing the received symbols to the four ideal encoded symbols.³ The branch metrics are obtained by assigning positive numbers to the 8 possible values of the input signal. The two symbols of the received code word can be projected on the coordinate system. The Euclidean distance between ideal code words and an arbitrary point in this space (the received code word) gives the branch metrics.

By increasing the number of soft bits the number of possible values for branch metrics also increases. Figure 2 shows the branch metric diagram for an 8-level decoder. A number of different measures such as Euclidean distance or Manhattan distance can be used to generate the branch metrics.

The ACS Unit

The ACS unit is the heart of the Viterbi decoder. Each node in the trellis diagram corresponds to an ACS processor in the corresponding Viterbi decoder. The constraint length of the encoder (K) gives the number of ACS processors for a parallel architecture (Figure 3).

If the data frequency is very high, then parallel architecture is advisable but if the data rate is less or comparable to the clock frequency, a serial or mixed architecture (where the number of ACS processor is less than 2(sup)k-1, and a stage is computed over a number of clock cycles) is not practical. It should be noted that two ACS processors that share the same input can be grouped into a butterfly processor.

Figure 3 shows the structure of an ACS processor. In this example, the ACS processor has 4 inputs (two- branch metrics and two-path Metrics) and two outputs (the new path metric and the decision bit). The decision bit is the most important information generated by the ACS .It indicates which sum between an input path metric and a branch metric generated the smallest result and was selected as the output path metric or local winner.

If the connected bit of a state is 0 the associated ascending branch is the local winner leading to previous state. If it is 1, the descending branch will be chosen. The 64 bits are grouped and for every stage, a 64-b memory location is written. All decision bits generated at one stage are used later in trace back unit to decode the output bits.

Normalization metrics

As in convolution decoder the data is coming continuously so the path metric, which is a sum of the branch metrics of previous stages, increases to a point where an overflow occurs. In order to prevent arithmetic flow and in order to keep the register effort and the combinatorial delay for add and compare operations in the ACS unit as small as possible, metric normalization schemes are used.

Several methods for state metric normalization are known, which are based on two facts:

1.The differences δ between all state metrics at any trellis step k is bounded in magnitude by a fixed quantity δ_max independent of the number of ACS operation already performed in the trellis. 2. A common value may be subtracted from all state metrics for any trellis step k, since the subtraction of a common value does not have any impact on the results of the following metric comparisons.

The technique based on second fact is known as rescaling approach. Under this approach, each iteration the minimum metric is subtracted from all the metrics. The use of 2s complement modulo normalization technique, which is based on first fact, is alternative to the rescaling approach.

The second scheme avoids any kind of rescaling subtractions. The obvious advantage in the implementation is hardware savings and a speedup inside the metric update loop, which is critical to the decoder's computational throughput.

In order to reduce the power and area utilization it is desirable to represent the path metrics in as few bits as possible, in our case it is 9 bits. The number of bits should be such that it follows:

2^c-1-1>δ_max

c=number of bits decided to represent path metrics.

δ_max is related to branch metric as δ_max= m* (Maximum value of branch metric- minimum value of branch metric)+2)

where m = 2* constraint length in case of soft viterbi and equal to constraint length in case of hard viterbi.

In VLSI implementation of the normalization techniques, the two most desirable properties are locality and uniformity. Metric normalization is considered local if it is accomplished within each ACS processor without information from other ACS processor. It is considered uniform if the ACS operation is not interrupted to perform metric normalization. Locality minimizes the global signal communication and uniformity not only reduces the complexity but also avoiding the additional functional units (Figure 4).

There are various techniques for implementing local and uniform normalization techniques. In the present design, the modified comparison rule is used.

Under modulo technique, the metric m_j is replaced by the normalized metric m_norm= (m_j+c/2)(modC)-C/2, where C is the maximum value represent by the number of bits used for defining path metric.

The modified comparison rule gives the survivor bits to the trace back unit. This rule is computed using the following equation:

Survivor (m_norm1, m_norm2)= m_norm1 x or m_norm2 x or y (m1, m2)

Where y (m1, m2) denotes the unsigned comparison. In other words survivor (mn1, mn2) equals y (m1, m2) [or the logical inverse of y (m1, m2)] if mn1 and mn2 have the same (or opposite) sign.

Trace back unit

The ACS block assigns the measurement functions to each state, but the actual Viterbi decisions on encoder states are based on the trace back operation to find the path of the states. Using the trace back operation, every state from a current time is followed backwards through its maximum likelihood path. All of the paths converge at a point somewhere previous point in time.

The point at which the corrected bit streams starts is called the merger point (also called the trace back depth). By finding this point, the trace back operation decisively determines the state of the encoder at a given time, by showing that at this point, there is no choice for an encoder state given the global maximum likelihood path.

The performance of Viterbi decoder largely depends upon the trace back depth. The increase in trace back depth increases the complexity and hardware exponentially so one has to trade off between the performance level and the complexity and hardware.

Normally for decoders using non-punctured codes, the trace back depth equals 5-times constraint length, which is sufficient to decode the correct output in the presence of noise. But for decoders using punctured codes and a 2/3 data rate, and 8-times constraint length is optimal. If the data rate if 3/4, then 10-times constraint length should be used. Going beyond a 10-level constraint length does not make sense because performance gains are minimal. Thus, it is best to cap the constraint length at 10 levels. (Note: in the 1/2 rate design described here, a 7-times trace back depth was chosen).

The main bottleneck in implementing Viterbi algorithm for convolution codes is that for every new piece of symbol information, the algorithm must trace back over multiple states. The best way to implement trace back algorithm is described by Thung.² Under this method, at the beginning of the array, the butterfly matrix calculates the next states as a function of the current path metrics of all the states and the most recent symbol. The paths top each state in the trellis imply the decision bits that were used to reach those states, and that information is also explicitly computed. The maximum likely state is selected from the maximum path metrics of all the current states, and is passed along with the decision vector. The minimum state represents the starting point for the traceback through to encoder trellis (Figure 5).

The systolic array keeps the high throughput for the traceback operations by launching a new traceback into the pipeline on every cycle. The pipeline has two components, propagating through the stages.

1. The Traceback states.
2. he Decision vectors.

While the decision vectors move one step ahead on every cycle, the maximum likelihood (ML) state stages actually jump ahead two steps at a time. The beginning of the pipeline is analogous to time k in figure 5, in that all of the possible stages have a path to a previous state as defined in the decision bit vector. The state register at the beginning of the pipeline represents the state the traceback will occur from, On the next clock cycle, the t^th state decision vector moves from one stage, but the ML traceback state jumps forward to the decision vector for time (t-1).

Again the previous state is calculated and as the state travels in to the pipeline, it moves closer to the final traceback time. The pipeline is sized such that the traceback state will reach the final state where a symbol decision is made (analogous to the traceback of the ML path in figure 5 from time k to time 0) at the end of the pipeline, and at that point the decision vector bit can be released as the true symbol.

In hardware implementation, the trace back unit has 2-level traceback length registers having a width of 64 to store and shift survivor bits, 64 registers of width 6 to store the current state, and 64 multiplexes to select the survivor bit used in the formation of next state.

Comparison of hard vs. soft decision

In general, as the quantization level of bit metric is kept longer and the decoding depth deeper, we get better BER performance while the hardware complexity increases exponentially. Also decoding the data requires an additional delay proportional to the decoding depth.

The BER performance of the soft versus the hard decision in Rayleigh fading channels is shown below in figure 3. The soft method achieves the better performance than the hard decision method by about 2 dB.

In case of quantization level vs. BER performance, we determined that by using quantization, we get a significant processing gain, typically 2 dB for 3-b quantized data and about 2.2 dB for 4-b quantized data over hard decision.

References:

1. John B. Anderson, Seshadi Mohan, "Source and Channel Coding--An Algorithmic Approach," Chapter 4 1991, Kuwer Academic Publisher.
2. T.Trung, ET. Al, "A VLSI design for a Traceback Viterbi Decoder, "IEEE Transaction on Communications, vol.40, No.3, March 1992, p.616-624.
3. Boo, M., Arguello, F., Bruguera, J.D., Doallo, R., Zapatta, E.L, High performance VLSI Architecture for the Viterbi Algorithm, IEEE Transactions on Communications, Vol. 45, No.2, (February --1997).
4. Heller, J.A., Jacobs, I.M., Viterbi Decoding for Satellite and Space Communications, IEEE Transaction on Communication Technology, Vol. COM 19 no.5 (October 1971), 835-848.

About the Authors Sharad Singhal is a design engineer for DCM Technologies, Gurgaon, India. He has B-Tech (Electronics and Telecom) from Regional Engineering College Kurukshetra, India and can be reached at sharad_singhal@rediffmail.com.