3.8. Код з виправленням помилок

Пам'ять комп'ютера час від часу може робити помилки через сплески напруги на лінії електропередачі і з інших причин. Для боротьби з такими помилками, використовуються коди з виявленням і виправленням помилок. При цьому до кожного слова в пам'яті особливим чином додаються додаткові біти. Коли слово зчитується з пам'яті, ці біти перевіряються на наявність помилок.

Щоб зрозуміти, як усунути помилки, необхідно визначити, що являють собою ці помилки. Припустимо, що слово складається з m бітів даних, до яких додаються r додаткових бітів (контрольних розрядів). Нехай загальна довжина слова буде n (тобто n=m+r). n-бітну одиницю, що містить m бітів даних і r контрольних розрядів, часто називають кодованим словом.

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

Пам'ять складається з m-бітних слів, і отже, існує 2^m варіантів сполучення бітів. Кодовані слова складаються з п бітів, але внаслідок способу підрахунку контрольних розрядів припустимі тільки 2^m з 2ⁿ кодованих слів. Якщо в пам'яті виявляється неприпустиме кодоване слово, комп'ютер знає, що відбулася помилка. При наявності алгоритму для підрахунку контрольних розрядів можна скласти повний список припустимих кодованих слів і з цього списку знайти два слова, для яких інтервал Хеммінга буде мінімальним. Це інтервал Хеммінга повного коду.

Властивості перевірки і виправлення помилок визначеного коду залежать від його інтервалу Хеммінга. Щоб знайти d помилок у бітах, необхідний код з інтервалом d+1, оскільки d помилок не можуть змінити одне припустиме кодоване слово на інше припустиме кодоване слово. Відповідно, щоб виправити d помилок у бітах, необхідний код з інтервалом 2d+l, оскільки в цьому випадку припустимі кодовані слова так сильно відрізняються друг від друга, що навіть якщо відбудеться d змін, вихідне кодоване слово буде ближче до помилкового, чим будь-яке інше кодоване слово, тому його без зусиль можна буде визначити.

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

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

0000000000, 0000011111, 1111100000 і 1111111111

Інтервал цього коду дорівнює 5. Це значить, що він може виправляти подвійні помилки. Якщо з'являється кодоване слово 0000000111, комп'ютер знає, що вихідне слово повинно бути 0000011111 (якщо відбулося не більш двох помилок). При наявності трьох помилок, якщо, наприклад, слово 0000000000 змінилося на 0000000111, цей метод неприпустимий.

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

Таблиця 3.1. Число контрольних розрядів для коду, здатного виправляти одиночні помилки

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

Цієї теоретичної нижньої межі можна досягти, використовуючи метод Хеммінга. Але перш ніж звернутися до цього алгоритму, розглянемо просту графічну схему, що чітко ілюструє ідею коду з виправленням помилок для 4-бітних слів. Діаграма Венна на рис. 4 містить 3 кола, А, В і С, що разом утворюють сім секторів. Закодуємо як приклад слово з 4 бітів 1100 у сектори АВ, ABC, AC і ВС, по одному біту в кожному секторі (за абеткою). Кодування показане на рис.3.4, а.

А A А Помилка

0 С 0 0 C 0 1

1 1 1 1 1 1 1 1 С

0 0 0

0 0

Біти

B B парності В

Рис.4. Кодування числа 1100 (а); додаються біти парності (б); помилка в секторі АС (в)

Далі додамо біт парності до кожного з трьох порожніх секторів, щоб вийшла позитивна парність, як показано на рис.3.4,б. По визначенню сума бітів у кожному із трьох кіл, А, В, і С, повинна бути парною. У колі А знаходиться 4 числа: 0, 0, 1 і 1, що у сумі дають парне число 2. У колі В знаходяться числа 1, 1, 0 і 0, що також при додаванні дають парне число 2. Те ж і для кола С. У даному прикладі вийшло так, що всі суми однакові, але взагалі можливі випадки із сумами 0 і 4. Малюнок відповідає кодованому слову, що складається з 4 бітів даних і 3 бітів парності.

