Циклические коды

(краткий пересказ)

Что это такое

Циклические коды относятся к линейным кодам. Специфические свойства данного вида кодов помогают как при кодировании/декодировании, так и при аппаратной реализации этих процессов.

Одно из определений циклического кода

Определение: Линейный код называют циклическим, если для любого кодового слова [x_nx₀x₁...x_n-1] циклическая перестановка символов [x₀x₁...x_n-1x_n] также дает кодовое слово.

Процедура построения таких кодов гораздо более управляемая. Однако, нам потребуется перейти от векторного описания кодов к полиномиальному. Последовательность символов основного алфавита (0'ки и 1'ки в простейшем случае), составляющие сообщения и кодовые слова мы будем интерпретировать как коэффициенты полиномов. Например, считая, что коэффициенты записаны в порядке возрастания степени, сообщение [1010] запишем в виде многочлена 1 + x² . Кодирование сообщения в более "длинное" кодовое слово будет проводится умножением этого многочлена на другой, что дает в результате многочлен более высокой степени.

Рассмотрим операции с многочленами подробнее.

Полиномиальная арифметика

Рассмотрим многочлены с коэффициентами из поля Z₂. Сложение, умножение и деление полиномов проводится как обычно.

Для тех, кто это подзабыл, приведем пример на деление.

Пример 1

Найти (1 + x + x² + x⁵)/(1 + x²).

            x^3 +  x  +  1
          -----------------------------
x^2 +  1  | x^5 + x^2 +  x  +  1
		x^5 + x^3
          -----------------------------
                  x^3 + x^2 +  x  +  1
                  x^3 +  x 
                  ---------------------
                        x^2 +  1   
                        x^2 +  1
                        --------
                               0

(В арифметике поля Z₂ x + x = 0 , т.к. в более подробной записи x + x = (1 + 1)*x = 0*x = 0). Таким образом, 1 + x² делит 1 + x + x² + x⁵ нацело и результат есть 1 + x + x³.

Напомним также модульную арифметику многочленов. Многочлены называются сравнимыми по модулю многочлена p(x), если их разность делится на p(x) нацело. Поэтому для получения f(x)(mod p(x)) вам нужно просто разделить f(x) на p(x) и взять остаток от деления. Заметим, что если степень f(x) меньше степени p(x), то результатом будет просто f(x)

Пример 2

Нати 1 + x² + x⁵ (mod 1 + x²).

            x^3 +  x  +  1
          -----------------------------
x^2 +  1  | x^5 + x^2 +  1
		x^5 + x^3
          -----------------------------
                  x^3 + x^2 +  1
                  x^3 +  x 
                  ---------------------
                        x^2 +  x  +  1   
                        x^2 +  1
                        ---------------
                               x

Итак, 1 + x² + x⁵ (mod 1 + x²) = x.

Замечательным свойством полиномиального представления кодов является возможность осуществить циклический сдвиг на одну позицию вправо простым умножением кодового многочлена степени n-1 на многочлен "x" и нахождения остатка от деления на xⁿ + 1.

Пример 3

Осуществить единичный правый циклический сдвиг кодового слова [1011], используя полиномиальную интерпретацию.

Вектору [1011] соответствует полином 1 + x² + x³. Умножим его на x, что дает get x + x³ + x⁴. Далее, найдем остаток от деления на xⁿ + 1, т.е. x + x³ + x⁴ (mod xⁿ + 1) = x + x³ + x⁴ (mod x⁴ + 1).

             1
          -----------------------------
x^4 +  1  | x^4 + x^3 +  x
		x^4 +  1
          -----------------------------
                  x^3 +  x  +  1

Результат 1 + x + x³. Многочлен 1 + x + x³ соответствует вектору [1101], который получается из [1011] правым циклическим сдвигом на одну позицию.

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

Процедура кодирования в полиномиальной интерпретации сводится к умножению многочлена-сообщения на подходящий многочлен, называемый порождающим многочленом данного кода. Теоретическое обоснование опустим, приведем лишь формулировку соответствующей теоремы [3].

Tеорема: Многочлен g(x) является порождающим многочленом линейного циклического кода длины n тогда и только тогда, когда g(x) делит 1 + xⁿ.

