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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Формальное описание[править | править вики-текст]

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

Схема декодирования БЧХ кодов.jpg

Примечания[править | править вики-текст]

  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