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

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

Владимиров Сергей Сергеевич

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

05.12.13 - Системы, сети и устройства телекоммуникаций

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

10 ОКТ 2013

Санкт-Петербург -2013

005534325

Работа выполнена в Федеральном государственном образовательном бюджетном учреждении высшего профессионального образования "Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А. Бонч'-Бруевича".

Ведущая организация Закрытое акционерное общество «Институт телекоммуникаций», г. Санкт-Петербург.

Защита состоится 23 октября 2013 года в 14.00 на заседании диссертационного совета Д 219.004.02 при Федеральном государственном образовательном бюджетном учреждении высшего профессионального образования «Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А. Бонч-Бруевича», 193232, Санкт-Петербург, пр. Большевиков, д. 22, ауд. 554.

С диссертацией можно ознакомиться в библиотеке Федерального государственного образовательного бюджетного учреждении высшего профессионального образования «Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А. Бонч-Бруевича» по адресу Санкт-Петербург, наб. реки Мойки, д. 65 .

Автореферат разослан 23 сентября 2013 года.

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

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

Когновицкий Олег Станиславович

Официальные оппоненты: Деев Владимир Викторович,

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

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

к.т.н., доцент

В.Х. Харитонов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы. Результаты работы обсуждались и были одобрены на пяти международных конференциях и трех научно-технических конференциях профессорско-преподавательского состава СПбГУТ. По результатам диссертации опубликовано две статьи в изданиях из перечня, рекомендованного ВАК, а также принято участие в двух НИР по тематике диссертации. На разработанный программный комплекс "Программируемый сетевой калькулятор Га-луа" получено свидетельство о государственной регистрации программы для ЭВМ.

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

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

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

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

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

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

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

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

В первой главе рассматривается понятие эффективности методов декодирования, а также приводятся критерии и методы ее оценки.

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

1. Вероятностные характеристики. Основным параметром, по которому проводилось сравнение с прочими алгоритмами декодирования, является эквивалентная вероятность ошибки Рэкв- Для выбранных вариантов кодов были получены графики вероятностей правильного и

неправильного декодирования, а также вероятности отказа от декодирования.

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

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

предложена формула (1), учитывающая этот фактор.

i

Рэкв = 1 - Кдк + Родк]7. (1)

где РПдк — вероятность правильного декодирования кодовой комбинации помехоустойчивого кода, Родк — вероятность отказа от декодирования, i = к • т — количество двоичных единиц информации, содержащихся в кодовой комбинации (n, fe) кода, т — количество двоичных единиц информации в одном информационном символе.

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

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

В качестве моделей каналов передачи данных в диссертационной работе были выбраны следующие модели:

• Дискретный канал без памяти — двоичный симметричный канал (ДСК);

• Непрерывный канал с аддитивным белым гауссовским шумом (АБПП);

• Дискретный канал с памятью — канал Гилберта-Эллиотта (Gilbert-Elliott Channel, GEC).

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

Коды Рида-Соломона (РС) представляют из себя недвоичные циклические коды Боуза-Чоудхури-Хоквингема, символы которых представляют собой элементы поля Галуа ОР(<у), где ц = 2т — порядок поля, а т — степень поля Галуа.

Для (п, к) кодов РС для всех п и к справедливо неравенство:

О < к < п < 2т -1, (2)

где к — число информационных символов, подлежащих кодированию, а п — число кодовых символов в кодовом блоке. Для большинства (п, к) кодов РС

(п,к) = (я - 1,ч - 1 - 2Г), (3)

где / — количество ошибок, исправляемых кодом, ап — к = И = г — число избыточных символов.

Для задания циклических кодов РС используется порождающий многочлен д-1 (х) степени с1ТП1П — 1 = п — к = г вида:

Ь+2£-1

лС*)= П (4)

]=ь

где Ъ — целое число. Обычно Ъ = 0 или Ъ = 1.

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

= п - к + 1. (5)

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

