Application and Analysis of Parallel Iterative Algorithms for Calculating Posterior Probability to Practical Codes and Channels

Turbo码及其译码算法作为21世纪可靠通信与积累技术的重要技术，在纠错码研究领域中被提出，由于其良好的纠错能力，近年来受到了广泛的关注。已经知道，包括Turbo译码算法在内的迭代译码算法可以看作是信念传播算法的应用，信念传播算法是在知识信息处理研究领域作为不确定推理算法提出的。可以解释为turbo解码算法有效地计算了后验概率的近似值。得到了扩展结图（EJG）和计算后验概率的并行迭代算法，这是2000-2002年度科研资助项目“基于不确定推理的可靠迭代译码算法的分析与设计”的成果；与现有的信念传播算法相比，可以处理一般概率模型，即使图有循环（实际代码几乎都有循环）也能保持更高的性能。在本研究中，我们做了以下工作：(1)将EJG和并行迭代算法应用于具有小循环的LDPC码，进一步寻求效率并分析性能。(2)将该算法应用于ARQ方案等具有反馈信道的信道模型，并对其性能进行了分析。(3)将该算法应用于流密码的解密，并对其性能进行了分析。

For its good error correcting ability, Turbo code and Turbo decoding algorithm, which was proposed in the research area of the error correcting codes, have gotten a lot of attention recently as important technology of 21st century's reliable communication and accumulation technique. It have been known that the iterative decoding algorithms which includes Turbo decoding algorithm can be regarded as applications of Belief Propagation algorithm, which was proposed in the research area of the knowledge information processing as uncertain reasoning algorithm. It can be interpreted that the turbo decoding algorithm calculates the approximation of posterior probability effectively.It was obtained that the Extended Junction Graph (EJG) and the parallel iterative algorithm for calculating posterior probability, which are results achieved in "The Analysis and Design of the Reliable Iterative Decoding Algorithm based on Uncertain Reasoning" which is supported by Grant-in-Aid for Scientific Research in 2000-2002, can deal with general probabilistic models compared to existing belief propagation algorithm and retain the higher performance even when the graph has loops (almost of the practical codes have loops).In this research, we have done following,(1)We applied the EJG and the parallel iterative algorithm to the LDPC codes which have some small loops, we sought further efficiency and analyzed the performance.(2)We applied the algorithm to the channel models which have feedback channel such as ARQ Scheme and analyzed the performance.(3)Moreover, we applied the algorithm to the decryption of stream cipher and analyzed the performance.