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

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

О В Е Ч К И Н Павел Владимирович

РАЗРАБОТКА АЛГОРИТМОВ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ НЕДВОИЧНЫХ МНОГОПОРОГОВЫХ ДЕКОДЕРОВ В СИСТЕМАХ ПЕРЕДАЧИ И ХРАНЕНИЯ БОЛЬШИХ ОБЪЕМОВ ИНФОРМАЦИИ

Специальность 05.13.13 - «Телекоммуникационные системы и компьютерные сети»

АВТОРЕФЕРАТ

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

Рязань 2009

003472849

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

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

Золотарёв Валерий Владимирович

Официальные оппоненты: доктор физико-математических наук

Назаров Лев Евгеньевич

кандидат технических наук, доцент Гаврилов Александр Николаевич

Ведущая организация: ФГУП «Научно-исследовательский ин

ститут радио»

Защита диссертации состоится «23» июня 2009 г. в 13 часов на заседании диссертационного совета Д 212.211.02 в ГОУВПО «Рязанский государственный радиотехнический университет» по адресу: 390005, г. Рязань, ул. Гагарина, 59/1.

С диссертацией можно ознакомиться в библиотеке ГОУВПО «Рязанский государственный радиотехнический университет».

Автореферат разослан «21» мая 2009 г.

Ученый секретарь

диссертационного совета Д 212.211.02 к.т.н., доцент

И.А. Телков

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

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

Огромный вклад в развитие теории кодирования внесли такие ученые, как К. Шеннон, В.А. Котельников, В.В. Зяблов, К.Ш. Зигангиров, В.В. Золотарёв, А. Витерби, Дж. Месси, Р. Галлагер, Д. Форни, JIM. Финк, B.JI. Банкет, Дж. Возенкрафт, Е. Берлекэмп, Э.Л. Блох и др.

В настоящее время специалисты в области помехоустойчивого кодирования проявляют большой интерес к недвоичным кодам, работающим с цифровыми данными на уровне символов, например, с байтами информации. Недвоичные коды применяются в. каналах с группирующимися ошибками, в качестве составляющих элементов различных каскадных кодов, для защиты от ошибок информации на различного рода носителях (CD, DVD, Blu-ray и др.).

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

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

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

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

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

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

- разработать и исследовать алгоритмы построения наиболее эффективных недвоичных самоортогональных кодов (СОК) для дМПД, использование которых позволит повысить достоверность передачи и хранения информации;

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

- разработать и исследовать каскадные схемы коррекции ошибок на основе дМПД, позволяющие уменьшить вероятность ошибки декодирования по сравнению с базовым некаскадным методом;

- разработать программные средства для исследования эффективности дМПД;

- разработать программные средства для защиты файлов от искажений.

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

по модулю д, к решению оптимального декодера. В работе впервые предложено каскадирование дМПД с кодеком модифицированных недвоичных кодов Хэмминга.

Основные положения, выносимые на защиту:

- алгоритм построения эффективных недвоичных самоортогональных кодов для дМПД;

- алгоритм работы недвоичного порогового элемента, позволяющий значительно ускорить работу дМПД;

- доказательство теоремы о стремлении решения декодера каскадного кода, состоящего из недвоичного СОК и кода контроля по модулю д, к решению оптимального декодера;

- каскадная схема кодирования, состоящая из недвоичного самоортогонального кода и модифицированного недвоичного кода Хэмминга.

Практическая ценность работы. Разработанный алгоритм построения недвоичных самоортогональных кодов для схем параллельного кодирования позволяет приблизить область эффективной работы дМПД к пропускной способности канала более чем на 13%. Предложенный алгоритм работы недвоичного порогового элемента позволяет повысить быстродействие недвоичного многопорогового декодера более чем в 2 раза. Разработанная каскадная схема на базе недвоичного самоортогонального кода и модифицированного недвоичного кода Хэмминга позволяет уменьшить частоту появления ошибок на выходе дМПД в области его эффективной работы более чем на 3 порядка. Программные средства на основе недвоичного многопорогового декодера для защиты файлов от искажений при длительном хранении информации позволяют ускорить процессы кодирования и восстановления информации в десятки раз по сравнению с известными программами-аналогами при сопоставимой эффективности восстановления данных.

Внедрение результатов работы. Результаты диссертационной работы были использованы: ООО «Объединенные радиоэлектронные технологии» при разработке аппаратуры передачи информации, предназначенной для работы в условиях городской застройки; Институтом космических исследований Российской академии наук при разработке исходных данных на наземный комплекс приема, обработки и распределения данных КНА «Фобос-Грунт»; разработанные программные средства моделирования недвоичного многопорогового алгоритма декодирования и его модификаций используются в учебном процессе Рязанского государственного радиотехнического университета, что подтверждается актами о внедрении.

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

-корректным использованием теории вероятностей и математической статистики;

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

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

Апробация работы. Результаты работы докладывались на следующих конференциях и семинарах:

1. 11-я, 13-я, 14-я и 15-я международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». - 2002 г., 2004 г., 2005 г., 2008 г., Рязань.

2. Всероссийская научно-техническая конференция «Новые информационные технологии в научных исследованиях и в образовании, НИТ». - 2003 г., 2005 г., 2006 г., Рязань.

3. Межвузовская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в учебном процессе и производстве» . - 2004 г., Рязань.

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

5. Научно-практическая конференция «Научные исследования и их практическое применение. Современное состояние и пути развития», 2005 г., Одесса.

6. Всероссийский смотр-конкурс научно-технического творчества «Эврика-2005». - 2005 г., Новочеркасск.

7. 8-я, 9-я, 10-я, 11-я международная конференция и выставка «Цифровая обработка сигналов и ее применение». - 2006 г., 2007 г., 2008 г, 2009 г., Москва.

8. Межвузовская научно-методическая конференция «Методы организации учебного процесса в ВУЗе» - 2007 г., Рязань.

9. 5-я и 6-я конференция молодых ученых, посвященная Дню космонавтики «Фундаментальные и прикладные космические исследования». - 2008 г., 2009 г., Москва.

