BIDIRECTIONAL SEQUENTIAL-DECODING

The main drawback of sequential decoding is the variability of its dec oding effort which could cause decoding erasures. We propose and analy ze in this correspondence an efficient bidirectional sequential decodi ng (BSD) technique to alleviate this drawback. In the proposed BSD, tw o decoders are used; one is called a forward decoder (FD), and is used to search the tree from forward direction; while the other is called a backward decoder (ED), and is used for the backward search of the tr ee. Forward decoding and backward decoding are performed simultaneousl y, and stop whenever FD and ED merge at a common encoder state somewhe re in the tree. The relationships between backward coding and forward coding are examined in detail. Good rate 1/2 convolutional codes, with memory m ranging from 2 to 25, suitable for bidirectional decoding fo und through extensive computer search, are provided. These codes posse ss the same distance properties from both forward and backward directi ons. It is found by means of extensive computer simulations as well as a heuristic argument that the advantage of BSD appears as a substanti al decrease of the computational variability of sequential decoding. O ur findings suggest that the Pareto exponent of unidirectional sequent ial decoding (USD) can be practically doubled by using BSD.