Лекция 7. Коды, обнаруживающие ошибки. 
CRC-коды

CRC (Cyclic Redundancy Code — циклический избыточный код) — последовательность бит, полученная по определенному алгоритму на основании другой (исходной) битовой последовательности. Главная особенность (и практическая значимость) значения CRC состоит в том, что оно однозначно идентифицирует исходную битовую последовательность.

Коды CRC применяются, например, в программах-архиваторах. Работа программы-архиватора в общем случае заключается в следующем: архиватор упаковывает файлы в соответствии с некоторым алгоритмом архивации, вычисляя для каждого упаковываемого файла значение CRC. После этого заархивированные файлы могут множество раз копироваться, пересылаться по сети и т. д. В процессе передачи файл может столкнуться с различными неприятными воздействиями внешней среды, например, с неисправным накопителем, искажением внутреннего содержимого файла во время передачи по сети и т. п. Эти изменения не обязательно должны быть глобальными, они могут касаться всего одного бита. Когда приходит время, пользователь распаковывает архив, при этом архиватор в первую очередь проверяет целостность файлов в нем. Для этого архиватор по содержимому файла опять вычисляет его CRC и сравнивает полученное значение с тем значением CRC, которое было вычислено при упаковке файла. Если они равны, то считается, что целостность файла не была нарушена, и он распаковывается, иначе, если новое и старое значения CRC не совпадают, считается, что архивный файл поврежден, и процесс его распаковки завершается.

Основная идея вычисления CRC заключается в следующем. Исходная последовательность байтов, которой могут быть и огромный файл, и текст размером несколько слов и даже символов, представляется единой последовательностью битов. Эта последовательность делится (по определенным правилам) на некоторое фиксированное двоичное число. Интерес представляет остаток от этого деления, который и является значением CRC. Все, что теперь требуется, — это некоторым образом запомнить его и передать вместе с исходной последовательностью. Приемник данной информации всегда может таким же образом выполнить деление и сравнить его остаток с исходным значением CRC. Если они равны, то считается, что исходное сообщение не повреждено.

CRC-арифметика Расчеты CRC ведутся в двоичной системе счисления. При проведении CRC-вычислений используется специальная CRC-арифметика, которая, по сути, является полиномиальной арифметикой по модулю 2. Полиномиальная арифметика по модулю 2 — это один из видов арифметик, используемых для решения задач в определенной предметной области, который отличается от привычной двоичной арифметики с циклическим переносом отсутствием переносов и вычислением всех коэффициентов по модулю 2.

По определению, полином — линейная комбинация (сумма) произведений целых степеней заданного набора переменных с постоянными коэффициентами. Частный случай — полином, содержащий одну переменную:

u (x) = u_nxⁿ + u_n-1x^n-1 + … + u₁x¹ + u₀x⁰.

Здесь u_i — элементы некоторой алгебраической системы S, называемые коэффициентами; x — переменная полинома, которую можно рассматривать как формальный символ без определенного значения. Алгебраическая система S обычно представляет собой множество целых или рациональных чисел в диапазоне 0… m-1 со сложением, вычитанием и умножением, выполняемыми по модулю m. Для нашего рассмотрения особенно важна полиномиальная арифметика по модулю 2, в которой каждый коэффициент полинома равен одному из двух значений — 0 или 1. Например, шестнадцатеричное значение E3₁₆ может быть представлено следующим полиномом:

12⁷ + 12⁶ + 12⁵ + 02⁴ + 02³ + 02² + 12¹ + 12⁰.

Если вместо двойки использовать переменную x=2, то получим следующий двоичный полином:

1x⁷ + 1x⁶ + 1x⁵ + 0x⁴ + 0x³ + 0x² + 1x¹ + 1x⁰.

В этом полиноме, строго говоря, значение х не играет особой роли, так как данное двоичное число можно представить полиномом в другой системе счисления, например, шестнадцатеричной: Eх¹ + 3х⁰, где х=16. При этом заметим, что в том и другом случае цифры 0, 1, E, 3 — это просто цифры двоичной и шестнадцатеричной систем счисления.

Так как слагаемые двоичного полинома с нулевыми коэффициентами не дают никакого вклада в конечный результат, то их можно попросту отбросить, оставив только слагаемые, переменные которых имеют единичные коэффициенты:

1x⁷ + 1x⁶ + 1x⁵ + 0x⁴ + 0x³ + 0x² + 1x¹ + 1x⁰ =.

= 1x⁷ + 1x⁶ + 1x⁵ + 1x¹ + 1x⁰ =.

= x⁷ + x⁶ + x⁵ + x¹ + x⁰.

Над полиномами можно выполнять арифметические операции: сложение, вычитание, умножение и деление. Процессы выполнения этих операций для полиномиальной арифметики и обычной арифметики похожи. Главное отличие в том, что из-за отсутствия связи между коэффициентами полинома понятие переноса в полиномиальной арифметике отсутствует. Например, для умножения 7h (полином с коэффициентами 0111) на 5h (полином с коэффициентами 0101) выполняются действия:

(x² + x¹ + x⁰)(x² + x⁰) = x⁴ + x³ + x² + x² + x¹ + x⁰ = x⁴ + x³ + 2x² + x¹ + x⁰.

Для того, чтобы в ответе получить 35, необходимо взять x=2 и привести коэффициенты, не равные 1, к двоичным, сделав переносы соответствующих единиц в старшие разряды. В нашем случае коэффициент при x² равен 2₁₀=10₂, что для двоичной системы счисления эквивалентно выражению (1x³ + 0x²). Тогда полином принимает вид: x⁴ + 2x³ + 0x² + x¹ + x⁰, и при подстановке x=2 получаем 2⁴ + 22³ + 2¹ + 2⁰ = 2⁴ + 2⁴ + 2¹ + 2⁰ = 22⁴ + 2¹ + 2⁰ = 2⁵ + 2¹ + 2⁰ = 32+2+1 = 35. Последнее выражение соответствует двоичному полиному x⁵+x¹+x⁰.