Публикации. По теме диссертации опубликовано 26 работ, из них 18 в соавторстве. В их числе 1 статья в журналах, рецензируемых ВАК, 4 статьи в межвузовских сборниках научных трудов, 20 тезисов докладов на международных и всероссийских конференциях. Разработан и зарегистрирован в Российском агентстве по патентам и товарным знакам 1 пакет программ.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка и двух приложений. Содержит 131 страницу, 3 таблицы, 57 рисунков. Библиографический список состоит из 86 наименований.

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

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

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

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

Наиболее широкое применение в реальных системах передачи и хранения информации из недвоичных кодов нашли коды Рида-Соломона (РС). Замечательным свойством данных кодов является то, что с их помощью всегда возможно исправление [_/ / 2] ошибок или / стираний (Ы - операция взятия целой части числа х, Г - число проверочных символов кода), т.е. коды РС позволяют добавлять минимальное число избыточных символов для исправления любой конфигурации ошибок заданного веса. Однако декодеры коротких кодов Рида-Соломона, которые и применяются на практике, не могут обеспечить высокую эффективность декодирования, а для длинных кодов РС невозможно создать декодер из-за высокой сложности его реализации. Отметим, что вычислительная сложность декодирования кодов Рида-Соломона достаточно велика и пропорциональна квадрату длины кода.

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

Наиболее перспективным методом коррекции ошибок является метод недвоичного многопорогового декодирования. Ценность дМПД за-

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

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

Недвоичный многопороговый декодер (д>МПД) является простейшим декодером мажоритарного типа. дМПД используется для декодирования недвоичных самоортогональных кодов (СОК). Пример схемы </МПД блокового недвоичного СОК, заданного образующим полиномом

£(х) = 1 + х + х4 + х6, представлен на рисунке 1.

(+] - Сумматор по модулю ц 0 - Вычитатель по модулю д дПЭ- д-ичный пороговый элемент

Рисунок 1 - Пример схемы ^гМПД блокового недвоичного СОК

Процедура декодирования дЫЛД заключается в том, что для очередного контролируемого недвоичным пороговым элементом (дПЭ) информационного символа кода му происходит подсчет количества и определение значений двух относящихся к нему наиболее часто встречающихся проверок кода, например, Ъ\ и Ьг, причем Ь\ встречается т\ раз, ¿2 ~~ Щ раз (/И1>т2), а остальные значения проверок для декодируемого символа и,- встречаются не более тг раз. Если разница т\-тг будет больше значения порога Т, то на

выходе дПЭ будет значение Ъ\, которое вычитается из соответствующих элементов синдромного регистра, из текущего элемента информационного регистра и заносится в связанный с информационным элемент разностного регистра. Если окажется, что два наиболее часто встречающихся значения проверок таковы, что т\=т2, то выход <?ПЭ устанавливается равным нулю, т. е. символ uj не изменяется, и делается попытка декодирования любого другого информационного символа кода.

До настоящего времени были известны характеристики дМПД только для <у-ичных симметричных каналов (дСК), где ошибки появлялись независимо друг от друга с равной вероятностью. Однако часто в реальных системах передачи и хранения информации возникают пакеты ошибок, которые обычно существенно ухудшают эффективность классических методов коррекции ошибок. Для описания таких каналов подходит'модель канала Гилберта-Эллиота. Поэтому в диссертационной работе были проведены исследования эффективности ¿¡гМПД в этих более сложных условиях. Результаты такого исследовании показали, что дМПД для кода с кодовой скоростью R= 1/2, минимальным кодовым расстоянием d=\l, длиной л=32000 однобайтовых символов (размер алфавита q=256) эффективно исправляет около 25% ошибок в данном канале, а декодер кодов Рида-Соломона длиной 255 однобайтовых символов - только 1% ошибок.

Типичными представителями каналов с пакетирующимися ошибками являются системы хранения данных. Например, для защиты информации, находящейся на DVD дисках, используются коды произведения Рида-Соломона с Ä=7/8 и общей длиной «=38000. Во второй главе диссертации были подобраны недвоичные СОК с аналогичными параметрами, обладающие существенно лучшими корректирующими способностями.

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

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

На рисунке 2 представлены зависимости вероятности невосстановления символа на выходе декодера от вероятности стирания в канале. Здесь показаны характеристики декодера кодов PC и <?МПД для кодов с Л= 1/2. Из рисунка видно, что эффективность дМПД при существенно

10

о.1 10

10"'

10"

