Код Хеммінга

Кодування по методу, запропонованому американським інженером Робертом Хеммінгом в 1948 р., дозволяє побудувати оптимальний систематичний код.

Оптимальним називається (n, m) код, який забезпечує мінімальну імовірність помилкового декодування серед усіх інших кодів з тими ж n і m.

Найвідоміші з кодів, що самоконтролюються і самокоректуються, – коди Хеммінга. Побудовані вони відносно двійкової системи числення.

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

Коди Хеммінга мають більшу надмірність, ніж коди з перевіркою на парність, і призначені для виправлення одиночних помилок, або для виправлення одиночних і виявлення без виправлення подвійних помилок (зі збільшенням надмірності). У такому коді n-значне число має m інформаційних і k контрольних розрядів. Кожен з контрольних розрядів є ознакою парності для певної групи інформаційних знаків базового кодового слова. При декодуванні здійснюється k групових перевірок на парність і формується певне число – синдром спотворень S. У результаті кожної перевірки у відповідний розряд синдрому спотворень Sі записується 0, якщо перевірка була успішною, або 1, якщо була знайдена непарність.

Групи для перевірки утворюються так, що в регістрі спотворень після закінчення перевірки виходить k -розрядне двійкове число, що показує номер позиції помилкового двійкового розряду. Зміна цього розряду – виправлення спотворень.

Спочатку ці коди запропоновані у такому вигляді, при якому контрольні ознаки займають особливі позиції: позиція
i-го знаку має номер 2 ⁱ –1. При цьому кожен контрольний знак входить лише в одну перевірку на парність.

Розглянемо код Хеммінга, призначений для виправлення одиночних помилок.

Поодиноке спотворення можливе в одній з n позицій. Отже, кількість контрольних знаків, а значить, і кількість розрядів регістра помилок повинна задовольняти умову

k ≥ log2 log2 (n + 1).

(4.1)

Звідси

Значення m і k для деяких коротких кодів, обчислені по формулах (4.1) і (4.2) дані в табл. 4.1.

Таблиця 4.1

Як перевірочні біти зручно вибрати такі, які входять тільки один раз у кожну перевірку, тобто такі, для яких S_i містить лише один ненульовий біт; очевидно, це S ₁, S ₂, S ₄, S ₈ і т.д.–ті біти, номери яких є цілим степенем 2 (див. рис. 4.1).

Рис. 4.1. Базове кодове слово для коду Хеммінга

Іншими словами в коді Хеммінга інформаційні і перевірочні біти не рознесені в окремі підматриці, а чергуються. При цьому береться така нумерація біт (знаків коду): усі біти кодової комбінації одержують номери, починаючи з 1, справа наліво (варто нагадати, що інформаційні біти нумеруються з 0 справа наліво); контрольними (перевірочними) є біти з номерами 1, 2, 4, 8 і т.д. – усі інші є інформаційними.

Щоб число в синдромі спотворень указувало номер позиції помилкового розряду, групи для перевірки вибираються за правилом:

Примітка 1. Кожен контрольний знак входить тільки до однієї групи, що перевіряється. У кожен з контрольних розрядів при побудові коду Хеммінга надсилається таке значення, щоб загальна кількість одиниць у його контрольній сумі була парною. Тобто, для (n, m) коду Хеммінга перевірочні символи визначаються із перевірочних рівнянь:

де: − перевірочні символи.

При перевірці наявності спотворень за розглянутими вище правилами розраховуються так звані елементи синдрому спотворень Si. Але при розрахунку елементів синдрому спотворень використовуються і сформовані раніше перевірочні елементи. Тобто елементи синдрому визначаються з виразів (синдромних рівнянь):

Приклад 1. Хай k = 5 (табл. 4.2).

Формування контрольних груп. Таблиця 4.2

Приклад 2. Розглянемо семизначний код Хеммінга для зображення чисел від 0 до 9 (табл. 3).

Семизначний код Хеммінга. Таблиця 4.3

Хай переданий код числа 6 у вигляді «0 1 1 0 0 1 1», а прийняли у вигляді «0 1 0 0 0 1 1».

Перевірочні групи при нумерації розрядів, починаючи з правого (молодшого):

Вміст синдрому спотворень «101» свідчить про помилку у п’ятій позиції.

Той же алгоритм, але застосований при іншій нумерації розрядів, починаючи з лівого (молодшого):

Вміст синдрому спотворень «011» свідчить про помилку в третій позиції.

Перевірочні рівняння використовуються для побудови кодера, а синдромні − для побудови декодера коду Хеммінга.

Поиск по сайту: