Лінійний код

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


1. Основи

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

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

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

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

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

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

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

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

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


1.2. Блокові коди

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

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

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

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

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

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


2. Лінійні простори

2.1. Породжує матриця

Нехай вектори \ Overrightarrow {x_1} = (x_ {11}, .., x_ {1n}), \ overrightarrow {x_2} = (x_ {21}, .., x_ {2n}), .., \ overrightarrow {x_k} = (x_ {k1}, .., x_ {kn}) є базисом лінійного простору C . За визначенням базису, будь-який вектор \ Overrightarrow {v} \ in C можна представити у вигляді лінійної комбінації базисних векторів: \ Overrightarrow {v} = {c_1} \ overrightarrow {x_1} + {c_2} \ overrightarrow {x_2} + ... + {C_k} \ overrightarrow {x_k} , Або в матричної формі, як:

\ Overrightarrow {v} = ({c_1}, {c_2}, .., {c_k}) \ begin {bmatrix} x_ {11} & x_ {12} & .. & X_ {1n} \ \ x_ {21} & x_ {22} & .. & X_ {2n} \ \ .. & .. & .. & .. \ \ X_ {k1} & x_ {k2} & .. & X_ {kn} \ \ \ end {bmatrix} = \ overrightarrow {c} G ,

де G = \ begin {bmatrix} x_ {11} & x_ {12} & .. & X_ {1n} \ \ x_ {21} & x_ {22} & .. & X_ {2n} \ \ .. & .. & .. & .. \ \ X_ {k1} & x_ {k2} & .. & X_ {kn} \ \ \ end {bmatrix} називається породжує матрицею лінійного простору.

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


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

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

Нехай \ Mathbb {C} - Лінійне k-мірний простір над полем \ Mathbb {F} _q і \ Mathbb {W} - Ортогональне доповнення \ Mathbb {C} . Тоді по одній з теорем лінійної алгебри, розмірність \ Mathbb {W} дорівнює r = n - k . Тому в \ Mathbb {W} існує r базисних векторів. Нехай \ Overrightarrow {h} _1 = ({{h_1} _1}, ..., {{h_1} _n}), \ overrightarrow {h} _2 = ({{h_2} _1}, ..., {{h_2} _n}), ..., \ overrightarrow {h} _r = ({{h_r} _1}, ..., {{h_r} _n})базис в \ Mathbb {W} .

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

\ Begin {cases} h_ {11} x_1 + h_ {12} x_2 + ... + H_ {1n} x_n = 0 \ \ h_ {21} x_1 + h_ {22} x_2 + ... + H_ {2n} x_n = 0 \ \ ... \ \ H_ {r1} x_1 + h_ {r2} x_2 + ... + H_ {rn} x_n = 0 \ end {cases}

Або в матричної формі: \ Overrightarrow {v} H ^ T = 0 ,

де H = \ begin {bmatrix} \ overrightarrow {h} _1 \ \ \ overrightarrow {h} _2 \ \ ... \ \ \ Overrightarrow {h} _r \ \ \ end {bmatrix} = \ begin {bmatrix} h_ {11} & h_ {12} & .. & H_ {1n} \ \ h_ {21} & h_ {22} & .. & H_ {2n} \ \ .. & .. & .. & .. \ \ H_ {r1} & h_ {r2} & .. & H_ {rn} \ \ \ end {bmatrix} - Перевірочна матриця.


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


3. Формальне визначення

Лінійний код довжини n і рангу k є лінійним підпростором C розмірності k векторного простору \ Mathbb {F} _q ^ n , Де \ Mathbb {F} _q - Конечномерное поле з q елементів. Такий код з параметром q називається q-арним кодом (напр. якщо q = 5 - то це 5-арний код). Якщо q = 2 або q = 3, то код являє собою двійковий код, або тернарних відповідно.

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

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

Нехай C ^ {\ perp} - Ортогональне підпростір по відношенню до C , А H - Матриця, що задає базис цього підпростору. Тоді для будь-якого вектора \ Overrightarrow {v} \ in C справедливо:

\ Overrightarrow {v} H ^ T = \ overrightarrow {0} .

4. Властивості і важливі теореми

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

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

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

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

Теорема 1:

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

d = \ min_ {\ overrightarrow {c} \ in C, \ overrightarrow {c} \ not = \ overrightarrow {0}} (w (\ overrightarrow {c}))

Доказ:

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

Мінімальна відстань Хеммінга d є важливою характеристикою лінійного блокового коду. Вона визначає іншу, не менш важливу характеристику - коригувальну здатність :

t = \ left \ lfloor \ frac {d - 1} {2} \ right \ rfloor , Тут кутові дужки позначають округлення "вниз".

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

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

Число виявлених помилок - число помилок, при якому код може судити про помилкову ситуації. Це число дорівнює

f = d - 1 .

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

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

Теорема 3 (без доведення):

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


4.2. Коди Хеммінга

Історично "коди Хеммінга" повинні називатися кодами Р. Фішера і був представлений в 1942р (Fisher RA The theory of confouding in factor to thr theory). Коди Хеммінга - найпростіші лінійні коди з мінімальною відстанню 3, тобто здатні виправити одну помилку. Код Хеммінга може бути представлений у такому вигляді, що синдром

\ Overrightarrow {s} = \ overrightarrow {r} H ^ T , Де \ Overrightarrow {r} - Прийнятий вектор,

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