Из теоремы следует, что для получения порождающего многочлена g(x) нам необходимо разложить на множители xⁿ + 1 и выделить многочлен такой степени, которая соответствует длине кодового слова. Длина кодового слова n и длина сообщения k связаны соотношением, k = n - deg(g(x)), где deg(g(x)) обозначает степень g(x).

Пример 4

Найти порождающий многочлен (ПМ) линейного циклического кода длины n = 15, который осуществляет кодирование сообщений длины k = 7. Затем кодировать сообщение [0110110].

Если нам нужен ПМ для кода длины 15 при длине сообщения 7, то нужно найти делитель x¹⁵ + 1 степени 15 - 7 = 8.

Многочлен x¹⁵ + 1 разлагается на множители (как? - вот в чем вопрос)

x¹⁵ + 1 = (1 + x)(1 + x + x²)(1 + x + x² + x³ + x⁴)(1 + x + x⁴)(1 + x³ + x⁴), поэтому можно взять g(x) = (1 + x + x² + x³ + x⁴)(1 + x + x⁴) = 1 + x⁴ + x⁶ + x⁷ + x⁸. Используя этот многочлен как ПМ мы строим код с минимальным расстоянием 5, который исправляет 2 ошибки. Найдя ПМ, мы можем кодировать сообщение [0110110]. В полиномиальной интерпретации вектору [0110110] соответствует x + x² + x⁴ + x⁵. Умножим его на ПМ g(x). (x + x² + x⁴ + x⁵)(1 + x⁴ + x⁶ + x⁷ + x⁸) = x + x² + x⁴ + x⁶ + x⁷ + x⁸ + x⁹ + x¹³

Соответствующее кодовое слово[011010111100010]. Итак, сообщение [0110110] кодировано в слово [011010111100010].

Алгоритм декодирования

Процедура декодирования циклического кода следующая [3].

Найти синдромный многочлен s(x) = r(x)(mod g(x)), где r(x) полученное слово.
Для каждого i >= 0, вычислять s_i(x) = xⁱs(x)(mod g(x)) до тех пор, пока не будет найден, s_j такой, что для него (вес)wt(s_j) <= t, где t -- максимальное число ошибок, исправляемых кодом. Таким образом полином ошибки есть e(x) = x^n-js_j(x) (mod (1 + xⁿ))

Пример 4 (прод.)

Декодировать полученное слово [011010111010010], которое было отправлено после кодирования кодом из первой части примера 4. Соответствующий вектору [011010111010010] многочлен x + x² + x⁴ + x⁶ + x⁷ + x⁸ + x¹⁰ + x¹³Найдем многочлен-синдром, (напомню, что g(x) = 1 + x⁴ + x⁶ + x⁷ + x⁸). x + x² + x⁴ + x⁶ + x⁷ + x⁸ + x¹⁰ + x¹³ (mod 1 + x⁴ + x⁶ + x⁷ + x⁸) = x² + x⁶ + x⁸

Для кодового слова синдром, как известно, равен 0. В данном случае это не так, посланное слово было искажено помехой. В соответствии с описанной процедурой декодирования будем вычислять s_i(x) = xⁱ(x² + x⁶ + x⁸)(mod g(x)) для последовательных возрастающих значений i пока не найдем многочлен степени меньшей или равной двум (число ошибок t = 2 ).

s₁ = xs(x)(mod g(x)) = (x³ + x⁷ + x⁹)(mod g(x)) = x³ + x⁴ + x⁵ + x⁶ + x⁷

s₂ = x²s(x)(mod g(x)) = (x⁴ + x⁸ + x¹⁰)(mod g(x)) = 1 + x + x² + x⁵

s₃ = x³s(x)(mod g(x)) = (x⁵ + x⁹ + x¹¹)(mod g(x)) = x + x² + x³ + x⁶

s₄ = x⁴s(x)(mod g(x)) = (x⁶ + x¹⁰ + x¹²)(mod g(x)) = x² + x³ + x⁴ + x⁷

s₅ = x⁵s(x)(mod g(x)) = (x⁷ + x¹¹ + x¹³)(mod g(x)) = 1 + x³ + x⁵ + x⁶ + x⁷

s₆ = x⁶s(x)(mod g(x)) = (x⁸ + x¹² + x¹⁴)(mod g(x)) = x + 1

