Помехоустойчивое кодирование. Циклические коды

Помехоустойчивое
кодирование
Циклические коды – подкласс
линейных кодов
Примеры использования
линейных кодов
• Пример 1. Протокол передачи данных по
телефонному каналу ISDN-D, в котором
используется формат передачи данных
LAPD.
1
2 1(2)
F
A
C
max 260
I
2
1
FCS
F
Примеры использования
линейных кодов
• F=01111110 (flag)
• А – поле адреса (address)
• С поле команд (control)
• I –информационное поле (information)
• FCS – проверочные разряды (frame check sequence)
• Общая длина 266х8=21128 бит, проверочных – 16 бит
•
F
1
A
C
2 1(2)
I
max 260
FCS F
2
1
Примеры использования
линейных кодов
• Пример 2. Протокол передачи данных в 802.3
CSMA/CD для передачи данных в локальных сетях
связи (LAN)
Преамбула
Разделитель
Адрес получателя
Адрес источника
Данные
Контроль четности
7
1
2(6)
2(6)
65-1518
4
Линейные циклические коды
Циклические коды интенсивно изучаются, так как:
•
Циклические коды обладают богатой алгебраической
структурой, что используется в различных
приложениях.
• Для циклических кодов чрезвычайно кратко
формулируются технические требования
(спецификации).
•
Циклические коды легко реализуются с помощью
сдвиговых регистров.
• Многие практически важные коды являются
циклическими.
Линейные циклические коды
Линейный (n,k)-код С называется циклическим, если
циклический сдвиг любого кодового слова из С также
принадлежит С:
 x0 


x1


   ... 


 xn2 
x 
 n 1 
 
(1 )
 x n 1 


x0


  ... 


 xn3 
x 
 n2 
Замечание
• Для задания произвольного кода из 2k
слов длины n необходимо выписать
все 2k кодовых слов длины n.
• Для задания линейного кода из 2k слов
длины n достаточно выписать k
базисных слов длины n (порождающая
матрица).
• Для задания линейного циклического
кода из 2k слов длины n достаточно
выписать одно ненулевое кодовое
слово.
Реализация циклического сдвига
Циклический сдвиг реализуется с помощью
регистра сдвига длины n с обратной
связью:
x 0 x1
x2
…
x n  2 x n 1
Реализация циклического сдвига
Регистр сдвига на такте 1
x n 1 x 0
x1
…
xn 3 xn  2
Регистр сдвига на такте 2
x n  2 x n 1 x 0
…
x n  4 xn 3
Представление кодовых слов в
виде кодовых многочленов
 a0 


a1


n 1
   ...   a ( x )  a 0  a1 x  ...  a n 1 x


a
 n2 
a 
 n 1 
Представление кодовых слов
в виде многочленов
Циклический сдвиг многочлена
a ( x )  a 0  a1 x  ...  a n 1 x
a
(1 )
( x )  a n 1  a 0 x  ...  a n  3 x
 a 0 x  ...  a n  3 x
n2
 an2 x
n 1
n2
n 1
 an2 x
n 1

 a n 1 x (mod x  1) 
n
 x  a ( x )(mod x  1)
n
n
Пример
a( x)  1  x  x ,
3
 1101000
n7
Пример
(1  x  x ) a ( x )  (1  x  x )( 1  x  x ) 
4
4
1101000

0110100

1000110

0011010  x  x  x
2
3
5
3
Пример
(1  x  x ) a ( x )  (1  x  x )(1  x  x ) 
4
4
3
 1 x  x  x  x  x  x  x  x 
4
2
5
3
4
1 x  x  x  x 
2
3
5
7
 x  x  x mod( x  1)
2
3
5
7
7
Циклический сдвиг многочлена

(i)
 a ni 


a n  i 1


i
n
  ...   x  a ( x )(mod x  1)


a ni2 
a

 n  i 1 
Важные теоремы
• Теорема 1. Циклический код содержит
единственный кодовый многочлен
минимальной степени.
• Теорема 2.Если g ( x ) – кодовый многочлен
минимальной степени, то его младший
коэффициент g  1 .
• Теорема 3.Пусть g ( x )-кодовый многочлен
минимальной степени. Многочлен a ( x )
является кодовым многочленом тогда и
g ( x ).
только тогда, когда он кратен
0
Порождающий многочлен
Пусть g ( x ) -кодовый многочлен минимальной степени,
этот многочлен называется порождающим
многочленом. Пусть степень порождающего
многочлена равна r.
Базис подпространства С (порождающая матрица):
g ( x ), x  g ( x ), x
2
 g ( x ) ,..., x
