Анализ эффективности декодирования циклических кодов Рида-Соломона с использованием двойственного базиса тема диссертации и автореферата по ВАК РФ 05.12.13, кандидат наук Владимиров, Сергей Сергеевич

• Владимиров, Сергей Сергеевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Владимиров, Сергей Сергеевич

Оглавление

Введение

1 Эффективность методов декодирования. Характеристики методов и их оценка

1.1 Характеристики методов декодирования помехоустойчивых кодов

1.1.1 Вероятностные характеристики

1.1.2 Энергетическая эффективность

1.1.3 Временные характеристики

1.1.4 Сложность реализации

1.2 Оценка вероятностных характеристик методом моделирования

1.3 Модели каналов передачи данных

1.3.1 Двоичный симметричный канал

1.3.2 Канал Гилберта-Эллиотта

1.3.3 Канал с аддитивным белым гауссовским шумом

1.4 Выводы

2 Циклические коды Рида-Соломона

2.1 Особенности построения кодов Рида-Соломона

2.1.1 Коды РС

2.1.2 Эквивалентные коды РС

2.2 Методы декодирования циклических кодов РС

2.2.1 Алгебраический метод декодирования

2.2.2 Определительный метод декодирования

2.3 Выводы

3 Декодирование кодов РС с использованием двойственного базиса

3.1 Двойственный базис конечного поля

3.2 Принципы мажоритарного декодирования кодов РС методом двойственного базиса

3.2.1 Определение информационных элементов по к-элементному участку кодовой последовательности кода РСЭ

3.2.2 Процесс декодирования кодовой комбинации кода РСЭ

по методу МДБ

3.2.3 Оценка сложности реализации декодера МДБ

3.3 Повышение корректирующих свойств кодов РСЭ путём применения децимаций

3.3.1 Возможные методы повышения исправляющей способности алгоритма мажоритарного декодирования на основе МДБ

3.4 Анализ алгоритмов декодирования кодов РСЭ с использованием двойственного базиса и принципы их реализации

3.4.1 Использование МДБ для обнаружения ошибок

3.4.2 Использование МДБ для декодирования кодовых комбинаций с ошибками

3.4.3 Использование МДБ для декодирования кодовых комбинаций со стираниями

3.5 Выводы

4 Оценка эффективности метода декодирования кодов РСЭ на

основе двойственного базиса

4.1 Определение необходимого для проведения экспериментов объёма выборки

4.2 Оценка вероятностных характеристик метода декодирования кодов РСЭ на основе двойственного базиса

4.2.1 Оценка вероятностных характеристики для цифрового двоично-симметричного канала

4.2.2 Оценка вероятностных характеристики для канала с аддитивным белым гауссовским шумом

4.2.3 Оценка вероятностных характеристики для модели цифрового канала Гилберта-Эллиотта

4.3 Пороговый алгоритм декодирования кодов РСЭ на основе двойственного базиса

4.3.1 Описание порогового алгоритма МДБ

4.3.2 Вероятностные характеристики порогового алгоритма МДБ

в цифровом канале ДСК

4.3.3 Вероятностные характеристики порогового алгоритма МДБ

в цифровом канале с группированием ошибок СЕС

4.4 Выводы

5 Разработка инструментария для проведения моделирования и экспериментального исследования эффективности кодов Рида-Соломона

5.1 Поля Галуа, и основные операции над элементами ноля

5.1.1 Поле Галуа и его свойства

5.1.2 Представление элементов поля и операции над полиномами

5.1.3 Основные действия над элементами поля

5.2 Программируемый калькулятор Галуа

5.2.1 Обгдее описание программного комплекса. Сравнение с имеющимися аналогами

5.2.2 Реализация алгоритма построения поля Галуа. Реализация операций логарифмирования и антилогарифмирования

5.2.3 Реализация основных операций над элементами поля

5.2.4 Реализация операций над двоичными многочленами

5.2.5 Распознавание вводимой формулы

5.2.6 Примеры формульных выражений и функций

5.3 Сетевой программируемый калькулятор Галуа

5.4 Программная реализация системы моделей для проведения исследований

5.4.1 Общее описание программных моделей

