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

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

Код был разработан Алексисом Хоквингемом^[fr] в 1959 году и от него Раджем Чандра Боузом^[en] и Дидженом Рэй-Чоудхури^[en] в 1960 году^[1][2][3].

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

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

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

Поясним, почему у получившегося кода будут именно такие характеристики (длина кода ${\displaystyle n}$, минимальное расстояние ${\displaystyle d_{0}}$). Действительно, как показано у Сагаловича^[4], длина БЧХ-кода равна порядку элемента ${\displaystyle \beta }$, если ${\displaystyle d>2}$, и равна порядку элемента ${\displaystyle \beta ^{l_{0}}}$, если ${\displaystyle d=2}$. Так как случай ${\displaystyle d=2}$ нам не интересен (такой код не может исправлять ошибки, только обнаруживать), то длина кода будет равна порядку элемента ${\displaystyle \beta }$, то есть равна ${\displaystyle n}$. Минимальное расстояние ${\displaystyle d_{0}}$ может быть больше ${\displaystyle d}$, когда корнями минимальных функций^[5] от элементов ${\displaystyle \beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}}$ будут элементы, расширяющие последовательность, то есть элементы ${\displaystyle \beta ^{l_{0}+d-1},\beta ^{l_{0}+d},\ldots ,\beta ^{l_{0}+d_{0}-2}}$.

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

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

${\displaystyle c(x)=m(x)g(x).}$

Построение

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

• выбрать ${\displaystyle q}$, то есть поле ${\displaystyle GF(q)}$, над которым будет построен код;
• выбрать длину ${\displaystyle n}$ кода из условия ${\displaystyle n=(q^{m}-1)/s}$, где ${\displaystyle m,s}$ — целые положительные числа;
• задать величину ${\displaystyle d}$ конструктивного расстояния;
• построить циклотомические классы элемента ${\displaystyle \beta =\alpha ^{s}}$ поля ${\displaystyle GF(q^{m})}$ над полем ${\displaystyle GF(q)}$, где ${\displaystyle \alpha }$ — примитивный элемент ${\displaystyle GF(q^{m})}$;
• поскольку каждому такому циклотомическому классу соответствует неприводимый полином над ${\displaystyle GF(q)}$, корнями которого являются элементы этого и только этого класса, со степенью равной количеству элементов в классе, то выбрать ${\displaystyle \beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}}$ таким образом, чтобы суммарная длина циклотомических классов была минимальна; это делается для того, чтобы при заданных характеристиках кода ${\displaystyle n}$ и ${\displaystyle d}$ минимизировать количество проверочных символов ${\displaystyle k}$;
• вычислить порождающий полином ${\displaystyle g(x)=f_{1}(x)f_{2}(x)\ldots f_{h}(x)}$, где ${\displaystyle f_{i}(x)}$ — полином, соответствующий ${\displaystyle i}$-му циклотомическому классу; или вычислить ${\displaystyle g(x)}$, как НОК минимальных функций от элементов ${\displaystyle \beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2}}$.

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

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

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

${\displaystyle g(x)=f_{1}(x)f_{2}(x)=x^{8}+x^{7}+x^{6}+x^{4}+1}$

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

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

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

${\displaystyle 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}.}$

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

Кодирование

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

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

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

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

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

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

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

${\displaystyle S_{1}=r(\alpha ^{b})=e_{J_{1}}\alpha ^{bJ_{1}}+e_{J_{2}}\alpha ^{bJ_{2}}+\ldots +e_{J_{\nu }}\alpha ^{bJ_{\nu }},}$

${\displaystyle 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 }},}$

${\displaystyle \vdots }$

${\displaystyle 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 }},}$

где ${\displaystyle 2t_{d}=d-1}$.

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

${\displaystyle \sigma (x)=\prod _{l=1}^{\nu }(1+\alpha ^{J_{l}}x)=1+\sigma _{1}x+\sigma _{2}x^{2}+\ldots +\sigma _{\nu }x^{\nu },}$

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

${\displaystyle \sigma _{1}S_{t}+\sigma _{2}S_{t-1}+\ldots +\sigma _{t}S_{1}=-S_{t+1},}$

${\displaystyle \sigma _{1}S_{t+1}+\sigma _{2}S_{t}+\ldots +\sigma _{t}S_{2}=-S_{t+2},}$

${\displaystyle \vdots }$

${\displaystyle \sigma _{1}S_{2t-1}+\sigma _{2}S_{2t-2}+\ldots +\sigma _{t}S_{t}=-S_{2t}.}$

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

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

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