k 1
 g ( x )
Степень порождающего многочлена
deg g ( x )  n  k
Теоремы о порождающем многочлене
• Теорема1.Порождающий многочлен
циклического кода g ( x ) делит без остатка
многочлен x  1 . .
• Теорема 2.Если некоторый многочлен g ( x ) степени n-k делит многочлен x  1 без
остатка, то g ( x ). порождает циклический
(n,k)-код.
n
n
Кодирование
• Кодирование циклического кода –
умножение информационного
многочлена на порождающий
многочлен
Циклический (7,4)-код
• Пример.
• (разложение
g ( x)  1  x  x
3
x  1  ( x  1)(1  x  x )(1  x  x )
7
3
2
3
)
инф.сл.
кодовое сл.
0000
0000000
1000
1101000
0100
0110100
1100
•
1011100
0010
0011010
1010
1110010
0110
0101110
1110
1000110
0001
0001101
многочлен
0  g (x)
1  g(x)
x  g(x)
(1  x )  g ( x )
2
x  g(x)
2
(1  x )  g ( x )
2
( x  x )  g ( x)
2
(1  x  x )  g ( x )
3
x  g(x)
1001
0101
1101
0011
1011
0111
1111
Заполните самостоятельно
Циклический (7,4)-код
• Минимальный вес (7,4)-кода равен 3,
код исправляет 1 ошибку
• Это циклический код Хэмминга
Замечания (1)
•По сравнению с линейными,
циклические коды редки. Например,
существует 11 811 линейных
двоичных (7,3)-кодов, но только два
из них являются циклическими.
Замечания (2)
•Тривиальные двоичные циклические коды.
•Код без информации – код из нулевого слова.
•Код с повторением – код состоящий из двух
слов: 00…0 и 11…1.
• Код с проверкой на четность – код из слов
четного веса.
•Код без проверки – код из всех слов длины n.
•В некоторых случаях (например n = 19), не
существуют циклические коды, кроме
описанных выше четырех кодов.
Порождающая матрица
циклического кода
G
Т
kn
1

0
 0



0
g1
g2
...
g n  k 1
1
0
0
...
1
g1
...
g nk 2
g n  k 1
1
0
...
0
1
...
...
...
g n  k 1
1
...








...
...
0
1
g1
g2
...
g n  k 1
0

0


0

1
Проверочный многочлен
циклического кода
• Так как порождающий многочлен циклического
кода g ( x ) делит без остатка многочлен x n  1,
то
x  1  h( x)  g ( x)
n
• Многочлен h(x) – проверочный многочлен
Проверочная матрица
циклического кода
• Всякое кодовое слово можно представить
как c ( x )  a ( x )  g ( x ), deg a ( x )  k  1
• Тогда
c( x)  h( x)  a( x)  g ( x)  h( x) 
 a ( x )  (1  x ) 
n
 a( x)  a( x)  x
n
• поэтому deg c ( x )  h ( x )  k  1
Проверочная матрица
циклического кода
• Поэтому коэффициенты при степенях x
старше k-1 равны 0.
• Тогда
c 0  h k  c1  h k 1  ...  c k  h 0  0
c1  h k  c 2  h k 1  ...  c k  1  h 0  0
c 2  h k  c 3  h k 1  ...  c k  2  h 0  0

c n  k 1  h k  c n  k  h k 1  ...  c n 1  h 0  0
Проверочная матрица
циклического кода
H
( n  k ) n
 hk

 0
 0

 

 0
h k 1
hk  2
...
h1
h0
0
0
...
hk
h k 1
...
h2
h1
h0
0
...
0
hk
...
...
...
h1
h0
...








...
...
0
hk
h k 1
hk  2
...
h1
0 

0 
 

0 

h0 
Порождающий многочлен
дуального кода
h

 x   hk
 h k 1 x  ...  h 0 x
1
h ( x)  x  h( x )
*
k
k
Параметры циклического кода
Хэмминга
n  2 1
• Длина кода
• Число информационных символов
m
k  n  m  2 1 m
m
• Минимальное расстояние - 3
• Число исправляемых ошибок - 1