J. M. Walsh, P. A. Regalia, and C. R. Johnson, Jr.
Submitted to IEEE Trans. Inform. Theory on July 29, 2005.
The turbo decoder was not originally introduced as a solution to an optimization problem. This has made explaining the excellent performance of the turbo decoder difficult. In this paper it is shown that the turbo decoder is an iterative method attempting to find a solution to an intuitively pleasing constrained optimization problem. In particular, the turbo decoder is trying to find the maximum likelihood sequence under the false assumption that the input to the encoders were chosen independently of one another in the parallel case, and the false assumption that the output of the outer encoder was chosen independently of the input to the inner encoder in the serial case. To control the error introduced by the false assumption, the optimizations are performed subject to a constraint on the probability that the messages which were independently chosen happened to be the same. When the value of the constraining probability is one, the global maximum of the constrained optimization problem is the maximum likelihood sequence detection, allowing for a theoretically based approximate connection between turbo decoding and maximum likelihood sequence detection. It is then shown that the turbo decoder is a nonlinear block Gauss Seidel iteration which is trying to solve the optimization problem by zeroing the gradient of the Lagrangian with a Lagrange multiplier of $-1$. Some conditions for the convergence for the turbo decoder are then given by adapting the existing convergence literature for Gauss Seidel iterations.