Изучение циклического кода C(11,6) над Z3

    Рассматривается циклический код, порожденный многочленом g(x). Это делитель многочлена x^11-1 над полем Z3. Задача заведомо громоздкая и тудоемкая, но хорошо демонстрирующая все положения теории в работе. Расчеты были проведены с помощью пакета MapleV, а вам все придется делать вручную! 

> g(x):=x^5-x^3+x^2-x-1;

    Порождающая матрица данного кода, построенная по известной формуле.

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

> G:=matrix_modp(G,3);

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

> H:=check_matrix(x^5-x^3+x^2-x-1,11,3);

Умножая матрицы G и H в арифметике по модулю 3, получаем нулевую матрицу.

Проверочный многочлен h(x)=(x^11-1)/g(x) 

> Expand( g(x)*h(x) ) mod 3;

Умножив на g(x), получаем    x^11-1

Далее приводится список кодовых слов в векторном виде, он очень длинный и оставлен только фрагмент. Вектор наименьшего веса (5) не равный нулевому позволяет определить число исправляемых ошибок - 2.

> C:=code_list(G,3):
C:=sort(C,weight_order);

.............................................................................................................................................

Вам надо будет привести весь код (он будет гораздо малочисленнее!)

    Заметим, что матричные вычисления фактически дают коэффициенты кодовых многочленов. 

    Можно для данного кода ввести и другую процедуру кодирования, получив систематический код.

G матрица для систематического кода. Последние символы будут информационными.

> for i from 0 to 5 do for j from 0 to 10 do Gs[i+1,j+1]:=coeff(a[i],x,j) od:od:

> evalm(Gs);

>

> matrix_modp(multiply(Gs,transpose(H)),3);

> R:=delcols(Gs,6..11);

Проверочная матрица в систематическом виде.

> Hs:=augment(band([1],5),-transpose(R));

Кодирование/декодирование. Берем сообщение в полиномиальном виде

> m(x):=1+x+x^2+x^5;

Вектор

> u:=[0,0,0,0,0,0]:for i from 0 to 5 do u[i+1]:=coeff(m(x),x,i) od;

> multiply(u,G);

> v:=matrix_times_vector_modp(transpose(G),u,3);

кодовое слово как вектор.

Кодируем многочленом g(x) и получаем многочлен.

> c(x):=Expand( m(x)*g(x) ) mod 3;

Кодирование систематическое

> u;multiply(u,Gs);vs:=matrix_times_vector_modp(transpose(Gs),u,3);

сообщение

кодовое слово

Портим кодовые слова, добавив во второй и шестой разряды по единичке.

> r(x):=c(x)+x+x^5 mod 3;

полученный многочлен с ошибкой.

полученный систематический вектор

то же несистематический вектор

Проверка полиномная

> min_distance(Gs,3);

> min_distance(G,3);

Expand( r(x)*h(x) ) mod 3;

коэффициенты посчитаны в арифметике Z3 . Еще надо учесть то, что мы
 работаем по mod x^11-1, поэтому найдем остаток от деления

Есть ошибка!

# 
# Декодирование с использованием циклического свойства синдромов
# 

Смотри теорему из лекции. В теореме доказано, что синдром сдвинутого слова совпадает с остатком сдвинутого синдрома. Это дает возможности "двигая" циклически слово (вернее его синдром) загнать ошибочные разряды влево, получив многочлен ошибок наименьшей степени. А после "прокрутить" обратно и исправить ошибку.
     Получим синдром как остаток от деления принятого многочлена на проверочный и
 "сдвинутые" синдромы. Сдвинутый в смысле правого циклического сдвига.

  s(x):=modpol(r(x),g(x),x,3);s1(x):=modpol(x*s(x),g(x),x,3);s2(x):=modpol(x^2*s(x),g(x),x,3);s3(x):=modpol(x^3*s(x),g(x),x,3);s4(x):=modpol(x^4*s(x),g(x),x,3);s5(x):=modpol(x^5*s(x),g(x),x,3);s6(x):=modpol(x^6*s(x),g(x),x,3);s7(x):=modpol(x^7*s(x),g(x),x,3);s8(x):=modpol(x^8*s(x),g(x),x,3);s9(x):=modpol(x^9*s(x),g(x),x,3);s10(x):=modpol(x^(10)*s(x),g(x),x,3);

Получили ошибку веса 2, которая исправляется, Теперь все надо
"открутить" обратно (11-10) позиций! Т.е. многочлен ошибок будет 

