Двоичный симметричный канал
Математическое описание помехозащищенного кодирования
Чтобы описывать и сравнивать эффективность методов помехозащищенного кодирования нужна модель канала и ошибок в нем. Очевидно, что реальные каналы весьма разнообразны и описать их сразу все невозможно. Но и не имея модели — тоже ничего не сделать.
Решением этой проблемы служит простая модель «двоичного симметричного канала» и понятие «расстояние между двумя двоичными блоками».
Модель двоичного симметричного канала – простейшая модель канала с ошибками. Предполагается
1. Биты передаются по каналу последовательно — один за другим. Единомоментно передается только один бит, поэтому канал и называется двоичным.
2. Независимо от значения бита (0 или 1) вероятность его искажения постоянна и равна q. Поэтому канал называется симметричным.
Расстоянием Хемминга d(x1, x2) (метрикой Хемминга) между двумя битовыми блоками одинаковой длины x1 ={b1, b2, …bn} и x2 ={с1, с2, …сn} называется количество отличающихся бит на соответствующих позициях блока. Расстояние между абсолютно одинаковыми битовыми блоками равно нулю. Изменение одного бита в любом блоке увеличивает это расстояние на 1.
Очевидно, что расстоянием Хемминга между полученным и отправленным блоком можно характеризовать степень искажения информации.
Очевидно, что приемник не может сравнить полученный и отправленный блок. Если это возможно — значит приемнику известно точное значение отправленного блока. Если так — проблема искажений отсутствует.
Важно понять очевидную истину: обнаруживать и исправлять ошибки можно и нужно опираясь только на полученный блок данных. И ничего не зная про содержание отправленного.
Если передатчик использует ВСЕ возможные значения двоичного блока длиной m, то приемник не может обнаружить ошибку, ведь все значения блока допустимы. Однако закодированный двоичный блок длиной m может принимать 2m различных значений, а исходный блок длиной n < m имеет 2n различных значений. Т.е. 2m - 2n значений являются недопустимыми или лишними. Дополнительные m - n бит являются избыточной информацией.
Только получив недопустимое значение блока, приемник может обнаружить ошибку.
Избыточные биты желательно использовать так, чтобы обнаруживать и исправлять максимальное число ошибок. Здесь надо понимать — невозможно создать абсолютно помехозащищенный код. Всегда существует возможность такого искажения блока, что будет получено другое допустимое значение блока. Однако, желательно обеспечить максимальный эффект от «дополнительных» бит.
«Эффект» дополнительных бит проще всего определить как минимальное количество ошибок в блоке, которые код гарантированно может обнаружить и исправить. Чем больше это число – тем лучше используются дополнительные биты.
Эффективность блочного кода называется «корректирующей способностью кода». Корректирующая способность блочного кода определяется минимальным расстоянием Хемминга dmin между двумя допустимыми значениями блока кода.
Корректирующая способность t = [(dmin - 1)/2] определяет минимальное количество ошибок t в блоке кода, которое можно обнаружить и исправить, здесь […] обозначает взятие целой части.
Идеальным случаем является dmin = dmах, т.е. когда минимальное и максимальное расстояние между допустимыми значениями блоков равно. Тогда корректирующая способность максимальна, а избыточность данных минимальна. Такие коды называют «совершенными»
Коды обнаружения ошибок
Методы помехозащищенного кодирования направленные только на обнаружение ошибки называют – коды обнаружения ошибок. Обнаружение ошибки позволяет, в некоторых ситуациях, перезапросить данные с источника и исправить ошибку. Ну или не использовать ошибочные данные. Поскольку коррекция ошибок в этих методах не требуется, то размер дополнительно передаваемой информации минимален.
Простейшим кодом обнаружения ошибок является «контроль четности ». В этом случае, все сообщение разбивается на блоки бит равного размера, например, по 8-мь бит. И вычисляется сумма значений бит каждого из этих блоков. К блоку добавляется еще один бит: если сумма нечетная, то бит 1, иначе — бит 0. Т.е. получается блок длиной а один бит больше исходного — это «бит четности». При получении данных вычисление «бита четности» повторяется и результат сравнивается с переданным битом четности. Если вычисленное и переданное значение «бита четности» совпадают, то значит ошибки не было, иначе — ошибка передачи.
Легко сообразить, что искажение двух, четырех и любого четного количества бит в блоке не будет обнаружено.
Однако, в силу своей простоты, метод широко применяется в информационных каналах, где вероятность ошибки мала. Данный метод позволяет легко регулировать избыточность данных, выбирая размер блока. Чем больше исходный блок — тем меньше относительный размер дополнительной информации и тем выше вероятность пропустить ошибку.
Другим примером кодов обнаружения ошибок является «циклическая сумма » (Cyclic Redundancy Checksum или CRC). Этот метод является неблочным, но может быть использован и в блочном варианте. Принцип обнаружения ошибки схож с кодом «контроля четности». Используя особый алгоритм суммируются значения всех битов данных или порции данных, в результате суммирования получается некое число (не один бит, а несколько), которое передается вместе с данными или порцией данных. Принимающая сторона вычисляет CRC повторно и сравнивает с переданным.
«Контроль четности» — частный случай CRC.
Корректирующие коды — коды, служащие для обнаружения и исправления ошибок, возникающих при передаче информации под влиянием помех.
Для этого при передаче к исходной информации добавляют дополнительную информацию. Т.е. из исходного блока длиной n, делают блок длиной m, где m > n.
Приемник повторно вычисляет эту дополнительную информацию и сравнивает ее с переданной. На основании различий делается вывод о наличии или отсутствии ошибок. При обнаружении ошибок выполняется корректирующее действие.
Одним из самых простых, но неэффективных, способов коррекции является тройное мажорирование. Тройное мажорирование состоит в том, что данные (каждый бит или каждый блок битов) передаются три раза, а на приёмной стороне производится простое голосование по трём принятым значениям бита. Например, если требуется передать «1», то в канал связи поступит «111». В результате искажений может быть принято, например, «101», а после голосования получится «1» (так как в строке «101» единиц больше чем нулей). Однако искажение двух битов (например, принято «100», вместо «111») никогда не будет обнаружено и исправлено.
Надежность тройного мажорирования оставляет желать лучшего, ибо при некоторых типах информационных линий и некоторых типах ошибок обнаружить ошибку невозможно. Например, линия из 8-и проводов передает по 8-мь бит за такт (по одному через каждый провод). Если один из проводов оборван — эта ошибка никогда не будет обнаружена тройным мажорированием.
Другой существенный недостаток этого метода — перегрузка канала связи — передается в три раза больше бит, чем необходимо.