1.3. НА ПРИЕМНОМ КОНЦЕ

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

Тогда с вероятностью (в этом случае символ правильный) и с вероятностью символ неправильный). В примере первого параграфа было равно 1/100, но в общем случае может быть любым числом в диапазоне Итак, мы описываем действие канала, говоря, что он искажает кодовое слово х, прибавляя к нему вектор ошибок

Декодер (рис. 1.3) должен на основании у решить, какое сообщение и или (что обычно проще) какое кодовое слово было передано. Конечно, достаточно, если декодер найдет так как тогда Но декодер никогда не может знать наверняка, какой был вектор ошибок Его стратегия, следовательно, будет заклю чаться в выборе наиболее вероятного для данного принятого у вектора ошибок При условии, что все кодовые слова

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

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

Рис. 1.3. Полная система связи

Определение. Расстояние (Хэмминга) между двумя векторами равно числу позиций, в которых они различаются; оно обозначается например же самое определение справедливо и для недвоичных векторов).

Определение. Вес (Хэмминга) вектора равен числу ненулевых он обозначается например

Очевидно, что

так как обе части выражают число позиций, в которых различаются векторы х и у.

Упражнение. (7). Определим пересечение двоичных векторов х и у как вектор , имеющий единицы только в тех позициях, в которых их имеют оба вектора х и у, например Показать, что

Теперь вернемся к декодированию. Ошибки происходят с вероятностью например

В общем случае, если некоторый фиксированный вектор веса а, то

Так как

Следовательно, фиксированный вектор ошибок веса 1 более вероятен, чем фиксированный вектор ошибок веса 2, и т. д. Поэтому стратегия декодирования такова: у декодируется в ближайшее кодовое слово х (ближайшее в смысле расстояния Хэмминга), иначе говоря, выбирается вектор ошибок с наименьшим весом. Это называется декодированием в ближайшее кодовое слово.

Декодирование полным перебором заключается просто в сравнении у со всеми кодовыми словами и в выборе ближайшего слова. Это хорошо для небольших кодов. Но если велико, это невозможно! Одной из целей теории кодирования и является отыскание кодов, которые могут быть декодированы более быстрым методом, чем этот.

Минимальное расстояние кода. Третьим важным параметром кода кроме длины и размерности, является минимальное расстояние Хемминга между его кодовыми словами:

Число называется минимальным расстоянием или просто расстоянием кода. Любые два кодовых слова различаются по крайней мере в позициях.

Линейный код длины размерности и с минимальным расстоянием далее будет называться -кодом.

Для нахождения минимального расстояния линейного кода не обязательно сравнивать все возможные пары кодовых слов. Если принадлежат линейному коду то также является кодовым словом, и, как следует из (1.14),

Другими словами, справедлива теорема.

Теорема 1. Минимальное расстояние линейного кода равно минимальному весу ненулевых кодовых слов.

Пример. Минимальные расстояния кодов равны 3, 5, 2, 3 соответственно.

Как много ошибок может исправлять код?

Теорема 2. Код с минимальным расстоянием может исправлять ошибок. Если четное, то код может одновременно исправлять ошибок и обнаруживать ошибок.

Доказательство. Предположим, что (рис. 1.4). Шар радиуса с центром в точке и состоит из всех векторов таких, что Если вокруг каждого кодового слова описать шар радиуса 1, то эти шары не пересекаются. Если передавалось кодовое слово произошла одна ошибка, то принятый вектор а находится внутри шара, проведенного вокруг и, и поэтому а ближе к и, чем к любому другому кодовому слову Таким образом, декодирование в ближайшее кодовое слово исправит эту ошибку.

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

Рис. 1.4. Код с минимальным расстоянием обозначает кодовое слово)

Рис. 1.5. Код с минимальным расстоянием обозначает кодовое слово)

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

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

С другой стороны, если произошло больше чем ошибок, то принятый вектор может быть (или не быть) ближе к некоторому другому кодовому слову, а не к правильному. Если это произойдет, то декодер ошибется и выдаст неправильное кодовое слово. Это называется ошибкой декодирования. Конечно, с хорошим кодом это случается редко.

