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


Математическая модель системы связи - часть 3


Работа с древовидным шумозащитным кодом имеет сходство с работой с арифметическим кодом для сжатия информации.

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

Весом двоичного слова называется количество единиц в нем. Обозначение . Можно сказать, что .

Пример. Пусть и , тогда , .

Далее операция при применении к двоичным словам будет означать поразрядное сложение без переноса, т.е. сложение по модулю 2 или "исключающее ИЛИ" (XOR).

Расстояние между двоичными словами и равно весу их поразрядной суммы, т.е. .

Если два слова различаются в каком-либо разряде, то это добавит единицу к весу их поразрядной суммы.

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

Наример, вероятность того, что слово 1011 будет принято как 0011, равна .

Для возможности обнаружения ошибки в одной позиции минимальное расстояние между словами кода должно быть большим 1.

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

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

Достаточность доказывается конструктивно: если условие утверждения выполнено для , то в качестве декодирующей функции

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

Для такого кода вероятность того, что ошибки в сообщении останутся необнаруженными, равна

при малых и не слишком маленьких .

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




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



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