8.3: Лінійні коди

Щоб отримати більше знань про конкретний код та розробити більш ефективні методи кодування, декодування та виявлення помилок, нам потрібно додати додаткову структуру до наших кодів. Один із способів досягти цього - вимагати, щоб код також був групою. Код групи - це код, який також є підгрупою\({\mathbb Z}_2^n\text{.}\)

Щоб перевірити, що код є груповим кодом, нам потрібно перевірити лише одне. Якщо ми додамо будь-які два елементи в коді, результат повинен бути\(n\) -tuple, який знову є в коді. Не потрібно перевіряти, чи є зворотне\(n\) -кортежу в коді, оскільки кожне кодове слово є власним зворотним, а також не потрібно перевіряти, що\({\mathbf 0}\) це кодове слово. Наприклад,

\[ (11000101) + (11000101) = (00000000)\text{.} \nonumber \]

Приклад\(8.16\)

Припустимо, що у нас є код, який складається з наступних 7-кортежів:

\ почати {вирівнювати*} & (0000000) & (0001111) & (0010101) & (0010101) & (0011010)\\ & (01010110) & (0101001) & (0110011) & (0111100)\\ & (1001100) & (1010110) & (1011001)\\ 1100101) І (1101010) І ( 1110000) & (1111111)\ текст {.} \ end {вирівнювати*}

Рішення

Перевірити, що цей код також є підгрупою\({\mathbb Z}_2^7\) і, отже, груповим кодом є простим, але нудним завданням. Цей код є єдиним виявленням помилок та єдиним кодом, що виправляє помилки, але це довгий і виснажливий процес обчислення всіх відстаней між парами кодових слів, щоб визначити, що\(d_{\min} = 3\text{.}\) Набагато легше побачити, що мінімальна вага всіх ненульових кодових слів -\(3\text{.}\) Як ми скоро побачимо, це не випадково. Однак зв'язок між вагами і відстанями в конкретному коді сильно залежить від того, що код є груповим.

Лемма\(8.17\)

\({\mathbf y}\)Дозволяти\({\mathbf x}\) і бути двійкові\(n\) -кортежі. Тоді\(w({\mathbf x} + {\mathbf y}) = d({\mathbf x}, {\mathbf y})\text{.}\)

Доказ

Припустимо, що\({\mathbf x}\) і\({\mathbf y}\) є двійкові\(n\) -кортежі. Тоді відстань між\({\mathbf x}\) і\({\mathbf y}\) дорівнює саме тій кількості місць, в яких\({\mathbf x}\) і\({\mathbf y}\) відрізняються. Але\({\mathbf x}\) і\({\mathbf y}\) відрізняються певною координатою саме тоді, коли сума в координаті є\(1\text{,}\) з

\ почати {вирівнювати*} 1 + 1 & = 0\\ 0 + 0 & = 0\\ 1 + 0 & = 1\\ 0 + 1 & = 1\ текст {.} \ end {вирівнювати*}

Отже, вага суми повинна бути відстанню між двома кодовими словами.

Теорема\(8.18\)

\(d_{\min}\)Дозволяти мінімальна відстань для групового коду\(C\text{.}\) Тоді\(d_{\min}\) мінімальна вага всіх ненульових кодових слів у\(C\text{.}\) Тобто,

\[ d_{\min} = \min\{ w({\mathbf x}) : { {\mathbf x} \neq {\mathbf 0} } \}\text{.} \nonumber \]

Доказ

Зауважте, що

