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

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

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

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

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

Поясним, почему у получившегося кода будут именно такие характеристики (длина кода $n$, минимальное расстояние $d_0$). Действительно, как показано у Сагаловича, длина БЧХ-кода равна порядку элемента $\beta$, если $d>2$, и равна порядку элемента ${\beta }^{l_0}$, если $d=2$. Так как случай $d=2$ нам не интересен (такой код не может исправлять ошибки, только обнаруживать), то длина кода будет равна порядку элемента $\beta$, то есть равна $n$. Минимальное расстояние $d_0$ может быть больше $d$, когда корнями минимальных функций от элементов ${\beta }^{l_0},{\beta }^{l_0+1},\dots ,{\beta }^{l_0+d-2}$ будут элементы, расширяющие последовательность, то есть элементы ${\beta }^{l_0+d-1},{\beta }^{l_0+d},\dots ,{\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$ конструктивного расстояния;
• построить циклотомические классы элемента $\beta ={\alpha }^s$ поля $GF(q^m)$ над полем $GF(q)$, где $\alpha$ — примитивный элемент $GF(q^m)$;
• поскольку каждому такому циклотомическому классу соответствует неприводимый полином над $GF(q)$, корнями которого являются элементы этого и только этого класса, со степенью равной количеству элементов в классе, то выбрать ${\beta }^{l_0},{\beta }^{l_0+1},\dots ,{\beta }^{l_0+d-2}$ таким образом, чтобы суммарная длина циклотомических классов была минимальна; это делается для того, чтобы при заданных характеристиках кода $n$ и $d$ минимизировать количество проверочных символов $k$;
• вычислить порождающий полином $g(x)=f_1(x)f_2(x)\dots f_h(x)$, где $f_i(x)$ — полином, соответствующий $i$-му циклотомическому классу; или вычислить $g(x)$, как НОК минимальных функций от элементов ${\beta }^{l_0},{\beta }^{l_0+1},\dots ,{\beta }^{l_0+d-2}$.

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

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

Пусть $q=2$, требуемая длина кода $n=2^4-1=15$, и минимальное расстояние $d_0⩾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 битов. Можно сказать, что такой код работает с полубайтами информации.

Кодирование

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

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

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

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

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

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

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

$S_1=r({\alpha }^b)=e_{J_1}{\alpha }^{b{J}_1}+e_{J_2}{\alpha }^{b{J}_2}+\dots +e_{J_{\nu }}{\alpha }^{b{J}_{\nu }},$

$S_2=r({\alpha }^{b+1})=e_{J_1}{\alpha }^{(b+1)J_1}+e_{J_2}{\alpha }^{(b+1)J_2}+\dots +e_{J_{\nu }}{\alpha }^{(b+1)J_{\nu }},$

$⋮$

$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}+\dots +e_{J_{\nu }}{\alpha }^{(b+2t_d-1)J_{\nu }},$

где $2t_d=d-1$.

Для нахождения множества локаторов ошибок введём в рассмотрение многочлен локаторов ошибок

$\sigma (x)=\prod _{l=1}^{\nu }(1+{\alpha }^{J_l}x)=1+{\sigma }_{1}x+{\sigma }_2{x}^2+\dots +{\sigma }_{\nu }{x}^{\nu },$

корни которого равны обратным величинам локаторов ошибок. Тогда справедливо следующее соотношение между коэффициентами многочлена локаторов ошибок и синдромами:

${\sigma }_1{S}_t+{\sigma }_2{S}_{t-1}+\dots +{\sigma }_t{S}_1=-S_{t+1},$

${\sigma }_1{S}_{t+1}+{\sigma }_2{S}_t+\dots +{\sigma }_t{S}_2=-S_{t+2},$

$⋮$

${\sigma }_1{S}_{2t-1}+{\sigma }_2{S}_{2t-2}+\dots +{\sigma }_t{S}_t=-S_{2t}.$

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

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

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

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

Этот алгоритм лучше всего рассматривать как итеративный процесс построения минимального регистра (сдвига) с обратной связью, генерирующего известную последовательность синдромов $S_1,S_2,\dots ,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+\dots +{\sigma }_{l_{i+1}}^{i+1}{x}^{l_{i+1}}.$

Итеративный процесс построения такого многочлена и есть Алгоритм Берлекемпа — Мэсси.

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

В основе этого метода лежит широко известный алгоритм Евклида по нахождению наибольшего общего делителя двух чисел (НОД), только в данном случае ищем НОД не двух чисел, а двух полиномов. Обозначим полином значений ошибок как $\mathrm{\Lambda }=\sigma (x)S(x)$, где синдромный полином равен $S(x)=1+S_{1}x+\dots +S_{2t_d}{x}^{2t_d}$. Из системы уравнений следует, что $\mathrm{\Lambda }(x)=\sigma (x)S(x)mod{x}^{2t_d+1}$. Задача по сути сводится к тому чтобы определить $\mathrm{\Lambda }(x)$, удовлетворяющий последнему уравнению и при этом степени не выше $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)$, такое что $\mathrm{deg}[r_j(x)]⩽t_d$, то $\mathrm{\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},\dots ,{\beta }^{l_0+d-2},\beta \in GF(q^m),{\beta }^n=1,l_0$ — целое число (например, 0 или 1). Тогда каждое кодовое слово обладает тем свойством, что $c({\beta }^{l_0-1+j})=0,j=1,2,\dots ,d-1$. Принятое слово $r(x)$ можно записать как $r(x)=c(x)+e(x)$, где $e(x)$ — полином ошибок. Пусть произошло $u⩽t=(d-1)/2$ ошибок на позициях $i_1,i_2,\dots ,i_u$ ($t$ — максимальное число исправляемых ошибок), значит $e(x)=e_{i_1}{x}^{i_1}+e_{i_2}{x}^{i_2}+\dots +e_{i_u}{x}^{i_u}$, а $e_{i_1},e_{i_2},\dots ,e_{i_u}$ — величины ошибок.

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

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

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

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

