Алгоритм кодування коду Хеммінга

Практична частина

Ітеративний код

Припустимо, потрібно передати повідомлення m завдовжки 9 символів. Розмістимо символи повідомлення у вигляді матриці, додавши до кожного рядка і стовпця контрольні символи перевірки на парність (табл. 1.2.1).

Таблиця 1.2.1

Контрольні символи перевірки на парність

Якщо у процесі передачі в цій таблиці виникне одна помилка, то перевірка на парність у відповідному рядку і стовпці не виконуватиметься. Координати помилки однозначно визначаються номерами стовпця і рядка, в яких не виконується перевірка на парність. Відтак, такий код може не тільки виявляти, але й виправляти помилки.

Описаний метод кодування називається ітеративним. Його застосування доцільне, якщо дані формуються у вигляді масивів, наприклад, в шинах ЕОМ, в пам'яті, що має табличну структуру.

Недоліком такого кодування є значна надлишковість при порівняно низькій виправній здатності .

Таблица ASCII

	Запис числа у десятковій системі	Запис числа у шістнадцятковій системі	Запис числа у двійковій системі	Символ на клавіатурі
1. Барчина О.О.											@
2.											A
3.											B
4.											C
5.											D
6.											E
7.											F
8.											G
9.											H
											I
		4A									J
		4B									K
		4C									L
		4D									M
		4E									N
		4F									O

Місце внесення помилки у код Хеммінга

Варіант	Місце помилки
рядок	стовбець

Коди Хеммінга – лінійні коди, які забезпечують виявлення та корекцію помилок. Використовуються при передачі та зберіганні даних. Особливістю даного коду є використання кількох бітів контролю парності. Коди Хеммінга забезпечують виявлення двох помилок і виправлення однієї помилки.

Припустим в мене є код ASCII 0 1 0 0 0 0 0 1 який означає англійську літиру А.

Нам потрібно провірити чи в цьому коду немає помилок, ми це можем зробити за методом Хеммінга. Для легшого розуміння цього метода ми запишим певні позначення.

Виключне АБО

0+0=0

0+1=1

1+0=1

1+1=0

І елементи -- інформаційний символ (Він відповідає місцю розташування символа в зворотному порядку).

К елементи – елементи Хеммінга додаткові (надлишкові)

Е елементи – ……….(за допомогою цього елемента я визначатиму місце помилки.)

1, 2, 4, 8 і 16 визначає місце розташування К елементів в табличі, (величина є стала)

Для подальшого визначення помилки ми вносим К елементи, які розташовуються за формулою як зображена нище

= =1

= =2

= =4

= =8

= =16

От так виглядає табличка в якоі показано К елементи І елементи, місце їх розташування і также порядковий номе (для легшого розрахунку)

Таблиця 2.1

К елементи І елементи, місце їх розташування

В коді Хеммінга використаєм наступну таблицю 2.2. В ній буду брати інформацію для визначення місце знаходження місця елемент. (ця табличка є універсальна, вона підходить до К елементі Е елементів і так же я будем використовувати для самого знаходження місця помилки).

Таблиця 2.2

Таблиця для місцезнаходження К елементів і Е елементів

Місце розташуваня	Стобчики для метода Хеммінга
стб. 4	стб. 3	стб. 2	стб. 1

Припустим мені потрібно знай ) я беру значення стобчика 1(стб. 1, стобчик залежить від – стб. , іт.д.) і дивимось де знаходиться 1, потім дивимось яка цифра стоїть в першому стобчику, яка буде цифра таке буде й місце розташування нашого елемента Табл. 1

Далі ми знаходим самий К елемент за табл. 3 і обраховуємо за допомогою виключного АБО

Після того як знайшли К елементи, я вносю в таблицю.2.3

Таблиця 2.3

Код Хеммінга

код ASCII	І елементи з К елементами(Код Хеммінга)
І8	І7	І6	І5	К4	І4	І3	І2	К3	І1	К2	К1
0100 0000
0100 0001
0100 0010
0100 0011
0100 0100
0100 0101
0100 0110
0100 0111
0100 1000
0100 1001
0100 1010
0100 1011
0100 1100
0100 1101
0100 1110
0100 1111

Наступна моя задача знайти Е елементи [перевірити код на помилки]. Я проводжу таку роботу що й і з К елементами.

Для того що визначити місце помилки потрібно взяти відповідь з минулого рівняння і записати в зворотному порядку, після чого подивитись з табл. 3 для знаходження місце розташування помилки. Аналогічно записати всі отримані значення в таблицю 2.4

Таблиця 2.4

Місце помилки

Код Aski	Код Хеммінга	Е елементи	Місце помилки
Е1	Е2	Е3	Е4
0100 0000																	Правильний
0100 0001																	Правильний
0100 0010																	Правильний
0100 0011																	Правильний
0100 0100																	Правильний
0100 0101																	Правильний
0100 0110																	Правильний
0100 0111																	Правильний
0100 1000																	Правильний
0100 1001																	Правильний
0100 1010																	Правильний
0100 1011
0100 1100																	Правильний
0100 1101																	Правильний
0100 1110																	Правильний
0100 1111																	Правильний

Помилка виявилась в коді на 10 місці. Код повинен бути такий

Дата добавления: 2017-01-14