Линейный код - Linear code

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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 также равно минимальному количеству линейно зависимых столбцов проверочной матрицы ЧАС.

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

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

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

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

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

${\displaystyle {\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}},}$ ${\displaystyle {\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}}}$

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

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

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

Пример: Код линейного блока со следующей образующей матрицей представляет собой ${\displaystyle [8,3,4]_{2}}$ Код Адамара:${\displaystyle {\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}}}$.

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

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

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

Ввод: A получил вектор v в ${\displaystyle \mathbb {F} _{q}^{n}}$ .

Выход: кодовое слово ${\displaystyle w}$ в ${\displaystyle C}$ ближайший к ${\displaystyle v}$, если есть.

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

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

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

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

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

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

Граница синглтона

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

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

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

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

Теорема Бонисоли

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

Примеры

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

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

Обобщение

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

В последнее время,^{[когда? ]} некоторые авторы называют такие коды над кольцами просто линейными кодами.^[9]

Смотрите также

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

Рекомендации

1. Уильям Э. Райан и Шу Линь (2009). Коды каналов: классический и современный. Издательство Кембриджского университета. п.4. ISBN  978-0-521-84868-8.
2. Маккей, Дэвид, Дж. (2003). Теория информации, логический вывод и алгоритмы обучения (PDF). Издательство Кембриджского университета. п. 9. Bibcode:2003itil.book ..... M. ISBN  9780521642989. В линейный блочный код, дополнительный ${\displaystyle N-K}$ биты являются линейными функциями исходного ${\displaystyle K}$ биты; эти дополнительные биты называются биты проверки четности
3. Томас М. Кавер и Джой А. Томас (1991). Элементы теории информации. John Wiley & Sons, Inc., стр.210–211. ISBN  978-0-471-06259-2.
4. Эцион, Туви; Равив, Нетанель (2013). «Эквидистантные коды в грассманиане». arXiv:1308.6231 [math.CO ].
5. Бонисоли, А. (1984). «Каждый эквидистантный линейный код представляет собой последовательность дуальных кодов Хэмминга». Ars Combinatoria. 18: 181–186.
6. Маркус Греферат (2009). «Введение в теорию линейного кодирования». В Массимилиано Сала; Тео Мора; Людовик Перре; Сёдзиро Саката; Карло Траверсо (ред.). Основы Грёбнера, кодирование и криптография. Springer Science & Business Media. ISBN  978-3-540-93806-4.
7. «Энциклопедия математики». www.encyclopediaofmath.org.
8. J.H. ван Линт (1999). Введение в теорию кодирования (3-е изд.). Springer. Глава 8: Коды закончились ℤ₄. ISBN  978-3-540-64133-9.
9. S.T. Догерти; Ж.-Л. Ким; П. Соле (2015). «Открытые проблемы теории кодирования». В Стивене Догерти; Альберто Факкини; Андре Жерар Лерой; Эдмунд Пучиловски; Патрик Соул (ред.). Некоммутативные кольца и их приложения.. American Mathematical Soc. п. 80. ISBN  978-1-4704-1032-2.

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

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

внешняя ссылка

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