Циклический избыточный код (CRC) для обнаружения ошибок данных

Введение

Код обнаружения ошибок для выявления изменений данных

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

Введение

CRC основаны на теории циклических кодов исправления ошибок. Использование систематических циклических кодов, кодирующих сообщения путем добавления контрольной суммы фиксированной длины, для обнаружения ошибок в сетях связи, было впервые предложено У. Уэсли Петерсоном в 1961 году. Циклические коды не только просты в реализации, но и особенно хорошо подходят для обнаружения блочных ошибок – последовательных цепочек ошибочных символов данных в сообщениях. Это важно, поскольку блочные ошибки являются распространенными ошибками передачи во многих каналах связи, включая магнитные и оптические устройства хранения. Как правило, n-битный CRC, применяемый к блоку данных произвольной длины, обнаружит любую одиночную блочную ошибку длиной не более n бит, а доля всех более длинных блочных ошибок, которые он обнаружит, составляет приблизительно (1 − 2−n). Для спецификации кода CRC требуется определение так называемого образующего полинома. Этот полином становится делителем в алгоритме деления многочленов, где сообщение выступает в качестве делимого, а частное отбрасывается, и остаток становится результатом. Важно отметить, что коэффициенты полинома вычисляются в арифметике конечного поля, поэтому операция сложения всегда может выполняться параллельно побитово (переноса между разрядами нет). На практике все широко используемые CRC используют конечное поле из двух элементов, GF(2). Эти два элемента обычно обозначаются 0 и 1, что удобно согласуется с компьютерной архитектурой. CRC называется n-битным, если его контрольная сумма имеет длину n бит. Для заданного n возможно несколько CRC, каждый из которых использует свой полином. Такой полином имеет степень n, то есть содержит n + 1 членов. Иными словами, длина полинома равна n + 1; его кодирование требует n + 1 битов. Следует отметить, что в большинстве спецификаций полиномов опускается старший или младший бит, поскольку они всегда равны 1. CRC и соответствующий ему полином обычно имеют название вида CRC n XXX, как показано в таблице ниже. Самая простая система обнаружения ошибок, бит четности, фактически является 1-битным CRC: она использует образующий полином x + 1 (два члена) и называется CRC 1.

CRCs are based on the theory of cyclic error correcting codes. The use of systematic cyclic codes, which encode messages by adding a fixed length check value, for the purpose of error detection in communication networks, was first proposed by W. Wesley Peterson in 1961. Cyclic codes are not only simple to implement but have the benefit of being particularly well suited for the detection of burst errors: contiguous sequences of erroneous data symbols in messages. This is important because burst errors are common transmission errors in many communication channels, including magnetic and optical storage devices. Typically an n bit CRC applied to a data block of arbitrary length will detect any single error burst not longer than n bits, and the fraction of all longer error bursts that it will detect is approximately (1 − 2−n). Specification of a CRC code requires definition of a so called generator polynomial. This polynomial becomes the divisor in a polynomial long division, which takes the message as the dividend and in which the quotient is discarded and the remainder becomes the result. The important caveat is that the polynomial coefficients are calculated according to the arithmetic of a finite field, so the addition operation can always be performed bitwise parallel (there is no carry between digits). In practice, all commonly used CRCs employ the finite field of two elements, GF(2). The two elements are usually called 0 and 1, comfortably matching computer architecture. A CRC is called an n bit CRC when its check value is n bits long. For a given n, multiple CRCs are possible, each with a different polynomial. Such a polynomial has highest degree n, which means it has n + 1 terms. In other words, the polynomial has a length of n + 1; its encoding requires n + 1 bits. Note that most polynomial specifications either drop the MSB or LSB, since they are always 1. The CRC and associated polynomial typically have a name of the form CRC n XXX as in the table below. The simplest error detection system, the parity bit, is in fact a 1 bit CRC: it uses the generator polynomial x + 1 (two terms), and has the name CRC 1.

Применение

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

Математика

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

Описание многочленов

Выбор генераторного полинома является наиболее важной частью реализации алгоритма CRC. Полином должен быть выбран таким образом, чтобы максимизировать возможности обнаружения ошибок и минимизировать общую вероятность коллизий. Наиболее важной характеристикой полинома является его длина (степень наибольшего члена полинома + 1), поскольку она напрямую влияет на длину вычисляемого контрольного значения. Наиболее часто используемые длины полиномов – 9 бит (CRC 8), 17 бит (CRC 16), 33 бит (CRC 32) и 65 бит (CRC 64). Мы можем улучшить эту ситуацию. Если мы используем генераторный полином, где является примитивным полиномом степени , то максимальная общая длина блока равна , и код способен обнаруживать одиночные, двойные, тройные и любое нечетное количество ошибок. Затем можно выбрать полином, допускающий другие разложения на множители, чтобы сбалансировать максимальную общую длину блока с требуемой мощностью обнаружения ошибок. Коды БКХ представляют собой мощный класс таких полиномов, охватывающий вышеупомянутые примеры. Независимо от свойств приводимости генераторного полинома степени r, если он включает член "+1", код сможет обнаруживать шаблоны ошибок, локализованные в окне из r смежных битов. Эти шаблоны называются "скоплениями ошибок".

Спецификация

Концепция CRC как кода обнаружения ошибок усложняется, когда разработчик или комитет по стандартам использует её для создания практической системы. Вот некоторые из этих сложностей:

Иногда реализация добавляет фиксированный битовый шаблон к проверяемому битовому потоку. Это полезно, когда ошибки синхронизации могут вставлять нули в начало сообщения, изменение, которое иначе не повлияло бы на контрольную сумму. Обычно, но не всегда, реализация добавляет n нулей (где n – размер CRC) к проверяемому битовому потоку перед выполнением полиномиального деления. Такой способ добавления наглядно показан в статье "Вычисление CRC". Это удобно тем, что остаток от деления исходного битового потока с добавленной контрольной суммой равен нулю, поэтому CRC можно проверить, просто выполнив полиномиальное деление полученного битового потока и сравнив остаток с нулем. Благодаря ассоциативности и коммутативности операции исключающего ИЛИ, практические реализации, основанные на таблицах, могут получить результат, численно эквивалентный добавлению нулей, без фактического добавления нулей, используя эквивалентную схему.