Линейные коды. Коды Рида - Маллера

1. Линейные коды

Коды Рида-Маллера

2. Задание булевых функций с помощью таблиц

x1 x2
f ( x1 , x2 )
0
0
0
0
1
1
1
0
0
1
1
1
0
1
f ( x1 , x2 )
0
1

3. Задание булевых функций с помощью формул Определение

• ДНФ
• КНФ
• Полином Жегалгина (полином РидаМаллера)

4. Степень булевой функции

степень коньюнкции
число сомножителей :
deg xi1 xi2 ... xik k

5. Степень булевой функции

степень булевой функции :
deg f ( x1 , x2 ,... xn )
наибольшая из степеней конъюнкций ,
входящих в полином Жегалкина
(полином Рида Маллера )

6. Пример

степень коньюнкции
deg x1 x3 x4 3
степень функции
f ( x1 , x2 ,... xn ) x1 x1 x2 x2 x3
равна 2

7. Покомпонентное произведение кодовых слов

(a0 , a1 ,..., an 1 )
T
и
(b0 , b1 ,..., bn 1 )
(a0b0 , a1b1 ,..., an 1bn 1 )
T
T

8. Пример покомпонентного произведения

(01110101)
T
и (11011011)
(01010001)
T
T

9. Определение

• Код Рида-Маллера порядка r (РМ-r –
код) – это множество булевых
функций степени не выше r.

10. Пример кодов длины 4

• Всего 16 функций:
степени 1 : x1 , x2 , 1 x1 , 1 x2 , x1 x2 , 1 x1 x2
0 0 1 1 0 1
0 1 1 0 1 0
1 , 0 , 0 , 1 , 1 , 0
1 1 0 0 0 1
степени 2 : x1 x1 , 1 x1 x1 , x1 x1 x1 ...
0 1 0 0 1 1 0 1
0 1 0 1 1 0 1 0
0 , 1 , 1 , 0 , 0 , 1 , 1 , 0
1 0 0 0 1 1 1 0
0 1
0 1
степени 0 : 0,1 ,
0 1
0 1

11. Пример кодов длины 4

0 1
• Всего 16 функций:
0 1
РМ 0 код : ,
0 1
0 1
0 1 0 0 1 1 0 1
0 1 0 1 1 0 1 0
РМ 1 код : , , , , , , ,
0 1 1 0 0 1 1 0
0 1 1 1 0 0 0 1
РМ 2 код : все 16 слов

12. Порождающая матрица РМ-1 – кода длины 8

Пример.
1 x1 x 2 x 3
1
1
1
1
G
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
0
1
G
0
G1

13. Порождающая матрица РМ-2 – кода длины 8

Пример1. x1
1
1
1
1
G
1
1
1
1
x 2 x 3 x1 x 2 x1 x 3 x 2 x 3
0 0
0 0
0 1
0 1
1 0
1 0
1 1
1 1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
0
0
1
G0
0
0
0
1
G1 G2

14. Порождающая матрица РМr-кода

G G0 G1 ... Gr

15. Параметры РМ-r - кода

Длина кода
n 2
m
Число информационных разрядов
k 1 m C ... C
2
m
Минимальное расстояние
r
m
d min 2
m r

16. Пример параметров РМ-2 - кода

Длина кода n 2
4
16,
m 4
Число информационных разрядов
k 1 4 C 1 4 6 11
2
4
Минимальное расстояние
d min 2
m r
4

17. Пример параметров РМ-3 - кода

Длина кода
n 2 16,
4
m 4
Число информационных разрядов
k 1 4 C C 1 4 6 4 15
2
4
3
4
Минимальное расстояние
d min 2
4 3
2

18. Кодированиe – блоки информационного и кодового слова

G G0 G1
0
1
... Gr
...
r
G0 0 G1 1 ... Gr r

19. Пример

1
1
1
1
G
1
1
1
1
G0
0 0
0 0
0 1
0 1
1 0
1 0
1 1
1 1
0
1
0
1
0
1
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
1
0
1
0
1
0
0 1
1
0
0 1
0
1 1
0
0
1
1
0
1
1
0 1
1
0
1
0 1
1
1
1
1
G1
G2
0
0
1
1
0
0
1
1
0
0
0
1
0
0
1
1 0
0
0
0
0
1
0
1
0
1
1
0
0
0
0
0
1
0
1
0
0
0
1
1
0
0
1
0
0
1

20. Построение проверок - на примере РМ-1 кода длины 16

с0 1
с 1
1
с2 1
с3 1
с4 1
с5 1
с 1
6
с7 1
с
1
8
с9 1
с10 1
с11 1
с12 1
с 1
13
с14 1
с 1
15
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
a0
0
a1
1
a2
0
a3
1
a4
0
1
0
1
0
1

21. Построение проверок - на примере РМ-1 кода длины 16

с0 1
с 1
1
с2 1
с3 1
с4 1
с5 1
с 1
6
с7 1
с
1
8
с9 1
с10 1
с11 1
с12 1
с 1
13
с14 1
с 1
15
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
a0
0
a1
1
a2
0
a3
1
a4
0
1
0
1
0
1
c0 a0
c1 a0 a4
c0 c1 c2 c3 0
c2 a0 a3
c3 a0 a3 a4

22. Построение проверок - на примере РМ-1 кода длины 16