x + 1 имеет вес 2, поэтому для нахождения многочлена ошибок вычисляем e(x) = x^15-6s₆(x)(mod (1 + xⁿ)) = x⁹(x + 1)(mod (1 + xⁿ)) = x¹⁰ + x⁹.

Итак, если отправленное кодовое слово имеет не более двух ошибок, то оно было таким

(x + x² + x⁴ + x⁶ + x⁷ + x⁸ + x¹⁰ + x¹³) + (x¹⁰ + x⁹) =

x + x² + x⁴ + x⁶ + x⁷ + x⁸ + x⁹ + x¹³

Этот многочлен соответствует вектору [011010111100010]. Чтобы восстановить само сообщение нам надо разделить кодовое слово на ПМ g(x) и получить

x + x² + x⁴ + x⁵,

значит сообщение было [0110110].

Немного подробнее

IV. Размерность, порождающая и проверочная матрицы

Сейчас мы рассмотрим, как идеи, которые первоначально обсуждались применительно к линейным кодам, будут интерпретироваться при полиномиальном описании циклических кодов.

Теорема: Если ПМ g(x) кода C имеет степень n-k тогда C является (n,k)-циклическим кодом. Если g(x) = a₀ + a₁x + a₂x² + ... + a_n-k x^n-k , то порождающая матрица кода C k x n матрица вида:

[cyclic form of generator matrix]

Док-во: Векторы g(x), xg(x), x²g(x), ..., x^k-1g(x) линейно -независимы. IВ противном случае существует нетривиальный набор коэффициентов {b_i} такой, что

b₀g(x) + b₁xg(x) + b₂ x² g(x) + ... + b_k-1 x^k-1 g(x) = 0,
(b₀ + b₁x + b₂x² + ... + b_k-1 x^k-1) g(x) = 0.

Но степень этого произведения k - 1 + n - k = n - 1 < n, поэтому оно не может быть тождественно = 0 mod (xⁿ - 1), кроме как при всех b_i = 0.

