Линейный код

В теории кодирования линейный код — это код, исправляющий ошибки , для которого любая линейная комбинация кодовых слов также является кодовым словом. Линейные коды традиционно делятся на блочные коды и сверточные коды , хотя турбокоды можно рассматривать как гибрид этих двух типов. Линейные коды позволяют использовать более эффективные алгоритмы кодирования и декодирования, чем другие коды (см. Синдромное декодирование ).

Линейные коды используются при прямом исправлении ошибок и применяются в способах передачи символов (например, битов ) по каналу связи , так что в случае возникновения ошибок при передаче некоторые ошибки могут быть исправлены или обнаружены получателем блока сообщения. Кодовые слова в линейном блочном коде представляют собой блоки символов, которые закодированы с использованием большего количества символов, чем исходное значение для отправки. Линейный код длины n передает блоки, содержащие n символов. Например, код Хэмминга [7,4,3] представляет собой линейный двоичный код , который представляет 4-битные сообщения с использованием 7-битных кодовых слов. Два различных кодовых слова отличаются по крайней мере тремя битами. Как следствие, можно обнаружить до двух ошибок на одно кодовое слово и исправить одну ошибку. Этот код содержит 2 ⁴ =16 кодовых слов.

Определение и параметры

Линейный код длины n и размерности k — это линейное подпространство C размерности . k векторного пространства $\mathbb {F} _{q}^{n}$ где $\mathbb {F} _{q}$ — конечное поле с q элементами. Такой код называется q -ичным кодом. Если q = 2 или q = 3, код описывается как двоичный или троичный код соответственно. Векторы в C называются кодовыми словами . Размер . кода равен количеству кодовых слов и равен q ^к .

Вес кодового слова — это количество его элементов, которые не равны нулю, а расстояние между двумя кодовыми словами — это расстояние Хэмминга между ними, то есть количество элементов, которыми они отличаются. Расстояние d линейного кода — это минимальный вес его ненулевых кодовых слов или, что то же самое, минимальное расстояние между различными кодовыми словами. Линейный код длины n , размерности k и расстояния d называется кодом [ n , k , d ] (или, точнее, $[n,k,d]_{q}$ код).

Мы хотим дать $\mathbb {F} _{q}^{n}$ стандартная основа, поскольку каждая координата представляет собой «бит», который передается по «шумному каналу» с некоторой небольшой вероятностью ошибки передачи ( двоичный симметричный канал ). Если используется какой-то другой базис, то эту модель использовать нельзя, и метрика Хэмминга не измеряет количество ошибок при передаче, как нам хотелось бы.

Генератор и проверочные матрицы

Как линейное подпространство $\mathbb {F} _{q}^{n}$, весь код C (который может быть очень большим) может быть представлен как диапазон набора $k$ кодовые слова (известные как базис в линейной алгебре ). Эти базовые кодовые слова часто сопоставляются по строкам матрицы G, известной как матрица для кода C. порождающая Когда G имеет форму блочной матрицы ${\boldsymbol {G}}=[I_{k}|P]$, где $I_{k}$ обозначает $k\times k$ единичная матрица и P — некоторая $k\times (n-k)$ матрица, то мы говорим, что G находится в стандартной форме .

Матрица H, представляющая линейную функцию $\phi :\mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n-k}$ которого ядром является C, ( или иногда называется проверочной матрицей C проверочной матрицей четности). Эквивалентно, H — матрица, пространство которой равно C. нулевое Если C — код с порождающей матрицей G в стандартной форме, ${\boldsymbol {G}}=[I_{k}|P]$, затем ${\boldsymbol {H}}=[-P^{T}|I_{n-k}]$ является проверочной матрицей для C. Код, порожденный H , называется двойственным кодом C. Можно проверить, что G является $k\times n$ матрица, а H является $(n-k)\times n$ матрица.

Линейность гарантирует, что минимальное расстояние Хэмминга d между кодовым словом c ₀ и любым другим кодовым словом c ≠ c ₀ не зависит от c ₀ . Это следует из того свойства, что разность c − c ₀ двух кодовых слов в C также является кодовым словом (т. е. элементом подпространства C ), и того свойства, что d ( c , c ₀ ) = d ( c − c ₀ , 0). Эти свойства подразумевают, что

$\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.$

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

Расстояние d линейного кода C также равно минимальному количеству линейно зависимых столбцов проверочной H. матрицы

