Помехоустойчивое кодирование Свойства линейных кодов
Расстояние и вес Хэмминга Пусть заданы двоичные слова Расстояние Хэмминга Вес Хэмминга
Расстояние Хэмминга Пусть - линейный код и Тогда и их поразрядная сумма Обозначим Получим Расстояние Хэмминга
Минимальное расстояние Хэмминга минимальный вес кода
Модель ошибки Замена В линейном пространстве n-разрядных двоичных столбцов это равносильно преобразованию кодового слова: - вектор ошибки
Модель ошибки Если в кодовом слове произошло t ошибок, то ошибочное слово находится на расстоянии t от кодового. Или вес вектора ошибки равен t:
Синдромное декодирование линейного кода
Корректирующая способность линейного кода – геометрическая иллюстрация Шар с центром в кодовом слове – кодовое слово + ошибочные слова из столбца при синдромном декодировании
Модель ошибки – геометрическая интерпретация Центры шара – кодовые слова Шар – кодовое слово и всевозможные ошибочные слова, полученные из кодового слова
Корректирующая способность линейного кода Случай 1. Распознаваемая и исправляемая ошибка( Случай 1. Распознаваемая и исправляемая ошибка ( ошибочное слово находится внутри «своей» сферы)
Корректирующая способность линейного кода Случай 2. Распознаваемая ошибка (ошибочное слово – вне «своей» сферы)
Случай 3. Необнаруженная ошибка (ошибочное слово совпадает с некоторым кодовым словом)
Случай 4. Отказ от декодирования(ошибочное слово не принадлежит ни однму из шаров)
Модель ошибки – геометрическая интерпретация Ошибка распознается и исправляется, если шары не пересекаются и ошибочные слова - внутри сферы.
Пример – систематический (7,4)-код Хэмминга - проверочная матрица
Пример – систематический (7,4)-код Хэмминга d=3, t=1 Кодовые слова: , , ,……..
Модель ошибки
Совершенный код
Совершенные коды Коды, в которых непересекающиеся сферические области декодирования покрывают все пространство двоичных слов, называются совершенными или плотноупакованными. Пусть дан (n,k)–код, исправляющий t ошибок. Тогда каждый шар содержит ровно слов (объем шара) Всего кодовых слов (всего шаров) -
Совершенный код Отсюда Или
Граница Хэмминга Отсюда Или Для совершенных кодов