Министерство образования и наук
и Российской Федерации
МОСКОВСКИЙ ФИЗИКО-ТЕХНИЧЕСКИЙ ИНСТИТУТ
(ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ)
На правах рукописи
КОБОЗЕВА ИРИНА ГЕННАДЬЕВНА
Исследование сигнально-кодовых конструкций на
основе обобщенных кодов с локализацией ошибок
05.13.17 – Теоретические основы информатики
АВТОРЕФЕРАТ
диссертации на соискание учёной степени кандидата физико-математических наук Москва – 2013
Работа выполнена в Федеральном государственном бюджетном учреждении науки Институте проблем передачи информации им. А.А.
Харкевича Российской академии наук (ИППИ РАН).
Научный руководитель: доктор технических наук, Зяблов Виктор Васильевич
Официальные оппоненты: доктор технических наук Федоренко Сергей Валентинович, эксперт в ООО «Техкомпания Хуавэй»;
кандидат физико-математических наук Владимиров Сергей Михайлович, инженер программист в ООО «Одноклассники»
Ведущая организация: Санкт-Петербургский государственный университет аэрокосмического приборостроения
Защита состоится 16 декабря 2013 г. в 13.30 на заседании диссертационного совета Д 212.156.04 при Федеральном государственном автономном образовательном учреждении высшего профессионального образования «Московском физико-техническом институте (государственном университете)» по адресу: 141700, г. Долгопрудный, Московская обл., Институтский пер., д. 9, ауд. 204.
С диссертацией можно ознакомиться в библиотеке МФТИ (ГУ).
Автореферат разослан 15 ноября 2013 г.
Ученый секретарь диссертационного совета, к. ф.-м. н. Стрыгин Л. В.
Общая характеристика работы
История кодирования началась в 1948 г. с публикацией знаменитой статьи К. Шеннона «Математическая теория связи». Шеннон показал, что с любым каналом передачи данных связано измеряемое в битах в секунду и называемое пропускной способностью канала число C. Если требуемая от системы связи скорость передачи информации R (измеряемая в битах в секунду) меньше С, то, используя исправляющие ошибки коды, для данного канала можно построить такую систему связи, что вероятность ошибки на выходе будет сколь угодно мала. В самом деле, понятно, что построение очень хороших каналов является сложной задачей; экономически гораздо выгоднее использовать кодирование. Шеннон, однако, не указал, как найти подходящие коды, а лишь доказал их существование.
С тех пор, течение более чем 60 лет, прошедших с момента появления кодов, исправляющих ошибки, наблюдается устойчивый рост требований к их корректирующим свойствам, и предлагаются новые, все более сложные кодовые конструкции. В последнее годы требования к качеству передаваемой информации еще более ужесточились (вероятность ошибки декодирования порядка 10-12 и менее). Кроме того, из-за очень высокой скорости передачи данных необходимыми условиями также являются использование методов кодирования и декодирования, требующих относительно малое количество вычислений на бит передаваемой информации, а также возможность параллельных вычислений при кодировании и декодировании. В свою очередь, при высокой кратности модуляции, обеспечивающей большую скорость передачи, более целесообразно использовать недвоичные коды, которые имеют лучшую корректирующую способность по сравнению с двоичными кодами с той же избыточностью.
Можно выделить несколько классов кодов, позволяющих построить длинный код с хорошей корректирующей способностью. Обычно это каскадные коды или МПП-коды. Среди этих кодов особое место занимает подкласс обобщенных каскадных кодов, а именно обобщенные коды с локализацией ошибок (далее обозначены как ОЛО-коды), которые и являются основным предметом исследований в данной работе. В работе будут исследованы две разновидности ОЛО-кодов – обычные ОЛО-коды (в дальнейшем, чтобы избежать путаницы, обозначены как ОЛО-2 коды) и их новая трехмерная разновидность (далее обозначены как ОЛО-3 коды).
Цели и задачи диссертационной работы Цель диссертационной работы состоит в исследовании методов повышения защиты от помех и увеличения пропускной способности информационных коммуникаций с использованием кодов с локализацией ошибок. Существенной частью работы является исследование свойств кодов с локализацией ошибок, включая предложенную автором усложнённую трёхмерную версию, а также разработка методов, позволяющих аналитически определять оптимальные параметры для ОЛО-2 и ОЛО-3 кодов.
Для достижения поставленных целей были решены следующие задачи:
анализ существующих способов кодирования и декодирования обобщенными кодами с локализацией ошибок;
разработка алгоритмов кодирования/декодирования ОЛО-3 кодов;
разработка методов выбора оптимальных параметров для ОЛО-2 и ОЛО- кодов, позволяющих найти код с максимальной скоростью передачи при заданных входной и выходной вероятностях ошибки.
Научная новизна работы Предложена модификация обобщенных кодов с локализацией ошибок – а именно, трехмерные обобщенные коды с локализацией ошибок.
Для трехмерных обобщенных кодов с локализацией ошибок были разработаны алгоритмы кодирования и декодирования.
Разработан теоретический метод расчёта вероятности неправильного декодирования для ОЛО-2 и ОЛО-3 кодов, позволяющий выбрать оптимальные параметры кода для известного канала передачи, а также оценить вероятность неправильного декодирования для хороших условий переда-