Илюстриран урок за задачи и примери Асемблер ›CRC изчисление› Директен алгоритъм

Алгоритъм за директно изчисляване на 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.