Здесь [^означает наибольшее целое, не превышающее х.

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

к

д(х) = + а (7)

1=1

где £1 — корни образующего многочлена. Часто выбирают п = 2т — 1, тогда для эквивалентного (дуального) кода д(х) = ——.

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

Многочлен ,д(х) является характеристическим многочленом д(х) = д0хк + з1х*~1 + д2хк~2 + ... + дк_хх + дк ; д, е С¥(2т), (8) порождающим возвратные рекуррентные последовательности {5} = (х0 з2 53 ... 52т_2) с периодом п = 2т — 1 и элементами, принадлежащими полю СР(2т).

В соответствии с видом характеристического многочлена д(х), у которого всегда д0 = 1, возвратная последовательность {я} будет удовлетворять рекуррентному уравнению:

Ъ = 1-1 + 92^1-2 + - + 9к-1*1-к+1 + 9к51-к- (9)

где I > к и, кроме того, индекс г приводится по модулю 2т — 1.

В работе было проведено сравнение кодов РСЭ с сопряженными и несопряженными корнями по распределению весов. Результаты были получены посредством математического расчета, а потом подтверждены путем имитационного моделирования. Было определено, что коды РСЭ с сопряженными корнями образующего полинома д(х) имеют меньшее минимальное кодовое расстояние, нежели коды с несопряженными корнями. На рисунке 2 приведено распределение весов для кода (31,5).

Несояряжённые корни

1.4е+07 1.2е+07 1С+07 8е+0б бе 4-06 4е+06 2е+06

: :

..........;...........;......... 11926 126 10 291

..........

97Г6г 6723

27 28 29 30 3: Вес кодового слова, ш

Сопряжённые корни

..... .......;.......... .39373760

18 20 22 24 26 28 30 32 Вес кодового слова, ш

Рисунок 2 — Распределение весов для кода РСЭ (31,5).

Как можно видеть из рисунка 2, код РСЭ (31,5) с сопряженными корнями имеет минимальное кодовое расстояние Лт1П — 16 и кратность гарантийно исправляемых ошибок 1 = 1. Для кода РСЭ (31,5) с несопряженными корнями минимальное кодовое расстояние ЛтхП = 27, а кратность гарантийно исправляемых ошибок С = 13.

Кодирующее устройство эквивалентного (дуального) кода Рида-Соломона может строиться по принципу систематического или несистематического кодирования.

В случае систематического кодирования кода РСЭ информационными элементами кода (п, к) будут начальные к элементов последовательности {5}, т. е. Остальные избыточные элементы кодовой комбинации, как ре-

куррентной последовательности, определяются по рекуррентной формуле (9).

В основе несистематического кодирования кодов РСЭ лежит тот факт, что кодовые комбинации кода РСЭ являются возвратными последовательностями, произвольный элемент которых может быть выражен через корни £1,£2,...,Ек характеристического многочлена д(х) и соответствующие корням элементы поля А1,А2, — ,Ак как

= + А2е12 + ... + Ак£1к. (10)

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

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

• алгоритм Берлекэмпа-Месси, частным случаем которого является определительный метод декодирования;

• алгоритм Евклида;

• алгоритм Питерсона-Горенштейна-Цирлера.

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

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

Базис, двойственный левому степенному (1, £,..., £т_1), позволяет выразить произвольный элемент поля Гапуа СР(2т) через линейно-независимые элементы — элементы двойственного базиса ш2,..., <ит), которые могут быть определены по формуле (11), выведенной профессором Когновицким О.С.

Ут~]п е1

2„=о ср(2Ж) (П)

1 Р'(«|)

