Контроль данных при вводе и передаче по каналам

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

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

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

Популярным здесь является контроль по модулю 11 или по модулю 97. Можно в качестве модуля использовать и другие простые числа. Обозначим модуль буквой Р.

Пусть мы вводим шестизначные числа. Обозначим их Х₁Х₂Х₃Х₄Х₅Х₆. Введём шесть различных весовых множителей W₁, W₂, W₃, W₄, W₅, W₆, не превосходящих Р. Например, 1, 2, 3, 4, 5, 6.

Введём сумму S = W₁X₁ + W₂X₂ + W₃Х₃ + W₄X₄ + W₅Х₅ + W₆X₆ и определим число Y = S mod P, которое называется контрольным разрядом.

Очевидно, что Y< P. Заменим данные шестизначные числа Х₁Х₂Х₃Х₄Х₅Х₆ на Х₁Х₂Х₃Х₄Х₅Х₆Y. Полученная комбинация удовлетворяет условию: сумма (W₁X₁ + W₂X₂ + W₃Х₃ + W₄X₄ + W₅Х₅ + W₆X₆ - Y) mod P = 0, т.е. величина стоящая в скобках делится нацело на Р. После ввода расширенной комбинации указанное условие проверяется. Если условие для введённой последовательности Х₁Х₂Х₃Х₄Х₅Х₆Y выполняется, считается, что последовательность введена без ошибок.

Наибольшее распространение нашёл модуль Р = 11. Можно доказать, что с помощью этого метода обнаруживаются все одиночные и некоторые двойные ошибки. Существенный недостаток этого метода, связан с тем, что контрольный разряд может оказаться равным 10, т.е. быть двухзначным, а расширенные комбинации имеют при этом переменную длину. Чтобы избежать этого вместо 10 подставляют 0, что снижает эффективность метода. Метод, основанный на модуле 97, лишён этого недостатка. Здесь все контрольные величины можно считать двухзначными. Кроме того, в случае Р = 97 мы можем использовать 96 весовых множителя, а не 10.

Рассмотрим пример. Пусть необходимо ввести комбинацию 823842. Эта комбинация не обладает избыточностью, и ее ввод не может нами контролироваться. Воспользуемся Р = 11 и весовыми множителями (1, 2, 3, 4, 5, 6). Получим S = 1*8 + 2*2 + 3*3 + 4*8 + 5*4 + 6*2 = 85 и Y = 85 mod 11 = 8. Поэтому вместо комбинации 823842 мы вводим 82384208. Эта комбинация цифр удовлетворяет условию 1*8 + 2*2 + 3*3 + 4*8 + 5*4 + 6*2 - 8 = 77, т.е. делится на 11 без остатка. Любая единичная ошибка приводит к тому, что это условие перестанет выполняться и ошибка будет обнаружена.

Если приходится иметь дело с потоком десятичных цифр, то можно разбить его на отрезки, длина которых может достигать 10 в случае Р = 11 и 96 в случае Р = 97. Получим контрольные разряды Y₁, Y₂, ..., Y_m. Эту последовательность можно при необходимости свернуть, применяя к этой десятичной последовательности ту же технологию подсчёта контрольного разряда.

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

Приведённые выше способы контроля не исчерпывают всех возможных. Например, для данной комбинации цифр Х₁Х₂Х₃Х₄Х₅Х₆ можно ввести две серии весовых множителей V₁, V₂, V₃, V₄, V₅, V₆ и U₁, U₂, U₃, U₄, U₅, U₆ и два контрольных разряда Y₁ и Y₂. В результате получим расширенную комбинацию Х₁Х₂Х₃Х₄Х₅Х₆Y₁Y₂. Надёжность контроля при этом возрастает.

Хотя математики занимаются задачами контроля достаточно давно, их интересы ограничиваются в основном двоичными данными, где получено огромное количество результатов. Для десятичных данных исследован подробно только случай Р = 11.