- •Глава3 4
- •Часть 1 введение 4
- •Часть 2 коды хемминга, голея и рида-маллера 39
- •Часть 3 двоичные циклические коды и коды бчх 54
- •Часть 4 недвоичные бчх коды -коды рида-соломона 105
- •Глава3 часть 1 введение
- •1.1. Кодирование для исправления ошибок: Основные положения
- •1.1.1. Блоковые и сверточные коды
- •1.1.2. Хеммингово расстояние, Хемминговы сферы и корректирующая способность
- •1.2. Линейные блоковые коды
- •1.2.1. Порождающая и проверочная матрицы
- •1.2.2. Вес как расстояние
- •1.3. Кодирование и декодирование линейных блоковых кодов
- •1.3.1. Кодирование с помощью матриц g и н
- •1.3.2. Декодирование по стандартной таблице
- •1.3.3. Хемминговы сферы, области декодирования и стандартная таблица
- •1.4. Распределение весов и вероятность ошибки
- •1.4.1. Распределение весов и вероятность необнаруженной ошибки в дск.
- •1.4.2. Границы вероятности ошибки в дск, каналах с абгш и с замираниями
- •1.5 Общая структура жесткого декодера для линейных кодов
- •Часть 2 коды хемминга, голея и рида-маллера
- •2.1. Коды Хемминга
- •2.1.1. Процедуры кодирования и декодирования
- •2.2. Двоичный код Голея
- •2.2.1 Кодирование
- •2.2.2. Декодирование
- •2.2.3. Арифметическое декодирование расширенного (24,12,8) кода Голея.
- •2.3. Двоичные коды Рида-Маллера
- •2.3.1. Булевы полиномы и рм коды
- •2.3.2. Конечные геометрии и мажоритарное декодирование.
- •Часть 3 двоичные циклические коды и коды бчх
- •3.1. Двоичные циклические коды.
- •3.1.1. Порождающий и проверочный полиномы.
- •3.1.2. Порождающий многочлен
- •3.1.3. Кодирование и декодирование двоичных циклических кодов.
- •3.1.4. Проверочный полином.
- •3.1.5. Укороченные циклические коды и crc коды
- •3.2. Общий алгоритм декодирования циклических кодов
- •3.1.5 Пакеты ошибок
- •3.2.1. Арифметика gf(q)
- •3.3. Двоичные коды бчх
- •3.4. Полиномиальные коды
- •3.5. Декодирование двоичных бчх кодов
- •2. Евклидов алгоритм (еа)
- •3.5.1. Общий метод декодирования для бчх кодов
- •3.5.2. Алгоритм Берлекемпа-Мэсси (вма)
- •3.5.3. Декодер pgz
- •3.5.4. Евклидов алгоритм (еа)
- •3.5.5. Метод Ченя и исправление ошибок
- •3.5.6. Исправление стираний и ошибок
- •3.6. Распределение весов и границы вероятности ошибки
- •3.6.1. Оценка вероятности ошибки
- •Часть 4 недвоичные бчх коды -коды рида-соломона
- •4.1. Коды pc как полиномиальные коды
- •4.2. От двоичных кодов бчх к pc кодам
- •4.3. Декодирование кодов pc
- •4.3.1. Комментарий к алгоритмам декодирования
- •4.3.2. Исправление ошибок и стираний
- •4.4. Распределение весов
- •Глоссарий
- •Литература
3.5.5. Метод Ченя и исправление ошибок
Для поиска корней σ(х) на множестве локаторов позиций кодовых символов используется метод проб и ошибок, получивший название метод Ченя. Для всех ненулевых элементов β GF(2m), которые генерируются в порядке 1, a, а2,... a14 проверяется условие σ(β-1) =0. Этот процесс легко реализуется аппаратно. На самом деле, поиск корней (факторизация) многочленов над GF(2m) является увлекательной математической задачей, которая еще ждет своего решения.
Для двоичных кодов БЧХ исправление ошибок на позициях j1, ..., jv, соответствующих найденным корням, сводится к инвертированию символов, принятых на этих позициях, т.е.
после чего, выдается восстановленное кодовое слово v(x).
Пример 37. Продолжая Пример 34, находим, что корни многочлена локаторов ошибок равны: 1, а9 = а-6 и а3 = а-12. Другими словами, получено следующее разложение многочлена на множители
Соответственно, восстановленный многочлен ошибок равен и
Три ошибки исправлены.
3.5.6. Исправление стираний и ошибок
Существует много ситуаций, когда решение о принятом символе не может считаться надежным. Рассмотрим, например, передачу двоичных символов по каналу с АБГШ с двоичной фазовой манипуляцией, т.е. с отображением 0→+1 и 1→ -1. Если значение принятого сигнала слишком близко к нулю, то возможно, более разумно, с точки зрения минимизации вероятности ошибки декодирования, отказаться от решения о принятом символе. В таких случаях принятый символ «стирается», а такое решение называют стиранием. Подобные стирания представляют собой простейшую форму мягкого решения.
Введение стираний, по сравнению с исправлением только ошибок, обладает тем преимуществом, что декодеру известны позиции с ненадежными символами. Пусть d минимальное кодовое расстояние, v число ошибок и µ число стираний в принятом слове. Тогда минимальное Хеммингово расстояние по нестертым позициям снижается, по меньшей мере, до величины d-µ. Следовательно, корректирующая способность равна [(d — µ — 1 )/2] и справедливо следующее соотношение
(3.26)
Последнее неравенство, на уровне интуиции, означает, что исправление ошибок требует вдвое больше усилий (и избыточности), чем исправление стираний, поскольку позиции стираний известны.
Для двоичных линейных кодов, включая коды БЧХ, стирания и ошибки могут быть исправлены следующим ниже методом.
Записать нули на стертые позиции и декодировать полученное слово в кодовое слово обозначенное v0(x).
Записать единицы на стертые позиции и декодировать в кодовое слово v1(x).
Выбрать из v0(x) и v1(x) в качестве результата декодирования кодовое слово, ближайшее к принятому слову по нестертым позициям. Иначе говоря, в качестве результата декодирования выбирается слово, потребовавшее наименьшего числа исправлений.
Таким образом, любая допустимая по условию (3.26) комбинация стираний и ошибок исправляется за две попытки исправления ошибок.
Пример 38. Рассмотрим циклический (7,4,3) код Хемминга с порождающим многочленом g(x) = 1 + х + х3 и конечное поле GF(23) с примитивным элементом а, удовлетворяющим условию р(а) = 1 + а + а3. Предположим, что передано слово v(x) = х + х2 + х4 и что приемник ввел два стирания. Так как d = 3 >µ, то эти стирания могут быть исправлены. Пусть r(x) =f+ х + х2 + fx3 + х4 полином, ассоциированный с принятым словом, где через f обозначены стирания.
Первая попытка: декодируем принятое слово при f = 0, r0(x) = х + х2 + х4. Синдромы для него равны: S1 = r0(α) =0 и S2 = (S1)2 = 0 Следовательно, v0(x) - r0(х) = х + х2 + х4.
Вторая попытка: теперь декодируем при f=1, r1(х) = 1 + х + х2 + х3 + х4, S1 = а и S2 = а2. Уравнение (3.16) имеет в этом случае вид: аσ1 = а2. В результате получаем σ(х) = 1 + ах, е(х) = х и кодовое слово v1(x) = r1(x) + е(х) = 1 + х2 + х3 + х4, которое отличается от принятого слова r(х) в одной нестертой позиции. В качестве результата декодирования выбираем слово v0(x). Таким образом, исправлены два стирания.
Следует напомнить, что для исправления только стираний линейным кодом (при точном отсутствии ошибок) достаточно найти решение системы линейных уравнений rНт=0. Решение этой системы единственно, если число стираний меньше кодового расстояния. Кроме того, этим методом можно исправить многие из комбинаций с числом стираний больше кодового расстояния (но не более числа проверок), хотя решение может быть не всегда единственным.