-о- РСст(<р256,л=255,А=127) -*- чМПДст((р256,0= 11,/7=50000) -в-Оценка чМПДст(сМ 1) ЧШДст(дг=25е, сМ 9, п= 100000) -«-Оценка дМПДст(г*=19)

~ ___ 1 « «

0.5

0.45

0.4

0.35

0.3

Рисунок 2 - Характеристики #МПД и декодера кодов РС в каналах со стираниями

меньшей сложности реализации превосходит эффективность практически реализуемого декодера кодов РС длиной 255 однобайтовых символов.

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

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

Также во второй главе оценена нижняя граница вероятности ошибки декодирования для рассматриваемого дМПД в таком канале. Для этого были выписаны наиболее частые события, которые всегда приводят к ошибкам оптимального декодера недвоичных СОК, и определены вероятности появления этих событий:

1. Все проверочные символы и информационный символ стерты:

2. Информационный символ стерт, один проверочный символ принят правильно, один проверочный символ ошибочен, остальные проверочные символы стерты:

Рг=Рй-{\-Рс-Р0)-Р?-г-(с1-1)-(с1-2).

3. Информационный символ ошибочен, один проверочный символ принят правильно, остальные проверочные символы стерты:

4. Информационный символ стерт, один проверочный символ ошибочен, остальные проверочные символы стерты:

5. Информационный символ стерт, два проверочных символа ошибочны, один проверочный символ принят правильно, остальные проверочные символы стерты:

Нижняя оценка вероятности символьной ошибки оптимального декодирования определяется суммой найденных выше вероятностей:

Р.^Р,-

м

Данная оценка оказывается достаточно точной для предварительного оценивания характеристик с/МПД, способного исправлять ошибки и восстанавливать стирания.

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

В третьей главе «Алгоритмы улучшения характеристик дМГТД» приводятся алгоритмы, применение которых позволяет ускорить работу и повысить эффективность декодирования дМПД; разработаны каскадные схемы коррекции ошибок на базе дМПД, позволяющие улучшить характеристики дМПД в области его эффективной работы.

Несмотря на то, что скорость работы ¿/МПД во много раз превосходит скорость работы других недвоичных декодеров, существует возможность дополнительного ускорения работы дМПД. Среди элементов дМПД наибольшую сложность имеет недвоичный пороговый элемент (дПЭ). В результате проведенного анализа был предложен новый алгоритм работы дПЭ, позволяющий существенно ускорить <?МПД. Схема дМПД, использующего модифицированный <?ПЭ, представлена на рисунке 3. Отметим, что в эту схему вводится дополнительный регистр, элементы которого показывают, нужно ли заново обрабатывать информацию, поступающую на

пороговый элемент с синдромного и разностного регистров. При этом, так как на различных итерациях может измениться значение порога дПЭ, необходимо запоминать значение разности т\-т2 и значение Ь\ наиболее популярной проверки, которое используется при срабатывании <?ПЭ.

Процедура декодирования принятого сообщения модифицированным дМПД состоит в следующем:

1. Произвольно выбирается декодируемый информационный символ Ну принятого сообщения.

2. Если элемент регистра признаков пересчета, соответствующий информационному символу ц, равен 1, то подсчитывается число двух наиболее часто встречающихся проверок. Значения этих двух проверок равны Ь\ и ¿2. а их количество равно т\ и тг соответственно, причем т\>тг. Если элемент регистра признаков пересчета равен 0, то значение разности т\-тг устанавливается равным значению текущего элемента порогового регистра, а значение Ь\ - значению текущего элемента регистра коррекций.

3. Если т\-т1<Т, то устанавливается в 0 значение элемента регистра признаков пересчета, соответствующего информационному символу и,-, в текущий элемент порогового регистра заносится разность т\-тъ в текущий элемент регистра коррекций - значение Ъ\. Если т^-т^Т, то из ир 4 и всех проверок относительно щ вычитается оценка ошибки, равная Ь\. Также устанавливаются в 1 все элементы регистра признаков, соответствующие информационные символы которых участвовали в формировании измененных символов синдромного регистра.

4. Осуществляется переход к новому ит, гг&} и далее переход к п. 2.

Для большего выигрыша по объему операций данную модификацию дМПД в некоторых случаях следует применять после нескольких обычных итераций декодирования. Использование предложенного алгоритма позволяет в 2-3 раза ускорить работу дМПД, при этом эффективность декодирования по сравнению с обычным ^МПД остается без изменений.

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

Здесь ро/у[][][] - полином, определяющий недвоичный СОК; Р°1уЩ [/][0] ~ определяет количество символов г-й информационной ветви, участвующих в формировании символов _/-й проверочной ветви; тш[г'][/] -минимальное количество символов г-й информационной ветви, участвующих в формировании символов /-й проверочной ветви; тах[И\\]] - макси-

Рисунок 4 - Алгоритм построения недвоичных СОК

мальное количество символов i-й информационной ветви, участвующих в формировании символов j-й проверочной ветви; GetProb(po/y) - функция для определения вероятности ошибки на выходе ^МПД для недвоичного СОК, заданного полиномом poly.

Результаты моделирования недвоичных параллельных СОК в дСК показаны на рисунке 5. Из рисунка видно, что область эффективной работы параллельного недвоичного СОК с R= 1/2, полученного с помощью применения данного алгоритма, оказывается на 13% ближе к пропускной способности канала по сравнению с лучшими из известных недвоичных СОК. Область эффективной работы параллельного кода с R=7/8 оказыва-

Рисунок 5 - Результаты моделирования параллельных СОК в #СК

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

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

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

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

Зи+1 -3.2™ +1

дифицированных недвоичных кодов Хэмминга, равна 1--,

где т - количество проверочных символов в кодовом слове. Например, для ти=8 исправляется порядка 71% блоков с двумя ошибками.

Доля блоков с двумя ошибками, исправляемых декодером модифицированных недвоичных расширенных кодов Хэмминга, равна (д-2)/д. Например, для д=256 исправляется 99.2% блоков с двумя ошибками, а при <7=65536 исправляется 99.997% блоков с двумя ошибками.

Получена нижняя оценка вероятности ошибки на выходе каскадной схемы, состоящей из £/МПД и декодера модифицированного недвоичного кода Хэмминга:

Р„.„.^.яг^-«».--),

где Рг - оценка вероятности ошибки на выходе дМПД, Nк = 2" -1 - длина блока недвоичного кода Хэмминга

Получена нижняя оценка вероятности ошибки на выходе каскадной схемы, состоящей из дМПД и декодера модифицированного недвоичного расширенного кода Хэмминга:

"еггЕх! л '

Ч 2

где = 2'" - длина блока недвоичного расширенного кода Хэмминга.

На рисунке 6 представлены характеристики каскадных схем кодирования, состоящих из недвоичного СОК и недвоичных кодов Хэмминга.

Из рисунка видно, что применение совместно с дМПД в области его эффективной работы декодеров модифицированных недвоичных кодов Хэмминга позволяет снизить вероятность ошибки на выходе каскадной схемы на три и более порядков.

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

ю'2

ю ю"4

ю'8

0.28 0.27 0.26 0.25 0.24 0.23 0.22 Р0

Рисунок 6 - Характеристики каскадных схем кодирования

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

В заключении сформулированы основные результаты работы:

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

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

3. Предложен алгоритм построения наиболее эффективных недвоичных самоортогональных кодов для схем параллельного кодирования. Применение таких кодов позволило приблизить области эффективной работы дМПД для кодов с Л=1/2 на 13% и для малоизбыточных кодов с #=7/8 на 20% к границе Шеннона, определяющей потенциальные корректирующие возможности кодов.

-<)МПД(<*=9) ■■Оценка дМПД(<*=9) -с/МПД(с*=9)+дХэмминг(л=127) ■Оценка оМПД(<*=9)+дХэмминг(л=127) -ЧМПД(<*=9)+Расширенный!;Хэмминг(л=128) -Оценка дМПД(с>=9)+Расцшренный дХэмминг(л=128)

4. Предложен новый алгоритм работы недвоичного порогового элемента дМГЩ, применение которого позволило повысить быстродействие дМПД более чем в 2 раза.

