Due to the recursive and iterative nature of turbo decoding algorithm, the computational decoding delay of turbo codes may not be acceptable. To reduce the decoding delay in turbo decoding, one may use a short frame size code at the expense of performance degradation. This is a plausible option in low data rate systems because the time span of the codeword is the dominant factor in decoding delay. However, in high data rate systems, such as multi-mega bps, the computational decoding delay is dominant and it may be required to reduce the computational decoding delay.

To reduce the computational decoding delay of turbo codes, we propose a parallel algorithm for MAP decoders that use multiple processors to perform sub-block MAP decoding in parallel. However, unlike the previously published parallel algorithm with sub-block overlapping, we utilized the forward and backward variables computed in the previous iteration to provide boundary distributions for each sub-block MAP decoder. The proposed algorithm is based on the belief propagation paradigm, where each sub-block take messages from the neighbors, update their belief and send them back to the neighbors. We obtain at least two advantages over the previous parallel MAP scheme. First, there are no additional computations due to overlapping. Second, communicating with their neighbors, each sub-block MAP decoder can converge to optimal values since information in one sub-block propagates through the entire network by message passing.