Введение

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

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

Линейный код длины n и размерности k — это линейное подпространство C размерности k векторного пространства , где — конечное поле с q элементами. Такой код называется q-ичным кодом. Если q = 2 или q = 3, код описывается как двоичный код или троичный код соответственно. Векторы в C называются кодовыми словами. Размер кода — это количество кодовых слов и равен qk. Вес кодового слова — это количество его ненулевых элементов, а расстояние между двумя кодовыми словами — это расстояние Хэмминга между ними, то есть количество позиций, в которых они различаются. Расстояние d линейного кода — это минимальный вес его ненулевых кодовых слов или, эквивалентно, минимальное расстояние между различными кодовыми словами. Линейный код длины n, размерности k и расстояния d называется кодом [n,k,d] (или, точнее, -кодом). Мы хотим использовать стандартный базис, потому что каждая координата представляет собой «бит», который передается по «зашумлённому каналу» с некоторой небольшой вероятностью ошибки передачи (бинарный симметричный канал). Если использовать другой базис, то эта модель неприменима, и метрика Хэмминга не будет измерять количество ошибок при передаче, как нам требуется.

Генератор и контрольные матрицы

В качестве линейного подпространства , весь код C (который может быть очень большим) может быть представлен как линейная оболочка набора кодовых слов (известная как базис в линейной алгебре). Эти базисные кодовые слова часто располагаются в строках матрицы G, известной как порождающая матрица для кода C. Если G имеет блочную матричную форму , где обозначает единичную матрицу, а P – некоторая матрица, то говорят, что G находится в стандартной форме. Матрица H, представляющая линейное отображение, ядро которого является C, называется контрольной матрицей C (или иногда матрицей проверки четности). Эквивалентно, H – это матрица, чье нулевое пространство совпадает с C. Если C – код с порождающей матрицей G в стандартной форме, , то является контрольной матрицей для C. Код, порожденный H, называется двойственным кодом к C. Можно проверить, что G является матрицей, а H – матрицей. Линейность гарантирует, что минимальное расстояние Хэмминга d между кодовым словом c₀ и любым другим кодовым словом c ≠ c₀ не зависит от c₀. Это следует из того свойства, что разность c − c₀ двух кодовых слов в C также является кодовым словом (т.е. элементом подпространства C), и из свойства d(c, c₀) = d(c − c₀, 0). Эти свойства подразумевают, что, другими словами, для определения минимального расстояния между кодовыми словами линейного кода достаточно рассмотреть ненулевые кодовые слова. Ненулевое кодовое слово с наименьшим весом имеет минимальное расстояние до нулевого кодового слова и, следовательно, определяет минимальное расстояние кода. Расстояние d линейного кода C также равно минимальному числу линейно зависимых столбцов контрольной матрицы H.

Доказательство: Поскольку , что эквивалентно , где – это -й столбец. Удалим те столбцы, для которых , тогда оставшиеся столбцы линейно зависимы. Следовательно, число столбцов не меньше минимального числа линейно зависимых столбцов. С другой стороны, рассмотрим минимальный набор линейно зависимых столбцов , где является множеством индексов столбцов. Теперь рассмотрим вектор , такой что если Заметим, что , следовательно, у нас есть , что является минимальным числом линейно зависимых столбцов в H. Таким образом, доказанное свойство верно.

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

Как первый класс линейных кодов, разработанных для коррекции ошибок, коды Хэмминга широко используются в системах цифровой связи. Для любого положительного целого числа *m* существует код Хэмминга. Поскольку *r* ≥ *m*, этот код Хэмминга может исправить однобитовую ошибку. Пример: Линейный блочный код со следующей образующей матрицей и матрицей проверки на четность является кодом Хэмминга.

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

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

Вход: Полученный вектор v из
Выход: Кодовое слово из , ближайшее к , если таковое существует. Начиная с , повторите следующие два шага. Перечислите элементы шара (Хэммингова) радиуса вокруг полученного слова , обозначенного . Для каждого из , проверьте, принадлежит ли ему . Если да, верните как решение. Завершите работу с ошибкой только тогда, когда перечисление завершено и решение не найдено. Мы говорим, что линейный код является -ошибочно-корректирующим, если для каждого существует не более одного кодового слова в .

Популярная нотация

Коды в целом часто обозначаются буквой 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 удовлетворяет условию. Код C, параметры которого удовлетворяют k+d=n+1, называется кодом с максимальным разделением расстояний, или MDS-кодом. Такие коды, когда они существуют, в некотором смысле являются оптимальными. Если C1 и C2 – два кода длины n и существует перестановка p в симметрической группе Sn, такая что (c1, ..., cn) принадлежит C1 тогда и только тогда, когда (cp(1), ..., cp(n)) принадлежит C2, то мы говорим, что C1 и C2 эквивалентны по перестановке. В более общем случае, если существует мономиальная матрица, которая отображает C1 изоморфно на C2, то мы говорим, что C1 и C2 эквивалентны. Лемма: Любой линейный код эквивалентен по перестановке коду, представленному в стандартной форме.

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

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

Обобщение

Рассматривались также пространства Хамминга над не-полевыми алфавитами, особенно над конечными кольцами, в частности, кольцами Галуа над Z4. Это приводит к появлению модулей вместо векторных пространств и кольцевых линейных кодов (отождествляемых с подмодулями) вместо линейных кодов. Типичной метрикой, используемой в этом случае, является расстояние Ли. Существует изометрия Грей между GF(2^(2m)) с расстоянием Хэмминга и GR(4,m) с расстоянием Ли; ее главное преимущество заключается в том, что она устанавливает соответствие между некоторыми "хорошими" кодами, которые не являются линейными над GF(2^(2m)), как образами кольцевых линейных кодов. В последнее время некоторые авторы также называют такие коды над кольцами просто линейными кодами.