Код Боуза

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

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

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

---

Пусть $~\alpha$ — примитивный элемент поля $~GF(q^m)$ (то есть $\alpha^{q^m-1}=1, \alpha^i \neq 1, i< q^m-1$), пусть $~\beta=\alpha^s$, — элемент поля $~GF(q^m)$ порядка $~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}$ элемента $~\beta$ для некоторого целого $~l_0$ (в том числе 0 и 1), является порождающим полиномом БЧХ-кода над полем $~GF(q)$ с длиной $n$ и минимальный расстоянием $~d_0 \geqslant d$. Поясним почему у получившегося кода будут именно такие характеристики (длина кода $~n$ , минимальное расстояние $~d_0$). Действительно, как показано в ^[1] , длина БЧХ кода равна порядку элемента $~\beta$, если $~d>2$ и равна порядку элемента $~\beta^{l_0}$, если $~d=2$, тогда ,так как случай $~d=2$ нам не интересен (такой код не может исправлять ошибки, только обнаруживать), то длина кода будет равна порядку элемента $~\beta$ ,то есть равна $~n$. Минимальное расстояние $~d_0$ может быть больше $~d$, когда корнями минимальных функций(стр.83^[2]) от элементов $~\beta^{l_0}, \beta^{l_0+1},\ldots,\beta^{l_0+d-2}$ будут элементы расширяющие последовательность, то есть элементы $~\beta^{l_0+d-1},\beta^{l_0+d},\ldots,\beta^{l_0+d_0 - 2}$.

---

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

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

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

Построение

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

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

1) построить циклотомические классы элемента $\beta=\alpha^s$ поля $GF(q^m)$ над полем $GF(q)$, где $\alpha$ — примитивный элемент $GF(q^m)$;

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

3) вычислить порождающий полином $g(x)=f_1(x)f_2(x)\ldots f_h(x)$, где $f_i(x)$ — полином, соответствующий $i$-ому циклотомическому классу; или вычислить $g(x)$, как НОК минимальных функций от элементов $\beta^{l_0}, \beta^{l_0+1},\ldots,\beta^{l_0+d-2}$ (стр.168^[1]).

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

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

Пусть $q=2$, требуемая длина кода $n=2^4-1=15$ и минимальное расстояние $d_0 \geqslant d = 5$. Возьмем $\alpha$ — примитивный элемент поля $GF(16)$, и $\alpha, \alpha^2, \alpha^3 ,\alpha^4$ — четыре подряд идущих степеней элемента $\alpha$. Они принадлежат двум циклотомическим классам над полем $GF(2)$, которым соответствуют неприводимые полиномы $f_1(x) = x^4+x+1$ и $f_2(x) = x^4+x^3+x^2+x+1$. Тогда полином

$g(x)=f_1(x)f_2(x)=x^8+x^7+x^6+x^4+1$

имеет в качестве корней элементы $\alpha, \alpha^2, \alpha^3 ,\alpha^4$ и является порождающим полиномом БЧХ-кода с параметрами $(15, 7, 5)$.

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

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

$g(x)=(x-\alpha)(x-\alpha^2)(x-\alpha^3)(x-\alpha^4)=x^4+\alpha^{13}x^3+\alpha^{6}x^2+\alpha^{3}x+\alpha^{10}$

.

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

Кодирование

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

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

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

Главной идеей в декодировании БЧХ кодов является использование элементов конечного поля для нумерации позиций кодового слова(или, эквивалентно, в порядке коэффициентов ассоциированного многочлена). Ниже приведена такая нумерация для вектора $~r = (r_0,r_1,\ldots,r_{n-1})$, соответствующего многочлену $~r(x)$.

значения	$r_0$	$r_1$	$\ldots$	$r_{n-1}$
локаторы позиций	$1$	$\alpha$	$\ldots$	$\alpha^{n-1}$

Пусть принятое слово ассоциировано с полиномом $r(x)=\nu(x) + e(x)$, где многочлен ошибок определён как: $e(x) = e_{J_1}x^{J_1}+e_{J_2}x^{J_2}+\ldots+e_{J_\nu}x^{J_\nu}$, где $\nu \le t_d$ число ошибок в принятом слове. Множества ${e_{J_1},e_{J_2},\ldots,e_{J_\nu}}$ и ${\alpha^{J_1},\alpha^{J_2},\ldots,\alpha^{J_\nu}}$ называют значениями ошибок и локаторами ошибок, соответственно, где $e_J \in GF(q)$ и $\alpha \in GF(q^m)$.