\ почати {вирівнювати*} д_ {\ хв} & =\ хв\ {d ({\ mathbf x}, {\ mathbf у}): {\ mathbf х}\ neq {\ mathbf y}\}\ &=\ хв\ {d ({\ mathbf x}, {\ mathbf y}): {\ mathbf y}): {\ mathbf y}): {\ mathbf y}): {\ mathbf y}): {\ mathbf y}): {\ mathbf у}): {\ mх} + {\ mathbf у}\ новий {\ mathbf 0}\}\ &=\ хв\ {w ({\ mathbf x} + {\ mathbf y}): {\ mathbf x} + {\ mathbf y}\ neq {\ mathbf 0}\\ & =\ хв\ {w ({\ mathbf z}): { \ mathbf z}\ neq {\ mathbf 0}\}\ текст {.} \ end {вирівнювати*}

Лінійні коди

На прикладі тепер легко перевірити\(8.16\), що мінімальна ненульова вага,\(3\text{;}\) отже, код дійсно виявляє та виправляє всі поодинокі помилки. Зараз ми зменшили проблему пошуку «хороших» кодів до проблеми генерації групових кодів. Один простий спосіб генерувати групові коди - використовувати трохи теорії матриць.

Визначте внутрішній добуток двох бінарних\(n\) кортежів, які повинні бути

\[ {\mathbf x} \cdot {\mathbf y} = x_1 y_1 + \cdots + x_n y_n\text{,} \nonumber \]

де\({\mathbf x} = (x_1, x_2, \ldots, x_n)^\transpose\) і\({\mathbf y} = (y_1, y_2, \ldots, y_n)^\transpose\) є векторами стовпців. ⁵ Наприклад, якщо\({\mathbf x} = (011001)^\transpose\) і\({\mathbf y} = (110101)^\transpose\text{,}\) тоді\({\mathbf x} \cdot {\mathbf y} = 0\text{.}\) Ми також можемо подивитися на внутрішній твір як добуток матриці рядків з матрицею стовпців; тобто

\ почати {align*} {\ mathbf x}\ cdot {\ mathbf y} & = {\ mathbf x} ^\ транспонувати {\ mathbf y}\\ & =\ почати {pmatrix} x_1 & x_2 &\ cdots & x_n\ кінець {pmatrix}\ почати {pmatrix} y_1\ y_2\\\ vdots\\ y_n\ кінець {pmatrix}\\ & = x_ {1} y_ {1} + x_ {2} y_ {2} +\ cdots + x_ {n} y_ {n}\ текст {.} \ end {вирівнювати*}

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

Приклад\(8.19\)

Припустимо, що слова, які потрібно закодувати, складаються з усіх двійкових\(3\) -кортежів і що наша схема кодування парна парність.

Рішення

Щоб кодувати довільний\(3\) -кортеж, ми додаємо четвертий біт, щоб отримати парне число\(1\) s. Зверніть увагу, що довільний\(n\) -кортеж\({\mathbf x} = (x_1, x_2, \ldots, x_n)^\transpose\) має парне число\(1\) s точно тоді, коли\(x_1 + x_2 + \cdots + x_n = 0\text{;}\) отже,\(4\) -кортеж\({\mathbf x} = (x_1, x_2, x_3, x_4)^\transpose\) має парне число\(1\) s, якщо\(x_1+ x_2+ x_3+ x_4 = 0\text{,}\) або

\[ {\mathbf x} \cdot {\mathbf 1} = {\mathbf x}^\transpose {\mathbf 1} = \begin{pmatrix} x_1 & x_2 & x_3 & x_4 \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} = 0\text{.} \nonumber \]

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

Нехай\({\mathbb M}_{m \times n}({\mathbb Z}_2)\) позначимо набір всіх\(m \times n\) матриць з записами в\({\mathbb Z}_2\text{.}\) Ми робимо матричні операції як зазвичай, за винятком того, що всі наші операції додавання і множення відбуваються в\({\mathbb Z}_2\text{.}\) Визначити нульовий простір матриці,\(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\) щоб бути множиною всіх двійкових\(n\) - кортежі\({\mathbf x}\) такі, що\(H{\mathbf x} = {\mathbf 0}\text{.}\) Ми позначаємо нульовий простір матриці\(H\) шляхом\(\Null(H)\text{.}\)

Приклад\(8.20\)

Припустимо, що

\[ H = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \end{pmatrix}\text{.} \nonumber \]

\({\mathbf x} = (x_1, x_2, x_3, x_4, x_5)^\transpose\)Щоб\(5\) -кортеж знаходився в нульовому просторі\(H\text{,}\)\(H{\mathbf x} = {\mathbf 0}\text{.}\) еквівалентно, повинна бути виконана наступна система рівнянь:

\ почати {вирівнювати*} x_2 + x_4 & = 0\\ x_1 + x_2 + x_3 + x_4 & = 0\\ x_3 + x_4 + x_4 + x_5 & = 0\ текст {.} \ end {вирівнювати*}

Рішення

Множина двійкових\(5\) -кортезів, що задовольняють ці рівняння, дорівнює

\[ (00000) \qquad (11110) \qquad (10101) \qquad (01011)\text{.} \nonumber \]

Цей код легко визначити як груповий код.

Теорема\(8.21\)

\(H\)Дозволяти бути в\({\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Тоді нульовий простір\(H\) є груповим кодом.

Доказ

Так як кожен елемент\({\mathbb Z}_2^n\) є своїм зворотним, єдине, що дійсно потрібно перевірити тут - це замикання. Нехай\({\mathbf x}, {\mathbf y} \in \Null(H)\) для деякої матриці\(H\) в\({\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Тоді\(H{\mathbf x} = {\mathbf 0}\) і\(H{\mathbf y} = {\mathbf 0}\text{.}\) так

\[ H({\mathbf x}+{\mathbf y}) = H{\mathbf x} + H{\mathbf y} = {\mathbf 0} + {\mathbf 0} = {\mathbf 0}\text{.} \nonumber \]

Отже,\({\mathbf x} + {\mathbf y}\) знаходиться в нульовому просторі\(H\) і тому має бути кодове слово.

Код - це лінійний код, якщо він визначається нульовим простором деякої матриці.\(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\)

Приклад\(8.22\)

\(C\)Дозволяти код, заданий матрицею

\[ H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}\text{.} \nonumber \]

Рішення

Припустимо, що отримано\(6\)\({\mathbf x} = (010011)^\transpose\) -кортеж. Це проста справа множення матриці, щоб визначити, чи\({\mathbf x}\) є кодовим словом чи ні. Так як

\[ H{\mathbf x} = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix}\text{,} \nonumber \]

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