Полиномиальные коды

1. Полиномиальные коды

2.

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

3.

• Сообщение
• Многочлен
a (a0 , a1 ,..., an 1 )
a ( x) a0 a1 x ... an 1 x n 1
• Все вычисления проводятся по модулю 2
10011
1 x x
3
4

4.

• Зафиксируем некоторый многочлен
степени k g ( x) g g x ... g x k
0
1
k
g 0 0, g k 0
• Полиномиальный код с образующим
(кодирующим) многочленом g(x),
кодирует слово сообщения а
многочленом b(x)=a(x)g(x) или кодовым
словом из коэффициентов многочлена
b(x)

5.

• Коэффициенты образующего
многочлена g ( x) g 0 g1 x ... g k x k
образуют кодовое слово
Причем среди всех кодовых многочленов
образующий многочлен имеет
наименьшую степень и g 0 0, g k 0
Степень кодирующего полинома
определяет количество проверочных
символов кода.

6.

g ( x) 1 x 2 x 3
Кодирующий многочлен
3
4
Сообщение
01011 x x x
Будет закодировано коэффициентами
многочлена
b( x) a( x) g ( x) x x 5 x 7
01011 01000101
Количество информационных символов 5,
проверочных -- 3

7.

• Полиномиальный код с кодирующим многочленом
g(x) степени k является матричным кодом с
порождающей матрицей размерности n x (n+k)
• Степень кодирующего полинома – количество
проверочных символов
g0
0
G 0
...
0
g1
g0
0
...
0
g2
g1
g0
...
0
... g k
... g k 1
... g k 2
... ...
... ...
0
gk
g k 1
...
...
0
0
gk
...
...
... 0
... 0
... 0
... ...
... g k

8.

• (6,3)-код с кодирующим многочленом
g ( x) 1 x x 3
1 1 0 1 0 0
G 0 1 1 0 1 0
0 0 1 1 0 1

9.

Блок n=3
000
001
010
011
100
101
110
111
Код
000000
001101
011010
010111
110100
111001
101110
100011
m=6

10. Утверждение

• Имеется (m,n)-код с кодирующим
многочленом g(x)
• После передачи закодированного
сообщения строка ошибок e (e0 , e1 ,..., en 1 )
останется необнаруженной в том и
только в том случае, если многочлен
e(x) делится на g(x)

11.

• Действительно, a(x)g(x)+e(x) делится на
g(x) тогда и только тогда, когда e(x)
делится на g(x)
• Поэтому любая ошибка, многочлен
которой не делится на g(x), будет
обнаружена.
• Ошибка, многочлен которой делится на
g(x), не будет обнаружена

12.

• v(x)=a(x)g(x)+e(x)=
• =a(x)g(x)+e1(x)g(x)+e2(x)=
• =A(x)g(x)+e2(x)
• A(x)=a(x)+e1(x) неправильное исходное
сообщение
• Исправление a(x)=A(x)+e1(x)

13.

• Таким образом, обнаружение ошибки
при использовании полиномиального
кода с кодирующим многочленом g(x)
может быть реализовано как деление
многочленов с остатком.
• Если остаток ненулевой, то при
передаче произошло искажение данных

14.

• (6,3)-код с кодирующим многочленом
g ( x) 1 x x 3
• Получено сообщение 011011

15.

• 011011 ⇒
x x 2 x 4 x5
• Поделим на кодирующий многочлен
x5 x 4 x 2 x x3 x 1
x5 x3 x 2 x 2 x 1
x 4 x3 x
x4 x2 x
• частное
x3 x 2
x3 x 1
x2 x 1
• остаток

16. таблица синдромов

ошибка
многочлен
Остаток от
деления на g(x)
частноекорректор
100000
1
1
0
010000
x
x
0
001000
x2
x2
0
000100
x3
x+1
1
000010
x4
x2+x
x
000001
x5
x2+x+1
x2+1

17.

• Остаток x2+x+1 соответствует вектору
ошибок 000001 и частному (корректору)
x2+1
• Корректируем искаженное сообщение
• 111+101=010
• частное+корректор

18. Проверка

• исправленное кодовое слово
• 011011+000001=011010
x 4 x 2 x x3 x 1
x
x4 x2 x
0
• исправленное исходное сообщение
• 010

19.

• Код Хэмминга является
полиномиальным
• (7,4)-код с кодирующим полиномом
x x 1
3
2

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

21.

• Циклическим кодом называется
линейный код, который для каждого
кодового слова содержит все
циклические сдвиги этого слова

22. Код Хэмминга

0000
0001
0010
0011
0100
0101
0110
0111
код
0000000
1000101
0001011
1001110
1010011
0010110
1011000
0011101
1000
1001
1010
1011
1100
1101
1110
1111
код
1100010
0100111
1101001
0101100
0110001
1110100
0111010
1111111

23.

• Циклический сдвиг наборов
соответствует умножению кодового
многочлена на х и вычитанию
слагаемого со степенью m
c( x) c0 c1 x ... cm 1 x
m 1
c (c0 , c1 ,..., cm 1 ) c (cm 1 , c0 , c1 ,..., cm 2 )
m
c ( x) c( x) x cm 1 ( x 1)

24.

• Если считать, что
• то
x 1
m
c ( x) c( x) x
• Тогда порождающий многочлен g(x) является
m
делителем
( x 1)
• Любой кодовый многочлен можно
представить как произведение образующего
многочлена на некоторый многочлен

