1Viterbi Detector: Review of Fast Algorithm and Implementation By sheng, Xiaohong I. Introduction Viterbi Algorithm is the optimum-decoding algorithm for convolutional codes and has often been served as a standard technique in digital communication systems for maximum likelihood sequence estimation. Given a sequence of symbols, the Viterbi Algorithm finds the most likely state transition sequence in a state diagram. Implementing high-coding gain Viterbi decoders in high-speed applications is more difficult compared to in low-speed applications because of the massive hardware size, large power consumption and expensive cost in high-speed application. However, it becomes more important to implement high-speed Viterbi decoders in recent years. For example, the application of Viterbi decoders to magnetic storage channels for decoding intersymbol interference has pushed required decode rates to over 100Mb/s for high-end drives. A potential application of even higher rates is in convolutionally coded optical M-ary pulse position modulation (PPM) systems, for which decode rates extend into the Gb/s range. To meet these demands, it is imperative to solve the problems of massive hardware size, large power consumption and slow detecting speed for high-speed application. This project will focus on a review on increasing the detector speed rather than reducing its power consumption. In general, there are two ways to increase the detector speed. One way is to modify the decoder at the algorithm level and another way is to increase the implementation speed at the hardware level. Both of these two methods will be reviewed in this report. The Organization of this report is as follows. In section II, the convolutional encode and its Viterbi decoder will be briefly reviewed. Algorithm level methods to increase the detecting speed will be discussed in section III. In this section, three different algorithm modification methods will be introduced. First, linear distances to represent the branch metrics will be briefly introduced. Then, a modified Viterbi Algorithm that decodes convolutional codes with noise adaptive and reduced effort is presented. Finally, a reduced state Viterbi algorithm will be illustrated. The hardware level implementation improvement will be addressed in section IV. In this section, the overall hardware2implementation to solve the problems of Viterbi Algorithm such as slow decoding speed, massive hardware size and large power consumption is briefly introduced first. Then, several hardware implementation methods to increase the Viterbi decoder speed are described in detail. A conclusion is given in section V. II. Viterbi algorithm and convolutional code 2.1 Convolutional code Convolutional codes are widely used for digital communication system. Given a set of base of the code, symbol is constructed by the convolution of states and base according to the following equation. ∑=−=mllljjX0GC (1) where Cj is the jth symbol and Xj is the states at jth time and Gl is the lth code base. Following is an example for four state convolutional code. The symbol C is supposed to be composed of two elements, i.e.,{}1,0=C , and base is:=110111G , we get: [ ] [ ]jjjjjjjjjXXXXXXXX +++==−−−−− 21212110111C (2) Fig 1. shows the diagram of the convolutional encoder for the above example. Xj-1 Xj-2+ ++XjCj=[Cj1,Cj2] Fig 1. Convolutional Encoder3 2.2 Viterbi Algorithm Viterbi Algorithm (VA) is the optimum-decoding algorithm for convolutional codes. It finds the sequence of symbols in the given trellis that is closest in distance to the received sequence of noisy symbols. This sequence computed is the global most likely sequence. To compute the global most-likely sequence, the VA first recursively computes the survivor path entering each state. After the survivor paths entering all states are computed, the survivor path that has the minimum path metric is selected to be the global most likely path. In VA, the branch metric is defined as the distance between the received noisy symbol, yn and the ideal noiseless output symbol, Ci,j. The branch metric transition from state i to state j at recursion n is ( )∑=⊕=KlljinnjiCyB1,,, (3) The path metric in VA is defined as the distance between the survivor path and the sequence of noisy symbols. Mj,n, which is the path metric for state j at recursion n, is the most likely path coming into state j at recursion n. It is calculated as follows: )min(,,1,, njininjBMM +=− (4) After the most likely transition to state j at recursion n is computed, the path metric for state j, Mj,n, is updated and this most likely transition is appended to the survivor path of state m at recursion n-1 in order to form the updated survivor path coming into state j at the current recursion, n. The path metrics and the survivor paths are updated for all states at each recursion. At the end of the recursions, the survivor path with the minimum path metric is selected to be the most likely path. Fig. 2 is a four state of trellis diagram for the Viterbi decoder. The dark bode line is the final survivor path (winner) as it has the minimum path metric.4Winner!1001110000 00 00 00 00111001000110011010101111111111111122312452222333323301 01 00 11 10ReceiveDetected: 00 00 00 11 10 III. Algorithm level methods to increase the Viterbi decoding speed VA is the optimal maximum likelihood detection method in AWGN when Euclidean distance is used as a distance measure. Practically, Hamming distance is used to speed up the decoding speed. However, the performance of the VA with Hamming distance as a metric measure is sub-optimal. If we intend to use Euclidean distance to improve the VA performance, we might have to use the duplication of the multipliers to obtain the squared distances for high bit-rate applications. These can increase the decoder complexity significantly. Hui-Ling Lou [1] proposed a method with which linear distances were used to represent the branch metrics, without compromising the Viterbi decoder performance. Therefore, the high complexity caused by the duplication of the multipliers can be avoided while VA performance can still be maintained. Christian Feldmann [2] proposed a modified Viterbi Algorithm that decoded convolutional codes with noise adaptive and reduced effort while retaining coding gain close to the VA over the range of
View Full Document
Unlocking...