Аннотация:В системах хранения и передачи информации актуальна проблема защиты данных от искажений в зашумленных каналах, которая решается применением помехоустойчивого кодирования. В данной области хорошо себя зарекомендовали коды с малой плотностью проверок на четность (LDPC). В основе любого линейного кода лежит двудольный граф, называемый графом Таннера (матрица смежности которого совпадает с проверочной матрицей линейного кода). График зависимости вероятности ошибки декодирования от уровня шума является показателем качества кода. Качество матрицы зависит от наличия в ней подграфов определенного вида - так называемых «ловушек» (trapping set). Чем ниже обхват графа (минимальная длина цикла), тем более опасные «ловушки» встречаются в графе Таннера. Задача поиска в графе подрафа изоморфного данному является сложной и в настоящее время лучшие матрицы оптимизируются на вычислительных кластерах неделями. Готовая матрица записывается в устройство, а память, предназначенная для хранения матриц, составляет значительную часть схемы декодера.
Кириллом был предложен алгоритм, который позволяет с линейной сложностью строить семейство графов Таннера обхвата не менее 8. В виду простоты построения матрицы, есть возможность не хранить саму матрицу в памяти устройства, а генерировать ее на месте при необходимости. На основе алгоритма Кириллом была составлена программа на ЭВМ для получения таблиц смежности графов семейства.