DocumentCode :
1229236
Title :
A fast algorithm for computing distance spectrum of convolutional codes
Author :
Cedervall, M.L. ; Johannesson, Rolf
Author_Institution :
Dept. of Inf. Theory, Lund Univ., Sweden
Volume :
35
Issue :
6
fYear :
1989
fDate :
11/1/1989 12:00:00 AM
Firstpage :
1146
Lastpage :
1159
Abstract :
A fast algorithm for searching a tree (FAST) is presented for computing the distance spectrum of convolutional codes. The distance profile of a code is used to limit substantially the error patterns that have to be searched. The algorithm can easily be modified to determine the number of nonzero information bits of an incorrect path as well as the length of an error event. For testing systematic codes, a faster version of the algorithm is given. FAST is much faster than the standard bidirectional search. On a microVAX, d=27 was verified for a rate R=1/2, memory M=25 code in 37 s of CPU time. Extensive tables of rate R=1/2 encoders are given. Several of the listed encoders have distance spectra superior to those of any previously known codes of the same rate and memory. A conjecture than an R=1/2 systematic convolutional code of memory 2M will perform as well as a nonsystematic convolutional code of memory M is given strong support
Keywords :
coding errors; encoding; error correction codes; FAST; convolutional codes; distance profile; distance spectrum; encoders; error event; error patterns; fast algorithm; nonzero information bits; systematic codes; Binary codes; Conferences; Convolutional codes; Error probability; Information theory; Maximum likelihood decoding; System testing;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/18.45271
Filename :
45271
Link To Document :
بازگشت