Навчально-методичний центр мовної підготовки АВТФ кц
1.3. Кодова відстань і виправлення помилок
Одним з найважливіших параметрів коду є кодова відстань. Кодовою відстанню або просто відстанню коду V називається мінімальна відстань між двома різними кодовими словами, т. Е.
Для двійкового коду V під відстанню розуміється відстань Хеммінга.
Теорема 1.1. Код V виправляє все комбінації з t-менш помилок, якщо і тільки якщо кодове відстань не менше, аніж 2t +1, т. Е. DV ≥ 2t +1.
Доказ теореми грунтується на побудові сфер з радіусом t навколо кожного кодового слова. Для того щоб кожна помилка кратності t була виправлена, слово з такою помилкою повинно міститися всередині сфери, описаної тільки навколо одного кодового слова. Таким чином, відстань між центрами двох сфер, т. Е. Різними кодовими словами повинно бути не менше 2t +1. Геометрична ілюстрація приведена на рис. 3.
Теорема 1.2. Код V виявляє все комбінації з t-менш помилок, якщо і тільки якщо кодове відстань не менше, аніж t +1, тобто dV ≥ t +1.
Для того, щоб кожна помилка кратності t була виявлена, слово з такою помилкою не повинно бути кодовою, т. Е. Відстань між будь-якими різними кодовими словами повинно бути більше t.
Рис 3. Сфери, центрами яких є кодові слова.
Наприклад, код з відстанню 3 виправляє все поодинокі помилки і виявляє все дворазові помилки. Код з відстанню 4 виявляє всі помилки кратності 3 та менше; однак такий код і раніше виправляє тільки одну помилку.
Завдання побудови реального коду, т. Е. Коду, довжина слів в якому досягає сотень символів, із заданим кодовою відстанню не наважується повним перебором навіть з використанням сучасної обчислювальної техніки. Теорія кодування пропонує методи для побудови таких кодів.
Приклад. Як приклад спробуємо побудувати код з кодовим словом довжини 5, який має 3 інформаційних символу і виправляє одну помилку. Так як інформаційних символів три, то різних кодових слів повинно бути 2 3 = 8. Згідно з теоремою 1.1 відстань між двома різними кодовими словами повинно бути не менше 2 × 1 + 1 = 3. Включимо в код V слово 00000. Тоді всі інші кодові слова мають вагу не менше 3. Після включення в код V будь-якого слова ваги 3, жодне слова ваги 3 в код додано бути не може, так як відстань між будь-якими двома словами ваги 3 дорівнює 2. З тієї ж причини слово 11111 ваги 5 теж належить коду V. Залишаються 5 слів ваги 4, яких не достатньо, щоб мати 8 кодових слів.