Коды Боуза-Чоудхури-Хоквингема

РЕФЕРАТ По курсу «Теория информации и кодирования»

на тему:

" КОДЫ БОУЗА-ЧОУДХУРИ-ХОКВИНГЕМА"

БЧХ коды

Коды Боуза-Чоудхури-Хоквингема (БЧХ) — класс циклических кодов, исправляющих кратные ошибки, т. е. две и более (d₀ 5).

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

Методика построения кодов БЧХ отличается от обычных циклических, в основном, выбором определяющего полинома P (х). Коды БЧХ строятся по заданной длине кодового слова n и числа исправляемых ошибок S, при этом количество информационных разрядов k не известно пока не выбран определяющий полином.

Рассмотрим процедуру кодирования с использованием кода БЧХ на конкретных примерах.

Пример Построить 15-разрядный код БЧХ, исправляющий две ошибки в кодовой комбинации (т. е. n = 15, S = 2).

Решение:

1. Определим количество контрольных m и информационных разрядов k

m h S .

Определим параметр h из формулы

n = 2^h-1, h = log₂(n+1) = log₂16 = 4,

при этом: m h S = 42 = 8; k = n-m = 15−8 = 7.

Таким образом, получили (15, 7)-код.

2. Определим параметры образующего полинома:

— количество минимальных многочленов, входящих в образующий

L = S = 2;

— порядок старшего (все минимальные — нечетные) минимального многочлена = 2S-1 = 3;

— степень образующего многочлена = m 8.

3. Выбор образующего многочлена.

Из таблицы для минимальных многочленов для кодов БЧХ (см. приложение 4) из колонки 4 (т. к. l = h = 4) выбираем два минимальных многочлена 1 и 3 (т. к. = 3):

M₁(x) = 10 011;

M₂(x) = 11 111.

При этом

P (x) =M₁(x)M₂(x)=1 001 111 111=111010001= x⁸+ x⁷+ x⁶+ x⁴+1.

4. Строим образующую матрицу. Записываем первую строку образующей матрицы, которая состоит из образующего полинома с предшествующими нулями, при этом общая длина кодовой комбинации равна n = 15. Остальные строки матрицы получаем в результате k-кратного циклического сдвига справа налево первой строки матрицы.

Строки образующей матрицы представляют собой 7 кодовых комбинаций кода БЧХ, а остальные могут быть получены путем суммирования по модулю 2 всевозможных сочетаний строк матрицы.

Процедура декодирования, обнаружения и исправления ошибок в принятой кодовой комбинации такая же, как и для циклических кодов с d₀ < 5

Пример Построить 31-разрядный код БЧХ, исправляющий три ошибки в кодовой комбинации (т. е. n = 31, S = 3).

Решение:

1. Определим количество контрольных разрядов m и информационных разрядов k.

m h S.

Определим параметр h из формулы

n = 2^h-1,h = log₂(n+1) = log₂32 = 5,

при этом: m h S = 53 = 15; k = n-m = 31−15 = 16.

Таким образом, получили (31, 16)-код.

2.Определим параметры образующего полинома:

— количество минимальных многочленов, входящих в образующий

L = S = 3;

порядок старшего минимального многочлена

= 3S-1 = 5;

степень образующего многочлена

= m 15.

Выбор образующего многочлена.

Из таблицы для минимальных многочленов для кодов БЧХ (приложение 4) из колонки 5 (т. к. l = h = 5) выбираем три минимальных многочлена 1, 3 и 5 (т. к. = 5):

M₁(x) =100 101;

M₂(x) =111 101;

M₃(x) =110 111.

При этом

P (x) = M₁(x) M₂(x) M₃(x) =1 000 111 110 101 111=

= x¹⁵+ x¹¹ +x¹⁰+ x⁹+ x⁸+ x⁷+ x⁵+ x³ + x²+x+ 1.

4. Строим образующую матрицу. Записываем первую строку образующей матрицы, которая состоит из образующего полинома с предшествующими нулями, при этом общая длина кодовой комбинации равна n = 31. Остальные строки матрицы получаем в результате k-кратного циклического сдвига справа налево первой строки матрицы.

G (31,16)=1 000 111 110 111 110

.. .

Строки образующей матрицы представляют собой 16 кодовых комбинации кода БЧХ, а остальные могут быть получены путем суммирования по модулю 2 всевозможных сочетаний строк матрицы.

Декодирование кодов БЧХ

Коды БЧХ представляют собой циклические коды и, следовательно, к ним применимы любые методы декодирования циклических кодов. Открытие кодов БЧХ привело к необходимости поиска новых алгоритмов и методов реализации кодеров и декодеров. Получены существенно лучшие алгоритмы, специально разработанные для кодов БЧХ. Это алгоритмы Питерсона, Бэрлекэмпа и др.

