1.4 Код хеммінга

Припустимо, що слово складається з m бітів даних, до яких додаємо р додаткових бітів (контрольних розрядів). Нехай загальна довжина слова буде n (n-m+р). п-бітову одиницю, що містить m бітів даних і р контрольних розрядів, часто називають кодованими словом. Для будь-яких двох кодованих слів, наприклад 10001001 і 10110001, можна визначити, скільки відповідних бітів у них відрізняється. У даному прикладі таких біта три. Щоб визначити кількість відмінних бітів, потрібно над двома кодованими словами виконати логічну операцію ВИКЛЮЧНЕ АБО й порахувати кількість бітів зі значенням 1 в отриманому результаті. Число бітових позицій, по яких розрізняються два слова, називається інтервалом Хеммінга. Якщо інтервал Хеммінга для двох слів дорівнює d, це означає, що достатньо d бітових помилок, щоб перетворити одне слово в інше. Наприклад, інтервал Хеммінга кодованих слів 11110001 і 00110000 дорівнює 3, оскільки для перетворення першого слова в друге досить 3 помилок у біт. Пам'ять складається з m-бітних слів, і, отже, існує 2^m варіантів поєднання бітів. Кодовані слова складаються з n бітів, але через спосіб підрахунку контрольних розрядів припустимі тільки 2^т з 2" кодованих слів. Якщо у пам'яті виявляється неприпустиме кодоване слово, комп'ютер знає, що сталася помилка. При наявності алгоритму для підрахунку контрольних розрядів можна скласти повний список доступних кодованих слів і з цього списку знайти два слова, для яких інтервал Хеммінга буде мінімальним. Це інтервал Хеммінга повного коду. Властивості перевірки і виправлення помилок певного коду залежать від його інтервалу Хеммінга. Щоб виявити d помилок у бітах, необхідний код з інтервалом d+1, оскільки d помилок не можуть змінити одне допустиме кодоване слово на інше допустиме кодоване слово. Відповідно, щоб виправити d помилок у бітах, необхідний код з інтервалом 2d+l, оскільки в цьому випадку допустимі кодовані слова так сильно відрізняються один від одного, що навіть якщо станеться d змін, початкове кодоване слово буде ближче до помилкового, ніж будь-яке інше кодоване слово, тому його легко можна буде визначити.

В якості простого прикладу коду з виявленням помилок розглянемо код, в якому до даних приєднується один біт парності. Біт парності вибирається таким чином, що число бітів зі значенням 1 в кодованому слові парне (або непарне). Інтервал цього коду дорівнює 2, оскільки будь-яка помилка в бітах призводить до кодованого слова з неправильною парністю. Іншими словами, достатньо двох помилок у бітах для переходу від одного допустимого кодованого слова до іншого допустимого слова. Такий код може використовуватись для виявлення одиночних помилок. Якщо з пам'яті зчитується слово, що містить неправильну парність, надходить сигнал про помилку. Програма не зможе продовжуватись, але зате не буде невірних результатів.

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

0000000000, 0000011111, 1111100000 і 1111111111

Інтервал цього коду дорівнює 5. Це означає, що він може виправляти подвійні помилки. Якщо з'являється кодоване слово 0000000111, комп'ютер знає, що початкове слово повинно бути 0000011111 (якщо сталося не більше двох помилок). При наявності трьох помилок, якщо, наприклад, слово 0000000000 змінилося на 0000000111, цей метод не допускається. Уявімо, що хочемо розробити код m з бітами даних і р контрольних розрядів, який дозволив би виправити всі помилки в бітах. Кожне з 2^r допустимих слів має n неприпустимих кодованих слів, які відрізняються від допустимого одним бітом. Вони утворюються інвертуванням кожного з n бітів n-бітовому кодованому слові. Отже, кожне з 2^r допустимих слів вимагає п+1 можливих поєднань бітів, які приписуються цьому слову (п можливі помилкові варіантів і один правильний). Оскільки загальна кількість різних поєднань бітів дорівнює 2ⁿ, то (n+l) 2^m < 2ⁿ.

Оскільки n=m+r, отже, (m+r+1)< 2^r. Ця формула дає нижню межу числа контрольних розрядів, необхідних для виправлення одиничних помилок. У табл. 1.3 показано необхідну кількість контрольних розрядів для слів різного розміру.

Табл.1.3 – Розмірність коду

Розмір слова	Кількість контрольних розрядів	Загальний розмір	% збільшення довжини слова
8 16 32 64 128 256 512	4 5 6 7 8 9 10	12 21 38 71 136 265 522	50 31 19 11 6 4 2

Цієї теоретичної нижньої межі можна досягти, використовуючи метод Річарда Хеммінга. В коді Хеммінга до речі, що складається з m бітів, додається r біт парності, при цьому утворюється слово довжиною m+r бітів. Біти нумеруються з одиниці (а не з нуля), причому першим вважається крайній лівий. Всі біти, номери яких – ступеня двійки, є бітами парності; інші використовуються для даних. Наприклад, до 16-бітного слова потрібно додати 5 біт парності. Біти з номерами 1, 2, 4, 8 та 16 – біти парності, а всі інші - біти даних. Всього слово містить 21 біт (16 біт даних і 5 біт парності). У розглянутому прикладі будемо використовувати позитивну парність (довільний вибір). Кожен біт парності перевіряє певні бітові позиції. Загальне число бітів зі значенням 1 в позиціях, що перевіряються повинно бути парним. Нижче наведено позиції перевірки для кожного біта парності: