Оглавление
- 1 Линейный код
- 1.1 Линейные коды
- 1.2 Определение и параметры
- 1.3 Генератор и контрольные матрицы
- 1.4 Свойства линейных кодов
- 1.5 Примеры кодов
- 1.6 Алгоритм декодирования ближайшего соседа
- 1.7 Популярная нотация
- 1.8 Лемма с привязкой к синглтону
- 1.9 Эквивалентность кодов
- 1.10 Лемма и теорема Бонисоли
- 1.11 Примеры линейных кодов
- 1.12 Обобщение на неполевые алфавиты
- 1.13 Способы декодирования
- 1.14 Полный текст статьи:
- 2 Линейный код
Линейный код
-
Линейные коды
- Линейные коды исправляют ошибки, используя линейные комбинации кодовых слов.
- Линейные коды делятся на блочные и сверточные, турбокоды — гибрид этих типов.
- Линейные коды позволяют использовать эффективные алгоритмы кодирования и декодирования.
-
Определение и параметры
- Линейный код длины n и размерности k — это линейное подпространство векторного пространства Fq^n.
- Вес кодового слова — это количество его элементов, отличных от нуля.
- Расстояние между кодовыми словами — это расстояние Хэмминга между ними.
- Расстояние d линейного кода — это минимальный вес его ненулевых кодовых слов.
-
Генератор и контрольные матрицы
- Линейный код может быть представлен в виде базиса из k кодовых слов.
- Генерирующая матрица G — это матрица, сопоставляющая кодовые слова.
- Контрольная матрица H — это матрица, нулевое пространство которой равно C.
-
Свойства линейных кодов
- Минимальное расстояние Хэмминга не зависит от кодового слова c0.
- Расстояние d равно минимальному числу линейно зависимых столбцов контрольной матрицы H.
-
Примеры кодов
- Коды Хэмминга: [2^r-1, 2^r-r-1, 3]2, исправляют 1-битные ошибки.
- Коды Адамара: [2^r, r, 2^r-1]2, исправляют 2^r-2-1 ошибок.
-
Алгоритм декодирования ближайшего соседа
- Алгоритм декодирования ближайшего соседа ищет кодовое слово, ближайшее к вектору v.
- Код C является t-исправляющим ошибки, если в коде есть не более одного кодового слова, близкого к v.
-
Популярная нотация
- Коды обозначаются буквой C, (n, k) код — это код длиной n и рангом k.
- Линейные блочные коды обозначаются как [n, k, d], где d — минимальное расстояние Хэмминга.
-
Лемма с привязкой к синглтону
- Каждый линейный [n, k, d] код удовлетворяет k + d ≤ n + 1.
- Коды с k + d = n + 1 называются разделяемыми на максимальное расстояние (MDS).
-
Эквивалентность кодов
- Коды C1 и C2 эквивалентны, если существует перестановка p, переводящая C1 в C2 и наоборот.
- Коды эквивалентны, если существует матрица M, переводящая C1 в C2 изоморфно.
-
Лемма и теорема Бонисоли
- Любой линейный код эквивалентен коду в стандартной форме.
- Равноудаленные линейные коды являются последовательностью двойных кодов Хэмминга.
-
Примеры линейных кодов
- Код повторения, код четности, циклический код, код Хэмминга, код Голея, полиномиальные коды, коды Рида-Соломона, код Рида-Мюллера, код алгебраической геометрии, двоичный код Goppa, коды для проверки четности с низкой плотностью, код расширителя, многомерный код проверки на четность, торический код, турбо-код, локально восстанавливаемый код.
-
Обобщение на неполевые алфавиты
- Рассматривались пространства Хэмминга над конечными кольцами, особенно кольцами Галуа над Z4.
- Типичным показателем является подветренное расстояние.
- Существует серая изометрия между Z22m и Z4m, устанавливающая соответствие между “хорошими” кодами.
-
Способы декодирования
- Рекомендации по декодированию линейных кодов.