Эти рассуждения призваны сформулировать тезис о том, что переносы, как и в обычной арифметике, можно выполнять в случае, когда известно основание системы счисления. То есть до тех пор, пока мы не знаем х, мы не можем производить и переносы. В приведенном выше примере, мы не знаем, что 2х² на самом деле является х³ до тех пор, пока не известно, что х=2. То есть в полиномиальной арифметике коэффициенты при разных степенях изолированы друг от друга и отношения между ними не определены. Из-за этого возникает первая странность полиномиальной арифметики — операции сложения и вычитания в ней абсолютно идентичны и вместо них можно смело оставлять одну. Например, сложение по правилам полиномиальной арифметики по модулю 2 (CRC-арифметики), будет выполнено так:

Из этого примера видны правила сложения двоичных разрядов в арифметике t с отсутствием переносов: 0+0=0; 0+1=1; 1+0=1; 1+1=0.

Операцию вычитания демонстрирует следующий пример:

Правила выполнения вычитания в арифметике с отсутствием переносов: 0−0=0; 0−1=1; 1−0=1; 1−1=0.

Сравнение примеров для сложения и вычитания полиномов по модулю 2, а также правил, по которым они выполняются, показывает то, что эти две операции CRC-арифметики идентичны, и по принципу формирования результата аналогичны логической операции XOR. Цель, которой достигают всеми этими условностями, — исключить из поля внимания все величины, лежащие за границей старшего разряда и затрагиваемые в результате переносов и заемов.

Умножение в арифметике с отсутствием переносов также выполняется с учетом особенностей CRC-сложения:

Видно, что в самом умножении особенностей нет, а вот сложение промежуточных результатов производится по правилам CRC-сложения.

Однако наибольший интерес для нас представляет операция деления, так как в основе любого алгоритма вычисления CRC лежит представление исходного сообщения в виде огромного двоичного числа, делении его на другое двоичное число и использовании остатка от этого деления в качестве значения CRC. Деление — самая сложная из операций CRC-арифметики.

Здесь необходимо ввести так называемое слабое понятие размерности: число X больше или равно числу Y, если оба числа имеют одинаковую размерность и значения их старших битов единичны. При этом соотношение остальных битов чисел X и Y для операции сравнения не имеет значения. Рассмотрим примеры операции деления, причем для лучшего понимания сделаем это в двух вариантах: вначале вспомним, как выполняется обычное деление (по правилам двоичной арифметики с циклическим переносом), а затем выполним собственно CRC-деление.

Очевидно, что результаты обычного и CRC-делений отличаются. При выполнении CRC-деления особое внимание следует обратить на порядок формирования промежуточных результатов в процессе деления. Снос двоичных разрядов из делимого продолжается до тех пор, пока размерности промежуточного битового значения и делителя не сравняются, а их старшие разряды не станут равными 1. После этого над двоичными разрядами выполняется побитовое CRC-вычитание. Соотношение разрядов не важно, главное — это одинаковая размерность и единичные старшие биты. В этом случае считается, что уменьшаемое больше вычитаемого, что влечет за собой формирование очередного бита частного равным единице и выполнение операции CRC-вычитания. Это как раз и есть проявление слабого понятия размерности. Корзина для мусора, показанная на втором рисунке, означает тот факт, что частное для процесса вычисления CRC-битовой последовательности не имеет никакого значения и в конце деления отбрасывается.

Обычное деление:

CRC-деление:

Реальные двоичные последовательности являются результатом сцепления огромного количества отдельных байтов (символов), образуя одно большое двоичное число, для представления которого нужно использовать двоичные полиномы огромных степеней. При этом каждый бит в подобной последовательности произвольной длины представляется в виде коэффициента полинома. Например, для представления 128-байтового блока необходим полином, состоящий из 128*8=1024 слагаемых, а для 1024-битного блока необходим полином уже с 1024*8=8192 слагаемыми. В терминах полиномиальной арифметики двоичное число, сформированное в результате подобной сцепки составляющих блока данных, называется полиномом данных и обозначается как D (x). В алгоритме вычисления CRC вводится еще несколько полиномов и соотношений между ними:

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

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

D (x) = Q (x) G (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)G (x)+R (x);
• — остаток от деления двух полиномов R (x) является двоичным числом, которое после вычитания из D (x) дает в результате еще один полином, делящийся без остатка на G (x); получающееся в результате этого деления частное Q (x) отбрасывается за ненадобностью, а полином-остаток R (x) называют CRC.

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

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

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

— х¹⁶+х¹²+х⁵+х⁰ — полином 1021₁₆, используемый в протоколе XMODEM и производных от него протоколах передачи данных. Он стандартизован в спецификации V.41 МККТТ «Кодонезависимая система контроля ошибок».

— х¹⁶+х¹⁵+х²+х⁰ — …

исходным значением CRC) на полином и анализирует остаток. Если остаток от этого деления нулевой, то исходная последовательность не была нарушена во время передачи. В обратном случае существует очень большая вероятность нарушения целостности исходной последовательности, и нужно принимать дополнительные меры по выяснению и исправлению ситуации.

Рассмотренный алгоритм вычисления значения CRC называется прямым и чаще всего реализуется аппаратно. Очевидный недостаток прямого метода — большое количество операций сдвига, операций XOR и операций условного перехода, которые выполняются для каждого бита исходного сообщения. Поэтому на практике используются иные способы расчета CRC, например, табличный способ. Подобные способы в рамках данного курса не рассматриваются.