Користувач:Danbst/Робоча

Початок робочої

Книги: [1]

Систематичне кодування

Нехай $C$ — лінійний $[n,k]$-код над полем ${\textbf {F}}_{q}$ з твірною матрицею $G$. Даний код має $q^{k}$ кодових слів, які мають точну взаємовідповідність з $q^{k}$ повідомленнями. Найпростіший спосіб представлення цих повідомлень — це модель кортежів ${\textbf {x}}$ довжини $k$ у полі ${\textbf {F}}_{q}$. Найелементарнішим є кодування повідомлення ${\textbf {x}}$ через кодове слово ${\textbf {c}}={\textbf {x}}G$. Якщо $G$ записана у стандартній формі, перші $k$ розрядів кодового слова ${\textbf {c}}$ будуть інформаційними символами ${\textbf {x}}$; решта $n-k$ розрядів використовують для перевірки парності, тобто вони є надлишковими, проте необхідними для відновлення ${\textbf {x}}$ у випадку наявності помилки. Твірна матриця $G$ може бути і не у стандартній формі. Якщо, однак, існують такі індекси колонок $i_{1},i_{2},\ldots ,i_{k}$, що матриця $k\times k$, складена з цих $k$ колонок матриці $G$, є одиничною матрицею розмірності $k$, тоді повідомлення, що розміщується у цих $k$ розрядах $i_{1},i_{2},\ldots ,i_{k}$ кодового слова, є зпотвореним; це означає, що розряд повідомлення $x_{j}$ є розрядом $i_{j}$ кодового слова. Якщо це так, то кодування називається систематичним. Якщо замінити $G$ на іншу твірну матрицю, то кодування повідомлення ${\textbf {x}}$ зміниться.

Альтернативне визначення систематичності коду

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

Повідомлення          Кодове слово
     00                 1 00 00
     01                 0 01 00
     10                 1 10 11
     11                 0 11 11

Як видно, розряди 2 і 3 кодового слова повторюють повідомлення.

Визначення з англ. вікі

In coding theory, a systematic code is any error-correcting code in which the input data is embedded in the encoded output. Conversely, in a non-systematic code the output does not contain the input symbols.

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

Плашка описаного коду

Властивості:

• лінійний
• систематичний
• блоковий
• просте кодування
• не таке просте декодування

Двійковий лінійний $[n,k,d]$-код складається з $2^{k}$ кодових слів ${\textbf {x}}=x_{1}\ldots x_{n},\;x_{i}\in \{0,1\}$, і будь-які два кодових слова відрізняются один від одного щонайменше у $\;d$ позиціях. Код можна визначити або як множину векторів, що задовільняють рівняння ${\textbf {Hx}}^{T}=0$, де ${\textbf {H}}$ — перевірна матриця, або як усі лінійні комбінації рядків породжуючої матриці $G$. Такий код може виправляти $\lfloor (d-1)/2\rfloor$ помилок. Декодування по максимуму правдоподібності використовує стандартну форму матриці.