Виявлення й виправлення помилок у коді Хеммінга

Розглянемо правила виявлення і виправлення помилок у коді Хеммінга на наступному прикладі:

Приклад 4.2. Нехай в каналі зв'язку під дією завад відбулося спотворення коду і замість 0100101 було прийнято 0100111.

Розв‘язок: Для виявлення помилки виконують перевірки на парність.

Перша перевірка: сума П1+П3+П5+П7 = 0+0+1+1 парна. У молодший розряд номера помилкової позиції запишемо 0.

Друга перевірка: сума П2+П3+П6+П7 = 1+0+1+1 непарна. У другий розряд номера помилкової позиції запишемо 1.

Третя перевірка: сума П4+П5+П6+П7 = 0+1+1+1 непарна. У третій розряд номера помилкової позиції запишемо 1. Номер помилкової позиції 110 = 6.

Отже, символ шостої позиції варто змінити на зворотний, і одержимо правильну кодову комбінацію.

Методичні вказівки до виконання роботи

1. Складіть код Хеммінга заданого варіанту послідовності інформаційних біт з таблиці 4.4.

2. Перевірте правильність передачі заданого варіанту отриманої послідовності біт із таблиці 4.4.

3. Виправити виявлену в п.2 завдання помилку у заданому варіанті отриманої послідовності біт (дивись продовження таблиці 4.4).

4. Оформити результати у вигляді звіту.

 

Таблиця 4.4 – Варіанти завдань

№ вар.	Послідовність інформаційних біт
i1	i2	i3	i4	i5	i6	i7	i8	i9	i10	i11	i12	i13	i14	i15	i16
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.

 

Продовження таблиці 4.4

№ вар.	Отримана послідовність біт
k1	k2	i1	k3	i2	i3	i4	k4	i5	i6	i7	i8	i9	i10	i11	k5	i12	i13	i14	i15	i16
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.

Контрольні питання

1. Поясніть ідею побудови коду Хеммінга.

2. Яке співвідношення між кількістю інформаційних і контрольних символів у коді Хеммінга?

3. За якою формулою визначаються номери перевірочних позицій коду Хеммінга?

4. Опишіть алгоритм виявлення одиничної помилки у коді Хеммінга.

5. За яким алгоритмом можна виправити одиничну помилку у коді Хеммінга?

Рекомендована література

 

1. Стариченко Б.Е. Теоретические основы информатики: Учебное пособие для вузов. – М.: Горячая линия – Телеком, 2003. – 312 с.

2. Савельев В.В. Информатика: Учебник для вузов.– М: Высш.шк., 2001.

3. Прикладная теория цифровых автоматов / К.Г. Самофалов, А.М. Романкевич, В.Н. Валуйский, Ю.С. Каневский, М.М. Пикевич. – К.: Вища шк., Головное изд-во, 1987. – 375 с.

4. Кодирование информации: методические указания / сост.: В. Д. Горбоконенко, В. Е. Шикина. – Ульяновск: УлГТУ, 2006. – 56 с.

5. Капітонова Ю.В. Основи дискретної математики. – К.: "Наукова думка", 2002. – 572 с.

6. Брукшир Дж. Информатика и вычислительная техника. – СПб.: Питер, 2004. – 620 с.

 

 

На сьогодні існує нагальна потреба у розробці і впровадженні автоматизованих інформаційних технологій. Зокрема це стосується методів стиснення інформації, завадозахищеної передачі даних, кодування числової і символьної інформації за допомогою комп‘ютера і виконання арифметичних і логічних операцій з двійковими числами.

 

Користуючись алгоритмами, сформульованими в п.1.2, 1.3, можна заповнити таблицю 1.1.

 

 

1000001₂= 65₁₀.

 

де p_i = n_i / n – ймовірність появи i -го символу початкового алфавіту, n_i – кількість повторень i-го символу в кодованому повідомленні, n – довжина кодованого повідомлення.

 

Згідно (3.3) p ₀ ^преф.к. = å (p_i × (k ⁽ⁱ⁾_0/ k ⁽ⁱ⁾)) = 0,3 × 2/2 + 0,2 × 1/2 + 0,2 × 0/2 + 0,15 × × 2/3 + 0,1 × 2/4 + 0,05 × 1/4 = 0,563.

p ₁ = 1 - p ₀ = 1 - 0,563 = 0,437.

Визначимо середню кількість інформації на знак вторинного алфавіту отриманого префіксного коду. За формулою (3.2) маємо:

 

I^{(2) преф.к..} = - (p ₀ ^преф.к. log₂ p ₀ ^преф.к. + (1 - p ₀ ^преф.к log₂ (1 - p ₀ ^преф.к.) = - (0,563 ×
× log₂0,563 + 0,437 × log₂0,437) ≈ 0,988 біт.

 

 

УДК 004(07)

ББК 32.81

М 54

 

----------------------------------------------------------------------------------------------------

Підп. до друку 21.09.2009. Формат 60х84 1/16. Папір офс. Гарн. Times New Roman.

Друк оперативн. Ум. друк. арк. 1,63. Обл.-вид. арк. 1,43. Тираж 30 прим. Зам. № 09-0199.

----------------------------------------------------------------------------------------------------

Черкаський державний технологічний університет

Свідоцтво про державну реєстрацію ДК № 896 від 16.04.2002 р.

Надруковано в редакційно-видавничому центрі ЧДТУ

бульвар Шевченка, 460, м. Черкаси, 18006.