Синдромы определены как значения принятого полинома $r(x)$ в нулях порождающего многочлена кода:

       $S_1 = r(\alpha^b) = e_{J_1}\alpha^{bJ_1}+e_{J_2}\alpha^{bJ_2}+\ldots+e_{J_\nu}\alpha^{bJ_\nu}$
       $S_2 = r(\alpha^{b+1}) = e_{J_1}\alpha^{(b+1)J_1}+e_{J_2}\alpha^{(b+1)J_2}+\ldots+e_{J_\nu}\alpha^{(b+1)J_\nu}$
       $\vdots$
       $S_{2t_d} = r(\alpha^{b+2t_d-1}) = e_{J_1}\alpha^{(b+2t_d-1)J_1}+e_{J_2}\alpha^{(b+2t_d-1)J_2}+\ldots+e_{J_\nu}\alpha^{(b+2t_d-1)J_\nu}$
      

Здесь $~2*t_d = d - 1$ Для нахождения множества локаторов ошибок , введем в рассмотрение многочлен локаторов ошибок

$\sigma(x) = \prod_{l=1}^\nu (1 + \alpha^{J_l}x) = 1 + \sigma_{1}x + \sigma_{2}x^2 + \ldots + \sigma_{\nu}x^{\nu}$

корни которого равны обратным величинам локаторов ошибок. Тогда справедливо следующее соотношение между коэффициентами многочлена локаторов ошибок и синдромами(см. например ^[1], стр.200):

    $\sigma_{1}S_{t}+\sigma_{2}S_{t-1}+\ldots+\sigma_{t}S_{1} = -S_{t+1}$
    $\sigma_{1}S_{t+1}+\sigma_{2}S_{t}+\ldots+\sigma_{t}S_{2} = -S_{t+2}$
    $\ldots \quad \quad \quad \quad\quad \quad \quad \quad\quad \quad \quad \quad\quad \quad \quad \quad \quad \quad \quad(*)$ 
    $\sigma_{1}S_{2t-1}+\sigma_{2}S_{2t-2}+\ldots+\sigma_{t}S_{t} = -S_{2t}$

Известны следующие методы для решения этой системы уравнений относительно коэффициентов многочлена локаторов ошибок $\sigma_{i},i=1,2,\ldots,\nu$(ключевая система уравнений).

• Алгоритм Берлекемпа-Мэсси(BMA). По числу операций в конечном поле этот алгоритм обладает высокой эффективностью. BMA обычно используется для программной реализации или моделирования кодов БЧХ и кодов Рида-Соломона.
• Евклидов алгоритм(ЕА). Из-за высокой регулярной структуры этого алгоритма его широко используют для аппаратной реализации декодеров БЧХ и кодов Рида-Соломона.
• Прямое решение(Алгоритм Питерсона — Горенстейна — Цирлера (ПГЦ)). Исторически это первый метод декодирования , найденный Питерсоном для двоичного случая $(q=2)$, затем Горенстейном и Цирлером для общего случая. Этот алгоритм находит коэффициенты многочлена локаторов ошибок прямым решением, соответствующей системы линейных уравнений. В действительности , так как сложность этого алгоритма растет как куб минимального расcтояния $~d$, прямой алгоритм может быть использован только для малых значений $~d$, однако именно этот алгоритм лучше всего проясняет алгебраическую идею процесса декодирования.

Алгоритм Берлекемпа-Мэсси

Основная статья: Алгоритм Берлекэмпа — Мэсси

