с древовидным шумозащитным кодом имеет
Работа с древовидным шумозащитным кодом имеет сходство с работой с арифметическим кодом для сжатия информации.
Расстоянием (Хэмминга) между двоичными словами длины называется количество позиций, в которых эти слова различаются. Это одно из ключевых понятий теории кодирования. Если обозначить двоичные слова как и , то расстояние между ними обозначается .
Весом двоичного слова называется количество единиц в нем. Обозначение . Можно сказать, что .
Пример. Пусть и , тогда , .
Далее операция при применении к двоичным словам будет означать поразрядное сложение без переноса, т.е. сложение по модулю 2 или "исключающее ИЛИ" (XOR).
Расстояние между двоичными словами и равно весу их поразрядной суммы, т.е. .
Если два слова различаются в каком-либо разряде, то это добавит единицу к весу их поразрядной суммы.
Следовательно, если и - слова длины , то вероятность того, что слово будет принято как , равна .
Наример, вероятность того, что слово 1011 будет принято как 0011, равна .
Для возможности обнаружения ошибки в одной позиции минимальное расстояние между словами кода должно быть большим 1.
Иначе ошибка в одной позиции сможет превратить одно кодовое слово в другое, что не даст ее обнаружить.
Для того, чтобы код давал возможность обнаруживать все ошибки кратности, не большей , необходимо и достаточно, чтобы наименьшее расстояние между его словами было .
Достаточность доказывается конструктивно: если условие утверждения выполнено для , то в качестве декодирующей функции
следует взять функцию, сообщающую об ошибке, если декодируемое слово отличается от любого из слов из образа . Необходимость доказывается от противного: если минимальное расстояние , то ошибка в позициях сможет превратить одно кодовое слово в другое.
Для такого кода вероятность того, что ошибки в сообщении останутся необнаруженными, равна при малых и не слишком маленьких .
Для того, чтобы код давал возможность исправлять все ошибки кратности, не большей , необходимо и достаточно, чтобы наименьшее расстояние между его словами было .
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий