Алгоритъм за директно изчисляване на CRC Програмиране, уроци и примери
Дори малко практика струва много теория.
Закон на Букър (Приложна мурфология)
След всички тези разсъждения сме готови да възприемем смислено общата схема на реален алгоритъм за изчисляване на CRC - алгоритъм за директно (битово) изчисляване на CRC. В този случай е удобно да се разгледа алгоритъмът CRC от гледна точка на двете страни, участващи в процеса: източникът - обектът, който формира съобщението за предаване, и получателят - обектът, който получава съобщението и проверява неговата цялост. Действията с източника са както следва.
- 1. Изберете полином P, в резултат степента му N става автоматично известна.
2. Добавете N нула бита към оригиналната двоична последователност. Това добавяне се прави, за да се гарантира, че всички битове от оригиналната последователност се обработват.
3. Извършете разделяне на оригиналния низ S, допълнен с N нули, от полинома P съгласно правилата на CRC аритметиката. Запомнете остатъка, който ще бъде CRC.
4. Генерирайте окончателното съобщение, което ще се състои от две части: самото съобщение и добавената към края му стойност на CRC.
Например изчислението от този CRC алгоритъм за оригиналната последователност 1101001110010110100 (вж. Фиг. 9.4) и самата окончателна последователност от страна на източника ще изглеждат, както е показано на фиг. 9.5.
Фигурата показва, че в началото на изчислението оригиналната последователност 1101001110010110100 е подплатена с нули в размер, равен на степента на полинома (P = 1011 - степента на полинома N = 3): 1101001110010110100 + 000. Когато извършвате разделяне на CRC, тези допълнителни битове гарантират, че всички битове в оригиналната последователност ще участват в процеса на генериране на стойността на CRC. Получената последователност е равна на оригиналната последователност, подплатена със стойността на CRC: 1101001110010110100 + 011. Имайте предвид, че дължината на стойността на CRC, добавена към оригиналната последователност, трябва да бъде равна на степента на полинома, дори ако CRC, както в нашия случай, има водещи нули. Това е много важен момент, разбирането на който е ключът към разбирането на същността на процесите, протичащи от страната на получателя при получаване и определяне целостта на оригиналното съобщение. Действията на алгоритъма за приемника са прости - разделете получената последователност на полином. Освен това, за да се извърши разделяне, няма нужда да се допълва първоначалната последователност с нули, особено след като на практика спазването на това условие е изключително неудобно. Приемникът просто извършва CRC разделението на получения оригинален низ (подплатен в края