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


Групповые коды - часть 2


Каждый элемент из однозначно представляется в виде суммы , где - лидер соответствующего смежного класса и .

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

Если в рассматриваемой таблице в первом столбце записать лидеры, то полученная таблица называется таблицей декодирования. Она имеет вид:

То, что строк будет следует из теоремы Лагранжа1)

, т.к. - это порядок фактор-группы , , .

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

Для -кода из рассматриваемого примера таблица декодирования будет следующей:

Первая строка в ней - это строка кодовых слов, а первый столбец - это лидеры.

Чтобы декодировать слово , следует отыскать его в таблице и выбрать в качестве переданного слово в том же столбце и в первой строке.

Например, если принято слово 110011 (2-я строка, 3-й столбец таблицы), то считается, что было передано слово 010011; аналогично, если принято слово 100101 (3-я строка, 4-й столбец таблицы), переданным считается слово 110101, и т.д.

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

В рассмотренной схеме вероятность правильной передачи слова будет .

Кодовое слово любого столбца таблицы декодирования является ближайшим кодовым словом ко всем прочим словам данного столбца.

Пусть переданное слово принято как , , т.е. это расстояние равно весу соответствующего лидера. Расстояние от до любого другого кодового слова равно весу их поразрядной суммы, т.е.

т.к. - лидер смежного класса, к которому принадлежат как , так и .

Доказано, при схеме декодирования лидерами по полученному слову берется ближайшее к нему кодовое.

Упражнение 40

Для кодирующих матриц

, :

  1. Построить соответственно -код и -код.
  2. Найти основные характеристики полученных кодов: минимальное расстояние между словами кода; вероятность необнаружения ошибки; максимальную кратность ошибок, до которой включительно они все исправляются или обнаруживаются.
  3. Построить таблицы декодирования.
  4. Уточнить характеристики полученных кодов, при использовании их для исправления ошибок, т.е. найти вероятность правильной передачи и описать ошибки, исправляемые этими кодами.
  5. Во что будут декодированы слова: 10001, 01110, 10101, 1001, 0110, 1101?




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



Книжный магазин