5.4.2 Программная модель канала Гилберта-Эллиотта с группированием ошибок

5.5 Выводы

Заключение. Выводы диссертационной работы

Список литературы

Приложения

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

процесс Санкт-Петербургского государственного университета телекоммуникаций им. проф. М. А. Бонч-Бруевича

Введение диссертации (часть автореферата) на тему «Анализ эффективности декодирования циклических кодов Рида-Соломона с использованием двойственного базиса»

Введение

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

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

Свойства кодов Рида-Соломона подробно рассмотрены в работах Пи-терсона У., Касами Т., Кларка Дж., Берлекэмпа Э. Повышенный интерес к кодам РС подтверждается и тем, что разработано значительное количество алгоритмов декодирования таких кодов, как в частотной, так и во временной области. В России исследованиями кодов РС и алгоритмов их декодирования занимаются в различных университетах, среди которых можно выделить СПбГУТ, СПбГПУ, ЮФУ, МФТИ, институты РАН. Среди учёных, занимающихся данным вопросом, можно назвать Э. М. Габидулина, В. В. Де-ева, О. С. Когновицкого, В. М. Охорзина, Д. С. Кукунина, А. Э. Маевского, В. В. Мкртичяна, В. А. Варгаузина, И. А. Цикина и других. В работах профессора О. С. Когновицкого рассмотрена применимость двойственного базиса поля Галуа в вопросах декодирования циклических кодов с учетом их рекуррентных свойств. Рациональный выбор того или иного алгоритма требует проведения сравнительного анализа по корректирующим способностям различных методов декодирования кодов Рида-Соломона, в том числе методов декодирования с использованием двойственного базиса.

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

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

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

Методы исследования. Проводимые исследования основываются на теории полей Галуа, теории двойственного базиса поля Галуа, теории кодирования, теории рекуррентных последовательностей и теории вероятностей. Для проведения численных расчетов и построения графиков использовались программные пакеты: Octave, LibreOffice Cale, Maxima, Gnuplot и другие. Программное обеспечение, необходимое для решения поставленных в диссертации задач, написано на языке Pascal в среде разработки Geany с использованием компилятора Free Pascal 2.4. Для написания программных моделей использовалась система численных вычислений Octave и одноимённый язык программирования.

Научная новизна. Научная новизна работы состоит в следующем:

а) Исследован новый метод декодирования кодов PC как рекуррентных последовательностей с использованием двойственного базиса.

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

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

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

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

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

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

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

Реализация результатов работы. Основные научные результаты работы внедрены в практическую деятельность ЗАО «НПП «ИСТА-Системс», а также используются в учебном процессе Санкт-Петербургского государственного университета телекоммуникаций им. проф. М. А. Бонч-Бруевича, что подтверждено соответствующими актами внедрения.

Апробация работы. Результаты работы обсуждались и были одобрены па 61,62,63 НТК профессорско-преподавательского состава СПбГУТ и на пяти конференциях с международным участием. По результатам диссертации опубликованы 10 работ [1-Ю], две из которых напечатаны в журналах из

перечня ВАК [4,7]. Получено свидетельство о государственной регистрации программы для ЭВМ [1.1]. Были выполнены две научно-исследовательские работы по теме диссертации [12,13].

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

Структура и объем работы. Диссертация состоит из введения, 5 глав и заключения. Работа содержит 159 страниц машинописного текста, 68 рисунков, 7 таблиц и список литературы из 68 наименований.

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

а) Результаты исследования эффективности декодирования кодов Рида-Соломона на основе двойственного базиса (Метод двойственного базиса).

б) Пороговый алгоритм декодирования кодов Рида-Соломона на основе двойственного базиса.

в) Программный комплекс для моделирования и исследования эффективности кодов Рида-Соломона.

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

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

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

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

Глава 3 посвящена алгоритму декодирования эквивалентных кодов Рида-Соломона с использованием двойственного базиса. В главе приведены механизм и алгоритмы декодирования эквивалентных кодов Рида-Соломона на основе двойственного базиса.