Этот алгоритм лучше всего рассматривать как итеративный процесс построения минимального регистра (сдвига) с обратной связью, генерирующего известную последовательность синдромов ${\displaystyle S_{1},S_{2},\ldots ,S_{2t_{d}}}$. Его фактическая цель — построить полином ${\displaystyle \sigma ^{i+1}(x)}$ наименьшей степени, удовлетворяющему уравнению

${\displaystyle \sum _{j=0}^{l_{i}+1}S_{k-j}\sigma _{j}^{i+1}=0,\quad l_{i}<k<i+1.}$

Решение этого уравнения эквивалентно условию

${\displaystyle \sigma ^{i+1}(x)=1+\sigma _{1}^{i+1}x+\ldots +\sigma _{l_{i+1}}^{i+1}x^{l_{i+1}}.}$

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

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

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

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

Пусть БЧХ-код над полем ${\displaystyle GF(q)}$ длины ${\displaystyle n}$ и с конструктивным расстоянием ${\displaystyle d}$ задаётся порождающим полиномом ${\displaystyle g(x)}$, который имеет среди своих корней элементы ${\displaystyle \beta ^{l_{0}},\beta ^{l_{0}+1},\ldots ,\beta ^{l_{0}+d-2},\ \beta \in GF(q^{m}),\ \beta ^{n}=1,\ l_{0}}$ — целое число (например, 0 или 1). Тогда каждое кодовое слово обладает тем свойством, что ${\displaystyle c(\beta ^{l_{0}-1+j})=0,\ j=1,2,\ldots ,d-1}$. Принятое слово ${\displaystyle r(x)}$ можно записать как ${\displaystyle r(x)=c(x)+e(x)}$, где ${\displaystyle e(x)}$ — полином ошибок. Пусть произошло ${\displaystyle u\leqslant t=(d-1)/2}$ ошибок на позициях ${\displaystyle i_{1},i_{2},\ldots ,i_{u}}$ (${\displaystyle t}$ — максимальное число исправляемых ошибок), значит ${\displaystyle e(x)=e_{i_{1}}x^{i_{1}}+e_{i_{2}}x^{i_{2}}+\ldots +e_{i_{u}}x^{i_{u}}}$, а ${\displaystyle e_{i_{1}},e_{i_{2}},\ldots ,e_{i_{u}}}$ — величины ошибок.

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

${\displaystyle S_{j}=r(\beta ^{l_{0}-1+j})=e(\beta ^{l_{0}-1+j}),\quad j=1,\ldots ,d-1.}$

Задача состоит в нахождении числа ошибок ${\displaystyle u}$, их позиций ${\displaystyle i_{1},i_{2},\ldots ,i_{u}}$ и их значений ${\displaystyle e_{i_{1}},e_{i_{2}},\ldots ,e_{i_{u}}}$ при известных синдромах ${\displaystyle S_{j}}$.

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

${\displaystyle {\begin{cases}S_{1}=e_{i_{1}}\beta ^{l_{0}i_{1}}+e_{i_{2}}\beta ^{l_{0}i_{2}}+\ldots +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}}+\ldots +e_{i_{t}}\beta ^{(l_{0}+1)i_{t}},\\\vdots \\S_{d-1}=e_{i_{1}}\beta ^{(l_{0}+d-2)i_{1}}+e_{i_{2}}\beta ^{(l_{0}+d-2)i_{2}}+\ldots +e_{i_{t}}\beta ^{(l_{0}+d-2)i_{t}}.\\\end{cases}}}$

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

${\displaystyle {\begin{cases}S_{1}=Y_{1}X_{1}^{l_{0}}+Y_{2}X_{2}^{l_{0}}+\ldots +Y_{t}X_{t}^{l_{0}},\\S_{2}=Y_{1}X_{1}^{l_{0}+1}+Y_{2}X_{2}^{l_{0}+1}+\ldots +Y_{t}X_{t}^{l_{0}+1},\\\vdots \\S_{d-1}=Y_{1}X_{1}^{l_{0}+d-2}+Y_{2}X_{2}^{l_{0}+d-2}+\ldots +Y_{t}X_{t}^{l_{0}+d-2}.\end{cases}}}$

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

${\displaystyle \Lambda (x)=(1-xX_{1})(1-xX_{2})\ldots (1-xX_{t})=\Lambda _{t}x^{t}+\Lambda _{t-1}x^{t-1}+\ldots +\Lambda _{1}x+1.}$

