Код Хеммінга
Кодування по методу, запропонованому американським інженером Робертом Хеммінгом в 1948 р., дозволяє побудувати оптимальний систематичний код.
Оптимальним називається (n, m) код, який забезпечує мінімальну імовірність помилкового декодування серед усіх інших кодів з тими ж n і m.
Найвідоміші з кодів, що самоконтролюються і самокоректуються, – коди Хеммінга. Побудовані вони відносно двійкової системи числення.
Для побудови коду, що виявляє спотворення, достатньо мати один контрольний розряд (код з перевіркою на парність). Але при цьому не має ніяких указівок на те, в якому саме розряді відбулася помилка, і, отже, немає можливості виправити її. Залишаються непоміченими спотворення, що виникли в парному числі розрядів.
Коди Хеммінга мають більшу надмірність, ніж коди з перевіркою на парність, і призначені для виправлення одиночних помилок, або для виправлення одиночних і виявлення без виправлення подвійних помилок (зі збільшенням надмірності). У такому коді n-значне число має m інформаційних і k контрольних розрядів. Кожен з контрольних розрядів є ознакою парності для певної групи інформаційних знаків базового кодового слова. При декодуванні здійснюється k групових перевірок на парність і формується певне число – синдром спотворень S. У результаті кожної перевірки у відповідний розряд синдрому спотворень Sі записується 0, якщо перевірка була успішною, або 1, якщо була знайдена непарність.
Групи для перевірки утворюються так, що в регістрі спотворень після закінчення перевірки виходить k-розрядне двійкове число, що показує номер позиції помилкового двійкового розряду. Зміна цього розряду – виправлення спотворень.
Спочатку ці коди запропоновані у такому вигляді, при якому контрольні ознаки займають особливі позиції: позиція
i-го знаку має номер 2i–1. При цьому кожен контрольний знак входить лише в одну перевірку на парність.
Розглянемо код Хеммінга, призначений для виправлення одиночних помилок.
Поодиноке спотворення можливе в одній з n позицій. Отже, кількість контрольних знаків, а значить, і кількість розрядів регістра помилок повинна задовольняти умову
k ≥ log2  log2 (n + 1).
| (4.1) |
Звідси
| m ≥ n – log2(n + 1). | (4.2) |
Значення m і k для деяких коротких кодів, обчислені по формулах (4.1) і (4.2) дані в табл. 4.1.
Таблиця 4.1
| n | ||||||||||
| m | ||||||||||
| k |
Як перевірочні біти зручно вибрати такі, які входять тільки один раз у кожну перевірку, тобто такі, для яких Si містить лише один ненульовий біт; очевидно, це S1, S2, S4, S8 і т.д.–ті біти, номери яких є цілим степенем 2 (див. рис. 4.1).
Рис. 4.1. Базове кодове слово для коду Хеммінга
Іншими словами в коді Хеммінга інформаційні і перевірочні біти не рознесені в окремі підматриці, а чергуються. При цьому береться така нумерація біт (знаків коду): усі біти кодової комбінації одержують номери, починаючи з 1, справа наліво (варто нагадати, що інформаційні біти нумеруються з 0 справа наліво); контрольними (перевірочними) є біти з номерами 1, 2, 4, 8 і т.д. – усі інші є інформаційними.
Щоб число в синдромі спотворень указувало номер позиції помилкового розряду, групи для перевірки вибираються за правилом:
| I гр.: | : | усі непарні позиції, включаючи позиції контрольного розряду, тобто позиції, в першому молодшому розряді яких стоїть 1. |
| II гр.: | : | усі позиції, номери яких в двійковому поданні мають 1 у другому розряді справа (наприклад, 2, 3, 6, 7, 10) і т.д. |
| III гр. | : | розряди, що мають «1» у третьому розряді справа, і т.д. |
Примітка 1. Кожен контрольний знак входить тільки до однієї групи, що перевіряється. У кожен з контрольних розрядів при побудові коду Хеммінга надсилається таке значення, щоб загальна кількість одиниць у його контрольній сумі була парною. Тобто, для (n, m) коду Хеммінга перевірочні символи визначаються із перевірочних рівнянь:
де: 
− перевірочні символи.
При перевірці наявності спотворень за розглянутими вище правилами розраховуються так звані елементи синдрому спотворень Si. Але при розрахунку елементів синдрому спотворень використовуються і сформовані раніше перевірочні елементи. Тобто елементи синдрому визначаються з виразів (синдромних рівнянь):
Приклад 1. Хай k = 5 (табл. 4.2).
Формування контрольних груп. Таблиця 4.2
| Номер перевірки | Позиція контрольного біта | Позиції, що перевіряються |
| 1, 3, 5, 7, 9, 11, 13, ... | ||
| 2, 3, 6, 7, 10, 11, ... | ||
| 4, 5, 6, 7, 12, 13, ... | ||
| 8, 9, 10, 11, 12, 13, ... | ||
| 16, 17, 18, 19, 20, 21 |
Приклад 2. Розглянемо семизначний код Хеммінга для зображення чисел від 0 до 9 (табл. 3).
Семизначний код Хеммінга. Таблиця 4.3
| Десяткове | Простій двійковий | Код Хеммінга | ||||||||||
| число | код | k | k | k | ||||||||
Хай переданий код числа 6 у вигляді «0 1 1 0 0 1 1», а прийняли у вигляді «0 1 0 0 0 1 1».
Перевірочні групи при нумерації розрядів, починаючи з правого (молодшого):
| I перевірка: | розряди 1, 3, 5, 7– 0 1 0 0 0 1 1 дає 1 у молодший розряд синдрому спотворень S1. |
| II перевірка: | розряди 2, 3, 6, 7– 01 0 0 01 1 дає 0 у другий розряд синдрому спотворень S2. |
| III перевірка: | розряди 4, 5, 6, 7– 0100 0 1 1 дає 1 у третій розряд синдрому спотворень S3. |
Вміст синдрому спотворень «101» свідчить про помилку у п’ятій позиції.
Той же алгоритм, але застосований при іншій нумерації розрядів, починаючи з лівого (молодшого):
| I перевірка : | розряди 1, 3, 5, 7– 0 1 0 0 0 1 1 дає 1 у молодший розряд синдрому спотворень S1. |
| II перевірка : | розряди 2, 3, 6, 7– 0 1 0 0 0 1 1 дає 1 у другий розряд синдрому спотворень S2. |
| III перевірка: | розряди 4, 5, 6, 7– 0 1 0 0 0 1 1 дає 0 у третій розряд синдрому спотворень S3. |
Вміст синдрому спотворень «011» свідчить про помилку в третій позиції.
Перевірочні рівняння використовуються для побудови кодера, а синдромні − для побудови декодера коду Хеммінга.