5. Доказана теорема о стремлении решения декодера каскадного кода, состоящего из недвоичного СОК и кода контроля по модулю ц, к решению оптимального декодера.

6. Впервые была рассмотрена и исследована каскадная схема ко. дирования, состоящая из недвоичного СОК и модифицированных недвоичных кодов Хэмминга. Получены аналитические оценки эффективности данной каскадной схемы. Показано, что использование предложенной каскадной схемы позволяет уменьшить вероятность ошибки декодирования в области эффективной работы дМПД на три и более порядков.

7. Предложена методика применения дМПД для защиты файлов от искажений при длительном хранении. На базе данной методики было разработано программное средство МТЮРпЛей, быстродействие которого в десятки раз превышает быстродействие программ-аналогов при сопоставимой эффективности восстановления данных.

8. Разработаны программные средства для исследования эффективности дМПД.

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

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

1. Золотарёв В.В., Овечкин Г.В., Овечкин П.В. Сравнение алгоритмов декодирования помехоустойчивых кодов для цифровых систем связи // Материалы 11-й Межд. науч.-техн. конф. «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». Рязань: РГРТА, 2002, С. 91-93.

2. Овечкин Г.В., Овечкин П.В. Эффективность применения многопорогового декодера в каскадных схемах // Материалы 8-й Всероссийской науч.-техн. конф. «Новые информационные технологии в научных исследованиях и в образовании». Рязань: РГРТА, 2003, С. 131-132.

3. Овечкин Г.В., Овечкин П.В. Эффективность каскадной схемы кодирования на базе многопорогового декодера и кодов Хэмминга // Меж-вуз. сб. науч. тр. «Математическое и программное обеспечение вычислительных систем». Рязань: РГРТА, 2004, С. 79-82.

4. Золотарёв В.В., Епишина Т.А., Овечкин Г.В., Овечкин П.В. Программные средства моделирования цифрового спутникового канала связи // Материалы межвуз. науч.-техн. конф. студентов, молодых ученых и специалистов «Новые информационные технологии в учебном процессе и производстве». Рязань: РИМГОУ, 2004, С. 77-79.

5. Денисова М.А., Овечкин Г.В., Овечкин П.В. Применение многопорогового декодера в системах передачи данных с многопозиционными системами модуляции // Материалы 13-й Межд. науч.-техн. конф. «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». Рязань: РГРТА, 2004, С. 58-59.

6. Овечкин П.В., Цыплаков Д.А. Разработка методов декодирования помехоустойчивых кодов на базе многопороговых декодеров // Материалы всероссийского смотра-конкурса научно-технического творчества студентов высших учебных заведений «Эврика-2005». Новочеркасск, 2005, Часть 1.,С. 140-144.

7. Овечкин Г.В., Овечкин П.В. Построение самоортогональных кодов устойчивых к эффекту размножения ошибок // Мат. 14-й Межд. науч.-техн. конф. «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». Рязань: РГРТА, 2005, С. 70-71.

8. Золотарёв В.В., Овечкин Г.В., Овечкин П.В. Многопороговые декодеры: новые достижения // Мат. 14-й Межд. науч.-техн. конф. «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». Рязань: РГРТА, 2005, С. 57-58.

9. Гринченко H.H., Овечкин Г.В., Овечкин П.В. Развитие многопороговых алгоритмов декодирования помехоустойчивых кодов // Мат. науч.-практ. конф. «Научные исследования и их практическое применение. Современное состояние и пути развития». Одесса: Черноморье, 2005, Том 7, С. 13-14.

10. Овечкин П.В. Каскадное кодирование на базе многопороговых декодеров // Материалы 52-й студенческой науч.-техн. конф. «Математическое и программное обеспечение вычислительных систем». Рязань: РГРТА, 2005, С. 30.

11. Золотарёв В.В., Овечкин Г.В., Овечкин П.В. Современные методы помехоустойчивого кодирования для высокоскоростных спутниковых систем связи // Материалы 10 Всероссийской науч.-техн. конф. «Новые информационные технологии в научных исследованиях и в образовании НИТ-2005». Рязань: РГРТА, 2005, С. 2-3.

12. Гринченко H.H., Овечкин П.В. Свидетельство РОСПАТЕНТ №2006614261 о регистрации программы для ЭВМ «Имитационная модель многопорогового декодера помехоустойчивых кодов» (MultiDec) от 17.12.06.

13. Гринченко H.H., Золотарёв В.В., Овечкин Г.В., Овечкин П.В. Применение многопорогового декодера в каналах со стираниями // Труды НТОРЭС им. А.С.Попова, 2006, С. 338-340.

14. Гринченко H.H., Овечкин Г.В., Овечкин П.В. Вопросы применения многопороговых декодеров в каналах связи со стираниями // Межвуз. сб. науч. тр. «Математическое и программное обеспечение вычислительных систем». Рязань: РГРТА, 2006, С. 47-50.

15. Овечкин П.В. Эффективность использования многопорогового декодера в каналах связи со стираниями // мат. Всероссийской научно-технической конференции НИТ-2006. Рязань: 2006, С. 74-76.

16. Гринченко H.H., Овечкин Г.В., Овечкин П.В. Разработка каскадных схем кодирования на основе многопороговых декодеров // 8-я межд. конф. и выст. «Цифровая обработка сигналов и ее применение». М.: 2006, Том 1,С. 60-63.

17. Гринченко H.H., Золотарёв В.В., Овечкин Г.В., Овечкин П.В. Многопороговое декодирование в каналах с многопозиционной модуляцией // Вестник РГРТУ, Вып. 19,2006, С. 179-182.

18. Овечкин П.В. Использование программных средств имитации цифрового спутникового канала в учебном процессе // Материалы XII межвузовской научно-методической конференции «Методы организации учебного процесса в ВУЗе». Рязань: РГРТУ, 2007, С. 73-74.

19. Золотарёв В.В., Овечкин Г.В., Овечкин П.В. Эффективность многопороговых декодеров при использовании многопозиционных ФМ и KAM // 9-я межд. конф. и выст. «Цифровая обработка сигналов и ее применение». М.: 2007, Том 1, С. 5.

20. Овечкин П.В. Помехоустойчивое кодирование в широковещательном видео // Межвуз. сб. науч. тр. «Математическое и программное обеспечение информационных систем». Рязань: РГРТУ, 2007, С. 68-71.

