Контроль по модулю

Коды Хэмминга

Коды, предложенные американским ученым Р. Хэммингом, обладают способностью не только обнаружить, но и исправить одиночные ошибки. Эти коды – систематические.

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

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

Рассмотрим основные положения из теории сравнений.

Если целым числам А и В соответствует один и тот же остаток от деления на третье число р, то числа А и В равноостаточны друг другу по модулю р или сравнимы по модулю р. Сравнения — уравнения типа:

А = В(mod р).

Сравнимость двух чисел равносильна возможности представить их в алгебраическом виде

А = В + р1.

Сравнения обладают рядом свойств:

Сравнения можно почленно складывать. Если А₁ ≡ В₁(mod р);

А₂ ≡ В₂(mod р);...; А_n≡В_п(mod р), то А₁ + А₂ +... + А_п ≡ В₁ + В₂ +... + В_n(mod р).

Следовательно, слагаемое, стоящее в какой-либо части сравнения, можно переносить в другую часть, поменяв при этом его знак, т. е. А + В ≡ С(mod р) или А ≡ С - В(mod р).

Два числа, сравнимые с третьим числом, сравнимы и между собой:
если А ≡ В(mod р); С = B(mod р), то А ≡ С(mod р).

Сравнения можно почленно перемножить. Пусть A₁ ≡ В₁ (mod p);
А₂ ≡ В₂(mod p). Тогда A₁ = B₁ + l₁p; А₂ = В₂ + l₂р.

После умножения получаем А₁А₂ = В₁В₂ + В₁l₂p + В₂l₁р + l₁l₂pp. Следовательно, А₁А₂ = В₁В₂ + Np, или в общем случае:

А₁А₂А₃...А_m ≡ В₁В₂В₃...В_m (mod p).

Из свойства 3 также следует, что обе части сравнения можно умножить на одно и то же целое число.

Пусть А ≡ В(mod p); К = К(mod p). Тогда АК ≡ ВК(mod p).

Обе части сравнения и модуль можно умножить на одно и то же число:

А = В + lp; Аm = Вm + mlp, т. е. Аm = Вm(mod mp).

Обе части сравнения и модуль можно разделить на любой общий делитель. Пусть А ≡ B(mod p), где А = ad, В = bd, Р = p₁d. Тогда А = В + lp.

Подставив в это выражение значения А, В и Р, получим

ad = bd + lp₁d.

Разделив уравнение на d, получим а = b + lp₁, т. е. a = b(mod p₁).

Обе части сравнения можно возвести в степень. Если А ≡ В(mod p),

то А" = В"(mod p).

Из свойства 6 следует, что над сравнениями можно провести операцию извлечения корня n-й степени.

Рассмотренные выше свойства сравнений используются для осуществления операции контроля.

Существуют два метода получения контрольного кода: числовой и цифровой.

Дата добавления: 2014-01-06