Bidirectional sequential decoding
Creators: name: Li, Kaiping
Publisher: name: University of British Columbia
Year: 2009

description: The main drawback of sequential decoding is the variability of its decoding effort which could cause decoding erasures. We propose and analyze in this dissertation efficient bidirectional sequential decoding (B SD) techniques to alleviate this drawback, In the proposed BSD, two decoders are used; one is called forward decoder (PD), and is used to search the tree from forward direction; while the other is called backward decoder (BD), and is used for the backward search of the tree. Forward decoding and backward decoding are performed simultaneously, and stop somewhere in the tree. In one class of BSD, to which we refer as BSD-merge, decoding stops whenever FD and BD merge at a common encoder state some where in the tree. In the other class of BSD, that is BSD no-merge, no common encoder state is required, and decoding stops when FD meets BD. Different BSD algorithms based on the stack algorithm are constructed; namely Algorithm TAmeet which belongs to the class of BSD-no-merge, Algorithm TAmerge and Algorithm Timerge which belong to BSD-merge, and finally Algorithm HTTmerge which is a hybrid version of BSD-merge and BSD-no-merge. The relationships between backward coding and forward coding are examined in detail. Good convolutional codes, with memory m ranging from 2 to 25, suitable for bidirectional decoding, found through extensive computer search, are provided. These codes possess the same distance properties from both forward and backward directions. It is found by analysis and computer simulations that the distribution of the total number of computations per decoded block of the proposed BSD is still Pareto, as that of unidirectional sequential decoding (USD). However, the advantage of the proposed BSD appears as an increase in the Pareto exponent, and hence as a decrease in the computational variability and erasure probability. More specifically, we prove by using the random coding approach that the Pareto exponent of BSD using Algorithm TAmeet is asymptotically twice that of USD, and conjecture that this also applies to Algorithm TAmerge. On the other hand, it is found that the computational cutoff rate remains unchanged, but the use of our BSD reduces the average number of computations per decoded bit. Using the random coding approach, we show that the error performance of BSD merge is asymptotically the same as that of USD. Moreover, we show that the bit error probability of Algorithm TAmeet satisfies the random coding bound for block codes. Computer simulations are provided to confirm the analytical findings. The use of BSD-merge substantially reduces the computational variability of con ventional sequential decoding without compromising the error performance, However, BSD does not completely eliminate the erasure problem. We therefore combine our BSD idea in conjunction with the multiple stack algorithm (MSA), which is an erasure-free decoding algorithm. It is shown through analysis and computer simulations that the new bidirectional multiple stack algorithm (BMSA) offers substantial advantages over the MSA in terms of computational effort, memory requirements and error performance. The BMSA appears as an attractive alternative to the Viterbi algorithm (VA) where low error probabilities and high decoding speeds are required.