Линейный код

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

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

Определение и параметры [ править ]

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

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

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

Генератор и проверка матриц [ править ]

В качестве линейного подпространства в , весь код С (который может быть очень большим) может быть представлена в виде промежутка набора кодовых слов (известного как основы в линейной алгебры ). Эти базовые кодовые слова часто сопоставляется в строках матрицы 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)}$

Матрица Н , представляющий собой линейную функцию , чье ядро является С , называется матрица проверки на 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 (т. Е. Имеющий k кодовых слов в своей основе и 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 ₂ , то мы говорим , C ₁ и C ₂ являются перестановки эквивалентны . В более общем, если есть мономиальная матрица , которая отправляет С ₁ изоморфно 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)) с расстоянием Ли; его главная привлекательность состоит в том, что он устанавливает соответствие между некоторыми "хорошими" кодами, которые не являются линейными по${\displaystyle \mathbb {Z} _{2}^{2m}}$${\displaystyle \mathbb {Z} _{4}^{m}}$${\displaystyle \mathbb {Z} _{2}^{2m}}$как образы кольцевых линейных кодов из . ^{[6] [7] [8]}${\displaystyle \mathbb {Z} _{4}^{m}}$

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

См. Также [ править ]

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

Ссылки [ править ]

Библиография [ править ]

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

Внешние ссылки [ править ]

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