21. Овечкин П.В. Использование недвоичных многопороговых декодеров в магнитных и оптических запоминающих устройствах // 10-я Межд. конф. «Цифровая обработка сигналов и ее применение, DSPA-08». М.: 2008.

22. Овечкин П.В. Каскадные схемы на основе недвоичного многопорогового декодера // Мат. 15-й Межд. науч.-техн. конф. «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». Рязань: РГРТУ, 2008, С. 34-35.

23. Овечкин Г.В., Овечкин П.В. Использование многопороговых декодеров в системах дистанционного зондирования Земли // V Конференция молодых ученых, посвященная Дню космонавтики «Фундаментальные и прикладные космические исследования». М.: ЙКИ РАН, 2008, С. 33.

24. Овечкин П.В. Применение недвоичного многопорогового декодера для защиты файлов от искажений // 11-я Межд. конф. «Цифровая обработка сигналов и ее применение, DSPA-09». М.: 2009, С. 200-202.

25. Овечкин Г.В., Овечкин П.В. Оптимизация структуры недвоичных самоортогональных кодов для схем параллельного кодирования II Труды НИИР, №2,2009.

26. Овечкин П.В. Использование многопороговых декодеров в системах хранения больших объемов данных // VI Конференция молодых ученых, посвященная Дню космонавтики «Фундаментальные и прикладные космические исследования». М.: ИКИ РАН, 2009, С. 33-34.

Овечкин Павел Владимирович

РАЗРАБОТКА АЛГОРИТМОВ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ НЕДВОИЧНЫХ МНОГОПОРОГОВЫХ ДЕКОДЕРОВ В СИСТЕМАХ ПЕРЕДАЧИ И ХРАНЕНИЯ БОЛЬШИХ ОБЪЕМОВ ИНФОРМАЦИИ

Автореферат

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

Подписано в печать 19.05.2009 г. Формат бумаги 60x84 1/16. Бумага офсетная. Печать ризографическая. Усл. печ. л. 0,93. Уч.-изд. л. 1,0. Тираж 100 экз.

Отпечатано в ЗАО «Колорит», г. Рязань, Первомайский проспект, д. 37/1.

Введение.

Глава 1 Анализ современных методов помехоустойчивого кодирования. Выбор направлений исследования.

1.1 Структурная схема систем передачи и хранения информации.

1.2 Помехоустойчивое кодирование. Цель кодирования. Критерии эффективности.

1.3 Недвоичные коды.

1.4 Схема кодирования, используемая в аудио компакт-дисках.

1.5 Схема кодирования, используемая в обычных компакт-дисках.

1.6 Схема кодирования, используемая в ОЛШ дисках.

1.7 Использование кодов Рида-Соломона для защиты файлов от искажений.

1.8 Выводы.

Глава 2 Исследование недвоичного многопорогового декодера.

2.1 Алгоритм недвоичного многопорогового декодирования.

2.2 Исследование возможностей дМПД в каналах с пакетирующимися ошибками.

2.3 Использование дМПД в устройствах хранения данных.

2.4 Методика применения многопороговых декодеров в каналах со стираниями.

2.5 Методика применения многопороговых декодеров в каналах со стираниями и искажениями.

2.6 Использование недвоичного многопорогового декодера для защиты файлов от искажений.

2.6.1 Применение обычного дМПД для защиты файлов от искажений

2.6.2 Использование дМПД, способного исправлять стирания, для защиты файлов от искажений.

2.7 Выводы.

Глава 3 Алгоритмы улучшения характеристик недвоичных многопороговых декодеров.

3.1 Алгоритм построения наиболее эффективных недвоичных самоортогональных кодов.

3.2 Алгоритм ускорения работы порогового элемента недвоичного многопорогового декодера.

3.3 Каскадная схема кодирования, состоящая из недвоичного самоортогонального кода и кода контроля по модулю д.

3.4 Недвоичные коды Хемминга.

3.5 Каскадная схема, состоящая из недвоичного многопорогового декодера и декодера недвоичного кода Хемминга.

3.6 Аналитические оценки вероятности ошибки декодирования на выходе каскадной схемы, состоящей из недвоичного СОК и недвоичного кода Хэмминга.

3.7 Аналитические оценки вероятности ошибки декодирования каскадной схемы кодирования, состоящей из недвоичного СОК и недвоичного расширенного кода Хэмминга.

3.8 Экспериментальная оценка эффективности использования каскадной схемы кодирования, состоящей из недвоичного СОК и недвоичных кодов Хэмминга.

3.9 Выводы.

Глава 4 Программные средства моделирования недвоичных многопороговых декодеров и каналов связи. Программные средства для защиты файлов от искажений.

4.1 Программные средства моделирования недвоичных многопороговых декодеров.

4.1.1 Структура программных средств моделирования недвоичных многопороговых декодеров.

4.1.2 Модель д-ичного симметричного канала.

4.1.3 Модель канала Гилберта-Эллиота.

4.1.4 Модель канала с ошибками и стираниями.

4.1.5 Обеспечение точности и достоверности результатов моделирования.

4.2 Программные средства для защиты файлов от искажений.

4.2.1 Структура программных средств для защиты файлов от искажений.

4.2.2 Условия работы программы.

4.2.3 Руководство пользователя.

4.3 Выводы.

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

Огромный вклад в развитие теории кодирования внесли такие ученые, как К. Шеннон [72], В.А. Котельников [42], В.В. Зяблов [4,5], К.Ш. Зигангиров [19], В.В. Золотарёв [25, 28, 66], А. Витерби [9], Дж. Месси [43], Р. Галлагер [11, 78], Д. Форни [71], Л.М. Финк [70], В.Л. Банкет [1, 2], Дж. Возенкрафт [10], Е. Берлекэмп [3], Э.Л. Блох [4, 5] и др.

В настоящее время специалисты в области помехоустойчивого кодирования проявляют большой интерес к недвоичным кодам, работающим с цифровыми данными на уровне символов, например, с байтами информации.'Недвоичные коды применяются в каналах с группирующимися ошибками, в качестве составляющих элементов различных каскадных кодов, для защиты от ошибок информации на различного рода носителях (CD, DVD, Blu-ray и др.).

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

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

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

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

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

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

