Statistical Mechanics Properties of Bernoulli Generator Matrix Codes

MENG Fan-hui; MA Xiao

doi:10.12263/DZXB.20230319

您当前的位置：

首页 >

文章列表页 >

Statistical Mechanics Properties of Bernoulli Generator Matrix Codes

PAPERS | 更新时间：2025-12-11

- Statistical Mechanics Properties of Bernoulli Generator Matrix Codes
- ACTA ELECTRONICA SINICA Vol. 52, Issue 6, Pages: 1869-1877(2024)
- 作者机构：
  
  1.中山大学系统科学与工程学院,广东广州 510006
  2.中山大学计算机学院,广东广州 510006
  3.广东省信息安全技术重点实验室,广东广州 510006
- 作者简介：
- 基金信息：
  
  National Key Research and Development Program of China(2021YFA1000500)
- DOI：10.12263/DZXB.20230319
  CLC： TN911.22
- Received：11 April 2023，
  
  Revised：2023-08-06，
  
  Published：25 June 2024
- 稿件说明：
移动端阅览
孟凡辉,马啸.伯努利生成矩阵码中的统计力学性质[J].电子学报,2024,52(06):1869-1877.

MENG Fan-hui, MA Xiao.Statistical Mechanics Properties of Bernoulli Generator Matrix Codes[J].Acta Electronica Sinica, 2024, 52(06): 1869-1877.
孟凡辉,马啸.伯努利生成矩阵码中的统计力学性质[J].电子学报,2024,52(06):1869-1877. DOI：10.12263/DZXB.20230319

MENG Fan-hui, MA Xiao.Statistical Mechanics Properties of Bernoulli Generator Matrix Codes[J].Acta Electronica Sinica, 2024, 52(06): 1869-1877. DOI：10.12263/DZXB.20230319

摘要

从统计物理的角度，结合自旋玻璃理论与复杂网络理论，系统地研究了伯努利系统低密度生成矩阵码的统计力学性质.首先给出系统低密度生成矩阵码的伯努利构造、编译码框架，并讨论节点度分布以及正规图与Erdös-Rényi（ER）随机图的联系.然后研究自旋玻璃理论框架下的编译码模型、码本与微观构型的关系、空腔方法与消息传递方程，提出针对系统码的种群动力学算法来高效分析其渐近性能.最后提出正规图配置模型（Normal Graph Configuration Model，NGCM）生成具有连接偏好性的正规图，研究异配性对置信传播（Belief Propagation，BP）译码算法性能的影响，并进一步分析其机理.仿真结果表明，种群动力学算法与BP译码算法本质上相同，但前者不局限于某个具体的码，因此在分析码集的渐近性能时更具优势.此外，适当的异配性能够显著提升BP算法在瀑布区的译码性能，获得更低误码率（Bit Error Rate，BER）并且降低译码迭代次数（复杂度）.

Abstract

From the perspective of statistical physics

with the theory of spin glasses and complex networks

this paper systematically studies the statistical mechanics properties of Bernoulli systematic low-density generator matrix codes. First

we introduce Bernoulli construction of the systematic low-density generator matrix codes

encoding and decoding framework

and discuss the distribution of degree as well as the connection between normal graph and Erdös-Rényi (ER) random graphs. Then

we study the encoding and decoding model under the spin glasses theory

the association between codebook and configuration

cavity method and message-passing equation

and propose the population dynamics algorithm for systematic codes to perform asymptotic performance analysis efficiently. Finally

we propose the normal graph configuration model (NGCM) to generate normal graph with connection preference

study the effect of disassortativity on BP decoding performance and analyze the mechanism. The simulation results show that

although the population dynamics is essentially the same as the BP algorithm

the former is not limited to a concrete code

thus having an advantage in asymptotic analysis for code ensemble. In addition

appropriate disassortativity can significantly improve the BP decoding performance in the waterfall region

achieving lower bit error rate (BER) and reducing the iteration number of decoding (hence the complexity).

关键词

Keywords

references

EDWARDS S F , ANDERSON P W . Theory of spin glasses‍ [J ] . Journal of Physics F: Metal Physics , 1975 , 5 ( 5 ): 965 - 974 .

MEZARD M , PARISI G , VIRASORO M . Spin Glass Theory and Beyond [M ] . Singapore : World Scientific , 1986 .

NISHIMORI H . Statistical Physics of Spin Glasses and Information Processing: An Introduction [M ] . Oxford : Oxford University Press , 2001 .

MEZARD M , MONTANARI A . Information, Physics, and Computation [M ] . Oxford : Oxford University Press , 2009 .

SOURLAS N . Spin-glass models as error-correcting codes‍ [J ] . Nature , 1989 , 339 ( 6227 ): 693 - 695 .

RICHARDSON T , URBANKE R . Modern Coding Theory‍ [M ] . New York : Cambridge University Press , 2008 .

KABASHIMA Y , SAAD D . Belief propagation vs. TAP for decoding corrupted messages [J ] . Europhysics Letters , 1998 , 44 ( 5 ): 668 - 674 .

