автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Метод построения комбинированных декодеров кодов Рида-Маллера на основе оперативного мониторинга и побитовой коррекции

□□3489182 На правах рукописи

СКОРОБОГАТ ВЛАДИМИР РОМАНОВИЧ

МЕТОД ПОСТРОЕНИЯ КОМБИНИРОВАННЫХ ДЕКОДЕРОВ КОДОВ РИДА-МАЛЛЕРА НА ОСНОВЕ ОПЕРАТИВНОГО МОНИТОРИНГА И ПОБИТОВОЙ КОРРЕКЦИИ

Специальность 05.13.01 - Системный анализ, управление и обработка информации

Автореферат диссертации на соискание учёной степени кандидата технических наук

1 7 ДЕК 200В

Ростов-на-Дону 2009 г.

003489182

Работа выполнена на кафедре «Программное обеспечение вычислительной техники и автоматизированных систем», ФГОУ ВПО «Донской государственный технический университет».

Научный руководитель: доктор технических наук, профессор

Нейдорф Рудольф Анатольевич

Научный консультант:

Официальные оппоненты:

Ведущая организация:

кандидат технических наук, доцент Могилевская Надежда Сергеевна

доктор технических наук, профессор Фатхи Владимир Ахатович

доктор физ.-мат. наук, профессор Пилиди Владимир Ставрович

Федеральное государственное унитарное предприятие Таганрогский научно исследовательский институт связи (ФГУП НИИ Связи), г. Таганрог

Защита состоится «28» декабря 2009 года в «16-00» на заседании диссертационного совета Д 212.058.04 Донского государственного технического университета по адресу:

344000, г. Ростов-на-Дону, пл. Гагарина, 1. ДГГУ ауд. № 252.

С диссертацией можно ознакомиться в библиотеке Донского государственного технического университета.

Автореферат разослан «27» ноября 2009 года.

Отзывы на автореферат в двух экземплярах, заверенные гербовой печатью, просим направлять ученому секретарю диссертационного совета Д 212.058.04.

Учёный секретарь диссертационного совета,кандидат технических наук, доцент

Могилевская Н. С.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

Теория кодирования возникла в конце сороковых годов с появлением работ Шеннона, Голея и Хэмминга. Задача помехоустойчивого кодирования имеет широкое практическое применение в повседневной жизни, в организационных и технических системах, в первую очередь, в системах связи, где надёжность является одним из приоритетных свойств. При передаче данных по каналу связи на передаваемые сигналы неминуемо воздействует шумы и помехи, препятствующие правильному приёму данных. Этот факт вызвал развитие теории помехоустойчивого кодирования, которая направлена на создание методов преобразования информации, позволяющих обнаруживать и исправлять ошибки, возникающие при прохождении сигнала по каналу передачи, повышая надёжность системы связи.

Для борьбы с помехами разработан класс помехоустойчивых кодов, позволяющих обнаруживать и исправлять ошибки в сообщниях, которые возникают при передаче по каналам связи. Эти коды строятся таким образом, что для передачи сообщения используется лишь ограниченное подмножество всех возможных по структуре кодовых слов. Они отличаются друг от друга более, чем в одном символе, и называются разрешенными. Все остальные кодовые слова относятся к числу запрещенных и не используются, т.к. их появление означает наличие ошибки. Таким образом, искусственная избыточность кодового слова относительно исходного сообщения является фактором, обеспечивающим в дальнейшем при декодировании возможность восстановления ошибок, вносимых каналом связи. Помехоустойчивые коды применяются в таких областях как системы цифровой и сотовой связи, а также в системах преобразования, хранения и накопления информации, в том числе на магнитных и оптических носителях.

При реализации процесса кодирования используется два принципиально различающихся два подхода: поточный и блочный. С развитием вычислительной техники блочное кодирование практически вытеснило поточный (побитовый) подход. Одним из перспективных классов блочных помехоустойчивых кодов являются коды Рида-Маллера. Несмотря на их давнее происхождение (1954 г.) коды Рида-Маллера и постоянные исследования в области помехоустойчивого кодирования, данные коды продолжают активно исследоваться и успешно применяются во многих областях техники, конкурируя с более сложными кодами за счёт простоты реализации и надёжности алгоритма. Поэтому в настоящее время активно разрабатываются новые и совершенствуются уже существующие декодеры кодов Рида-Маллера. Совершенстование осуществляется по таким направлениям, как увеличение числа исправляемых ошибок и наделение декодера новыми

свойствами. Последнее, например, может быть связано с использованием современного списочного подхода к декодированию.

Не так давно было предложено новое перспективное направление применения помехоустойчивых кодов. Было предложено использовать методы теории помехоустойчивого кодирования для построения новых систем защиты передаваемой информации. Появились шифросистемы с открытым ключом и схемы электронной цифровой подписи, основанные на помехоустойчивых кодах. Среди такого класса шифросистем особое место занимают шифросистемы Мак-Элиса и Нидеррайтера, которые будучи построенными с применением кодов Рида-Маллера, на данное время являются одними из наиболее криптостойких.

Таким образом диссертационная работа посвящена решению актуальной научно-технической проблемы, связанной с исследованием особенностей помехоустойчивых кодов Рида-Маллера, анализом существующих алгоритмов декодирования и повышением корректирующей способности кодов за счет разработки новых методов и алгоритмов декодирования.

Цель и основные задачи диссертационной работы

Основной целью диссертации является повышение корректирующей способности процедуры вероятностного декодирования кодов Рида-Маллера.

Системные исследования выявили, что для достижения поставленной цели необходимо решить следующие научные и экспериментально-практические задачи:

1. Теоретическое и экспериментальное исследование современных вероятностных декодеров кодов Рида-Маллера и выявление наиболее перспективных из них.

2. Моделирование существующих алгоритмов декодирования, выявление недостатков, их исследование и поиск путей полной или частичной компенсации выявленных недостатков.

3. Исследование информационных признаков и разработка методов анализа структуры кодового слова с целью определения количества наложенных на него ошибок и способов их структурной идентификации и исправления.

4. Исследование и анализ возможностей повышения корректирующей способности кодов Рида-Маллера реализацией комбинированного декодера.

5. Разработка комплекта программных средств реализующих известные и разрабатываемые алгоритмы декодирования кодов Рида-Маллера, предназначенного для практического и научно-исследовательского использования, а также для проведения сравнительных численных экспериментов.

Основные результаты и степень их научной новизны

1. Математическая модель метода декодирования кодов Рида-Маллера по схеме Лоидрю-Саккура, которая позволяет как исследовать свойства данного метода декодирования, так и построить его имитационную модель.

2. Доказанный статистически представительным (более 1000 опытов) экспериментом и аналитическим системным исследованием алгоритма факт низкой степени фактической эффективности (от 20% правильного восстановления, в случае 4-х ошибок, приходящихся на кодовое слово, для кодов Рида-Маллера с параметрами т = 5, г = 2, до 8%, в случае 5-ти ошибок) особого уточняющего шага, заявленного в алгоритме Лоидрю-Саккура.

3. Обоснованный экспериментально более чем на 1000 опытах метод структурной идентификации количества ошибок, наложенных на кодовое слово, отличающий разработанный на его основе алгоритм декодирования от существующих вероятностных декодеров, игнорирующих этап анализа ошибок.

4. Основанный, в отличие от известных методов, на структурном мониторинге, использующем анализ восстанавливаемого кодового слова, метод его побитовой коррекции, позволивший значительно повысить вероятность точного декодирования, а, в отдельных случаях, добиться 100%-го декодирования.

5. Предложен комбинированный алгоритм декодирования кодов Рида-Маллера, впервые использующий мониторинг процесса декодирования и позволяющий гибко варьировать размер получаемого на выходе списка декодированных векторов вплоть до ординарного, эффективность которого подтверждена статистически представительным (более 10000 опытов) экспериментальным исследованием, показавшим, в частности, что даже при вероятности ошибки в канале 0,1 (сильно зашумлённый канал) применение метода комбинированного декодирования снижает её до 0,04, тогда как декодирование алгоритмом Лоидрю-Саккура увеличивает её до 0,15..

Методы исследования. В диссертации применялись методы математического анализа, исследования операций, математического моделирования, теории помехоустойчивого кодирования, математической статистики, теории планирования экспериментов.

Для формирования экспериментально-исследовательской базы разработана программа для ЭВМ «Программное средство декодирования кодов Рида-Маллера модифицированным алгоритмом Лоидрю-Саккура», построенная на основе концепции объектно-ориентированного

программирования. В настоящее время программный продукт находится на регистрации в Роспатенте.

Достоверность результатов исследования достигается за счёт корректного применения методов системного и математического анализа, моделирования, исчерпывающей статистической обработки результатов. Проведено большое количество имитационных экспериментов, результаты которых использованы для получения статистически достоверных данных. Общий объем имитационно-численных экспериментов, проведенных при решении различных задач и вариациях параметров модели, составил более ю5 опытов. Статистическая достоверность данных обеспечивалась не менее чем 1000 параллельных опытами.

Практическая значимость диссертационной работы. Исследуемые в диссертации методы декодирования помехоустойчивых кодов Рида-Маллера могут применяться во многих областях. Так, предложенный алгоритм комбинированного декодирования, может использоваться для повышения эффективности декодирования кодов Рида-Маллера при передаче информации по сильно зашумленным каналам. В силу того, что количество возникающих ошибок в канале связи напрямую зависит от мощности приемника/передатчика, а также от дальности связи применение более эффективных алгоритмов декодирования позволит снизить техническую сложность и стоимость таких типов систем связи как системы дальней и спутниковой связи, а также других типов связи, в которых остро стоит вопрос экономии энергии.

