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