Изчисляване на цикличния контролен код
Бележки от първо лице за ИТ, новини и технологично остаряване.
Блог → Изчисляване на цикличен код за проверка
Доста често програмистите - създателите на пакети за приложения са изправени пред задачата да контролират съдържанието както на самите програми, така и на данните. В този случай могат да се преследват най-различни цели: откриване на инфекция на програмата от вируси, защита на програмите от изпълнение под дебъгера (проверка на включването на точки за прекъсване в кода), защита на целостта на критичните данни и т.н. По правило такива задачи могат да бъдат решени с помощта на контролни кодове. Сред тях най-популярни са цикличните излишни кодове, които с достатъчно висока вероятност за откриване на грешки са относително лесни за изпълнение. Статията предлага на читателите един от алгоритмите за изчисляване на контролния номер на цикличния контролен код, както и вариант на неговата софтуерна реализация.
Теорията за изчисляване на контролната информация на цикличен контролен код се основава на концепцията за полином или, както се нарича още, полином. Полиномът е формално дадена степенна поредица, т.е. сумата от множеството изрази на степен за независими променливи. Например (фиг. 1):
Степента на многочлен е число r, равно на максималната степен на полином (в нашия случай r = 4). Обърнете внимание, че броят на членовете в многочлен винаги е с един повече от степента на полинома. Даденият пример не противоречи на това твърдение, тъй като формално той трябва да бъде написан по следния начин (фиг. 2):
В общия случай всеки блок информация в паметта на компютър (ако разглеждаме един бит като променлива x) може да се счита за полином. Ние го наричаме информационен полином и го обозначаваме с A (x). За да изчислите контролния код, имате нужда от още един полином - генератора. Означаваме този полином с G (x). В известен смисъл полиномът на генератора е ключът на цикличния код. За да получите контролния номер, който също може да бъде описан с помощта на полином, информационният полином трябва да бъде умножен по x по степен r (което съответства на изместване с r бита вляво) и след това разделен на полинома на генератора. Остатъкът от делението R (x) ще бъде контролното число (фиг. 3, където r е степента на генериращия полином):
Обикновено номерът за проверка се прилага, както следва. R (x), изчислен преди съхраняване на информационния полином в паметта, е примерен (референтен) и се съхранява отделно. За да се провери целостта на информационния полином, е необходимо отново да се изчисли R (x) и да се сравни с примерния. Несъответствието на числата означава, че в информационния полином са въведени изкривявания.