VICENTE R , SAAD D , KABASHIMA Y . Finite-connectivity systems as error-correcting codes [J ] . Physical Review E , 1999 , 60 ( 5 ): 5352 - 5366 .

KABASHIMA Y , MURAYAMA T , SAAD D . Typical performance of Gallager-type error-correcting codes [J ] . Physical Review Letters , 2000 , 84 ( 6 ): 1355 - 1358 .

VICENTE R , SAAD D , KABASHIMA Y . Low-density parity-check codes—A statistical physics perspective [M ] // Advances in Imaging and Electron Physics . Amsterdam : Elsevier , 2003 : 231 - 353 .

MONTANARI A . Tight bounds for LDPC and LDGM codes under MAP decoding [J ] . IEEE Transactions on Information Theory , 2005 , 51 ( 9 ): 3221 - 3246 .

KUDEKAR S , MACRIS N . Sharp bounds for optimal decoding of low-density parity-check codes [J ] . IEEE Transactions on Information Theory , 2009 , 55 ( 10 ): 4635 - 4650 .

MIGLIORINI G , SAAD D . Finite-connectivity spin-glass phase diagrams and low-density parity check codes [J ] . Physical Review E , 2006 , 73 ( 2 ): 026122 .

HUANG H , ZHOU H . Cavity approach to the Sourlas code system [J ] . Physical Review E , 2009 , 80 ( 5 ): 056113 .

AREF V , MACRIS N , VUFFRAY M . Approaching the rate-distortion limit with spatial coupling, belief propagation, and decimation [J ] . IEEE Transactions on Information Theory , 2015 , 61 ( 7 ): 3954 - 3979 .

GIURGIU A , MACRIS N , URBANKE R . Spatial coupling as a proof technique and three applications [J ] . IEEE Transactions on Information Theory , 2016 , 62 ( 10 ): 5281 - 5295 .

BARBIER J , CHAN C L , MACRIS N . Adaptive path interpolation method for sparse systems: Application to a censored block model [J ] . IEEE Transactions on Information Theory , 2021 , 67 ( 4 ): 2093 - 2114 .

MA X . Coding theorem for systematic low density generator matrix codes [C ] // 2016 9th International Symposium on Turbo Codes and Iterative Information Processing (ISTC) . Piscataway : IEEE , 2016 : 11 - 15 .

王翌昕 , 蔡穗华 , 马啸 . 基于SC-LDGM码的随机混合业务传输方案 [J ] . 电子学报 , 2022 , 50 ( 10 ): 2305 - 2310 .

WANG Y X , CAI S H , MA X . A scheme for transmission of random hybrid services based on SC-LDGM codes‍ [J ] . Acta Electronica Sinica , 2022 , 50 ( 10 ): 2305 - 2310 . (in Chinese)

李建东 , 郭凯 , 陈彦辉 . 一种基于之型分量码的系统GLDPC码 [J ] . 电子学报 , 2011 , 39 ( 1 ): 178 - 183 .

LI J D , GUO K , CHEN Y H . Systematic GLDPC codes with zigzag component codes [J ] . Acta Electronica Sinica , 2011 , 39 ( 1 ): 178 - 183 . (in Chinese)

CAI S , LIN W , YAO X , et al . Systematic convolutional low density generator matrix code [J ] . IEEE Transactions on Information Theory , 2021 , 67 ( 6 ): 3752 - 3764 .

BOLLOBÁS B . Random Graphs [M ] . New York : Springer , 1998 .

周海军 . 自旋玻璃与消息传递 [M ] . 北京 : 科学出版社 , 2015 .

ZHOU H J . Spinning Glass and Message Transmission‍ [M ] . Beijing : Science Press , 2015 . (in Chinese)

MÉZARD M , PARISI G . The Bethe lattice spin glass revisited [J ] . The European Physical Journal B - Condensed Matter and Complex Systems , 2001 , 20 : 217 - 233 .

NEWMAN M E J . Assortative mixing in networks [J ] . Physical Review Letters , 2002 , 89 ( 20 ): 208701 .

BARABÁSI A L . Network science [J ] . Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences , 2013 , 371 ( 1987 ): 20120375 .

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

A Dynamic Community Discovery Method via Fusing Node Change Information

Identification of Node Importance Order Structure Based on Multi-Order Neighborhood Contribution of Complex Network

Community Detection in Complex Networks Based on Link Label Propagation

Image Classification Network with Attenuation Disentangling Mechanism

Identification and Migration of Silent Security Patches in Blockchain Systems via Information Fusion

Related Author

CHEN Qi-mai

YU Peng

LIU Xing-yu

CHENG Jun-wei

CHENG Qi-wei

HE Chao-bo

REN Yong-jun

XU Xiang

Related Institution

Vivo Mobile Communication Co., Ltd.

School of Computer Science, South China Normal University

School of Computer Science， Nanjing University of Information Science and Technology

Science and Technology on Information Systems Engineering Laboratory， National University of Defense Technology

School of Economics and Management， Southeast University

⁰