An efficient decoding algorithm for cycle-free convolutional codes and its applications

This paper proposes an efficient graph-based sum-product algorithm for decoding 1/(1+D n ) code, whose Tanner graph is cycle-free. Rigorous proof is given which shows the proposed algorithm is equivalent to the MAP decoding implementing the BCJR algorithm, but with magnitude less of complexity. In this, the paper presents an explicit example which confirms the claim that sum-product algorithm is optimal on cycle-free graphs. A parallel realization is then discussed and shown to resemble LDPC decoding. The paper further proposes a min-sum algorithm which is equivalent to the max-log-MAP algorithm. Prospective applications which can take advantage of the proposed decoding algorithms are discussed and simulations are provided.

An efficient decoding algorithm for cycle-free convolutional codes and its applications Conference Paper