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