Доказательство: Потому что ${\boldsymbol {H}}\cdot {\boldsymbol {c}}^{T}={\boldsymbol {0}}$, что эквивалентно $\sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})={\boldsymbol {0}}$, где ${\boldsymbol {H_{i}}}$ это $i^{th}$ столбец ${\boldsymbol {H}}$. Удалите эти элементы с помощью $c_{i}=0$, те ${\boldsymbol {H_{i}}}$ с $c_{i}\neq 0$ линейно зависимы. Поэтому, $d$ - это как минимум минимальное количество линейно зависимых столбцов. С другой стороны, рассмотрим минимальный набор линейно зависимых столбцов $\{{\boldsymbol {H_{j}}}|j\in S\}$ где $S$ — набор индексов столбца. $\sum _{i=1}^{n}(c_{i}\cdot {\boldsymbol {H_{i}}})=\sum _{j\in S}(c_{j}\cdot {\boldsymbol {H_{j}}})+\sum _{j\notin S}(c_{j}\cdot {\boldsymbol {H_{j}}})={\boldsymbol {0}}$. Теперь рассмотрим вектор ${\boldsymbol {c'}}$ такой, что $c_{j}'=0$ если $j\notin S$. Примечание ${\boldsymbol {c'}}\in C$ потому что ${\boldsymbol {H}}\cdot {\boldsymbol {c'}}^{T}={\boldsymbol {0}}$ . Поэтому у нас есть $d\leq wt({\boldsymbol {c'}})$, что представляет собой минимальное количество линейно зависимых столбцов в ${\boldsymbol {H}}$. Таким образом, заявленное свойство является доказанным.

Пример: коды Хэмминга

Основная статья: Код Хэмминга

, первый класс линейных кодов, разработанных для исправления ошибок, Коды Хэмминга широко используются в цифровых системах связи. Для любого положительного целого числа $r\geq 2$, существует $[2^{r}-1,2^{r}-r-1,3]_{2}$ Код Хэмминга. С $d=3$, этот код Хэмминга может исправить 1-битную ошибку.

Пример: линейный блочный код со следующей порождающей матрицей и матрицей проверки четности представляет собой $[7,4,3]_{2}$ Код Хэмминга.

${\boldsymbol {G}}={\begin{pmatrix}1\ 0\ 0\ 0\ 1\ 1\ 0\\0\ 1\ 0\ 0\ 0\ 1\ 1\\0\ 0\ 1\ 0\ 1\ 1\ 1\\0\ 0\ 0\ 1\ 1\ 0\ 1\end{pmatrix}},$ ${\boldsymbol {H}}={\begin{pmatrix}1\ 0\ 1\ 1\ 1\ 0\ 0\\1\ 1\ 1\ 0\ 0\ 1\ 0\\0\ 1\ 1\ 1\ 0\ 0\ 1\end{pmatrix}}$

Пример: коды Адамара

Основная статья: Код Адамара

Код Адамара – это $[2^{r},r,2^{r-1}]_{2}$ линейный код и способен исправлять множество ошибок. Код Адамара можно построить столбец за столбцом: $i^{th}$ столбец — это биты двоичного представления целого числа $i$, как показано в следующем примере. Код Адамара имеет минимальное расстояние $2^{r-1}$ и поэтому может исправить $2^{r-2}-1$ ошибки.

Пример: линейный блочный код со следующей порождающей матрицей представляет собой $[8,3,4]_{2}$ Код Адамара: ${\boldsymbol {G}}_{Had}={\begin{pmatrix}0\ 0\ 0\ 0\ 1\ 1\ 1\ 1\\0\ 0\ 1\ 1\ 0\ 0\ 1\ 1\\0\ 1\ 0\ 1\ 0\ 1\ 0\ 1\end{pmatrix}}$.

Код Адамара является частным случаем кода Рида-Мюллера . Если мы возьмем первый столбец (столбец со всеми нулями) из ${\boldsymbol {G}}_{Had}$, мы получаем $[7,3,4]_{2}$ симплекс-код , который является двойственным кодом кода Хэмминга.

Алгоритм ближайшего соседа

Параметр d тесно связан со способностью кода исправлять ошибки. Это иллюстрирует следующая конструкция/алгоритм (называемый алгоритмом декодирования ближайшего соседа):

Входные данные: полученный вектор v в $\mathbb {F} _{q}^{n}$ .

Выход: кодовое слово. $w$ в $C$ ближайший к $v$, если таковые имеются.

• Начиная с $t=0$, повторите следующие два шага.
• Перечислить элементы шара радиуса (Хемминга) $t$ вокруг полученного слова $v$, обозначенный $B_{t}(v)$.
  • Для каждого $w$ в $B_{t}(v)$, проверьте, если $w$ в $C$. Если да, верните $w$ как решение.
• Приращение $t$. Потерпите неудачу только тогда, когда $t>(d-1)/2$ Итак, перечисление завершено, и решение не найдено.

Мы говорим, что линейная $C$ является $t$-исправление ошибок, если в коде присутствует не более одного кодового слова. $B_{t}(v)$, для каждого $v$ в $\mathbb {F} _{q}^{n}$.

Популярные обозначения

Основная статья: Блочный код § Популярные обозначения

Коды обычно обозначаются буквой C , а код длины n и ранга k (т. е. имеющий n кодовых слов в своей основе и k строк в порождающей матрице ) обычно называется ( n , k ) код. Линейные блочные коды часто обозначаются как [ n , k , d коды ], где d относится к минимальному расстоянию Хэмминга кода между любыми двумя кодовыми словами.

(Обозначение [ n , k , d ] не следует путать с обозначением ( n , M , d ), используемым для обозначения нелинейного кода длины n , размера M (т. е. имеющего M кодовых слов) и минимального кода Хэмминга. расстояние d .)

Синглтон связан

Лемма ( ограничение синглтона ): каждый линейный [n,k,d] код C удовлетворяет условию $k+d\leq n+1$.

Код C, параметры которого удовлетворяют k+d=n+1, называется отделяемым на максимальное расстояние или MDS . Такие кодексы, если они существуют, в каком-то смысле являются наилучшими из возможных.

Если C ₁ и C ₂ существует перестановка p, — два кода длины n и если в симметричной группе Sn _для которой (c ₁ ,...,c _n ) в C ₁ тогда и только тогда, когда (c _{p(1 )} ,...,c _p(n) ) в C ₂ , то мы говорим, что C ₁ и C ₂ эквивалентны перестановочно . В более общем плане, если существует $n\times n$ мономиальная матрица $M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}$ что переводит C1 _{изоморфно} в C2 _, то мы говорим, _C1 и _C2 эквивалентны что .

Лемма : Любой линейный код является перестановочным эквивалентом кода стандартной формы.

Бонизоли

Код считается эквидистантным тогда и только тогда, когда существует некоторая константа d такая, что расстояние между любыми двумя различными кодовыми словами кода равно d . В 1984 году Арриго Бонисоли определил структуру линейных одновесовых кодов над конечными полями и доказал, что каждый эквидистантный линейный код является последовательностью двойственных кодов Хэмминга .

Примеры

Некоторые примеры линейных кодов включают:

• Коды повторения
• Коды четности
• Циклические коды
• Коды Хэмминга
• Код Голея , как двоичная , так и троичная версии
• Полиномиальные коды которых являются коды BCH . , примером
• Коды Рида – Соломона
• Коды Рида – Мюллера
• Коды алгебраической геометрии
• Двоичные коды Гоппы
• Коды проверки четности низкой плотности
• Коды расширителя
• Многомерные коды проверки четности
• Торические коды
• Турбо коды

Обобщение

Пространства Хэмминга над неполевыми алфавитами также рассматривались, особенно над конечными кольцами , особенно над кольцами Галуа над Z ₄ . Это приводит к появлению модулей вместо векторных пространств и кольцевых линейных кодов (отождествляемых с подмодулями ) вместо линейных кодов. Типичная метрика, используемая в данном случае, — расстояние Ли . Существует изометрия Грея между $\mathbb {Z} _{2}^{2m}$ (т.е. GF(2 ^2м )) с расстоянием Хэмминга и $\mathbb {Z} _{4}^{m}$ (также обозначаемый как GR(4,m)) с расстоянием Ли; его главная привлекательность в том, что он устанавливает соответствие между некоторыми «хорошими» кодами, которые не являются линейными по $\mathbb {Z} _{2}^{2m}$ как изображения кольцевых линейных кодов из $\mathbb {Z} _{4}^{m}$.

Некоторые авторы также называют такие коды над кольцами просто линейными кодами.

См. также

• Методы декодирования

Ссылки

Библиография

• Дж. Ф. Хамфрис; МОЙ Перст (2004). Числа, группы и коды (2-е изд.). Издательство Кембриджского университета. ISBN  978-0-511-19420-7 . Глава 5 содержит более мягкое введение (чем эта статья) в тему линейных кодов.

Внешние ссылки

• Программа генератора q -арного кода
• Таблицы кодов: границы параметров различных типов кодов , IAKS, Fakultät für Informatik, Universität Karlsruhe (TH)] . В Интернете актуальная таблица оптимальных двоичных кодов, включая недвоичные коды.
• База данных кодов Z4 Онлайн, актуальная база данных оптимальных кодов Z4.