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

Работа добавлена на сайт bukvasha.net: 2015-01-08

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 27.12.2024

РЕФЕРАТ
По курсу “Теория информации и кодирования”
на тему:
"КОДЫ БОУЗА-ЧОУДХУРИ-ХОКВИНГЕМА"

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

Bukvasha