- разработать и исследовать алгоритмы построения наиболее эффективных недвоичных самоортогональных кодов (СОК) для дМПД, использование которых позволит повысить достоверность передачи и хранения информации;

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

- разработать и исследовать каскадные схемы коррекции ошибок на основе дМПД, позволяющие уменьшить вероятность ошибки декодирования по сравнению с базовым некаскадным методом;

- разработать программные средства для исследования эффективности дМПД;

- разработать программные средства для защиты файлов от искажений.

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

Основные положения, выносимые на защиту:

- алгоритм построения эффективных недвоичных самоортогональных кодов для дМПД;

- алгоритм работы недвоичного порогового элемента, позволяющий значительно ускорить работу дМПД;

- доказательство теоремы о стремлении решения декодера каскадного кода, состоящего из недвоичного СОК и кода контроля по модулю к решению оптимального декодера;

- каскадная схема кодирования, состоящая из недвоичного самоортогонального кода и модифицированного недвоичного кода Хэмминга.

Практическая ценность работы. Разработанный алгоритм построения недвоичных самоортогональных кодов для схем параллельного кодирования позволяет приблизить область эффективной работы дМПД к пропускной способности канала более чем на 13%. Предложенный алгоритм работы недвоичного порогового элемента позволяет повысить быстродействие недвоичного многопорогового декодера более чем в 2 раза. Разработанная каскадная схема на базе недвоичного самоортогонального кода и модифицированного недвоичного кода Хэмминга позволяет уменьшить частоту появления ошибок на выходе дМПД в области его эффективной работы более чем на 3 порядка. Программные средства на основе недвоичного многопорогового декодера для защиты файлов от искажений при длительном хранении информации позволяют ускорить процессы кодирования и восстановления информации в десятки раз по сравнению с известными программами-аналогами при сопоставимой эффективности восстановления данных.

Внедрение результатов работы. Результаты диссертационной работы были использованы: ООО «Объединенные радиоэлектронные технологии» при разработке аппаратуры передачи информации, предназначенной для работы в условиях городской застройки; Институтом космических исследований Российской академии наук при разработке исходных данных на наземный комплекс приема, обработки и распределения данных КНА «Фобос-Грунт»; разработанные программные средства моделирования недвоичного многопорогового алгоритма декодирования и его модификаций используются в учебном процессе Рязанского государственного радиотехнического университета, что подтверждается актами о внедрении.

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

- корректным использованием теории вероятностей и математической статистики;

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

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

Апробация работы. Результаты работы докладывались на следующих конференциях и семинарах:

1. 11-я, 13-я, 14-я и 15-я международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». - 2002 г., 2004 г., 2005 г., 2008 г., Рязань.

2. Всероссийская научно-техническая конференция «Новые информационные технологии в научных исследованиях и в образовании, НИТ». - 2003 г., 2005 г., 2006 г., Рязань.

3. Межвузовская научно-техническая конференция студентов, молодых ученых и специалистов «Новые информационные технологии в учебном процессе и производстве» . — 2004 г., Рязань.

4. 52-я студенческая научно-техническая конференция; «Математическое и программное обеспечение вычислительных систем». - 2005 г., Рязань.

5. Научно-практическая конференция «Научные исследования и их практическое применение. Современное состояние и пути развития», 2005 г., Одесса.

6. Всероссийский смотр-конкурс научно-технического творчества «Эв-рика-2005». - 2005 г., Новочеркасск.

7. 8-я, 9-я, 10-я, 11-я международная конференция и выставка «Цифровая обработка сигналов и ее применение». - 2006 г., 2007 г., 2008 г, 2009 г., Москва.

8. Межвузовская научно-методическая конференция «Методы организации учебного процесса в ВУЗе» - 2007 г., Рязань.

9. 5-я и 6-я конференция молодых ученых, посвященная Дню космонавтики «Фундаментальные и прикладные космические исследования». - 2008 г., 2009 г., Москва.

Публикации. По теме диссертации опубликовано 26 работ, из них 18 в соавторстве. В их числе 1 статья в журналах, рецензируемых ВАК, 4 статьи в межвузовских сборниках научных трудов, 20 тезисов докладов на международных и всероссийских конференциях. Разработан и зарегистрирован в Российском агентстве по патентам и товарным знакам 1 пакет программ.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка и двух приложений. Содержит 131 страницу, 3 таблицы, 57 рисунков. Библиографический список состоит из 86 наименований.

ЗАКЛЮЧЕНИЕ

Проведенные исследования позволяют сформулировать основные выводы и результаты:

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

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

3. Предложен алгоритм построения наиболее эффективных недвоичных самоортогональных кодов для схем параллельного кодирования. Применение таких кодов позволило приблизить области эффективной работы #МПД для кодов с Я= 1/2 на 13% и для малоизбыточных кодов с Я=7/8 на 20% к границе Шеннона, определяющей потенциальные корректирующие возможности кодов.

4. Предложен новый алгоритм работы недвоичного порогового элемента дМПД, применение которого позволило повысить быстродействие д-МПД более чем в 2 раза.

5. Доказана теорема о стремлении решения декодера каскадного кода, состоящего из недвоичного СОК и кода контроля по модулю к решению оптимального декодера.

6. Впервые была рассмотрена и исследована каскадная схема кодирования, состоящая из недвоичного СОК и недвоичных кодов Хэмминга. Получены аналитические оценки эффективности данной каскадной схемы. Показано, что использование предложенной каскадной схемы позволяет уменьшить вероятность ошибки декодирования в области эффективной работы дМПД на три и более порядков.

7. Предложена методика применения #МПД для защиты файлов от искажений при длительном хранении. На базе данной методики было разработано программное средство МТОРгсйес^ быстродействие которого в десятки раз превышает быстродействие программ-аналогов при сопоставимой эффективности восстановления данных.

8. Разработаны программные средства для исследования эффективности дМПД.

1. Банкет B.JL, Дорофеев В.М. Цифровые методы в спутниковой связи. -М.: Радио и связь, 1988, 240 с.

2. Банкет B.JL, Золотарёв В.В. Эффективность многопозиционных систем модуляции и многопорогового декодирования // В сб.: «ЕС Всесоюзная школа-семинар по вычислительным сетям». М.-Пушкино, 1984, Ч. 3.2.

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

