Viterbi Detector: Review of Fast Algorithm and Implementation 
-byXiaohong, Sheng

The 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.  It is the
optimal maximum likelihood detection method in AWGN( additive white
gaussian noise) when Euclidean distance is used as a distance measure. 

Since Viterbi Algorithm has the problem of computational complexity, its
detecting speed is slow in general and needs high power consumption. 
This project will more focus on increasing the detector speed rather
than reducing its power consumption.  In general, there are two ways to
increase the detector speed.  One is algorithm level method and another
is hardware implementation level method.  Each method has its own
various approaches. 

This project is a review of the algorithm and hardware implementation of
Viterbi detector.  It has four parts.  In the first part, the
convolutional code, which is widely used in digital communication, will
be briefly introduced.  And then, its decoder, viterbi detector will be
explained in detail. 

Algorithm level methods to increase the detecting speed will be
discussed in the second part.  Reduced state viterbi algorithm uses the
method of reducing the constraint length ( the number of states) to
decrease the Viterbi algorithm computational complexity, and so,
increase the detecting speed.  Constraint length based modified Viterbi
algorithm provides both a method for enhancing the frequency of matches
of the successive path segments and a mean for reducing path metric
computations when a match occurs.  It also provides an efficient method
for obtaining path metrics when a match does not occur.  It is applied
by collecting the sufficient received codewords to define a path segment
one constraint-length long.  Other methods such as 'linear distance as
branch metrics for viterbi decoding' can also be used to increase the
decoding speed. 

The hardware level implementation will be addressed in the third part. 
So far, Lots of methods have been proposed to increase the Viterbi
detecting speed in hardware level.  Pipeline architecture, path limited
PRML method and so on.  They will be discussed in this part. 

A briefly summery will be given in the last part. 

References

[1].  Implementing the Viterbi algorithm, Lou, H.-L.  IEEE Signal
Processing Magazine , Volume: 12 Issue: 5 , Sept.  1995, Page(s): 42 -52

[2].  A reduced-state Viterbi algorithm for blind sequence estimation of
DPSK sources,Tongtong Li; Zhi Ding Global Telecommunications Conference,
1999.  GLOBECOM '99 , Volume: 4 , 1999 ,Page(s): 2167 -2171 vol. 

[3].  A reduced state Viterbi algorithm for multiuser detection in
DS/CDMA systems ,Wang Zhaocheng; Ge Ning; Yao Yan; Qiang Wang
Communication Technology Proceedings, 1996.  ICCT'96., 1996
International Conference on , Volume: 2 , 1996 Page(s): 1102 -1105 vol.2

[4].  Linear distances as branch metrics for viterbi decoding of trellis
codes,Hut-Ling Lou Acoustics, Speech, and Signal Processing, 2000. 
ICASSP '00.  Proceedings.  2000 IEEE International Conference on ,
Volume: 6 ,Page(s): 3267 -3270

[5].  A constraint-length based modified Viterbi algorithm with adaptive
effort Feldmann, C.; Harris, J.H.  Communications, IEEE Transactions on,
Volume: 47 Issue: 11 , Nov.  1999 Page(s): 1611 -1614

[6].  Complexity reduction of the Viterbi algorithm using doubly
complementary convolutional codes, Haccoun, D.; Caron, M.; Nabli, M. 
Communications, Computers and Signal Processing, 1999 IEEE Pacific Rim
Conference on , 1999 Page(s): 408 -411

[7].  High-performance VLSI architecture for the Viterbi algorithm, Boo,
M.; Arguello, F.; Bruguera, J.D.; Doallo, R.; Zapata, E.L. 
Communications, IEEE Transactions on , Volume: 45 Issue: 2 , Feb.  1997
Page(s): 168 -176

[8].  Pipelined architectures for the Viterbi algorithm, Boo, M.;
Brugera, J.D.  TENCON '97.  IEEE Region 10 Annual Conference.  Speech
and Image Technologies for Computing and Telecommunications.,
Proceedings of IEEE , Volume: 1 , 1997 Page(s): 239 -242 vol. 

[9].  A high speed Viterbi decoder using path limited PRML method and
its application to 1/2 inch HD full bit rate digital VCR, Hara, M.;
Yoshinaka, T.; Sugizaki, Y.; Ohura, S.  Consumer Electronics, 2000. 
ICCE.  2000 Digest of Technical Papers.  Page(s): 96 -97

[10].  Novel Viterbi decoder VLSI implementation and its performance,
Kubota, S.; Kato, S.; Ishitani, T.  Communications, IEEE Transactions on,
Volume: 41 Issue: 8 , Aug.  1993 Page(s): 1170 -1178