Decoding of a Block Code by using List or Listless Algorithms

C.-L. Ho (Taiwan)


Parallel decoding, list parallel, listless parallel, A*-B&B algorithm.


Soft decoding of a binary block code can be implemented with or without use of stacks or lists. For the listless scheme, we show how to apply the threading method to parallel decoding. When a single processor is used, the list decoding may be faster than the listless one, but the complexity of the former is much higher than the later due to the use of stack. The value of the accumulated metric for each node is derived from the A* method and a branch-and-bound search method is used for the list scheme. While a recursive formula is used to calculate the metric of a node lying on the decoding tree, a stopping rule is used to terminate the recursion of a thread. By using the recursive formula and the termination rule, the search results are optimum. The listless scheme provides easy programming complexity requiring no stacks and can be scheduled to execute a preferred thread for an intermediate but suboptimum solution. For the intermediate case, better and reliability results can be obtained by allowing longer search time.

Important Links:

Go Back