4. Блох Э.Л., Зяблов В.В. Линейные каскадные коды М.: Наука, 1982.

5. Блох Э.Л., Зяблов В.В. Обобщенные каскадные коды М.: Связь, 1976.

6. Брауде-Золотарёв Ю.М., Золотарёв В.В., Шанина Н.И. Перспективные методы помехоустойчивого кодирования // Труды НИИР. М.: 1980, №1, с. 38-42.

7. Вентцель Е.С. Теория вероятностей М.: Наука, 1964, 576с.

8. Вентцель Е.С., Овчаров Л.А. Прикладные задачи теории вероятностей-М.: Радио и связь, 1983, 416 с.

9. Витерби А. Границы ошибок для сверточных кодов и асимптотически оптимальный алгоритм декодирования // Некоторые вопросы теории кодирования. М.: Мир, 1970, с. 142-165.

10. Возенкрафт Дж., Рейффен Б. Последовательное декодирование. 1963.

11. Галлагер Р. Теория информации и надежная связь М.: Советское радио, 1974.

12. Гринченко H.H., Золотарёв В.В., Овечкин Г.В., Овечкин П.В. Многопороговое декодирование в каналах с многопозиционной модуляцией // Вестник РГРТУ, Вып. 19, 2006, с. 179-182.

13. Гринченко H.H., Золотарёв В.В., Овечкин Г.В., Овечкин П.В. Применение многопорогового декодера в каналах со стираниями // Труды НТОРЭС им. А.С.Попова, 2006, с. 338-340.

14. Гринченко H.H., Овечкин Г.В., Овечкин П.В. Вопросы применения многопороговых декодеров в каналах связи со стираниями // Межвуз. сб. науч. тр, «Математическое и программное обеспечение вычислительных систем». Рязань, РГРТА, 2006, с. 47-50.

15. Гринченко H.H., Овечкин Г.В., Овечкин П.В. Разработка каскадных схем кодирования на основе многопороговых декодеров // 8-я межд. конф. и выст. «Цифровая обработка сигналов и ее применение». М.: 2006, Том 1, с. 60-63.

16. Гринченко H.H., Овечкин П.В. Свидетельство РОСПАТЕНТ №2006614261 о регистрации программы для ЭВМ «Имитационная модель многопорогового декодера помехоустойчивых кодов» (MultiDec) от 17.12.06.

17. Зигангиров К.Ш. Процедуры последовательного кодирования М.: Связь, 1974.

18. Золотарёв В.В. Каскадные схемы МПД декодирования для больших баз данных // Мобильные системы, М., 2008, №1.

19. Золотарёв В.В. Многопороговое декодирование для информационных потоков с байтовой структурой // Мобильные системы, М., 2006, №3, с. 25-27.

20. Золотарёв В.В. Недвоичные многопороговые декодеры // Цифровая обработка сигналов, 2003, № 3, с. 10-12.

21. Золотарёв В.В. Обобщение алгоритма МПД на недвоичные коды // Мобильные системы, М., 2007, №2, с. 36-39.

22. Золотарёв В.В. Параллельное кодирование в каналах СПД // Вопросы кибернетики, 1986, Вып. 120.

23. Золотарёв В.В. Теория и алгоритмы многопорогового декодирования М.: Радио и связь, Горячая линия - Телеком, 2006, 232 с.

24. Золотарёв В.В., Овечкин Г.В. Аппаратная реализация многопороговых декодеров // 7-я Межд. конф. и выст. «Цифровая обработка сигналов и ее применение». М.: 2005, т.2, с.451-454.

25. Золотарёв В.В., Овечкин Г.В. Помехоустойчивое кодирование. Методы и алгоритмы. Справочник М.: Горячая линия - Телеком, 2004, 126 с.

26. Золотарёв В.В., Овечкин Г.В. Эффективные алгоритмы помехоустойчивого кодирования для цифровых систем связи // Электросвязь. 2003, № 9, с. 34-37.

27. Золотарёв В.В., Овечкин Г.В., Овечкин П.В. Многопороговые декодеры: новые достижения // Мат. 14-й Межд. науч.-техн. конф. «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». Рязань: РГРТА, 2005, с. 57-58.

28. Золотарёв В.В., Овечкин Г.В., Овечкин П.В. Эффективность многопороговых декодеров при использовании многопозиционных ФМ и KAM // 9-я межд. конф. и выст. «Цифровая обработка сигналов и ее применение». М.: 2007, Том 1, с. 5.

29. Зубарев Ю.Б., Золотарёв В.В. Многопороговые декодеры: перспективы аппаратной реализации // 7-я Международная конференция «Цифровая обработка сигналов и ее применение». М., 2005, Вып. VII-1, с. 68-69.

30. Зубарев Ю.Б., Золотарёв В.В., Овечкин Г.В., Строков В.В., Жуков С.Е. Многопороговые декодеры для высокоскоростных спутниковых каналов связи: новые перспективы // Электросвязь. М.: 2005, № 2, с. 10-12.

31. Зюко А.Г., Фалько А.И., Панфилов И.П., Банкет В.Л., Иващен-ко П.В. Помехоустойчивость и эффективность систем передачи информации М.: Радио и связь, 1985, 272 с.

32. Калиткин H.H. Численные методы М.: Наука, 1978, 512 с.

33. Кельтон В., Jloy А. Имитационное моделирование. Классика CS. 3-е изд. СПб.: Питер, Киев, Издательская группа BHV, 2004.

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

35. Олифер В.Г., Олифер H.A. Компьютерные сети. Принципы, технологии, протоколы: Учебник для вузов. 2-е изд. СПб.: Питер, 2003.

36. Котельников B.JI. Теория потенциальной помехоустойчивости — М.-Л.: Госэнергоиздат, 1956.

37. Месси Дж. Пороговое декодирование — М.: Мир, 1966.

38. Мешков A.B., Тихомиров Ю.В. Visual С++ и MFC СПб.: БХВ-Петербург, 2003.

39. Многопороговые декодеры. Веб-сайт ИКИ РАН www.mtdbest.iki.rssi.ru.

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

