Сборник по задачам и примерам Assembler


       

предварительно особым образом выбранный полином,


  • порождающий полипом G(x) — предварительно особым образом выбранный полином, на который делится исходный полином сообщения;


  • полином-частное Q(x) — полином, получившийся в качестве частного от деления полиномов D(x)/G(x);


  • полином-остаток R(x) — полином, получившийся в качестве остатка от деления полиномов D(x)/G(x).


  • Между перечисленными полиномами существуют следующие отношения:

    D(x)=Q(x)xG(x)+R(x), Q(x)=(D(x)-R(x))/G(x).

    Эти соотношения приводят к следующим основополагающим для дальнейшего рассмотрения тезисам:

  • операция деления двух двоичных полиномов D(x)/G(x), где G(x)*0, дает в качестве результата полином-частное Q(x) и полином-остаток R(x), удовлетворяющие условиям: D(x)=Q(x)xG(x)+R(x);


  • остаток от деления двух полиномов R(x) является двоичным числом, которое после вычитания из D(x) дает в результате еще один полином, делящийся без остатка на G(x); получающееся в результате этого деления частное Q(x) отбрасывается за ненадобностью, а полином-остаток R(x) на-- зывают CRC (Cyclic Redundancy Code).


  • Из приведенного выше описания общей схемы вычисления CRC возникает ряд вопросов: что представляет собой этот магический делитель G(x), каков его размер? Выбор порождающего полинома G(x) — достаточно сложная задача. Перечислим некоторые важные свойства, которые должны учитываться при этом.

  • Число разрядов (количество членов) в полиноме-остатке R(x) непосредственно определяется длиной самого порождающего полинома G(x). Выбор G(x) длиной п гарантирует, что полином-остаток от деления R(x) будет иметь разрядность не более, чем п-1. Это следует из общего свойства операции деления, которое предполагает, что остаток от деления должен быть меньше делителя.


  • Порождающий полином G(x) должен быть полиномиально простым. Это означает его неделимость нацело на полиномы со значением в диапазоне от 2 до самого себя.


  • Способность порождающего полинома G(x) к выявлению ошибок, специфичных для передачи данных по каналами связи. Это такие ошибки, как ошибки в одном, двух, нечетном количестве битов, а также ошибки блока битов. Выше мы отмечали, что более простые методы обнаружения ошибок передачи не способны обнаружить с достаточной степенью вероятности большинство таких типов ошибок.



  • Содержание  Назад  Вперед