Практически значимыми эффектами применения результатов диссертационных исследований являются:

1. введение в практику помехозащищённого кодирования метода логического мониторинга, основанного на структурном анализе кодовых слов, позволяющем оценивать наиболее вероятное число ошибок, искажающих кодовое слово;

2. метод комбинированного декодирования, позволяющий производить безошибочное декодирование (вероятность возникновения ошибки менее 10"5) кодов Рида-Маллера с параметрами т = 5, г = 2 при вероятности ошибки в канале не более 0,01;

3. применение списочного способа декодирования, используемого в комбинированном методе декодирования позволило существенно (до 80%) повысить вероятность успешного декодирования кодов Рида-Маллера с параметрами т = 5,г = 2 при вероятности ошибки в канале 0,1 по сравнению с алгоритмом Лоидрю-Саккура.

Разработанное для исследований программное обеспечение «Программное средство декодирования кодов Рида-Маллера модифицированным алгоритмом Лоидрю-Саккура» может быть использовано для осуществления автоматизированного проведения имитационных экспериментов.

Результаты работы внедрены в учебный процесс, при изучении кодов Рида-Маллера в рамках курсов «Помехоустойчивое кодирование» и «Теория информации» специальности «Компьютерная безопасность» в Донском государственном техническом университете.

Апробация основных теоретических и практических результатов диссертационной работы

Основные результаты диссертационной работы докладывались и обсуждались на следующих международных научно-технических конференциях: «Математические методы в технике и технологиях -ММТТ-18». - Казань, 2005; «Математические методы в технике и технологиях - ММТТ-19». - Воронеж, 2006; «Математические методы в технике и технологиях - ММТТ-20». - Ярославль, 2007; «Системный анализ, управление и обработка информации». - ДГТУ-ТТИ ЮФУ, 2007; «Математические методы в технике и технологиях - ММТТ-22». - Псков, 2009; IX-я Международная научно-техническая конференция «Интеллектуальные системы "09»: Конгресс по интеллектуальным системам и информационным технологиям «AIS-IT'09». - Москва, 2009.

Большинство промежуточных результатов диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского государственного технического университета в 2007-2009 гг.

Публикации по теме диссертационной работы

Основные результаты диссертации опубликованы в 15 работах, из которых 4 - самостоятельные публикации. В 11 работах, опубликованных в соавторстве, доля материалов, принадлежащих автору диссертации, составляет не менее 50%. При этом 3 статьи, одна из которых - самостоятельная публикация, опубликованы в ведущих научных журналах, входящих в список ВАК РФ.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

Работа состоит из введения, четырех глав, заключения, списка литературы из 110 позиций, а также четырех приложений. Объем основной части - 154 страницы, 27 таблиц, 15 рисунков.

Первая глава диссертации посвящена обзору методов помехоустойчивого кодирования и существующих методов декодирования. В ней определены области применения помехоустойчивых кодов, приведено необходимое математическое описание общей теории помехоустойчивого кодирования и выделенных для исследования кодов Рида-Маллера.

На основании вполне представительного списка литературных источников приведены необходимые сведения по теории помехоустойчивого кодирования, представлена классификация существующих помехоустойчивых кодов и классификация декодеров помехоустойчивых кодов. Анализ достоинств и недостатков различных классов помехоустойчивых кодов позволил выбрать для исследования группу помехоустойчивых блочных линейных двоичных кодов. Особенностью блочных кодов является то, что кодирование и декодирование для них осуществляется в пределах одной кодовой комбинации или блока. Так каждые к, входных

символов кодируются п, выходными символами. В группе линейных

кодов общим свойством является то, что результат применения любых линейных комбинаций над кодовыми словами является кодовым словом.

Выполнен анализ существующих блочных линейных двоичных кодов среди которых выбран класс помехоустойчивых кодов Рида-Маллера. Коды Рида-Маллера (КРМ) являются на данный момент одними из наиболее хорошо изученных семейств кодов. Существенным преимуществом КРМ является то, что они достаточно просто декодируются при помощи мажоритарно-логических устройств. Параметрами КРМ являются натуральные числа т и г, такие, что г<т. Количество гарантированно исправляемых ошибок КРМ составляет f = 2m~r~' -1. Двоичный код Рида-Маллера с параметрами т и г состоит из векторов вида Qf = (/(«[),...,/(я„)), где f{x) - булева функция от т переменных,

порядок нелинейности которой не превосходит г, {a1,...,a„}e.F2m - множество всех двоичных векторов длины т .

Исследование существующих декодеров КРМ выявило перспективное направление, ориентированное на построение вероятностных декодеров, способных восстанавливать ошибки даже за пределами границы гарантированно исправляемого количества ошибок tKp. Показана актуальность задачи разработки декодеров для кодов Рида-Маллера и перспективность ориентации на повышение эффективности вероятностных декодеров этих кодов.

Среди вероятностных декодеров выделен декодер Сидельникова-Першакова и его модификация, предложенная П. Лоидрю и Б. Саккуром, которая ориентирована на улучшение корректирующих способностей исходного декодера. Поэтому принято решение об исследовании этих вероятностных декодеров и о поиске путей дальнейшего улучшения наиболее перспективных из них.

Во второй главе диссертации исследуются существующие методы и алгоритмы вероятностного декодирования Сидельникова-Перашкова (АСП) и Лоидрю-Саккура (АЛС). Проведено экспериментальное сравнительное исследование их как между собой, так и с классическим

алгоритмом Рида. Исследование показало, что при числе ошибок, превышающем значение tKp, мажоритарный декодер практически их не исправляет, а при применении вероятностных алгоритмов также наблюдается появление и значительное увеличение отрицательных результатов декодирования, но не происходит такого лавинообразного уменьшения правильно декодированных слов как при мажоритарном декодировании. Это подтвердило эффективность применения вероятностных алгоритмов. Исследование уточняющего шага алгоритма А/1С показало его дуальность: с одной стороны, наличие, в некоторых случаях, явного эффекта, а с другой - его явную ограниченность в существующем варианте. Это предопределило задачу дальнейшего исследования АЛС и его уточняющего шага с целью поиска методов и алгоритмов дальнейшего повышения эффективности декодирования.

С этой целью была построена и исследована математико-алгоритмическая модель АПС. В построенной модели выделено 4 этапа (у авторов АЛС она разбита на 7 шагов). Основным этапом модели являются первый подготовительный этап:

Пусть Y=(Ya¡,...,YaJ возможно искаженное кодовое слово, с координатами Yai е {-l;l}, где a¡ е F" . На первом подготовительном этапе

производится преобразование пришедшего по каналу возможно искаженного кодового слова (КС) во вспомогательную матрицу D{a) и нахождение п линейных булевых функций. Строками матрицы будут являться векторы a, eF? I Dai(Y) = (Ya¡+a.Yaí,...,Yan+a^_,) .

Задачей 2-го шага является нахождение множества функций С(а), содержащего подмножество функций с1пе(а), обеспечивающих правильное декодирование. Для этого Va, е F" рассматривается набор

т

линейных функций ClJ{x) = YJkijfXl, где kj¡eF2 и - биты дво-

i-i

ичной записи числа j-1. Далее производится вычисление функционала ß(ß(aj),C;())=2]£)(aj,a/)(-l)Cy(a') и нахождение максимумов его

i=i

модуля [ß(-)] = max[ö(ö(a,), С] (-)| для каждого а( i = а также экстремалей С'е(х), доставляющих ему максимум ОД : А/; [б(о(а,), С' ())j= max|g(-|.

На последнем этапе осуществляется расчет кодирующей функции

т

f(x) = f(xv...,xm) = YJaijxixj + Y,aixi+a0, которая своими коэффициента-

i<j /=1

ми однозначно определяет кодовое слово

а = К, я,,...,ат,ап,в|3а1т,а23,...а1т,атА т).

Анализ построенной модели позволил выявить ряд особенностей алгоритма, не отмеченных авторами. Так анализ математических преобразований, совершаемых в АЛС на 2 шаге, позволил обнаружить интересную и перспективную особенность алгоритма, связанную со свойствами экстремалей Се(х). Они являются булевыми функциями, порождающими векторы, которые, в соответствие с правилами их нахождения, декларируемыми АЛС, оказываются наиболее близкими к векторам Da,(Y)

по расстоянию Хемминга. При этом полная совокупность функций С'е(х)

дает вектор-функцию, которая порождает матрицу, наиболее близкую к D(a). Однако исследование показало, что на всем множестве а получаемых на 2-м шаге алгоритма функций-экстремалей Се(х) может оказаться несколько. При этом авторы АЛС не предлагают способа разрешения возникающей коллизии, связанной с многовариантностью решения. Диссертационное исследование позволило выявить два эффективных способа решения вопроса. Первый способ связан с процедурой нахождения всех значений C£t(a,) с использованием для последующего

декодирования всех наборов, что приводит к построению т.н. «списочного» декодера. Второй способ связан с выявлением заведомо неверных значений Сн(а,) и их отбраковкой, что позволяет либо сократить список на выходе декодера, либо свести декодер к унитарному варианту. Оба исхода повышают качество декодирования.

С этой целью была поставлена и решена задача по исследованию свойств начальных шагов АЛС, а также реализации соответствующим образом модифицированного АЛС. Для этого было изучено влияние на структурные свойства кодового слова накладываемых на него ошибок и оценена эффективность преобразований, производящихся на этом этапе модифицированного АЛС.

Для оценки влияния накладываемых ошибок было экспериментально смоделировано влияние ошибок на значения функционалов, вычисляемых в АЛС, для всех значений функций-экстремалей се4(а,). Проведенная статистически представительная серия из 9 экспериментов по 1000 опытов в каждом показала систематичность распределения значений Cei(a,) функций-экстремалей по значениям функционала, которые

можно объединить в структуры, представленные в таблице 1.

Анализ данных в таблице 1, позволили выявить ряд особенностей 2-го шага АЛС и промежуточных результатов его работы.

Так, при <>3 наблюдаемые распределения функций по значениям функционалов не являются постоянными, а могут меняться в зависимости от кодируемого информационного слова и накладываемого на него вектора ошибок. При этом вероятность получения той или иной структуры может быть оценена частотой их появления в эксперименте, гарантированной большим объёмом исследованной выборки.

Помимо этого, видно, что существуют повторяющиеся структуры, например структура 3-1 и 5-2, и это повторение имеет характерную закономерность. А именно, повторяющиеся структуры возникают с шагом количества накладываемых ошибок кратным 2. В структурах для случая < = 8 присутствует структура, совпадающая со структурой, получаемой при количестве накладываемых ошибок / = 0 и имеющая вероятность появления 0,01, что фактически определяет границу для возможного количества исправляемых ошибок на значении 8.

Таблица 1. Значения функционалов для / = о,..,8

О 4 8 12 16 20 24 28 32 Строк Вероят ность

0 31 0 0 0 0 0 0 0 1 32 1,0

1 31 0 0 0 0 0 0 0 1 1 1,0

16 15 0 0 0 0 0 1 0 31

2 31 0 0 0 0 0 0 0 1 2 1,0

24 0 7 0 0 0 1 0 0 30

31 0 0 0 0 0 0 0 1 1

3 16 15 0 0 0 0 0 1 0 3 1,0

16 12 0 3 0 1 0 0 0 28

31 0 0 0 0 0 0 0 1 1

4-1 28 0 0 0 4 0 0 0 0 1

24 0 7 0 0 0 1 0 0 6 0,876

22 0 8 0 2 0 0 0 0 24

4-2 31 0 0 0 0 0 0 0 1 4 0,124

28 0 0 0 4 0 0 0 0 28

31 0 0 0 0 0 0 0 1 1

5-1 16 12 0 3 0 1 0 0 0 15 0,757

16 10 0 6 0 0 0 0 0 16

31 0 0 0 0 0 0 0 1 1

5-2 16 15 0 0 0 0 0 1 0 3 0,243

16 12 0 3 0 1 0 0 0 28

6-1 31 0 0 0 0 0 0 0 1 1

28 0 0 0 4 0 0 0 0 1

1-я О 4 8 12 16 20 24 28 32 Строк Вероят ность

24 0 7 0 0 0 1 0 0 6 0,551

22 0 8 0 2 0 0 0 0 24

31 0 0 0 0 0 0 0 1 1

6-2 16 0 16 0 0 0 0 0 0 1 0,402

22 0 8 0 2 0 0 0 0 30

6-3 31 0 0 0 0 0 0 0 1 2 0,033

24 0 7 0 0 0 1 0 0 30

31 0 0 0 0 0 0 0 1 1

6-4 28 0 0 0 4 0 0 0 0 15 0,014

16 0 16 0 0 0 0 0 0 16

31 0 0 0 0 0 0 0 1 1

7-1 16 12 0 3 0 1 0 0 0 15 0,649

16 10 0 6 0 0 0 0 0 16

31 0 0 0 0 0 0 0 1 1

7-2 16 15 0 0 0 0 0 1 0 3 0,334

16 12 0 3 0 1 0 0 0 28

7-3 31 0 0 0 0 0 0 0 1 1 0,017

16 15 0 0 0 0 0 1 0 31

8-1 31 0 0 0 0 0 0 0 1 4 0,092

28 0 0 0 4 0 0 0 0 28

8-2 31 0 0 0 0 0 0 0 1 2 0,092

24 0 7 0 0 0 1 0 0 30

31 0 0 0 0 0 0 0 1 1

8-3 28 0 0 0 4 0 0 0 0 1 0,640

24 0 7 0 0 0 1 0 0 6

22 0 8 0 2 0 0 0 0 24

31 0 0 0 0 0 0 0 1 1

8-4 28 0 0 0 4 0 0 0 0 15 0,166

16 0 16 0 0 0 0 0 0 16

8-5 31 0 0 0 0 0 0 0 1 32 0,01

Для оценки эффективности преобразований, производящихся на 3-м шаге АЛС, было экспериментально рассчитано (при числе опытов 1000) и проанализировано распределение количества верных значений функций Се4(а,). Результаты эксперимента показали сильную зависимость

эффективности применения этого шага АЛС от параметра т КРМ и числа накладываемых ошибок. Так, в случае параметра т = 5 и ошибок веса 1 = 4 даже при максимально возможном числе голосов мажоритар-

ного голосования вероятность получения верного значения Сек(а,) на

этом шаге составляет 0,76. Удовлетворительные результаты работы этого шага в ходе проведения эксперимента были получены только в случае т = 6 и ошибок кратности / = 9, где вероятность получения верного ответа достигала 0,999, в то время как в случае т = 6 и ошибок веса г = 11 максимум вероятности получения верного значения функции смещался не в зону максимального числа голосов, а в середину ряда значений вероятности, в данном случае - 0,36. Выявленная особенность уточняющего шага АЛС показала его крайне низкую эффективность, особенно при большом числе накладываемых на кодовое слово ошибок, что обусловило задачу его дальнейшей модификации для повышения эффективности декодирования.

В третьей главе диссертации разрабатываются способы модификации АЛС и методы повышения эффективности декодирования кодов Рида-Малера.

Основываясь на полученных во второй главе результатах в третьей главе диссертации детально исследуются свойства структур распределения количества функций по значениям функционалов и структур функций-экстремалей. Для упрощения дальнейшего анализа предложена запись значений структур в виде упорядоченных векторов размерности п/4

= (с/*): \С1.(*)) = 4/, у = 0,.,и-1|,/ = 0,..,и/4 ), которые образуют множество

На основе этого предложен метод побитовой коррекции кодового слова (КС), где У - искаженное кодовое слово, записанное элементами {-1,1}, а 0(а]) - матрица, определяемая на подготовительном этапе

АЛС и зависящая от У .

Эксперименты показали, что по типу наблюдаемых структур может быть определено расстояние Хэмминга между искаженным кодовым словом и некоторым наиближайшим к нему другим кодовым словом кода, а именно, если 31р:51р{У)Г)8(У)Ф0, то /р принимается в качестве расстояния Хэмминга до некоторого наиближайшего кодового слова КРМ, где 5' (У) - набор эталонных структур, получаемых при числе ошибок равном I.

Учитывая перспективы, предлагаемые методикой структурного анализа кодового слова с целью определения предполагаемого числа накладываемых ошибок была поставлена задача построения алгоритма

адаптивном коррекции кодового слова, позволяющего уменьшить число наложенных ошибок.

Пусть искажённое кодовое слово У содержит ошибки в ( разрядах с позициями . Была введена следующая математическая опера-

ция над кодовым словом: К,(У) = У + К, = УЮ, где У - искаженное кодовое слово, Уа - скорректированное кодовое слово, К, - двоичный вектор, содержащий единицу в разряде г, а во всех остальных нули. Очевидно, что исход этой операции относительно количества ошибок, порождённый добавлением к,, может иметь два варианта:

ЫУ) + ,уе[1,г]; (а)

1(У)- 1<-У/ = еу,уе[1,г]. (Ь)

Тогда вариант (а) соответствует ситуации, когда позиция единицы в 1-м разряде вектора К, не совпала с позицией любой из ошибок,

наложенных на КС, и поэтому суммарное число ошибок, наложенных на КС увеличивается. Вариант (Ь) соответствует обратной ситуациии и суммарное количество ошибок, наложенных на кодовое слово уменьшается. Таким образом, применяя операцию К,{-) для каждой

позиции зашумленного КС и анализируя структуры Б(У) с

Г Вход Г, 1у )

вычислением количества ошибок, наложенных на КС, можно уменьшить число ошибок в декодируемом КС

(разумеется, лишь с некоторой верятностью).

На этом факте основан предложенный в диссер-тации метод побитовой коррекции, который для каждого из полученных векторов УК1

вычисляет значения /<2, как наименьшее число ошибок, при котором наблюдалась структура среди эталонного набора, и в случае, если

>

1 Г

Вычисление У*^

Г

Вычислите пруи^р для вектора У^

С

3

Рисунок 1. Схема работы метода побитовой коррекции.

{г < 1тт I гДе Ь ~~ предполагаеомое количество ошибок для вектора У,

то Ую отбрасывается. В противном случае, если ошибок стало меньше,

вектор добавляется в список векторов, получаемых на выходе

алгоритма побитовой коррекции. Схема работы алгоритма побитовой коррекции представлена на рисунке 1.

В работе было проведено экспериментальное исследование зависимости типа структур 5(У), получаемых в результате работы метода побитовой коррекции, от типа структуры изначального кодового слова. Эксперименты проводились для 4 и 5 ошибок, накладываемых на кодовое слово. Для статистической достоверности каждый эксперимент состоял из 1000 опытов. Результаты экспериментов представлены в таблицах 2 и 3.

Таблица 2. Результаты эксперимента для КРМ с параметрами г = 2,т = 5 и количества ошибок 4.

Начальная структура Преобразованные структуры Количество структур Количество опытов

4-1 3-1 8 971

5-1 24

4-2 3-1 32 29

Таблица 3. Результаты эксперимента для КРМ с параметрами г = 2,т = 5 и количества ошибок 5.

Начальная структура Преобразованные структуры Количество структур Количество опытов

5-1 4-1 15 815

6-1 16

6-2 1

3-1 2-1 3 185

4-1 28

4-2 1

На основе представленного метода побитовой коррекции построен алгоритм комбинированного декодирования. Если определенное расстояние Хэмминга между анализируемым искаженным кодовым словом и некоторым наиближайшим соседним кодовым словом не превосходит числа гарантированно исправляемых ошибок кода ), то из теории

помехоустойчивого кодирования известно, что такое кодовое слово будет единственным и может быть получено с помощью любого алгоритма декодирование КРМ. Для всех остальных г'»41 строится алгоритм, реализующих побитовую коррекцию кодового слова, который

осуществляет обработку входного вектора. Алгоритмически, предложенный метод может быть записан следующим образом: Алгоритм KD.

Вход: Возможно искаженное кодовое слово Y кода РМ с параметром г = 2 длины п.

Выход: список декодированных информационных слов a[j].

1. На основе структурного анализа кодового слова вычисляется i = t(Y).

2. Если i<t"p то к списку a[j] добавляется результат декодирования вектора Y, выход.

3. Реализуется цикл по всем р из интервала [1,...,и].

3.1 Инвертируется значение бита Yp.

3.2 Вычисляется t' = t{Y).

3.3 Если f' < I то к списку а[у] добавляется результат работы KD( Y).

3.4 Инвертируется значение бита Yp .

4. Выход.

Описанный алгоритм можно также дополнить вероятностным анализом кодового слова, основываясь на известном распределении вероятности ошибок для двоичного симметричного канала связи с аддитивными независимыми ошибками. Тогда, если ре - средняя вероятность ошибки на бит вероятность pc(t) наложения вектора ошибок веса t на некоторое кодовое слово может быть вычеслена по формуле Vi: Pc(t) = c'n(Pe)'Q-РеУ ■ Помимо этого введены условные вероятности ps{ilj) как вероятности наложения на кодовое слово вектора ошибок веса i при условии, что этому искаженному кодовому слову соответствует структура j в виде

„ ш л - РеИИ)-РС{1)

к

где pE{j/i) - вероятность наблюдения эталонной структуры j при условии, что накладываемое число ошибок равно i.

Четвертая глава диссертации посвящена алгоритмической разработке модели программного средства и реализации программного обеспечения автоматизированного проведения эксприментального моделирования А/1С и разработанного метода комбинированного декодирования.

В рамках диссертационной работы разработано программное обеспечение (ПО) «RM Decoder», удовлетворяющее поставленным требованиям. Программное обеспечение «RM Decoder» предназначено

для проведения вычислительных экспериментов по исследованию эффективности декодирования КРМ анализируемыми алгоритмами и в настоящее время проходит официальную регистрацию в Роспатенте.

С использованием разрабо- Таблица 4. Сравнение алгорит-

танного ПО было проведено мов декодирования АЛС и КД.

эксперим

ентальное исследование метода комбинированного декодирования (КД) на представительной выборке из 10000 опытов. Работа декодера моделировалась на двоичном симметричном канале связи с аддитивными независимыми ошибками с вероятностями ре = 0,001,

Л = 0,002, ре= 0,005, Л =0,01, ре = 0,02 , ре = 0,05 и ре = 0,1. Полученные значения вероятности остаточной ошибки для АЛС и метода комбинированного декодирования представлены в таблице 4. Графически полученные результаты представлены на рисунке 2.

Рисунок 2. Сравнение вероятностей остаточной ошибки комбинированного декодера (пунктирная линия) и алгоритма Лоидрю-Саккура (сплошная линия). В заключение сформулированы основные выводы и результаты диссертационной работы, а именно:

1. Проведенное теоретическое и экспериментальное исследование современных вероятностных декодеров кодов Рида-Маллера выявило наиболее перспективный декодер Лоидрю-Саккура.

Ре Ре, АЛС Ре, КД

0,001 0 0

0,002 0 0

0,005 0 0

0,01 0,00015 0

0,02 0,0014 0,00005

0,05 0,0282 0,00255

0,1 0,16925 0,0399

2. Построены математические модели алгоритмов декодирования, выявившие недостатки существующих алгоритмов, и предложены способы повышения их эффективности декодирования.

3. Получены и исследованы информационные признаки и методы анализа структуры кодового слова, позволяющие определить количество наложенных на него ошибок.

4. Разработан метод комбинированного декодирования кодов Рида-Маллера, позволяющий гибко варьировать длину списка наиболее вероятных информационных слов, получаемых на выходе алгоритма декодирования, вплоть до ординарного.

5. Программно реализованы алгоритмы декодирования кодов Рида-Маллера и показана возможность как практического, так и научно-исследовательского использования.

Таким образом, поставленная в диссертации цель достигнута.

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в ведущих рецензируемых изданиях, рекомендованных ВАК РФ

1. Могилевская Н.С. Экспериментальное исследование декодеров кодов Рида-Маллера второго порядка / Н.С. Могилевская, В.Р. Скоробогат, B.C. Чудаков // Вестник ДГТУ, Т.8 №3(38), 2008. - С. 231-237.

2. Скоробогат В.Р. Математико-алгоритмическая модель Лоидрю-Саккура для кодов Рида-Маллера второго порядка / В.Р. Скоробогат, P.A. Нейдорф // Вестник ДГТУ, Т.9, спец. выпуск. - Ростов н/Д, 2009. - С. 311.

3. Скоробогат В.Р. Экспериментальное исследование уточняющего шага алгоритма декодирования Лоидрю-Саккура кодов Рида-Маллера / В.Р. Скоробогат // Труды Конгресса по интеллектуальным системам и информационным технологиям «AIS-IT09»: сб. науч. тр. / Научное издание в 4-х томах, Т.З. - М.: Физматлит, 2009. - С. 329-332.

Публикации в других изданиях

4. Деундяк В.М. О реализации модифицированной шифросистемы Мак-Элиса, основанной на кодах Рида-Маллера / В.М. Деундяк, В.Р. Скоробогат, Интегро-дифференциальные операторы и их приложения: межвуз. сб. науч. тр. - Ростов н/Д, 2004. - Вып. 6, С. 17-23.

5. Деундяк В.М. О некоторых особенностях криптосистем с открытым ключом, построенных на помехоустойчивых кодах / В.М. Деундяк, Ю.В. Косолапов, В.Р. Скоробогат // Математические методы в технике и

технологиях, - ММТТ-18: сб. тр. XVIII междунар. науч. конф.? В Ют. -Казань, 2005. - Т.8, - С. 163-164

6. Скоробогат В.Р. О программной реализации схемы электронной цифровой подписи в случае кодов Рида-Маллера / В.Р. Скоробогат // Математические методы в технике и технологиях, - ММТТ-19: сб. тр. XIX междунар. науч. конф.: В Ют. - Воронеж, 2006. -Т.Ю, С. 190-192.

7. Скоробогат В.Р. Программная реализация алгоритма декодирования Лоидрю-Саккура для кодов Рида-Маллера второго порядка / В.Р. Скоро-богат, A.B. Скориков // Математические методы в технике и технологиях,

- ММТТ-20: сб. тр. XX междунар. науч. конф.: В Ют. - Ярославль, 2007. -Т.6, С. 50-53.

8. Могилевская Н.С. Исследование областей применимости блочных помехоустойчивых кодов / Н.С. Могилевская, В.Р. Скоробогат // Математические методы в технике и технологиях, - XX междунар. науч. конф. Математические методы в технике и технологиях, - Ростов-на-Дону, 2007, С. 236-237.

9. Могилевская Н.С. О проблемах реализации вероятностного алгоритма Лоидрю-Саккура декодирования кодов Рида-Маллера / Н.С. Могилевская, В.Р. Скоробогат // Системный анализ, управление и обработка информации: 1-й межвузовский сборник науч. статей / ДГТУ-ТТИ ЮФУ, 2007. - С.388-393.

10. Могилевская Н.С. Экспериментальное исследование алгоритма декодирования Лоидрю-Саккура кодов Рида-Маллера/ Н.С. Могилевская, В.Р. Скоробогат // Системный анализ, управление и обработка информации: 1-й межвузовский сборник науч. статей / ДГТУ-ТТИ ЮФУ, 2007. - С. 382387.

11. Свидетельство о государственной регистрации программы для ЭВМ № 2008614601. Программа декодирования кодов Рида-Маллера методом Сидельникова-Першакова «RM-Decoder». Авторы: Н.С. Могилевская, В.Р. Скоробогат, B.C. Чудаков. Зарегистрировано в Реестре программ для ЭВМ Федеральной службы по интеллектуальной собственности, патентам и товарным знакам (Роспатент) от 24 сентября 2008 г.

12. Нейдорф P.A. Принципы построения комбинированных декодеров на основе метода побитовой коррекции кодового слова / P.A. Нейдорф, В.Р. Скоробогат // Математические методы в технике и технологиях, - ММТТ-22: сб. трудов XXII Междунар. науч. конф. В 11т. Т.Н. / Международный научно-методический симпозиум «Современные проблемы многоуровневого образования» - Ростов-на-Дону: Донской гос. технич. ун-т, 2009,

- С. 108-113.

13. Скоробогат В.Р. Построение и оптимизация списочного декодера для кодов Рида-Маллера / В.Р. Скоробогат, P.A. Нейдорф // Математические методы в технике и технологиях, - ММТТ-22. сб. тр. XXII междунар. науч. конф.: В Ют, Т. 8. - Псков, 2009. - С. 205-207.

14. Скоробогат В.Р. Алгоритм-мониторинг процесса декодирования для кодов Рида-Маллера второго порядка / Скоробогат В.Р. // Математические методы в технике и технологиях, - ММТТ-22. сб. тр. XXII междунар. науч. конф.: В Ют, Т. 8. - Псков, 2009. - С. 212-214.

15. Скоробогат В.Р. Экспериментальное исследование корректирующих способностей алгоритма декодирования Лоидрю-Саккура / В.Р. Скоробогат // Математические методы в технике и технологиях, - ММТТ-22: сб. трудов XXII Междунар. науч. конф. В 11т. Т.Н. / Международный научно-методический симпозиум «Современные проблемы многоуровневого образования» - Ростов-на-Дону: Донской гос. технич. ун-т, 2009, - С. 113-117.

В работе [1] автору принадлежит разработка декодера Лоидрю-Саккура, постановка эксперимента и обсуждение результатов. В работе [2] автору принадлежит разработка большинства компонентов модели АЛС. В работах [4, 5] автору принадлежит программная реализация шифросистемы Мак-Элиса и построение модели шифросистемы. В работе [7] автору принадлежит постановка задачи исследования и общее руководство работой. В работе [8] автору принадлежит исследование применимости помехоустойчивых кодов в области защиты информации от злоумышленника. В работах [9, 10] автору принадлежит программная реализация АЛС и его экспериментальное исследование. В работе [12] автору принадлежит экспериментальное исследование метода побитовой коррекции и его реализация. В работе [13] автору принадлежит разработка списочного декодера кодов Рида-Маллера на основе АЛС.

В набор 26.11.2009 В печать 27.11.2009

Объем 1 усл.п.л., 1.0 уч.-изд.л. Офсет. Формат 60x84/16. Бумага тип №3. Заказ № 538. Тираж 120.

Издательский центр ДГТУ Адрес университета и полиграфического предприятия: 344000, г.Ростов-на-Дону, пл.Гагарина,!.

ВВЕДЕНИЕ.

ГЛАВА 1. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ И ОБЛАСТИ ЕГО ПРИМЕНЕНИЯ

1.1 Применение кодов, корректирующих ошибки, в задачах обеспечения помехоустойчивости.

1.1.1. Некоторые вехи истории развития теории помехоустойчивого кодирования.

1.1.2 Примеры применения кодов, корректирующих ошибки, в задаче обеспечения помехоустойчивости.

1.1.3 Основные параметры кодов, исправляющих ошибки.

1.1.4 Линейные коды и их свойства.

1.1.5 Сущность алгоритмов кодирования/декодирования линейных кодов и задачи их создания.

1.2 Алгоритмы кодирования для помехоустойчивых кодов и их классификация.

1.2.1 Общая классификация помехоустойчивых кодов.

1.2.2 Классификация кодеров линейных кодов.

1.3 Коды Рида-Маллера.

1.3.1 Общие сведения о кодах Рида-Маллера.

1.3.2 Виды декодеров кодов Рида-Маллера.

1.3.3 Классификация декодеров кодов Рида-Маллера.

1.3.4 Критерии сравнения декодеров кодов Рида-Маллера.

1.4 Декодеры кодов Рида-Маллера.

1.4.1 Классический мажоритарный алгоритм Рида декодирования кодов Рида-Маллера

1.4.2 Алгоритм Сидельникова-Першакова декодирования кодов Рида-Маллера второго и третьего порядка.

1.4.3 Алгоритм П. Лоидрю и Б. Саккура декодирования кодов Рида-Маллера второго порядка.

1.5 Выводы по первой главе.

ГЛАВА 2. ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ ИНФОРМАЦИОННОЙ СТРУКТУРЫ ПОДГОТОВИТЕЛЬНОГО ЭТАПА АЛГОРИТМА ЛОИДРЮ-САККУРА.

2.1 Сравнительное исследование восстановительных свойств алгоритмов декодирования кодов Рида-Маллера.

2.1.1 Сущность проблемы оценки свойств вероятностных декодеров.

2.1.2 Программное обеспечение сравнительного эксперимента декодеров кодов Рида-Маллера.

2.1.3 Методика проведения сравнительного эксперимента.

2.1.4 Предварительная обработка результатов сравнительного эксперимента.

2.1.5 Анализ результатов сравнительного исследования декодеров.

2.1.6 Выводы по результатам сравнительного исследования декодеров.

2.2 Разработка и анализ математической модели алгоритма Лоидрю-Саккура.

2.2.1 Основные объекты и этапы кодирования/декодирования кодов Рида-Маллера

2.2.2 Математическая модель АЛС. Подготовительный этап.

2.2.3 Математическая модель АЛС. Уточняющий этап.

2.2.4 Математическая модель АЛС. Этап восстановления квадратичной части информационного слова.

2.2.5 Математическая модель АЛС. Этап восстановления линейной части информационного слова.

2.2.6 Анализ математической модели алгоритма Лоидрю-Саккура и выводы.

2.3 Экспериментальное исследование структуры пространства кодовых слов и влияния ошибок на информационную структуру АЛС.

2.3.1 Анализ распределения кодовых слов кода Рида-Маллера в векторном пространстве.

2.3.2 Влияние искажения кодового слова на структуру и параметры результатов второго шага AJIC.

2.3.3 Анализ типа распределений функций-экстремалей не искаженного КС, получаемых на втором шаге AJIC.

2.3.4 Анализ влияния ошибок зашумленного кодового слова на структуру совокупности вычисляемых для него функций-экстремалей.

2.4 Экспериментальное исследование уточняющего шага AJIC.

2.4.1 Исследование влияния уточняющего шага алгоритма Лоидрю-Саккура на нахождение правильных функций-экстремалей.

2.4.2 Исследование влияния мажоритарного голосования уточняющего шага AJIC на выбор функций-экстремалей.

2.4.3 Уточнение влияния критериев отбраковки значений функций на вероятность успешного декодирования.

2.4.4 Анализ эффективности процедуры голосования уточняющего шага AJIC.

2.5 Выводы по второй главе.

ГЛАВА 3. ПОСТРОЕНИЕ АЛГОРИТМА КОМБИНИРОВАННОГО ДЕКОДИРОВАНИЯ КОДОВ РИДА-МАЛЛЕРА.

3.1 Структура и возможности общего алгоритма комбинированного декодирования кодов Рида-Маллера.

3.1.1 Анализ возможностей построения алгоритма комбинированного декодирования кодов Рида-Маллера.

3.1.2 Исследование свойств структур распределения количества функций по значениям функционалов и структур функций-экстремалей.

3.1.3 Пример нахождения предполагаемого количества ошибок зашумленного кодового слова КРМ.

3.1.4 Выводы и перспективы применения структурного анализа характеристик накладываемых на кодовое слово ошибок.

3.2 Метод побитовой коррекции искажённого кодового слова.

3.2.1 Анализ возможностей и перспектив методов коррекции кодового слова в задаче исправления ошибок.

3.2.2 Схема работы алгоритма побитовой коррекции кодового слова.

3.2.3 Исследование совокупности структур скорректированных кодовых слов, получаемых методом побитовой коррекции.

3.2.4 Пример корректировки зашумленного кодового слова КРМ методом побитовой коррекции.

3.3 Алгоритм комбинированного декодирования кодов Рида-Маллера.

3.3.1 Вероятностная модель структурного анализа предполагаемого количества накладываемых на КС ошибок.

3.3.2 Перспективы применения комбинированного декодирования кодов Рида-Маллера.

3.3.3 Схема работы алгоритма комбинированного декодирования кодов Рида-Маллера.

3.3.4 Итерационный алгоритм комбинированного декодирования кодов Рида-Маллера

3.3.5 Пример декодирования кодового слова кода Рида-Маллера.

3.4 Выводы по третьей главе.

ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС «RM DECODER» ИМИТАЦИОННОГО МОДЕЛИРОВАНИЯ ПРОЦЕССОВ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ КОДОВ РИДА-МАЛЛЕРА.

4.1 Структура программного комплекса.

4.1.1 Основные требования к программному комплексу.

4.1.2 Объектно-ориентированное конструирование функциональных блоков.

4.1.3 Структурная организация алгоритмов и данных.

4.2 Разработка ядра программного средства, реализующего алгоритм Лоидрю-Саккура

4.2.1 Особенности проектирования ядра программного средства «RM Decoder».

4.2.2 Разработка модуля построения экспериментов.

4.2.3 Вспомогательные классы для проведения экспериментов.

4.3 Экспериментальное исследование метода комбинированного декодирования применительно к слабозашумленным каналам.

4.3.1 Постановка задачи и методика проведения экспериментов.

4.3.2 Экспериментальное исследование метода комбинированного декодирования при средней вероятности ошибок в канале 0,001.

4.3.3 Экспериментальное исследование метода комбинированного декодирования при средней вероятности ошибок в канале 0,01.

4.3.4 Анализ результатов применения метода комбинированного декодирования при средней вероятности ошибок в канале 0,1.

4.3.5 Экспериментальное сравнение метода комбинированного декодирования и алгоритма Лоидрю-Саккура при средней вероятности ошибок в канале 0,001, 0,01 и 0,1.

4.4 Выводы по четвертой главе.

Актуальность темы

Теория кодирования возникла в конце сороковых годов с появлением работ Шеннона, Голея и Хэмминга. Задача помехоустойчивого кодирования имеет широкое практическое применение в повседневной жизни, в организационных и технических системах, в первую очередь, в системах связи, где надёжность является одним из приоритетных свойств. При передаче данных по каналу связи на передаваемые сигналы неминуемо воздействует шумы и помехи, препятствующие правильному приёму данных. Этот факт вызвал развитие теории помехоустойчивого кодирования, которая направлена на создание методов преобразования информации, позволяющих обнаруживать и исправлять ошибки, возникающие при прохождении сигнала по каналу передачи, повышая надёжность системы связи.

Для борьбы с помехами разработан класс помехоустойчивых кодов, позволяющих обнаруживать и исправлять ошибки в сообщниях, которые возникают при передаче по каналам связи. Эти коды строятся таким образом, что для передачи сообщения используется лишь ограниченное подмножество всех возможных по структуре кодовых слов. Они отличаются друг от друга более, чем в одном символе, и называются разрешенными. Все остальные кодовые слова относятся к числу запрещенных и не используются, т.к. их появление означает наличие ошибки. Таким образом, искусственная избыточность кодового слова относительно исходного сообщения является фактором, обеспечивающим в дальнейшем при декодировании возможность восстановления ошибок, вносимых каналом связи. Помехоустойчивые коды применяются в таких областях как системы цифровой и сотовой связи, а также в системах преобразования, хранения и накопления информации, в том числе на магнитных и оптических носителях.

При реализации процесса кодирования используется два принципиально различающихся два подхода: поточный и блочный. С развитием вычислительной техники блочное кодирование практически вытеснило поточный побитовый) подход. Одним из перспективных классов блочных помехоустойчивых кодов являются коды Рида-Маллера. Несмотря на их давнее происхождение (1954 г.) коды Рида-Маллера и постоянные исследования в области помехоустойчивого кодирования, данные коды продолжают активно исследоваться и успешно применяются во многих областях техники, конкурируя с более сложными кодами за счёт простоты реализации и надёжности алгоритма. Поэтому в настоящее время активно разрабатываются новые и совершенствуются уже существующие декодеры кодов Рида-Маллера. Со-вершенстование осуществляется по таким направлениям, как увеличение числа исправляемых ошибок и наделение декодера новыми свойствами. Последнее, например, может быть связано с использованием современного списочного подхода к декодированию.

Не так давно было предложено новое перспективное направление применения помехоустойчивых кодов. Было предложено использовать методы теории помехоустойчивого кодирования для построения новых систем защиты передаваемой информации. Появились шифросистемы с открытым ключом и схемы электронной цифровой подписи, основанные на помехоустойчивых кодах. Среди такого класса шифросистем особое место занимают шифросистемы Мак-Элиса и Нидеррайтера, которые будучи построенными с применением кодов Рида-Маллера, на данное время являются одними из наиболее криптостойких.

Таким образом диссертационная работа посвящена решению актуальной научно-технической проблемы, связанной с исследованием особенностей помехоустойчивых кодов Рида-Маллера, анализом существующих алгоритмов декодирования и повышением корректирующей способности кодов за счет разработки новых методов и алгоритмов декодирования.

Цель и основные задачи диссертационной работы

Основной целью диссертации является повышение корректирующей способности процедуры вероятностного декодирования кодов Рида-Маллера.

Системные исследования выявили, что для достижения поставленной цели необходимо решить следующие научные и экспериментальнопрактические задачи:

1. Теоретическое и экспериментальное исследование современных вероятностных декодеров кодов Рида-Маллера и выявление наиболее перспективных из них.

2. Моделирование существующих алгоритмов декодирования, выявление недостатков, их исследование и поиск путей полной или частичной компенсации выявленных недостатков.

3. Исследование информационных признаков и разработка методов анализа структуры кодового слова с целью определения количества наложенных на него ошибок и способов их структурной идентификации и исправления.

4. Исследование и анализ возможностей повышения корректирующей способности кодов Рида-Маллера реализацией комбинированного декодера.

5. Разработка комплекта программных средств реализующих известные и разрабатываемые алгоритмы декодирования кодов Рида-Маллера, предназначенного для практического и научно-исследовательского использования, а также для проведения сравнительных численных экспериментов.

Основные результаты и степень их научной новизны

1. Математическая модель метода декодирования кодов Рида-Маллера по схеме Лоидрю-Саккура, которая позволяет как исследовать свойства данного метода декодирования, так и построить его имитационную модель.

2. Доказанный статистически представительным (более 1000 опытов) экспериментом и аналитическим системным исследованием алгоритма факт низкой степени фактической эффективности (от 20% правильного восста7 новления, в случае 4-х ошибок, приходящихся на кодовое слово, для кодов Рида-Маллера с параметрами т—5,г= 2, до 8%, в случае 5-ти ошибок) особого уточняющего шага, заявленного в алгоритме Лоидрю-Саккура.

3. Обоснованный экспериментально более чем на 1000 опытах метод структурной идентификации количества ошибок, наложенных на кодовое слово, отличающий разработанный на его основе алгоритм декодирования от существующих вероятностных декодеров, игнорирующих этап анализа ошибок.

4. Основанный, в отличие от известных методов, на структурном мониторинге, использующем анализ восстанавливаемого кодового слова, метод его побитовой коррекции, позволивший значительно повысить вероятность точного декодирования, а, в отдельных случаях, добиться 100%-го декодирования.

5. Предложен комбинированный алгоритм декодирования кодов Рида-Маллера, впервые использующий мониторинг процесса декодирования и позволяющий гибко варьировать размер получаемого на выходе списка декодированных векторов вплоть до ординарного, эффективность которого подтверждена статистически представительным (более 10000 опытов) экспериментальным исследованием, показавшим, в частности, что даже при вероятности ошибки в канале 0,1 (сильно зашумлённый канал) применение метода комбинированного декодирования снижает её до 0,04, тогда как декодирование алгоритмом Лоидрю-Саккура увеличивает её до 0,15.

Основные результаты диссертационной работы докладывались и обсуждались на следующих международных научно-технических конференциях: «Математические методы в технике и технологиях - ММТТ-18». - Казань, 2005; «Математические методы в технике и технологиях - ММТТ-19». — Воронеж, 2006; «Математические методы в технике и технологиях - ММТТ-20». — Ярославль, 2007; «Системный анализ, управление и обработка информации». — ДГТУ-ТТИ ЮФУ, 2007; «Математические методы в технике и технологиях - ММТТ-22». - Псков, 2009; IX-я Международная научно-техническая конференция «Интеллектуальные системы '09»: Конгресс по интеллекту ал ьным системам и информационным технологиям «AIS-IT'09». - Москва, 2009.

Большинство промежуточных результатов диссертационных исследований докладывались на ежегодных научно-технических конференциях Донского государственного технического университета в 2007-2009 гг.

ЗАКЛЮЧЕНИЕ

Задача помехоустойчивого кодирования имеет широкое практическое применение в повседневной жизни, в организационных и технических системах, в первую очередь, в системах связи, где надёжность является, наряду с быстродействием, одним из приоритетных свойств. При передаче данных по каналу связи на передаваемые сигналы неминуемо воздействует шумы и помехи (как естественные, так и преднамеренные), препятствующие правильному приёму данных. Этот факт вызвал развитие теории помехоустойчивого кодирования, которая направлена на создание методов преобразования информации, позволяющих обнаруживать и исправлять ошибки, возникающие при прохождении сигнала по каналу передачи, повышая, тем самым, надёжность системы связи. Среди помехоустойчивых кодов особое место занимают коды Рида-Маллера, которые активно исследуются и в настоящее время. Помимо этого коды Рида-Маллера получили широкое распространение в криптографии с появлением шифросистем типа Мак-Элиса и Нидеррайтера.

В настоящей работы было проведено исследование декодеров кодов Рида-Маллера и поиск возможностей повышения эффективности их декодирования. Теоретические исследования и экспериментальный анализ позволил разработать новый способ комбинированного декодирования, позволяющего гибко варьировать список информационных слов, получаемых на выходе, и таким образом, объединять преимущества как списочных, так и ординарных декодеров.

Методы исследования. В диссертации применялись методы математического анализа, исследования операций, математического моделирования, теории помехоустойчивого кодирования, математической статистики, теории планирования экспериментов.

Для формирования экспериментально-исследовательской базы разработана программа для ЭВМ «Программное средство декодирования кодов Рида-Маллера модифицированным алгоритмом Лоидрю-Саккура», построенная на основе концепции объектно-ориентированного программирования.

В настоящее время программный продукт находится на регистрации в Роспатенте.

Достоверность результатов исследования достигается за счёт корректного применения методов системного и математического анализа, моделирования, исчерпывающей статистической обработки результатов. Проведено большое количество имитационных экспериментов, результаты которых использованы для получения статистически достоверных данных. Общий объем имитационно-численных экспериментов, проведенных при решении различных задач и вариациях параметров модели, составил более ю5 опытов. Статистическая достоверность данных обеспечивалась не менее чем 1000 параллельных опытами.

Практическая значимость диссертационной работы. Исследуемые в диссертации методы декодирования помехоустойчивых кодов Рида-Маллера могут применяться во многих областях. Так, предложенный алгоритм комбинированного декодирования, может использоваться для повышения эффективности декодирования кодов Рида-Маллера при передаче информации по сильно зашумленным каналам. В силу того, что количество возникающих ошибок в канале связи напрямую зависит от мощности приемника/передатчика, а также от дальности связи применение более эффективных алгоритмов декодирования позволит снизить техническую сложность и стоимость таких типов систем связи как системы дальней и спутниковой связи, а также других типов связи, в которых остро стоит вопрос экономии энергии.

Практически значимыми эффектами применения результатов диссертационных исследований являются:

1. введение в практику помехозащищённого кодирования метода логического мониторинга, основанного на структурном анализе кодовых слов, позволяющем оценивать наиболее вероятное число ошибок, искажающих кодовое слово;

2. метод комбинированного декодирования, позволяющий производить безошибочное декодирование (вероятность возникновения ошибки менее кг5) кодов Рида-Маллера с параметрами т = 5, г=2 при вероятности ошибки в канале не более 0,01;

3. применение списочного способа декодирования, используемого в комбинированном методе декодирования позволило существенно (до 80%) повысить вероятность успешного декодирования кодов Рида-Маллера с параметрами m=5,/•=2 при вероятности ошибки в канале 0,1 по сравнению с алгоритмом Лоидрю-Саккура.

Разработанное для исследований программное обеспечение «Программное средство декодирования кодов Рида-Маллера модифицированным алгоритмом Лоидрю-Саккура» может быть использовано для осуществления автоматизированного проведения имитационных экспериментов.

1. Аршинов М.Н. Коды и математика (рассказы о кодировании) / М.Н.Аршинов, Л.Е.Садовский. Изд.: Наука, 1983. - 145 с.

2. Бабков В. Ю. Системы мобильной связи. Термины и определения / В. Ю. Бабков, Г. 3. Голант, А. В. Русаков. — Изд.: Горячая Линия Телеком, 2009. — 162 с.

3. Беделл П. Сети. Беспроводные технологии / П. Беделл. — Изд.: НТ Пресс, 2008. 448 с.

4. Берлекэмп Э. Алгебраическая теория кодирования / Э. Берлекэмп — М.: Мир, 1971.-478 с.

5. Берлекэмп Э.Р. Техника кодирования с исправлением ошибок / Э.Р. Берлекэмп // ТИИЭР. Т. 68, № 5, 1980.- С. 24-58.

6. Берлин А. Н. Коммутация в системах и сетях связи / А. Н. Берлин Изд.: Эко-Трендз, 2006. 344 с.

7. Блейхут Р. Теория и практика кодов, контролирующих ошибки / Р. Блей-хут. -М.: Мир, 1986. 576 с.

8. Блох Э.Л. Модели источника ошибок в каналах передачи цифровой информации / Э.Л. Блох, В.Я. Турин, О.В. Попов. — М.: Связь, 1971. 312 с.

9. Борисов В. И. Помехозащищенность систем радиосвязи. Вероятностно-временной подход / В. И. Борисов, В. М. Зинчук. — Изд.: РадиоСофт, 2009. — 260 с.

10. Васильев К.К. Основы теории помехоустойчивых кодов: учебное пособие / К.К. Васильев, Л .Я. Новосельцев, В.Н. Смирнов. — Ульяновск: УлГТУ, 2000.-91 с.

11. Вернер М. Основы кодирования: Учебник для ВУЗов / М. Вернер. М.: Техносфера, 2004. — 287 с.

12. Влэдуц С. Г. Алгеброгеометрические коды. Основные понятия / С. Г. Влэдуц, Д. Ю. Ногин, М. А. Цфасман. Изд.: МЦНМО, 2003. - 504 с.

13. Волков JI. Н. Системы цифровой радиосвязи. Базовые методы и характеристики / JI. Н. Волков, М. С. Немировский, Ю. С. Шинаков. -Изд.: Эко-Трендз, 2005. 392 с.

14. Воронов А.В. Каналы связи в системах телекоммуникации: Учебное пособие / А.В. Воронов, А.В. Матвеев, И.С. Минченко. СПб.: Изд-во СПбГЭ-ТУ "ЛЭТИ",2001.-48 с.

15. Галлагер Р. Теория информации и надежная связь / Р. Галлагер. — М.: Сов. Радио, 1974. 720 с.

16. Горбоконенко В. Д. Кодирование информации: методические указания / сост.: В. Д. Горбоконенко, В. Е. Шикина. Ульяновск: УлГТУ, 2006. - 56 с.

17. Гуров И.П. Основы теории информации и передачи сигналов / И.П. Гуров. СПб.: BHV-Санкт-Петербург, 2000. - 97 с.

18. Дейтел Х.М. Как программировать на С++: 4-е издание. Пер. с англ. / Х.М. Дейтел, П. Дж. Дейтел. М.: ООО «Бином-Пресс», 2005. - 1248 с.

19. Деундяк В.М. Семейство кодов Рида-Маллера и коды Хемминга / В.М. Деундяк, Н.С. Могилевская, Е.А. Степанюченко // ДГТУ. Ростов-на-Дону, 2004. - 11 с.

20. Деундяк В. М., Могилевская Н. С., Математическое моделирование источников ошибок цифровых каналов передачи данных: учебное пособие / В. М. Деундяк, Н. С. Могилевская. ДГТУ, Ростов н/Д, - 2006.

21. Деундяк В.М. О реализации модифицированной шифросистемы Мак-Элиса, основанной на кодах Рида-Маллера / В.М. Деундяк, В.Р. Скоробогат,

22. Интегро-дифференциальные операторы и их приложения: межвуз. сб. науч. тр. Ростов н/Д, 2004. - Вып. 6, С. 17-23.

23. Дмитриев В. И. Помехоустойчивое кодирование в системах передачи данных: пособие / В. И. Дмитриев, В. В. Хромов. JI. ЛПИ, 1988. — 80 с.

24. Егоров С.И. Коррекция ошибок в информационных каналах периферийных устройств ЭВМ / С.И. Егоров. Курск: КурскГТУ, 2008. - 252 с.

25. Злотник Б.М. Помехоустойчивые коды в системах связи / Б.М. Злотник. — Статистическая теория связи, вып. 31. — М.: Радио и связь, 1989. — 232 с.

26. Золотарев В.В. Помехоустойчивое кодирование. Методы и алгоритмы / В.В. Золотарев, Г.В. Овечкин Изд.: Горячая линия - Телеком, 2004. - 128 с.

27. Зюко А.Г. Помехоустойчивость и эффективность систем связи / А.Г. Зю-ко. М.: Связьиздат, 1963. - 320 с.

28. Ильин В.А. Линейная алгебра: издание: 6-е / В.А. Ильин, Э.Г. Позняк. — Изд.: Физматлит, 2007. 280 с.

29. Кларк Дж. Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ. / Дж. Кларк, Дж. мл. Кейн. Статистическая теория связи, вып. 28. - М.: Радио и связь, 1987. - 392 с.

30. Кнут Д. Искусство программирования. Основные алгоритмы : в Зт. / Д. Кнут. — Том 1, 3-е изд. — М.: «Вильяме», 2006. — 720 с.

31. Колмогоров А.Н. Теория информации и теория алгоритмов /

32. A.Н.Колмогоров. Изд. Наука, 1987. - 305 с.

33. Коржик В.И. Помехоустойчивое кодирование дискретных сообщений в каналах со случайной структурой / В.И. Коржик, J1.M. Финк. Статистическая теория связи, вып. 4. -М.:"Связь", 1975. - 272 с.

34. Коржик В.И. Расчет помехоустойчивости систем дискретных сообщений: Справочник / В.И. Коржик, J1.M. Финк, К.Н. Щелкунов. М.: Радио и связь, 1981. - 231 с.

35. Кострикин А. И. Линейная алгебра и геометрия / А. И. Кострикин, Ю. И. Манин. Изд.: Лань, 2008. - 304 с.

36. Котельников В.А. Теория потенциальной помехоустойчивости /

37. B.А.Котельников. М.: ГЭИ, 1956. - 151 с.

38. Либерти Д. Освой самостоятельно С++ за 21 день: 5-е издание / Д. Либерти. — изд. Дом «Вильяме», Москва Санкт-Петербург - Киев, 2005. — 784 с.

39. Лидовский В.И. Теория информации / В.И. Лидовский. — М.:«Высшая школа», 2002. 120 с.

40. Логачев О.А. Булевы функции в теории кодирования и криптологии / О.А. Логачев, А.А. Сальников, В.В. Ященко. МЦНМО, 2004. - 470 с.

41. Логачев О. А. Коды типа Рида-Маллера на конечной абелевой группе / О.

42. A. Логачев, В. В. Ященко. // Проблемы передачи информации, т. 34, вып. 2, 1998.-С. 32-46.

43. Луадро П. Коды, полученные из двоичных кодов Гоппы / П. Луадро // Пробл. передачи информ., т.37:2, 2001, С. 8-17.

44. Мак-Вильямс Ф.Д. Теория кодов, исправляющих ошибки: Пер. с англ. / Ф.Д. Мак-Вильямс, Н.Дж. Слоэн. М.: Связь, 1979. - 744 с.

45. Маккалоу Д. Секреты беспроводных технологий / Д. Маккалоу. — Изд: НТ Пресс, 2005. 408 с.

46. Марченков С. С. Замкнутые классы булевых функций / С. С. Марченков. — М.: Физматлит, 2000. 126 с.

47. Матросов В. Теоретические основы информатики / В. Матросов, В. Горелик, С. Жданов. — Изд.: Академия, 2009. 352 с.

48. Мкртичян В.В. К вопросу об эффективности программной реализации мажоритарного декодера для кодов Рида-Маллера /В.В. Мкртичян // Интег-ро-дифференциальные операторы и их приложения. Вып. 6. Ростов-на-Дону: ДГТУ, 2004.

49. Могилевская Н.С. О проблемах реализации вероятностного алгоритма Лоидрю-Саккура декодирования кодов Рида-Маллера / Н.С. Могилевская,

50. B.Р. Скоробогат // Системный анализ, управление и обработка информации: 1-й межвузовский сборник науч. статей / ДГТУ-ТТИ ЮФУ, 2007. — С.388-393.

51. Могилевская Н.С. Экспериментальное исследование декодеров кодов Рида-Маллера второго порядка / Н.С. Могилевская, В.Р. Скоробогат, B.C. Чудаков // Вестник ДГТУ, Т.8 №3(38), 2008. С. 231-237.

52. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение / Р. Морелос-Сарагоса. — М.: Техносфера, 2006. — 320 с.

53. Муттер В.М. Основы помехоустойчивой телепередачи информации / В.М. Муттер. Л.: Энергоатомиздат. Ленингр. отделение, 1990. — 288 с.

54. Никитин Г.И. Помехоустойчивые циклические коды: Учебное пособие / Г.И. Никитин. СПб.: ГУАП, 2003. - 33 с.

55. Новые алгоритмы формирования и обработки сигналов в системах подвижной связи / А. М. Шлома и др.; Изд.: Горячая Линия Телеком, 2008. -344 с.

56. Олифер В. Г. Компьютерные сети. Принципы, технологии, протоколы: учебник для вузов / В. Г. Олифер, Н. А. Олифер. Изд.: Питер, 2007. — 960 с.

57. Осмоловский С. А. Стохастические методы защиты информации / С. А. Осмоловский. М., Радио и связь, 2002. - 187с.

58. Питерсон У. Коды, исправляющие ошибки / У. Питерсон, Э. Уэлдон — М.: Мир, 1976.-596 с.

59. Прокис Дж. Цифровая связь: пер. с англ. / Дж. Прокис; под ред. Д. Д. Кловского. М.: Радио и связь, 2000. — 800 с.

60. Рихтер С. Г. Кодирование и передача речи в цифровых системах подвижной радиосвязи / С. Г. Рихтер. — Издательство: Горячая Линия Телеком, 2009. - 306 с.

61. Самойленко С.И. Помехоустойчивое кодирование / С.И. Самойленко. — М.: «Наука», 1966. 240 с.

62. Семенов Ю.А. Алгоритмы телекоммуникационных сетей. Алгоритмы и протоколы каналов и сетей передачи данных: в Зч, ч. 1. / Ю.А. Семенов. -Изд.: Интернет-университет информационных технологий ИНТУИТ.ру, 2007. - 640 с.

63. Сидельников В.М. Декодирование кодов Рида-Маллера при большом числе ошибок / В.М. Сидельников, А.С. Першаков // Пробл. передачи ин-форм. 1992. - Т. 28. №3. - С. 80-94.

64. Сидельников В.М. Декодирование кода Рида-Соломона при числе ошибок, большем (d-l)/2 и нули многочленов нескольких переменных / В.М. Сидельников // Пробл. перед, инф. М.: 1994, т.З, № 30. — 51-69 С.

65. Сидельников В.М. О системе шифрования, построенной на основе обобщенных кодов Рида-Соломона / В.М. Сидельников, С.О. Шестаков // Дискр. матем. т.4, вып.3,1992. С. 57-63.

66. Скляр Б. Цифровая связь. Теоретические основы и практическое применение. Изд. 2-е, испр.: Пер. с англ. / Б. Скляр. — М.: Издательский дом «Вильяме», 2003.-1104 с.

67. Скоробогат В.Р. Математико-алгоритмическая модель Лоидрю-Саккура для кодов Рида-Маллера второго порядка / В.Р. Скоробогат, Р.А. Нейдорф // Вестник ДГТУ, Т.9, спец. выпуск. — Ростов н/Д, 2009. С. 3-11.

68. Скоробогат В.Р. Построение и оптимизация списочного декодера для кодов Рида-Маллера / В.Р. Скоробогат, Р.А. Нейдорф // Математические методы в технике и технологиях, — ММТТ-22. сб. тр. XXII междунар. науч. конф.: В Ют, Т. 8. Псков, 2009. - С. 205-207.

69. Скоробогат В.Р. Алгоритм-мониторинг процесса декодирования для кодов Рида-Маллера второго порядка / Скоробогат В.Р. // Математические методы в технике и технологиях, — ММТТ-22. сб. тр. XXII междунар. науч. конф.: В Ют, Т. 8. Псков, 2009. - С. 212-214.

70. Скоробогат В.Р. Экспериментальное исследование корректирующих способностей алгоритма декодирования Лоидрю-Саккура / В.Р. Скоробогат

71. Соммервиль И. Инженерия программного обеспечения / И. Соммервиль. М.: Изд. «Вильяме», 2002. - 624 с.

72. Теория информации и кодирование / Б. Б. Самсонов и др.; — Изд.: Феникс, 2002. 288 с.

73. Теория кодирования: пер. с япон. / Т. Касами и др.; М.:Мир, 1978. -576 с.

74. Теория передачи сигналов / А.Г. Зюко и др.; М: Радио и связь, 2001. -368 с.

75. Томаси У. Электронные системы связи / У. Томаси. Издательство: Техносфера, 2007. - 1360 с.

76. Феллер В. Введение в теорию вероятностей и ее приложения: т.1 в 2-х томах / В. Феллер. М.: Мир, 1984. - 527с.

77. Хэмминг Р.В. Коды с обнаружением и исправлением ошибок. В кн.: Коды с обнаружением и исправлением ошибок / Р.В. Хэмминг. — М. ИЛ, 1956. -С. 7-22.

78. Чернова Н.И. Теория вероятности / Н.И. Чернова. Изд.: Новосибирск, НГУ, 2006.- 139 с.

79. Шамшин А.В. Исследование помехоустойчивости кодов Рида-Маллера / А.В. Шамшин // Десятая юбилейная международная студенческая школа-семинар «Новые информационные технологии». Тезисы докладов. Т.1. Москва: МГИЭМ, 2002. С. 155-156.

80. Шахнович И. Современные технологии беспроводной связи / И. Шахно-вич. Изд.: Техносфера, 2006. - 288 с.

81. Шеннон К. Работы по теории информации и кибернетике / К. Шеннон. — М.:ИЛ, 1963.-С. 243-332.

82. Ashikhmin A. Simple MAP decoding of first-order Reed-Muller and Hamming codes / A. Ashikhmin, S. Litsyn // IEEE transactions on information theory, vol. 50, no. 8, August 2004.-pp. 1812-1818.

83. Courtois N. How to achieve a McEliece-based Digital Signature Scheme / N. Courtois, M. Finiasz, N. Sendrier // ASIACRYPT 2001, LNCS 2248, Springer, 2001.-pp 157-174.

84. Dumer I. On poly logarithmic decoding complexity for reed-muller codes// Information Theory, 2004. ISIT 2004. Proceedings. International Symposium on. — pp. 327-327.

85. Dumer I. Soft-decision decoding of Reed-Muller codes: A simplified algorithm / I. Dumer // IEEE transactions on information theory, vol. 52, no. 3, March 2006.-pp. 954-963.

86. Dumer I. Soft-decision decoding of Reed-Muller codes: Recursive lists / I. Dumer, K. Shabunov // IEEE Transactions on information theory, vol. 52, no. 3, March 2006. pp. 1260-1266.

87. Golay M. J. E. Notes on digital coding / M. J. E. Golay // Proc. IRE, v.37, 1949.-p. 657.

88. Guruswami V. Improved decoding of reed-solomon and algebraic-geometric codes / V. Guruswami, M. Sudan // IEEE Trans, on Inform. Theory 45, no. 6, 1999.-pp. 1757-1767.

89. Hin P.J.M. Private communications / P J.M. Hin // December 1986.

90. Hoholdt Т. On the decoding of algebraic-geometric codes / T. Hoholdt, R. Pellicaan // IEEE Trans. Inform. Theory. V. IT-41, 1995. pp. 1589-1614.

91. Lucas R. Improved soft-decision decoding of Reed-Muller codes as generalized multiple concatenated codes / R. Lucas, M. Bossert, A. Dammann // Proc. ITG Conf. source and channel coding, Aahen, Germany, 1998. pp. 137-141.

92. McEliece R.J. A Public-Key Cryptosystem Based on Algebraic Coding Theory / R.J. McEliece // DGN Progress Report 42-44, Jet Propulsi on Lab., Pasadena, CA, January-February, 1978. pp. 114-116.

93. Niederreiter H. Knapsack-Type Cryptosystems and Algebraic Coding Theory /

94. H. Niederreiter // Probl. Control and Inform. Theory, V. 15, 1986. pp. 19-34.

95. Reed I.S. A class of multiple-error-correcting codes and the decoding scheme /

96. S. Reed // IEEE Trans. Info. Theory, v. 4, 1954. pp. 38-49.

97. Solte N. Soft-decision stack decoding of binary Reed-Muller codes with "Look-ahead" technique / N. Solte, U. Sorger // 7th International Workshop on Algebraic and Combinatorial Coding Theory, Bansko, Bulgaria, 18-24 June 2000. -pp. 293-298.

98. Van Tilburg J. On the McEliece Public-key Cryptosystem / Johan van Tilburg // Springer-Verlag, 1998. pp. 224-228.