Корнями этого полинома являются элементы, обратные локаторам ошибок. Помножим обе части этого полинома на ${\displaystyle Y_{l}X_{l}^{\vartheta +t}}$. Полученное равенство будет справедливо для ${\displaystyle \vartheta =l_{0},l_{0}+1,\ldots ,l_{0}+d-1,\ l=1,\ldots ,t}$:

${\displaystyle \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}+\ldots +\Lambda _{1}xY_{l}X_{l}^{\vartheta +t}+Y_{l}X_{l}^{\vartheta +t}.}$

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

${\displaystyle 0=\Lambda _{t}Y_{l}X_{l}^{\vartheta }+\Lambda _{t-1}Y_{l}X_{l}^{\vartheta +1}+\ldots +\Lambda _{1}Y_{l}X_{l}^{\vartheta +t-1}+Y_{l}X_{l}^{\vartheta +t}.}$

Таким образом для каждого ${\displaystyle l}$ можно записать своё равенство. Если их просуммировать по ${\displaystyle l}$, то получится равенство, справедливое для каждого ${\displaystyle \vartheta \in \{l_{0},l_{0}+1,\ldots ,l_{0}+d-1\}}$:

${\displaystyle 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}+\ldots +\Lambda _{1}\sum _{l=1}^{t}Y_{l}X_{l}^{\vartheta +t-1}+\sum _{l=1}^{t}Y_{l}X_{l}^{\vartheta +t}.}$

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

${\displaystyle {\begin{cases}S_{1}\Lambda _{t}+S_{2}\Lambda _{t-1}+\ldots +S_{t}\Lambda _{1}=-S_{t+1},\\S_{2}\Lambda _{t}+S_{3}\Lambda _{t-1}+\ldots +S_{t+1}\Lambda _{1}=-S_{t+2},\\\vdots \\S_{t}\Lambda _{t}+S_{t+1}\Lambda _{t-1}+\ldots +S_{2t-1}\Lambda _{1}=-S_{2t},\end{cases}}}$

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

${\displaystyle S^{(t)}{\bar {\Lambda }}^{(t)}=-{\bar {s}}^{(t)},}$

где

${\displaystyle S^{(t)}={\begin{pmatrix}S_{1}&S_{2}&\ldots &S_{t}\\S_{2}&S_{3}&\ldots &S_{t+1}\\\vdots &\vdots &\ddots &\vdots \\S_{t}&S_{t+1}&\ldots &S_{2t-1}\end{pmatrix}},\quad {\bar {\Lambda }}^{(t)}={\begin{pmatrix}\Lambda _{t}\\\Lambda _{t-1}\\\vdots \\\Lambda _{1}\end{pmatrix}},\quad {\bar {s}}^{(t)}={\begin{pmatrix}S_{t+1}\\S_{t+2}\\\vdots \\S_{2t}\end{pmatrix}}.}$

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

Поиск Ченя

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

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

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

См. также

• Конечное поле
• Многочлен над конечным полем
• Матрица Вандермонда
• Линейный код
• Алгоритм Евклида

Примечания

Литература

На русском

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

На других языках

• A. Hocquenghem^[en]. Codes correcteurs d'erreurs (фр.) // Chiffres. — Paris, 1959. — Septembre (vol. 2). — P. 147–156.
• R. C. Bose^[en], D. K. Ray-Chaudhuri^[en]. On A Class of Error Correcting Binary Group Codes (англ.) // Information and Control. — 1960. — March (vol. 3, iss. 1). — P. 68–79. — ISSN 0890-5401. — doi:10.1016/s0019-9958(60)90287-4. Архивировано 9 октября 2022 года.
• John Gill. EE387 Notes #7, Handout #24 (англ.). — Stanford University. Архивировано 5 июня 2013 года.
• Daniel Gorenstein^[en], W. Wesley Peterson^[en], N. Zierler. Two-Error Correcting Bose-Chaudhuri Codes are Quasi-Perfect (англ.) // Information and Control. — 1960. — Vol. 3, iss. 3. — P. 291—294. — doi:10.1016/s0019-9958(60)90877-9.
• Rudolf Lidl, Günter Pilz. Applied Abstract Algebra. — 2nd edition. — John Wiley, 1999.
• Irving S. Reed^[en], Chen Xuemin. Error-Control Coding for Data Networks. — Boston, MA: Kluwer Academic Publishers, 1999. — ISBN 0-7923-8528-4.

Эта страница в последний раз была отредактирована 18 марта 2024 в 15:45.