Лінійний код

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Лінійний код у теорії кодування - код з виправленням помилок, для якого будь-яка лінійна комбінація кодових слів також є кодовим словом. Лінійні коди традиційно розділяють на блокові коди і згорткові коди, хоча турбо-коди можна розглядати як гібрид цих двох типів. Лінійні коди, в порівнянні з іншими кодами, дозволяють реалізовувати більш ефективні алгоритми кодування і декодування інформації.

Лінійні коди використовуються при попередній корекції помилок і застосовуються для передачі символів (наприклад, біт) через канал зв'язку, так що, якщо відбуваються помилки в повідомленні, деякі помилки можуть бути виправлені або виявлені при отриманні блоку. Кодові слова в лінійному блоковому коді є блоком символів, які кодуються з використанням більшої кількості символів, ніж у даних для відправки. Лінійний код довжини N передає блоки, що містять N символів. Так, наприклад, [7,4,3] код Хеммінга є лінійний двійковий код, який представляє 4-бітові повідомлення з використанням 7-розрядних кодових слів. Два різних кодових слова розрізняються принаймні в трьох бітах. Як наслідок, до двох помилок на кодове слово може бути виявлено і одна помилка може бути виправлена. Цей код містить 24 = 16 кодових слів.

\boldsymbol{G}=\begin{pmatrix} 1\ 1\ 0\ 1\ 0\ 0\ 0 \\ 0\ 1\ 1\ 0\ 1\ 0\ 0 \\ 1\ 1\ 1\ 0\ 0\ 1\ 0 \\ 1\ 0\ 1\ 0\ 0\ 0\ 1 \end{pmatrix}   ,  : \boldsymbol{H}=\begin{pmatrix} 1\ 0\ 0\ 1\ 0\ 1\ 1 \\ 0\ 1\ 0\ 1\ 1\ 1\ 0 \\ 0\ 0\ 1\ 0\ 1\ 1\ 1  \end{pmatrix}

де G - породжувальна матриця; H - матриця перевірки парності.

Допустимі і недопустимі комбінації[ред.ред. код]

Як уже відзначалося, завадостійкість кодування забезпечується за рахунок внесення надмірності в кодові комбінації. Це значить, що з n символів кодової комбінації для передачі інформації використовується k < n символів. Отже, із загального числа No=2n можливих кодових комбінацій для передачі інформації використовується тільки N = 2k комбінацій. Відповідно до цього вся множина No=2n можливих кодових комбінацій поділяється на дві групи. У першу групу входить множина N = 2k дозволених комбінацій, друга група містить у собі множину (No - N) = 2n-2k заборонених комбінацій.

Якщо на стороні приймання встановлено, що прийнята комбінація відноситься до групи дозволених, то вважається, що сигнал прийшов без перекручувань. В іншому випадку робиться висновок, що прийнята комбінація перекручена. Однак це справедливо лише для таких перешкод, коли усунута можливість переходу одних дозволених комбінацій в інші.

Коригуюча здатність коду[ред.ред. код]

Коригуюча здатність коду визначається мінімальною кодовою відстанню. Складемо матрицю відстаней між кодовими комбінаціями для таких дозволених комбінацій: 00000; 01110; 10101; 11011.

Таблиця – Матриця відстаней

00000 01110 10101 11011
00000 0 3 3 4
01110 3 0 4 3
10101 3 3 0 3
11011 4 3 4 0

Як видно з матриці, мінімальна кодова відстань dmin=3. Отже, даний код здатний:

  • виявляти дворазові помилки;
  • усувати однократні помилки;
  • усувати і виявляти однократні помилки.

Джерела[ред.ред. код]