25.

• Пусть задан порождающий многочлен
g ( x) g 0 g1 x ... g k x
k
• Все произведения являются кодовыми
многочленами степени не выше m-1
g ( x), xg( x), x 2 g ( x),..., x m k 1 g ( x)

26.

Кроме того, все линейные комбинации
этих многочленов также являются
кодовыми. Таким образом, циклический
код имеет порождающую матрицу
g0
0
G 0
...
0
g1
g0
0
...
0
g2
g1
g0
...
0
... g k
... g k 1
... g k 2
... ...
... ...
0
gk
g k 1
...
...
0
0
gk
...
...
... 0
... 0
... 0
... ...
... g k

27.

• Проверочный многочлен h(x) –
многочлен, для которого верно
x 1 h( x ) g ( x )
m

28.

• Проверочная матрица циклического
кода
0
0
H ...
0
h
m k
0
0
...
hm k
...
0
0
...
...
h1
...
0
... hm k
... ...
... ...
h0
0
hm k
...
...
...
...
...
h1
...
...
...
h1 h0
h0 0
... ...
... ...
0 0

29. Пример

• Двоичный циклический код длины m=7 с
порождающим многочленом
2
3
g ( x) 1 x x (1011000)
1
0
G
0
0
0
1
0
0
1
0
1
0
1
1
0
1
0
1
1
0
0
0
1
1
0
0
0
1

30. Проверочная матрица

• Найдем проверочный многочлен
x 1
x3 x 2 1
x7 x6 x 4 x 4 x3 x 2 1
7
x x 1
x6 x5 x3
6
4
x5 x 4 x3 1
x5 x 4 x 2
x3 x 2 1
x3 x 2 1
x 1 h( x)( x x 1)
7
3
2
h( x) x x x 1
4
3
2

31. Проверочная матрица

• m=7, k=3, h=(10111)
0 0 1 0 1 1 1
H 0 1 0 1 1 1 0
1 0 1 1 1 0 0

32. Несистематическое кодирование

• m=7, k=3 а=(1001)
g ( x) 1 x 2 x 3 (1011000)
c( x) a( x) g ( x) (1 x 3 )(1 x 2 x 3 )
1 x 2 x3 x3 x5 x6 1 x 2 x5 x6
c (1010011)

33. Несистематическое декодирование

• Получено сообщение v=c+e
• Если v(x) делится без остатка на
образующий многочлен g(x), то
сообщение передано без ошибок
• Если остаток ненулевой, то произошла
ошибка

34. Образующий многочлен выбирается так, чтобы остатки были все различны

многочлен
Остаток ri(x) от
Ошибка
частное
деления на g(x)
в i разряде
1000000
1
1
0
0100000
x
x
0
0010000
x2
x2
0
0001000
x3
x2+1
1
0000100
x4
x2+x+1
x+1
0000010
x5
x+1
x2 +x+1
0000001
x6
x2+x
x3 +x2 +x

35.

x mod g ( x) x( x mod g ( x))
4
3
[ x( x 1)] mod g ( x) x 1 x
2
2
ri ( x) ri 1 ( x) ri 3 ( x)

36. Декодирование

• Сообщение v=(1101011)
v( x) 1 x x 3 x 5 x 6
• Просуммируем остатки 1, x, x2+1, x+1,
x2+x
• Ненулевой результат x+1

37.

• Частное от деления на образующий
многочлен x3 =(0001)
• частное-корректор x2 +x+1=(1110),
ошибка в 6 разряде
• Декодированное сообщение (1111)

38.

Проверка
• Исправленное кодовое слово
v+е=(1101011)+(0000010)=(1101001)
• Делим на кодирующий многочлен
x6 x3 x 1 x3 x 2 1
x6 x5 x3 x3 x 2 x 1
x5 x 1
x5 x 4 x 2
x4 x2 x 1
x 4 x3 x
x3 x 2 1
0
• Декодированное
сообщение (1111)

39. Систематическое кодирование

• При систематическом кодировании
исходное сообщение входит в кодовое
слово в неизменном виде с
дополнительными проверочными
символами

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

• m=7, k=3 а=(1001)
g ( x) 1 x 2 x 3 (1011000)
• при систематическом кодировании
кодовое слово состоит из двух блоков
c( x) p ( x) a ( x) x 3
проверочные
информационные
c( x) ( p( x) a( x) x ) mod g ( x) 0
3
p( x) a( x) x3 mod g ( x)

41.

• Найдем проверочный блок (3 символа)
a( x) x3 (0001001)
x6 x3
x3 x 2 1
p( x) x 1
x6 x5 x3 x3 x 2 x 1
(110)
x5
x5 x 4 x 2
x4 x2
x 4 x3 x
x3 x 2 x
x3 x 2 1
x 1
• Кодовое слово для
(1001) ⇒(1101001)

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

• Получено сообщение v=c+e
• Если v(x) делится без остатка на
образующий многочлен g(x), то
сообщение передано без ошибок
• Если остаток ненулевой, то произошла
ошибка

43.

• Получено сообщение v=(1101011)
Делим на образующий многочлен
x6 x5 x3 x 1 x3 x 2 1
x3
x6 x5 x3
x 1
• Остаток x+1 соответствует ошибке
e=(0000010)
Корректируем
(0111011)+(0000010)=(0111001)
Информационные символы 1001