В теории кодирования , линейный код является кодом коррекции ошибок , для которых любая линейная комбинация из кодовых слов также является кодовым слово. Линейные коды традиционно делятся на блочные коды и сверточные коды , хотя турбокоды можно рассматривать как гибрид этих двух типов. [1] Линейные коды позволяют использовать более эффективные алгоритмы кодирования и декодирования, чем другие коды (см. Синдромное декодирование ). [ необходима цитата ]
Линейные коды используются при прямом исправлении ошибок и применяются в способах передачи символов (например, битов ) по каналу связи, так что, если при передаче возникают ошибки, некоторые ошибки могут быть исправлены или обнаружены получателем блока сообщения. Кодовые слова в линейном блочном коде - это блоки символов, которые закодированы с использованием большего количества символов, чем исходное значение, которое должно быть отправлено. [2] Линейный код длины n передает блоки, содержащие n символов. Например, код Хэмминга [7,4,3] представляет собой линейный двоичный код.который представляет 4-битные сообщения с использованием 7-битных кодовых слов. Два различных кодовых слова отличаются по крайней мере тремя битами. Как следствие, может быть обнаружено до двух ошибок на кодовое слово, в то время как одна ошибка может быть исправлена. [3] Этот код содержит 2 4 = 16 кодовых слов.
Определение и параметры
Линейный код длины п и ранга к является линейным подпространством С с размерностью к части векторного пространства где - конечное поле из q элементов. Такой код называется q- мерным кодом. Если q = 2 или q = 3, код описывается как двоичный код или троичный код соответственно. Векторы в C называются кодовыми словами . Размер кода это число кодовых слов и равна Q K .
Вес кодового слова является количество его элементов, которые отличны от нуля , а расстояние между двумя кодовыми словами представляет собой расстояние Хэмминга между ними, то есть, количество элементов , в которых они отличаются. Расстояние d линейного кода - это минимальный вес его ненулевых кодовых слов или, что эквивалентно, минимальное расстояние между различными кодовыми словами. Линейный код длины n , размерности k и расстояния d называется кодом [ n , k , d ].
Мы хотим дать стандартная основа, поскольку каждая координата представляет собой «бит», который передается по «зашумленному каналу» с некоторой небольшой вероятностью ошибки передачи ( двоичный симметричный канал ). Если используется какой-то другой базис, то эту модель использовать нельзя, а метрика Хэмминга не измеряет количество ошибок при передаче, как мы этого хотим.
Генераторные и проверочные матрицы
Как линейное подпространство в, весь код C (который может быть очень большим) может быть представлен как промежуток наборакодовые слова (известные как базис в линейной алгебре ). Эти базовые кодовые слова часто сопоставляется в строках матрицы G , известный как порождающая матрица для кода C . Когда G имеет вид блочной матрицы, где обозначает единичная матрица, а P - некоторая матрица, то мы говорим, что G имеет стандартную форму .
Матрица H, представляющая линейную функциючье ядро является C называется проверочную матрицу из С (или иногда проверки четности матрицы). Эквивалентно, Н является матрицей, нуль - пространство является С . Если C - код с порождающей матрицей G в стандартной форме,, тогда является проверочной матрицей для C. Код, порожденный H , называется двойственным кодом C. Можно проверить, что G является матрица, а H - матрица.
Линейность гарантирует, что минимальное расстояние Хэмминга d между кодовым словом c 0 и любым другим кодовым словом c ≠ c 0 не зависит от c 0 . Это следует из того свойства, что разность c - c 0 двух кодовых слов в C также является кодовым словом (т. Е. Элементом подпространства C ), и того свойства, что d ( c , c 0 ) = d ( c - c 0 , 0). Из этих свойств следует, что
Другими словами, чтобы определить минимальное расстояние между кодовыми словами линейного кода, нужно только посмотреть на ненулевые кодовые слова. Ненулевое кодовое слово с наименьшим весом тогда имеет минимальное расстояние до нулевого кодового слова и, следовательно, определяет минимальное расстояние кода.
Расстояние d линейного кода C также равно минимальное количество линейно зависимых столбцов проверочной матрицы H .
Доказательство: Потому что, что эквивалентно , где это столбец . Удалите эти элементы с помощью, те с участием линейно зависимы. Следовательно,- по крайней мере, минимальное количество линейно зависимых столбцов. С другой стороны, рассмотрим минимальный набор линейно зависимых столбцов. где - это набор индексов столбца. . Теперь рассмотрим вектор такой, что если . Примечание так как . Следовательно, мы имеем, который представляет собой минимальное количество линейно зависимых столбцов в . Таким образом, заявленное имущество доказано.
Пример: коды Хэмминга
В качестве первого класса линейных кодов, разработанных для исправления ошибок, коды Хэмминга широко используются в цифровых системах связи. Для любого положительного целого числасуществует Код Хэмминга. С, этот код Хэмминга может исправить 1-битную ошибку.
Пример: линейный блочный код со следующей образующей матрицей и матрицей проверки на четность является Код Хэмминга.
Пример: коды Адамара
Код Адамара - этолинейный код и способен исправлять многие ошибки. Код Адамара может быть построен столбец за столбцом: столбец - это биты двоичного представления целого числа , как показано в следующем примере. Код Адамара имеет минимальное расстояние и поэтому может исправить ошибки.
Пример: линейный блочный код со следующей образующей матрицей является Код Адамара: .
Код Адамара - это частный случай кода Рида – Маллера . Если мы возьмем первый столбец (столбец с нулевыми значениями) из, мы получили симплексный код , который является двойным кодом кода Хэмминга.
Алгоритм ближайшего соседа
Параметр d тесно связан со способностью кода исправлять ошибки. Следующая конструкция / алгоритм иллюстрирует это (так называемый алгоритм декодирования ближайшего соседа):
Вход: полученный вектор v в .
Выход: кодовое слово в ближайший к , если есть.
- Начиная с , повторите следующие два шага.
- Перечислим элементы шара радиуса (Хэмминга) вокруг полученного слова , обозначенный .
- Для каждого в , проверить, если в . Если да, верните как решение.
- Инкремент . Неудача только тогда, когда так что перечисление завершено и решения не найдено.
Мы говорим, что линейный является -исправление ошибок, если есть не более одного кодового слова в , для каждого в .
Популярные обозначения
Коды в общем случае часто обозначаются буквой 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 удовлетворяет.
Код C, параметры которого удовлетворяют условию k + d = n + 1, называется максимальным разделимым расстоянием или MDS . Такие коды, если они существуют, в некотором смысле являются наилучшими из возможных.
Если C 1 и C 2 - два кода длины n и если существует перестановка p в симметрической группе S n, для которой (c 1 , ..., c n ) в C 1 тогда и только тогда, когда (c p (1 ) , ..., с р (п) ) в C 2 , то мы говорим , C 1 и C 2 являются перестановки эквивалентны . В общем, если есть мономиальная матрица который посылает C 1 изоморфно C 2 , то мы говорим , С 1 и С 2 являются эквивалентны .
Лемма : Любой линейный код является перестановочно эквивалентным коду в стандартной форме.
Теорема Бонисоли
Код определяется как эквидистантный тогда и только тогда, когда существует некоторая константа d такая, что расстояние между любыми двумя различными кодовыми словами кода равно d . [4] В 1984 году Арриго Бонисоли определил структуру линейных одновесовых кодов над конечными полями и доказал, что каждый эквидистантный линейный код является последовательностью двойственных кодов Хэмминга . [5]
Примеры
Некоторые примеры линейных кодов включают:
- Коды повторения
- Коды четности
- Циклические коды
- Коды Хэмминга
- Код Голея , как двоичная, так и троичная версии
- Полиномиальные коды , примером которых являются коды БЧХ
- Коды Рида – Соломона
- Коды Рида – Маллера
- Коды гоппы
- Коды проверки на четность с низкой плотностью
- Коды расширителей
- Многомерные коды проверки на четность
- Торические коды
- Турбо коды
Обобщение
Также рассматривались пространства Хэмминга над неполевыми алфавитами, особенно над конечными кольцами (особенно над Z 4 ), приводящими к модулям вместо векторных пространств и кольцевым линейным кодам (отождествленным с подмодулями ) вместо линейных кодов. Типичная метрика, используемая в этом случае - расстояние Ли . Существует изометрия Грея между(т.е. GF (2 2m )) с расстоянием Хэмминга и(также обозначается как GR (4, м)) с расстоянием Ли; его главная привлекательность состоит в том, что он устанавливает соответствие между некоторыми "хорошими" кодами, которые не являются линейными по как образы кольцевых кодов из . [6] [7] [8]
Совсем недавно [ когда? ] некоторые авторы также называют такие коды над кольцами просто линейными кодами. [9]
Смотрите также
- Методы декодирования
Рекомендации
- ^ Уильям Э. Райан и Шу Линь (2009). Коды каналов: классический и современный . Издательство Кембриджского университета. п. 4 . ISBN 978-0-521-84868-8.
- ^ Маккей, Дэвид, JC (2003). Теория информации, выводы и алгоритмы обучения (PDF) . Издательство Кембриджского университета . п. 9. Bibcode : 2003itil.book ..... M . ISBN 9780521642989.
В линейном блочном коде дополнительные биты являются линейными функциями исходного биты; эти дополнительные биты называются битами проверки четности
- ^ Томас М. Кавер и Джой А. Томас (1991). Элементы теории информации . John Wiley & Sons, Inc., стр. 210–211 . ISBN 978-0-471-06259-2.
- ^ Эцион, Туви; Равив, Нетанель (2013). «Эквидистантные коды в грассманиане». arXiv : 1308.6231 [ math.CO ].
- ^ Бонисоли А. (1984). «Каждый эквидистантный линейный код представляет собой последовательность дуальных кодов Хэмминга». Ars Combinatoria . 18 : 181–186.
- ^ Маркус Греферат (2009). «Введение в теорию линейного кодирования». В Массимилиано Сала; Тео Мора; Людовик Перре; Сёдзиро Саката; Карло Траверсо (ред.). Основы Грёбнера, кодирование и криптография . Springer Science & Business Media. ISBN 978-3-540-93806-4.
- ^ «Энциклопедия математики» . www.encyclopediaofmath.org .
- ^ Дж. Х. ван Линт (1999). Введение в теорию кодирования (3-е изд.). Springer. Глава 8: Коды 4 . ISBN 978-3-540-64133-9.
- ^ С.Т. Догерти; Ж.-Л. Ким; П. Соле (2015). «Открытые проблемы теории кодирования» . В Стивене Догерти; Альберто Факкини; Андре Жерар Лерой; Эдмунд Пучиловски; Патрик Соул (ред.). Некоммутативные кольца и их приложения . American Mathematical Soc. п. 80. ISBN 978-1-4704-1032-2.
Библиография
- Дж. Ф. Хамфрис; 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.