Групповые коды - часть 2
Каждый элемент из однозначно представляется в виде суммы , где - лидер соответствующего смежного класса и .
Множество классов смежности группы образуют фактор-группу, которая есть фактор-множество множества по отношению эквивалентности-принадлежности к одному смежному классу, а это означает, что множества, составляющие это фактор-множество, образуют разбиение . Отсюда следует, что строки построенной таблицы попарно либо не пересекаются, либо совпадают.
Если в рассматриваемой таблице в первом столбце записать лидеры, то полученная таблица называется таблицей декодирования. Она имеет вид:
То, что строк будет следует из теоремы Лагранжа1)
, т.к. - это порядок фактор-группы , , .
Декодирование слова состоит в выборе кодового слова в качестве переданного и последующем применении операции, обратной умножению на . Такая схема декодирования сможет исправлять ошибки.
Для -кода из рассматриваемого примера таблица декодирования будет следующей:
Первая строка в ней - это строка кодовых слов, а первый столбец - это лидеры.
Чтобы декодировать слово , следует отыскать его в таблице и выбрать в качестве переданного слово в том же столбце и в первой строке.
Например, если принято слово 110011 (2-я строка, 3-й столбец таблицы), то считается, что было передано слово 010011; аналогично, если принято слово 100101 (3-я строка, 4-й столбец таблицы), переданным считается слово 110101, и т.д.
Групповое кодирование со схемой декодирования посредством лидеров исправляет все ошибки, строки которых совпадают с лидерами. Следовательно, вероятность правильного декодирования переданного по двоичному симметричному каналу кода равна сумме вероятностей всех лидеров, включая нулевой.
В рассмотренной схеме вероятность правильной передачи слова будет .
Кодовое слово любого столбца таблицы декодирования является ближайшим кодовым словом ко всем прочим словам данного столбца.
Пусть переданное слово принято как , , т.е. это расстояние равно весу соответствующего лидера. Расстояние от до любого другого кодового слова равно весу их поразрядной суммы, т.е.
т.к. - лидер смежного класса, к которому принадлежат как , так и .
Доказано, при схеме декодирования лидерами по полученному слову берется ближайшее к нему кодовое.
Упражнение 40
Для кодирующих матриц
, :
- Построить соответственно -код и -код.
- Найти основные характеристики полученных кодов: минимальное расстояние между словами кода; вероятность необнаружения ошибки; максимальную кратность ошибок, до которой включительно они все исправляются или обнаруживаются.
- Построить таблицы декодирования.
- Уточнить характеристики полученных кодов, при использовании их для исправления ошибок, т.е. найти вероятность правильной передачи и описать ошибки, исправляемые этими кодами.
- Во что будут декодированы слова: 10001, 01110, 10101, 1001, 0110, 1101?