О модификации декодера bit-flipping кодов с низкой плотностью проверок на четность

Введение. Во всех видах цифровой связи применяются методы помехоустойчивого кодирования. Во многих стандартах цифровой связи, например вай-фай (англ. Wi-Fi) и 5G, используются коды с низкой плотностью проверок на четность. Эти коды популярны потому, что для них возможно построение кодеров и декодеров с невысокой вычислительной сложностью. Цель настоящей работы — повышение корректирующей способности известного битфлиппинг-декодера (англ. bit-flipping, BF) LDPC-кодов. Для этого строится модификация декодера, позволяющая динамически управлять одним из его основных параметров, выбор которого существенно влияет на качество декодирования.

Материалы и методы. Рассмотрен известный декодер bit-flipping двоичных LDPC-кодов. Некоторые его параметры не имеют жесткой связи с параметрами кода. С помощью имитационного моделирования исследована зависимость качества декодирования от выбора выходных параметров декодера bit-flipping. Показано, что на результаты декодирования в этом случае существенно влияет входной параметр декодера — порог 𝑇. Разработана модификация BF-декодера двоичных LDPC-кодов, в которой предлагается задавать порог динамически во время выполнения алгоритма в зависимости от степени повреждения   кодового слова ошибками. Проведен сравнительный анализ корректирующей способности декодеров методом имитационного моделирования.

Результаты исследования. Сформулирована и доказана лемма о максимальном значении порога 𝑇  декодера. Найдены верхние оценки для количества операций оригинального и модифицированного декодеров. Построена имитационная модель, реализующая цифровой помехоустойчивый канал связи. В модели  исходные данные кодируются заданным LDPC-кодом, зашумляются аддитивными равномерно  распределенными ошибками, а затем поочередно декодируются алгоритмом bit-flipping  с    различными параметрами порога 𝑇 и модифицированным декодером. По входным и  выходным данным оценивается корректирующая способность использованных декодеров. Эксперименты    показали, что  в диапазоне реального уровня ошибок корректирующая способность  модифицированного декодера выше, чем у оригинального, вне зависимости от выбора его параметров.

Обсуждение и заключения. Доказанная в работе лемма устанавливает верхнюю границу значения порога в оригинальном декодере, что облегчает его настройку. По сравнению с оригинальным декодером разработанная модификация способна лучше исправлять ошибки. При этом сложность модификации увеличена незначительно по сравнению с оригинальным алгоритмом. Отмечено, что качество декодирования модифицированным декодером растет при увеличении длины  кода и уменьшении количества циклов в графе  Таннера, соответствующего проверочной матрице кода.

1. Gallager, R. Low-density parity-check codes / R. Gallager // IRE Transactions on information theory. — 1962. — Vol. 8, no. 1. — P. 21–28.

2. Milicevic, M. Quasi-cyclic multi-edge LDPC codes for long-distance quantum cryptography / M. Milicevic, Ch. Feng, L. M. Zhang [et al.] // NPJ Quantum Information. — 2018. — No. 4 (1). — P. 1–9. DOI: 10.1038/s41534-018-0070-6

3. Chen, P. Rate-Adaptive Protograph LDPC Codes for Multi-Level-Cell NAND Flash Memory / P. Chen, K. Cai, S. Zheng // IEEE Communications Letters. — 2018. Vol. 22, iss. 6. — P. 1112–1115. DOI: 10.1109/LCOMM.2018.2814985

4. Baldi, M. A Post-quantum Key Encapsulation Mechanism Based on QC-LDPC Codes. Post-Quantum Cryptography / M. Baldi, A. Barenghi, F. Chiaraluce [et al.] // PQCrypto 2018 : Lecture Notes in Computer Science. — Cham : Springer, 2018. — Vol. 10786. — P. 3–24. DOI: 10.1007/978-3-319-79063-3_1

5. Maity, R. K. Robust Gradient Descent via Moment Encoding and LDPC Codes / R. K. Maity, R. A. Singh, A. Mazumdar // In: Proc. IEEE International Symposium on Information Theory (ISIT). — Paris : IEEE, 2019. — P. 2734–2738. DOI: 10.1109/ISIT.2019.8849514

6. Li H. Algebra-Assisted Construction of Quasi-Cyclic LDPC Codes for 5G New Radio / Li H, Bai B, Mu X [et al.] // IEEE Access. — 2018. — Vol. 6. — P. 50229–50244. DOI: 10.1109/ACCESS.2018.2868963

7. Cai, Z. Efficient encoding of IEEE 802.11n LDPC codes / Z. Cai, J. Hao, P. H. Tan [et al.] // Electronics Letters. — 2006. — Vol. 42, iss 25. — P. 1471–1472. DOI: 10.1049/el:20063126

8. Колесник, В. Д. Кодирование при передаче и хранении информации / В. Д. Колесник. — Москва : Высшая школа, 2009. — 550 с.

9. Tong Zhang. Joint(3,k)-regular LDPC code and decoder/encoder design // Tong Zhang, K. K. Parhi // IEEE Transactions on Signal Processing. — 2004. — Vol. 52, iss. 4. — P. 1065–1079. DOI: 10.1109/TSP.2004.823508

10. Yang, M. Design of efficiently encodable moderate-length high-rate irregular LDPC codes / M. Yang, W. E. Ryan, Yan Li // IEEE Transactions on Communications. — 2004. — Vol. 52, iss. 4. — P. 564–571.

11. Malema, G. A. Low-Density Parity-Check Codes: Construction and Implementation / G. A. Malema. — University of Adelaide, 2007. — 160 р. URL : https://digital.library.adelaide.edu.au/dspace/bitstream/ 2440/45525/8/02whole.pdf (accessed : 07.06.2020).

12. Etzion, T. Which codes have cycle-free Tanner graphs? / T. Etzion, A. Trachtenberg, A. Vardy // IEEE Transactions on Information Theory. — 2006. — Vol. 52, iss. 9. — P. 4219–4223. DOI: 10.1109/TIT.2006.880060

13. Морелос-Сарагоса, Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / Р. Морелос-Сарагоса. — Москва : Техносфера, 2006. — С. 259–262.

14. Деундяк, В. М. Методы оценки применимости помехоустойчивого кодирования в каналах связи /В. М. Деундяк, Н. С. Могилевская. — Ростов-на-Дону : Изд-во ДГТУ, 2007. — 85 c.

15. Деундяк, В. М. Решение задачи подбора модели источника ошибок в ИС ОПСАПК / В. М. Деундяк, М. А. Жданова, Н. С. Могилевская // Вестник Донского государственного технического университета. — 2017. — № 17 (4). — С. 107–115. DOI: 10.23947/1992-5980-2017-17-4-107-115

16. Деундяк, В. М. Имитационная модель цифрового канала передачи данных и алгебраические методы помехоустойчивого кодирования / В. М. Деундяк, Н. С. Могилевская // Вестник Донского государственного технического университета. — 2001. — № 1 (1). — С. 98–104.