CRC16 - Описание на алгоритъма и пример за изчисление в C
CRC (Cyclic Redundancy Code - цикличен код на резервиране) - алгоритъмът за изчисляване на контролната сума за предаденото съобщение, базиран на полиномиална аритметика.
Основната идея на алгоритъма CRC е да представи съобщението като огромно двоично число, да го раздели на друго фиксирано двоично число и да използва остатъка от това разделение като контролна сума. След като получи съобщението, получателят трябва да извърши подобно действие и да сравни получения резултат с получената контролна сума. Съобщението се счита за валидно, това равенство е изпълнено.
Алгоритъмът CRC се основава на полиномиална аритметика, което означава, че съобщението, делителят и остатъкът могат да бъдат представени като полиноми с двоични коефициенти или като низ от битове, всеки от които е коефициент на полином.
Освен това трябва да се отбележи, че алгоритъмът на CRC използва полиномиален аритметичен модул 2. Това означава, че действията, извършени по време на изчисляването на CRC, са аритметични операции, без да се отчита носенето. Тоест добавянето и изваждането се извършват малко по бит, без да се отчита, така че тези две операции дават еквивалентен резултат. Операциите за събиране и изваждане в този случай са идентични с операцията XOR (изключително ИЛИ).
Делението се извършва по аналогия с обикновеното аритметично дълго деление, с тази разлика, че се използва операцията XOR, вместо да се извади делителят от дивидента. При софтуерната реализация на този алгоритъм дивидентът се измества вместо делителя. Преместването се извършва наляво, по един бит наведнъж. В този случай битът, който се изважда, се проверява: ако е равен на единица, се извършва XOR операцията на делителя (полином) с най-значимите цифри на дивидента (съобщението).
За да извършите изчислението на CRC, трябва да изберете делител - полином. Важна характеристика, която определя по-нататъшните изчисления, е степента на полинома или неговата ширина W (от английския Width - ширина). Обикновено се избира мощността на 16 или 32, тъй като те са кратни на битовата ширина на регистрите на съвременните процесори, което значително опростява изпълнението на CRC алгоритмите.
Степента на полинома е реалното положение на най-значимия бит. Позициите на битовете се броят, започвайки от нула.
След като сте избрали полином, трябва да добавите W нула бита в края на съобщението.
В тази статия, за да се изчисли CRC, ще бъде достатъчно да се използва полином със степен W = 16, който осигурява вероятността да не се открие грешка 1/2 16
= 15,3 · 10 -6. Въпреки факта, че грешките също се появяват с доста малка вероятност, делът на изкривените данни сред всички получени за съхранение от компютъра ще бъде много малък и няма да има значителен ефект върху по-нататъшната работа с данните, съхранявани в компютъра.