Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Циклические коды.
Циклическим кодом называется линейный n,k код, обладающий следующим свойством:
Если - вектор кода, то вектор кода.
(циклический сдвиг). Обратите внимание на нумерацию от до .
Теорема. Циклический код есть идеал в алгебре многочленов по модулю многочлена f(x)=xn+1.
mod f(x)= xn+1 циклический код.
а) Линейный код векторное подпространство векторного пространства всех последовательностей длины n.
Идеал так же векторное подпространство векторного пространства всех последовательностей длины n.
Отсюда Идеал линейный код.
б) Далее:пусть принадлежит идеалу J.
Тогда по определению идеала.
Но .
Откуда , т.е. циклический сдвиг принадлежит идеалу, ч.т.д.
Пусть - вектор кода. Тогда - вектор кода как его циклический сдвиг.
Следовательно - вектор кода, i=0,2,…,n-1.
Далее, пусть в(x) вектор из кольца многочленов по
mod f(x)= =xn+1.
Тогда
В правой части линейная комбинация векторов, т.е. вектор кода. Отсюда . Следовательно, циклический код идеал.
Задание циклического кода.
f(x)= xn+1;
степень n-k степень k
Порождающая матрица несистематического
циклического кода.
g(x) Пример:
G= xg(x) ;
……. g(x) h(x)
xk-1g(x)
1 0 1 1 0 0 0
G= ; G= 0 1 0 1 1 0 0 ; ),
0 0 1 0 1 1 0
0 0 0 1 0 1 1
Проверочная матрица.
h(x) Для условий примера:
H= xh(x) ;
…….
xn-k-1h(x)
0 0 1 1 1 0 1
H= ; H= 0 1 1 1 0 1 0
1 1 1 0 1 0 0 7,4 код
Хэмминга
c dmin=3
Задание несистематического
циклического кода многочленом g(x).
Вектор кода V(x);
Выводы:
Пример:
a(x)=x
0 1 0 0
0 1 0 1 1 0 0
Получение порождающей матрицы
систематического циклического n,k кода.
степень n-k степень k
К равенств
………………………………………………………….
i=0,1,…,k-1
k векторов. Степень r(x) меньше n-k.
Поэтому: вектора
i=0,1,…,k-1
- линейно независимые (К векторов)
Так как , т.е. делится на g(x), то
- вектор кода
i=0,1,…,k-1.
K линейно независимых векторов кода его базис. Отсюда порождающая матрица:
Здесь
G= -
…………………………….. остаток от
деления
……………………………. на g(x);
i=0,1,…,k-1.
Пример:
1
3
1
2
4
x+1
G= 1 0 1 1 0 0 0 ;
1 1 1 0 1 0 0
1 1 0 0 0 1 0
0 1 1 0 0 0 1
P Jk
Получение алгоритма задания систематического
циклического кода.
.
В соответствии с алгоритмом Евклида R(x) остаток от деления на g(x);
V(x)=g(x)d(x);
что такое R(x)-???
Степень R(x) меньше степени n-k;
Алгоритм задания систематического
циклического кода.
так как степень R(x) меньше степени g(x) степень n-k, то это сложение просто приписывается.
Пример:
0 1 0 1 a(x)=x+x3
2
1
Делим на g(x):
V(x)=a(x)x3+R(x)=x6+x4+1
1 = R(x)
1 0 0 0 1 0 1
проверочные информационные