Пока что мы предположили, что декодер всегда будет пытаться найти ближайшее кодовое слово. Эта схема декодирования, называемая полным декодированием хороша для сообщений, которые не могут быть переданы еще раз, таких как фотография с Марса или старая магнитная лента. В таком случае мы хотим извлечь из принятого вектора как можно больше.

Но часто мы хотим быть более осторожными или просто не в состоянии воспользоваться самым дорогим методом декодирования. В таких случаях можно пользоваться следующей стратегией неполного декодирования: если полагается, что произошло не более чем I ошибок, то они исправляются, в противном случае сообщение отвергается или переспрашивается.

Обнаружение ошибок представляет собой предельный вариант такой стратегии, когда получатель не пытается исправлять ошибки, а только проверяет, является ли принятый вектор кодовым словом. Если это не так, то он обнаруживает, что произошла ошибка, и просит еще раз передать сообщение. Эта схема имеет те преимущества, что алгоритм обнаружения ошибок очень прост (смотри следующий раздел) и что вероятность необнаруженной ошибки: очень мала (см. § 1.5). Недостатком схемы является то, что в

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

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

Рис. 1.6. Троичный симметричный канал вероятность ошибки)

Предположим, что равно 0 с вероятностью и равно любому из ненулевых элементов с вероятностью Другими словами, канал является -ичным симметричным каналом с входами, выходами, вероятностью что никакой ошибки не произошло, и вероятностью что произошла ошибка, причем все возможных ошибок равновероятны.

Пример. Для случая троичный симметричный канал показан на рис. 1.6.

Упражнения. (8). Показать, что для двоичных векторов:

причем равенство выполняется, если и только если всегда, когда

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

(9). Для векторов х и у над любым полем определим их произведение как вектор .

Для двоичных векторов это называется пересечением — см. упражнение (7). Показать, что для троичных векторов

где если вектор содержит а нулей, единиц и с двоек. Следовательно,

(10). Показать, что в линейном двоичном коде либо все кодовые слова имеют четный вес, либо точно половина слов имеет четный вес и половина слов имеет нечетный вес.

(11). Показать, что в линейном двоичном коде либо все кодовые слова начинаются с 0, либо точно половина слов начинается и половина слов начинается с 1. Обобщите!

Оба упражнения (10) и (11) следуют из упражнения (12).

(12). Предположим, что абелева группа, которая содержит подмножество А, удовлетворяющее следующим трем свойствам: (i) если то если то если то а Показать, что либо либо А — подгруппа и существует элемент такой, что

где — множество всех элементов вида

(13). Показать, что расстояние Хэмминга удовлетворяет неравенству треугольника: для любых векторов

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

(14). Как следствие показать, что если минимальное расстояние кода равно и при передаче кодового слова произошло не более чем ошибок, то для всех кодовых слов выполняется неравенство где у — принятый вектор (более формальное доказательство теоремы 2).

(15). Показать, что код одновременно может исправлять ошибки кратности не более чем а и обнаруживать ошибки кратности если и только если код имеет по крайней мере расстояние

(16). Показать, что если х и у — двоичные векторы, то евклидово расстояние между точками х и у равно

(17). Комбинирование двух кодов (I). Пусть порождающие матрицы для -кодов соответственно. Показать, что коды с порождающими матрицами

представляют собой -коды соответственно, причем

(18). Биномиальные коэффициенты. Биномиальный коэффициент который читается «число сочетаний из по определяется следующим образом:

где любое действительное число, а Читатель должен знать следующие свойства:

(a). Если натуральное число и то

что равно числу всех возможных неупорядоченных выборок по элементов из множества элементов.

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

(c). Биномиальные ряды:

[Помните о студенте, который на экзаменационный вопрос о разложении в ряд выражения ответил:

Простые тождества. (Здесь целые неотрицательные числа, любое действительное число.)

(см. скан)

(19). Предположим, что двоичные векторы с расстоянием Показать, что число векторов таких, что равно где .

Если нечетно, то число таких векторов равно нулю, в то же время если то это число равно

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