[Править] Коды как линейные операторы

То, что на множестве {0,1} есть структура числового поля, позволяет осуществлять алгебраические интерпретации кодирования. Заметим, в частности, что как коды Хемминга, так и циклические коды линейны:\\ 1) отношения ((eq:hem)) на с. \pageref{eq:hem}, связывающие контрольные биты кода Хемминга с другими линейны,\\ 2) остаток от деления суммы многочленов на третий равен сумме остатков.\\ То есть кодирование в этих двух случаях есть линейное отображение из в . Поясним на примерах. Ниже представлена матрица кода Хемминга Hem(7,4) (см. соотношения ((eq:hem))). Исходное слово есть , а результирующее (слова соответствуют столбцам).

Процесс выявления ошибок тоже линейная операция, она осуществляется с помощью проверочной матрицы . Пусть принято слово . Слово в случае правильной передачи должно быть равно 000. Значение называется синдромом ошибки. i-ый разряд слова контролирует i-ое соотношение в ((eq:hem)) и, таким образом, равно сумме номеров бит в которых произошла ошибка, как векторов в .

Заметим, что столбцы проверочной матрицы представляют собой последовательно записанные в двоичной форме натуральные числа от 1 до 7.

Вычиcление рабочей матрицы для циклических кодов основывается на значениях . Верхняя её часть равна единичной, так m бит сообщения помещаются без изменения в начало слова, а нижние r строчек есть m столбцов высоты r состоящие из коэффициентов многочленов G_n, G_{n − 1}, \dots, G_{n − r}. Например, для G(x) = x³ + x + 1 и m = 4 имеем r = 3, n = 7 и

Рабочая и проверочная матрицы равны

то есть

Кроме рабочей и проверочной матриц есть ещё множество порождающих матриц и декодирующих матриц . Понятно, что в случае линейных кодов допустимые слова образуют линейное подпространство равное . Любая матрица, столбцы которой образуют базис этого подпространства, называется порождающей. В частности, рабочая матрица является порождающей. Способность обнаруживать и исправлять ошибки однозначно определяется подпространством L. Порождающих, рабочих и проверочных матриц соответствующих L несколько.

Действительно, в порождающей и рабочей матрицах можно осуществлять элементарные операции со столбцами, а в проверочной — со строчками. Матрицы , и всегда удовлетворяют отношениям

где  — нулевая матрица .

Любая порождающая матрица может использоваться как рабочая.

Декодирующая матрица должна декодировать: . Матриц с таким свойством может быть несколько. Множество декодирующих матриц определяется рабочей матрицей:

где  — единичная матрица . На подпространстве L все декодирующие матрицы действуют одинаково. Они отличаются на подпространстве ортогональном L. Приведём декодирующую матрицу для Hem(7,4) и :

К каждой строчке декодирующей матрицы можно добавить любую линейную комбинацию строчек из проверочной матрицы. Следует отметить, что процесс исправления ошибок для кодов Хемминга нелинеен и его нельзя «внедрить» в декодирующую матрицу.

Сформулируем теперь основные моменты, касающиеся линейных кодов.

1. Процесс кодирования и декодирования — линейные операторы. :

2. Обнаружение ошибок равносильно проверке принадлежности полученного слова подпространству L допустимых слов. Для этого необходимо найти проекцию (синдром ошибки) полученного слова на  — тоже линейная операция. Для правильно переданного слова . :

3. В случае, когда векторы подпространства L достаточно удалены друг от друга в смысле метрики Хемминга, есть возможность обнаруживать и исправлять некоторые ошибки. В частности, значение синдрома ошибки в случае кода Хемминга равно векторной сумме номеров бит, где произошла ошибка.

4. Комбинация (композиция) линейных кодов есть снова линейный код.

Практические методы помехоустойчивого кодирования все основаны на линейных кодах. В основном это модифицированные CRC, коды Хемминга и их композиции. Например Hem(7,4) плюс проверка на чётность. Такой код может исправлять уже две ошибки. Построение эффективных и удобных на практике задача сходная с творчеством художника. На практике важны не только корректирующая способность кода, но и вычислительная сложность процессов кодирования и декодирования, а также спектральная характеристика результирующего аналогового сигнала. Кроме того, важна способность исправлять специфические для данного физического уровня групповые ошибки.

Задача 8.

Для данной проверочной матрицы постройте рабочую и декодирующую матрицу. Докажите, что кодовое расстояние равно 4.

Подсказка

1. Это проверочная матрица Hem(7,4) плюс условие на чётность числа единичек в закодированном слове вместе с дополнительным восьмым контрольным битом.

2. Кодовое расстояние равно минимальному количеству линейно зависимых столбцов в .

Конец задачи.

Задача 9.

Посторойте декодирующую и проверочную матрицу для циклического кода с G(x) = x³ + x + 1 и m = 4 при условии, что в качестве рабочей матрицы использовалась матрица

Конец задачи.