В главе 4 приведена оценка эффективности алгоритма декодирования на основе двойственного базиса. Показано сравнение исследуемого алгоритма с другими алгоритмами декодирования кодов Рида-Соломона. Рассмотрен разработанный автором пороговый алгоритм декодирования кодов Рида-Соломона на основе двойственного базиса.

Глава 5 посвящена разработке инструментария для исследования кодов РС и проведения имитационного моделирования — «Программируемого калькулятора Галуа», а также разработке программных моделей для системы численных вычислений Octave. Данный программный комплекс является одним из основных средств проведения экспериментальных исследований в диссертационной работе.

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

1 Эффективность методов декодирования. Характеристики методов и их оценка

1.1 Характеристики методов декодирования помехоустойчивых кодов

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

К таким характеристикам относят следующие:

а) вероятностные характеристики;

б) энергетическую эффективность алгоритма;

в) временные характеристики;

г) сложность реализации алгоритма.

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

1.1.1 Вероятностные характеристики

К вероятностным характеристикам метода декодирования относят следующие [14]:

а) Вероятность обнаружения ошибки Р<эо — вероятность того, что в принятом кодовом слове будут обнаружены (но не исправлены) ошибки.

б) Вероятность необнаруженной ошибки Рцо — вероятность того, что ошибка в принятом кодовом слове будет не обнаружена.

в) Вероятность правильного декодирования Рпдк — вероятность того, что кодовое слово на выходе декодера совпадает с кодовым словом на входе кодера.

г) Вероятность неправильного декодирования -Рндк (англ. Word Error Rate, WER) — вероятность того, что кодовое слово на выходе декодера отличается от кодового слова на входе кодера.

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

е) Вероятность битовой ошибки рь (англ. Bit Error Rate, BER) — вероятность того, что бит кодового слова на выходе декодера отличается от соответствующего бита кодового слова на входе кодера.

Для сравнения систем связи между собой J1.M. Финком [15] предложено использовать два способа.

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

К недостаткам данного способа следует отнести то, что данная мера неприменима [15] для тех случаев, когда ошибки в принимаемом сообщении недопустимы, что характерно для многих систем передачи и хранения данных для электронных вычислительных машин. Поскольку именно в таких системах широко применяются помехоустойчивые коды, на практике чаще используют другой критерий оценки.

Второй способ заключается в использовании эквивалентной вероятности ошибки РэкВ) т-е. вероятности ошибки в постоянном симметричном двоичном канале без памяти, в котором система с примитивным кодированием (кодированием без избыточности) оказывается эквивалентной рассматриваемой системе [15,16].

Согласно формулам, введённым Финком [15], для систем с блочным кодом эквивалентная вероятность вычисляется через вероятность правильного декодирования -Рццк по формуле:

Рэкв = 1-[Рпдк]1Л, (1.1)

где г — количество двоичных единиц информации, содержащихся в кодовой комбинации.

Для (п, &)-кода РС г можно записать как:

г ~ к • га, (1.2)

где га — количество двоичных единиц информации в одном информационном символе.

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

Яжв = 1 - [-Рццк + Рот]1'1 • (1-3)

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

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

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

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

1.1.2 Энергетическая эффективность

Оценка энергетической эффективности метода декодирования оценивается на основании сравнения показателей энергетической эффективности передачи сообщения при исрользовапии определённого метода декодирования и передачи того же сообщения без применения кодирования [17].

Количественно энергетическая эффективность метода декодирования оценивается как уменьшение отношения сигнал/шум ЭКИ,), достигаемого при использовании данного метода декодирования. В цифровой связи чаще используется нормированная версия БИЯ, Еь/Щ — отношение энергии сигнала, приходящейся на 1 бит принимаемого сообщения (Еь), к энергетической спектральной плотности шума (А^) [18]. Оценка энергетической эффективности производится при данной вероятности битовой ошибки в канале передачи данных. Как правило, энергетическая эффективность выражается в децибелах и рассчитывается по формуле

с(дб)=Й)нк(ДБ)-(5)к(дб)' (ы)

где ~~' отношение Еь/Щ без использования помехоустойчивого кода,

а — отношение Еъ/Щ при использовании помехоустойчивого кода с