4.3. Код Ріда-Маллер

Код Ріда-Маллер en: Reed-Muller code - лінійний двійковий блоковий код. При певному побудові він може бути систематичним. У загальному випадку код Ріда-Маллер не є циклічним. Коди Ріда-Маллер задаються наступними параметрами для будь-яких значень m і r, званого порядком коду, меншого, ніж m: - довжина кодового слова n = 2 m; - довжина інформаційної частини k = 1 + C m 1 + ... + C m r; - довжина перевірочної частини nk = 1 + Cm1 + ... + Cmm-r-1; - мінімальна кодова відстань d min = 2 mr. Код Ріда-Маллер визначається за допомогою породжує матриці, що складається з базисних векторів. Будується за правилом: - нехай V0 - вектор, всі компоненти якого рівні 1; - нехай V1, V2, ..., Vm - рядки матриці, стовпцями якої є всі двійкові набори довжини m. Код Ріда-Маллер r-го порядку містить в якості базису вектори V0, V1, ..., Vm і всі компонентні твори r або меншого числа цих векторів.



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

Лінійний код довжини n з k інформаційними символами є k-мірним лінійним підпростором, тому кожне кодове слово є лінійною комбінацією базисних векторів \ Overrightarrow {g_1} = (g_ {11}, .., g_ {1n}), \ overrightarrow {g_2} = (g_ {21}, .., g_ {2n}), .., \ overrightarrow {g_k} = (g_ {k1}, .., g_ {kn}) підпростори:

\ Overrightarrow {c} = {m_1} \ overrightarrow {g_1} + {m_2} \ overrightarrow {g_2} + ... + {M_k} \ overrightarrow {g_k} .

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

\ Overrightarrow {c} = \ overrightarrow {m} G = ({m_1}, {m_2}, .., {m_k}) \ begin {bmatrix} g_ {11} & g_ {12} & .. & G_ {1n} \ \ g_ {21} & g_ {22} & .. & G_ {2n} \ \ .. & .. & .. & .. \ \ G_ {k1} & g_ {k2} & .. & G_ {kn} \ \ \ end {bmatrix} , Де \ Overrightarrow {m} = ({m_1}, .., {m_k}), {m_1}, .., {m_k} \ in \ mathbb {Q}


Це співвідношення є правило кодування, по якому інформаційне слово \ Overrightarrow {m} = ({m_1}, .., {m_k}) відображається у кодове \ Overrightarrow {c} = ({c_1}, .., {c_n})


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

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

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


5. Лінійні циклічні коди

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

Циклічним кодом є лінійний код, що володіє наступним властивістю: якщо \ Overrightarrow {v} є кодовим словом, то його циклічна перестановка також є кодовим словом.

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

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


5.1. Породжує поліном

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

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

  • несистематичне кодування здійснюється шляхом множення кодованого вектора на g (x) : v (x) = u (x) g (x) ;
  • систематичне кодування здійснюється шляхом "дописування" до кодованих слову залишку від ділення x ^ {n-k} u (x) на g (x) , Тобто v (x) = x ^ {n-k} u (x) + [x ^ {n-k} u (x) \ mod g (x)] .

5.2. Коди CRC

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

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

назву коду ступінь поліном
CRC-12 12 x ^ {12} + x ^ {11} + x ^ {3} + x ^ {2} + x +1
CRC-16 16 x ^ {16} + x ^ {15} + x ^ {2} +1
CRC- CCITT 16 x ^ {16} + x ^ {15} + x ^ {5} +1
CRC-32 32 x ^ {32} + x ^ {26} + x ^ {23} + x ^ {22} + x ^ {16} + x ^ {12} + x ^ {11} + x ^ {10} + x ^ {8} + x ^ {7} + x ^ {5} + x ^ {4} + x ^ {2} + x +1

5.3. Коди БЧХ

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

Математично побудова кодів БЧХ та їх декодування використовують розкладання породжує полінома g (x) на множники в поле Галуа.


5.4. Коди Ріда-Соломона

Коди Ріда-Соломона (РС-коди) фактично є Недвійкова кодами БЧХ, тобто елементи кодового вектора є не бітами, а групами бітів. Дуже поширені коди Ріда-Соломона, що працюють з байтами ( октет).

6. Переваги та недоліки лінійних кодів

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

- Хоча лінійні коди, як правило, добре справляються з рідкими, але великими пачками помилок, їх ефективність при частих, але невеликих помилках (наприклад, в каналі з АБГШ), менш висока.


7. Оцінка ефективності

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

7.1. Кордон Хеммінга і досконалі коди

Нехай є двійковий блоковий (N, k) код з коригуючої здатністю t . Тоді справедливо нерівність (зване кордоном Хеммінга):

\ Sum_ {i = 0} ^ t {n \ choose i} \ le 2 ^ {n-k} .

Коди, що задовольняють цій кордоні з рівністю, називаються досконалими. До досконалим кодами відносяться, наприклад, коди Хеммінга. Часто вживані на практиці коди з великою коректує здатністю (такі, як коди Ріда-Соломона) не є досконалими.


7.2. Енергетичний виграш

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

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


8. Застосування

Лінійні коди застосовуються:

  • в системах цифрового зв'язку, в тому числі: супутникового, радіорелейного, стільникового, передачі даних по телефонних каналах;
  • в системах зберігання інформації, у тому числі магнітних і оптичних;
  • в мережевих протоколах різних рівнів.