Этот алгоритм лучше всего рассматривать как итеративный процесс построения минимального регистра(сдвига) с обратной связью, генерирующего известную последовательность синдромов $S_1,S_2,\ldots,S_{2t_d}$. Его фактическая цель - построить полином $\sigma^{i+1}(x)$ наименьшей степени, удовлетворяющему следующему уравнению $\sum_{j=0}^{l_{i}+1} S_{k-j} \sigma_{j}^{i+1} = 0, l_{i}<k<i+1$.Решение этого уравнения эквивалентно следующему условию $\sigma^{i+1}(x) = 1 + \sigma_{1}^{i+1} x + \ldots + \sigma_{l_{i+1}}^{i+1} x^{l_{i+1}}$. Итеративный процесс построения такого многочлена и есть Алгоритм Берлекемпа-Мэсси.

Евклидов алгоритм

В основе этого метода лежит широко известный алгоритм Евклида по нахождению наибольшего общего делителя двух чисел (НОД), только в данном случае ищем НОК не двух чисел , а двух полиномов. Обозначим полином значений ошибок как $\Lambda = \sigma(x) S(x)$, где синдромный полином равен $S(x) = 1 + S_1 x + \ldots + S_{2*t_d} x^{2t_d}\quad (1)$. Из системы уравнений (*) следует что $\Lambda(x) = \sigma(x) S(x) \mod x^{2t_d + 1} \quad (2)$. Задача по сути сводится к тому чтобы определить $\Lambda(x)$ удовлетворяющего (2) и при этом степени не выше $t_{d}$. По сути такое решение и будет давать расширенный алгоритм Евклида, примененный к многочленам $r_0(x) = x^d$ и $r_1(x)=S(x)$ , где $d = 2t_d + 1$. Если на j-ом шаге расширенный алгоритм Евклида выдает решение $r_{j} = a_{j}(x) x^{2t_d + 1} + b_{j}(x) S(x)$, такое что $\deg[r_{j}(x)] \le t_d$, то $\Lambda(x) = r_j(x)$ и $\sigma_i(x) = b_j(x)$. При этом найденный полином $a_j(x)$ дальше не принимает участия в декодировании(он ищется только как вспомогательный). Таким образом будет найден полином локаторов ошибок $\sigma(x)$.

Прямое решение(Алгоритм Питерсона — Горенстейна — Цирлера (ПГЦ))

Пусть БЧХ код над полем $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$-ый синдром $S_j$ принятого слова $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}$ при известных синдромах $S_j$.

Предположим, для начала, что $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$. При этом все $X_k$ различны, так как порядок элемента $\beta$ равен $n$, и поэтому при известном $X_k$ можно определить $i_k$ как $i_k = \log_{\beta} X_k$.

${ \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)}$ и т. д., до тех пор, пока не установим истинное число ошибок.

Поиск Ченя

После того как ключевая система уравнений $(*)$ решена , получаются коэффициенты полинома локаторов ошибок. Его корни (элементы, обратные локаторам ошибок) можно найти простым перебором по всем элементам поля $GF(q^m)$. К ним найти элементы, обратные по умножению, — это локаторы ошибок $X_k, \quad k=1,\ldots,u$. Этот процесс легко реализовать аппаратно.

Алгоритм Форни

По локаторам можно найти позиции ошибок ($i_k=\log_{\beta}X_k$), а значения $Y_k$ ошибок из системы $(2)$, приняв $t=u$(алгоритм Форни). Декодирование завершено. Ниже приведена общая схема декодирования БХЧ кодов

Примечания

1. ↑ ^{1 2 3} Сагалович Ю. Л. Введение в алгебраические коды: Учебное пособие. — М.: МФТИ, 2007. — С. 175-176. — ISBN 5-7417-0191-4
2. ↑ Введение в алгебраические коды
3. ↑ Искусство помехоустойчивого кодирования

См. также

• Обнаружение и исправление ошибок
• Конечное поле
• Многочлен над конечным полем
• Матрица Вандермонда
• Линейный код
• Циклический код
• Код Рида — Соломона
• Алгоритм Евклида

Литература

• Блейхут Р. Теория и практика кодов, контролирующих ошибки = Theory and Practice of Error Control Codes. — М.: Мир, 1986. — 576 с.
• Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. — М.: Мир, 1976. — С. 596.
• Сагалович Ю. Л. Введение в алгебраические коды: Учебное пособие. — М.: МФТИ, 2007. — 262 с. — ISBN 5-7417-0191-4
• Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. — М.: Техносфера, 2005. — 320 с. — ISBN 5-94836-035-0