исследуемым алгоритмом декодирования.

1.1.3 Временные характеристики

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

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

1.1.4 Сложность реализации

Сложность реализации алгоритма декодирования (как программная, так и аппаратная) имеет большое значение [19], поскольку сложные методы декодирования могут иметь высокую энергетическую эффективность, но практическое использование данных алгоритмов будет невозможным.

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

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

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

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

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

1.2 Оценка вероятностных характеристик методом моделирования

Для определения характеристик и поведения сложных процессов и систем широко используется имитационное моделирование [20,21].

В работе Шеннона [20] приводится следующее определение имитационного моделирования.

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

Данное определение охватывает в частности и моделирование с использованием метода Монте-Карло, подробно рассмотренное в работах многих авторов, в качестве примера которых можно привести Дж. Клейиена [21] и Дж. С. Фишмана [22]. Клейнен [21] определяет метод Монте-Карло в широком смысле как любой способ решения модели, в котором используются случайные или псевдослучайные числа.

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

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

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

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

Способ определения вероятностных характеристик методом накопления статистики позволяет определить эти характеристики лишь с некоторой точностью, в зависимости от объёма выборки. Таким образом, данный способ позволяет получить лишь оценочные значения вероятностных характеристик, так называемую частоту или частость события [23,24]. Соответственно, в дальнейшем, когда речь будет идти о вероятностных характеристиках алгоритма, полученных в результате проведения моделирования, будут иметься в виду именно оценочные значения этих характеристик.

Точность полученных оценочных значений зависит от объёма накопленных данных. Далее в разделе 4.1 будет определено, какой объём выборки можно считать достаточным для проводимого в работе имитационного моделирования.

Само моделирование в работе проводилось при помощи ЭВМ с использованием системы компьютерной алгебры Octave и разработанного автором Программируемого калькулятора Галуа. Описание программных моделей и разработанного программного комплекса дано в разделе 5.

Рассмотрим блок-схему модели в общем виде (рисунок 1.1).

Рисунок 1.1 — Блок-схема программной модели для определения оценочных значений вероятностных характеристик алгоритмов декодирования в общем

виде

Рассмотрим приведённую блок-схему подробнее.

«Генератор информационных комбинаций», как следует из названия, служит для того, чтобы создавать случайные информационные комбинации, которые далее будут переданы на вход кодирующего устройства исследуемого помехоустойчивого кода. На схеме данное устройство названо «Кодер». Поскольку кодовые комбинации помехоустойчивого кода представляют из себя данные в цифровом виде, то в случае использования модели аналогового канала передачи данных необходимо использовать «Устройство сопряжения с каналом». «Устройство сопряжения с каналом», установленное на

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

«Канал передачи данных» представляет из себя модель канала передачи данных, в которой па полученную кодовую комбинацию накладывается ошибка, в зависимости от заданных параметров канала. Используемые в работе модели каналов описаны в разделе 1.3.

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

1.3 Модели каналов передачи данных

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

В физическом канале сигнал S(t) подвергается воздействию шума n(t) [19]. Схема этого явления показана на рисунке 1.2.

Рисунок 1.2 — Структурная схема физического канала в общем виде

Для количественной оценки степени влияния шума п(£) на сигнал б'(^) обычно используют отношение сигнал-шум (SNR), определяемое как отношение мощности сигнала к мощности шума. Часто данное отношение выражается в децибелах.

Выделяют два основных вида моделей каналов передачи данных. Непрерывные (аналоговые) каналы и дискретные (цифровые) каналы.

Непрерывные каналы имеют непрерывный сигнал £(£) на входе и непрерывный сигнал Я(£) на выходе, которые являются непрерывной функцией от времени.

