го рядок помилок e = e 1 e 2 ... e n ,, отже приймач пріймає сигнал c = c 1 c 2 ... c n ,, де c i = b i + e i .. Система, что віправляє помилки, перекладати слово c 1 c 2 ... c n у найближче кодове слово b 1 b 2 ... b n .. Система, что віявляє помилки, Тільки встановлює, чи є прийнятя слово кодовий чи ні. Останнє означає, что при передачі Відбулася помилка. p> Ідею представлення код, что коректують, можна представіті помощью N-вімірного куба.
Візьмемо трівімірній куб (мал. 2), довжина ребер, в якому дорівнює одній одініці. Вершини такого куба відображають двійкові коди. Мінімальна відстань между вершинами візначається мінімальною кількістю ребер, что знаходяться между вершинами. Ця відстань назівається кодовий (або хемінговою) i позначається буквою d.
В
Малюнок 2 - Представлення двійковіх код за помощью куба
Інакше, кодовий відстань - це ті мінімальне число ЕЛЕМЕНТІВ, в якіх одна кодовий комбінація відрізняється від Іншої. Для визначення кодової відстані й достатньо порівняті Дві кодові комбінації за модулем 2. Так, склавші Дві комбінації
10110101101
11001010101
01111111000
візначімо, что відстань между ними d = 7.
Для кодом з N = 3 Вісім кодовий комбінацій розміщуються на вершинах трівімірного куба. Такий код має кодовий відстань d = 1, и для передачі Використовують ВСІ Вісім кодовий комбінацій 000,001 .., 111. Такий код є НЕ перешкодостійкім, ВІН не в змозі віявіті помилки.
Если віберемо комбінації з кодовими відстанню d = 2, Наприклад, 000,110,101,011, то такий код дозволити віявляті одноразові помилки. Назвемо ці комбінації дозволеними, призначеня для передачі ІНФОРМАЦІЇ. Всі Останні 001,010,100,111 - Заборонені. p> Будь-яка одиночна помилка приводити до того, что дозволена комбінація переходити в найближче, Заборонений комбінацію (дів. малий. 2). Отримай Заборонений комбінацію, мі віявімо помилки. Віберемо далі вершини з кодовими відстанню d = 3
В
такий код может виправити одну одиночну помилки або віявіті Дві помилки. Таким чином, збільшуючі кодовий відстань можна збільшити перешкодостійкість коди. У Загальне випадка кодовий відстань візначається по Формулі
d = t + l + 1
де t - число помилок, что віправляються, l - число помилок, что віявляються. Зазвічай l> t. p> Більшість кодів, что коректують, утворюються Шляхом додавання до початкової k - комбінації r - контрольних сімволів. У результаті в лінію передаються n = k + r сімволів. При цьом коди, что коректують, назіваються (n, k) кодами. Як можна візначіті необхідне число контрольних сімволів?
Для побудова коди здатн віявляті и віправляті одиночному помилки необхідне число контрольних розрядів складатіме. Це рівносільно відомому Завдання про мінімум числа контрольних харчування, на Які могут буті дано ВІДПОВІДІ вигляд "Та чи ні", для однозначного визначення одного з ЕЛЕМЕНТІВ кінцевої множини. p> Если звітність, виправити Дві помилки, то число різніх результатів складатіме Тоді, в цьом випадка віявляються одноразові и двократні помилки. У загально випадка, число контрольних сімволів має буті не менше
В
Ця формула назівається нерівністю Хеммінга, або Нижнім межею Хеммінга для числа контрольних сімволів.
матричного кодування
При явному завданні схеми кодування в (m, n)-коді слід вказаті 2 m кодовий слів, что вельми неефективно.
Одним з економних способів Опису схеми кодування є методика матричного кодування.
Хай - матриця порядку mfn з елементами e ij , рівнімі 0 або 1. Символ + позначає складання по модулю 2. Тоді схема кодування задається системою рівнянь
В
або в матрічній ФОРМІ b = aЕ, де a = a 1 a 2 ... a m - вектор, відповідній передаванням повідомленню; b = b 1 b 2 ... b n - Вектор, відповідній кодованому повідомленню; Е - матриця коду, что породжує. p> Матриця коду, что породжує, Визначи неоднозначно. Код не винних пріпісуваті різнім словами-повідомленням Одне и ті ж кодове слово. Можна довести, что цього НЕ Відбудеться, ЯКЩО Перші m стовпців матріці Е утворюють одінічну матрицю.
Замість 2 m кодові слова й достатньо знаті m слів, что є рядками матріці Є.
Групові коди
Безліч всех двійковіх слів a = a 1 ... a m Довжина m утворює абелеву (Комутатівну) групу Щодо порозрядно складання. p> Хай E - кодуюча-матриця, у Якої є-підматріця з відміннім від нуля Визначник, Наприклад, одінічна. Тоді відображення переводити групу всех двійковіх слів Довжина m в групу кодових слів Довжина n.
Припустиме, что
.
