БЧХ-коды и коды Рида-Соломона

Граница Синглтона

Пусть \(C\) – код над алфавитом мощности \(q\) с длиной кодового слова \(n\) и минимальным кодовым расстоянием \(d.\) Тогда, если построить на его основе код \(C^*\), просто удалив первые \(d-1\) символов из каждого кодового слова, новый код останется однозначным, и следовательно \(\abs{C^*} = \abs{C}.\)

Длина кодового слова в \(C^*\) равна \(n - (d-1) = n-d+1,\) и его мощность не может превышать \(\abs{C} = \abs{C^*} \le q^{n-d+1}.\)

Соотношение \(\abs{C} \le q^{n-d+1}\) называется границей Синглтона.

БЧХ-коды

Коды Боуза-Чоудхури-Хоквингема (БЧХ)
класс помехоустойчивых кодов, являющийся подмножеством циклических кодов. БЧХ-коды задаются над полем \(GF(p^k)\), где \(p\) – простое число.

Основным интересным свойством БЧХ-кодов является возможность конструировать коды с заведомо известным минимальным кодовым расстоянием.

Конструкция порождающего многочлена примитивного БЧХ-кода

Как и любой циклический код, БЧХ-код задаётся порождающим многочленом, и допускает “простое” либо систематическое построение кодовых слов.

Порождающий многочлен БЧХ-кода задаётся следующим образом. Выбирается желаемое минимальное кодовое расстояние \(d\). Выбирается длина кодового слова \(n = q^m - 1\) (такой код называется примитивным). Пусть \(α\) – примитивный элемент поля \(GF(q^m)\). Пусть \(m_i(x)\) – минимальный многочлен с коэффициентами в \(GF(q)\) для \(α^i\), т.е. многочлен с минимальной степенью, имеющий корнем \(α^i\). Тогда порождающий многочлен БЧХ-кода может быть построен как \[g(x) = lcm(m_1(x),\ldots,m_{d-1}(x)).\]

Конструкция порождающего многочлена обобщённого БЧХ-кода

Обобщённый БЧХ-код отличается от примитивного тем, что вместо примитивного элемента \(α\), выбирается корень \(n\)-той степени из \(1\). Длина кодового слова \(n = \mathrm{ord}(α),\) т.е. порядок \(α\).

Выбирается \(GF(q),\) где \(q\) – целая степень простого числа. Выбираются целые \(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\). Порождающий многочлен тогда \[g(x) = lcm(m_с(x),\ldots,m_{с+d-2}(x)),\] где \(c\) – некоторое целое, \(c\ge 0.\)

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

Абсолютно аналогично кодированию любым другим циклическим кодом. Пусть \(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\) минимально, и \(e(x)\) соответствует найденным синдромам.

Корнями этого многочлена являются \(x = α^{-i_j},\) что позволяет вычислить \(i_j\) (отсюда название “локатор ошибок”).

Существует три популярных алгоритма для нахождения \(Λ(x)\):

  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},\] причём степень \(r_i\) убывает с увеличением \(i\). Тогда, как только степень \(r_i(x)\) меньше \((d-1)/2,\) т.е. количеству ошибок, которые код может исправить, имеем \[a_i(x) = Λ(x),\] \[b_i(x) = -q(x),\] \[r_i(x) = Ω(x).\]

Коды Рида-Соломона

Исторически, коды Рида-Соломона не являлись БЧХ-кодами, однако наиболее популярная (в силу эффективности) модификация кодов Рида-Соломона представляет собой ни что иное как БЧХ-код с \(m=1\). Обычно, под кодами Рида-Соломона понимается именно эта модификация.

Коды Рида-Соломона являются оптимальными в смысле границы Синглтона (что прямо следует из свойств циклических кодов).

Наибольшее распространение получили коды Рида-Соломона:

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

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

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

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