- •Глава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.3. Двоичные коды бчх
Коды БЧХ это двоичные коды, конструкция которых определяется заданием их нулей, т.е. корней порождающего их многочлена:
БЧХ код с кодовым расстоянием dmin ≥2td+1 является циклическим кодом, порождающий многочлен g(x) которого имеет 2td последовательных корней в точках a b, a b+1,… , a b+ δ , где δ = 2td -1.
Таким образом, порождающий многочлен двоичного (n, k, dmin) кода БЧХ имеет вид
а длина и размерность кода равны, соответственно,
Двоичный БЧХ код, заданный таким образом, имеет конструктивное кодовое расстояние равное 2td + 1. Однако, следует заметить, что истинное кодовое расстояние может быть больше конструктивного.
Пример 31. Над полем GF(23), порождаемым примитивным многочленом р(х) = х3 + х + 1, для параметров td = 1 и b = 1 многочлен
порождает двоичный (7,4,3) код БЧХ. На самом деле, это двоичный циклический код Хемминга! Заметим, что вес Хемминга этого порождающего многочлена равен 3 и, следовательно (в данном случае, но не всегда), конструктивное и истинное расстояние кода совпадают.
Пример 32. Рассмотрим поле GF(24) , порождаемое примитивным многочленом, и параметры td = 2,b=1. Тогда многочлен
порождает двоичный (15,7,5) код БЧХ, исправляющий две ошибки.
Пример 33. В поле GF(24) , порождаемом примитивным многочленом р(х) = х4 + х + 1, и параметры td = 3,b= 1, многочлен
порождает двоичный (15,5,7) код БЧХ, исправляющий три ошибки.
Рассмотрим нижнюю границу минимального расстояния кодов БЧХ известную как граница БЧХ. Это полезно не только тем, что позволяет оценить корректирующие способности кода в общем случае, но и тем, что выделяет особые свойства кодов БЧХ. Напомним, что элементы a b, a b+1, , a b+ δ , где δ = 2td-1, являются корнями порождающего многочлена g(x) и что все кодовые слова v кода БЧХ, ассоциированные с полиномами v(x), кратны порождающему многочлену кода. Следовательно
(3.11)
Таким образом, на основании (3.11), все кодовые слова удовлетворяют следующей системе 2td уравнений (в матричной форме)
(3.12)
Соответственно, проверочная матрица двоичного БЧХ кода имеет вид
(3.13)
Эта проверочная матрица обладает следующим свойством: любая ее 2td * 2td подматрица, т.е. образованная любыми 2td столбцами, является матрицей Вандермонда. Следовательно, любые 2td столбцов проверочной матрицы линейно независимы. Отсюда следует, что минимальное кодовое расстояние этого кода удовлетворяет неравенству d > 2td + 1. Этот результат можно интерпретировать следующим образом:
Граница БЧХ. Если порождающий многочлен g(x) циклического (n,k,d) кода имеет z последовательных корней, например, ab,ab+1, ...,ab+z,тo d≥2z+ l.
3.4. Полиномиальные коды
Класс циклических полиномиальных кодов включает циклические коды Рида-Маллера, коды БЧХ и Рида-Соломона, коды над конечными геометриями. Задание полиномиальных кодов связано с наложением условий на их корни (нули) следующим образом.
Пусть а примитивный элемент поля GF(2ms). Пусть s положительное целое число и b делитель 2s — 1. Тогда ah является корнем порождающего полинома g(x) полиномиального кода порядка µ, если и только если b делит h и
где для любого целого i,
функция Wa(s) определена как (a(s) = 2s) - иначе вес целого числа i, т.е.
Согласно этому определению коды БЧХ и Рида-Соломона являются полиномиальными с параметрами b = т = 1. Коды Рида-Маллера является подкодами полиномиальных кодов с параметром s=1. Коды над конечными геометриями возникают как дуальные к полиномиальным кодам. Ниже даются свойства нулей конечно-геометрических кодов.
Евклидово геометрические (ЕГ) коды
Пусть а примитивный элемент поля GF(2ms). Пусть h неотрицательное целое меньше 2тs-1. Тогда аh является корнем порождающего многочлена g(x) ЕГ кода порядка (µ,s), длины 2ms-1, если и только если
Для s = 1 ЕГ коды совпадают с циклическими РМ*m,µ , кодами и, следовательно, ЕГ коды можно рассматривать как обобщенные коды РМ (Рида-Маллера).
Проективно геометрические (ПГ) коды
Пусть а примитивный элемент поля GF(2(m+1)s). Пусть h неотрицательное целое меньше 2(m+1)s - 1. Тогда ah является корнем порождающего многочлена g(x) ПГ кода порядка (µ,s), длины (2тs — 1)/(2s - 1), если и только если h делится на 2s - 1 и