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

9509

знаков

таблиц

изображения

РЕФЕРАТ

По курсу “Теория информации и кодирования”

на тему:

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

БЧХ коды

Коды Боуза-Чоудхури-Хоквингема (БЧХ) – класс циклических кодов, исправляющих кратные ошибки, т. е. две и более (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 = 4×2 = 8; k = n-m = 15-8 = 7.

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

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

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

L = S = 2;

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

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

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

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

M₁(x) = 10011;

M₂(x) = 11111.

При этом

P(x) =M₁(x)×M₂(x)=10011´11111=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 = 5×3 = 15; k = n-m = 31-15 = 16.

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

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

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

L = S = 3;

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

r = 3S-1 = 5;

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

b = m £ 15.

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

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

M₁(x) =100101;

M₂(x) =111101;

M₃(x) =110111.

При этом

P(x) = M₁(x) ×M₂(x) ×M₃(x) =1000111110101111=

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

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

000000000000000100011111011111

G(31,16)=000000000000001000111110111110

. . .

100011111011111000000000000000

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

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

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

Рассмотрим алгоритм ПГЦ (Питерсона-Горенстейна-Цирлера). Пусть БЧХ код над полем GF(q) длины n и с конструктивным расстоянием d задается порождающим полиномом g(x), который имеет среди своих корней элементы $\beta^{l_0},\beta^{l_0+1},\ldots,\beta^{l_0+d-2} \quad \beta \in GF(q^m), \quad \beta^n=1$ , $\quad l_0$ — целое число (например 0 или 1). Тогда каждое кодовое слово обладает тем свойством, что $c(\beta^{l_0-1+j}) = 0, \quad j=1,2,\ldots,d-1$ . Принятое слово r(x) можно записать как r(x) = c(x) + e(x), где e(x) — полином ошибок. Пусть произошло $u \leqslant t = (d-1)/2$ ошибок на позициях $i_1,i_2,\ldots,i_u$ (t максимальное число исправляемых ошибок), значит $e(x) = e_{i_1}x^{i_1}+e_{i_2}x^{i_2}+\ldots+e_{i_u}x^{i_u}$ , а $e_{i_1}, e_{i_2},\ldots, e_{i_u}$ — величины ошибок.

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

$S_j = r(\beta^{l_0-1+j}) = e(\beta^{l_0-1+j}), \quad j=1,\ldots,d-1\quad\quad (1)$ .

Задача состоит в нахождений числа ошибок u, их позиций $i_1,i_2,\ldots,i_u$ и их значений $e_{i_1}, e_{i_2},\ldots, e_{i_u}$ при известных синдромах Sj.

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

${ \begin{cases}S_1 = e_{i_1} \beta^{l_0 i_1} + e_{i_2} \beta^{l_0 i_2} + \dots + e_{i_t} \beta^{l_0 i_t} \\S_2 = e_{i_1} \beta^{(l_0+1) i_1} + e_{i_2} \beta^{(l_0+1) i_2} + \dots + e_{i_t} \beta^{(l_0+1) i_t} \\\cdots \cdots \cdots \cdots \cdots \cdots \cdots \\S_{d-1} = e_{i_1} \beta^{(l_0+d-2) i_1} + e_{i_2} \beta^{(l_0+d-2) i_2} + \dots + e_{i_t} \beta^{(l_0+d-2) i_t} \\\end{cases} }$

Обозначим через $X_k = \beta^{i_k}$ локатор k-ой ошибки, а через $Y_k = e_{i_k}$ величину ошибки, $k=1,\ldots,t$ . При этом все Xk различны, так как порядок элемента β равен n, и поэтому при известном Xk можно определить ik как ik = logβXk.

${ \begin{cases}S_1 = Y_1 X_1^{l_0} + Y_2 X_2^{l_0} + \dots + + Y_t X_t^{l_0} \\S_2 = Y_1 X_1^{l_0+1} + Y_2 X_2^{l_0+1} + \dots + + Y_t X_t^{l_0+1} \quad \quad \quad \quad \quad\quad(2) \\\cdots \cdots \cdots \cdots \cdots \cdots \cdots \\S_{d-1} = Y_1 X_1^{l_0+d-2} + Y_2 X_2^{l_0+d-2} + \dots + + Y_t X_t^{l_0+d-2} \end{cases} }$

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

$\Lambda (x) = (1-xX_1)(1-xX_2)\dots (1-xX_t) = \Lambda_t x^t + \Lambda_{t-1} x^{t-1} + \dots + \Lambda_1 x + 1$

Корнями этого полинома являются элементы, обратные локаторам ошибок. Помножим обе части этого полинома на $Y_l X_{l}^{\vartheta+t}$ . Полученное равенство будет справедливо для

$\vartheta = l_0,l_0+1,\dots,l_0+d-1,\quad l=1,\ldots,t$ :

$\Lambda (x) Y_l X_{l}^{\vartheta+t} = \Lambda_t x^t Y_l X_{l}^{\vartheta+t} + \Lambda_{t-1} x^{t-1} Y_l X_{l}^{\vartheta+t} + \dots + \Lambda_1 x Y_l X_{l}^{\vartheta+t} + Y_l X_{l}^{\vartheta+t} \quad (3)$

Положим $x=X_l^{-1}$ и подставим в (3). Получится равенство, справедливое для каждого $l \in {1,2,...,t}$ и при всех $\vartheta \in { l_0,l_0+1,\dots,l_0+d-1 }$ :

$0 = \Lambda_t Y_l X_{l}^{\vartheta} + \Lambda_{t-1} Y_l X_{l}^{\vartheta+1} + \dots + \Lambda_{1} Y_l X_{l}^{\vartheta+t-1} + Y_l X_{l}^{\vartheta+t}$

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

$\vartheta \in { l_0,l_0+1,\dots,l_0+d-1 }$ :

$0 = \Lambda_t \sum_{l=1}^t Y_l X_{l}^{\vartheta} + \Lambda_{t-1} \sum_{l=1}^t Y_l X_{l}^{\vartheta+1} + \dots + \Lambda_{1} \sum_{l=1}^t Y_l X_{l}^{\vartheta+t-1} + \sum_{l=1}^t Y_l X_{l}^{\vartheta+t}$ .

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

$S_{j+p} = \sum_{l=1}^t Y_l X_{l}^{l_0+j+p-1} = \sum_{l=1}^t Y_l X_{l}^{\vartheta+p}, \quad j=1,\ldots,d-1, \quad \vartheta = l_0+j-1,$

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

${ \begin{cases}S_1 \Lambda_t + S_2 \Lambda_{t-1} + \dots + S_t \Lambda_1 = -S_{t+1} \\S_2 \Lambda_t + S_3 \Lambda_{t-1} + \dots + S_{t+1} \Lambda_1 = -S_{t+2} \quad \quad \quad \quad \quad\quad(4) \\\cdots \cdots \cdots \cdots \cdots \cdots \cdots \\S_t \Lambda_t + S_{t+1} \Lambda_{t-1} + \dots + S_{2t-1} \Lambda_1 = -S_{2t}\end{cases} }$

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

$S^{(t)} \bar\Lambda^{(t)} = -\bar s^{(t)}$ ,

Где

$S^{(t)}={ \left[ \begin{matrix}S_1 & S_2 & \dots & S_t \\S_2 & S_3 & \dots & S_{t+1} \\\cdots & \cdots & \cdots & \\S_t & S_{t+1} & \dots & S_{2t-1} \end{matrix} \right] }, \quad \quad \quad \quad \quad\quad(5)$

$\bar\Lambda^{(t)} = { \left[ \begin{matrix}\Lambda_t \\\Lambda_{t-1} \\\cdots \\\Lambda_1\end{matrix} \right] }, \quad \quad \bar s^{(t)}{ \left[ \begin{matrix}S_{t+1} \\S_{t+2} \\\cdots \\S_{2t}\end{matrix} \right] }$

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

После этого можно решить систему (4) и получить коэффициенты полинома локаторов ошибок. Его корни (элементы, обратные локаторам ошибок) можно найти простым перебором по всем элементам поля GF(qm). К ним найти элементы, обратные по умножению, — это локаторы ошибок $X_k, \quad k=1,\ldots,u$ . По локаторам можно найти позиции ошибок (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.

Раздел: Информатика, программирование
Количество знаков с пробелами: 9509
Количество таблиц: 0
Количество изображений: 2

Скачать

... СК содержит регистр памяти для хранения определенного числа информационных символов и преобразователь информационной последовательности в кодовую последовательность. Процесс кодирования производится непрерывно. Скорость кода R=k/n, где k - число информационных символов, одновременно поступающих на вход кодера, n - число соответствующих им символов на выходе кодера. Схема простого кодера показана ...

Скачать

... , що у дійсності виправляє сім помилок. Тому, що коди БЧХ є циклічними кодами, то при кодуванні використовуються загальні правила кодування інформації циклічними кодами. 3 Коди БЧХ. Алгоритми декодування Коди БЧХ є циклічними, і, отже, до них застосовні будь-які методи декодування циклічних кодів. Є, однак, істотно кращі алгоритми, розроблені спеціально для декодування кодів БЧХ. ...

Скачать

... , работавших в области электротехники, заинтересовалась возможностью создания технологии хранения данных, обеспечивающей более экономное расходование пространства. Одним из них был Клод Элвуд Шеннон, основоположник современной теории информации. Из разработок того времени позже практическое применение нашли алгоритмы сжатия Хаффмана и Шеннона-Фано. А в 1977 г. математики Якоб Зив и Абрахам Лемпел ...

Скачать

... процедуру перемешивания порядка символов в закодированной последовательности перед передачей и восстановлением исходного порядка символов после приема с тем, чтобы рандомизировать ошибки, объединенные в пакеты. Особенности практического кодирования Предположим, что все представляющие интерес данные могут быть представлены в виде двоичной (закодированной двоично) информации, т. е. в виде ...

Главная Новости Рефераты Статьи Вузы

О проекте Соглашение

Наверх

Войти на сайт

Навигация

Похожие работы

0 комментариев

Разделы

Инфо

Следите за новостями