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

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

Щоб зрозуміти, як усунути помилки, необхідно визначити, що являють собою ці помилки. Припустимо, що слово складається з 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. Число контрольних розрядів для коду, здатного виправляти одиночні помилки

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

А A А Помилка

С 0 0 C 0 1

1 1 1 1 1 1 1 1 С

0 0 0

0 0

Біти

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