с0 1
с 1
1
с2 1
с3 1
с4 1
с5 1
с 1
6
с7 1
с
1
8
с9 1
с10 1
с11 1
с12 1
с 1
13
с14 1
с 1
15
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
a0
0
a1
1
a2
0
a3
1
a4
0
1
0
1
0
1
c0 a0
c1 a0 a4
c0 c1 c2 c3 0
c2 a0 a3
c3 a0 a3 a4
c 4 a0 a 2
c4 c5 c6 c7 0
c5 a0 a2 a4
c0 c1 c4 c5 0
c6 a0 a2 a3
c c c c 0
0
2
4
6
c7 a0 a2 a3 a4

23. Построение проверок - на примере РМ-1 кода длины 16

с 1 0 0 0 0
0
с 1
1
с2 1
с3 1
с4 1
с5 1
с 1
6
с 1
7
с
1
8
с9 1
с10 1
с11 1
с12 1
с 1
13
с14 1
с 1
15
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
0
1
a0
0
a1
1
a2
0
a3
1
a4
0
1
0
1
0
1
c0 a0
c1 a0 a4
c0 c1 c2 c3 0
c2 a0 a3
c3 a0 a3 a4
c4 a0 a2
c4 c5 c6 c7 0
c5 a0 a2 a4
c0 c1 c4 c5 0
c6 a0 a2 a3
c c c c 0
0
2
4
6
c7 a0 a2 a3 a4
c8 a0 a1
c9 a0 a1 a4
c8 c9 c10 c11 0
c10 a0 a1 a3
c11 a0 a1 a3 a4

24. Построение проверок - на примере РМ-1 кода длины 16

c0 a0
c1 a0 a4
c0 c1 c2 c3 0
c2 a0 a3
c3 a0 a3 a4
c 4 a0 a 2
c4 c5 c6 c7 0
c5 a0 a2 a4
c0 c1 c4 c5 0
c6 a0 a2 a3
c c c c 0
0
2
4
6
c7 a0 a2 a3 a4
c8 a0 a1
c9 a0 a1 a4
c8 c9 c10 c11 0
c10 a0 a1 a3
c11 a0 a1 a3 a4
c12 a0 a2
c12 c13 c14 c15 0
c13 a0 a2 a4
c8 c9 c12 c13 0 и т. д.
c14 a0 a2 a3
c c c c 0
8
10
12
14
c15 a0 a2 a3 a4

25. Построение проверок - на примере РМ-1 кода длины 16 – шаг 1

с0 1
с 1
1
с2 1
с3 1
с4 1
с5 1
с 1
6
с 1
7
с
1
8
с9 1
с10 1
с11 1
с12 1
с 1
13
с14 1
с 1
15
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
a0
0
a1
1
a2
0
a3
1
a4
0
1
0
1
0
1
a4 c0 c1
с2 c3
c4 c5
c6 c7
c8 c9
c10 c11
c12 c13
c14 c15

26. Построение проверок - на примере РМ-1 кода длины 16 – шаг 1

с0 1
с 1
1
с2 1
с3 1
с4 1
с5 1
с 1
6
с7 1
с
1
8
с9 1
с10 1
с11 1
с12 1
с 1
13
с14 1
с 1
15
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
a0
0
a1
1
a2
0
a3
1
a4
0
1
0
1
0
1
a3 c0 c2
c1 c3
c4 c6
c5 c7
c8 c10
c9 c11
c12 c14
c13 c15

27. Построение проверок - на примере РМ-1 кода длины 16 – шаг 1

с0 1
с 1
1
с2 1
с3 1
с4 1
с5 1
с 1
6
с7 1
с
1
8
с9 1
с10 1
с11 1
с12 1
с 1
13
с14 1
с 1
15
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
1
a0
0
a1
1
a2
0
a3
1
a4
0
1
0
1
0
1
a2 c0 c4
c1 c5
c2 c6
c3 c7
c8 c12
c9 c13
c10 c14
c11 c15

28. Построение проверок - на примере РМ-1 кода длины 16 – шаг 1

Построение проверок - на примере РМ-1
0 0 0 длины
0
с 1 кода
16 – шаг 1
0
с1 1
с2 1
с3 1
с4 1
с5 1
с 1
6
с 1
7
с
1
8
с9 1
с10 1
с11 1
с12 1
с 1
13
с14 1
с 1
15
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1
1
0
1
0
1
a0
0
a1
1
a2
0
a3
1
a4
0
1
0
1
0
1
a1 c0 c8
c1 c9
c2 c10
c3 c11
с4 c12
c5 c13
c6 c14
c7 c15

29. Построение проверок - на примере РМ-1 кода длины 16 – шаг 2

с0 1
с 1
1
с2 1
с3 1
с4 1
с5 1
с 1
6
с7 1
а0
с
1
8
с9 1
с10 1
с11 1
с12 1
с 1
13
с14 1
с 1
15
a0 c0 c1
с2 c3
c4 c5
c6 c7
с8 c9
c10 c11
c12 c13
c14 c15

30. Мажоритарное декодирование РМ - кодов

• Строятся проверки для
r
всего 2
m r
• Затем – для r 1
и т.д.
проверок
всего 2
m r 1
• На последнем шаге исправляется
0 a0 всего 2 проверок
m
проверок