Участник:Terraqottik

Определение:

Линейный код (англ. Linear code) — код фиксированной длины (блоковый код), исправляющий ошибки, для которого любая линейная комбинация кодовых слов также является кодовым словом.

Линейные коды обычно делят на блоковые коды и свёрточные коды. Также можно рассматривать турбо-коды, как гибрид двух предыдущих.

По сравнению с другими кодами, линейные коды позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации (см. синдромы ошибок).

Формальное определение

Определение:

Линейный код длины [math]n[/math] и ранга [math]k[/math] является линейным подпространством [math]C[/math] размерности [math]k[/math] векторного пространства [math]\mathbb{F}_q^n[/math], где [math]\mathbb{F}_q[/math] — конечное поле (поле Галуа) из [math]q[/math] элементов. Такой код с параметром [math]q[/math] называется [math]q[/math]-арным кодом (напр. если [math]q = 5[/math] — то это 5-арный код). Если [math]q = 2[/math] или [math]q = 3[/math], то код представляет собой двоичный код, или тернарный соответственно.

Векторы в [math]C[/math] называют кодовыми словами. Размер кода — это количество кодовых слов, т.е. [math]\mathbb{q}^k[/math].

Весом кодового слова называют число его ненулевых элементов. Расстояние между двумя кодовыми словами — это расстояние Хэмминга. Расстояние [math]d[/math] линейного кода — это минимальный вес его ненулевых кодовых слов или равным образом минимальное расстояние между всеми парами различных кодовых слов. Линейный код длины [math]n[/math], ранга [math]k[/math] и с расстоянием [math]d[/math] называют [math][n,k,d]_q[/math]-кодом (англ. [n,k,d] code).

Порождающая матрица

Определение:

Порождающая матрица — это матрица, чьи столбцы формируют базис линейного кода.

Так как линейный код является линейным подпространством [math]\mathbb{F}_q^n[/math], целиком код [math]C[/math] (может быть очень большим) может быть представлен как линейная оболочка набора из [math]k[/math] кодовых слов (т.е. базис). Этот базис часто объединяют в столбцы матрицы [math]G[/math] и называют такую матрицу порождающей матрицей кода [math]C[/math].

В случае, если [math]\boldsymbol{G} = [I_k | P][/math], где [math]I_k[/math] — это единичная матрица размера [math]k[/math], а [math]P[/math] — это матрица размера [math]k \times (n - k)[/math] говорят, что матрица [math]G[/math] находится в каноническом виде.

Имея матрицу [math]G[/math] можно получить из некоторого входного вектора [math]s[/math] кодовое слово [math]w[/math] линейного кода [math]C[/math]

[math]w=sG[/math],

где [math]w[/math] и [math]s[/math] — векторы-строки. Порождающая матрица линейного [math][n, k, d]_q[/math]-кода имеет вид [math]k \times n[/math]. Число избыточных бит тогда определяется как [math]r = n - k[/math].

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

Определение:

Проверочная матрица [math]H[/math] линейного кода [math]C[/math] — это порождающая матрица ортогонального дополнения [math]C^\perp[/math]. Другими словами, это матрица, которая описывает правила, которым должны удовлетворять части кодового слова.

Используется, чтобы определить, является ли некий вектор кодовым словом, а также в алгоритмах декодирования (напр. syndrome decoding).

Кодовое слово [math]c[/math] принадлежит коду [math]C[/math] тогда и только тогда, когда [math]Hc^\top = 0[/math] или, что то же самое, [math]cH^\top = 0[/math].

Проверочную матрицу можно получить из порождающей и наоборот: пусть дана порождающая матрица [math]G[/math] в каноническом виде [math]G = \begin{bmatrix} I_k | P \end{bmatrix}[/math], тогда проверочную матрицу [math]H[/math] можно получить по формуле

[math]H = \begin{bmatrix} -P^{\top} | I_{n-k} \end{bmatrix}[/math],

так как [math]G H^{\top} = P-P = 0[/math].

Кодирование и декодирование, примеры

Предположим, что имеется линия связи, по которой мы можем пересылать и принимать биты. В среднем какой-то известный процент переданных битов будет поврежден, ошибочен. Такая модель называется двоичным симметричным каналом.

