Лінійний код

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

Зміст

У процесі зберігання даних та передачі інформації по мережах зв'язку неминуче виникають помилки. Контроль цілісності даних та виправлення помилок – важливі завдання на багатьох рівнях роботи з інформацією (зокрема, фізичному, канальному, транспортному рівнях моделі OSI).

У системах зв'язку можливі кілька стратегій боротьби з помилками:

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

Коди виявлення та виправлення помилок

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

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

Зкодами, що виправляють помилки, тісно пов'язанікодивиявлення помилок. На відміну від перших, останні можуть встановити факт наявності помилки в переданих даних, але не виправити її.

Насправді, коди виявлення помилок, що використовуються, належать до тих же класів кодів, що і коди, що виправляють помилки. Фактично, будь-який код, що виправляє помилки, може бути використаний для виявлення помилок (при цьому він буде здатний виявити більше помилок, ніж був здатний виправити).

За способом роботи з даними коди, що виправляють помилки діляться наблокові, що ділять інформацію на фрагменти постійної довжини і обробляють кожен з них окремо, ізгорткові, що працюють з даними як з безперервним потоком.

Блокові коди

Нехай інформація, що кодується, ділиться на фрагменти довжиною $k$ біт, які перетворюються накодові словадовжиною $n$ біт. Тоді відповідний блоковий код зазвичай позначають $(n,k)$. У цьому число $R = \frac$ називаєтьсяшвидкістю коду.

Якщо вихідні $k$ біт код залишає незмінними, і додає $n-k$перевірочних, такий код називаєтьсясистематичним, інакшенесистематичним.

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

здатність виправляти якомога більше помилок,
якомога менша надмірність,
простота кодування та декодування.

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

Практично всевикористовуються коди є лінійними. Це з тим, що нелінійні коди значно складніше досліджувати, і їм важко забезпечити прийнятну легкість кодування і декодування.

Породжувальна матриця

Нехай вектори $\overrightarrow = (x_. x_), \overrightarrow = (x_. x_). \overrightarrow = (x_. x_)$ є базисом лінійного простору $C$. За визначенням базису, будь-який вектор $\overrightarrow \in C$ можна подати у вигляді лінійної комбінації базисних векторів: $\overrightarrow = \overrightarrow + \overrightarrow + . + \overrightarrow$, або в матричній формі, як:

Це співвідношення встановлює зв'язок між векторами коефіцієнтів $\overrightarrow = (,. )$ і векторами $\overrightarrow \in C$. Перераховуючи всі вектори коефіцієнтів $\overrightarrow = (,. ) $ можна отримати всі вектори $\overrightarrow \in C$. Іншими словами, матриця (G) породжує лінійний простір.

Перевірочна матриця

Іншим способом завдання лінійних просторів є опис через перевірочну матрицю.

Нехай $\mathbb$ - лінійний k-вимірний простір над полем $\mathbb_q$ і $\mathbb$ - ортогональне доповнення $\mathbb$. Тоді однією з теорем, розмірність $\mathbb$ дорівнює $r = n - k$. Тому в $\mathbb$ існує r базисних векторів. Нехай $\overrightarrow_1 = (_1>. _n>), \overrightarrow_2 = (_1>. _n>). \overrightarrow_r = (_1>. _n>) $ базис в $\mathbb$.

Тоді будь-який вектор $\overrightarrow \in C$ задовольняє наступній системі лінійних рівнянь:

\( \begin h_ x_1 + h_ x_2 + . + h_ x_n = 0 \\ h_ x_1 + h_ x_2 + . + h_ x_n = 0 \\ . \\ h_ x_1 + h_ x_2 + . + h_ x_n = 0 \end \ )

Або в матричній формі: $\overrightarrow H^T = 0$,

де $H =\begin \overrightarrow_1\\ \overrightarrow_2\\ . \\ \overrightarrow_r\\ \end = \begin h_ & h_ & .. & h_\\ h_ & h_ & .. & h_\\.. & .. & .. & ..\\ h_ & h_ & .. & h_\\end$ - перевірна матриця.

