Содержание к диссертации
Введение
1 Эффективность методов декодирования. Характеристики методов и их оценка 10
1.1 Характеристики методов декодирования помехоустойчивых кодов 10
1.1.1 Вероятностные характеристики 10
1.1.2 Энергетическая эффективность 13
1.1.3 Временные характеристики 14
1.1.4 Сложность реализации
1.2 Оценка вероятностных характеристик методом моделирования 15
1.3 Модели каналов передачи данных
1.3.1 Двоичный симметричный канал 19
1.3.2 Канал Гилберта-Эллиотта 20
1.3.3 Капал с аддитивным белым гауссовским шумом 23
1.4 Выводы 24
2 Циклические коды Рида-Соломона 26
2.1 Особенности построения кодов Рида-Соломона 26
2.1.1 Коды PC 26
2.1.2 Эквивалентные коды PC 29
2.2 Методы декодирования циклических кодов PC 35
2.2.1 Алгебраический метод декодирования 35
2.2.2 Определительный метод декодирования 43
2.3 Выводы 54
3 Декодирование кодов PC с использованием двойственного базиса 56
3.1 Двойственный базис конечного поля 56
3.2 Принципы мажоритарного декодирования кодов PC методом двойственного базиса
3.2.1 Определение информационных элементов по /с-элемент-ному участку кодовой последовательности кода РСЭ 57
3.2.2 Процесс декодирования кодовой комбинации кода РСЭ
по методу МДБ 59 Оценка сложности реализации декодера МДБ 62
Повышение корректирующих свойств кодов РСЭ путём при менения децимаций 64
1 Возможные методы повышения исправляющей способности алгоритма мажоритарного декодирования на основе МДБ 71
Анализ алгоритмов декодирования кодов РСЭ с использованием двойственного базиса и принципы их реализации 72
1 Использование МДБ для обнаружения ошибок 72
2 Использование МДБ для декодирования кодовых комбинаций с ошибками 73
3 Использование МДБ для декодирования кодовых комбинаций со стираниями 79
Выводы 83
Оценка эффективности метода декодирования кодов РСЭ на основе двойственного базиса 85
Определение необходимого для проведения экспериментов объёма выборки 85
Оценка вероятностных характеристик метода декодирова ния кодов РСЭ па основе двойственного базиса 88
1 Оценка вероятностных характеристики для цифрового двоично-симметричного канала 89
2 Оценка вероятностных характеристики для канала с аддитивным белым гауссовским шумом 91
3 Оценка вероятностных характеристики для модели цифрового канала Гилберта-Эллиотта 95
Пороговый алгоритм декодирования кодов РСЭ на основе двойственного базиса 97
1 Описание порогового алгоритма МДБ 97
2 Вероятностные характеристики порогового алгоритма МДБ
в цифровом канале ДСК .- 100
3 Вероятностные характеристики порогового алгоритма МДБ
в цифровом канале с группированием ошибок GEC 102
Выводы 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 Примеры формульных выражений и функций 1 5.3 Сетевой программируемый калькулятор Галуа 141
5.4 Программная реализация системы моделей для проведения исследований 1 5.4.1 Общее описание программных моделей 143
5.4.2 Программная модель капала Гилберта-Эллиотта с группированием ошибок 145
5.5 Выводы 145
Заключение. Выводы диссертационной работы 147
Список литературы
- Энергетическая эффективность
- Эквивалентные коды PC
- Определение информационных элементов по /с-элемент-ному участку кодовой последовательности кода РСЭ
- Определение необходимого для проведения экспериментов объёма выборки
Введение к работе
Актуальность проблемы. Помехоустойчивое кодирование занимает важное место в современных системах связи. На сегодняшний день в различных системах передачи данных существует большое количество способов помехоустойчивого кодирования, которые активно используются и, соответственно, сохраняют актуальность исследования. Данная работа посвящена изучению одного из наиболее широко используемых классов циклических помехоустойчивых кодов, а именно, кодов Рида-Соломона (PC).
Классическое описание кодов Рида-Соломона опирается на понятия минимального кодового расстояния и гарантированно исправляемой кратности ошибок, что способствует выбору кодов с заданными параметрами. Коды Рида-Соломона используются в системах хранения данных, в цифровом телевидении, в системах радиосвязи и в дальней космической связи, как отдельно, так и в составе турбо-кодов.
Свойства кодов Рида-Соломона подробно рассмотрены в работах Питер-сона У., Касами Т., Кларка Дж., Берлекэмпа Э. Повышенный интерес к кодам PC подтверждается и тем, что разработано значительное количество алгоритмов декодирования таких кодов, как в частотной, так и во временной области. В России исследованиями кодов PC и алгоритмов их декодирования занимаются в различных университетах, среди которых можно выделить СПбГУТ, СПбГПУ, ЮФУ, МФТИ, институты РАН. Среди учёных, занимающихся данным вопросом, можно назвать Э.М. Габидулина, В.В. Деева, О.С. Когновицкого, В.М. Охорзина, Д.С. Кукунина, А.Э. Маевского, В.В. Мкртичяна, В.А. Варгаузина, И.А. Цикина и др. В работах профессора Когновицкого О.С. рассмотрена применимость двойственного базиса поля Галуа в вопросах декодирования циклических кодов с учетом их рекуррентных свойств. Рациональный выбор того или иного алгоритма требует проведения сравнительного анализа по корректирующим способностям различных методов декодирования кодов Рида-Соломона, в том числе методов декодирования с использованием двойственного базиса.
Цель и задачи исследования. Целью диссертационной работы является исследование эффективности декодирования циклических кодов PC на основе двойственного базиса. Под эффективностью декодирования будем понимать корректирующие возможности кодов, рассматривая в качестве критериев эффективности эквивалентную вероятность ошибки в канале, а также сложность реализации декодирующего устройства.
В связи с этим выделены два направления, определяющие постановку задач диссертационной работы. Первое направление связано непосредственно с исследованием метода декодирования циклических кодов Рида-Соломона на основе двойственного базиса и его сравнением с существующими методами декодирования, прежде всего, по корректирующей способности. Второе направление является логическим продолжением первого и ставит задачу повышения эффективности исследуемого метода декодирования на основе двойственного базиса путем его модернизации.
Методы исследования. Проводимые исследования основываются на теории полей Галуа, теории двойственного базиса поля Галуа, теории кодирования, теории рекуррентных последовательностей и теории вероятностей. Для проведения численных расчетов и построения графиков использовались программные пакеты: Octave, LibreOffice Calc, Maxima, Gnuplot и другие. Программное обеспечение, необходимое для решения поставленных в диссертации задач, написано на языке Pascal в среде разработки Geany с использованием компилятора Free Pascal 2.4. Для написания программных моделей использовалась система численных вычислений Octave и одноименный язык программирования.
Научная новизна. Научная новизна работы состоит в следующем:
-
Исследован новый метод декодирования кодов PC как рекуррентных последовательностей с использованием двойственного базиса.
-
Проведен сравнительный анализ эффективности метода декодирования на основе двойственного базиса и классических методов декодирования кодов PC по выбранным критериям оценки эффективности.
-
Предложен пороговый метод декодирования на основе двойственного базиса, позволяющий значительно улучшить корректирующие способности. Практическая ценность. Исследуемый в работе метод декодирования
циклических кодов на основе двойственного базиса опирается на рекуррентные свойства кодовых комбинаций и обладает расширенными корректирующими возможностями по сравнению с классическими методами декодирования. Проведенное в работе имитационное моделирование позволило более подробно изучить свойства исследуемых методов и зафиксировать результаты, подтверждающие теоретические предположения.
В работе было показано, что декодирование с использованием двойственного базиса поля Галуа способно обеспечивать исправление определенной доли комбинаций с ошибками, кратность которых превышает гарантированно исправляемую кратность, определяемую минимальным кодовым расстоянием. Данное свойство открывает новое направление в теории циклического кодирования, связанное с использованием двойственного базиса в задачах повышения эффективности передачи данных.
Разработан новый пороговый алгоритм декодирования кодов Рида-Соломона на основе двойственного базиса, который показал значительно лучшие результаты по исправляющей способности чем классический алгоритм мажоритарного декодирования эквивалентных кодов Рида-Соломона (РСЭ) на основе двойственного базиса, и результаты не хуже, а в некоторых случаях и лучше, нежели синдромный алгоритм декодирования.
В качестве основного инструмента для проведения экспериментов был использован разработанный автором программный комплекс — "Программируемый калькулятор Галуа", предназначенный для исследования и моделирования помехоустойчивых кодов Рида-Соломона, а также система программных моделей на языке программирования Octave, предназначенная для проведения имитационного моделирования.
Реализация результатов работы. Основные научные результаты работы внедрены в практическую деятельность ЗАО "НПП "ИСТА-Системс", а также используются в учебном процессе Санкт-Петербургского государственного университета телекоммуникаций им. проф. М.А. Бонч-Бруевича, что подтверждено соответствующими актами внедрения.
Апробация работы. Результаты работы обсуждались и были одобрены на пяти международных конференциях и трех научно-технических конференциях профессорско-преподавательского состава СПбГУТ. По результатам диссертации опубликовано две статьи в изданиях из перечня, рекомендованного ВАК, а также принято участие в двух НИР по тематике диссертации. На разработанный программный комплекс "Программируемый сетевой калькулятор Га-луа" получено свидетельство о государственной регистрации программы для ЭВМ.
Методология исследования. В работе используется имитационное моделирование с применением метода Монте-Карло. При проведении эксперимента производится набор статистических данных, по которым далее производится оценка параметров исследуемых алгоритмов декодирования.
Структура и объем работы. Диссертация состоит из введения, 5 глав, заключения. Работа содержит 162 страниц машинописного текста, 66 рисунков, 6 таблиц и список литературы из 68 наименований.
Основные положения, выносимые на защиту:
-
Результаты исследования эффективности декодирования кодов РСЭ на основе двойственного базиса (Метод двойственного базиса, МДБ).
-
Пороговый алгоритм декодирования кодов Рида-Соломона на основе двойственного базиса.
-
Программный комплекс для моделирования и исследования эффективности кодов Рида-Соломона.
Энергетическая эффективность
Сложность реализации алгоритма декодирования (как программная, так и аппаратная) имеет большое значение [19], поскольку сложные методы декодирования могут иметь высокую энергетическую эффективность, но практическое использование данных алгоритмов будет невозможным.
Затраты на реализацию декодирующего усторойства можно оценить, например, по количеству требуемых элементов памяти.
При рассмотрении кодов, декодирование которых требует проведения вычислений в конечных полях Галуа, сложность реализации также может оцениваться в числе операций над конечным полем. Можно рассматривать как все операции вместе, так и различные операции по отдельности.
Необходимо учитывать, что сложность реализации и временные характеристики связаны между собой. Так, например, некоторые алгоритмы могут быть реализованы с использованием распараллеливания вычислений, что может значительно увеличить быстродействие декодирующего устройства. Однако, в этом случае увеличивается сложность реализации декодирующего устройства и, соответственно, затраты на его реализацию.
Также стоит упомянуть тот факт, что алгоритмы декодирования могут иметь различную сложность в случае аппаратной и программной реализаций. Это может происходить, например, по той причине, что операции, выполняющиеся в аппаратной реализации параллепыю, в программной ре-лизации будут выполняться последовательно.
В данной работе в качестве основного критерия сложности реализации выбрано количество операций над конечным полем. Для определения характеристик и поведения сложных процессов и систем широко используется имитационное моделирование [20,21]. В работе Шеннона [20] приводится следующее определение имитационного моделирования.
Имитационное моделирование — есть процесс конструирования модели реальной системы и постановки экспериментов на этой модели с целью либо понять поведение системы, либо оценить (в рамках ограничений, накладываемых некоторым критерием или совокупностью критериев) различные стратегии, обеспечивающие функционирование данной системы.
Данное определение охватывает в частности и моделирование с использованием метода Монте-Карло, подробно рассмотренное в работах многих авторов, в качестве примера которых можно привести Дж. Клейиена [21] и Дж. С. Фишмана [22]. Клейнен [21] определяет метод Монте-Карло в широком смысле как любой способ решения модели, в котором используются случайные или псевдослучайные числа. В данной работе для определения вероятностных характеристик алгоритмов декодирования будет использоваться имитационное моделирование с использованием метода Монте-Карло. Выделим два способа определения вероятностных характеристик кода. Вероятностные характеристики исследуемого алгоритма для конкретного кода, исправляющего ошибки, можно получить путем полного перебора всех возможных ошибочных комбинаций, Такой способ позволяет получить наиболее точные значения вероятностных характеристик. Однако, данный способ требует значительных временных затрат на проведение расчётов и поэтому подходит только для коротких кодов.
Другим способом является создание модели капала передачи данных и накопление статистики по декодированию передаваемых по данному каналу кодовых комбинаций. Этот способ требует значительно меньших временных затрат, но при этом более сложен в реализации, поскольку требуется дополнительно реализовать модель канала передачи данных. Данный способ позволяет получить вероятностные характеристики для различных моделей канала передачи данных. В данной работе используется именно этот вариант. Способ определения вероятностных характеристик методом накопления статистики позволяет определить эти характеристики лишь с некоторой точностью, в зависимости от объёма выборки. Таким образом, данный способ позволяет получить лишь оценочные значения вероятностных характеристик, так называемую частоту или частость события [23,24]. Соответственно, в дальнейшем, когда речь будет идти о вероятностных характеристиках алгоритма, полученных в результате проведения моделирования, будут иметься в виду именно оценочные значения этих характеристик.
Точность полученных оценочных значений зависит от объёма накопленных данных. Далее в разделе 4.1 будет определено, какой объём выборки можно считать достаточным для проводимого в работе имитационного моделирования.
Само моделирование в работе проводилось при помощи ЭВМ с использованием системы компьютерной алгебры Octave и разработанного автором Программируемого калькулятора Галуа. Описание программных моделей и разработанного программного комплекса дано в разделе 5.
«Генератор информационных комбинаций», как следует из названия, служит для того, чтобы создавать случайные информационные комбинации, которые далее будут переданы на вход кодирующего устройства исследуемого помехоустойчивого кода. На схеме данное устройство названо «Кодер». Поскольку кодовые комбинации помехоустойчивого кода представляют из себя данные в цифровом виде, то в случае использования модели аналогового канала передачи данных необходимо использовать «Устройство сопряжения с каналом». «Устройство сопряжения с каналом», установленное на выходе кодирующего устройства, представляет из себя, как правило, модулятор. «Устройство», стоящее на входе декодера, является демодулятором, предназначенным для преобразования аналогового сигнала, передающегося по каналу, в цифровой вид, пригодный для последующего декодирования. В случае же использования моделей цифрового канала передачи, «Устройство сопряжения с каналом» не требуется.
«Канал передачи данных» представляет из себя модель канала передачи данных, в которой на полученную кодовую комбинацию накладывается ошибка, в зависимости от заданных параметров канала. Используемые в работе модели каналов описаны в разделе 1.3.
«Декодер» непосредственно реализует исследуемый алгоритм декодирования. Результаты декодирования передаются в блок, отвечающий за обработку результатов, в котором эти результаты анализируются, сравниваются с исходными кодовыми комбинациями, полученными от «Генератора информационных комбинаций», и накапливаются для последующей статистической обработки.
Эквивалентные коды PC
Алгоритм Берлекэмпа-Мэсси. Открытый в 1968 году Э. Бер-лекэмпом и применённый к линейным кодам в 1969 году Дж. Мэсси [43,47,48], данный алгоритм синтезирует минимальный регистр с линейной обратной связью, порождающий заданную последовательность символов [38]. Рассмотрим вариант алгоритма Берлекэмпа-Мэсси, известный как алгоритм Мэсси [37]. Исходные данные: So, Si,..., Sr_i — синдромы. Начальные условия: а(х) = 1, корректор р(х) = х, счетчик і — О, длина регистра 1 = 0. I Вычисляем различие Д = \ , VjSj-j-i 3=0 Проверяем различие Д: если Д = 0, то переходим к (ж). Модифицируем многочлен локаторов ошибок: anew(x) = а(х) + Ар(х). Проверяем длину регистра: если 21 г, то переходим к (е). д) Исправляем длину регистра и заменяем корректор: I = г — I, р(х) = а(х)/А. Обновляем многочлен локаторов ошибок: а(х) = апеш(х). ж) Обновляем корректор: р(х) = хр(х). Обновляем счетчик: г — г + 1. Если г d, то переходим к (а), иначе останавливаемся. Предположим, что из канала связи получена комбинация рассмотренного ранее кода PC (7,3), представляемая многочленом и(х) = f(x) + е(х) = ех2 + є5ж4, тогда, согласно формуле (2.14) синдромы будут равны: So = є6) 5 1 = є5, 5г = є, 5з = є. Начинаем декодирование по алгоритму Мэсси [37]. г = 1: а(х) = 1, р(х) = х, I — 0. о i=o Vnewix) = о"(ж) + Др(ж) = 1 + є6ж, 2/ = 0 г. J-M-Z = l-0 = 1, р(х) = а(х)/А = 1/е6 = є"6 = є. Сг(ж) = 7пег(,(ж) = 1 + 6Ж, р(ж) — Жр(ж) = EX. г = 2: і Д = 5Z 2-j-i = a0S1 + Sb = є5 + є6є6 = 0. j=o р(ж) — жр(ж) = ех2. г = 3: і Д = 53 J53-J-I = ст052 + «Ті Si = + 6є5 = є2. 3=0 Vnew{x) = г(х) + Ар(х) = 1 + є6ж + 3ж2, 21 = 2 і. — -г — Z = 3 — 1 = 2, р(ж) - (т(ж)/Д = г5 + є4ж. т(ж) = т„еш(ж) = 1 + eGx + 3ж2, р(х) - хр(х) = є5х + 4ж2. г = 4: Д = 53 A-j-i = з + iS2 + o-2Si = є + є6є + є3є5 = 1. 3=0 О-пеш(ж) = О-(ж) + Др(ж) = 1 + Є6Ж + 3Ж2 + 5Ж + 4Ж2 = 1 + ЄХ + 6Ж2, 2Z = 4 = і т(ж) = anew(x) = 1 + єх + є6ж2, р(ж) — жр(ж) = є5ж2 4- є4ж3. і = 5 = d: Стоп. Теперь по ключевому уравнению найдем многочлен значений ошибок: ш(х) = 5(ж)(т(ж) (mod ж5) = 1 + є5ж + 3ж2.
В основе этого алгоритма лежит процедура нахождения наибольшего общего делителя (НОД) двух полиномов. [37] Так, для решения ключевого уравнения, расширенный алгоритм Евклида применяется к многочленам Го(ж) = xd и г_і(ж) = S(x). Если на J -M шаге алгоритма получено решение Tj{x) — a,j(x)xd + bj(x)S(x), такое, что deg[rj(x)} (сі — 1)/2, то ш(ж) = г,-(ж) и а(х) = bj{x). Расширенный алгоритм Евклида вычисления НОД состоит в следующем [37]. а) Вход: r0(.x), п{х), deg[r0(x)] deg[n(ar)]. б) Начальные условия: ао(х) = 1, Ьо(ж) = 0, ai(x) = О, Ь\[х) = 1. в) На шаге j (j 2), применяем длинное деление к многочленам Tj-2{x) и Tj-i{x), rj-2{x) = qj{x)rj-i{x) + rj(x), 0 deg[rj(z)] deg[r i(x)}. г) Вычисляем Oj(a;) = aj-2{x) — qj(x)dj-i(x), bj(x) = bj 2{x) — qj(x)bj-i(x). д) Останавливаем вычисления на итерации last = jiast, когда deg[riast(x)] r/2. е) Выход: НОД(гож, гіж) = Гк(х), где А; наибольшее ненулевое целое такое, ЧТО Гк(х) ф Q К к jiast. Данный алгоритм отличается большей простотой аппаратной реализации по сравнению с алгоритмом Берлекэмпа-Мэсси, но требует больше операций в конечном поле [37]. Важно отметить, что алгоритм Евклида вычисляет а(х) и и(х) одновременно, как а(х) = biast(x) и ш(х) = riast(x). Предположим, что из канала связи получена комбинация, представляемая многочленом и(х) = f{x) + е(х) = єх2 + є5х4, тогда, согласно формуле (2.14) синдромы будут равны: SQ = є6, Si = є5, S2 = є, 5з = є. Начинаем декодирование по алгоритму Евклида [37]. Начальные условия (шаг 1): r0(x) = х5, п(х) = S(x) = 1+е6х+5х 2+ех +ех4, b0(x) = О, bi(x) = 1. Шаг 2: Xй = (1 + є6х + є5х2 + єх3 + єх4)(є6х + Є6) + ЄЬХ3 + X2 + єх + є6, г2{х) = Є5Х3 + X2 + єх + є6, q2(x) = є6ж + є6, Ь2(х) = 0 + {є6х + є6)(1) = є6ж + Є6. ШагЗ: 1 + 6ж + є5ж2 + єж3 + єх4 = (є5ж3 + х2 + ЄХ + 6) (є3ж + є2) + 6ж2 + Ж + 3, Гз(гс) = 6Ж2 + ЄХ + Є3, 9з (ж) = Є3Ж + 2, Ь3(ж) = 1 + (є3х + є2)(є6ж + 6) = є3 + 4ж + Є2Х2. Алгоритм останавливается, так как deg[r3(a;)] — 1 = г/2. Следовательно: a(x) = є3 + 4ж + є2х2 = є3(1 + єж + 6ж2), о; (ж) = є3 + єж + є6ж2 = є3(1 + є5 ж + є3ж2).
Для поиска корней а(х) на множестве лока торов позиций кодовых символов используется метод проб и ошибок, полу чивший название метод Ченя. [37] Для всех ненулевых элементов Z Є GF(q), которые генерируются в порядке 1,є,є2,... проверяется условие a(Z l) = 0. Этот процесс легко реализуется аппаратно. Так, для примера, рассмотренного выше в пунктах 2.2.1.1 и 2.2.1.2, решением ключевого уравнения будут элементы поля є 2 и є-4. О-(ж) = 1 + SX + 6Ж2 = (1 + 2Ж)(1 + 4Ж). Таким образом, ошибки произошли на позициях 7i = 2 и 72 = 4. 2.2.1.4 Вычисление значений ошибок. Для рассматриваемого приме ра значения ошибок будут вычисляться следующим образом: е7 = Z {Z-l)[a\Z-x)\ = Z7(l + e5Z l + e3Z;2)e l тогда е2 = є2(1 + є5є-2 + є3є і)є-1=є, Є4 = 4(1 + Є5Є-4 + eV8) 1 = Є5. Таким образом, е(ж) — ж2 + є5ж4 и декодированное слово равно / = и(х) + е(ж) = 0 Исправлены две ошибки. 2.2.1.5 Оценка сложности реализации синдромного декодера. В программной реализации декодера на первое место выходит количество операций в конечном поле, требуемых для декодирования кодовой комбинации.
Определение формул для оценки максимального числа операций, необходимого для декодирования кодовой комбинации кода PC синдромным методом декодирования при использовании алгоритма Берлекэмпа-Месси достаточно подробно рассмотрено в работах Э. М. Габидуллина и В. Б. Афанасьева.
Полная оценка сверху общего числа операций в поле для синдромного метода на основе алгоритма Берлекэмпа-Месси производится по формуле (2.22) [38]. Лсвдр. = Grit + 9t2, (2.22) где t — кратность гарантийно исправляемой ошибки, рассчитываемая по формуле (2.6). Вопросы сложности аппаратной реализации синдромного декодера кодов PC рассмотрены в работах многих авторов [49-51]. В частности, М. Н. Тай-леб [51] приводит следующие оценки для аппаратной реалицации декодера PC на ПЛИС:
Определение информационных элементов по /с-элемент-ному участку кодовой последовательности кода РСЭ
Возведение в степень также может быть просто реализовано как операция умножения. Блоки отказа от декодирования (6) и определения кратности ошибок (7) легко могут быть реализованы путем проверки значений главных определителей на равенство (или неравенство) нулю, что не вызывает трудностей.
Блок составления многочлена локаторов ошибок (8) формирует многочлен Ф(ж) в зависимости от найденной в блоке 7 кратности ошибки 8. Эта операция легко реализуется путем записи в ячейки памяти регистра значений главного As и частных А$к определителей, входящих в выражение многочлена локаторов ошибок Ф(ж). Блок вычисления локаторов ошибок (9) реализует процедуру Ченя, в результате выполнения которой находятся корни многочлена Ф(ж), являющиеся как раз локаторами ошибок. Как было показано выше, при кратности ошибок 5 t многочлен Ф(ж) имеет вид
Суть процедуры Ченя сводится не к явному решению уравнения Ф(єг) = 0, а к последовательной подстановке элементов поля г-7 в многочлен Ф(ж) вместо переменной х и запоминания тех элементов поля, для которых выполняется равенство Ф(е ) = 0,modP(x). Элементы поля, для которых выполняется вышеуказанное равенство, и являются локаторами ошибок. Функциональная схема вычисления локаторов ошибок [52] имеет вид, показанный на рисунке 2.10.
На рисунке 2.10 Rk обозначает регистр, реализующий умножение на Fk на каждом такте, где F — сопровождающая матрица. В исходном состоянии на входы регистров подаются коэффициенты многочлена Ф(ж), представляющие собой значения соответствующих главного As или частных А$к определителей. Блок составления многочлена ошибок (10) функционально реализуется с помощью элементов памяти для миноров, схем умножения элементов поля и сумматора. Функциональная схема блока при кратности ошибок 5 показана на рисунке 2.11. Блок вычисления значений ошибок (11) реализует процедуру деления элементов поля GF(27): 4 us(xb) в числителе дроби находится главный определитель А$ для кратности исправляемой ошибки S, а в знаменателе — значение многочлена ошибок, ко Д«
Функциональная схема вычисления локаторов ошибок (процедура Чспя) торос сформировано на выходе блока 10 при подстановке вместо переменной х локатора ошибки. Процедура деления в поле GF(27) может быть функционально реализована как умножение на элемент поля, обратный элементу, стоящему в знаменателе. Например, необходимо разделить элемент є1 на элемент є3. Можно операцию деления записать как где т = (г — j)mod 127 (для рассматриваемого варианта кода).
Функционально это можно реализовать по схеме, представленной на рисунке 2.12, которая отличается от схемы на рисунке 2.9 лишь наличием схемы обращения элемента.
Все операции обращения, логарифмирования и антилогарифмирования выполняются с помощью таблиц, находящихся в памяти устройства. Операция сложения двух чисел г и (—j) по mod 127 не вызывает затруднений.
Блок исправления ошибок (12) представляет собой обычный сумматор по mod 2, на один вход которого подается элемент кодовой комбинации с выхода буферного накопителя 1, а на второй — значение ошибки Yi+k с выхода блока 11.
Коды Рида-Соломона представляют из себя недвоичные циклические коды Боуза-Чоудхури-Хоквингема, символы которых представляют из себя элементы поля Галуа GF(2m). Также выделяют эквивалентные (или дуальные) (п,к) коды Рида-Соломоиа, среди которых отдельно выделяют коды РСЭ с сопряжёнными корнями, образующий полином которых равен одному из минимальных многочленов над полем либо равен произведению нескольких таких многочленов.
В диссертационной работе получено распределение весов для кодов РСЭ с иесопряжёнными и сопряжёнными корянми. При этом, результаты, полученные путём математического расчёта, были подтверждены экспериментально. Определено, что коды РСЭ с сопряжёнными корнями образующего полипома имеют .меньшее минимальное кодовое расстояние, нежели коды с иесопряжёнными корнями, в связи с чем коды РСЭ с сопряжёнными корнями имеют меньшую кратность гарантированно исправляемых ошибок.
Кодирующие устройства кодов Рида-СоломоЕіа строятся по принципам систематического или несистематического кодирования. В случае систематического кодирования кода РСЭ информационными элементами кода (п,к) будут начальные к элементов кодовой последовательности {s}. В основе несистематического кодирования кодов РСЭ лежит тот факт, что кодовые комбинации кода РСЭ являются возвратными последовательностями, произвольный элемент которых может быть выражен через корни образующего многочлена кода и информационные элементы.
В главе рассмотрен один из самых распространённых на сегодня алгоритмов декодирования кодов PC — алгебраический (или синдромный) алгоритм декодирования, основанный на нахождении синдромов и решении ключевого уравнения. Среди алгоритмов решения ключевого уравнения выделяют три равнозначных по исправляющей способности алгоритма: алгоритм Берлекэмпа-Месси, частным случаем которого является определительный метод декодирования, алгоритм Евклида и алгоритм Питерсона-Горен-штейна-Цирлера.
Алгоритмы Берлекэмпа-Месси и Евклида подробно рассмотрены в данной главе. Поскольку известно, что они идентичны по своей исправляющей способности, было решено использовать при моделировании и сравнении исследуемого в работе алгоритма на основе двойственного базиса алгоритм син-дромного декодирования на основе алгоритма решения ключевого уравнения Берлекэмпа-Месси. 3 Декодирование кодов PC с использованием двойственного базиса
Определение необходимого для проведения экспериментов объёма выборки
Как можно видеть из алгоритма и приведенной блок-схемы, декодирование принятой кодовой комбинации может завершиться еще до окончания ее приема.
Далее, на рисунке 3.9, приведем блок-схему декодирующего устройства, реализующего вышеприведенный алгоритм. Устройство состоит из сдви 77 гового циклического регистра на п ячеек, в который по мере получения записываются символы принимаемой кодовой комбинации; блока, осуществляющего расчет информационных элементов А\, А ..., А), по формуле (3.3); блока накопления статистики и принятия решения, в котором хранятся результаты вычислений и осуществляется принятие решения о результате декодирования; также этот блок управляет ключевой схемой, расположенной на входе декодирующего устройства; ключевая схема блокирует вход сдвигового регистра на время обработки последних к — 1 -элементных комбинаций либо при досрочном декодировании кодовой комбинации до начала получения следующей кодовой комбинации.
Далее перейдём к рассмотрению того, как изменятся алгоритм и устройство декодирования кода РСЭ для случая использования децимаций.
Основным отличием станет добавление блока децимирования принятой комбинации, который будет либо сохранять децимировапную комбинацию для дальнейшей обработки, либо передавать ее по мере перемешивания в соответствующие ветки устройства, которые параллельно будут обрабатывать все децимированные комбинации для увеличения скорости декодирования. Соответственно, в первом случае изменится часть устройства декодирования, отвечающая за вычисление информационных элементов, она должна будет корректировать результат вычислений согласно индексу децимации. Во втором случае, в устройстве добавятся параллельные ветки для обработки децимированных комбинаций, состоящие из регистра памяти и блока вычислений каждая. В первом варианте устройство усложнится незначительно, но декодирование будет занимать больше времени и досрочное декодирование станет невозможным. Второй вариант позволит сохранить время декодирования на том же уровне при усложнении конструкции. На рисунке 3.10 приведена блок-схема устройства декодирования для первого варианта.
Блок децимирования и хранения декодера, изображенного на схеме 3.10, по мере получения символов кодовой комбинации формирует децимированные комбинации и записывает их в память. После обработки пришедшей кодовой комбинации, в том случае, если определить информационные элементы не представляется возможным, блок децимирования и хранения блокирует прием (либо продолжает принимать последующие кодовые комбинации, записывая их в память) и начинает по очереди передавать на сдвиговый регистр децимированные комбинации. Таким образом, декодирование кодовой комбинации может как закончиться досрочно по накоплению _J +1 одинаковых результатов, так и продлиться до конца обработки децимиро-ванных комбинаций. В последнем случае время декодирования комбинации может превышать время приема кодовой комбинации.
Данную схему построения декодера можно применять в хороших каналах, где вероятность появления ошибок, требующих применения децимаций, мала.
При использовании декодера, изображенного па схеме 3.11, блок приема пересылает полученные символы кодовой комбинации в блоки распределения элементов, каждый из которых соответствует определенному индексу децимации. Блок распределения записывает полученные элементы в ячейки запоминающего регистра, соответственно своему индексу децимации. По мере появления в запоминающих регистрах fc-элемептпых последовательностей, блоки расчета информационных ЗЛЄМЄЕІТОВ считывают их, производят расчет и пересылают результат в блок накопления статистики. Условие завершения декодирования то же, что и в первом случае, но данный декодер позволяет получить решение еще до приема всей кодовой комбинации, что достигается за счет распараллеливания процессов обработки децимированных комбинаций.
Данная схема декодера заметно сложнее в реализации поскольку требует в разы больше элементов (регистров памяти, сумматоров и умножителей) для построения. Такая схема может применяться в каналах с высокой вероятностью появления ошибок, когда известно, что большинство принятых комбинаций потребуют обработку при помощи децимаций.
Первоначально рассмотрим само понятие стирания. Стирание представляет из себя символ принятой кодовой комбинации, значение которого невозможно определить точно. В случае двоичных сигналов, это обозначает невозможность определить принят сигнал, обозначающий единицу, или сигнал обозначающий ноль. Для рассматриваемых в данной работе кодов РСЭ, стирание одного двоичного сигнала приводит к стиранию всего элемента кодовой комбинации, состоящего из m двоичных сигналов, где т — степень поля Галуа GF(2m), на основе которого построен код.
При исправлении стираний можно использовать различные способы декодирования.
Один из способов заключается в том, чтобы подставить вместо стёртого символа все возможные его значения, декодировать все получившиеся варианты комбинации, а затем провести сравЕїение полученных результатов. Данный способ имеет ряд очевидных недостатков, основным из которых является необходимость проводить дополнительные операции декодирования, количество которых увеличивается с увеличением количества стираний.
При использовании мажоритарного алгоритма МДБ можно исключить стёртые символы из процесса декодирования, и отказаться от обработки fc-элементных комбинаций, содержащих стёртые символы. В этом случае уменьшается количество требуемых расчётов, однако возникает следующая проблема. При определённом количестве стираний они могут расположиться таким образом, что невозможно будет выделить ни одного fc-элемеитного участка. Например для кода (7,3) это может выглядеть следующим образом: {s0Xs2SzXs5X}, здесь символом X обозначены стёртые позиции. Видно, что в первом примере остаётся всего один возможный fc-эле-ментный участок, во втором примере таких участков уже пет. В этом случае возможно использование децимаций. Рассмотрим применение децимаций при исправлении стираний. Для примера возьмём вторую последовательность с тремя стираниями из приведённого выше примера. Получившиеся децимироваппые последовательности сведём в таблицу 3.5.
Как можно видеть из таблицы 3.5, после проведения первой децимации (q = 2), мы получаем два fc-элементных участка, которые позволят восстановить всю кодовую последовательность.
