Гурский Семен Сергеевич, аспирант кафедры «Алгебра и дискретная математика»
344090, г. Ростов-на-Дону, ул. Мильчакова, 8а
Gurskiy, Semen S., undergraduate student of the Algebra and Discrete Mathematics Department
8a, Milchakova St., Rostov-on-Don, 344090
Могилевская Надежда Сергеевна, доцент кафедры «Алгебра и дискретная математика» , кандидат технических наук, доцент
344090, г. Ростов-на-Дону, ул. Мильчакова, 8а
Mogilevskaya, Nadezhda S., associative professor of the Algebra and Discrete Mathematics Department, Cand.Sci. (Eng.), associate professor
8a, Milchakova St., Rostov-on-Don, 344090
Introduction. In all types of digital communication, error control coding techniques are used. Many digital communication standards, such as Wi-Fi and 5G, use low density parity check (LDPC) codes. These codes are popular because they provide building encoders and decoders with low computational complexity. This work objective is to increase the error correcting capability of the well-known bit-flipping decoder (BF) of LDPC-codes. For this purpose, a modification of the decoder is built, which enables to dynamically control one of its main parameters whose choice affects significantly the quality of decoding.
Materials and Methods. The well-known bit-flipping decoder of binary LDPC-codes is considered. This decoder has several parameters that are not rigidly bound with the code parameters. The dependence of the decoding quality on the selection of the output parameters of the bit-flipping decoder was investigated through simulation modeling. It is shown that the decoding results in this case are significantly affected by the input parameter of the decoder — threshold T. A modification of the BF-decoder of binary LDPC-codes has been developed, in which it is proposed to set the threshold dynamically during the execution of the algorithm depending on the error rate. A comparative analysis of the error- correcting capability of decoders is carried out by the simulation modeling method.
Results. A lemma on the maximum value of the decoder threshold T is formulated and proved. Upper bounds for the number of operations are found for the original and modified decoders. A simulation model that implements a digital noise-immune communication channel has been built. In the model, the initial data is encoded with a given LDPC-code, then it is made noisy by additive uniformly distributed errors, and thereafter, it is decoded in turn by the bit-flipping algorithm with different threshold T parameters, as well as by a modified decoder. Based on the input and output data, the correction capacity of the decoders used is estimated. Experiments have shown that the error-correcting capability of the modified decoder in the range of the real error rate is higher than that of the original decoder, regardless of the selection of its parameters.
Discussion and Conclusions. The lemma, proved in the paper, sets the upper bound on the threshold value in the original decoder, which simplifies its adjustment. The developed modification of the decoder has a better error- correcting capability compared to the original decoder. Nevertheless, the complexity of the modification is slightly increased compared to the original algorithm. It has been pointed out that the decoding quality of a modified decoder develops with a decrease in the number of cycles in the Tanner graph and an increase in the length of the code.
Введение. Во всех видах цифровой связи применяются методы помехоустойчивого кодирования. Во многих стандартах цифровой связи, например вай-фай (англ. Wi-Fi) и 5G, используются коды с низкой плотностью проверок на четность. Эти коды популярны потому, что для них возможно построение кодеров и декодеров с невысокой вычислительной сложностью. Цель настоящей работы — повышение корректирующей способности известного битфлиппинг-декодера (англ. bit-flipping, BF) LDPC-кодов. Для этого строится модификация декодера, позволяющая динамически управлять одним из его основных параметров, выбор которого существенно влияет на качество декодирования.
Материалы и методы. Рассмотрен известный декодер bit-flipping двоичных LDPC-кодов. Некоторые его параметры не имеют жесткой связи с параметрами кода. С помощью имитационного моделирования исследована зависимость качества декодирования от выбора выходных параметров декодера bit-flipping. Показано, что на результаты декодирования в этом случае существенно влияет входной параметр декодера — порог 𝑇. Разработана модификация BF-декодера двоичных LDPC-кодов, в которой предлагается задавать порог динамически во время выполнения алгоритма в зависимости от степени повреждения кодового слова ошибками. Проведен сравнительный анализ корректирующей способности декодеров методом имитационного моделирования.
Результаты исследования. Сформулирована и доказана лемма о максимальном значении порога 𝑇 декодера. Найдены верхние оценки для количества операций оригинального и модифицированного декодеров. Построена имитационная модель, реализующая цифровой помехоустойчивый канал связи. В модели исходные данные кодируются заданным LDPC-кодом, зашумляются аддитивными равномерно распределенными ошибками, а затем поочередно декодируются алгоритмом bit-flipping с различными параметрами порога 𝑇 и модифицированным декодером. По входным и выходным данным оценивается корректирующая способность использованных декодеров. Эксперименты показали, что в диапазоне реального уровня ошибок корректирующая способность модифицированного декодера выше, чем у оригинального, вне зависимости от выбора его параметров.
Обсуждение и заключения. Доказанная в работе лемма устанавливает верхнюю границу значения порога в оригинальном декодере, что облегчает его настройку. По сравнению с оригинальным декодером разработанная модификация способна лучше исправлять ошибки. При этом сложность модификации увеличена незначительно по сравнению с оригинальным алгоритмом. Отмечено, что качество декодирования модифицированным декодером растет при увеличении длины кода и уменьшении количества циклов в графе Таннера, соответствующего проверочной матрице кода.
The authors declare that there are no conflicts of interest present.