§6. Коди, що виправляють помилки.
Будемо розглядати всі можливі двійкові
слова довжини
у якості символів деякого алфавіту
(де
).
Якщо поставити у відповідність кожному
такому слову його код Хеммінга довжини
ми одержимо схему кодування
.
(13)
Основна властивість одержаної схеми
кодування полягає в тому, що зробивши
одну помилку в будь-якому кодовому слові
,
ми все одно можемо визначити символ
,
який воно кодує.
Цю властивість можна узагальнити.
Розглянемо, тепер, довільний алфавіт
і довільну схему кодування (13). Нехай
– ціле додатне число. Припустимо, що
зробивши у будь-якому з кодових слів
не більше ніж
помилок, ми все одно завжди можемо
однозначно відновити символ
,
який воно кодує. Тоді кодова функція,
задана схемою (13) називається кодуванням,
що виправляє
помилок.
В подальшому будемо вважати, що всі
кодові слова схеми (13) мають однакову
довжину
.
Нехай
– двійковий алфавіт,
– множина двійкових слів довжини
.
Нехай
,
– два елементи
.
Відстанню
між цими елементами називається кількість
значень індексу
,
для яких
.
Теорема 6. Множина разом з відстанню утворюють метричний простір.
Доведення. Перші дві аксіоми метрики очевидні. Для перевірки третьої аксіоми зазначимо, що відстань між елементами , множини може бути обчислена за формулою
.
Розглянемо елементи
.
.
Отже третя аксіома теж виконується. Теорема доведена.
Позначимо через
схему кодування (13). Кодовою відстанню
схеми
називається найменша з відстаней між
її кодовими словами:
.
Поняття кодової відстані дозволяє сформулювати критерій того, що кодування виправляє помилок.
Теорема 7. Кодування виправляє помилок тоді й лише тоді, коли кодова відстань задовольняє нерівності
.
(14)
Доведення. Достатність. Нехай кодова
відстань схеми
задовольняє нерівності (14). Візьмемо
довільне кодове слово
і зробимо у ньому
помилок. Одержане при цьому нове слово
знаходиться від
на відстані
,
отже
.
Якщо знайдеться якесь інше слово
,
,
таке що
,
то ми будемо мати
,
що суперечить умові (14).
Отже для всіх відмінних від
кодових слів
.
Це означає, що ми завжди можемо відновити
правильне слово
,
вибравши з кодових слів найближче до
.
Необхідність. Припустимо, що кодування
виправляє
помилок, але умова (14) порушується. Тоді
існують кодові слова
,
такі що
.
В цьому разі