Русская Википедия:Циклический код
Шаблон:Rq Циклический код — линейный, блочный код, обладающий свойством цикличности, то есть каждая циклическая перестановка кодового слова также является кодовым словом. Используется для преобразования информации для защиты её от ошибок (см. Обнаружение и исправление ошибок).
Введение
Пусть <math>\overline{y} = (y_0, y_1, \dots, y_{n-1}) \in L^n</math> — слово длины n над алфавитом из элементов конечного поля <math>L = GF(q)</math> и <math>y(x) = y_0 + y_1 x + y_2 x^2 + \dots+ y_{n-1} x^{n-1}</math> — полином, соответствующий этому слову, от формальной переменной <math>x</math>. Видно, что это соответствие является изоморфизмом линейных пространств. Так как «слова» состоят из букв из поля, то их можно складывать и умножать (поэлементно), причём результат будет в том же поле. Полином, соответствующий линейной комбинации <math>\overline{y} = m_1 \overline{y_1} + m_2 \overline{y_2}</math> пары слов <math>\overline{y_1} = (y_{1,0}, \dots, y_{1,n-1})</math> и <math>\overline{y_2} = (y_{2,0}, \dots, y_{2,n-1})</math>, равен линейной комбинации полиномов этих слов <math>{y}(x) = \sum_{k=0}^{n-1} (m_1 y_{1k} + m_2 y_{2k}) x^k = m_1 \overline{y_1}(x) + m_2 \overline{y_2}(x)</math>.
Это позволяет рассматривать множество слов длины n над конечным полем как линейное пространство полиномов со степенью не выше n − 1 над полем <math>GF(q)</math>.
Алгебраическое описание
Если <math>\overrightarrow{c_1}</math> — кодовое слово, получающееся циклическим сдвигом на один разряд влево из слова <math>\overrightarrow{c}</math>, то соответствующий ему полином <math>c_1(x)</math> получается из предыдущего умножением на x:
- <math>c_1(x) = x c(x) \mod (x^n - 1)</math>, пользуясь тем, что <math>x^n \equiv 1 \mod (x^n - 1).</math>
Сдвиг вправо и влево соответственно на <math>j</math> разрядов:
- <math>c_j(x) = x^j c(x) \mod (x^n - 1),</math>
- <math>c_{-j}(x) x^j = c(x) \mod (x^n - 1).</math>
Если <math>m(x)</math> — произвольный полином над полем <math>GF(q)</math>, и <math>c(x)</math> — кодовое слово циклического <math>(n, k)</math> кода, то <math>m(x) c(x) \mod (x^n-1)</math> — тоже кодовое слово этого кода.
Порождающий полином
- Определение
Порождающим полиномом циклического <math>(n, k)</math> кода <math>C</math> называется такой ненулевой полином <math>g(x) = \sum\limits_{i=0}^r g_i x^i</math> из <math>C</math>, степень которого наименьшая, и коэффициент при старшей степени <math>g_r = 1</math>.
- Теорема 1
Если <math>C</math> — циклический <math>(n, k)</math> код, и <math>g(x)</math> — его порождающий полином, то степень <math>g(x)</math> равна <math>r = n - k</math>, и каждое кодовое слово может быть единственным образом представлено в виде
- <math>c(x) = m(x) g(x),</math>
где степень <math>m(x)</math> меньше или равна <math>k - 1</math>.
- Теорема 2
<math>g(x)</math> — порождающий полином циклического <math>(n, k)</math> кода — является делителем двучлена <math>x^n - 1</math>.
- Следствия
Таким образом, в качестве порождающего полинома можно выбирать любой полином делитель <math>x^n - 1</math>. Степень выбранного полинома будет определять количество проверочных символов <math>r</math>, число информационных символов <math>k = n - r</math>.
Порождающая матрица
Полиномы <math>g(x), x g(x), x^2 g(x), \dots, x^{k-1} g(x)</math> линейно независимы, иначе <math>m(x) g(x) = 0</math> при ненулевом <math>m(x)</math>, что невозможно.
Значит кодовые слова можно записывать, как и для линейных кодов, следующим образом:
- <math>\overline{m} G = (m_0, m_1, \dots, m_{k-1})
\begin{bmatrix}
g(x) \\
x g(x) \\
\dots \\
x^{k-1} g(x)
\end{bmatrix} = m(x) g(x),</math> где <math>G</math> является порождающей матрицей, <math>m(x)</math> — информационным полиномом.
Матрицу <math>G</math> можно записать в символьной форме:
- <math>
G = \begin{bmatrix}
g_0 & g_1 & \dots & g_{r-1} & g_r & 0 & \dots & 0 \\
0 & g_0 & \dots & g_{r-2} & g_{r-1} & g_r & \dots & 0 \\
\vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & \dots & 0 & g_0 & g_1 & \dots & g_r
\end{bmatrix}. </math>
Проверочная матрица
Для каждого кодового слова циклического кода справедливо <math>c(x) = 0 \mod g(x)</math>. Поэтому проверочную матрицу можно записать как
- <math>
H = \begin{bmatrix}
1 & x & x^2 & \dots & x^{n-2} & x^{n-1} \\
\end{bmatrix} \mod g(x). </math>
Тогда
- <math>\overline{c} H^T = \sum\limits_{i=0}^{n-1} c_i x^i = 0 \mod g(x).</math>
Кодирование
Несистематическое
При несистематическом кодировании кодовое слово получается в виде произведения информационного полинома на порождающий:
- <math>c(x) = m(x) g(x).</math>
Оно может быть реализовано при помощи перемножения полиномов.
Систематическое
При систематическом кодировании кодовое слово формируется в виде информационного подблока и проверочного:
- <math>c(x) = [s(x)\;m(x)].</math>
Пусть информационное слово образует старшие степени кодового слова, тогда
- <math>c(x) = x^r m(x) + s(x), \quad r = n - k.</math>
Тогда из условия <math>c(x) = x^r m(x) + s(x) = 0 \mod g(x)</math> следует
- <math>s(x) = -x^r m(x) \mod g(x).</math>
Это уравнение и задаёт правило систематического кодирования. Оно может быть реализовано при помощи многотактных линейных фильтров (МЛФ).
Примеры
Двоичный (7,4,3) код
В качестве делителя <math>x^7 - 1</math> выберем порождающий полином третьей степени <math>g(x) = x^3 + x + 1</math>, тогда полученный код будет иметь длину <math>n = 7</math>, число проверочных символов (степень порождающего полинома) <math>r = 3</math>, число информационных символов <math>k = 4</math>, минимальное расстояние <math>d = 3</math>.
Порождающая матрица кода:
- <math>G =
\begin{bmatrix}
1 & 1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1
\end{bmatrix},</math> где первая строка представляет собой запись полинома <math>g(x)</math> коэффициентами по возрастанию степени.
Остальные строки — циклические сдвиги первой строки.
Проверочная матрица:
- <math>H =
\begin{bmatrix}
1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 1
\end{bmatrix},</math> где i-й столбец, начиная с 1-го, представляет собой остаток от деления <math>x^{i-1}</math> на полином <math>g(x)</math>, записанный по возрастанию степеней, начиная сверху.
Так, например, 4-й столбец получается <math>h_4(x) = x^3 \mod g(x) = x + 1</math>, или в векторной записи <math>[1 1 0]</math>.
Легко убедиться, что <math>G H^T = 0</math>.
Двоичный (15,7,5) БЧХ код
В качестве порождающего полинома <math>g(x)</math> можно выбрать произведение двух делителей <math>x^{15} - 1</math>:
- <math>g(x) = g_1(x) g_2(x) = (x^4 + x + 1)(x^4 + x^3 + x^2 + x + 1) = x^8 + x^7 + x^6 + x^4 + 1.</math>
Тогда каждое кодовое слово можно получить с помощью произведения информационного полинома <math>m(x)</math> со степенью <math>k - 1</math> таким образом:
- <math>c(x) = m(x) g(x).</math>
Например, информационному слову <math>\overline m = [1000111]</math> соответствует полином <math>m(x) = x^6 + x^5 + x^4 + 1</math>, тогда кодовое слово <math>c(x) = (x^6 + x^5 + x^4 + 1)(x^8 + x^7 + x^6 + x^4 + 1) = x^{14} + x^{12} + x^9 + x^7 + x^5 + 1</math>, или в векторном виде <math>\overline c = [100001010100101]</math>.
См. также
- Обнаружение и исправление ошибок
- Линейный код
- БЧХ код
- Конечное поле
- Многочлен над конечным полем
- Код Рида — Соломона
- Код Хэмминга
Ссылки
