WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     || 2 | 3 |

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

О В Е Ч К И Н Павел Владимирович РАЗРАБОТКА АЛГОРИТМОВ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ НЕДВОИЧНЫХ МНОГОПОРОГОВЫХ ДЕКОДЕРОВ В СИСТЕМАХ ПЕРЕДАЧИ И ХРАНЕНИЯ БОЛЬШИХ ОБЪЕМОВ ИНФОРМАЦИИ Специальность 05.13.13 – «Телекоммуникационные системы и компьютерные сети»

АВТОРЕФЕРАТ

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

Рязань 2009 2

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

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

Официальные оппоненты: доктор физико-математических наук Назаров Лев Евгеньевич кандидат технических наук, доцент Гаврилов Александр Николаевич

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

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

Рязань, ул. Гагарина, 59/1.

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

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

Ученый секретарь диссертационного совета Д 212.211.02 к.т.н., доцент И.А. Телков 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Разработанная каскадная схема на базе недвоичного самоортогонального кода и модифицированного недвоичного кода Хэмминга позволяет уменьшить частоту появления ошибок на выходе qМПД в области его эффективной работы более чем на 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 статья в журналах, рецензируемых ВАК, статьи в межвузовских сборниках научных трудов, 20 тезисов докладов на международных и всероссийских конференциях. Разработан и зарегистрирован в Российском агентстве по патентам и товарным знакам 1 пакет программ.

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

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

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

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

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

Наиболее широкое применение в реальных системах передачи и хранения информации из недвоичных кодов нашли коды Рида-Соломона.

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

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

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

Pages:     || 2 | 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»