Циклические коды
Что это такое
Циклические коды относятся к линейным кодам. Специфические свойства данного вида кодов помогают как при кодировании/декодировании, так и при аппаратной реализации этих процессов.
Одно из определений циклического кода Определение Линейный код называют циклическим, если для любого кодового слова [x n x 0 x 1 . x n-1 ] циклическая перестановка символов [x 0 x 1 . x n-1 x n ] также дает кодовое слово.
Процедура построения таких кодов гораздо более управляемая. Однако, нам потребуется перейти от векторного описания кодов к полиномиальному. Последовательность символов основного алфавита (0’ки и 1’ки в простейшем случае), составляющие сообщения и кодовые слова мы будем интерпретировать как коэффициенты полиномов. Например, считая, что коэффициенты записаны в порядке возрастания степени, сообщение [1010] запишем в виде многочлена 1 + x 2 . Кодирование сообщения в более «длинное» кодовое слово будет проводится умножением этого многочлена на другой, что дает в результате многочлен более высокой степени.
Рассмотрим операции с многочленами подробнее.
Полиномиальная арифметика
Рассмотрим многочлены с коэффициентами из поля Z 2 . Сложение, умножение и деление полиномов проводится как обычно.
Для тех, кто это подзабыл, приведем пример на деление.
Пример 1
(В арифметике поля Z 2 x + x = 0 , т.к. в более подробной записи x + x = (1 + 1)*x = 0*x = 0). Таким образом, 1 + x 2 делит 1 + x + x 2 + x 5 нацело и результат есть 1 + x + x 3 .
Напомним также модульную арифметику многочленов. Многочлены называются сравнимыми по модулю многочлена p(x), если их разность делится на p(x) нацело. Поэтому для получения f(x)(mod p(x)) вам нужно просто разделить f(x) на p(x) и взять остаток от деления. Заметим, что если степень f(x) меньше степени p(x), то результатом будет просто f(x)
Пример 2
Замечательным свойством полиномиального представления кодов является возможность осуществить циклический сдвиг на одну позицию вправо простым умножением кодового многочлена степени n-1 на многочлен «x» и нахождения остатка от деления на x n + 1.
Пример 3
Вектору [1011] соответствует полином 1 + x 2 + x 3 . Умножим его на x, что дает get x + x 3 + x 4 . Далее, найдем остаток от деления на x n + 1, т.е. x + x 3 + x 4 (mod x n + 1) = x + x 3 + x 4 (mod x 4 + 1). Результат 1 + x + x 3 . Многочлен 1 + x + x 3 соответствует вектору [1101], который получается из [1011] правым циклическим сдвигом на одну позицию.
Порождающий многочлен
Процедура кодирования в полиномиальной интерпретации сводится к умножению многочлена-сообщения на подходящий многочлен, называемый порождающим многочленом данного кода. Теоретическое обоснование опустим, приведем лишь формулировку соответствующей теоремы [3].
Tеорема
Из теоремы следует, что для получения порождающего многочлена g(x) нам необходимо разложить на множители x n + 1 и выделить многочлен такой степени, которая соответствует длине кодового слова. Длина кодового слова n и длина сообщения k связаны соотношением, k = n — deg(g(x)), где deg(g(x)) обозначает степень g(x).
Пример 4
Если нам нужен ПМ для кода длины 15 при длине сообщения 7, то нужно найти делитель x 15 + 1 степени 15 — 7 = 8.
Многочлен x 15 + 1 разлагается на множители (как? — вот в чем вопрос) x 15 + 1 = (1 + x)(1 + x + x 2 )(1 + x + x 2 + x 3 + x 4 )(1 + x + x 4 )(1 + x 3 + x 4 ), поэтому можно взять g(x) = (1 + x + x 2 + x 3 + x 4 )(1 + x + x 4 ) = 1 + x 4 + x 6 + x 7 + x 8 . Используя этот многочлен как ПМ мы строим код с минимальным расстоянием 5, который исправляет 2 ошибки. Найдя ПМ, мы можем кодировать сообщение [0110110]. В полиномиальной интерпретации вектору [0110110] соответствует x + x 2 + x 4 + x 5 . Умножим его на ПМ g(x). (x + x 2 + x 4 + x 5 )(1 + x 4 + x 6 + x 7 + x 8 ) = x + x 2 + x 4 + x 6 + x 7 + x 8 + x 9 + x 13
Соответствующее кодовое слово[011010111100010]. Итак, сообщение [0110110] кодировано в слово [011010111100010].
Алгоритм декодирования
Процедура декодирования циклического кода следующая [3].
- Найти синдромный многочлен s(x) = r(x)(mod g(x)), где r(x) полученное слово.
- Для каждого i >= 0, вычислять s i (x) = x i s(x)(mod g(x)) до тех пор, пока не будет найден, s j такой, что для него (вес)wt(s j ) n-j s j (x) (mod (1 + x n ))
Пример 4 (прод.)
Для кодового слова синдром, как известно, равен 0. В данном случае это не так, посланное слово было искажено помехой. В соответствии с описанной процедурой декодирования будем вычислять s i (x) = x i (x 2 + x 6 + x 8 )(mod g(x)) для последовательных возрастающих значений i пока не найдем многочлен степени меньшей или равной двум (число ошибок t = 2 ).
s 1 = xs(x)(mod g(x)) = (x 3 + x 7 + x 9 )(mod g(x)) = x 3 + x 4 + x 5 + x 6 + x 7
s 2 = x 2 s(x)(mod g(x)) = (x 4 + x 8 + x 10 )(mod g(x)) = 1 + x + x 2 + x 5
s 3 = x 3 s(x)(mod g(x)) = (x 5 + x 9 + x 11 )(mod g(x)) = x + x 2 + x 3 + x 6
s 4 = x 4 s(x)(mod g(x)) = (x 6 + x 10 + x 12 )(mod g(x)) = x 2 + x 3 + x 4 + x 7
s 5 = x 5 s(x)(mod g(x)) = (x 7 + x 11 + x 13 )(mod g(x)) = 1 + x 3 + x 5 + x 6 + x 7
s 6 = x 6 s(x)(mod g(x)) = (x 8 + x 12 + x 14 )(mod g(x)) = x + 1
x + 1 имеет вес 2, поэтому для нахождения многочлена ошибок вычисляем e(x) = x 15-6 s 6 (x)(mod (1 + x n )) = x 9 (x + 1)(mod (1 + x n )) = x 10 + x 9 .
Итак, если отправленное кодовое слово имеет не более двух ошибок, то оно было таким
(x + x 2 + x 4 + x 6 + x 7 + x 8 + x 10 + x 13 ) + (x 10 + x 9 ) =
x + x 2 + x 4 + x 6 + x 7 + x 8 + x 9 + x 13
Этот многочлен соответствует вектору [011010111100010]. Чтобы восстановить само сообщение нам надо разделить кодовое слово на ПМ g(x) и получить
x + x 2 + x 4 + x 5 ,
значит сообщение было [0110110].
IV. Размерность, порождающая и проверочная матрицы
Теорема: Если ПМ g(x) кода C имеет степень n-k тогда C является (n,k)-циклическим кодом. Если g(x) = a 0 + a 1 x + a 2 x 2 + . + a n-k x n-k , то порождающая матрица кода C k x n матрица вида:
Док-во: Векторы g(x), xg(x), x 2 g(x), . x k-1 g(x) линейно -независимы. IВ противном случае существует нетривиальный набор коэффициентов такой, что
b 0 g(x) + b 1 xg(x) + b 2 x 2 g(x) + . + b k-1 x k-1 g(x) = 0,
(b 0 + b 1 x + b 2 x 2 + . + b k-1 x k-1 ) g(x) = 0.
Но степень этого произведения k — 1 + n — k = n — 1 n — 1), кроме как при всех b i = 0.
Пусть c(x) из C, тогда c(x) = b(x) g(x) и можно заключить, что b(x) имеет степень n — 1 и придется приводить к остатку по mod (x n — 1), b'(x), удовлетворяющему этому ограничению на степень ). Таким образом, c(x) может быть представлено линейной комбинацией функций вида x i g(x).
Система
Рассмотрим многочлен h(x) = (x n — 1)/g(x), где g(x) ПМ кода C. Если deg(g(x)) = n — k, то deg(h(x)) = k и он также нормированный, поэтому h(x) порождает циклический код C’ размерности n — k. Пусть c 1 (x) = a 1 (x)g(x) из C и c 2 (x) = a 2 (x)h(x) из C’. Тогда
c 1 (x) c 2 (x) = a 1 (x)g(x)a 2 (x)h(x) = a 1 (x)a 2 (x)f(x) = 0 (mod f(x)),
где f(x) = x n — 1. Поэтому, используя умножение многочленов по модулю mod f(x), произведение любого кодового многочлена из C и любого многочлена из C’ будет давать 0. Означает ли это, что C’ — дуальный к C код? К сожалению нет, поскольку построенный изоморфизм не сохраняет скалярное произведение, т.е. скалярное произведение векторов не соответствует нулевому произведению многочленов. Однако, коды C’ и C тесно связаны — они эквивалентны.
Рассмотрим два вектора:
a = (a 0 a 1 . a n-1 ) из C
и
b = (b 0 b 1 . b n-1 ) из C’,
и их произведение (вернее, соответствующих многочленов)
для каких-то c i из F. Свободный член произведения
c 0 = a 0 b 0 + a 1 b n-1 + a 2 b n-2 + . + a n-1 b 1 ,
т.к x n = 1 (mod f(x)). Теперь c 0 можно записать как скалярное произведение
где b’ вектор, полученный из b циклическим сдвигом координат b на одну позицию влево и изменением порядка записи координат (т.е. (b 0 b n-1 b n-2 . b 1 )). Заметим, что умножение многочлена [sum from
где b’ теперь вектор, связанный с x n-t b(x). По отношению к b(x), b’ это вектор, полученный циклическим сдвигом b на t+1 позиций влево с последующим изменением порядка координат на противоположный.
Примет: Пусть n = 3, и вектора a = (a 0 a 1 a 2 ) и b = (b 0 b 1 b 2 ). Перемножая их по mod x 3 — 1, получим
a(x)b(x) = (a 0 + a 1 x + a 2 x 2 )(b 0 + b 1 x + b 2 x 2 )
= (a 0 b 0 + a 1 b 2 + a 2 b 1 ) + (a 0 b 1 + a 1 b 0 + a 2 b 2 )x + (a 0 b 2 + a 1 b 1 + a 2 b 0 )x 2 .
Коэффициент при x 2 будет a (b 2 b 1 b 0 ). Этот вектор b’ получен из b сдвигом на 3 ( = 2 + 1) позиции влево (это ставит все координаты на старые места) и изменением порядка координат с последней на первую. b-вектор в коэффициенте при x получается из b сдвигом на 2 ( = 1 + 1) позиции влево, что дает (b 2 b 0 b 1 ) и изменением порядка следования (b 1 b 0 b 2 ).
Теперь поскольку a(x)b(x) = 0 mod (x n — 1), коэффициенты при всех степенях x должны равняться 0. Вышеприведенное рассуждение приводит к заключению, что ac = 0 (т.е., векторы a и c ортогональны) для c полученного любой циклической перестановкой (сдвигом) вектора, координаты которого имеют противоположный порядок следования, чем у b . Поскольку h(x) порождает код C’,
Пример: Предположим, что мы хотим построить порождающую матрицу для (7,4)- бинарного циклического кода. Поскольку g(x) = 1 + x + x 3 делит f(x) = x 7 — 1, то g(x) порождает (7,4) — циклический код C. h(x) = f(x)/g(x) = 1 + x + x 2 + x 4 порождает (7,3)-циклический код C’. Порождающая матрица для C
Порождающая матрица для C’
Перепишем колонки G’ в обратном порядке, получим порождающую матрицу для C perp (она же проверочная для исходного кода)
Нетрудно проверить, что GH T = 0.
Поскольку C’ и C perp могут быть получены простой перестановкой координат всех векторов — это эквивалентные коды. Повторим ранее данное определение,
Определение : Пусть h(x) = a 0 + a 1 x + . + a k x k многочлен степени k (a k #0). Определим обратный многочлен h R (x) для h(x) формулой
Заметим, что h R (x) = x k h(1/x), где k = deg h(x). Суммируя все вышесказанное, получим следующее.
Tеорема : Пусть g(x) — нормированный делитель f(x) = x n — 1 степени n-k, и, следовательно, ПМ для циклического (n,k)-кода C. Пусть h(x) = f(x)/g(x). Тогда h R (x) — обратный многочлен к h(x), есть ПМ кода C perp .
V. Синдромы и охота на ошибки
где deg(r i (x)) 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 3 . Алгоритм деления дает:
x 3 = (1)(x 3 + x + 1) + (1+ x)
x 4 = (x)(x 3 + x + 1) + (x + x 2 )
x 5 = (x 2 + 1)(x 3 + x + 1) + (1 + x + x 2 )
x 6 = (x 3 + x + 1)(x 3 + x + 1) + (1 + x 2 ).
Порождающая матрицаЗаметим, что строки R как раз остатки от деления.
Соответствующая проверочная матрица это H = [I n-k -R t ]. Разделение матрицы подобным образом предоставляет возможность удобной полиномиальной интерпретации синдрома вектора.
Tеорема : Пусть r(x) и s(x) есть соответствующие полиномиальные представления для вектора r и его синдрома s = H r t . Тогда s(x) — остаток от деления r(x) на g(x).
Док-во: Пусть r(x) = a 0 + a 1 x + . + a n-1 x n-1 . Заметим, что столбцы i, 0 i a столбцы j, n-k j-n+k (x), так что
где h(x) = a n-k q 0 (x) + . + a n-1 q k-1 (x). Таким образом r(x) = h(x)g(x) + s(x). Поскольку deg r i (x) n-k-1 g'(x)) n-k-1 g(x). Приходим к выводу:
Tеорема : Пусть C циклический (n,k)-код над F с ПМ g(x), и пусть r(x) имеет синдромный многочлен s(x) = s 0 + s 1 x + . + s m x m . Тогда синдромный многочлен xr(x) есть
- xs(x) если deg s(x) n-k-1 g(x), если deg s(x) = n-k-1.
Пример : Рассмотрим код предыдущего примера с ПМ g(x) = 1 + x + x 3 . Используя записанную там порождающую матрицу, мы можем получить проверочную матрицу, Получили вектор r = (1011011). Синдром r равен H r t = (001) t = s . Многочлен
r(x) = 1 + x 2 + x 3 + x 5 + x 6 .
Если разделить r(x) на g(x), то получим
r(x) = (x 3 + x 2 + x + 1)g(x) + x 2 .
Остаток, как и следовало ожидать, равен s .
А теперь найдем остаток циклического сдвига r . Положим w = (1101101), что соответствует многочлену xr(x). H w t = (110) t . В полиномиальной интерпретации этот синдром получается так. Поскольку deg s(x) = 2 = n-k-1, синдром xr(x) есть
xs(x) — 1g(x) = x 3 — (x 3 + 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 ) e* ) e = e* , поскольку смежный класс содержит не более одного вектора веса меньше или равного t.
Следовательно, в этом случае ошибка известна и равна e = ( s t ,0).
Алгоритм декодирования
- Вычислим синдром s 0 (x) of r(x) по алгоритму деления.
- Положим i = 0.
- Если wt(s i (x)) n-i (s i , 0 ), и декодируем to r(x) — e(x).
- Положим i = i + 1.
- Если i = n then stop; ошибка не исправляется.
- Если deg s i-1 (x) i (x) = xs i-1 (x); иначе s i (x) = xs i-1 (x) — g(x).
- Go to (3).
Пример: g(x) = 1 + x 2 + x 3 генерирует бинарный (7,4)-циклический код с минимальным расстоянием 3 (и следовательно 1-ошибку исправляет). Рассмотрим кодовое слово 1 + x + x 5 = (1 + x + x 2 ) g(x), пусть после передачи многочлен r(x) = 1 + x + x 5 + x 6 был получен. Декодируем его. Разделим r(x) на g(x) для нахождения синдрома,
r(x) = (x 3 + 1)g(x) + (x + x 2 ),
так s(x) = x + x 2 .Так как вес s(x) > 1 (= t), вычислим синдром s 1 (x) xr(x). Так как of s(x) = 2 = n — k — 1, умножаем s(x) на x и делим на g(x), что дает s 1 (x) = 1. Поскольку вес 1, мы получили маску ошибки
e(x) = x 7-1 (s 1 , 0 ) = x 6 (1000000) = x 6 .
Так как n = 7 все ошибки веса 1 имеют циклический сдвиг на шесть 0’s и 6 > k = 4, исправляются все единичные ошибки..
Пример : g(x) = 1 + x 4 + x 6 + x 7 + x 8 порождает бинарный (15,7)-циклический код. Если минимальное расстояние 5(так), то t = 2. Некоторые (по меньшей мере) веса 2 маски ошибок могут содержать сдвиги не менее 7 0й и могут бытьотловлены. Если мы получили
r = (1100 1110 1100 010)
r(x) = (x + x 2 + x 4 + x 5 )g(x) + (1 + x 2 + x 5 + x 7 ).
Вычисляем синдромы s i (x) для x i r(x) пока wt(s i (x)) e = x 15-7 (s 7 , 0 ) = x 8 (100001000000000) = (0000 0000 1000 010),
и мы исправляем r(x) на r — e = (1100 1110 0100 000).
Источник