$\{\begin{array}{l}{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},\\ ⋮\\ 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{array}$

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

$\{\begin{array}{l}{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},\\ ⋮\\ 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{array}$

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

$\mathrm{\Lambda }(x)=(1-x{X}_1)(1-x{X}_2)\dots (1-x{X}_t)={\mathrm{\Lambda }}_t{x}^t+{\mathrm{\Lambda }}_{t-1}{x}^{t-1}+\dots +{\mathrm{\Lambda }}_{1}x+1.$

Корнями этого полинома являются элементы, обратные локаторам ошибок. Помножим обе части этого полинома на $Y_l{X}_l^{\vartheta +t}$. Полученное равенство будет справедливо для $\vartheta =l_0,l_0+1,\dots ,l_0+d-1,l=1,\dots ,t$:

$\mathrm{\Lambda }(x)Y_l{X}_l^{\vartheta +t}={\mathrm{\Lambda }}_t{x}^t{Y}_l{X}_l^{\vartheta +t}+{\mathrm{\Lambda }}_{t-1}{x}^{t-1}{Y}_l{X}_l^{\vartheta +t}+\dots +{\mathrm{\Lambda }}_{1}x{Y}_l{X}_l^{\vartheta +t}+Y_l{X}_l^{\vartheta +t}.$

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

$0={\mathrm{\Lambda }}_t{Y}_l{X}_l^{\vartheta }+{\mathrm{\Lambda }}_{t-1}{Y}_l{X}_l^{\vartheta +1}+\dots +{\mathrm{\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={\mathrm{\Lambda }}_t\sum _{l=1}^t{Y}_l{X}_l^{\vartheta }+{\mathrm{\Lambda }}_{t-1}\sum _{l=1}^t{Y}_l{X}_l^{\vartheta +1}+\dots +{\mathrm{\Lambda }}_1\sum _{l=1}^t{Y}_l{X}_l^{\vartheta +t-1}+\sum _{l=1}^t{Y}_l{X}_l^{\vartheta +t}.$

Поскольку $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},j=1,\dots ,d-1,\vartheta =l_0+j-1$ (то есть, $\vartheta$ меняется в тех же пределах, что и ранее), система уравнений для синдромов преобразуется в систему линейных уравнений:

$\{\begin{array}{l}{S}_1{\mathrm{\Lambda }}_t+S_2{\mathrm{\Lambda }}_{t-1}+\dots +S_t{\mathrm{\Lambda }}_1=-S_{t+1},\\ S_2{\mathrm{\Lambda }}_t+S_3{\mathrm{\Lambda }}_{t-1}+\dots +S_{t+1}{\mathrm{\Lambda }}_1=-S_{t+2},\\ ⋮\\ S_t{\mathrm{\Lambda }}_t+S_{t+1}{\mathrm{\Lambda }}_{t-1}+\dots +S_{2t-1}{\mathrm{\Lambda }}_1=-S_{2t},\end{array}$

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

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

где

$S^{(t)}=\left(\begin{array}{cccc}{S}_1& S_2& \dots & S_t\\ S_2& S_3& \dots & S_{t+1}\\ ⋮& ⋮& \ddots & ⋮\\ S_t& S_{t+1}& \dots & S_{2t-1}\end{array}\right),{\overline{\mathrm{\Lambda }}}^{(t)}=\left(\begin{array}{c}{\mathrm{\Lambda }}_t\\ {\mathrm{\Lambda }}_{t-1}\\ ⋮\\ {\mathrm{\Lambda }}_1\end{array}\right),{\overline{s}}^{(t)}=\left(\begin{array}{c}{S}_{t+1}\\ S_{t+2}\\ ⋮\\ S_{2t}\end{array}\right).$

Если число ошибок и в самом деле равно $t$, то эта система разрешима, и можно найти значения коэффициентов ${\mathrm{\Lambda }}_1,\dots ,{\mathrm{\Lambda }}_t$. Если же число $u<t$, то определитель матрицы $S^{(t)}$ будет равен $0$. Это есть признак того, что количество ошибок меньше $t$. Поэтому необходимо составить систему, предполагая число ошибок равным $t-1$, вычислить определитель новой матрицы $S^{(t-1)}$ и т. д. до тех пор, пока не установим истинное число ошибок.

Поиск Ченя

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

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

Общая схема декодирования БХЧ кодов (алгоритм Форни)

По локаторам можно найти позиции ошибок ($i_k={\log }_{\beta }{X}_k$), а значения $Y_k$ ошибок из системы для синдромов, приняв $t=u$. Декодирование завершено.

См. также

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

Литература

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