Линейный код

Класс кода исправления ошибок

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

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

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

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

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

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

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

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

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

Доказательство: Поскольку , что эквивалентно , где — столбец . Удалим те элементы с , те, у которых линейно зависимы. Следовательно, — по крайней мере минимальное количество линейно зависимых столбцов. С другой стороны, рассмотрим минимальный набор линейно зависимых столбцов, где — набор индексов столбцов. . Теперь рассмотрим вектор такой, что если . Обратите внимание , поскольку . Следовательно, у нас есть , что является минимальным количеством линейно зависимых столбцов в . Заявленное свойство, таким образом, доказано. ${\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}}}$

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

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

Пример: Линейный блочный код со следующей порождающей матрицей и матрицей проверки четности является кодом Хэмминга. ${\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 тесно связан с возможностью исправления ошибок кода. Следующая конструкция/алгоритм иллюстрирует это (называемая алгоритмом декодирования ближайшего соседа):

Вход: Полученный вектор 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 , а код длины n и ранга k (т. е. имеющий n кодовых слов в своей основе и k строк в своей порождающей матрице ) обычно называют кодом ( n ,  k ). Линейные блочные коды часто обозначают как коды [ n ,  k ,  d ], где d относится к минимальному расстоянию Хэмминга кода между любыми двумя кодовыми словами.

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

Синглтон-граница

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

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

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

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

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

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

Примеры

Вот некоторые примеры линейных кодов:

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

Обобщение

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

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

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

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

Ссылки

1. Уильям Э. Райан и Шу Линь (2009). Channel Codes: Classical and Modern . Cambridge University Press. стр. 4. ISBN 978-0-521-84868-8.
2. MacKay, David, JC (2003). Теория информации, вывод и алгоритмы обучения (PDF) . Cambridge University Press . стр. 9. Bibcode :2003itil.book.....M. ISBN 9780521642989. В линейном блочном коде дополнительные биты являются линейными функциями исходных битов; эти дополнительные биты называются битами проверки четности. ${\displaystyle N-K}$ ${\displaystyle K}${{cite book}}: CS1 maint: multiple names: authors list (link)
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. JH van Lint (1999). Введение в теорию кодирования (3-е изд.). Springer. Глава 8: Коды по ℤ ₄ . ISBN 978-3-540-64133-9.
9. ST Dougherty; J.-L. Kim; P. Sole (2015). "Открытые проблемы в теории кодирования". В Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (ред.). Некоммутативные кольца и их приложения . American Mathematical Soc. стр. 80. ISBN 978-1-4704-1032-2.

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

• JF Humphreys; MY Prest (2004). Числа, группы и коды (2-е изд.). Cambridge University Press. ISBN 978-0-511-19420-7.Глава 5 содержит более мягкое введение (чем эта статья) в тему линейных кодов.

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

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