Достаточность доказывается конструктивно: если условие
Достаточность доказывается конструктивно: если условие утверждения выполнено для , то в качестве декодирующей функции следует взять функцию, возвращающую ближайшее к декодируемому слово из образа . Необходимость доказывается от противного. Пусть расстояние между выбранными словами в коде равно . Тогда если при передаче каждого из этих слов случится ошибок, которые изменят биты, в которых различаются эти слова, то приемник получит два идентичных сообщения, что свидетельствует о том, что в данной ситуации исправление ошибок невозможно. Следовательно, минимальное расстояние между словами кода должно быть большим .
Пример. Рассмотрим -код, состоящий из , задающей отображение и , и , задающей отображение . Этот код (с тройным повторением) исправляет ошибки в одной позиции, т.к. минимальное расстояние между словами кода равно 3.
Если код исправляет все ошибки кратности и меньшей, то вероятность ошибочного приема слова длины очевидно не превосходит . Вероятность правильного приема в этом случае не меньше, чем
Передачу данных часто удобно рассматривать следующим образом. Исходное сообщение кодируется функцией в кодовое слово . Канал связи при передаче добавляет к нему функцией
строку ошибок так, что приемник получает сообщение , где . Система, исправляющая ошибки, переводит в некоторое (обычно ближайшее) кодовое слово. Система, только обнаруживающая ошибки, лишь проверяет, является ли принятое слово кодовым, и сигнализирует о наличии ошибки, если это не так.
Пример. Пусть передаваемое слово кодируется словом , а строка ошибок - . Тогда будет принято слово . Система, исправляющая ошибки, переведет его в 0110 и затем восстановит переданное слово 01.
Если система только обнаруживает ошибки и расстояние между любыми кодовыми словами , то любая строка ошибок с единственной единицей приведет к слову , которое не является кодовым.
Пример. Рассмотрим -код с проверкой четности. Множество кодовых слов - . Ни одна из строк ошибок 001, 010, 100, 111 не переводит одно кодовое слово в другое.
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий