Участник:Terraqottik — различия между версиями
(→Кодирование и декодирование, примеры) |
(→Кодирование и декодирование, примеры) |
||
Строка 73: | Строка 73: | ||
где <tex>H</tex> {{---}} [[Участник:Terraqottik#Проверочная матрица | проверочная матрица]]. | где <tex>H</tex> {{---}} [[Участник:Terraqottik#Проверочная матрица | проверочная матрица]]. | ||
+ | |||
+ | === Пример === | ||
+ | |||
+ | Проверочная матрица | ||
+ | |||
+ | : <tex>\begin{equation*} | ||
+ | H = \left[ | ||
+ | \begin{array}{c|c} | ||
+ | 011 & 100\\ | ||
+ | 101 & 010\\ | ||
+ | 110 & 001 | ||
+ | \end{array} | ||
+ | \right] | ||
+ | \end{equation*}</tex> | ||
+ | |||
+ | определяет код с <tex>k = 3</tex> и <tex>n = 6</tex>. Для этого кода | ||
+ | |||
+ | <tex>\begin{equation*} | ||
+ | A = \left[ | ||
+ | \begin{array}{c} | ||
+ | 011\\ | ||
+ | 101\\ | ||
+ | 110 | ||
+ | \end{array} | ||
+ | \right] | ||
+ | \end{equation*}</tex>. | ||
+ | |||
+ | Сообщение <tex>u_1u_2u_3</tex> кодируется в кодовое слово <tex>x = x_1x_2x_3x_4x_5x_6</tex>, которое начинается с самого сообщения: | ||
+ | |||
+ | : <tex>x_1 = u_1; x_2 = u_2; x_3 = u_3</tex>, | ||
+ | |||
+ | а последующих три проверочных символа <tex>x_4x_5x_6</tex> выбираются так, чтобы выполнялось уравнение <tex>Hx^{\top} = 0</tex>. | ||
+ | |||
+ | Если сообщение <tex>u = 011</tex>, то <tex>x_1 = 0; x_2 = 1; x_3 = 1</tex>, и проверочные биты легко определяются: <tex>x_4 = 0; x_5 = 1; x_6 = 1</tex>, так что кодовое слово <tex>x = 011011</tex>. | ||
== Минимальное расстояние и корректирующая способность == | == Минимальное расстояние и корректирующая способность == |
Версия 10:54, 18 февраля 2021
Определение: |
Линейный код (англ. Linear code) — код фиксированной длины (блочный код), исправляющий ошибки, для которого любая линейная комбинация кодовых слов также является кодовым словом. |
Линейные коды обычно делят на блочные коды и свёрточные коды. Также можно рассматривать турбо-коды, как гибрид двух предыдущих.[1]
По сравнению с другими кодами, линейные коды позволяют реализовывать более эффективные алгоритмы кодирования и декодирования информации (см. синдромы ошибок).
Содержание
Формальное определение
Определение: |
Линейный код длины | и ранга является линейным подпространством размерности векторного пространства , где — конечное поле (поле Галуа) из элементов. Такой код с параметром называется -арным кодом (напр. если — то это 5-арный код). Если или , то код представляет собой двоичный код, или тернарный соответственно.
Векторы в называют кодовыми словами. Размер кода — это количество кодовых слов, т.е. .
Весом кодового слова называют число его ненулевых элементов. Расстояние между двумя кодовыми словами — это расстояние Хэмминга. Расстояние линейного кода — это минимальный вес его ненулевых кодовых слов или равным образом минимальное расстояние между всеми парами различных кодовых слов. Линейный код длины , ранга и с расстоянием называют -кодом (англ. [n,k,d] code).
Порождающая матрица
Определение: |
Порождающая матрица — это матрица, чьи столбцы формируют базис линейного кода. |
Так как линейный код является линейным подпространством , целиком код (может быть очень большим) может быть представлен как линейная оболочка набора из кодовых слов (т.е. базис). Этот базис часто объединяют в столбцы матрицы и называют такую матрицу порождающей матрицей кода .
В случае, если
, где — это единичная матрица размера , а — это матрица размера говорят, что матрица находится в каноническом виде.Имея матрицу
можно получить из некоторого входного вектора кодовое слово линейного кода- ,
где
и — векторы-строки. Порождающая матрица линейного -кода имеет вид . Число избыточных бит тогда определяется как .Проверочная матрица
Определение: |
Проверочная матрица | линейного кода — это порождающая матрица ортогонального дополнения . Другими словами, это матрица, которая описывает правила, которым должны удовлетворять части кодового слова.
Используется, чтобы определить, является ли некий вектор кодовым словом, а также в алгоритмах декодирования (напр. syndrome decoding).
Кодовое слово
принадлежит коду тогда и только тогда, когда или, что то же самое, .Проверочную матрицу можно получить из порождающей и наоборот: пусть дана порождающая матрица
в каноническом виде , тогда проверочную матрицу можно получить по формуле- ,
так как
.Кодирование и декодирование, примеры
Предположим, что имеется линия связи, по которой мы можем пересылать и принимать биты. В среднем какой-то известный процент переданных битов будет поврежден, ошибочен. Такая модель называется двоичным симметричным каналом.
Блок из
символов сообщения будет кодироваться в кодовое слово , где ; эти кодовые слова образуют код.Первая часть кодового слова состоит из информационных битов сообщения:
- ,
за которым следуют
проверочных битов . Проверочные биты выбраны так, чтобы кодовые слова удовлетворяли уравнению- ,
где проверочная матрица.
—Пример
Проверочная матрица
определяет код с
и . Для этого кода.
Сообщение
кодируется в кодовое слово , которое начинается с самого сообщения:- ,
а последующих три проверочных символа
выбираются так, чтобы выполнялось уравнение .Если сообщение
, то , и проверочные биты легко определяются: , так что кодовое слово .Минимальное расстояние и корректирующая способность
Линейность гарантирует, что расстояние Хэмминга между кодовым словом и любым другим кодовым словом не зависит от . Так как — тоже кодовое слово, а , то
Иными словами, чтобы найти минимальное расстояние между кодовыми словами линейного кода, необходимо рассмотреть ненулевые кодовые слова. Тогда ненулевое кодовое слово с минимальным весом будет иметь минимальное расстояние до нулевого кодового слова, таким образом показывая минимальное расстояние линейного кода.
Минимальное расстояние кода однозначно определяет количество ошибок, которое способен обнаружить ( ) и исправить ( ) данный код.
Синдромы и метод обнаружения ошибок в линейном коде
Любой код (в том числе нелинейный) можно декодировать с помощью обычной таблицы, где каждому значению принятого слова
соответствует наиболее вероятное переданное слово . Однако, данный метод требует применения огромных таблиц уже для кодовых слов сравнительно небольшой длины.Для линейных кодов этот метод можно существенно упростить. При этом для каждого принятого вектора
вычисляется синдром . Поскольку , где — кодовое слово, а — вектор ошибки, то . Затем с помощью таблицы по синдрому определяется вектор ошибки, с помощью которого определяется переданное кодовое слово. При этом таблица получается гораздо меньше, чем при использовании предыдущего метода.Преимущества и недостатки линейных кодов
+ Благодаря линейности для запоминания или перечисления всех кодовых слов достаточно хранить в памяти кодера или декодера существенно меньшую их часть, а именно только те слова, которые образуют базис соответствующего линейного пространства. Это существенно упрощает реализацию устройств кодирования и декодирования и делает линейные коды весьма привлекательными с точки зрения практических приложений.
- Хотя линейные коды, как правило, хорошо справляются с редкими, но большими пачками ошибок, их эффективность при частых, но небольших ошибках (например, в канале с АБГШ), менее высока.
Примечания
Источники информации
- wikipedia.org — Линейный код
- wikipedia.org — Linear code
- Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М: Связь, 1979. — 744 с., стр. 12-33
- Ф.И. Соловьева — Введение в теорию кодирования
- В. А. Липницкий, Н. В. Чесалин — Линейные коды и кодовые последовательности: учеб.-метод. пособие для студентов мех.-мат. фак. БГУ. Минск: БГУ, 2008. — 41 с.