Участник:Terraqottik

Материал из Викиконспекты
Версия от 10:34, 18 февраля 2021; Terraqottik (обсуждение | вклад) (→‎Кодирование и декодирование, примеры)
Перейти к: навигация, поиск
Определение:
Линейный код (англ. Linear code) — код фиксированной длины (блочный код), исправляющий ошибки, для которого любая линейная комбинация кодовых слов также является кодовым словом.


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

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

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

Определение:
Линейный код длины [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]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]. Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.

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

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

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

Примечания

  1. ↑ William E. Ryan and Shu Lin (2009). Channel Codes: Classical and Modern. Cambridge University Press. p. 4. ISBN 978-0-521-84868-8.

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Участник:Terraqottik&oldid=80661»