A linear-time method for contender sifting in breadth-first decoding of error control codes
A.D. Kot · 2002
We introduce a very efficient (linear-time) method for finding the best metrics from among a number of contenders during breadth-first decoding of block or convolutional codes. This method can provide a sorted set of survivor metrics during M algorithm decoding of binary linear block codes using only /spl Lambda/1 comparisons in the worst case. This is a significant improvement over comparison-based sorting, which requires O(M log/sub 2/ M) comparisons. A similar improvement is attained over Hadian and Sohel's comparison-based selection method (where the best metrics are found without regard to order). The method is also readily applicable to the decoding of convolutional codes.>