Блог → Вычисление циклического контрольного кода

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

В основе теории вычисления контрольной информации циклического контрольного кода лежит понятие полинома, или, как его еще называют, многочлена. Полином - это формально заданный степенной ряд, т.е. сумма множества степенных выражений независимых переменных. Например (рис. 1):



Степень полинома - это число r, равное максимальному показателю степени полинома (в нашем случае r=4). Отметим, что количество слагаемых в полиноме всегда на единицу больше степени полинома. Приведенный пример не противоречит этому утверждению, поскольку формально он должен быть записан так (рис. 2):



В общем случае любой блок информации в памяти вычислительной машины (если рассматривать в качестве переменной х один бит) можно считать полиномом. Назовем его информационным полиномом и обозначим А(х). Для вычисления контрольного кода понадобится еще один полином - порождающий. Этот полином обозначим G(x). Порождающий полином в некотором смысле - это ключ циклического кода. Чтобы получить контрольное число, которое также можно описать с помощью полинома, информационный полином надо умножить на х в степени r (что соответствует сдвигу на r разрядов влево), а затем разделить на порождающий полином. Остаток от деления R(x) и будет контрольным числом (рис. 3, где r - степень порождающего полинома):



Обычно контрольное число применяют следующим образом. R(x), вычисленное перед записью информационного полинома в запоминающее устройство, является образцовым (эталонным) и хранится отдельно. Для проверки целостности информационного полинома необходимо снова вычислить R(x) и сравнить его с образцовым. Несовпадение чисел означает, что в информационный полином были внесены искажения.

Из формулы (3) видно, что вычисление контрольного числа сводится к умножению и делению числа произвольной разрядности. Если умножение информационного полинома на х реализуется тривиально, как дописывание в "хвост" полинома r нулевых разрядов, то для деления полиномов необходимо реализовать специальный алгоритм, суть которого сводится к следующему: r+1 старших разрядов информационного полинома складываются по модулю 2 с порождающим полиномом, и в частное заносится единица. В дальнейшем полином, полученный в результате сложения информационного и порождающего полиномов, будем называть остатком информационного полинома. После сложения старший разряд остатка информационного полинома будет равен нулю, поэтому сдвинемся на один разряд вправо. Если и этот разряд равен нулю, то в частное заносится нуль и мы двигаемся дальше, в противном случае снова складываем по модулю 2 группу разрядов длиной r+1 остатка информационного полинома и порождающий полином. Последнее действие повторяется до тех пор, пока степень остатка не станет меньше степени порождающего полинома. Полученный остаток и будет контрольным числом.

Для иллюстрации теоретических рассуждений и алгоритма деления рассмотрим небольшой пример. Предположим, что контролируются данные вида 11010011. В качестве порождающего полинома выберем число 10011 (r = 4), следовательно, контрольный код будет получен делением 110100110000 на 10011.



Здесь специально приведен пример вычисления контрольного числа из рис. 3, поскольку оригинал содержит ошибку в частном. Из теории следует, чем больше величина r, тем больше обнаруживающая способность контрольного кода. При аппаратной реализации метода подсчета R(x) величина r в общем случае ограничена только допустимыми объемом и стоимостью аппаратуры, при программной же реализации алгоритма величину r удобно принять равной разрядности машинного слова (для персональных компьютеров - 16). Основная сложность программной реализации заключается в том, что для получения 16-разрядного остатка информационный полином необходимо делить на 17-разрядный порождающий полином. Это ограничение можно преодолеть таким образом. Обратим внимание, что при сложении по модулю 2 как старший разряд остатка информационного полинома, так и старший разряд порождающего полинома всегда равны единице и, следовательно, известен результат их сложения - нуль. Поэтому складывать с остатком уже можно только младшие 16 разрядов порождающего полинома. Поскольку нас интересует только контрольное число (остаток от деления), частное не вычисляется.

Ниже приведен фрагмент программы для получения циклического контрольного кода. Порождающий полином длиной data_length слов находится по адресу data_buffer. Считается, что data_length+1-слово в буфере уже обнулено. Распределение регистров для организации деления таково. Регистр DX содержит младшие 16 разрядов порождающего полинома (по умолчанию старший, 17-й, разряд равен единице). При сложении старший разряд остатка информационного полинома находится во флаге переноса, а следующие 16 разрядов - в регистре BX. Регистр AX задействован как временный буфер для "подпитки" регистра BX очередным разрядом информационного полинома.

Конструктивно фрагмент состоит из двух вложенных циклов. Внешний цикл служит для загрузки в регистр AX очередной 16-разрядной порции информационного полинома, внутренний - для сдвига 32-разрядной пары BX-AX через флаг переноса и (при наличии единицы во флаге переноса) сложения с порождающим полиномом, а в конечном итоге - для получения в регистре BX контрольного числа.

mov cx,data length+1
mov dx,parent code
mov si,OFFSET data buffer
lods
mov bx,ax x
main_loop:
lods
push cx
mov cx,16
internal_loop:
shl ax,l
rcl bx,l
jnc next_bit
xor bx,dx
next_bit:
loop internal_loop
pop cx
loop main_loop


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