Блок из [math]k[/math] символов сообщения [math]u = u_1u_2{\ldots}u_k, u_i \in \{0, 1\}[/math] будет кодироваться в кодовое слово [math]x = x_1x_2{\ldots}x_n, x_i \in \{0, 1\}[/math], где [math]n \gt = k[/math]; эти кодовые слова образуют код.

Первая часть кодового слова состоит из информационных битов сообщения:

[math]x_1 = u_1, x_2 = u_2, {\ldots}, x_k = u_k[/math],

за которым следуют [math]n - k[/math] проверочных битов [math]x_{k+1}, {\ldots}, x_n[/math]. Проверочные биты выбраны так, чтобы кодовые слова удовлетворяли уравнению

[math]\begin{equation*} H\left( \begin{array}{c} x_1\\ x_2\\ {\ldots}\\ x_n \end{array} \right) = Hx^{\top} = 0 \end{equation*}[/math],

где [math]H[/math] — проверочная матрица.

Пример

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

[math]\begin{equation*} H = \left[ \begin{array}{c|c} 011 & 100\\ 101 & 010\\ 110 & 001 \end{array} \right] \end{equation*}[/math]

определяет код с [math]k = 3[/math] и [math]n = 6[/math]. Для этого кода

[math]\begin{equation*} A = \left[ \begin{array}{c} 011\\ 101\\ 110 \end{array} \right] \end{equation*}[/math].

Сообщение [math]u_1u_2u_3[/math] кодируется в кодовое слово [math]x = x_1x_2x_3x_4x_5x_6[/math], которое начинается с самого сообщения:

[math]x_1 = u_1; x_2 = u_2; x_3 = u_3[/math],

а последующих три проверочных символа [math]x_4x_5x_6[/math] выбираются так, чтобы выполнялось уравнение [math]Hx^{\top} = 0[/math].

Если сообщение [math]u = 011[/math], то [math]x_1 = 0; x_2 = 1; x_3 = 1[/math], и проверочные биты легко определяются: [math]x_4 = 0; x_5 = 1; x_6 = 1[/math], так что кодовое слово [math]x = 011011[/math].

Минимальное расстояние и корректирующая способность

Линейность гарантирует, что расстояние Хэмминга [math]d[/math] между кодовым словом [math]c_0[/math] и любым другим кодовым словом [math]c \neq c_0[/math] не зависит от [math]c_0[/math]. Так как [math]c - c_0[/math] — тоже кодовое слово, а [math]d(c, c_0) = d(c - c_0, 0)[/math], то

[math]\min_{c \in C,\ c \neq c_0}d(c,c_0)=\min_{c \in C,\ c \neq c_0}d(c-c_0, 0)=\min_{c \in C,\ c \neq 0}d(c, 0)=d.[/math]

Иными словами, чтобы найти минимальное расстояние между кодовыми словами линейного кода, необходимо рассмотреть ненулевые кодовые слова. Тогда ненулевое кодовое слово с минимальным весом будет иметь минимальное расстояние до нулевого кодового слова, таким образом показывая минимальное расстояние линейного кода.

Минимальное расстояние кода [math]d[/math] однозначно определяет количество ошибок, которое способен обнаружить ([math][{{d-1}\over{2}}][/math]) и исправить ([math]d - 1[/math]) данный код.

Синдромы и метод обнаружения ошибок в линейном коде

Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова [math]\overrightarrow{r_i}[/math] соответствует наиболее вероятное переданное слово [math]\overrightarrow{u_i}[/math]. Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.

Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора [math]\overrightarrow{r_i}[/math] вычисляется синдром [math]\overrightarrow{s_i}=\overrightarrow{r_i} H^T[/math]. Поскольку [math]\overrightarrow{r_i} = \overrightarrow{v_i} + \overrightarrow{e_i}[/math], где [math]\overrightarrow{v_i}[/math] — кодовое слово, а [math]\overrightarrow{e_i}[/math] — вектор ошибки, то [math]\overrightarrow{s_i}=\overrightarrow{e_i} H^T[/math]. Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.

Преимущества и недостатки линейных кодов

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

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

Источники информации

• wikipedia.org — Линейный код
• wikipedia.org — Linear code
• Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М: Связь, 1979. — 744 с., стр. 12-33
• Ф.И. Соловьева — Введение в теорию кодирования
• В. А. Липницкий, Н. В. Чесалин — Линейные коды и кодовые последовательности: учеб.-метод. пособие для студентов мех.-мат. фак. БГУ. Минск: БГУ, 2008. — 41 с.