Помехоустойчивый код Хемминга

1.

Коррекция ошибок при
передаче данных

2.

Символ
0
1
Двоичный код
Кодовое слово
2
3
4
5
6
7
8
9
Помехоустойчивый код Хемминга
основные понятия – кодовое слово

3.

Символ
0
1
Двоичный код
0000
0001
Кодовое слово
0000
0001
2
3
4
0010
0011
0100
0010
0011
0100
5
6
7
0101
0110
0111
0101
0110
0111
8
9
1000
1001
1000
1001
Код Хемминга
основные понятия – кодовое слово

4.

Символ
0
1
Двоичный код
0000
0001
Кодовое слово
0000 000
0001 111
2
3
4
0010
0011
0100
0010 110
0011 001
0100 101
5
6
7
0101
0110
0111
0101 010
0110 011
0111 100
8
9
1000
1001
1000 011
1001 100
Код Хемминга
основные понятия – кодовое слово

5.

Символ
0
1
2
3
4
5
6
7
8
9
Двоичный код
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
Кодовое слово
0000 000
0001 111
0010 110
0011 001
0100 101
0101 010
0110 011
0111 100
1000 011
1001 100
4
3
4
?
?
3
?
?
4
Код Хемминга
основные понятия – расстояние между двумя словами
(количество несовпадений в цифрах)

6.

Символ
0
1
2
3
4
5
6
7
8
9
Двоичный код
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
Кодовое слово
0000 000
0001 111
0010 110
0011 001
0100 101
0101 010
0110 011
0111 100
1000 011
1001 100
4
3
4
4
4
3
?
?
4
Код Хемминга
основные понятия – расстояние между двумя словами
(количество несовпадений в цифрах)

7.

Символ
0
1
2
3
4
5
6
7
8
9
Двоичный код
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
Кодовое слово
0000 000
0001 111
0010 110
0011 001
0100 101
0101 010
0110 011
0111 100
1000 011
1001 100
4
3
4
4
4
3
4
7
4
Код Хемминга
основные понятия – расстояние между двумя словами
(количество несовпадений в цифрах)

8.

АЛГОРИТМ ПОИСКА ПОМЕХ
• Разделить полученное сообщение на 7-битовые
слова
1000011 1001111 0110010
0100101
• Сравниваем каждую группу с кодовым словом из
кода Хемминга

9.

1000011
• Если полученное слово
совпало с кодовым
словом в таблице, то
сообщение прошло без
ошибок
Символ
0
1
2
3
Кодовое слово
0000 000
0001 111
0010 110
0011 001
4
5
6
7
8
9
0100 101
0101 010
0110 011
0111 100
1000 011
1001 100

10.

1001111
• Если в таблице есть слово,
расстояние от которого до
полученного равно 1, то
полученное слово
заменяется на ближайшее
к нему из таблицы
Символ
0
1
2
3
Кодовое слово
0000 000
0001 111
0010 110
0011 001
4
5
6
7
8
9
0100 101
0101 010
0110 011
0111 100
1000 011
1001 100

11.

0110010
• Если в таблице есть слова,
расстояние от которого до
полученного равно 1, то
полученное слово
заменяется на ближайшее
к нему из таблицы
Символ
0
1
2
3
Кодовое слово
0000 000
0001 111
0010 110
0011 001
4
5
6
7
8
9
0100 101
0101 010
0110 011
0111 100
1000 011
1001 100

12.

0100101
• Если полученное слово
совпало с кодовым
словом в таблице, то
сообщение прошло без
ошибок
Символ
0
1
2
3
Кодовое слово
0000 000
0001 111
0010 110
0011 001
4
5
6
7
8
9
0100 101
0101 010
0110 011
0111 100
1000 011
1001 100

13.

Следовательно, передано сообщение: 8164.
Если в таблице есть слова, расстояние от
которого до полученного равно 2, тогда слово
исправить нельзя.

14.

Практическая часть
• Реализуйте программу Hemming в системе
программирования
• ДОМАШНЕЕ ЗАДАНИЕ. § 1.5.3