Рассмотрим алгоритм ПГЦ (Питерсона-Горенстейна-Цирлера). Пусть БЧХ код над полем GF (q) длины n и с конструктивным расстоянием d задается порождающим полиномом g (x), который имеет среди своих корней элементы, — целое число (например 0 или 1). Тогда каждое кодовое слово обладает тем свойством, что. Принятое слово r (x) можно записать как r (x) = c (x) + e (x), где e (x) — полином ошибок. Пусть произошло ошибок на позициях (t максимальное число исправляемых ошибок), значит, а — величины ошибок.

Можно составить j-ый синдром Sj принятого слова r (x):

.

Задача состоит в нахождений числа ошибок u, их позиций и их значений при известных синдромах Sj.

Предположим, для начала, что u в точности равно t. Запишем (1) в виде системы нелинейных уравнений в явном виде:

Обозначим через локатор k-ой ошибки, а через величину ошибки,. При этом все Xk различны, так как порядок элемента? равен n, и поэтому при известном Xk можно определить ik как ik = log? Xk.

Составим полином локаторов ошибок:

Корнями этого полинома являются элементы, обратные локаторам ошибок. Помножим обе части этого полинома на. Полученное равенство будет справедливо для

:

Положим и подставим в (3). Получится равенство, справедливое для каждого и при всех :

Таким образом для каждого l можно записать свое равенство. Если их просуммировать по l, то получиться равенство, справедливое для каждого

:

.

Учитывая (2) и то, что

(то есть меняется в тех же пределах, что и ранее) получаем систему линейных уравнений:

.

Или в матричной форме

Где Если число ошибок и в самом деле равно t, то система (4) разрешима, и можно найти значения коэффициентов. Если же число u < t, то определитель матрицы S (t) системы (4) будет равен 0. Это есть признак того, что количество ошибок меньше t. Поэтому необходимо составить систему (4), предполагая число ошибок равным t? 1. Высчитать определитель новой матрицы S (t? 1) и т. д., до тех пор, пока не установим истинное число ошибок.

После этого можно решить систему (4) и получить коэффициенты полинома локаторов ошибок. Его корни (элементы, обратные локаторам ошибок) можно найти простым перебором по всем элементам поля GF (qm). К ним найти элементы, обратные по умножению, — это локаторы ошибок. По локаторам можно найти позиции ошибок (ik = log? Xk), а значения Yk ошибок из системы (2), приняв t = u. Декодирование завершено.

Коды Рида-Соломона

Широко используемым подмножеством кодов БЧХ являются коды Рида-Соломона, которые позволяют исправлять пакеты ошибок. Пакет ошибок длины b представляет собой последовательность из таких b ошибочных символов, что первый и последний из них отличны от нуля. Существуют классы кодов Рида-Соломона, позволяющие исправлять многократные пакеты ошибок.

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

Обычно 1 кадр (кодовое слово) = 32 символа данных +24 сигнальных символа +8 контрольных бит = 256 бит.

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

При передаче данных производится перемежение (изменение порядка следования по длине носителя и во времени) блоков с различным сдвигом во времени, в результате чего расчленяются сдвоенные ошибки, что облегчает их локализацию и коррекцию. При этом используются коды Рида-Соломона с минимальным кодовым расстоянием d₀ = 5.

Сверточные коды

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

Выводы

Таким образом, в результате написания реферата, пришли к выводу, что коды Боуза-Чоудхури-Хоквингхема — это широкий класс циклических кодов, способных исправлять многократные ошибки.

БЧХ-коды играют заметную роль в теории и практике кодирования. Интерес к ним определяется следующим: коды БЧХ имеют весьма хорошие свойства; данные коды имеют относительно простые методы кодирования и декодирования; коды Рида-Соломона являются широко известным подклассом недвоичных БЧХ кодов, которые обладают оптимальными свойствами, и применяются для исправления многократных пакетов ошибок.

1. Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and practice of error control codes. — М.: Мир, 1986. — С. 576

2. Дмитриев В. И. Прикладная теория информации: Учебник для вузов. М.: Высшая школа, 1989. 320 c.

3. Колесник В. Д., Полтырев Г. Ш. Курс теории информации. — М.: Наука, 1982.

4. Кудряшов Б. Д. Теория информации. Учебник для вузов Изд-во ПИТЕР, 2008. — 320с.

5. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. — С. 596.

6. Семенюк В. В. Экономное кодирование дискретной информации. — СПб.: СПб ГИТМО (ТУ), 2001

7. У. Петерсон, Э. Уэлдон, Коды, исправляющие ошибки, Москва, «Мир», 1976.

8. Э. Берлекэмп, Алгебраическая теория кодирования, Москва, «Мир», 1971.