Минимальное кодовое расстояние и корректирующая способность

Расстояние между битовыми блоками. Метрика Хемминга

Двоичный симметричный канал

Математическое описание помехозащищенного кодирования

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

Решением этой проблемы служит простая модель «двоичного симметричного канала» и понятие «расстояние между двумя двоичными блоками».

Модель двоичного симметричного канала – простейшая модель канала с ошибками. Предполагается

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

2. Независимо от значения бита (0 или 1) вероятность его искажения постоянна и равна q. Поэтому канал называется симметричным.

Расстоянием Хемминга d(x₁, x₂) (метрикой Хемминга) между двумя битовыми блоками одинаковой длины x₁ ={b₁, b₂, …b_n} и x₂ ={с₁, с₂, …с_n} называется количество отличающихся бит на соответствующих позициях блока. Расстояние между абсолютно одинаковыми битовыми блоками равно нулю. Изменение одного бита в любом блоке увеличивает это расстояние на 1.

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

Очевидно, что приемник не может сравнить полученный и отправленный блок. Если это возможно — значит приемнику известно точное значение отправленного блока. Если так — проблема искажений отсутствует.

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

Если передатчик использует ВСЕ возможные значения двоичного блока длиной m, то приемник не может обнаружить ошибку, ведь все значения блока допустимы. Однако закодированный двоичный блок длиной m может принимать 2^m различных значений, а исходный блок длиной n < m имеет 2ⁿ различных значений. Т.е. 2^m - 2ⁿ значений являются недопустимыми или лишними. Дополнительные m - n бит являются избыточной информацией.

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

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

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

Эффективность блочного кода называется «корректирующей способностью кода». Корректирующая способность блочного кода определяется минимальным расстоянием Хемминга d_min между двумя допустимыми значениями блока кода.

Корректирующая способность t = [(d_min - 1)/2] определяет минимальное количество ошибок t в блоке кода, которое можно обнаружить и исправить, здесь […] обозначает взятие целой части.

Идеальным случаем является d_min = d_mах, т.е. когда минимальное и максимальное расстояние между допустимыми значениями блоков равно. Тогда корректирующая способность максимальна, а избыточность данных минимальна. Такие коды называют «совершенными».