Methods of information systems synthesis

Abstract

This paper presents a detailed analysis of the problem of constructing encoders for linear block codes, with a special emphasis on low-density parity-check (LDPC) codes. The aim of this paper is to provide a comprehensive description of the mathematical methods for the transition from the verification matrix to the efficient coding process. Both classical linear algebra approaches and specialized methods for sparse matrices. Results. The fundamental algebraic constructions underlying the duality between the generating and checking matrices over Galois fields, in particular GF (2), are considered. The classical Gaussian exclusion method for systematic coding is analyzed in detail and its shortcomings in the context of LDPC codes, related to the fill in phenomenon and loss of sparsity, are revealed. The central place in the study is occupied by the Approximate Lower Triangulation method proposed by Richardson and Urbanky, which allows achieving linear coding complexity. The article contains a detailed description of matrix preprocessing algorithms, mathematical derivation of formulas for calculating parity bits, as well as an analysis of quasicyclic constructions used in modern telecommunications standards (5G, Wi-Fi). Full numerical examples of transformations for low-dimensional codes and a detailed analysis of the LDPC encoder architecture are given. Conclusion. The solution was to abandon the explicit use of the generating matrix in favor of approximate triangulation methods of the check matrix and the use of quasicyclic structures, which has become standard in 5G and Wi-Fi. The integration of algebraic-geometric methods opens up new prospects for creating codes with specified properties.

У цій статті подано детальний аналіз задачі побудови кодерів для лінійних блокових кодів із особливим акцентом на коди з низькою щільністю перевірок парності (LDPC). Метою роботи є надання всебічного опису математичних методів переходу від перевірочної матриці до ефективного процесу кодування. Розглядаються як класичні підходи лінійної алгебри, так і спеціалізовані методи для розріджених матриць. Результати. Розглянуто фундаментальні алгебраїчні конструкції, що лежать в основі дуальності між породжувальною та перевірочною матрицями над Galois fields, зокрема GF(2). Детально проаналізовано класичний метод гаусового виключення для систематичного кодування та виявлено його недоліки в контексті LDPC-кодів, пов'язані з явищем "заповнення" (fill-in) і втратою розрідженості. Центральне місце в дослідженні займає метод наближеної нижньої триангуляції, запропонований Tom Richardson та Rüdiger Urbanke, який дозволяє досягти лінійної складності кодування. Стаття містить детальний опис алгоритмів попередньої обробки матриць, математичне виведення формул для обчислення бітів парності, а також аналіз квазіциклічних конструкцій, що використовуються в сучасних телекомунікаційних стандартах, таких як 5G та Wi-Fi. Наведено повні числові приклади перетворень для кодів малої розмірності та детальний аналіз архітектури LDPC-кодера. Висновки. Рішенням стало відмовлення від явного використання породжувальної матриці на користь методів наближеної триангуляції перевірочної матриці та застосування квазіциклічних структур, що стало стандартом у 5G і Wi-Fi. Інтеграція алгебро-геометричних методів відкриває нові перспективи для створення кодів із заданими властивостями.