Bidirectional search for convolutional codes

Abstract

In sequential decoding, the buffer overflow is often caused by the Paretian computational distribution problem. This troublesome distribution arises from the sequential decoding algorithm, not from the basic properties of convolutional codes. In this paper, we show that this problem could be removed by using a bidirectional search. In Section 2, we develop a bidirectional tree structure that is applicable to any given convolutional code. In Section 3, we fully interpret why a decoding sequence could recover to the correct path after accepting errors. Also, factors which would affect the length of recovery decoding error bursts are discussed. In Section 4, we first introduce four new properties of convolutional codes. Then we describe the general bidirectional search procedure and explain why and how this search could eliminate the recovery decoding errors. To clarify all the involvements and considerations of using the proposed scheme, examples are given for general reference. It is understood that the performance of a system using long codes depends on the decoding speed and the buffer capability of the decoder. Therefore, the new decoding approach presented in this paper could open a new direction toward overcoming the existing difficulties of using long convolutional codes.