519.6:004 Применение аппроксимации энергии Бете для определения числовых характеристик кодов на графе
Егоров С. И. (Юго-Западный государственный университет (ЮЗГУ)), Сапожников Д. А. (ООО "Т8"), Усатюк В. С. (ООО "Т8")
БЕТЕ ПЕРМАНЕНТ, ПЕРМАНЕНТ, ПСЕВДОКОДОВОЕ СЛОВО, НИЗКОПЛОТНОСТНЫЙ КОД, КОД НА ГРАФЕ, ЭНЕРГИЯ БЕТЕ
doi: 10.18698/2309-3684-2025-1-104115
В работе рассматривается применение Бете-аппроксимации энергии Гиббса для определения перманента матрицы. Проведен анализ зарубежной литературы, включая известные аналитические и численные методы оценки Бете-перманента. Предложен комбинаторный метод определения Бете-перманента при помощи циклического индекса группы симметрии. Также предложен вероятностный метод определения Бете-перманента на основе Якоби-аппроксимации (normalized min-sum) метода распространения доверия (Belief Propagation), позволяющий вычислять перманент с линейной сложностью. Предложен способ применения Бете-перманента для определения псевдокодовых слов протоматрицы низкоплотностного кода.
[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] Усатюк В.С. Построение квазициклических недвоичных низкоплотностных кодов на основе совместной оценки их дистантных свойств и спектров связности. Телекоммуникации, 2016, № 8, c. 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] Усатюк В.С., Егоров С.И. Построение LDPC-кодов с использованием модифицированного метода выборки по значимости Коула. Известия Юго-Западного государственного университета, 2023, т. 27, № 1, с. 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] Усатюк В.С. Определение кодового расстояния недвоичного LDPC-кода блочным методом Коркина-Золотарева. Известия Юго-Западного государственного университета. Серия: Управление, вычислительная техника, информатика. Медицинское приборостроение, 2015, т. 3, № 16, с. 76-85.
[9] Vontobel P. O. The Bethe permanent of a non-negative matrix. IEEE Transac-tions 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] Гантмахер Ф. Р. Теория матриц. Изд. 2-е, доп. Москва, Наука, 1966, 577 с.
Егоров С.И., Сапожников Д.А., Усатюк В.С. Применение аппроксимации энергии Бете для определения числовых характеристик кодов на графе. Математическое моделирование и численные методы, 2025, № 1, с. 104–115.
Скачать статью
Количество скачиваний: 5