NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
A hybrid M-algorithm/sequential decoder for convolutional and trellis codesThe Viterbi Algorithm (VA) is optimum in the sense of being maximum likelihood for decoding codes with a trellis structure. However, since the VA is in fact an exhaustive search of the code trellis, the complexity of the VA grows exponentially with the constraint length upsilon. This limits its application to codes with small values of upsilon and relatively modest coding gains. The M-Algorithm (MA) is a limited search scheme which carries forward M paths in the trellis, all of the same length. All successors of the M paths are extended at the next trellis depth, and all but the best M of these are dropped. Since a limited search convolutional decoder will flounder indefinitely if one of the paths in storage is not the correct one, the data are usually transmitted in blocks. It has been shown that the performance of the MA approaches the VA at high signal to noise ratios (SNR's) with an M which is far less than the 2 sup upsilon states in the full trellis. Thus the MA can be used with larger values of upsilon, making larger coding gains possible at high SNR's. However, it still requires a relatively large fixed computational effort to achieve good performance.
Document ID
19900017212
Acquisition Source
Legacy CDMS
Document Type
Contractor Report (CR)
Authors
Wang, Fu-Quan
(Notre Dame Univ. IN, United States)
Costello, Daniel J., Jr.
(Notre Dame Univ. IN, United States)
Date Acquired
September 6, 2013
Publication Date
June 29, 1990
Subject Category
Computer Programming And Software
Report/Patent Number
NAS 1.26:186863
NASA-CR-186863
Accession Number
90N26528
Funding Number(s)
CONTRACT_GRANT: NAG5-557
CONTRACT_GRANT: NSF NCR-89-03429
Distribution Limits
Public
Copyright
Work of the US Gov. Public Use Permitted.
No Preview Available