14. Принцип помехоустойчивого кодирования. Классификация кодов.

Код, способный обнаружить или исправить ошибки, называют корректирующим.

Корректирующие или помехоустойчивые коды строятся так, что для передачи сообщения используются не все кодовые комбинации, а лишь некоторая их часть ( разрешенные кодовые комбинации ). Тем самым создается возможность обнаружения и исправления ошибки при неправильном воспроизведении некоторого числа символов. Корректирующие свойства кодов достигаются введением в кодовые комбинации дополнительных ( избыточных ) символов.

Каждому символу исходного алфавита сообщений N поставим в соответствии n- элементную двоичную последовательность – кодовую комбинацию. Тогда общее число последовательностей длины n , будет , причем должно соблюдаться условие.

Если, то все возможные кодовые комбинации кода используются для передачи сообщений ( разрешенные комбинации ). Такой код называется простым.

Степень различия кодовых комбинаций называется кодовым расстоянием. Кодовое расстояние для двух любых кодовых комбинаций определяется числом несовпадающих в них разрядов.

Например:

010



100

110

Подсчитав количество 1 получим кодовое расстояние d=2. Иначе кодовое расстояние определяется как все суммы по модулю 2. Весом кодовой комбинации называется число входящих в нее ненулевых элементов. Перебрав все возможные пары кодовых комбинаций можно найти минимальное кодовое расстояние или расстояние Хэмминга.

Для простого кода . Любая ошибка ( даже одиночная ) приведет к тому, что переданная разрешенная комбинация перейдет в другую разрешенную кодовую комбинацию. Таким образом, простой код не способен обнаруживать и тем более исправлять ошибки.

Для того, чтобы код мог обнаруживать ошибки, необходимо, чтобы выполнялось условие . Кодовые комбинациибудут называться запрещенными и для передачи информации не используются. Они определяют избыточность кода. Обнаружение ошибки произойдет, если разрешенная кодовая комбинация перейдет в запрещенную. В качестве разрешенных кодовых комбинаций берутся такие, которые максимально отличаются друг от друга. Помехоустойчивые коды должны иметь минимальное кодовое расстояние.

Пример:

Алфавит передаваемых сообщений N=2. Возьмем максимально отличающиеся кодовые комбинации – 000, 111. Кодовое расстояние . Ошибки кратности один или два превращает кодовую комбинацию в запрещенную. Максимальная кратность обнаруживаемых ошибок равна двум ().

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

Вывод о том какая кодовая комбинация передавалась, делается на основании сравнения принятой запрещенной комбинации со всеми разрешенными. Принятая комбинация отождествляется с той комбинацией, от которой она отличается меньше. Например: передавалась 000, принята запрещенная 001. Вынесено решение, что передавалась 000.

Очевидно, что чем больше минимальное кодовое расстояние, тем лучше код обнаруживает и исправляет ошибки. Но при больших n перебор кодовых комбинаций для сравнения может оказаться непосильным даже для современных ЭВМ. Кроме того, это приводит к уменьшению скорости передачи. Поэтому основное направление теории помехоустойчивого кодирования заключается в поисках таких классов кодов , для которых кодирование и декодирование осуществляются не перебором кодовых комбинаций для сравнения, а с помощью некоторых регулярных правил , определенных алгебраической структурой кодовых комбинаций.

Классификация помехоустойчивых кодов.

Помехоустойчивые или корректирующие блоки подразделяются на два основных вида: блочные и непрерывные. К блочным относятся коды, в которых каждому символу алфавита сообщений соответствует блок ( кодовая комбинация ) из n (i) элементов, где i- номер сообщения. Если длина блока ( кодовой комбинации ), то код называется равномерным ( код Бодо ). Если кодовые комбинации отличаются длиной, то блочный код называется неравномерным ( код Морзе ).

В непрерывных кодах передаваемая информационная последовательность не разбивается на блоки, а проверочные элементы размещаются в определенном порядке между информационными.

Равномерные блочные коды делятся на разделимые и неразделимые.

В разделимых кодах элементы разделяются на информационные и проверочные, занимающие определенные места в кодовой комбинации.

В неразделимых кодах отсутствует деление элементов кодовых комбинаций на информационные и проверочные ( семиэлементный телеграфный код № 3 ).

Разделимые коды подразделяются на систематические и несистематические.

Систематическими называют коды, у которых сумма по модулю два двух разрешенных комбинаций дает разрешенную комбинацию того же кода. Особенностью этих кодов является то, что информационные и проверочные элементы связаны между собой зависимостями, которые описываются линейными уравнениями. Отсюда второе название этих кодов – линейные. К этим кодам относятся код Хэмминга и циклические коды. Для систематического кода применяется обозначение (n, r ) – код, где n – число элементов в комбинации, r – число информационных элементов.