Лінійний код

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

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

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


де 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. Отже, даний код здатний:

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

Примітки[ред.ред. код]

  1. William E. Ryan and Shu Lin (2009). Channel Codes: Classical and Modern. Cambridge University Press. с. 4. ISBN 978-0-521-84868-8. 
  2. MacKay, David, J.C. (2003). Information Theory, Inference, and Learning Algorithms. Cambridge University Press. с. 9. ISBN 9780521642989. «In a linear block code, the extra bits are linear functions of the original bits; these extra bits are called parity-check bits» 
  3. Thomas M. Cover and Joy A. Thomas (1991). Elements of Information Theory. John Wiley & Sons, Inc. с. 210–211. ISBN 0-471-06259-6. 

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