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

Рефераты / Программирование, компьютеры и кибернетика / Коды Боуза-Чоудхури-Хоквингема

${ \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} \<p>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 бит.

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

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

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

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

Выводы

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

Скачать реферат

Страница: 1 2 3

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

Другие рефераты на тему «Программирование, компьютеры и кибернетика»:

Поиск рефератов

Последние рефераты раздела

document.write('<p class="otherfont" style="float:right; color:#222222; text-align:center;">Страница <br /><big style="font-size:18px;"><b>2</b></big></p>'); Коды Боуза-Чоудхури-Хоквингема

Другие рефераты на тему «Программирование, компьютеры и кибернетика»:

Поиск рефератов

Последние рефераты раздела

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