Лінійний код

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

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

${\displaystyle {\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}},\qquad {\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 — це лінійний підпростір C з розмірністю k векторного простору ${\displaystyle \mathbb {F} _{q}^{n}}$, де ${\displaystyle \mathbb {F} _{q}}$ — скінченне поле з q елементами. Такий код має назву «q-нарний код». Якщо q = 2 або q = 3, код описується як бінарний або тернарний відповідно. Вектори в C називаються кодовими словами. Розмір коду — це кількість кодових слів та дорівнює q^k.

Вага кодового слова — це кількість його ненульових елементів, а відстань між двома кодовими словами — це відстань Геммінга, яка є кількістю елементів, які в них відрізняються. Відстань d лінійного коду — це мінімальна вага його ненульових кодових слів або, еквівалентно, мінімальна відстань між різними кодовими словами. Лінійний код довжини n, розмірності k та відстані d називається [n,k,d] код.

Ми хочемо використовувати у ${\displaystyle \mathbb {F} _{q}^{n}}$ стандартний базис, оскільки кожна координата являє собою «біт», який передається через «канал з шумом» з деякою невеликою ймовірністю помилки передачі (). Якщо використовувати якийсь інший базис, тоді ця модель буде не придатна, бо відстань Геммінга не буде вимірювати кількість помилок при передачі, як нам би того хотілося.

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

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

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

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

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

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

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

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

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

Приклад: код Адамара

Докладніше: Код Адамара

Код Адамара — це ${\displaystyle [2^{r},r,2^{r-1}]_{2}}$ лінійний код, який дає можливість виправити багато помилок. Код Адамара можна побудувати за стовпцями: ${\displaystyle i^{th}}$ стовпець — це біти побітового представлення цілого числа ${\displaystyle i}$, див. наступний приклад. Код Адамара має мінімальну відстань ${\displaystyle 2^{r-1}}$, отже може виправити ${\displaystyle 2^{r-2}-1}$ помилку.

Приклад: Лінійний код з наступною породжувальною матрицею — це ${\displaystyle [8,3,4]_{2}}$ код Адамара: ${\displaystyle {\boldsymbol {G}}_{Had}={\begin{pmatrix}0\ 0\ 0\ 0\ 1\ 1\ 1\ 1\\0\ 0\ 1\ 1\ 0\ 0\ 1\ 1\\0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\end{pmatrix}}}$.

Код Адамара — це окремий випадок . Якщо взяти перший стовпець (нульовий стовпець) з ${\displaystyle {\boldsymbol {G}}_{Had}}$, то ми отримаємо ${\displaystyle [7,3,4]_{2}}$ симплексний код, який є подвійним кодом коду Хеммінга.

Алгоритм найближчого сусіда

Параметр d тісно пов'язаний із можливістю виправляти помилки коду. Наступний алгоритм це ілюструє (та має назву «алгоритм найближчого сусіда»):

Вхідні дані: отриманий вектор v в ${\displaystyle \mathbb {F} _{q}^{n}}$.

Вихідні дані: кодове слово ${\displaystyle w}$ в ${\displaystyle C}$ найближчий до ${\displaystyle v}$, якщо таке існує.

• Починаючи з ${\displaystyle t=0}$, повторюються наступні 2 кроки.
• Перебрати елементи кулі радіусу ${\displaystyle t}$ навколо отриманого слова ${\displaystyle v}$, позначеної ${\displaystyle B_{t}(v)}$.
  • Для кожного ${\displaystyle w}$ в ${\displaystyle B_{t}(v)}$ треба перевірити чи належить ${\displaystyle w}$ до ${\displaystyle C}$. Якщо це вірно, тоді ${\displaystyle w}$ — рішення.
• Збільшити t на 1. Припинити лише коли ${\displaystyle t>(d-1)/2}$, тоді перебір закінчено та не знайдено жодного рішення.

Лінійний код ${\displaystyle C}$ називається виправляючим ${\displaystyle t}$-помилку, якщо є щонайбільше одне кодове слово в ${\displaystyle B_{t}(v)}$ для кожного ${\displaystyle v}$ у ${\displaystyle \mathbb {F} _{q}^{n}}$.

Поширене позначення

Коди загалом часто позначаються літерою C, а код довжини n і рангу k (тобто код, який має n кодових слів у своїй основі та k рядків у його породжувальній матриці) зазвичай називають (n, k) код. Лінійні коди часто позначаються [n, k, d] кодами, де d  означає мінімальну відстань коду Хеммінга між будь-якими двома кодовими словами. ([n, k, d] позначення не слід плутати з (n, M, d) позначенням, яке використовується для позначення нелінійного коду довжиною n, розміром M (тобто має M кодових слів) та мінімальною відстанню Хеммінга d.)

Примітки

1. William E. Ryan and Shu Lin (2009). Channel Codes: Classical and Modern. Cambridge University Press. с. 4. ISBN .
2. (2003). (PDF). Cambridge University Press. с. 9. ISBN . Архів оригіналу (PDF) за 19 жовтня 2016. Процитовано 19 грудня 2017. In a linear block code, the extra ${\displaystyle N-K}$ bits are linear functions of the original ${\displaystyle K}$ 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 .

Джерела