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

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

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

Содержание

Формальное описание

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


Пусть α — примитивный элемент поля GF(qm) (то есть \alpha^{q^m-1}=1, \alpha^i \neq 1, i< q^m-1), пусть β = αs, — элемент поля GF(qm) порядка n, \quad s = (q^m-1) / n . Тогда нормированный полином g(x) минимальной степени над полем GF(q), корнями которого являются d − 1 подряд идущих степеней \beta^{l_0}, \beta^{l_0+1},\ldots,\beta^{l_0+d-2} элемента β для некоторого целого l0 (в том числе 0 и 1), является порождающим полиномом БЧХ-кода над полем GF(q) с длиной n и минимальный расстоянием d_0 \geqslant d.


Число проверочных символов r равно степени g(x), число информационных символов k = nr, величина d называется конструктивным расстоянием БЧХ-кода. Если n = qm − 1, то код называется примитивным, иначе непримитивным.

Так же, как и для циклического кода, кодовый полином c(x) может быть получен из информационного полинома m(x), степени не больше k − 1, путем перемножения m(x) и g(x):

c(x) = m(x)g(x).

Построение

Для нахождения порождающего полинома необходимо выполнить несколько этапов:

  • выбрать q, то есть поле GF(q), над которым будет построен код;
  • выбрать длину n кода из условия n = (qm − 1) / s, где m,s — целые положительные числа;
  • задать величину d конструктивного расстояния;

1) построить циклотомические классы элемента β = αs поля GF(qm) над полем GF(q), где α — примитивный элемент GF(qm);

2) поскольку каждому такому циклотомическому классу соответвует неприводимый полином над GF(q), корнями которого являются элементы этого и только этого класса, со степенью равной количеству элементов в классе, то выбрать \beta^{l_0}, \beta^{l_0+1},\ldots, \beta^{l_0+d-2} таким образом, чтобы суммарная длина циклотомических классов была минимальна

3) вычислить порождающий полином g(x)=f_1(x)f_2(x)\ldots f_h(x), где fi(x) — полином, соответсвующий i-ому циклотомическому классу

Примеры кодов

Примитивный 2-ичный (15,7,5) код

Пусть q = 2, требуемая длина кода n = 24 − 1 = 15 и минимальное расстояние d_0 \geqslant d = 5 . Возьмем α — примитивный элемент поля GF(16), и α,α234 — четыре подряд идущих степеней элемента α. Они принадлежат двум циклотомическим классам над полем GF(2), которым соответсвуют неприводимые полиномы f1(x) = x4 + x + 1 и f2(x) = x4 + x3 + x2 + x + 1. Тогда полином

g(x) = f1(x)f2(x) = x8 + x7 + x6 + x4 + 1

имеет в качестве корней элементы α,α234 и является порождающим полиномом БЧХ-кода с параметрами (15,7,5).

16-ричный (15,11,5) код (код Рида — Соломона)

Пусть n = q − 1 = 15 и α — примитивный элемент GF(16). Тогда

g(x) = (x − α)(x − α2)(x − α3)(x − α4) = x4 + α13x3 + α6x2 + α3x + α10

.

Каждому элементу поля GF(16) можно сопоставить 4 битам, поэтому одно кодовое слово эквивалентно 60=15*4 битам, таким образом набору из 44 бит ставится в соответствие набор из 60 бит. Можно сказать, что такой код работает с полубайтами информации.

Кодирование

Для кодирования кодами БЧХ применяются те же методы, что и для кодирования циклическими кодами.

Методы декодирования

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

Исторически первым методом декодирования был найден Питерсоном для двоичного случая (q = 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. Декодирование завершено.

См. также

Литература

  • Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and practice of error control codes. — М.: Мир, 1986. — С. 576.
  • Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. — С. 596.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Полезное


Смотреть что такое "Код Боуза-Чоудхури-Хоквингема" в других словарях:

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

  • Код Рида — Соломона — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… …   Википедия

  • Код коррекции ошибок Рида-Соломона — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… …   Википедия

  • Код Рида-Соломона — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… …   Википедия

  • Код Рида — Коды Рида Соломона (англ. Reed–Solomon codes) недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона,… …   Википедия

  • КОД С ИСПРАВЛЕНИЕМ ОШИБОК — код, корректирующий ошибки, множество сообщений, предназначенных для передачи по каналу связи с шумами, обладающее тем свойством, что окрестность ошибок каждого сообщения (т. е. совокупность искаженных вариантов этого сообщения) не пересекается с …   Математическая энциклопедия

  • Контрольный код — Обнаружение ошибок в технике связи  действие, направленное на контроль целостности данных при записи/воспроизведении информации или при её передаче по линиям связи. Исправление ошибок (коррекция ошибок)  процедура восстановления информации после… …   Википедия

  • РС код — Коды Рида Соломона недвоичные циклические коды, позволяющие исправлять ошибки в блоках данных. Элементами кодового вектора являются не биты, а группы битов (блоки). Очень распространены коды Рида Соломона, работающие с байтами (октетами). Код… …   Википедия

  • Турбо-код — Турбо код  параллельный каскадный блоковый систематический код, способный исправлять ошибки, возникающие при передаче цифровой информации по каналу связи с шумами. Синонимом турбо кода является известный в теории кодирования термин … …   Википедия

  • Линейный код — В области математики и теории информации линейный код  это важный тип блокового кода, использующийся в схемах определения и коррекции ошибок. Линейные коды, по сравнению с другими кодами, позволяют реализовывать более эффективные алгоритмы… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»