Recursive Suboptimal Decoding Algorithm for Binary Linear Black Codes

点击翻译按钮获取中文摘要

1. A soft-decision decoding algorithm is derived by approximating some computations in the recursive maximum likelihood decoding (RMLD) algorithm. In the RMLD algorithm, the most likely code vector is computed by constructing tables of most likely local vectors in a divide-and conquer manner. In the proposed suboptimum algorithm, vectors in the tables are pruned according to a certain criteria. The relation among the criteria of pruning, error performance and the decoding complexity is analyzed. A simulation result for the third order Reed-Muller code of length 64 shows that we can realize a suboptimum decoder which achieves almost the same error performance as an ML decoder and costs only one-fourth decoding complexity compared to the RMLD algorithm [1,2].2. The original RMLD is not adaptive to signal-to-noise (SN) ratios. In RMLD, every most likely local vectors are computed in bottom-up way. We propose a new version of RMLD which is very adaptive to SN-ratios by introducing "lazy evaluation" in a top-down way. That is, most likely local vectors are computed when it is required for the first time. These computation can be efficiently carried out by using parity check matrices of certain local subcodes of the entire code [3,4]. For several Reed-Muller codes and extended permuted BCH codes, simulation results show remarkable reduction of time and space complexity of decoding.3. The weight distribution of coset leaders of cosets with respect to a local subcode provides primary information on how to prune an insignificant subtables for most likely local vectors. A new relatively efficient algorithm for computing the weight distribution of coset leaders of binary linear block codes is proposed [5].4. The quantization levels for received sequences and the accuracy of the metric computation have effect on the probability of decoding error and the complexity of decoding circuits. A detailed case study of RMLD decoder for a (64, 35) Reed-Muller subcode has been done [6].