Методичні вказівки до лабораторних занять з дисципліни «прикладна теорія цифрових автоматів», страница 5

3.Елементи теорії побудови кодів Хемінга.

Питання, розглядувані в цьому розділі, виникли найперше в основному у техніці зв'язку, а не в обчислювальної техніці. Саме тому типова ситуація, розглянута тут, полягає у тому, що виконується передача (а не переробка) інформації, і з деякою ймовірністю можуть виникати випадкові помилки. Передачу інформації можна розуміти у широкому розумінні цього слова, включаючи зміну фізичної форми сигналів, затримку їх по часу, зміну порядку слідування сигналів та ін. Практичну важливість цих питань для обчислювальної техніки та їх застосування до обчислювальної техніки не слід переоцінювати. У більшості випадків в подальшому припускається, що при передачі числа найбільш ймовірною є помилка в одному розряді, менш ймовірною – помилка водночас у двох розрядах, ще менш ймовірною – одночасна помилка у трьох розрядах і т.д. Часто, однак, таке припущення виявляється занадто штучним.

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

Нехай кожне число представлене m двійковими розрядами, та нехай найбільш ймовірна помилка полягає у викривленні одного з них (замість нуля приймається одиниця або навпаки). Для побудови контролюючого коду достатньо приписати до кожного числа один додатковий (контрольний) двійковий розряд та вибрати цифру цього розряду так, щоб загальна кількість одиниць у зображенні будь-якого числа була, наприклад, парним. Поодинока помилка в будь-якому з розрядів числа (і у контрольному розряді теж) змінює парність загальної кількості одиниць. Лічильник по модулю 2, що підраховує кількість одиниць, які містяться серед двійкових цифр числа, міг би давати сигнал про наявність помилок. При цьому ми не одержуємо жодних вказівок про те, в якому саме розряді сталася помилка, тому не маємо можливості виправити її. Залишаються непомітними також помилки, що виникають водночас у двох, у чотирьох або взагалі у парній кількості розрядів. Проте подвійні, а тем більш чотирикратні помилки вважаються малоймовірними.