Введение к работе
Актуальность темы
Теория кодирования возникла в конце сороковых годов с появлением работ Шеннона, Голея и Хэмминга. Задача помехоустойчивого кодирования имеет широкое практическое применение в повседневной жизни, в организационных и технических системах, в первую очередь, в системах связи, где надёжность является одним из приоритетных свойств. При передаче данных по каналу связи на передаваемые сигналы неминуемо воздействует шумы и помехи, препятствующие правильному приёму данных. Этот факт вызвал развитие теории помехоустойчивого кодирования, которая направлена на создание методов преобразования информации, позволяющих обнаруживать и исправлять ошибки, возникающие при прохождении сигнала по каналу передачи, повышая надёжность системы связи.
Для борьбы с помехами разработан класс помехоустойчивых кодов, позволяющих обнаруживать и исправлять ошибки в сообщниях, которые возникают при передаче по каналам связи. Эти коды строятся таким образом, что для передачи сообщения используется лишь ограниченное подмножество всех возможных по структуре кодовых слов. Они отличаются друг от друга более, чем в одном символе, и называются разрешенными. Все остальные кодовые слова относятся к числу запрещенных и не используются, т.к. их появление означает наличие ошибки. Таким образом, искусственная избыточность кодового слова относительно исходного сообщения является фактором, обеспечивающим в дальнейшем при декодировании возможность восстановления ошибок, вносимых каналом связи. Помехоустойчивые коды применяются в таких областях как системы цифровой и сотовой связи, а также в системах преобразования, хранения и накопления информации, в том числе на магнитных и оптических носителях.
При реализации процесса кодирования используется два принципиально различающихся два подхода: поточный и блочный. С развитием вычислительной техники блочное кодирование практически вытеснило поточный (побитовый) подход. Одним из перспективных классов блочных помехоустойчивых кодов являются коды Рида-Маллера. Несмотря на их давнее происхождение (1954 г.) коды Рида-Маллера и постоянные исследования в области помехоустойчивого кодирования, данные коды продолжают активно исследоваться и успешно применяются во многих областях техники, конкурируя с более сложными кодами за счёт простоты реализации и надёжности алгоритма. Поэтому в настоящее время активно разрабатываются новые и совершенствуются уже существующие декодеры кодов Рида-Маллера. Совершенстование осуществляется по таким направлениям, как увеличение числа исправляемых ошибок и наделение декодера новыми
свойствами. Последнее, например, может быть связано с использованием современного списочного подхода к декодированию.
Не так давно было предложено новое перспективное направление применения помехоустойчивых кодов. Было предложено использовать методы теории помехоустойчивого кодирования для построения новых систем защиты передаваемой информации. Появились шифросистемы с открытым ключом и схемы электронной цифровой подписи, основанные на помехоустойчивых кодах. Среди такого класса шифросистем особое место занимают шифросистемы Мак-Элиса и Нидеррайтера, которые будучи построенными с применением кодов Рида-Маллера, на данное время являются одними из наиболее криптостойких.
Таким образом диссертационная работа посвящена решению актуальной научно-технической проблемы, связанной с исследованием особенностей помехоустойчивых кодов Рида-Маллера, анализом существующих алгоритмов декодирования и повышением корректирующей способности кодов за счет разработки новых методов и алгоритмов декодирования.
Цель и основные задачи диссертационной работы
Основной целью диссертации является повышение корректирующей способности процедуры вероятностного декодирования кодов Рида-Маллера.
Системные исследования выявили, что для достижения поставленной цели необходимо решить следующие научные и экспериментально-практические задачи:
-
Теоретическое и экспериментальное исследование современных вероятностных декодеров кодов Рида-Маллера и выявление наиболее перспективных из них.
-
Моделирование существующих алгоритмов декодирования, выявление недостатков, их исследование и поиск путей полной или частичной компенсации выявленных недостатков.
-
Исследование информационных признаков и разработка методов анализа структуры кодового слова с целью определения количества наложенных на него ошибок и способов их структурной идентификации и исправления.
-
Исследование и анализ возможностей повышения корректирующей способности кодов Рида-Маллера реализацией комбинированного декодера.
-
Разработка комплекта программных средств реализующих известные и разрабатываемые алгоритмы декодирования кодов Рида-Маллера, предназначенного для практического и научно-исследовательского использования, а также для проведения сравнительных численных экспериментов.
Основные результаты и степень их научной новизны
-
Математическая модель метода декодирования кодов Рида-Маллера по схеме Лоидрю-Саккура, которая позволяет как исследовать свойства данного метода декодирования, так и построить его имитационную модель.
-
Доказанный статистически представительным (более 1000 опытов) экспериментом и аналитическим системным исследованием алгоритма факт низкой степени фактической эффективности (от 20% правильного восстановления, в случае 4-х ошибок, приходящихся на кодовое слово, для кодов Рида-Маллера с параметрами т = 5, г = 2, до
8%, в случае 5-ти ошибок) особого уточняющего шага, заявленного в алгоритме Лоидрю-Саккура.
-
Обоснованный экспериментально более чем на 1000 опытах метод структурной идентификации количества ошибок, наложенных на кодовое слово, отличающий разработанный на его основе алгоритм декодирования от существующих вероятностных декодеров, игнорирующих этап анализа ошибок.
-
Основанный, в отличие от известных методов, на структурном мониторинге, использующем анализ восстанавливаемого кодового слова, метод его побитовой коррекции, позволивший значительно повысить вероятность точного декодирования, а, в отдельных случаях, добиться 100%-го декодирования.
-
Предложен комбинированный алгоритм декодирования кодов Рида-Маллера, впервые использующий мониторинг процесса декодирования и позволяющий гибко варьировать размер получаемого на выходе списка декодированных векторов вплоть до ординарного, эффективность которого подтверждена статистически представительным (более 10000 опытов) экспериментальным исследованием, показавшим, в частности, что даже при вероятности ошибки в канале 0,1 (сильно зашумлённый канал) применение метода комбинированного декодирования снижает её до 0,04, тогда как декодирование алгоритмом Лоидрю-Саккура увеличивает её до 0,15..
Методы исследования. В диссертации применялись методы
математического анализа, исследования операций, математического
моделирования, теории помехоустойчивого кодирования,
математической статистики, теории планирования экспериментов.
Для формирования экспериментально-исследовательской базы разработана программа для ЭВМ «Программное средство декодирования кодов Рида-Маллера модифицированным алгоритмом Лоидрю-Саккура», построенная на основе концепции объектно-ориентированного
программирования. В настоящее время программный продукт находится на регистрации в Роспатенте.
Достоверность результатов исследования достигается за счёт корректного применения методов системного и математического анализа, моделирования, исчерпывающей статистической обработки результатов. Проведено большое количество имитационных экспериментов, результаты которых использованы для получения статистически достоверных данных. Общий объем имитационно-численных экспериментов, проведенных при решении различных задач и вариациях параметров модели, составил более ю5 опытов. Статистическая достоверность данных обеспечивалась не менее чем 1000 параллельных опытами.
Практическая значимость диссертационной работы. Исследуемые в диссертации методы декодирования помехоуаоичивых кодов Рида-Маллера могут применяться во многих областях. Так, предложенный алгоритм комбинированного декодирования, может использоваться для повышения эффективности декодирования кодов Рида-Маллера при передаче информации по сильно зашумленным каналам. В силу того, что количество возникающих ошибок в канале связи напрямую зависит от мощности приемника/передатчика, а также от дальности связи применение более эффективных алгоритмов декодирования позволит снизить техническую сложность и стоимость таких типов систем связи как системы дальней и спутниковой связи, а также других типов связи, в которых остро стоит вопрос экономии энергии.
Практически значимыми эффектами применения результатов диссертационных исследований являются:
-
введение в практику помехозащищённого кодирования метода логического мониторинга, основанного на структурном анализе кодовых слов, позволяющем оценивать наиболее вероятное число ошибок, искажающих кодовое слово;
-
метод комбинированного декодирования, позволяющий производить безошибочное декодирование (вероятность возникновения ошибки менее Ю-5) кодов Рида-Маллера с параметрами т = 5, г = 2 при вероятности ошибки в канале не более 0,01;
-
применение списочного способа декодирования, используемого в комбинированном методе декодирования позволило существенно (до 80%) повысить вероятность успешного декодирования кодов Рида-Маллера с параметрами т = 5, г = 2 при вероятности ошибки в канале 0,1 по сравнению с алгоритмом Лоидрю-Саккура.
Разработанное для исследований программное обеспечение «Программное средство декодирования кодов Рида-Маллера модифицированным алгоритмом Лоидрю-Саккура» может быть использовано для осуществления автоматизированного проведения имитационных экспериментов.
Результаты работы внедрены в учебный процесс, при изучении кодов Рида-Маллера в рамках курсов «Помехоустойчивое кодирование» и «Теория информации» специальности «Компьютерная безопасность» в Донском государственном техническом университете.
Апробация основных теоретических и практических результатов диссертационной работы
Основные результаты диссертационной работы докладывались и обсуждались на следующих международных научно-технических конференциях: «Математические методы в технике и технологиях -ММТТ-18». - Казань, 2005; «Математические методы в технике и технологиях - ММТТ-19». - Воронеж, 2006; «Математические методы в технике и технологиях - ММТТ-20». - Ярославль, 2007; «Системный анализ, управление и обработка информации». - ДГТУ-ТТИ ЮФУ, 2007; «Математические методы в технике и технологиях - ММТТ-22». - Псков, 2009; 1Х-я Международная научно-техническая конференция «Интеллектуальные системы "09»: Конгресс по интеллектуальным системам и информационным технологиям «AIS-IT'09». - Москва, 2009.
Большинство промежуточных результатов диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского государственного технического университета в 2007-2009 гг.
Публикации по теме диссертационной работы
Основные результаты диссертации опубликованы в 15 работах, из которых 4 - самостоятельные публикации. В 11 работах, опубликованных в соавторстве, доля материалов, принадлежащих автору диссертации, составляет не менее 50%. При этом 3 статьи, одна из которых - самостоятельная публикация, опубликованы в ведущих научных журналах, входящих в список ВАК РФ.
Похожие диссертации на Метод построения комбинированных декодеров кодов Рида-Маллера на основе оперативного мониторинга и побитовой коррекции
