49.tex

\section{
 Циклические коды. Эквивалентное описание. Коды БЧХ. Пример.
}

Шпаргалка: $q = p^s$, $m, n$ такие, что $q^m-1 \vdots n$, $2 \le d \le n$, $l_0 \le n$. $\alpha$ -- образующая ${\mb F_{q^m}}^*$, $\beta=\alpha^{(q^m-1)/n}$



Будем смотреть на множество слов $\mb F_q^n$ как на $\mb F_q[x]/x^n-1$ и рассматривать коды только  вида $I \leq \mb F_q[x]/x^n-1$, гд $I$ -- идеал.


\thrm Пусть $C\leq \mb F_q[x]/x^n-1$ подпространство. Тогда $C$ идеал тогда и только тогда, когда для всякого слова $(a_0,\dots,a_{n-1})\in C$ слово $(a_{n-1},a_0,\dots,a_{n-2})$ тоже из $C$.
\proof
Достаточно чтобы домножение на $x$ оставляло любой элемент $I$ в $I$. Т.к. $x^n = 1$, домножение на $x$ это циклический сдвиг.
\endproof
\ethrm

\dfn Такие коды называются циклическими.
\edfn

Идеалы в этом кольце однозначно сопоставляются делителям $x^n-1$ (т.к. взаимно простые с нем многочлены обратимы). Каждый делитель $g \di x^n-1$ степени $\deg g = l$ дает нам $n, n-l, q$ код ($n-l$ т.к. $\frac {x^n-1} g$ -- минимальный, переводимый в ноль домножением на $g$).

Кодировать можно разными способами. Самое простое -- тупо домножить. Но можно сделать систематическое кодирование
$$m(x) \to m(x)x^{l}-r(x), \text{ где } r(x)=x^{l}m(x) \mod g(x).$$
Здесь строго говоря $m(x)$ записан в последние биты.

\dfn Коды БЧХ. Выберем $q = p^s$, $m, n$ такие, что $q^m-1 \vdots n$, $2 \le d \le n$, $l_0 \le n$. $\alpha$ -- образующая ${\mb F_{q^m}}^*$, $\beta=\alpha^{(q^m-1)/n}$.  $d$ называется конструктивным расстоянием. Спойлер -- оно не меньше кодового расстояния.

Рассмотрим элементы $\beta^{l_0},\beta^{l_0+1},\dots, \beta^{l_0+d-2}$ и многочлен наименьшей степени $g(x)$, корнями которого являются эти элементы.

$\beta^n - 1 = \alpha^{q^m-1} - 1 = 1-1 = 0$ поэтому $x^n-1$ от степеней $\beta$ равен $0$, значит $x^n-1$ делится на $g$.
\edfn

(мб описание проверочной матрицы входит в этот билет. Я ее вставил в следующий)

\noindent {\bf Пример тупо из конспекта:}\\
Пусть $q=2$. Возьмём $n=2^4-1=15$ (то есть $m=4$). Для того, чтобы построить поле из 16 элементов рассмотрим многочлен $x^4+x^3+1$. Он неприводим над $\mb F_2$. Его корень $\alpha$ -- первообразный корень степени $15$ из единицы. Возьмём $l_0=1$ и $d=5$. Тогда необходимо найти минимальные многочлены для элементов $\alpha,\alpha^2,\alpha^3,\alpha^4$. Заметим, что минимальные многочлены для $\alpha,\alpha^2,\alpha^4$ одинаковы и равны $x^4+x^3+1$ так как два последних элемента есть образы предыдущих при автоморфизме Фробениуса. Минимальный многочлен для $\alpha^3$ равен $x^4+x^3+x^2+x+1$.