Теория информации


Групповые коды


Множество всех двоичных слов длины

образует абелеву (коммутативную) группу относительно поразрядного сложения.

Пусть - кодирующая -матрица, у которой есть -подматрица с отличным от нуля определителем, например, единичная. Тогда отображение переводит группу всех двоичных слов длины в группу кодовых слов длины .

Предположим, что . Тогда для , , , получаем

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

Блочный код называется групповым, если его кодовые слова образуют группу.

Если код является групповым, то наименьшее расстояние между двумя кодовыми словами равно наименьшему весу ненулевого слова.

Это следует из соотношения .

В предыдущем примере наименьший вес ненулевого слова равен 3. Следовательно, этот код способен исправлять однократную ошибку или обнаруживать однократную и двойную.

При использовании группового кода незамеченными остаются те и только те ошибки, которые отвечают строкам ошибок, в точности равным кодовым словам.

Такие строки ошибок переводят одно кодовое слово в другое.

Следовательно, вероятность того, что ошибка останется необнаруженной, равна сумме вероятностей всех строк ошибок, равных кодовым словам.

В рассмотренном примере вероятность ошибки равна .

Рассмотрим задачу оптимизации декодирования группового кода с двоичной матрицей кодирования . Требуется минимизировать вероятность того, что .

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

Лидером каждого из таких построенных смежных классов называется слово минимального веса.




- Начало -    - Вперед -