A new algorithm for the maximum a posteriori (MAP) decoding of linear block codes is presented. The proposed algorithm can be regarded as a conventional BCJR algorithm for a section trellis diagram, where branch metrics of the trellis are computed by the recursive MAP algorithm proposed by the authors. The decoding complexity of the proposed algorithm depends on the sectionalization of the trellis. A systematic way to find the optimum sectionalization which minimizes the complexity is also presented. Since the algorithm can be regarded as a generalization of both of the BCJR and the recursive MAP algorithms, the complexity of the proposed algorithm cannot be larger than those algorithms, as far as the sectionalization is chosen appropriately.

A recursive maximum likelihood decoding (RMLD) algorithm is more efficient than the Viterbi algorithm. The decoding complexity of the RMLD algorithm depends on the recursive sectionalization. The recursive sectionalization which minimizes the decoding complexity is called the optimum sectionalization. In this paper, for a class of non-linear codes, called rectangular codes, it is shown that a near optimum sectionalization can be obtained with a dynamic programming approach. Furthermore, for a subclass of rectangular codes, called C-rectangular codes, it is shown that the exactly optimum sectionalization can be obtained with the same approach. Following these results, an efficient algorithm to obtain the optimum sectionalization is proposed. The optimum sectionalizations for the minimum weight subcode of some Reed-Muller codes and of a BCH code are obtained with the proposed algorithm.