Июнь 18th, 2013
Например, для двоичногоИ00,80)-кода требуется таблица декодирования с 2100 входами, что, конечно, далеко выходит за пределы разумного. Число смежных классов равно 220 — величине, много меньшей, но тем не менее все еще совсем нереальной.Теорема 3.7. Пусть V — линейный двоичный (п, k)-Kod (т. е. групповой код), используемый для передачи по двоичному симметричному каналу. Предположим, что все кодовые векторы имеют одну и ту же вероятность быть переданными. Тогда средняя вероятность правильного декодирования совпадает с наибольшей возможной для этого кода, если в качестве таблицы декодирования используется стандартное расположение, в котором каждый образующий смежного класса имеет минимальный вес в своем классе.Доказательство. Обозначим через v- вектор, стоящий в i-й строке и -м столбце таблицы декодирования. Кодовое слово в верхней строке столбца обозначим через v0j. Обозначим через da расстояние Хэмминга между полученным вектором \ и кодовым словом v0j, в которое он преобразуется при декодировании. Тогда вероятность правильного декодирования, если было передано слово V(y, равнагде P — вероятность ошибки в канале, a Q = 1 — Р (см. фиг. 1.4). Поскольку имеется 2h кодовых слов, которые предполагаются равновероятными, то при осреднении вероятности правильного декодирования используется весовой множитель 2~k:Каждому возможному двоичному вектору на выходе в этой сумме соответствует одно слагаемое, и каждое из этих слагаемых принимает максимальное значение, если соответствующий вектор декодируется в ближайший кодовый вектор в смысле Хэмминга, так как Р UQn~dti есть монотонно убывающая функция от d.
