- •Глава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. Распределение весов
- •Глоссарий
- •Литература
Часть 4 недвоичные бчх коды -коды рида-соломона
В этой главе вводятся наиболее известные кодовые конструкции и объясняются алгоритмы их кодирования и декодирования. Коды Рида-Соломона (PC) нашли множество применений в системах цифровой памяти и связи. В качестве примеров упомянем знаменитый (255,223,33) код в системах космической связи НАСА (NASA), укороченные коды PC над GF(28) в системах цифровой записи «компакт-диск» CD-ROM и DVD, а также в наземных цифровых системах HDTV (цифрового ТВ), расширенные (128,122,7) коды PC над GF(27) для модемов на кабельных линиях, среди многих и многих других.
4.1. Коды pc как полиномиальные коды
Аналогично кодам Рида-Маллера коды PC можно определить как множество кодовых слов, компоненты которых равны значениям некоторых определенных многочленов. В действительности, это определение PC кодов принадлежит Риду и Соломону [RS]. Коды Рида-Маллера, конечно-геометрические коды [LC] и коды PC являются членами большого класса Полиномиальных кодов [PW] и тесно связаны с классом алгебро-геометрических (AG) кодов [Pre]. Обозначим
(4.1)
информационный полином с коэффициентами ui GF(2m), 10 < i < к. Очевидно, что всего имеется 2тk таких многочленов. Вычисляя значения многочлена (4.1) для ненулевых элементов поля GF(2m), получаем кодовое слово v кода PC с параметрами (2m-l, к, d)
(4.2)
4.2. От двоичных кодов бчх к pc кодам
Коды PC можно также интерпретировать как недвоичные коды БЧХ. Можно сказать, что PC коды являются кодами БЧХ, значения кодовых символов которых взяты из поля GF(2m). В частности, нулями PC кода, исправляющего td ошибок, являются 2td последовательных степеней примитивного элемента поля Галуа. Более того, так как над полем GF(2m) минимальные многочлены имеют вид фi(х) = (х - аi), 0 < i < 2т - 1, (см. уравнение (3.9)) все делители порождающего код многочлена являются линейными (т.е. имеют степень 1) и
(4.3)
где b целое число, обычно 0 или 1.
Из (4.3) и границы БЧХ следует, что минимальное кодовое расстояние (n,k,d) PC кода над GF(2m) удовлетворяет неравенству d ≥ n-k +1.Из границы Синглтона [Sin], утверждающей, что d ≤ п- к + 1, следует, что d = п — к+l. Коды, удовлетворяющие последнему равенству, называют МДР кодами (кодами с максимальным достижимым расстоянием) [Sin]. Таким образом, PC код является МДР кодом. Из этого следуют полезные свойства кодов PC. Одно из них состоит в том, что укороченные коды PC являются МДР кодами.
Изоморфизм между GF(2m) и {0,1}m означает, что любому двоичному т - вектору хβ может быть поставлен в соответствие элемент β GF(2m),
Другими словами, т информационных бит можно сгруппировать в блок, образующий символ GF(2m). Если элементы GF(2m) рассматривать как векторы из т бит, то из кода PC получаем двоичный линейный код длины п = т(2т — 1) и размерности k = т(2т — 1 - 2td). Минимальное расстояние такого кода не меньше 2td. Такое двоичное отображение кода PC позволяет исправлять не только до td случайных (двоичных) ошибок, но и многократные случайные пакеты ошибок. Например, может быть исправлен любой однократный пакет ошибок длиной до m(td - 1) + 1 бит. Это следует из того, что пакет ошибок длины m(q — 1) + 1 или меньше покрывается не более q символами GF(2m). Таким образом, коды PC способны исправлять многие комбинации случайных ошибок и пакетов ошибок. В этом основная причина огромной популярности кодов PC в практических системах.
Пример 40. Пусть т=3 и поле GF(23) генерируется примитивным элементом α, удовлетворяющим условию р(α) = α 3 + а + 1 = 0. Пусть b = 0 и td = 2. Тогда имеется (7,3,5) код PC с порождающим полиномом
Отображением символов GF(23) в вектора длины 3 получаем двоичный (21,9,5) код. способный исправлять до двух случайных ошибок и любой пакет до 4-х ошибок.