41. Нейфах А.Э. Сверточные коды для передачи дискретной информации М.: Наука, 1979, 222 с.

42. Овечкин Г.В., Овечкин П.В. Оптимизация структуры недвоичных самоортогональных кодов для схем параллельного кодирования //Труды НИИР, 2009 г., №2.

43. Овечкин Г.В., Овечкин П.В. Построение самоортогональных кодов устойчивых к эффекту размножения ошибок // Мат. 14-й Межд. науч.-техн. конф. «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций». Рязань: РГРТА, 2005, с. 70-71.

44. Овечкин Г.В., Овечкин П.В. Эффективность каскадной схемы кодирования на базе многопорогового декодера и кодов Хэмминга // Межвуз. сб. науч. тр. «Математическое и программное обеспечение вычислительных систем» Рязань: РГРТА, 2004, с. 79-82.

45. Овечкин П.В. Использование многопороговых декодеров в системах хранения больших объемов данных // VI Конференция молодых ученых, посвященная Дню космонавтики. «Фундаментальные и прикладные космические исследования». Москва, ИКИ РАН, 2009, с. 33-34.

46. Овечкин П.В. Использование недвоичных многопороговых декодеров в магнитных и оптических запоминающих устройствах// 10-я Международная конференция «Цифровая обработка сигналов и ее применение, 08РА-08», М., 2008.

47. Овечкин П.В. Использование программных средств имитации цифрового спутникового канала в учебном процессе // Материалы XII межвузовской научно-методической конференции «Методы организации учебного процесса в ВУЗе» Рязань, РГРТУ, 2007, с. 73-74.

48. Овечкин П.В. Каскадное кодирование на базе многопороговых декодеров // Материалы 52-й студенческой науч.-техн. конф. «Математическое и программное обеспечение вычислительных систем» Рязань: РГРТА, 2005, с. 30

49. Овечкин П.В. Каскадные схемы на основе недвоичного многопорогового декодера //Мат. 15-й Межд. науч.-техн. конф. «Проблемы передачи и обработки информации в сетях и системах телекоммуникаций» Рязань: РГРТУ, 2008, с. 34-35.

50. Овечкин П.В. Помехоустойчивое кодирование в широковещательном видео // Межвуз. сб. науч. тр. «Математическое и программное обеспечение информационных систем». Рязань, РГРТУ, 2007, с. 68-71.

51. Овечкин П.В. Применение недвоичного многопорогового декодера для защиты файлов от искажений // 11-я Международная конференция «Цифровая обработка сигналов и ее применение, DSPA-09». М., 2009, с. 200-202.

52. Овечкин П.В. Эффективность использования многопорогового декодера в каналах связи со стираниями // мат. Всероссийской научно-технической конференции НИТ-2006. Рязань: 2006, с. 74-76.

53. Полляк Ю.Г. Вероятностное моделирование на ЭВМ М.: Сов. радио, 1971.

54. Полляк Ю.Г., Филимонов В.А. Статистическое моделирование средств связи М.: Радио и связь, 1988.

55. Райе Дж. Матричные вычисления и математическое обеспечение — М.: Мир, 1984, 264 с.

56. Рид И.С., Соломон Г. Полиномиальные коды над некоторыми конечными полями // Кибернетический сборник, вып 7, 1983, с. 74-79.

57. Самойленко С.И., Давыдов A.A., Золотарёв В.В., Третьякова Е.И. Вычислительные сети М.: Наука, 1981, 277 с.

58. Скляр Б. Цифровая связь. Теоретические основы и практическое применение М., 2003.

59. Советов Б.Я., Яковлев С.А. Моделирование систем: Учеб. для вузов М.: Высш. шк., 2001.

60. Феллер В. Введение в теорию вероятностей и ее приложения М.: Мир, 1967, 498 с.

61. Финк JI.M. Теория передачи дискретных сообщений М.: Советское радио, 1970.

62. Форни Д. Каскадные коды / Пер. с англ. под ред. Самойленко С.И. -М.: Мир, 1970, 208 с.

63. Шеннон К.Е. Математическая теория связи. Работы по теории информации и кибернетике. 1963, с. 243-332.

64. Chen J., Tanner R. M. A hybrid coding scheme for the Gilbert-Elliott channel // IEEE Transactions on Communications, №54(10), p. 1787-1796, 2006.

65. Chen L., Carrasco R. A., Chester E. G. Decoding Reed-Solomon codes using the Guruswami-Sudan algorithm // University of Newcastle-upon-Tyne, United Kingdom, 2006.

66. Davey M. Error-correction using Low-Density Parity-Check Codes -Gonville and Caius College Cambridge, December, 1999, 107 p.

67. Davey M.C., MacKay D.J.C. Low density parity check codes over GF(g) // IEEE Comm. Letters, 2(6), 1998, p. 165-167.

68. Declercq D., Fossorier M. Extended minsum algorithm for decoding LDPC codes over GF(#) // IEEE International Symp. on Inf. Theory, 2005, p.464-468.

69. Gallager R. Low-density parity-check codes // IRE Trans. Information Theory. January 1962, p. 21-28.

70. Mushkin M., Bar-David I. Capacity and Coding for the Gilbert-Elliott channels // IEEE Trans. Inform. Theory, vol. IT-35 №.6, p. 1277-1290, 1989.

71. Plank J. S. A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems // Software Practice & Experience, September, 1977, p. 9951012.

72. Richardson T. Modern coding theory Cambridge University Press, 2008, 272 p.

73. Shokrollahi A., Wang W. Low-density parity-check codes with rates very close to the capacity of the q-ary symmetric channel for large q IIISIT, Chicago, USA, 2004.

74. Sripimanwat K. Turbo Code Applications Springer, Netherlands, 2005, p. 386.

75. Sudan M. Decoding of Reed Solomon codes beyond the error correction bound//J. Compl., 13, 1997, p. 180-193.

76. Weidmann C. Coding for the q-ary symmetric channel with moderate q II Proceedings IEEE International Symposium Information Theory, July 6-11, 2008, Toronto, Canada.

77. Zhang F., Pfister H. List-Message Passing Achieves Capacity on the q-ary Symmetric Channel for Large q II In Proc. IEEE Global Telecom. Conf., Washington, DC, Nov. 2007, p. 283-287.