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

Turbo码和Turbo译码算法由于其良好的纠错能力，作为21世纪可靠通信和积累技术的重要技术，近年来在纠错码研究领域受到了极大的关注。众所周知，包括Turbo译码算法在内的迭代译码算法可以看作是信任传播算法的应用，它是在知识信息处理研究领域中提出的不确定推理算法。研究表明，Turbo译码算法能有效地计算后验概率的近似，得到了2000-2002年科研资助项目《基于不确定推理的可靠迭代译码算法的分析与设计》中的扩展连接图(EJG)和计算后验概率的并行迭代算法，与现有的信任传播算法相比，它能够处理一般的概率模型，并且在图有环的情况下仍能保持更高的性能(几乎所有的实用代码都有环)。(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.