2015-07-14
4053
Коди, запропоновані американським вченим Р. Хемінгом, володіють здатністю не лише виявити, але і виправити поодинокі помилки. Ці коди - систематичні.
Властивість кодів Хемінга таке, що контрольне число вказує номер позиції, де сталася помилка. За відсутності помилки в цій позиції послідовність міститиме тільки нулі. Отримане число таким чином описує n=(m + k +1) подій.
Код Хемінга дозволяє відновлювати частково пошкоджену інформацію за рахунок надлишкового її кодування. Кількість контрольних розрядів для коду Хемінга з виправленням поодинокої помилки визначається за формулою:
2 k 
m+k+1,
де m - число інформаційних розрядів; k – число контрольних розрядів.
Для контролю інформації потрібно k додаткових розрядів. Число k вибирається згідно з наступними правилами.
1. Контролююче число k вибирається так, щоб воно мало кількість комбінацій, достатню для розпізнавання однієї з m+k позицій або для сигналізації відсутності помилки. Отримане таким чином число описує n=m+k +1 подій.
2. (m+k) - розрядні позиції нумеруються від одиниці до (m+k), починаючи від молодшої значущої. Контрольні розряди P0, P1, P2,., Pk - 1 поміщаються в розряди, що мають номери 1, 2,4, 8,., 2k-1 (m+k) - розрядного числа. Інші m розрядів можуть бути розміщені у будь-якому порядку між контрольними розрядами.
|
|
|
3. Контрольні розряди P0, P1, P2,., Pk - 1 вибрані так, щоб для певних розрядів слова служити як контрольні надмірні розряди.
Визначити максимальне значення m для k можна з наступного:
| n… | 4… | 8…15 | 16…31 | 32…63 | ||||
| m… | 1… | 4…11 | 11…26 | 26…57 | ||||
| k… | 3… | 4…4 | 5…5 | 6…6 |
Під час першої перевірки перевіряються ті номери позицій, двійкові зображення яких мають у першому розряді 1, тобто
1 = 000 1; 3 = 001 1; 5 = 010 1; 7 = 011 1; 9 = 100 1 і т.д.
Отже, перша перевірка охоплює позиції 1, 3, 5, 7, 9,11… Для другої перевірки виберемо такі позиції, двійкові зображення яких мають 1 у другому розряді, що відповідає 2, 3, 6, 7, 10... Для третьої перевірки виберемо позиції, двійкові зображення яких мають 1 в третьому розряді, тобто маємо 4, 5, 6, 7, 12, 13, 14…
Такий вибір позицій, що перевіряються, дає можливість визначити номер позиції, в якій виникла одинична помилка. Якщо виникла помилка на одній з позицій першої перевірки, то в контрольному числі в нижчому (правому) розряді з'явиться 1. Подальшу перевірку числа дає друга перевірка: якщо серед всіх позицій другої перевірки помилок немає, то з'являтиметься 0. Отже, будь-яку одиничну помилку на певній позиції можна усунути перевірками.
Залишається вирішити, які позиції використати для контрольних чисел. Вибір для перевірки позицій 1, 2, 4, 8 … забезпечує появу хоча б однієї з цих позицій у кожній перевірці, і це дає змогу незалежно від знаків числа, що передається, дістати у кожній перевірці парне число одиниць.
|
|
|
| Перевірка | Розряди, що перевіряються | ||||||||||||||
| … | |||||||||||||||
| … | |||||||||||||||
| … | |||||||||||||||
| … | |||||||||||||||
| … | . | . | . |
P0 вибране з таким розрахунком, щоб в позиціях 1, 3, 5, 7, 9, 11 число одиниць кожного слова було парним, P1 - вибрано для того, щоб виконувалася умова парності в розрядах 2, 3, 6, 7, 10, 11, 14, 15., аналогічно P2 контролює позиції 4, 5, 6, 7,12,13,14,15,20. і P3 для розрядів 8, 9,10,11,12,13,14,15,24,25.
На підставі розглянутих правил в таблиці показані семирозрядні коди. Контрольні розряди позначені P0, P1 і P2 і поміщені в позиціях 1, 2 і 4.
Таблиця 2.21 - Семирозрядні коди.
| Розряди | |||||||
| Число | |||||||
| A | B | C | P2 | D | P1 | P0 | |
Структура коду Хемінга для 15-розрядного числа (11 інформаційних розрядів та 4 контрольних) надана на рис. 2.68.
Рисунок 2. 68 – Структура коду Хемінга для 15-розрядного числа
Узагальнені формули обчислення контрольних розрядів (1),...,(4) мають вигляд:
P3 = S09 Å S10 Å S11 Å S12ÅS13 Å S14 ÅS15;
P 2 = S05 ÅS06 Å S07ÅS12 Å S13ÅS14 Å S15;
P1 = S03 ÅS06 ÅS07 Å S10 Å S11 ÅS14 ÅS15;
P0= S03Å + S05 Å S07 Å S09 Å S11 ÅS13ÅS15.
Якщо деякі інформаційні розряди будуть відсутні (наприклад, S14, S15), то необхідно вважати, що вони дорівнюють нулю.
Результат перевірки на парність записують як 1 або 0 залежно від того, виявлена помилка чи ні. За результатами цих перевірок будують двійкове число с1, с2,…сk, яке дорівнює десятеричному значенню, наданому місцеположенню помилкового розряду, якщо відбулася помилка, і нулю, якщо її немає. Це число називають номером позиції.
Приклад. Закодувати чотирьохрозрядну інформаційну комбінацію 1011 кодом Хемінга.
k=3 (тому що n =4). Розмістимо інформаційні та контрольні розряди, пронумерувавши їх від 1 до 7:
S7 S6 S5 S4 S3 S2 S1
1 0 1? 1??
Обчислимо значення контрольних розрядів:
P0=S3ÅS5ÅS7=1Å1Å1=1;
P1=S3ÅS6ÅS7=1Å0Å1=0;
P2=S5ÅS6ÅS7=1Å0Å1=0.
Тоді повна кодова комбінація коду Хемінга буде мати вигляд:1010101.
Приклад Знайти та виправити помилку у прийнятій комбінації коду Хемінга 1101101.
Положення помилки можна визначити виконанням трьох перевірок на парність:
| Позиція: | ||||||||
| p0 | p1 | m1 | p2 | m2 | m3 | m4 | ||
| Отримане повідомлення: | ||||||||
| Перевірка на парність позицій 4, 5, 6, 7 | с3 = 1 – помилка, тому що результат непарний | |||||||
| Перевірка на парність позицій 2, 3, 6, 7 | с2 = 0, тому що результат парний | |||||||
| Перевірка на парність позицій 1, 3, 5, 7 | с1 = 1 – помилка, тому що результат непарний |
Отже, здобуто номер позиції, який дорівнює 101, що означає наявність помилки в п'ятій позиції. Для її виправлення слід замінити п'ятий розряд його доповненням, після чого матимемо правильне повідомлення 1101001.
|
|
|
Код Хемінга з виправленням поодинокої помилки та контролем подвійної відрізняється від коду з виправленням поодинокої помилки тим, що вводиться ще один додатковий контрольний розряд. Його називають «розрядом подвійного контролю» (ПК). Він визначається додаванням всіх розрядів (інформаційних та контрольних) по модулю 2, тобто по суті цей розряд подвійного контролю здійснює контроль на парність отриманого коду. Якщо уявити вектор помилки (ВП) коду Хемінга, як число, що приймає значення 0 або 1, то можна заповнити таку таблицю:
Таблиця 2.22 – Результати декодування в залежності від ПК та ВП
| ПК | ВП | Результат, отриманий під час декодування |
| Відсутність помилки | ||
| Подвійна помилка | ||
| Помилка у додатковому контрольному розряді | ||
| Помилка не у додатковому контрольному розряді |
Корегувальну здатність коду можна підвищувати і далі, будуючи коди для виявлення r - кратної і виправлення s - кратної помилок. При цьому буде зростати число додаткових знаків і загальна довжина кодової комбінації (при незмінному 
). Очевидно, що 
, 
.
Можливості різних кодів наведено в табл. 2.23.
Таблиця 2.23 -Можливості різних кодів
| d | r | s | Можливості коду |
| Відмінність однієї комбінації від іншої | |||
| Виявлення одиничної помилки | |||
| Виявлення і виправлення одиничної помилки | |||
| Виявлення дворазової помилки | |||
| Виявлення дворазової і виправлення одиничної помилки | |||
| Виявлення триразової помилки | |||
| Виявлення і виправлення дворазової помилки | |||
| Виявлення триразової і виправлення одиничної помилок | |||
| Виявлення чотириразової помилки |
Контрольні питання і завдання
1. У яких одиницях вимірюється кількість інформації?
2. У чому сенс адитивної міри Хартлі?
3. Що називають відстанню Хемінга?
4. У чому сенс і призначення кодів?
5. Чим відрізняється код, що коригує, від контролюючого?
6. Яку відстань Хемінга повинен мати код з виявленням потрійної помилки і виправленням поодинокої?
|
|
|
7. П'ятирозрядну кодову комбінацію 10110 закодуйте в коді Хемінга з виправленням поодинокої помилки.
8. Знайдіть і виправіть поодиноку помилку в коді Хемінга 1011010 з n =4.
9. Яку кількість інформації необхідно витратити для вибору однієї з восьми рівноімовірних букв?
Рекомендована література
Базова
1. Рябенький В. М., Жуйков В. Я., Гулий В. Д.Цифрова схемотехніка: Навч. посібник. — Львів: "Новий Світ-2000", 2009. — 736 с.
2. Савельев А.Я. Прикладная теория цифровых автоматов. - М.: Высшая школа, 1987. - 272 с.
3. Схемотехніка електронних систем: У 3кн. Кн.2. Цифрова схемотехніка: Підручник/ Бойко В.І., Гуржій А.М. Багрій В.В. та інші. – 2-ге вид., допов. переробл.- К.: Вища школа, 2004. – 423с.
4. Цифрова схемотехніка. Частина 1: Навчальний посібник для студентів вузів Бойко В.І., Багрій В.В.-К.: НМЦВО, 2002-244с.
5. Цифрова схемотехніка. Частина 2: Навчальний посібник для студентів вузів Бойко В.І., Багрій В.В.-К.: НМЦВО, 2002-220с.
6. Самофалов К.Г., Романкевич А.М., Валуйский В.Н. и др. Прикладная теория цифровых автоматов. – Киев: Вища шк.,1987. – 375 с.