Пусть c(x) из C, тогда c(x) = b(x) g(x) и можно заключить, что b(x) имеет степень <= k - 1 (иначе произведение будет иметь степень > n - 1 и придется приводить к остатку по mod (xⁿ - 1), b'(x), удовлетворяющему этому ограничению на степень ). Таким образом, c(x) может быть представлено линейной комбинацией функций вида xⁱ g(x).

Система {xⁱ g(x) }, 0 <= i <= k - 1 является базисом C, а, следовательно, размерность кода k.

Получив полиномиальную интерпретацию циклического кода C, мы рассмотрим соответствующую интерпретацию дуального к C кода C^perp . Покажем, что дуальный циклическому коду C код C^perp также циклический.

Рассмотрим многочлен h(x) = (xⁿ - 1)/g(x), где g(x) ПМ кода C. Если deg(g(x)) = n - k, то deg(h(x)) = k и он также нормированный, поэтому h(x) порождает циклический код C' размерности n - k. Пусть c₁(x) = a₁(x)g(x) из C и c₂(x) = a₂(x)h(x) из C'. Тогда

c₁(x) c₂(x) = a₁(x)g(x)a₂(x)h(x) = a₁(x)a₂(x)f(x) = 0 (mod f(x)),

где f(x) = xⁿ - 1. Поэтому, используя умножение многочленов по модулю mod f(x), произведение любого кодового многочлена из C и любого многочлена из C' будет давать 0. Означает ли это, что C' -- дуальный к C код? К сожалению нет, поскольку построенный изоморфизм не сохраняет скалярное произведение, т.е. скалярное произведение векторов не соответствует нулевому произведению многочленов. Однако, коды C' и C тесно связаны - они эквивалентны.

Рассмотрим два вектора:

a = (a₀ a₁ ... a_n-1) из C
и
b = (b₀ b₁ ... b_n-1) из C',

и их произведение (вернее, соответствующих многочленов)

$[a(x) b(x) = sum from {i=0} to {n-1} c_i x^i (mod x^n - 1)]$

для каких-то c_i из F. Свободный член произведения

c₀ = a₀ b₀ + a₁b_n-1 + a₂ b_n-2 + ... + a_n-1 b₁,

т.к xⁿ = 1 (mod f(x)). Теперь c₀ можно записать как скалярное произведение

c₀ = a b'

где b' вектор, полученный из b циклическим сдвигом координат b на одну позицию влево и изменением порядка записи координат (т.е. (b₀ b_n-1 b_n-2 ... b₁)). Заметим, что умножение многочлена [sum from {i=0} to {n-1} c_i xⁱ] на x^n-t приводит к тому, что c_t становится свободным членом, а значит c_t -- свободный член a(x)(x^n-t b(x)). Поэтому,

c_t = a b'

где b' теперь вектор, связанный с x^n-t b(x). По отношению к b(x), b' это вектор, полученный циклическим сдвигом b на t+1 позиций влево с последующим изменением порядка координат на противоположный.

Примет: Пусть n = 3, и вектора a = (a₀ a₁ a₂) и b = (b₀ b₁ b₂). Перемножая их по mod x³ - 1, получим

a(x)b(x) = (a₀ + a₁x + a₂ x²)(b₀ + b₁x + b₂ x²)
= (a₀ b₀ + a₁b₂ + a₂ b₁) + (a₀ b₁ + a₁ b₀ + a₂ b₂)x + (a₀ b₂ + a₁ b₁ + a₂ b₀)x².

Коэффициент при x² будет a(b₂ b₁ b₀). Этот вектор b' получен из b сдвигом на 3 ( = 2 + 1) позиции влево (это ставит все координаты на старые места) и изменением порядка координат с последней на первую. b-вектор в коэффициенте при x получается из b сдвигом на 2 ( = 1 + 1) позиции влево, что дает (b₂ b₀ b₁) и изменением порядка следования (b₁ b₀ b₂).

Теперь поскольку a(x)b(x) = 0 mod (xⁿ - 1), коэффициенты при всех степенях x должны равняться 0. Вышеприведенное рассуждение приводит к заключению, что ac = 0 (т.е., векторы a и c ортогональны) для c полученного любой циклической перестановкой (сдвигом) вектора, координаты которого имеют противоположный порядок следования, чем у b. Поскольку h(x) порождает код C', {h(x), xh(x), ..., x^n-k-1h(x) } это базис для C' и G' = [h(x), xh(x), ..., x^n-k-1h(x)]^t -- порождающая матрица для C'. Теперь G' порождает код C' той же размерности n - k, что и C . Более того, взяв в качестве b(x) сам h(x), мы видим, что обратнопереставленный любой вектор из C' ортогонален любому вектору из C. Это означает, что переставив в обратном порядке колонки G', мы получим матрицу H, которая порождает код C^perp , а значит является проверочной для C.

Пример: Предположим, что мы хотим построить порождающую матрицу для (7,4)- бинарного циклического кода. Поскольку g(x) = 1 + x + x³ делит f(x) = x⁷ - 1, то g(x) порождает (7,4) - циклический код C. h(x) = f(x)/g(x) = 1 + x + x² + x⁴ порождает (7,3)-циклический код C'. Порождающая матрица для C

[G = matrix { 1101000, 0110100, 0011010, 0001101}]

Порождающая матрица для C'

[G' = matrix { 1110100, 0111010, 0011101}]

Перепишем колонки G' в обратном порядке, получим порождающую матрицу для C^perp (она же проверочная для исходного кода)

[H = matrix { 0010111, 0101110, 1011100}]

Нетрудно проверить, что GH^T = 0.

Поскольку C' и C^perp могут быть получены простой перестановкой координат всех векторов - это эквивалентные коды. Повторим ранее данное определение,

Определение : Пусть h(x) = a₀ + a₁ x + ... + a_k x^k многочлен степени k (a_k#0). Определим обратный многочлен h_R (x) для h(x) формулой

$[h_R (x) = sum from {i=0} to k a_{k-i} x^i]$

Заметим, что h_R(x) = x^k h(1/x), где k = deg h(x). Суммируя все вышесказанное, получим следующее.

Tеорема: Пусть g(x) -- нормированный делитель f(x) = xⁿ - 1 степени n-k, и, следовательно, ПМ для циклического (n,k)-кода C. Пусть h(x) = f(x)/g(x). Тогда h_R(x) -- обратный многочлен к h(x), есть ПМ кода C^perp .

V. Синдромы и охота на ошибки

Прежде всего рассмотрим альтернативный вид [R, I_k] порождающей матрицы циклического кода (систематический). Пусть g(x) ПМ кода. Разделим x^n-k+i на g(x) для 0 <= i <= k-1. Это дает

x^n-k+i = q_i(x)g(x) + r_i(x)

где deg(r_i(x)) < deg (g(x)) = n-k или r_i(x) = 0. Then

x^n-k+i - r_i(x) = q_i(x)g(x) in C

система k линейно независящих кодовых слов, матрица, по строкам которой записаны эти слова, есть порождающая матрица требуемого вида.

Пример: Рассмотрим бинарный (7,4)-циклический код, порожденный g(x) = 1 + x + x³. Алгоритм деления дает:

x³ = (1)(x³ + x + 1) + (1+ x)
x⁴ = (x)(x³ + x + 1) + (x + x²)
x⁵ = (x² + 1)(x³ + x + 1) + (1 + x + x²)
x⁶ = (x³ + x + 1)(x³ + x + 1) + (1 + x²).

Порождающая матрица

                    1 1 0 1 0 0 0                                         1 1 0
                    0 1 1 0 1 0 0                                         0 1 1
             G =    1 1 1 0 0 1 0    =  [R I₄]            где   R  =      1 1 1
                    1 0 1 0 0 0 1                                         1 0 1   .

Заметим, что строки R как раз остатки от деления.

Соответствующая проверочная матрица это H = [I_n-k -R^t]. Разделение матрицы подобным образом предоставляет возможность удобной полиномиальной интерпретации синдрома вектора.

Tеорема: Пусть r(x) и s(x) есть соответствующие полиномиальные представления для вектора r и его синдрома s = Hr^t. Тогда s(x) -- остаток от деления r(x) на g(x).

Док-во: Пусть r(x) = a₀ + a₁ x + ... + a_n-1 x^n-1. Заметим, что столбцы i, 0 <= i <= n-k-1, матрицы H соответствуют xⁱ a столбцы j, n-k <= j <= n-1, соответствуют r_j-n+k(x), так что

[s(x) = r(x) - h(x) g(x)]

где h(x) = a_n-k q₀(x) + ... + a_n-1 q_k-1(x). Таким образом r(x) = h(x)g(x) + s(x). Поскольку deg r_i(x) <= n-k-1, то deg s(x) <= n-k-1. В силу единственности промежуточного частного и остатка при делении многочленов, мы можем заключить, что s(x) это остаток при делении r(x) на g(x).

Таким образом синдром вектора можно получить делением многочленов. Более того, синдром вектора и его циклического сдвига тесно связаны. Предположим, что

r(x) = q(x)g(x) + s(x),

где deg(s(x)) самое большее n-k-1. По вышеприведенной теореме s(x) синдром r(x). Теперь

xr(x) = xq(x)g(x) + xs(x).

Если степень xs(x) не более n-k-1, то снова это синдром xr(x). В противном случае, синдром xr(x) остаток от деления xs(x) на g(x). В этом случае, положим

$[s(x) = s'(x) + s_{n-k-1} x^{n-k-1}]$

Пусть ПМ

$[g(x) = g'(x) + x^{n-k}]$

Тогда

$[x s(x) = s_{n-k-1} g(x) + (x s'(x) -s_{n-k-1} g'(x) )]$

где deg (xs'(x) - s_n-k-1 g'(x)) <= n - k - 1. Теперь в силу единственности остатка и предыдущей теоремы, мы видим, что синдром xs(x) есть xs(x) - s_n-k-1 g(x). Приходим к выводу:

Tеорема: Пусть C циклический (n,k)-код над F с ПМ g(x), и пусть r(x) имеет синдромный многочлен s(x) = s₀ + s₁ x + ... + s_m x^m. Тогда синдромный многочлен xr(x) есть

xs(x) если deg s(x) < n-k-1, и
xs(x) - s_n-k-1 g(x), если deg s(x) = n-k-1.

Пример: Рассмотрим код предыдущего примера с ПМ g(x) = 1 + x + x³. Используя записанную там порождающую матрицу, мы можем получить проверочную матрицу,

                                              1 0 0 1 0 1 1
                       H = [I₃  -R^t]  =       0 1 0 1 1 1 0    .
                                              0 0 1 0 1 1 1

Получили вектор r = (1011011). Синдром r равен Hr^t = (001)^t = s. Многочлен

r(x) = 1 + x² + x³ + x⁵ + x⁶.

Если разделить r(x) на g(x), то получим

r(x) = (x³ + x² + x + 1)g(x) + x².

Остаток, как и следовало ожидать, равен s.

А теперь найдем остаток циклического сдвига r. Положим w = (1101101), что соответствует многочлену xr(x). Hw^t = (110)^t. В полиномиальной интерпретации этот синдром получается так. Поскольку deg s(x) = 2 = n-k-1, синдром xr(x) есть

xs(x) - 1g(x) = x³ - (x³ + x + 1) = 1 + x.

Предыдущее расмотрение дает нам интересный метод декодирования некоторых видов ошибок в циклических кодах. Эту технику иногда называют охотой(капканы) на ошибки ( error trapping).

Предположим, что C это (n,k)-код с минимальным расстоянием d = 2t + 1, и проверочной матрицей H = [I_n-k A]. Пусть c кодовое слово и e вектор ошибки веса не более t. Если получено r = c + e , то синдром r равен

s = H r^t = H (c + e)^t = H e^t.

Пусть e* = (s^t, 0), где 0 это k-вектор из 0'ей. Тогда H e*^t = s, т.е. e* и e имеют один и тот же синдром, значит в одном смежном классе C. Теперь пусть wt(s) <= t. Тогда wt(e*)<= t и значит e = e* , поскольку смежный класс содержит не более одного вектора веса меньше или равного t.

Следовательно, в этом случае ошибка известна и равна e = (s^t,0).

Алгоритм декодирования

Вычислим синдром s₀(x) of r(x) по алгоритму деления.
Положим i = 0.
Если wt(s_i(x)) <= t, тогда установим e(x) = x^n-i(s_i,0), и декодируем to r(x) - e(x).
Положим i = i + 1.
Если i = n then stop; ошибка не исправляется.
Если deg s_i-1(x) < n-k-1, тогда set s_i(x) = xs_i-1(x); иначе s_i(x) = xs_i-1(x) - g(x).
Go to (3).

Пример: g(x) = 1 + x² + x³ генерирует бинарный (7,4)-циклический код с минимальным расстоянием 3 (и следовательно 1-ошибку исправляет). Рассмотрим кодовое слово 1 + x + x⁵ = (1 + x + x²) g(x), пусть после передачи многочлен r(x) = 1 + x + x⁵ + x⁶ был получен. Декодируем его. Разделим r(x) на g(x) для нахождения синдрома,

r(x) = (x³ + 1)g(x) + (x + x²),

так s(x) = x + x².Так как вес s(x) > 1 (= t), вычислим синдром s₁(x) xr(x). Так как of s(x) = 2 = n - k - 1, умножаем s(x) на x и делим на g(x), что дает s₁(x) = 1. Поскольку вес 1, мы получили маску ошибки

e(x) = x^7-1(s₁,0) = x⁶(1000000) = x⁶.

Так как n = 7 все ошибки веса 1 имеют циклический сдвиг на шесть 0's и 6 > k = 4, исправляются все единичные ошибки..

Пример: g(x) = 1 + x⁴ + x⁶ + x⁷ + x⁸ порождает бинарный (15,7)-циклический код. Если минимальное расстояние 5(так), то t = 2. Некоторые (по меньшей мере) веса 2 маски ошибок могут содержать сдвиги не менее 7 0й и могут бытьотловлены. Если мы получили

r = (1100 1110 1100 010)

считаем,

r(x) = (x + x² + x⁴ + x⁵)g(x) + (1 + x² + x⁵ + x⁷).

Вычисляем синдромы s_i(x) для xⁱ r(x) пока wt(s_i(x)) <= 2.

                               i              s_i(x)

                               0             10100101
                               1             11011001
                               2             11100111
                               3             11111000
                               4             01111100
                               5             00111110
                               6             00011111
                               7             10000100

Итак, ошибка

e = x^15-7(s₇,0) = x⁸(100001000000000) = (0000 0000 1000 010),

и мы исправляем r(x) на r - e = (1100 1110 0100 000).