Дискретные каналы имеют на входе дискретные кодовые символы х^, а на выходе — дискретные кодовые символы у^ в общем случае не совпадающие с х{ [15].

Почти во всех реальных линиях связи дискретный канал содержит внутри себя непрерывный канал, на вход которого подаются сигналы б'(^), а с выхода снимаются искаженные помехами сигналы Я(£) [15]. Свойства этого непрерывного канала наряду с характеристиками модулятора и демодулятора однозначно определяют все параметры дискретного канала. Поэтому иногда дискретный канал называют дискретным отображением непрерывного канала. Однако при математическом исследовании дискретного канала обычно отвлекаются от непрерывного канала и действующих в нем помех и определяют дискретный канал через алфавит источника {я;о> ^ъ • • • > ха-1}-> вероятности появления символов алфавита, скорость передачи символов, алфавит получателя {т/о, 2/1, ■ • •, Ус}-1} и значения переходных вероятностей РЫх3), где г = 0,1,... 3 = 0,1, ...,<? [15,25].

Список литературы диссертационного исследования кандидат наук Владимиров, Сергей Сергеевич, 2013 год

Список литературы

[1] Владимиров С.С. Программируемый калькулятор Галуа // 61-я научно-техническая конференция профессорско-преподавательского состава, научных сотрудников и аспирантов: материалы. — СПб. : ГОУВПО СПб-ГУТ, 2009.-С. 46-47.

[2] Владимиров С.С. Моделирование процессов мажоритарного декодирования комбинации эквидистантного кода по К линейно-независимым элементам // 62-я научно-техническая конференция профессорско-преподавательского состава, научных сотрудников и аспирантов: материалы,- СПб. : ГОУВПО СПбГУТ, 2010.- С. 78-79.

[3] Владимиров С.С. Программируемый калькулятор Галуа // VIII Всероссийская научно-практическая конференция с международным участием по теоретическим основам проектирования и разработке распределённых информационных систем. ПРИС-2010: материалы конференции, 25 мая 2010 г. / Под ред. проф. Г.М. Рудаковой.— Красноярск : «ЛИТЕРА-припт», 2010. - С. 29-34.

[4] Владимиров С.С. Моделирование процессов мажоритарного декодирования комбинации эквидистантного кода по К линейно-независимым элементам // Научно-технические ведомости СПбГПУ. Серия «Информатика. Телекоммуникации. Управление». — 2010. — № 3 (101). — С. 149-156. — ISSN: 1994-2354.

[5] Владимиров С.С., Когновицкий О.С. Исследование алгоритма мажоритарного декодирования кода Рида-Соломона на основе двойственного базиса // 63-я научно-техническая конференция профессорско-преподавательского состава, научных сотрудников и аспирантов: материалы.- СПб. : ГОУВПО СПбГУТ, 2011,- С. 53-56.

[6] Когновицкий О.С., Владимиров С.С. Расширенный мажоритарный метод декодирования комбинаций эквидистантного циклического кода // Международная научно-техническая и научно-методическая конференция «Актуальные проблемы инфотелекоммуникаций в науке и образовании». № 64. 20-24 февраля 2012 года: материалы. — СПб. : Издательство СПбГУТ, 2012.-С. 150-154.

[7] Владимиров С.С. Исследование алгоритма мажоритарного декодирования кода Рида-Соломона на основе двойственного базиса // Вестник Поволжского государственного технологического университета. Серия «Радиотехнические и инфокоммупикациоппые системы». — 2012. — № 1 (15). - С. 60-66. - ISSN: 2306-2819.

[8] Когиовицкий О.С., Владимиров С.С. Расширенный мажоритарный метод декодирования децимированных комбинаций эквидистантного циклического кода // Региональная информатика (РИ-2012). Юбилейная XIII Санкт-Петербургская международная конференция «Региональная информатика (РИ-2012)». Санкт-Петербург, 24-26 октября 2012 г.: Материалы конференции. - СПб. : СПОИСУ, 2012.- С. 99-100.

[9] Владимиров С.С. Оценка исправляющей способности алгоритма декодирования кодов РСЭ на основе двойственного базиса в случае использования канала АБГШ // Актуальные проблемы инфотелекоммуникаций в науке и образовании. Н-я Международная научно-техническая и научно-методическая конференция: сб. науных статей / Под ред. С. М. Доцен-ко. — СПб. : Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича, 2013. — С. 86-89. — URL: http ://itt.sut.ru/index.php/conf sut2013.

[10] Владимиров С.С. Оценка исправляющей способности алгоритма декодирования кодов РСЭ на основе двойственного базиса в канале ДСК // Тезисы докладов Четвертой Международной научно-практической конференции «Методы и средства кодирования, защиты и сжатия информации» г. Винница, 23-25 апреля 2013 года / Под ред. В.А. Лужецько-го ; Винницкий национальный технический университет. — Винница : ПП «ТД «Едельвейс i К», 2013. - С. 61-64.

[11] Владимиров С.С. NetGFCalc v.l «Программируемый Сетевой Калькулятор Галуа, версия 1» // Свидетельство о государственной регистрации программы для ЭВМ № 2010615406. - 2010. - 08/2010. - С. 1.

[12] Повышение эффективности декодирования циклических кодов, как рекуррентных последовательностей, на основе использования двойственного базиса : отчет о НИР (заключ.) : № гос. per. 01200964865 / СПбГУТ ;

исполн.: О.С. Когновицкий, Д.С. Кукунии, С.С. Владимиров, М.Ю. Сергеева. - СПб. : 2009.

[13] Исследование корректирующих свойств циклических кодов рида-соломона как рекуррентных последовательностей, декодируемых с использованием двойственного базиса : отчет о НИР (заключ.) : № гос. per. 01201066842 / СПбГУТ ; исполн.: О.С. Когновицкий, С.С. Владимиров, A.A. Губина. - СПб. : 2010.

[14] Moon Todd К. Error correction coding: mathematical methods and algorithms. — John Wiley and Sons, 2005. — 804 p.

[15] Финк JI.M. Теория передачи дискретных сообщений. — М. : «Сов. радио», 1970. - 728 с.

[16] Деев В.В. Методы модуляции и кодирования в современных системах связи. - Спб. : Наука, 2007. - 267 с. - ISBN: 978-5-02 - 025182-3.

[17] Варгаузин В.А., Цикии И.А. Методы повышения энергетической и спектральной эффективности цифровой радиосвязи: учеб. пособие. — СПб. : БХВ-Петербург, 2013. - 352 с. - ISBN: 978-5-9775-0878-0.

[18] Скляр Б. Цифровая связь. Теоретические основы и практическое применение / Под ред. A.B. Назареико. — М. : Издательский дом «Вильяме», 2003. - 1104 с. - ISBN: 5-8459-0497-8.

[19] Золотарёв В.В., Овечкин Г.В. Помехоустойчивое кодирование. Методы и алгоритмы: Справочник / Под ред. чл.-корр. РАН Ю.Б. Зубарева. — М. : Горячая линия-Телеком, 2004. — 126 с.

[20] Шеннон Р. Имитационное моделирование систем — искусство и наука / Под ред. Е.К. Масловского. - М. : Мир, 1978. — 421 с.

[21] Клейнен Дж. Статистические методы в имитационном моделировании / Под ред. Ю.П. Адлера и В.Н. Варыгина. — М. : «Статистика», 1978. — 221 с.

[22] Fishman G.S. Monte Carlo: concepts, algorithms, and applications.— Springer, 1996. - 698 p. - ISBN: 0-387-94527-X.

[23] Кибзуи А.И., Горяинова Е.Р., Наумов А.В. Теория вероятностей и математическая статистика. Базовый курс с примерами и задачами: Учеб. пособие / Под ред. А.И. Кибзуна. - М. : ФИЗМАТЛИТ, 2005. - 232 с. -ISBN: 5-9221-0626-0.

[24] Козлов М.В., Прохоров А.В. Введение в математическую статистику.— М. : Изд-во МГУ, 1987. - 264 с.

[25] Теория электрической связи: учебное пособие / К.К. Васильев, В.А. Глушков, А.В. Дормидонтов, А.Г. Нестеренко ; Под ред. К.К. Васильева. - Ульяновск : УлГТУ, 2008. - 452 с. - ISBN: 978-5-9795-0203-8.

[26] Гладких А.А. Основы теории мягкого декодирования избыточных кодов в стирающем канале связи. — Ульяновск : УлГТУ, 2010. — 379 с.

[27] MacKay David J. С. Information Theory, Inference, and Learning Algorithms. — Cambridge : Cambridge University Press, 2003. — 640 p. — ISBN: 0-521-64298-1.

[28] Richardson Т., Urbanke R. Modern Coding Theory.— Cambridge : Cambridge University Press, 2008.- 590 p. - ISBN: 978-0-5218-5229-6.

[29] Hasslinger G., Hohlfeld O. The Gilbert-Elliott Model for Packet Loss in Real Time Services on the Internet // Measuring, Modelling and Evaluation of Computer and Communication Systems (MMB), 2008 14th GI/ITG Conference -. - 2008. - P. 1-15.

[30] Elliott E. O. Estimates of error rates for codes on burst-noise channels // Bell System Technical Journal. - 1963. - Vol. 42. - P. 1977-1997. - ISSN: 00058580.

[31] Gilbert E. N. Capacity of a burst-noise channel // Bell System Technical Journal.- 1960.-September.- Vol. 39,- P. 1253-1265.- ISSN: 00058580.

[32] Rezaeian M. Computation of capacity for Gilbert-Elliott channels, using a statistical method // Communications Theory Workshop, 2005. Proceedings. 6th Australian. - 2005. - P. 56-61.

[33] Massey James L. Deep-Space Communications and Coding: A Marriage Made in Heaven //in Proceedings of the 1992 DLR Seminar Advanced Methods for Satellite and Deep Space Comm. — Springer, 1992. — P. 1-17.

[34] The Key Technologies of Deep Space Communications / Xiao Song, Li Yunsong, Bai Baoming, ZhouYouxi // China Communications. — 2006. — December. - P. 82-94.

[35] A Study on performance evaluation of Reed-Solomon Codes through an AWGN Channel model for an efficient Communication System / V. Korrapati, M.V.D. Prasad, D.V. Reddy, G.A. Tej // International Journal of Engineering Trends and Technology. — 2013.—April. — Vol. 4, no. 4.— P. 1038-1041.-ISSN: 2231-5381.

[36] BER performance of OFDM-BPSK, -QPSK, -QAM over AWGN channel using forward Error correcting code / V. Sharma, A. Shrivastav, A. Jain, A. Panday // International Journal of Engineering Research and Applications.— 2012. — May-Jun. - Vol. 2, no. 3.- P. 1619-1624.— ISSN: 2248-9622.

[37] Морелос-Сарагоса P. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. Мир связи. — М. : Техносфера, 2005. — 320 е. - ISBN: 5-94836-035-0.

[38] Габидуллин Э.М., Афанасьев В.Б. Кодирование в радиоэлектронике.— М. : Радио и связь, 1986. — 176 с.

[39] Галлагер Р. Теория информации и надежная связь / Под ред. М.С. Пин-скера, Б.С. Цыбакова. — М. : «Сов. радио», 1974. — 720 с.

[40] Lin Shu, Costello D.J. Error Control Coding: Fundamentals and Applications. — Printice-Hall, 1983. — 617 p.

[41] Когновицкий О.С. Двойственный базис и его применение в телекоммуникациях. - СПб. : Линк, 2009. - 424 с. - ISBN: 978-5-98595-020-5.

[42] Кларк Д.К., Кейн Д.Б. Кодирование и исправление ошибок в системах цифровой связи. Статистическая теория связи. — М. : «Радио и Связь», 1987. - 392 с.

[43] Берлекемр Э. Алгебраическая теория кодирования. — М. : Мир, 1972. — 480 с.

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

[45] Singleton Richard С. Maximum distance q-nary codes // Information Theory, IEEE Tmnsactkms on. - 1964. - Vol. 10, no. 2. - R 116-118. - ISSN: 00189448.

[46] Вернер M. Основы кодирования. Учебник для ВУЗов. Мир программирования. - М. : Техносфера, 2006. - 288 с. - ISBN: 5-94836-019-9.

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

[48] Massey J. L. Shift-Register Synthesis and BCH Decoding // Information Theory, IEEE Transacüons on.- 1969.-Jan.- Vol. 15.- P. 122-127. — ISSN: 0018-9448.

[49] Reed-Solomon Error Correction : Technical Report : WHP 031 / BBC Research &; Development; Executor: C.K.P. Clarke. — Salford : 2002. — July.

[50] Федоров С. В. Аппаратная реализация решателя ключевых уравнений Берлекэмпа-Месси для кодов Рида-Соломона на ПЛИС // Наука и образование: электронное научно-техническое издание.— 2011.— № 7.— С. 1-11.-ISSN: 1994-0408.

[51] Тайлеб М.Н. Аппаратная реализация кодеков Рида-Соломона на ПЛИС на основе высокоуровневых параметризованных описаний функциональных узлов : автореферат диссертации / М.Н. Тайлеб ; Национальный исследовательский университет МЭИ. — Москва, 2012.

[52] Когновицкий О.С. Основы циклических кодов. Учебное пособие. — Л. : ЛЭИС, 1990.- 64 с.

[53] Лидл Р., Нидеррайтер Г. Конечные поля: В 2-х т. : Пер. с англ / Под ред. В.И. Нечаева. - М. : Мир, 1988. - 430 с. - ISBN: 978-5-0300-0064-0.

[54] Теория кодирования. / Т. Касами, Н. Токура, Е. Ивадари, Я. Ирагаки. — М. : Мир, 1978. - 576 с.

[55] Кукунин Д.С. Модель системы с адаптивным выбором кода // Научно-технические ведомости СПбГПУ. Серия «Информатика. Телекоммуникации. Управление». - 2008. - Т. 5, № 65. - С. 81-86. - ISSN: 2304-9766.

[56] Кукунин Д.С., Когновицкий О.С. Методика оценки качества канала в процессе передачи данных // Научно-технические ведомости СПбГПУ. Серия «Информатика. Телекоммуникации. Управление». — 2008. — Т. 5, № 65. - С. 86-92. - ISSN: 2304-9766.

[57] Кукунин Д.С. Анализ эффективности декодирования циклических кодов с использованием двойственного базиса : диссертация / Д.С. Кукунин ; Санкт-Петербургский государственный университет телекоммуникаций им. М.А. Бонч-Бруевича. — Санкт-Петербург, 2009.

[58] Чеботарёв Н.Г. Основы теории Галуа. Часть 1. — M.-JI. : ОНТИ, 1934.— 221 с.

[59] Чеботарёв Н.Г. Основы теории Галуа. Часть 2. - M.-JI. : ОНТИ, 1937. — 162 с.

[60] Постников М.М. Основы теории Галуа. — М. : Физматгиз, 1960. — 124 с.

[61] Постников М.М. Теория Галуа. — М. : Физматгиз, 1968. — 218 с.

[62] Винберг Э.Б. Малая теорема Ферма и ее обобщения // Математическое просвещение. - Сер. 3 № 12.- М. : МЦНМО, 2008.- С. 43-53.

[63] Кукунин Д.С., Когновицкий О.С. Сетевая версия калькулятора Галуа // 57-я Юбилейная НТК профессорско-преподавательского состава: мат-лы. - СПб. : ГОУВПО СПбГУТ, 2005. - С. 25.

[64] Кукунин Д.С. Калькулятор Галуа с удаленным доступом через Интернет // 59-я НТК профессорско-преподавательского состава: мат-лы. — СПб. : ГОУВПО СПбГУТ, 2007.- С. 31.

[65] Fast Galois Field Arithmefcic Library in C/C++ : Technical Report : UT-CS-07-593 / University of Tennessee. Department of Computer Science ; Executor: J.S. Plank. — Tennessee : 2007.

[66] Кукунин Д.С. Дискретное логарифмирование в полях Галуа с использованием контрольных точек // Научно-технические ведомости СПбГПУ. Серия «Информатика. Телекоммуникации. Управление». — 2009. — Т. 2, № 76. - С. 185-192. - ISSN: 2304-9766.

[67] Сканави М.И. Элементарная математика. — М. : Наука, 1972.— 592 с.

[68] A Gilbert-Elliot Bit Error Model and the Efficient Use in Packet Level Simulation : Technical Report : TKN-99-002 / Technical University Berlin. Telecommunication Networks Group ; Executor: J.-P. Ebert, A. Willig. — Berlin : 1999.-March.

157