Decoding Algorithm of Low-density Parity-check Codes based on Bowman-Levin Approximation
Decoding Algorithm of Low-density Parity-check Codes based on Bowman-Levin Approximation
复制标题
DOI：
10.1007/s00354-008-0069-1
复制
发表时间：
2009-11
影响因子：
2.6
通讯作者：
K. Tamura;Miho Komiya;Masato Inoue;Y. Kabashima
中科院分区：
文献类型：
--
作者：
K. Tamura;Miho Komiya;Masato Inoue;Y. Kabashima
信念传播（BP）和凹凸过程（CCCP）是利用贝特自由能作为代价函数来解决信息处理任务的算法。我们开发了一种新的算法，它同样使用贝特自由能，但改变了主变量和从变量的角色。这在统计物理领域被称为鲍曼-列文近似。当我们在加性高斯白噪声（AWGN）信道上应用BL近似解码常规低密度奇偶校验（LDPC）码时，其平均性能与BP或CCCP大致相似，但如果计算成本不高，则性能略优于它们。这意味着我们基于BL近似的算法可以成功地应用于BP或CCCP已经应用过的其他问题。我们还发现，BL算法的解码动态特别依赖于内循环的数量。这些与BP的不同可能对理解贝特自由能的复杂情况很重要。
Belief propagation (BP) and the concave-convex procedure (CCCP) are algorithms that use the Bethe free energy as a cost function and are used to solve information processing tasks. We have developed a new algorithm that also uses the Bethe free energy but changes the roles of the master and slave variables. This is called the Bowman-Levin (BL) approximation in the domain of statistical physics. When we applied the BL approximation to decode the regular low-density parity-check (LDPC) codes over an additive white Gaussian noise (AWGN) channel, its average performance was roughly similar to that of either BP or CCCP, but slightly outperforms them if the vast calculation cost is not prohibitive. This implies that our algorithm based on the BL approximation can be successfully applied to other problems to which BP or CCCP have already been applied. We also found that the decoding dynamics of the BL algorithm particularly depend on the number of inner loops. These differences from BP may be important in understanding the complicated landscape of the Bethe free energy.