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


An efficient decoding algorithm for cycle-free convolutional codes and its applications	GLOBECOM 2001 San Antonio Nov., 2001
J.Li, C.N.Georghades

» [ps] [pdf]

Abstract -- 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 that the proposed algorithm (serial realization) 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 shown to be equivalent to the max-log-MAP algorithm. Prospective applications which can take advantage of the proposed decoding algorithms are discussed and simulations are provided.

Keywords -- message-passing algorithm, sum-product algorithm, min-sum algorithm, code graph, Tanner graph, trellis decoding, accumulator, BCJR algorithm, Max-log-MAP decoding, product accumulate codes