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



         

CRC-арифметика - часть 5


  • порождающий полипом 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) к выявлению ошибок, специфичных для передачи данных по каналами связи. Это такие ошибки, как ошибки в одном, двух, нечетном количестве битов, а также ошибки блока битов. Выше мы отмечали, что более простые методы обнаружения ошибок передачи не способны обнаружить с достаточной степенью вероятности большинство таких типов ошибок.



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