Наведену систему лінійних рівнянь слід розглядати як систему перевірок для всіх векторів лінійного простору, тому матриця $\mathbb$ називається перевірочною матрицею.

Лінійний коддовжиниnі рангуkє лінійним підпросторомCрозмірностіkвекторного простору $\mathbb_q^ n$, де $\mathbb_q$ - кінцевомірне поле з q елементів. Такий код з парметром q називається q - арним кодом (напр., якщоq= 5 — це 5-арний код). Якщоq= 2 абоq= 3, то код єдвійковий код, аботернарнийвідповідно.

Лінійний (блоковий) код— такий код, що множина йогокодових слівутворює $k$-вимірний лінійний підпростір (назвемо його $C$) в $n\ )-мірному лінійному просторі, ізоморфному просторі \(k$-бітних векторів.

Це означає, що операція кодування відповідає множенню вихідного $k$-бітного вектора на невироджену матрицю $G$, званународженою матрицею.

Нехай $C^$ - ортогональний підпростір по відношенню до $C$, а $H$ - матриця, що задає базис цього підпростору. Тоді для будь-якого вектора $\overrightarrow \in C$ справедливо: $$\overrightarrow H^T = \overrightarrow.$$

Мінімальна відстань і здатність коригувати

Відстанню Хеммінга(метрикою Хеммінга) між двома кодовими словами $\overrightarrow$ і $\overrightarrow$ називається кількість відмінних біт на відповідних позиціях, тоє число «одиниць» у векторі (overrightarrow oplus overrightarrow).

Мінімальна відстань$d$ лінійного коду є мінімальною з усіх відстаней Хеммінгу всіх пар кодових слів.

Вага вектора- відстань Хемінг між цим вектором і нульовим вектором, іншими словами - число ненульових компонент вектора.

Мінімальна відстань лінійного коду дорівнює мінімальному з ваг Хеммінгу ненульових кодових слів:

$d = min_ \in C, \overrightarrow \not = 0>( w( \overrightarrow) )$

Відстань між двома векторами $d(\overrightarrow, \overrightarrow)$ задовольняє рівності $d(\overrightarrow, \overrightarrow) = w(\overrightarrow - \overrightarrow)$, де $w( \overrightarrow)$ - вага Хеммінгу вектора \ (\ overrightarrow \). З того, що різниця будь-яких двох кодових слів лінійного коду також є кодовим словом лінійного коду, випливає затвердження теореми: $d = min_ \in C, \overrightarrow \not = 0>( w( \overrightarrow) )$

Мінімальна відстань Хеммінга$d$ є важливою характеристикою лінійного блокового коду. Вона визначає іншу, не менш важливу характеристику -коригуючу здатність: $$t = \mathcal\frac\mathcal,$$ тут кутові дужки позначають округлення «вниз».

Коригуюча здатність визначає, скільки помилок код можегарантовановиправити.

Пояснимо на прикладі. Припустимо, що є два кодові слова A і B, відстань Хеммінга між ними дорівнює 3. Якщо було передано слово A, і канал вніс помилку в одному биті, вона може бути виправлена, тому що навіть у цьому випадку прийняте слово ближче до кодового слова A , ніж B. Але якщо каналом було внесено помилки у двох бітах, декодер може вважати, що було передано слово B.

Теорема 2 (бездокази):

Якщо будь-які стовпці перевірочної матриці H лінійного (n,k)-коду лінійно незалежні, то мінімальна відстань коду дорівнює щонайменше d. Якщо при цьому знайдуться d лінійно залежні стовпці, то мінімальна відстань коду дорівнює d точності.

Теорема 3 (без доказу):

Якщо мінімальна відстань лінійного (n,k)-коду дорівнює d, то будь-які стовпці перевірочної матриці H (l \) лінійно незалежні і знайдуться d лінійно залежних стовпців.

Коди Хеммінгу

Коди Хеммінга - найпростіші лінійні коди з мінімальною відстанню 3, тобто здатні виправити одну помилку. Код Хеммінгу може бути представлений у такому вигляді, щосиндром$$\overrightarrow=\overrightarrow H^T,$$ де $\overrightarrow$ - прийнятий вектор,

дорівнюватиме номеру позиції, в якій сталася помилка. Ця властивість дозволяє зробити декодування дуже простим.

Загальний метод кодування лінійних кодів

Лінійний код довжини n з k інформаційними символами є k-вимірним лінійним підпростором, тому кожне кодове слово єлінійної комбінаціїбазисних векторів $\overrightarrow = (g_. g_), \overrightarrow = (g_. g_). \overrightarrow = (g_. g_)$ підпростору:

$\overrightarrow = \overrightarrow + \overrightarrow + . + \overrightarrow$.

Або за допомогою матриці, що породжує:

$\overrightarrow = \overrightarrow G = (,. ) \begin g_ & g_ & .. & g_\\ g_ & g_ & .. & g_\\ .. & .. & . .&..\\g_&g_&..&g_\\end$, де \(\overrightarrow = (. ), .

Це співвідношення єправило кодування, яким інформаційне слово $\overrightarrow = (. )$ відображається в кодове$\overrightarrow = (. )$

Загальний метод декодування лінійних кодів

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

Для лінійних кодів цей спосіб можна значно спростити. При цьому для кожного прийнятого вектора $\overrightarrow$ обчислюєтьсясиндром$\overrightarrow=\overrightarrow H^T$. Оскільки $\overrightarrow = \overrightarrow + \overrightarrow$, де $\overrightarrow$ - кодове слово, а $\overrightarrow$ - вектор помилки, то $\overrightarrow=\overrightarrow H^T$. Потім за допомогою таблиці синдромом визначається вектор помилки, за допомогою якого визначається передане кодове слово. При цьому таблиця виходить набагато менше, ніж під час використання попереднього методу.

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

Циклічним кодом є лінійний код, що має наступну властивість: якщо $\overrightarrow$ є кодовим словом, то його циклічна перестановка також є кодовим словом.

Слова циклічного коду зручно представляти як многочленов. Наприклад, кодове слово $\overrightarrow = (v_0, v_1, . v_)$ представляється у вигляді полінома $v(x) = v_0 + v_1 x + . + v_ x^$. При цьому циклічний зсув кодового слова еквівалентний множенню многочлена на (x) по модулю (x n-1).

Надалі,якщо не вказано інше, ми вважатимемо, що циклічний код єдвійковим, тобто $v_0, v_1$… можуть набувати значення0або1.

Що породжує поліном

Можна показати, що всі кодові слова конкретного циклічного коду кратні певномуполіном, що породжує$g(x)$. Що породжує поліном є дільником (x^n-1).

За допомогою полінома, що породжує, здійснюється кодування циклічним кодом. Зокрема:

несистематичне кодуванняздійснюється шляхом множення кодованого вектора на $g(x)$: $v(x) = u(x) g(x)$;

систематичне кодуванняздійснюється шляхом «дописування» до кодованого слова залишку від розподілу $x^u(x)$ на $g(x)$, тобто $v(x) = x^ u(x) + [x u(x) mod g(x)]$.

Коди CRC

Коди CRC (cyclic redundancy check - циклічна надмірна перевірка) єсистематичнимикодами, призначеними не для виправлення помилок, а для їх виявлення. Вони використовують спосіб систематичного кодування, викладений вище: «контрольна сума» обчислюється шляхом поділу (x u (x)) на (g (x)). Зважаючи на те, що виправлення помилок не потрібне, перевірка правильності передачі може проводитися так само.

Таким чином, вид полінома g(x) визначає конкретний код CRC. Приклади найпопулярніших поліномів: