ИСТИНА

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