Код Боуза — Чоудхури — Хоквингема: различия между версиями

Пусть <math>~\alpha</math> — [[Примитивный элемент конечного поля|примитивный элемент]] [[Конечное поле|поля]] <math>~GF(q^m)</math> (то есть <math>\alpha^{q^m-1}=1,\;\alpha^i \neq 1,\;i< q^m-1</math>), пусть <math>~\beta=\alpha^s </math>, — элемент поля <math>~GF(q^m)</math> порядка <math>~n, \quad s = (q^m-1) / n </math>. Тогда нормированный [[Многочлен над конечным полем|полином]] <math>g(x)</math> минимальной степени над полем <math>GF(q)</math>, [[Корень многочлена|корнями]] которого являются <math>~d-1</math> подряд идущих степеней <math>~\beta^{l_0},\; \beta^{l_0+1},\;\ldots,\;\beta^{l_0+d-2}</math> элемента <math>~\beta</math> для некоторого целого <math>~l_0</math> (в том числе 0 и 1), является порождающим полиномом БЧХ-кода над полем <math>~GF(q)</math> с длиной <math>n</math> и минимальный расстоянием <math>~d_0 \geqslant d</math>. Поясним почему у получившегося кода будут именно такие характеристики (длина кода <math>~n</math>, минимальное расстояние <math>~d_0</math>). Действительно, как показано у Сагаловича{{sfn|Сагалович|2007|с=175—176}}, длина БЧХ кода равна [[Словарь терминов теории групп#П|порядку]] элемента <math>~\beta</math>, если <math>~d>2</math> и равна порядку элемента <math>~\beta^{l_0}</math>, если <math>~d=2</math>, тогда, так как случай <math>~d=2</math> нам не интересен (такой код не может исправлять ошибки, только обнаруживать), то длина кода будет равна порядку элемента <math>~\beta</math> ,то есть равна <math>~n</math>. Минимальное расстояние <math>~d_0</math> может быть больше <math>~d</math>, когда корнями минимальных функций{{sfn|Сагалович|2007|с=176}} от элементов <math>~\beta^{l_0},\;\beta^{l_0+1},\;\ldots,\;\beta^{l_0+d-2}</math> будут элементы расширяющие последовательность, то есть элементы <math>~\beta^{l_0+d-1},\;\beta^{l_0+d},\;\ldots,\;\beta^{l_0+d_0 - 2}</math>.

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

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

''Здесь'' <math>~2t_d = d - 1</math>

* '''Прямое решение''' (алгоритм Питерсона — Горенстейна — Цирлера, ПГЦ). Исторически это первый метод декодирования, найденный Питерсоном для двоичного случая <math>(q=2)</math>, затем Горенстейном и Цирлером для общего случая. Этот алгоритм находит коэффициенты ''многочлена локаторов ошибок'' прямым решением соответствующей системы линейных уравнений. В действительности, так как сложность этого алгоритма растет как куб минимального расстояния <math>~d</math>, прямой алгоритм может быть использован только для малых значений <math>~d</math>, однако именно этот алгоритм лучше всего проясняет алгебраическую идею процесса декодирования.