> e(x):=Expand(x^(11-10)*s10(x)) mod 3;

Исправленный многочлен r(x)-e(x)=c(x), остается разделить на g(x) и получить сообщение.

> divide(r(x)-e(x),g(x)) mod 3;

# 
# Можно для интереса сравнить полученное с синдромом сдвинутого многочлена и с синдромами всех
# сдвинутых ошибок.
# Вот они:

> sr1(x):=modpol(x*r(x),g(x),x,3);

> se(x):=modpol(x+x^5,g(x),x,3);se1(x):=modpol(x*(x+x^5),g(x),x,3);se2(x):=modpol(x^2*(x+x^5),g(x),x,3);se3(x):=modpol(x^3*(x+x^5),g(x),x,3);se4(x):=modpol(x^4*(x+x^5),g(x),x,3);se5(x):=modpol(x^5*(x+x^5),g(x),x,3);se6(x):=modpol(x^6*(x+x^5),g(x),x,3);se7(x):=modpol(x^7*(x+x^5),g(x),x,3);se8(x):=modpol(x^8*(x+x^5),g(x),x,3);se9(x):=modpol(x^9*(x+x^5),g(x),x,3);se10(x):=modpol(x^(10)*(x+x^5),g(x),x,3);

Как видите, синдромы, естественно совпадают.

# Декодирование по таблице лидеров и синдромов

    Синдромы считаем матричные, только перебирать таблицу лидеров и синдромов
в нашем случае будет тяжеловато! Эта процедура программируется, но все равно занимает много
 времени.

Несистематическая матрица

> matrix_times_vector_modp(H,vr,3);

синдром полученного слова

> matrix_times_vector_modp(H,[0,1,0,0,0,1,0,0,0,0,0],3);

синдром лидера - ошибки

Систематическая матрица

> matrix_times_vector_modp(Hs,vsr,3);

синдром полученного слова

> matrix_times_vector_modp(Hs,[0,1,0,0,0,1,0,0,0,0,0],3);

синдром ошибки

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

Для систематического кода есть и другой способ. Последние 6 разрадов информационные. Сравниваем проверочные разряды принятые и вычисленные по полученным информационным. Если совпадает - ошибки нет, иначе ошибка! Итак

отправлен вектор

> u;

> vs;

систематический код

> vsr;

"испорченное" слово

Пересчитываем проверочные символы так же, как мы это делали первоначально. Поскольку ошибка именно в проверочных символах, то результат совпадает с отправленным.

> u;multiply(u,Gs);vs:=matrix_times_vector_modp(transpose(Gs),u,3);

> vs-vsr;

разность полученного и пересчитанного слова.

Отличие во втором и шестом разрядах! Как и должно быть. Можно исправить ошибку и взять информационные разряды.

Теперь мы испортим один информационный разряд. Вектор ошибок

> e1:=[1,0,0,0,0,0,0,2,0,0,0];

> vs;vse:=v+e1;

> vse := [0, 1, 2, 2, 0, 2, 0, 1, 2, 0, 1];

испорченное систематическое слово

> u1:=[2, 0, 1, 2, 0, 1]; информационые разряды

> u1;multiply(u1,Gs);vs:=matrix_times_vector_modp(transpose(Gs),u1,3);

вычисляем по ним проверочные и находим разность

> ve;ve-vs;

matrix_times_vector_modp(Hs,ve,3);синдром полученного слова

matrix_times_vector_modp(Hs,e1,3);

синдром ошибки по таблице. Исправляем и декодируем.

>Можно и здесь использовать циклическое свойство синдромов. s(x):=2*x+x^3+x^4;s1(x):=modpol(x*s(x),g(x),x,3);s2(x):=modpol(x^2*s(x),g(x),x,3);s3(x):=modpol(x^3*s(x),g(x),x,3);s4(x):=modpol(x^4*s(x),g(x),x,3);s5(x):=modpol(x^5*s(x),g(x),x,3);s6(x):=modpol(x^6*s(x),g(x),x,3);s7(x):=modpol(x^7*s(x),g(x),x,3);s8(x):=modpol(x^8*s(x),g(x),x,3);s9(x):=modpol(x^9*s(x),g(x),x,3);s10(x):=modpol(x^(10)*s(x),g(x),x,3);

Сдвигаем обратно s4(x) := x^4+2; на 11-4=7 позиций и получаем нашу ошибку e(x)=1+2x^7.

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