519.6:004 Application of Bethe energy approximation to determine the numerical characteristics of codes on a graph structures
Egorov S. I. (South-West State University), Sapozhnikov D. A. (LLC "T8"), Usatyuk V. S. (LLC "T8")
BETHE PERMANENT, PERMANENT, PSEUDO-CODE WORD, LOW-DENSITY CODE, GRAPH CODE, BETHE ENERGY
doi: 10.18698/2309-3684-2025-1-104115
The paper considers the application of the Bethe approximation of the Gibbs energy to determine the matrix permanent. An analysis of foreign literature in the area under consideration was carried out. A combinatorial method for determining the Bethe permanent using the cyclic index of the symmetry group is proposed. A probabilistic method for determining the Bethe permanent is also proposed based on the Jacobi approximation (normalized min-sum) of the Belief Propagation method, which allows calculating the permanent with linear complexity. A method for using the Bethe permanent to determine pseudocode words of the protomatrix of a low-density code is proposed.
[1] Usatyuk V.S., Egorov S.I. Hyper neural network as the diffeomorphic domain for short code soft decision beyound belief propagation decoding problem, 2020 2020 IEEE East-West Design & Test Symposium (EWDTS), pp. 1-6.
[2] Mézard M., Montanari A. Information, Physics, and Computation. Oxford, Oxford University Press, 2009, 569 p.
[3] Shannon C. E. A Mathematical Theory of Communication. Bell System Technical Journal, 1948, vol. 27, no. 4, pp. 623–656.
[4] Usatyuk V. S. Postroenie kvaziciklicheskih nedvoichnyh nizkoplotnostnyh kodov na osnove sovmestnoj ocenki ih distantnyh svojstv i spektrov svyaznosti [Construction of quasi-cyclic non-binary low-density codes based on a joint assessment of their distance properties and connectivity spectra]. Telekommunikacii [Telecommunications], 2016, no. 8, pp. 32-40.
[5] Usatyuk V. S. Low error floor QC-LDPC codes construction using modified cole's trapping sets enumerating. IEEE, 2023, pp. 1-6. DOI: 10.1109/DSPA57594.2023.10113442
[6] Usatyuk V.S., Egorov S.I. Constructing LDPC codes using the modified Cole significance sampling method. Proceedings of the Southwest State University, 2023, vol. 27, no. 1, pp. 92-110.
[7] Usatyuk V., Egorov. S., Svistunov G. Construction of length and rate adaptive met QC-LDPC codes by cyclic group decomposition. IEEE East-West Design & Test Symposium (EWDTS), 2019, pp. 1-5
[8] Usatyuk V.S. Determination of the code distance of a non-binary LDPC code using the Korkin-Zolotarev block method. Proceedings of the Southwest State University. Series: IT Management, Computer Science, Computer Engineering. Medical Equipment Engineering, 2015, vol. 3, no. 16, pp. 76-85.
[9] Vontobel P. O. The Bethe permanent of a non-negative matrix. IEEE Transactions on Information Theory, 2013, vol. 59, pp. 1866–1901.
[10] Huang Y., Vontobel P.O. Bounding the Permanent of a Non-negative Matrix via its Degree- M Bethe and Sinkhorn Permanents. IEEE International Symposium on Information Theory (ISIT), 2023, pp. 2774-2779.
[11] Vontobel P. O. Connecting the Bethe entropy and the edge zeta function of a cycle code. IEEE International Symposium on Information Theory, 2010, pp. 704-708. DOI: 10.1109/ISIT.2010.5513594.
[12] Huang Y., Vontobel P.O. On the Relationship Between the Minimum of the Bethe Free Energy Function of a Factor Graph and Sum-Product Algorithm Fixed Points, IEEE Information Theory Workshop (ITW), 2022, pp. 666-671. DOI: 10.1109/ITW54588.2022.9965874.
[13] Kit Shing NG, Vontobel P.O. Double-cover-based analysis of the Bethe permanent of non-negative matrices. IEEE Information Theory Workshop (ITW), 2022, pp.672-677.
[14] Roxana Smarandache. Pseudocodewords from Bethe permanents. IEEE International Symposium on Information Theory, 2013.
[15] Roxana Smarandache. Pseudocodewords from Bethe permanents. ISIT, 2013, pp. 2059-2063
[16] Huang B., Jebara T. Approximating the permanent with Belief propagation. Journal of machine learning research, 2013, vol. 14, pp. 2029-2066.
[17] Straszak D., Vishnoi N.K. Belief Propagation, Bethe Approximation and Polynomials. IEEE Transactions on Information Theory, 2019, vol. 65, no. 7, pp. 4353-4363. DOI:10.1109/ALLERTON.2017.8262801.
[18] Anari N., Rezaei A. A Tight Analysis of Bethe Approximation for Permanent. SIAM Journal on Computing, 2021. https://doi.org/10.1137/19M1306142
[19] Gantmaher F. R. Teoriya matric. Izd. 2-e [Theory on matrices. 2nd Ed.]. Moscow, Nauka Publ., 1966, 577 p.
Егоров С.И., Сапожников Д.А., Усатюк В.С. Применение аппроксимации энергии Бете для определения числовых характеристик кодов на графе. Математическое моделирование и численные методы, 2025, № 1, с. 104–115.
Download article
Количество скачиваний: 205