где р! — коэффициенты порождающего характеристического многочлена поля р(х), а £[ — корни многочлена р(х).

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

кодовой комбинации {х} согласно формулам (12), выведенным на кафедре ОПДС СПбГУТ при участии автора.

А1 = £Г'Саи5г + «12^+1 + ... +

Аг = Е2'(«21+ «22^+1 + - + а2/с5г+/с-1); (12)

= Ек1(.ак151 + + — + где постоянные коэффициенты а^ ¿,/ = 1,2,...,к, зависят от образующего

многочлена кода д(х) и определяются по выражению

ъизьч-М. ср(24 (13)

1 д&д

через корни и коэффициенты д]- многочлена д(х).

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

Рисунок 3 — Функциональная схема устройства вычисления информационных элементов

согласно формулам (12)

На рисунке 4 представлен принцип мажоритарного декодирования для алгоритма МДБ. В дальнейшем накопления элементов, представленные графически, будем называть для большей наглядности термином "деревья", совокупность "деревьев" — "лесом". Данные термины были введены ранее Д. Кукуни-ным в его работе по исследованию кодов БЧХ.

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

С одной ошибкой

2 3 4

Порядковый номер набора

п 1с наборов

1 1 ■ ,

Порядковый номер набора ин дюпмационных элементов

инсЬопмапнонных элементов

Рисунок 4 — Принцип мажоритарного декодирования для алгоритма МДБ

Таким образом, мажоритарное декодирование кода РСЭ для алгоритма МДБ может быть классифицировано как декодирование по принципу максимального правдоподобия.

На рисунке 5 представлена блок-схема соответствующего алгоритма.

Начало алгоритма

I

Получаем 1-е к эл-тов кодов. комО-п

Получаем СЛСД-Й З.Ч-Т кодов, комб-и

Да

Записываем иглучгпим? :4ломенты в регистр и ИМЧИРЛЖ'М 1шф<Т»М. 5.1-Ти

Записываем £н"*тультат ^ и 7япл. пагмггикя /

Накоплено одинаковых реп-

С

Т!Г7Г7>

^пльтатсиз; /

Понята вгм кпмЛпнжшя?

С

>

Есть опиты одниякхтым !«тг!

Выная рстультпга

>

^^^ Кошц а.ич>р итм я ^^^

Выпод сигнала «откач ог дектлрояания»

>

Рисунок 5 — Блок-схема алгоритма декодирования кода РСЭ на основе двойственного базиса

Следует отметить, что при отсутствии ошибок или их малом количестве необязательно дожидаться приема всей кодовой комбинации. Достаточно получить "дерево" высотой [^+1], что позволяет принять решение о верности принимаемой комбинации еще до завершения приема.

Путем анализа формул (12) и схемы на рисунке 3 была определена формула (14) для оценки сверху сложности реализации алгоритма МДБ по критерию количества операций в конечном поле для (п, к) кода РС.

«операций = пк(-2к + ^ (14)

Проведённые рассчёты показали, что алгоритм МДБ имеет значительно меньшую сложность для кодов РС с большой избыточностью по сравнению с синдромным методом декодирования на основе алгоритма Берлекэмпа-Месси, формула для оценки сложности которого показана, например, в работах Э.М. Габидулина. Так, для кода РС (31,5) алгоритм МДБ имеет более чем в два раза меньшую сложность: 1705 операций в поле, против 3939 операций для син-дромного метода на основе алгоритма Берлекэмпа-Месси.

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

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

В этом случае справедливы выведенные на кафедре ОПДС СПбГУТ теоремы идентичности и однозначности, подробно описанные и доказанные в работах Когновицкого О.С.

В таблице приведен пример децимаций для кодовой комбинации кода длиной 7.

Таблица

Пример децимаций для кодовой комбинации кода длиной 7

Индекс децимации Децимированная комбинация

q = 2° = 1 Г{*0 53 56} Ос 1 е е3 г3}

ц = 21 = 2 ({щ щ. "2 "з "+ щ "б} {и}2 = \ Оо Х2 Я* «1 ®5> ({1 £ £ £3 0 1 £3}

Ч = 22 = 4 С 0>О »1 1>2 VI V* V;; {и}4 = < 54 % ( {1 £ 0 Е3 £ Е3 1}

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

дут дополнительно определяться информационные элементы поля. Таким образом, декодирование кодов РС сводится к накоплению элементов поля Галуа по сумме последовательно проводимых децимаций.

На рисунке 6, на примере декодирования комбинации кода РС (7,3) с двумя ошибками и информационными элементами (е6, е, £4) показано, как децимации повышают достоверность декодирования.

Без децимаций

Количество сочетаний для данного индекса децимаций Общее количества сочетаний

II I Ц

00 00 00 00 00 00

Однократные децимации 0 = 1)

Количество сочетаний для данного индекса децимаций Общее количество сочетаний

1

1 1

Л_

11

90 90 90

г51 <.<■ «? г4 г* г

Двукратные децимации 0-2)

Количество сочетаний для данного индекса децимаций

Общее количество сочетаний • ' -

Рисунок 6 — Пример декодирования кода РС (7,3) с использованием децимаций

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

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

На рисунке 7 приведены зависимости вероятности Рэкв от вероятности ошибки в канале ДСК для различных кодов РС (31, к).

Из графиков видно, что в случае каналов с равномерным распределением ошибок наилучшие результаты показывает алгоритм синдромного декодирования. А среди алгоритмов МДБ наилучшие результаты получаются при использовании кода с несопряженными корнями, что обуславливается его более высоким с(т(п по сравнению с кодом с сопряженными корнями.

Аналогичные результаты были получены в результате имитационного моделирования, проведенного для канала АБГШ.

0.02 0.015 0.01 0.005 0

0.001

Эквивалентная вероятность ошибки для кодов РСЭ (31,х)

Код РС (31,5)

МДБ сопр., без леи. (1) МДБ сопр., с дец. (2)

0.004

Код РС (31,15)

Рисунок 7 — Зависимость Рэкв от вероятности битовой ошибки р0 в канале ДСК

На рисунке 8 показаны графики зависимости вероятностных характеристик от средней вероятности битовой ошибки ре в канале Гильберта-Эллиотта (СЕС) для кода (31,5). Как можно видеть из приведенных графиков, алгоритм МДБ обеспечивает значительно большую вероятность правильного декодирования для канала с памятью, нежели синдромный метод. Как показали результаты статистического моделирования, для кода (31,5) при средней вероятности битовой ошибки ре = 0.15 алгоритм МДБ позволяет исправить порядка 70% ошибок, тогда как синдромный алгоритм — порядка 50% ошибок. Однако, из-за того, что при декодировании алгоритмом МДБ доля неправильно декодированных комбинаций выше за счёт уменьшения доли отказов от декодирования, эквивалентная вероятность ошибки для каналов с ре > 2 • 10~2 больше, чем в случае синдромного метода.

0.002 0.0015 0.001 0.0005 0

Эквивалентная вероятность ошибки

Вероятность прав, декодирования

0.05

МДБ несопр. корни (1) Алгебр, метод, БМ (2)

0.05

Рисунок 8 — Зависимость оценочных значений вероятностных характеристик от средней вероятное™ битовой ошибки ре в канале СЕС для кода РС (31,5)

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

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

На рисунке 9 приведены результаты имитационного моделирования для порогового МДБ для канала ДСК и кода РС (31,5).

Вероятность прав, декодирования Эквивалентная вероятность ошибки

Рисунок 9 — Вероятностные характеристики алгоритма МДБ для кода РСЭ (31,5) с несопряженными корнями образующего полинома при различных Д в канале ДСК

Как можно видеть из графиков, при увеличении параметра А вероятность неправильного декодирования и эквивалентная вероятность ошибки приближаются к нулю. При этом, вероятность правильного декодирования практически не изменяется. Таким образом, по достоверности передачи пороговый алгоритм МДБ не уступает синдромному методу. Скорость декодирования при этом не уменьшается, а сложность не возрастает.

Аналогичные результаты дает применение порога Д и для метода МДБ с децимациями. Однако, в случае использования кода РСЭ с сопряжеными корнями и МДБ с децимациями, применение порога нерационально, так как в этом случае становится существенно меньшим (¿т;п.

На рисунке 10 приведены графики с результатами применения порога А для канала с памятью в случае использования кода (31,5) с несопряженными корнями.

Из графиков видно, что введение Д практически не влияет на вероятность правильного декодирования, а вероятность неправильного декодирования и эквивалентная вероятность ошибки приближаются к нулю. Следует отметить, что увеличивать Д до больших значений не следует. Так, в приведенных графиках уже при Д= 3 эквивалентная вероятность ошибки снизилась на всем рассматриваемом диапазоне средней вероятности битовой ошибки ре в канале вЕС и составила значение не хуже Ю-7, и дальнейшее увеличение Д приводит лишь к некоторому уменьшению вероятности правильного декодирования.

Вероятность прав, декодирования Эквивалентная вероятность ошибки

Ре Ре

Рисунок 10 — Вероятностные характеристики алгоритма МДБ с децимациями для кода РСЭ (31,5) с несопряженными корнями образ)Ющего полинома при различных Д в канале GEC

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

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

Автором был разработан сетевой калькулятор, с доступом через сеть Интернет, предназначенный для исследования и моделирования кодов РС, а также для выполнения операций в полях Галуа. "Программируемый сетевой калькулятор Галуа" используется в учебном процессе на кафедре ОПДС СПбГУТ и является зарегистрированным продуктом в реестре программ для ЭВМ Российской Федерации. Номер государственной регистрации № 2010615406.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. Проведено исследование эффективности алгоритма декодирования циклических кодов Рида-Соломона на основе двойственного базиса (МДБ) и алгоритма декодирования кодов РС на основе двойственного базиса с применением децимаций.

2. Проведен сравнительный анализ эффективности методов декодирования кодов Рида-Соломона, в результате которого установлено, что алгоритм МДБ имеет меньшую сложность для кодов РС с большой избыточностью по сравнению с синдромным методом декодирования. Так, для кода (31,5) МДБ имеет более чем в два раза меньшую сложность: 1705 операций в поле, против 3939 операций. Это позволяет рекомендовать алгоритм МДБ для использования именно для таких кодов.

3. Показано, что алгоритм МДБ позволяет исправлять определённую долю ошибок, кратность которых превышает гарантированно исправляемую кратность ошибок в соответствии с ит;п кода.

4. Доказано, что алгоритм МДБ показывает лучшие результаты в каналах с группированием ошибок по доле исправляемых ошибок, что позволяет рекомендовать его к применению для таких каналов передачи данных. Так для кода (31,5) при средней вероятности битовой ошибки ре = 0.15 алгоритм МДБ позволяет исправить порядка 70% ошибок, тогда как син-дромный алгоритм — порядка 50% ошибок.

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

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

7. Разработан программный комплекс — "Программируемый калькулятор Галуа", предназначенный для исследования кодов Рида-Соломона и построения различных имитационных моделей. "Программируемый сетевой калькулятор Галуа" используется в учебном процессе на кафедре ОПДС СПбГУТ и является зарегистрированным продуктом в реестре программ для ЭВМ Российской Федерации.

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

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

2. Владимиров С.С. Оценка исправляющей способности алгоритма декодирования кодов РСЭ на основе двойственного базиса в случае использования канала АБГШ // "Актуальные проблемы инфотелекоммуникаций в науке и образовании". II-я Международная научно-техническая и научно-методическая конференция: сб. науных статей / Под ред. С. М. Доценко. — СПб. : Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича, 2013. — С. 86-89.

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

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

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

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

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

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

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

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

Подписано в печать 19.09.2013. Формат 60x84 1/16. Печ. л. 1,0. Тираж 100 экз. Отпечатано в СПбГУТ, 191186, Санкт-Петербург, наб. реки Мойки, 61

со

ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ

Федеральное государственное образовательное бюджетное учреждение

высшего профессионального образования «Санкт-Петербургский государственный университет телекоммуникаций

им. проф. М.А. Бонч-Бруевича»

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

Владимиров Сергей Сергеевич

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

05.12.13 — Системы, сети и устройства телекоммуникаций

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

СО

<о

со С\| Научный руководитель

0 доктор технических наук, профессор,

(N1 ^д Когновицкий Олег Станиславович

Санкт-Петербург -2013

Оглавление

Введение ..................................................................5

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

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

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

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

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

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

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

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

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

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

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

1.4 Выводы..............................24

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

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

2.1.1 Коды РС............................26

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

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

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

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

2.3 Выводы..............................54

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

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

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

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

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

по методу МДБ........................59

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

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

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

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

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

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

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

3.5 Выводы..............................83

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

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

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

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

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

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

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

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

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

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

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

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

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

4.4 Выводы..............................105

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.5 Выводы..............................145

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

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

Приложения...............................157

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

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

Введение

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

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

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

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

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

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

Методы исследования. Проводимые исследования основываются на теории полей Галуа, теории двойственного базиса поля Галуа, теории кодирования, теории рекуррентных последовательностей и теории вероятностей. Для проведения численных расчетов и построения графиков использовались программные пакеты: 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) — вероятность того, что кодовое слово на выходе декодера отличается от кодового слова на входе кодера.

д) Вероятность отказа в декодировании Лэдк в