Припустимо, що біт у секторі АС змінився з 0 на 1, як показано на рис.3.4, в. Комп'ютер бачить, що кола А і С мають негативну парність. Єдиний спосіб виправити помилку, змінивши тільки один біт, – повернення бітові АС значення 0. Таким способом комп'ютер може виправляти одиночні помилки автоматично.

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

Кожен біт парності перевіряє визначені бітові позиції. Загальне число бiтiв зі значенням 1 у позиціях, що перевіряються, повинне бути парним. Нижче зазначені позиції перевірки для кожного біта парності:

Біт 1 перевіряє біти 1, 3, 5, 7, 9,11,13,15, 17, 19, 21.

Біт 2 перевіряє біти 2, 3, 6, 7, 10, 11, 14,15, 18, 19.

Біт 4 перевіряє біти 4,5, 6,7,12,13,14,15,20, 21.

Біт 8 перевіряє біти 8, 9, 10,11,12,13, 14, 15.

Біт 16 перевіряє біти 16,17,18,19,20, 21.

У загальному випадку біт b перевіряється бітами Ьь D2,..., Ь,, такими що bi+b₂+.. ,+bj-b. Наприклад, біт 5 перевіряється бітами 1 і 4, оскільки 1+4=5. Біт 6 перевіряється бітами 2 і 4, оскільки 2+4-6 і т.д.

На Рис. 2.12 показана побудова коду Хэмминга для 16-бітного слова 1111000010101110. Відповідним 21-бітним кодованим словом є 001011100000101101110. Щоб побачити, як відбувається виправлення помилок, розглянемо, що відбудеться, якщо біт 5 змінить значення через різкий стрибок напруги на лінії електропередачі. У результаті замість кодованого слова 001011100000101101110 вийде 001001100000101101110. Будуть перевірені 5 бітів парності. От результати перевірки:

Біт парності 1 неправильний (біти 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21 містять п'ять одиниць).

Біт парності 2 правильний (біти 2,3,6,7,10,11,14,15,18,19 містять шість одиниць).

Біт парності 4 неправильний (біти 5,6,7,12,13,14,15,20,21 містять п'ять одиниць).

Біт парності 8 правильний (біти 8,9,10,11,12,13,14,15 містять дві одиниці).

Біт парності 16 правильний (біти 16,17,18,19,20,21 містять чотири одиниці).

Загальне число одиниць у бітах 1, 3, 5, 7, 9, 11, 13, 15, 17, 19 і 21 повинно бути парним, оскільки в даному випадку використовується позитивна парність. Неправильним повинний бути один з бітів, що перевіряються бітом парності 1 (а саме 1, 3,5,7,9,11,13,15,17,19 і 21). Біт парності 4 теж неправильний. Це значить, що змінив значення один з наступних бітів: 4,5,6,7,12,13,14,15,20, 21. Помилка повинна бути в біті, що утримується в обох списках. У даному випадку загальними є біти 5,7,13,15 і 21. Оскільки біт парності 2 правильний, біти 7 і 15 виключаються. Правильність біта парності 8 виключає наявність помилки в біті 13. Нарешті, біт 21 також виключається, оскільки біт парності 16 правильний. У підсумку залишається біт 5, у якому й утримується помилка. Оскільки цей біт має значення 1, він повинний прийняти значення 0. Саме в такий спосіб виправляються помилки.

Щоб знайти неправильний біт, спочатку потрібно підрахувати всі біти парності. Якщо вони правильні, помилки немає (або є, але більше однієї). Якщо виявилися неправильні біти парності, то потрібно скласти їхнього номера. Сума, отримана в результаті, дасть номер позиції неправильного біта. Наприклад, якщо біти парності 1 і 4 неправильні, а 2,8 і 16 правильні, то помилка відбулася в біті 5 (1+4).