Порождающий многочлен

• Выбирается \(GF(q),\) где \(q=p^k,\) \(p\) – простое.
• Выбираются целые \(m, n, d, c,\) \(2 \le d \le n,\) \(gcd(n,q)=1,\) \(m\) – порядок \(q\) по модулю \(n\).
• Пусть \(α\) – корень \(n\)-той степени из \(1\) в \(GF(q^m)\)
• пусть \(m_i(x)\) – минимальный многочлен над \(GF(q)\) для \(α^i,\) т.е. многочлен с минимальной степенью, имеющий корнем \(α^i\)
• Порождающий многочлен тогда \[g(x) = lcm(m_c(x),\ldots,m_{c+d-2}(x)),\] где \(c\) – некоторое целое, \(c\ge 0.\)

• Если \(α\) – примитивный элемент \(GF(q^m)\), то \(n = q^m - 1.\)
• Такой код называется примитивным.
• Если \(c = 1,\) такой код называется кодом БЧХ в узком смысле.
• Интересно отметить, что число проверочных символов \(r = \mathrm{ord}(g(x)) \le d-1\)

Кодирование БЧХ-кодом

• Абсолютно аналогично кодированию любым другим циклическим кодом.
• Пусть \(c(x)\) – кодовое слово, \(g(x)\) – порождающий многочлен, \(m(x)\) – сообщение.
• Тогда
• либо \(c(x) = g(x) m(x),\)
• либо \(c(x) = m(x)x^r - r(x),\)
• \(r(x) = m(x) x^r \pmod {g(x)},\) а \(r\) – число проверочных символов.

Декодирование БЧХ-кодов

• оптимизированный метод декодирования по синдрому
• большинство алгоритмов работает по следующему принципу:

1. Вычисляются синдромы \(s_j\)
2. Из синдрома определяется число ошибок \(t\) и вычисляется многочлен локатора ошибок \(Λ(x)\)
3. Вычисляются корни \(Λ(x)\), которые дают местонахождение ошибок \(x_i\)
4. Вычисляются значения ошибок \(y_i\)
5. Ошибки исправляются.

Вычисление синдромов

• Полученный вектор \(r(x)\) вычисляется в нулях порождающего многочлена: \(α^c,\ldots,α^{c+d-2}\) – даёт синдромы
• Если кодовое слово передано без ошибок, оно делится на \(g(x)\), и все синдромы равны нулю
• В противном случае, какие-то из синдромов не будут равны нулю, и какие именно – содержит информацию о положении ошибок.

Вычисление \(Λ(x)\)

• Если синдромы не равны \(0,\) то вектор ошибки \(e(x) = e_1x^{i_1} + e_2x^{i_2} + \ldots + e_tx^{i_t}\)
• Находится многочлен \(Λ(x) = \prod_{j=1}^{t} \paren{xα^{i_j} - 1},\) такой, что \(t\) минимально, \(i_j\) соответствуют синдромам.
• Корни \(x = α^{-i_j}\) позволяют вычислить \(i_j\) (отсюда название “локатор ошибок”).

Алгоритмы:

1. Алгоритм Питерсона-Горнстейна-Цирлера

   Достаточно неэффективный, сводится к прямому поиску.

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

   Достаточно эффективен, но сравнительно сложен, чаще используется в программной реализации.

3. Евклидов алгоритм (алгоритм Сугиямы)

   Основан на расширенном алгоритме Евклида, существуют крайне эффективные аппаратные реализации.

Нахождение значений ошибок

• сводится к решению системы линейных уравнений \[s_j = e_1 α^{(j+с) i_1} + e_2 α^{(j+с) i_2} + \ldots\]
• можно использовать любой стандартный метод
• существует более эффективный алгоритм Форни.

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

• основан на применении интерполяции Лагранжа
• Находится многочлен \(Ω(x) = s(x)Λ(x) \pmod {x^{d-1}}\) – вычислитель ошибок
• \(s(x) = \sum_{i=0}^{d-2} x^i s_i\) – многочлен синдромов
• значения ошибок вычисляются как \(e_j = - \frac{X_j^{1-c}Ω(X_j^{-1})}{Λ'(X_j^{-1})},\)
• \(X_j^{-1}\) – корни \(Λ(x),\)
• \(Λ'(x)\) – формальная производная, \(Λ'(x) = \sum_{i=1}^{t} i λ_i x^{i-1}.\)

Алгоритм Сугиямы

• \(s(x),\) \(Λ(x)\) и \(Ω(x)\) удовлетворяют соотношению \(Λ(x)s(x) = q(x)x^{d-1} + Ω(x),\)
• эквивалентно \(Ω(x) = Λ(x)s(x) - q(x)x^{d-1}.\)
• Можно применить расширенный алгоритм Евклида: \(r_i(x) = a_i(x) s(x) + b_i(x) x^{d-1},\)
• Как только \(\mathrm{ord}(r_i(x)) < (d-1)/2,\) \(a_i(x) = Λ(x),\) \(b_i(x) = -q(x),\) \(r_i(x) = Ω(x).\)

• Порождающий многочлен \(g(x) = \prod_{i=c}^{c+d-2} (x - α^i)\)
• \(\mathrm{ord}(g(x)) = d - 1 = r\)
• \(n - k = r = d - 1\)
• \(|C| = q^k = q^{n-d+1}\)
• Оптимальны в смысле границы Синглтона

Наибольшее распространение получили:

• В записи на оптические носители информации
• В высокоскоростной связи
• В мобильной связи
• В космической связи (со спутниками, зондами и т.п.)
• В штрих- и QR-кодах

• По построению, код Р-С не может быть двоичным.
• Длина кода \(n \le \mathrm{ord}(α),\)
• для двоичного кода, \(n = 1,\) и такой код был бы бесполезен.

• Ошибки редко случаются в одном бите: обычно они возникают в нескольких битах подряд.
• Код РС работает над алфавитом большей размерности.
• Более эффективно справляется с сериями битовых ошибок, чем двоичные коды.

• В качестве размера поля обычно выбирается степень двойки
• Крайне распространён вариант \(GF(2^8).\)