. Декодер ототожнює прийняту кодограмою В * тієї дозволеної кодограмою, для якої вектор помилок має найменше число одиниць.
Безліч дозволених кодових слів в таблиці декодування (перший рядок таблиці 1) є підмножиною множини всіх 2 n кодограм розрядністю n . У процесі побудови таблиці декодування безліч кодограм розрядністю n розбивається на підмножини (стовпчики таблиці декодування). Причому спочатку виписуються заборонені кодограми з одиночною помилкою, як найімовірнішою, потім кодограми з двома помилками і так далі.
У разі, коли код виправляє g помилок, підмножини є непересічними, а число заборонених кодограм Ne в стовпці повинно задовольняти нерівності [1, 22]
, (2.8)
де C ni =- число сполучень із n елемнтов по i .
Нерівність (2.8) випливає безпосередньо з того, що є рівно заборонених кодограм, що відрізняються від дозволеної в одній позиції, заборонених кодограм, що відрізняються в двох позиціях і так далі.
Тепер можна зв'язати надмірність коду з числом помилок, які їм виправляються. Зауважимо спочатку, що число всіляких кодограм 2 n , а кожен стовпець таблиці 1 містить Ne заборонених кодограм. Тому число дозволених кодограм повинно задовольняти нерівності
. (2.9)
шифрування інформація криптоалгоритм кодування
Ця нерівність називається кордоном Хеммінга або кордоном сферичної упаковки. Рівність у (2.9) досягається тільки для так званих досконалих кодів. Число відомих досконалих кодів дуже невелика. Коди, гарантовано виправляють одну помилку відносять до кодів Хеммінга. Для них умова (2.9) перетвориться до виду
. (2.10)
При дослідженні кодів з виправленням помилок інтерес представляє ймовірність появи на виході декодера помилковою послідовності. При незалежних помилках на підставі теореми Бернуллі ймовірність появи в n - розрядної кодограмою рівно m помилок визначається біноміальним розподілом
P ( m , n )=C nmp 0 m ( 1 - p 0) nm , при 0? m ? n . (2.11)
Якщо наведений в таблиці 1 код використовується виключно для виявлення помилок, то ймовірність правильного прийому дорівнює (1 - p 0) 5.
Необхідно зауважити, що для різних каналів властивості завадостійких кодів можуть використовуватися по-різному. Раніше передбачалося, що канал зв'язку двійковий симетричний. У двійковому симетричному каналі зі стиранням може розглядатися режим тільки виправлення стертих символів, оскільки отримання стертого символу вже свідчить про помилку. Визначимо можливості коригувальних кодів стосовно виправлення стертих символів. Припустимо, що стирання окремих символів - події незалежні, число стертих символів в кодограмою (кратність стирок) позначимо через t с і припустимо, що всі нестерті символи прийняті правильно. При цьому, прийнявши кодограмою з t з стиранням, утворюємо укорочений код розрядністю ( n - t с). Для цього в усіх дозволених кодограмою необхідно викреслити розряди, стерті в прийнятій кодограмою.
Для того, щоб кодограми укороченого коду були різні, відстань між ними пови...
