Помехоустойчивость. Восстановление информации в канале с шумом

При передаче данных (по сетям и внутри компьютера) возможны ошибки. Между тем ошибка даже в одном двоичном разряде может полностью исказить передаваемый текст, если это программа или сжатый по Хафмену текст.
Для уменьшения числа ошибок информацию часто передают с дополнительными проверочными данными - контрольными суммами.
Самый простой вариант контрольной суммы используется при передаче отдельных байтов. В записи байта выделяется один специальный разряд, бит четности - в некоторых случаях это восьмой бит, но чаще девятый, специально добавляемый в аппаратуре и невидимый для пользователя. При каждой передаче байта внутри компьютера передаются 9 битов, и четность передаваемого байта контролируется. Наряду с этим контролем, встроенным в аппаратуру предусмотрены разнообразные системы контроля в программных средствах передачи и обработки информации. Например, пр передаче информации с системе электронной почты и в Интернет предусматриваются контрольные суммы у каждого передаваемого пакета. Сейчас контрольное суммирование используется и для распознавания заражения компьютера вирусами - у зараженных программ изменяется контрольная сумма.
Очень прост и нагляден код Хемминга, который позволяет найти ошибку в последовательности битов при условии, что ошибок не больше одной. Рассмотрим этот способ кодирования. Если требуется передать n битов, а передается N, где N>=n, битов, то для возможности обнаружения ошибки нужно, чтобы в передаваемом тексте, кроме n битов основного текста, хватало места для распознавания одной из N+1 возможностей положения места ошибки (нулевая возможность - текст передан без ошибок). Таким образом, 2^N-n>=N+1. Видно, что необходимое приращение числа контрольных битов зависит от длины кодовой последовательности: N-n приблизительно равно Log2N. Вот таблица, показывающая максимальное значение n для некоторых значений N-n:

Покажем, что при достаточном добавлении битов можно сделать очень простой код, обнаруживающий один онибочный бит. Пусть задано некоторое n и N выбрано так, что выполнено приведенное неравентсво. передаваемые биты нумеруются от 1 до N и, зарезервировав номера 1, 2, 3, 4, 8, и т.д. (степени числа 2), все остальные места сопоставим местам в исходной последовательности. Сформируем матрицу контрольного суммирования, составленную из 0 и 1, в этой матрице N столбцов и N-n строк, каждый j- столбец содержит двоичное представление числа j. Эта матрица будет умножаться на передаваемый вектор. Выберем значения в резервных столбцах так, чтобы все компоненты вектора-произведения равнялись 0 по модулю 2.
Сформированный таким образом вектор передается по каналам связи и при получении умножается на ту же матрицу. Вектор остатков от деления его компонент на 2 может рассматриваться как двоичное разложение некоторого целого числа k. Если оно равно 0, информация передана без ошибок. Если больше 0, то число K дает номер бита с ошибкой.