|
Читайте также: |
Сейчас мы рассмотрим, как идеи, которые первоначально обсуждались применительно к линейным кодам, будут интерпретироваться при полиномиальном описании циклических кодов.
Теорема: Если ПМ g(x) кода C имеет степень n-k тогда C является (n,k)-циклическим кодом. Если g(x) = a0 + a1x + a2x2 +... + an-k xn-k, то порождающая матрица кода C k x n матрица вида:
Док-во: Векторы g(x), xg(x), x2g(x),..., xk-1g(x) линейно -независимы. IВ противном случае существует нетривиальный набор коэффициентов {bi} такой, что
b0g(x) + b1xg(x) + b2 x2 g(x) +... + bk-1 xk-1 g(x) = 0,
(b0 + b1x + b2x2 +... + bk-1 xk-1) g(x) = 0.
Но степень этого произведения k - 1 + n - k = n - 1 < n, поэтому оно не может быть тождественно = 0 mod (xn - 1), кроме как при всех bi = 0.
Пусть c(x) из C, тогда c(x) = b(x) g(x) и можно заключить, что b(x) имеет степень <= k - 1 (иначе произведение будет иметь степень > n - 1 и придется приводить к остатку по mod (xn - 1), b'(x), удовлетворяющему этому ограничению на степень). Таким образом, c(x) может быть представлено линейной комбинацией функций вида xi g(x).
Система {xi g(x) }, 0 <= i <= k - 1 является базисом C, а, следовательно, размерность кода k.
Получив полиномиальную интерпретацию циклического кода C, мы рассмотрим соответствующую интерпретацию дуального к C кода Cperp. Покажем, что дуальный циклическому коду C код Cperp также циклический.
Рассмотрим многочлен h(x) = (xn - 1)/g(x), где g(x) ПМ кода C. Если deg(g(x)) = n - k, то deg(h(x)) = k и он также нормированный, поэтому h(x) порождает циклический код C' размерности n - k. Пусть c1(x) = a1(x)g(x) из C и c2(x) = a2(x)h(x) из C'. Тогда
c1(x) c2(x) = a1(x)g(x)a2(x)h(x) = a1(x)a2(x)f(x) = 0 (mod f(x)),
где f(x) = xn - 1. Поэтому, используя умножение многочленов по модулю mod f(x), произведение любого кодового многочлена из C и любого многочлена из C' будет давать 0. Означает ли это, что C' -- дуальный к C код? К сожалению нет, поскольку построенный изоморфизм не сохраняет скалярное произведение, т.е. скалярное произведение векторов не соответствует нулевому произведению многочленов. Однако, коды C' и C тесно связаны - они эквивалентны.
Рассмотрим два вектора:
a = (a0 a1... an-1) из C
и
b = (b0 b1... bn-1) из C',
и их произведение (вернее, соответствующих многочленов)
для каких-то ci из F. Свободный член произведения
c0 = a0 b0 + a1bn-1 + a2 bn-2 +... + an-1 b1,
т.к xn = 1 (mod f(x)). Теперь c0 можно записать как скалярное произведение
c0 = a b'
где b' вектор, полученный из b циклическим сдвигом координат b на одну позицию влево и изменением порядка записи координат (т.е. (b0 bn-1 bn-2... b1)). Заметим, что умножение многочлена [sum from {i=0} to {n-1} ci xi] на xn-tприводит к тому, что ct становится свободным членом, а значит ct -- свободный член a(x)(xn-t b(x)). Поэтому,
ct = a b'
где b' теперь вектор, связанный с xn-t b(x). По отношению к b(x), b' это вектор, полученный циклическим сдвигом b на t+1 позиций влево с последующим изменением порядка координат на противоположный.
Примет: Пусть n = 3, и вектора a = (a0 a1 a2) и b = (b0 b1 b2). Перемножая их по mod x3 - 1, получим
a(x)b(x) = (a0 + a1x + a2 x2)(b0 + b1x + b2 x2)
= (a0 b0 + a1b2 + a2 b1) + (a0 b1 + a1 b0 + a2 b2)x + (a0 b2 + a1 b1 + a2 b0)x2.
Коэффициент при x2 будет a (b2 b1 b0). Этот вектор b' получен из b сдвигом на 3 (= 2 + 1) позиции влево (это ставит все координаты на старые места) и изменением порядка координат с последней на первую. b-вектор в коэффициенте при x получается из b сдвигом на 2 (= 1 + 1) позиции влево, что дает (b2 b0 b1) и изменением порядка следования (b1 b0 b2).
Теперь поскольку a(x)b(x) = 0 mod (xn - 1), коэффициенты при всех степенях x должны равняться 0. Вышеприведенное рассуждение приводит к заключению, что ac = 0 (т.е., векторы a и c ортогональны) для c полученного любой циклической перестановкой (сдвигом) вектора, координаты которого имеют противоположный порядок следования, чем у b. Поскольку h(x) порождает код C', {h(x), xh(x),..., xn-k-1h(x) } это базис для C' и G' = [h(x), xh(x),..., xn-k-1h(x)]t -- порождающая матрица для C'. Теперь G' порождает код C' той же размерности n - k, что и C. Более того, взяв в качестве b(x) сам h(x), мы видим, что обратнопереставленный любой вектор из C' ортогонален любому вектору из C. Это означает, что переставив в обратном порядке колонки G', мы получим матрицу H, которая порождает код Cperp, а значит является проверочной для C.
Пример: Предположим, что мы хотим построить порождающую матрицу для (7,4)- бинарного циклического кода. Поскольку g(x) = 1 + x + x3 делит f(x) = x7 - 1, то g(x) порождает (7,4) - циклический код C. h(x) = f(x)/g(x) = 1 + x + x2+ x4 порождает (7,3)-циклический код C'. Порождающая матрица для C
Порождающая матрица для C'
Перепишем колонки G' в обратном порядке, получим порождающую матрицу для Cperp (она же проверочная для исходного кода)
Нетрудно проверить, что GHT = 0.
Поскольку C' и Cperp могут быть получены простой перестановкой координат всех векторов - это эквивалентные коды. Повторим ранее данное определение,
Определение: Пусть h(x) = a0 + a1 x +... + ak xk многочлен степени k (ak#0). Определим обратный многочлен hR (x) для h(x) формулой
Заметим, что hR(x) = xk h(1/x), где k = deg h(x). Суммируя все вышесказанное, получим следующее.
Tеорема: Пусть g(x) -- нормированный делитель f(x) = xn - 1 степени n-k, и, следовательно, ПМ для циклического (n,k)-кода C. Пусть h(x) = f(x)/g(x). Тогда hR(x) -- обратный многочлен к h(x), есть ПМ кода Cperp.
Дата добавления: 2015-07-16; просмотров: 92 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Пример 4 (прод.) | | | V. Синдромы и охота на ошибки |