Министерство образования и науки российской федерации
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
Национальный исследовательский томский политехнический университет
Институт кибернетики
Направление 230400 «Информационные технологии»
Кафедра вычислительной техники
Отчет по лабораторной работе № 5 по курсу “Теория информации”
«Корректирующий код Хэмминга»
-
Выполнил: студент гр. 8И12
________
___.___._____
А.В. Матвиенко
Проверил: магистрант кафедры ВТ
________
___.___._____
М.Г. Логутенко
Томск – 2012
Цель работы
Изучение корректирующего кода Хэмминга, позволяющего обнаруживать двукратную и исправлять однократную ошибку, а именно: составление структуры кодовой группы для заданного количества букв используемого алфавита, составление выражений для формирования контрольных символов, составление выражений для формирователя указателя ошибки, экспериментальная проверка корректирующих свойств кода, выбор оптимальной длины передаваемого кода.
Ход работы
Задание 1.
Закодировать в коде Хэмминга, исправляющем однократную ошибку, первые буквы своих фамилии, имени и отчества (в кодах ASCII) и записать выражения для контрольных символов.
Решение.
q1 = a1 ⊕ a2 ⊕ a4 ⊕ a5 ⊕ a7
q2 = a1 ⊕ a3 ⊕ a4 ⊕ a6 ⊕ a7
q3 = a2 ⊕ a3 ⊕ a4 ⊕ a8
q4 = a5 ⊕ a6 ⊕ a7 ⊕ a8
М: 100101110001
q1 = 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 = 1
q2 = 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 = 0
q3 = 0 ⊕ 1 ⊕ 1 ⊕ 1 = 1
q4 = 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1
А: 000100010001
q1 = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
q2 = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
q3 = 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1
q4 = 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1
В: 100010010001
q1 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 = 1
q2 = 0 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 0 = 0
q3 = 1 ⊕ 0 ⊕ 0 ⊕ 1 = 0
q4 = 0 ⊕ 0 ⊕ 0 ⊕ 1 = 1
Задание 2. Сформировать указатель ошибки для принятого кода (код взять из таблицы N(6)) и записать выражения для разрядов указателя ошибки.
Решение.
Вариант: 2-2
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
q1 |
q2 |
a1 |
q3 |
a2 |
a3 |
a4 |
q4 |
a5 |
a6 |
a7 |
a8 |
b1 = q1 ⊕ a1 ⊕ a2 ⊕ a4 ⊕ a5 ⊕ a7
b2 = q2 ⊕ a1 ⊕ a3 ⊕ a4 ⊕ a6 ⊕ a7
b3 = q3 ⊕ a2 ⊕ a3 ⊕ a4 ⊕ a8
b4 = q4 ⊕ a5 ⊕ a6 ⊕ a7 ⊕ a8
b1 = 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 = 0
b2 = 1 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 = 1
b3 = 0 ⊕ 0 ⊕ 0 ⊕ 1 ⊕ 1 = 0
b4 = 1 ⊕ 0 ⊕ 0 ⊕ 0 ⊕ 1 = 0
Указатель ошибки: 00102 = 2. Ошибка произошла на второй позиции.
Задание 3. Используя формулу
построить таблицу и график
зависимости m/n для m принимающего
значения от 1 до 16.
m |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
k |
2 |
3 |
3 |
3 |
4 |
4 |
4 |
4 |
4 |
4 |
4 |
5 |
5 |
5 |
5 |
5 |
n |
3 |
5 |
6 |
7 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
17 |
18 |
19 |
20 |
21 |
|
0,33 |
0,4 |
0,5 |
0,57 |
0,556 |
0,6 |
0,636 |
0,67 |
0,69 |
0,71 |
0,733 |
0,706 |
0,722 |
0,737 |
0,75 |
0,76 |
На основании полученных данных в п.3 сделать выводы о наиболее оптимальной величине m.
рис.1 зависимость n от m
рис.2 зависимость m/n от m
Вывод: Из графика (рис.2) видно, что чем больше длина кодовой комбинации n, тем больше доля информационных символов m в ней, и значит, больше эффективность кодовой комбинации, кроме случаев когда m принимает значение 5, 12.
Задание 4. Исследовать способность кода обнаруживать и исправлять однократную ошибку для ASCII-кода первой буквы своей фамилии. Переберите все однократные ошибки. Так как материальным носителем является сигнал, то помимо кодов необходимо фиксировать эпюры сигналов.
Код сообщения: 00110001 Сообщение в коде Хэмминга: 100101110001 Сигнал
на входе канала связи:
|
Искаженные позиции |
Сигнал на выходе канала связи |
Некорректированный код |
Указатель ошибки |
Корректированный код |
0 |
|
000101110001 |
0001 |
100101110001 |
1 |
|
110101110001 |
0010 |
100101110001 |
2 |
|
101101110001 |
0011 |
100101110001 |
3 |
|
100001110001 |
0100 |
100101110001 |
4 |
|
100111110001 |
0101 |
100101110001 |
5 |
|
100100110001 |
0110 |
100101110001 |
6 |
|
100101010001 |
0111 |
100101110001 |
7 |
|
100101100001 |
1000 |
100101110001 |
8 |
|
100101111001 |
1001 |
100101110001 |
9 |
|
100101110101 |
1010 |
100101110001 |
10 |
|
100101110011 |
1011 |
100101110001 |
11 |
|
100101110000 |
0100 |
100101110001 |
Вывод: однократные ошибки исправляются при передаче данных.
Задание 5. Исследовать способность кода обнаруживать и исправлять двукратную ошибку для ASCII-кода первой буквы своего имени. Переберите все двукратные ошибки.
Таблица ввода результатов эксперимента № 2
Код сообщения: 00000001 Сообщение в коде Хэмминга: 000100010001 Сигнал на входе канала связи: |
||||
Искаженные позиции |
Сигнал на выходе канала связи |
Некорректированный код |
Указатель ошибки |
Корректированный код |
0 1 |
|
110100010001 |
0011 |
111100010001 |
0 2 |
|
101100010001 |
0010 |
111100010001 |
0 3 |
|
100000010001 |
0101 |
100010010001 |
0 4 |
|
100110010001 |
0100 |
100010010001 |
0 5 |
|
100101010001 |
0111 |
100101110001 |
0 6 |
|
100100110001 |
0110 |
100101110001 |
0 7 |
|
100100000001 |
1001 |
100100001001 |
0 8 |
|
100100011001 |
1000 |
100100001001 |
0 9 |
|
100100010101 |
1011 |
100100010111 |
0 10 |
|
100100010011 |
1010 |
100100010111 |
0 11 |
|
100100010000 |
1101 |
100100010000 |
1 2 |
|
011100010001 |
0001 |
111100010001 |
1 3 |
|
010000010001 |
0110 |
010001010001 |
1 4 |
|
010110010001 |
0111 |
010110110001 |
1 5 |
|
010101010001 |
0100 |
010001010001 |
1 6 |
|
010100110001 |
0101 |
010110110001 |
1 7 |
|
010100000001 |
1010 |
010100000101 |
1 8 |
|
010100011001 |
1011 |
010100011011 |
1 9 |
|
010100010101 |
1000 |
010100000101 |
1 10 |
|
010100010011 |
1001 |
010100011011 |
1 11 |
|
010100010000 |
1110 |
010100010000 |
2 3 |
|
001000010001 |
0111 |
001000110001 |
2 4 |
|
001110010001 |
0110 |
001111010001 |
2 5 |
|
001111010001 |
0101 |
001111010001 |
2 6 |
|
001100110001 |
0100 |
001000110001 |
2 7 |
|
001100000001 |
1011 |
001100000011 |
2 8 |
|
001100011001 |
1010 |
001100011101 |
2 9 |
|
001100010101 |
1001 |
001100011101 |
2 10 |
|
001100010011 |
1000 |
001100000011 |
2 11 |
|
001100010000 |
1111 |
001100010000 |
3 4 |
|
000010010001 |
0001 |
100010010001 |
3 5 |
|
000001010001 |
0010 |
010001010001 |
3 6 |
|
000000110001 |
0011 |
001000110001 |
3 7 |
|
000000000001 |
1100 |
000000000000 |
3 8 |
|
000000011001 |
1101 |
000000011001 |
3 9 |
|
000000010101 |
1110 |
000000010101 |
3 10 |
|
000000010011 |
1111 |
000000010011 |
3 11 |
|
000000010000 |
1000 |
000000000000 |
4 5 |
|
000111010001 |
0011 |
001111010001 |
4 6 |
|
000110110001 |
0010 |
010110110001 |
4 7 |
|
000110000001 |
1101 |
000110000001 |
4 8 |
|
000110011001 |
1100 |
000110011000 |
4 9 |
|
000110010101 |
1111 |
000110010101 |
4 10 |
|
000110010011 |
1110 |
000110010011 |
4 11 |
|
000110010000 |
1001 |
000110010000 |
5 6 |
|
000101110001 |
0001 |
100101110001 |
5 7 |
|
000101000001 |
1110 |
000101000001 |
5 8 |
|
000101011001 |
1111 |
000101011001 |
5 9 |
|
000101010101 |
1100 |
0001010101000 |
5 10 |
|
000101010011 |
1101 |
000101010011 |
5 11 |
|
000101010000 |
1010 |
000101010100 |
6 7 |
|
000100100001 |
1111 |
000100100001 |
6 8 |
|
000100111001 |
1110 |
000100111001 |
6 9 |
|
000100110101 |
1101 |
000100110101 |
6 10 |
|
000100110011 |
1100 |
000100110010 |
6 11 |
|
000100110000 |
1011 |
000100110010 |
7 8 |
|
000100001001 |
0001 |
100100001001 |
7 9 |
|
000100000101 |
0010 |
010100000101 |
7 10 |
|
000100000011 |
0011 |
001100000011 |
7 11 |
|
000100000000 |
0100 |
000000000000 |
8 9 |
|
000100011101 |
0011 |
001100011101 |
8 10 |
|
000100011011 |
0010 |
010100011011 |
8 11 |
|
000100011000 |
0101 |
000110011000 |
9 10 |
|
000100010111 |
0001 |
100100010111 |
9 11 |
|
000100010100 |
0110 |
000101010100 |
10 11 |
|
000100010010 |
0111 |
000100110010 |
Вывод: Код Хэмминга обнаруживает, но не всегда исправляет двукратную ошибку. Примеры исправления пункты: 0-11, 1-11, 2-11 и т.д.
Задание 6. Исследовать способность кода обнаруживать и исправлять трехкратную ошибку для ASCII-кода первой буквы своего отчества. Переберите 15 комбинаций трехкратных ошибок.
Таблица ввода результатов эксперимента № 3
Код сообщения: 01000001 Сообщение в коде Хэмминга: 100010010001 Сигнал на входе канала связи: |
Искаженные позиции |
Сигнал на выходе канала связи |
Некорректированный код |
Указатель ошибки |
Корректированный код |
0 1 2 |
|
011010010001 |
0000 |
011010010001 |
0 3 4 |
|
000100010001 |
0000 |
000100010001 |
2 4 5 |
|
101001010001 |
0000 |
101001010001 |
2 5 8 |
|
101011011001 |
1100 |
101011011000 |
2 7 11 |
|
101010000000 |
0111 |
101010100000 |
3 6 7 |
|
100110100001 |
1011 |
100110100011 |
4 5 6 |
|
100001110001 |
0100 |
100101110001 |
4 7 10 |
|
100000000011 |
0110 |
100001000011 |
4 9 11 |
|
100000010100 |
0011 |
101000010100 |
5 6 7 |
|
100011100001 |
1001 |
1000011101001 |
6 7 8 |
|
100010101001 |
0110 |
1000011101001 |
7 8 9 |
|
100010001101 |
1011 |
1000100001111 |
7 9 11 |
|
100010000100 |
1110 |
1000100000100 |
8 9 11 |
|
100010011100 |
1111 |
100010011100 |
9 10 11 |
|
100010010110 |
1101 |
100010010110 |
Вывод: код Хэмминга в общем случае некорректно исправляет трехкратную ошибку, и не всегда обнаруживает её. Пример: 0-1-2, 0-3-4.
ВЫВОД
В ходе выполнения лабораторной работы, получены следующие результаты: корректирующий код Хэмминга эффективно исправляет однократную и обнаруживает двукратную ошибку.
При большем числе ошибок код Хэмминга не эффективен. Алгоритм кодировки и исправления ошибок достаточно прост в реализации на ЭВМ, поэтому широко используется в вычислительной технике для создания помехоустойчивых систем.