Циклический код обнаружения ошибок crc

Тип хеш-функции, используемой для обнаружения ошибок при хранении или передаче данных

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

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

CRC была изобретена У. Уэсли Петерсоном в 1961 году; 32-битная функция CRC, используемая в Ethernet и многих других стандартах, является работой нескольких исследователей и была опубликована в 1975 году.

Введение

CRC основаны на теории циклических кодов с исправлением ошибок. Использование систематических циклических кодов, которые кодируют сообщения путем добавления контрольного значения фиксированной длины, с целью обнаружения ошибок в сетях связи, было впервые предложено W. Уэсли Петерсон в 1961 году. Циклические коды не только просты в реализации, но и имеют то преимущество, что они особенно хорошо подходят для обнаружения пакетных ошибок : непрерывных последовательностей ошибочных символов данных в сообщениях. Это важно, потому что пакетные ошибки являются общими ошибками передачи во многих каналах связи, включая магнитные и оптические запоминающие устройства. Обычно n-битный CRC, применяемый к блоку данных произвольной длины, обнаруживает любой одиночный пакет ошибок не длиннее n битов, а доля всех более длинных пакетов ошибок, которые он обнаружит, составляет (1-2).

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

На практике все обычно используемые CRC используют поле Галуа из двух элементов, GF (2). Эти два элемента обычно называются 0 и 1, что удобно для компьютерной архитектуры.

CRC называется n-битным CRC, если его контрольное значение имеет длину n бит. Для заданного n возможно несколько CRC, каждый с различным полиномом. Такой многочлен имеет наивысшую степень n, что означает, что он имеет n + 1 член. Другими словами, полином имеет длину n + 1; для его кодирования требуется n + 1 бит. Обратите внимание, что в большинстве спецификаций полиномов либо отбрасываются MSB, либо LSB, поскольку они всегда равны 1. CRC и связанный с ним многочлен обычно имеют имя в форме CRC-n-XXX, как в таблица ниже.

Простейшая система обнаружения ошибок, бит четности, на самом деле является 1-битным CRC: он использует полином генератора x + 1 (два члена) и имеет название CRC. -1.

Приложение

Устройство с поддержкой CRC вычисляет короткую двоичную последовательность фиксированной длины, известную как контрольное значение или CRC, для каждого блока данных, который должен быть отправлен или сохранен, и добавляет ее в данные, образующие кодовое слово.

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

Если значения CRC не совпадают, то блок содержит ошибку данных.

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

Целостность данных

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

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

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

В-третьих, CRC – это линейная функция с свойство, которое

в результате, даже если CRC зашифрован с помощью потокового шифра, который использует XOR в качестве операции объединения (или режим из блочного шифра, который эффективно превращает его в потоковый шифр, такой как OFB или CFB), и сообщением, и связанным CRC можно манипулировать без знания ключа шифрования; это был один из хорошо известных недостатков конструкции протокола Wired Equivalent Privacy (WEP).

Вычисление

Чтобы вычислить n-битный двоичный CRC, выведите строку биты, представляющие ввод в строке, и размещают (n + 1) -битовый шаблон, представляющий делитель CRC (называемый «полиномом ») под левым концом строки.

В этом примере мы закодируем 14 бит сообщения с помощью 3-битной CRC с полиномом x + x + 1. Полином записывается в двоичном формате как коэффициенты; многочлен 3-й степени имеет 4 коэффициента (1x + 0x + 1x + 1). В этом случае коэффициенты равны 1, 0, 1 и 1. Результат вычисления составляет 3 бита.

Начните с сообщения, которое нужно закодировать:

Сначала оно дополняется нулями, соответствующими длине битов n CRC. Это делается для того, чтобы результирующее кодовое слово имело систематическую форму. Вот первое вычисление для вычисления 3-битного CRC:

11010011101100 000 <— input right padded by 3 bits 1011 <— divisor (4 bits) = x³ + x + 1 —————— 01100011101100 000 <— result

Алгоритм воздействует на биты непосредственно над делителем на каждом шаге. Результатом этой итерации является побитовое исключающее ИЛИ полиномиального делителя с битами над ним. Биты не выше делителя просто копируются прямо ниже для этого шага. Затем делитель сдвигается вправо, чтобы выровняться с наивысшим оставшимся 1 битом на входе, и процесс повторяется до тех пор, пока делитель не достигнет правого конца входной строки. Вот полный расчет:

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

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

Следующий код Python описывает функцию, которая будет возвращать начальный остаток CRC для выбранного ввода и полинома с 1 или 0 в качестве начального заполнения. Обратите внимание, что этот код работает со строковыми входными данными, а не с необработанными числами:

Алгоритм CRC-32

Это практический алгоритм для CRC -32 вариант CRC. CRCTable – это мемоизация вычисления, которое должно быть повторено для каждого байта сообщения (Вычисление циклических проверок избыточности § Многобитовое вычисление ).

Математика

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

Разработка многочленов

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

Самым важным атрибутом полинома является его длина (наибольшая степень (экспонента) +1 любого члена в полиноме) из-за его прямого влияния на длину вычисляемого контрольного значения.

Наиболее часто используемые полиномиальные длины:

• 9 бит (CRC-8)
• 17 бит (CRC-16)
• 33 бита (CRC-32)
• 65 бит (CRC-64)

CRC называется n-битным CRC, если его контрольное значение равно n битам. Для заданного n возможно несколько CRC, каждый с различным полиномом. Такой многочлен имеет наивысшую степень n, а значит, n + 1 член (длина многочлена n + 1). Остаток имеет длину n. CRC имеет имя в форме CRC-n-XXX.

Схема полинома CRC зависит от максимальной общей длины блока, который должен быть защищен (данные + биты CRC), желаемых функций защиты от ошибок и типа ресурсов для реализации CRC, а также желаемая производительность. Распространенное заблуждение состоит в том, что «лучшие» полиномы CRC получаются либо из неприводимых полиномов, либо из неприводимых полиномов, умноженных на множитель 1 + x, что добавляет к коду возможность обнаруживать все ошибки, влияющие на нечетное количество битов.. В действительности все описанные выше факторы должны входить в выбор полинома и могут привести к приводимому полиному. Однако выбор приводимого полинома приведет к определенной доле пропущенных ошибок из-за того, что кольцо частных имеет делителей нуля.

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

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

• Иногда реализация добавляет фиксированный битовый шаблон к проверяемому битовому потоку. Это полезно, когда ошибки синхронизации могут вставлять 0-биты перед сообщением, изменение, которое в противном случае оставило бы значение проверки неизменным.
• Обычно, но не всегда, реализация добавляет n 0-битов (n – размер CRC) в поток битов, который должен быть проверен до того, как произойдет полиномиальное деление. Такое добавление явно продемонстрировано в статье Вычисление CRC. Это удобно в том, что остаток от исходного потока битов с добавленным контрольным значением равен нулю, поэтому CRC можно проверить, просто выполнив полиномиальное деление полученного потока битов и сравнив остаток с нулем. Благодаря ассоциативным и коммутативным свойствам операции исключающее ИЛИ практические реализации, управляемые таблицами, могут получить результат, численно эквивалентный добавлению нулей без явного добавления нулей, с помощью эквивалентного, более быстрого алгоритма, который объединяет поток битов сообщения с потоком сдвигается из регистра CRC.
• Иногда реализация исключающее ИЛИ использует фиксированный битовый шаблон в оставшуюся часть полиномиального деления.
• Порядок битов: Некоторые схемы рассматривают младший бит каждого байта как «первый», который затем во время полиномиального деления означает «крайний левый», что противоречит нашему обычному пониманию «младшего разряда». Это соглашение имеет смысл, когда передачи последовательного порта проходят аппаратную проверку CRC, потому что некоторые широко распространенные соглашения о передаче последовательного порта сначала передают байты младшего бита.
• Порядок байтов : С многобайтовыми CRC может возникнуть путаница в отношении того, является ли байт, переданный первым (или сохраненный в байте с наименьшим адресом памяти), младшим (LSB) или старшим (MSB) байтом. Например, некоторые 16-битные схемы CRC меняют местами байты контрольного значения.
• Пропуск старшего бита полинома делителя: поскольку старший бит всегда равен 1, и поскольку n- бит CRC должен определяться (n + 1) -битным делителем, который переполняет n-битный регистр, некоторые авторы предполагают, что нет необходимости упоминать старший бит делителя

В таблице ниже они показаны как:

Обфускация

CRC в проприетарных протоколах могут быть запутаны с использованием нетривиального начального значения и окончательного XOR, но эти методы не добавляют криптографической стойкости к алгоритму и могут быть реконструированным с использованием простых методов.

Стандарты и обычное использование

В технические стандарты включены многочисленные разновидности циклических проверок избыточности. Ни в коем случае не один алгоритм или по одной каждой степени подходит для всех целей; Купман и Чакраварти рекомендуют выбирать полином в соответствии с требованиями приложения и ожидаемым распределением длин сообщений. Количество используемых различных CRC сбивает разработчиков с толку, и авторы стремились исправить эту ситуацию. Сообщается о трех полиномах для CRC-12, о двадцати двух конфликтующих определениях CRC-16 и о семи для CRC-32.

Обычно применяемые полиномы не являются наиболее эффективными из возможных. С 1993 года Купман, Кастаньоли и другие исследовали пространство многочленов размером от 3 до 64 бит и нашли примеры, которые имеют гораздо лучшую производительность (с точки зрения расстояния Хэмминга для данного размера сообщения), чем многочлены. более ранних протоколов и публикация лучших из них с целью улучшения способности обнаружения ошибок будущих стандартов. В частности, в iSCSI и SCTP был принят один из результатов этого исследования – полином CRC-32C (Кастаньоли).

Разработка 32-битного многочлена, наиболее часто используемого органами стандартизации, CRC-32-IEEE, была результатом совместных усилий Римской лаборатории и электронных систем ВВС США. Подразделение Джозефа Хаммонда, Джеймса Брауна и Шиан-Шианг Лю из Технологического института Джорджии и Кеннета Брайера из Mitre Corporation. Самые ранние известные появления 32-битного полинома были в их публикациях 1975 года: Технический отчет 2956 Брайера для Mitre, опубликованный в январе и выпущенный для публичного распространения через DTIC в августе, и отчет Хаммонда, Брауна и Лю. для Римской лаборатории, опубликовано в мае. Оба отчета содержали материалы другой команды. В декабре 1975 года Брайер и Хаммонд представили свою работу в докладе на Национальной телекоммуникационной конференции IEEE: полином IEEE CRC-32 является порождающим полиномом кода Хэмминга и был выбран за его способность обнаруживать ошибки. Даже в этом случае полином CRC-32C Кастаньоли, используемый в iSCSI или SCTP, соответствует своей производительности для сообщений от 58 бит до 131 кбит и превосходит его в нескольких диапазонах размеров, включая два наиболее распространенных размера интернет-пакетов. Стандарт ITU-T G.hn также использует CRC-32C для обнаружения ошибок в полезной нагрузке (хотя он использует CRC-16-CCITT для заголовков PHY ).

Вычисление CRC32C реализовано аппаратно как операция (CRC32) набора инструкций SSE4.2, впервые представленная в процессорах Intel Микроархитектура Nehalem. Операции CRC32C также определены в AArch64.

Полиномиальные представления циклических проверок избыточности

Эта статья — о коде. О методе мозгового штурма см. CRC-карта.

[править] Алгоритм CRC

Алгоритм CRC базируется на свойствах деления с остатком двоичных многочленов, то есть многочленов над конечным полем GF(2). Значение CRC является по сути остатком от деления многочлена, соответствующего входным данным, на некий фиксированный порождающий многочлен.

Каждой конечной последовательности битов

взаимооднозначно сопоставляется двоичный многочлен

, последовательность коэффициентов которого представляет собой исходную последовательность. Например, последовательность битов 1011010 соответствует многочлену:

Количество различных многочленов степени меньшей N равно

, что совпадает с числом всех двоичных последовательностей длины N.

Значение CRC с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):

— многочлен, представляющий значение CRC.

— многочлен, коэффициенты которого представляют входные данные.

— порождающий многочлен.

— степень порождающего многочлена.

нулевых битов к входной последовательности, что улучшает качество хеширования для коротких входных последовательностей.

При делении с остатком степень многочлена-остатка строго меньше степени многочлена-делителя, то есть при делении на многочлен G(x) степени N можно получить 2N различных остатков от деления. При «правильном» выборе порождающего многочлена G(x), остатки от деления на него будут обладать нужными свойствами хеширования — хорошей перемешиваемостью и быстрым алгоритмом вычисления. Второе обеспечивается тем, что степень порождающего многочлена обычно пропорциональна длине байта или машинного слова (например 8, 16 или 32).

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

Тогда контрольная сумма будет равна операции XOR тех столбцов, над которыми в верхней строке расположена 1. В этом случае, 010 xor 101 xor 011 xor 111 xor 110 = 101 (CRC).

Ниже представлены реализации получения некоторых CRC для многочленов степени 8 (CRC-8), 16 (CRC-16) и 32 (CRC-32).

[править] Формализованный алгоритм расчёта CRC16

Для получения контрольной суммы, необходимо сгенерировать полином. Основное требование к полиному: его степень должна быть равна длине контрольной суммы в битах. При этом старший бит полинома обязательно должен быть равен «1».

Из файла берется первое слово. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции XOR. Соответственно если старший бит в слове «0», то после сдвига операция XOR не выполняется. После сдвига (умножения) теряется старый старший бит, а младший бит освобождается (обнуляется). На место младшего бита загружается очередной бит из файла. Операция повторяется до тех пор, пока не загрузится последний бит файла.

После прохождения всего файла, в слове остается остаток, который и является контрольной суммой.

[править] CRC-4

Пример программы, генерирующей массив, предназначенный для табличного способа вычисления CRC4 на языке C#

/*
Name : CRC-4
Poly : 0x13 x4 + x + 1
rtbOutput : объект класса RichTextBox
*/

CRC_Table

Form1 Form

Polinom 0x13

Form1

InitializeComponent

btnGenerate_Click sender, EventArgs e

rtbOutput

local
i i i

rtbOutput local
rtbOutput CRCTableCelli
rtbOutput local 0xf

local
local 0xf

rtbOutput

CRCTableCell value

r

r value 0xFF00
shifted_Polinom Polinom // 3 сдвига для дополнения полинома до размера 1 байта, 8 сдв. для заполнения нулями

j j j

r 0x8000

r shifted_Polinom
r r

r r

r r
, r

Итоговый массив для табличного (быстрого) расчёта CRC4 (результат работы вышеприведенного кода)

[править] CRC-8

Пример программы расчёта CRC8 на языке Си

Пример программы табличного (быстрого) расчёта CRC8 на языке Си

/*
Name : CRC-8
Poly : 0x31 x^8 + x^5 + x^4 + 1
Init : 0xFF
Revert: false
XorOut: 0x00
Check : 0xF7 (“123456789”)
MaxLen: 15 байт (127 бит) – обнаружение
одинарных, двойных, тройных и всех нечетных ошибок
*/

[править] CRC-16

CRC-CCITT (отличается от классического CRC-16, так как использует другой полином и порядок данных).

Оптимизированный расчёт CRC-16 CCITT на языке Си, полином 0x8408

/*
Name : CRC-16 CCITT
Poly : 0x8408
Init : 0xFFFF
Revert: false
XorOut: 0x0000
Check : 0x6F91 (“123456789”)
MaxLen: 4095 байт (32767 бит) – обнаружение
одинарных, двойных, тройных и всех нечетных ошибок
*/
crc_ccitt_update crc data
t
data crc
data data
t data crc
t data
t data
t

Пример программы расчёта CRC-16 CCITT на языке Си

Пример программы табличного (быстрого) расчёта CRC-16 CCITT на языке Си

/*
Name : CRC-16 CCITT
Poly : 0x1021 x^16 + x^12 + x^5 + 1
Init : 0xFFFF
Revert: false
XorOut: 0x0000
Check : 0x29B1 (“123456789”)
MaxLen: 4095 байт (32767 бит) – обнаружение
одинарных, двойных, тройных и всех нечетных ошибок
*/

Пример программы табличного (быстрого) расчёта стандартного (ARC) CRC-16 на языке Си

/*
Name : CRC-16
Poly : 0x8005 x^16 + x^15 + x^2 + 1
Init : 0xFFFF
Revert: true
XorOut: 0x0000
Check : 0x4B37 (“123456789”)
MaxLen: 4095 байт (32767 бит) – обнаружение
одинарных, двойных, тройных и всех нечетных ошибок
*/

Пример программы расчёта CRC-16 CCITT на языке PHP

/*
Name : CRC-16 CCITT
Poly (default) : 0x1021 x^16 + x^12 + x^5 + 1
Init (default) : 0xFFFF
XorOut (default): 0x0000
Revert : false
Check : 0x29B1 (“123456789”)
MaxLen : 4095 байт (32767 бит) – обнаружение
одинарных, двойных, тройных и всех нечетных ошибок
*/
crc16

//– устанавливаем значения по умолчанию у незаданных параметров

//– инициализируем переменные

^

? ^

^

Пример программы табличного (быстрого) расчёта стандартного (ARC) CRC-16 на языке AVR assembler

Name CRC
Poly x^ x^ x^
Init
Revert
XorOut
Check

[править] CRC-32

Алгоритм CRC32 основан на примитивном полиноме 0xEDB88320 (зеркальное отображение полинома 0x04C11DB7).

Пример программы расчёта CRC-32 на языке Си

/*
Name : CRC-32
Poly : 0x04C11DB7 x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11
+ x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
Init : 0xFFFFFFFF
Revert: true
XorOut: 0xFFFFFFFF
Check : 0xCBF43926 (“123456789”)
MaxLen: 268 435 455 байт (2 147 483 647 бит) – обнаружение
одинарных, двойных, пакетных и всех нечетных ошибок
*/
Crc32 buf len

crc_table
crc i j

i i i

crc i
j j j
crc crc crc 0xEDB88320UL crc

crc_tablei crc

crc 0xFFFFFFFFUL

len
crc crc_tablecrc buf crc

crc 0xFFFFFFFFUL

Пример программы табличного (быстрого) расчёта CRC-32 на языке Си

[править] Наиболее используемые и стандартизованные CRC

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

в настоящее время вытеснены криптографическими хеш-функциями.

[править] Классификация реализаций алгоритмов CRC

На самом деле достаточно указать ряд параметров, точно описывающих конкретный частный алгоритм CRC (если это на самом деле CRC).

В модели алгоритма Ross N. Williams. CRC Rocksoft (1993). Архивировано из первоисточника 15 мая 2012., получившей некоторое хождение, используются следующие параметры:

Name: Это имя, присвоенное данному алгоритму.

Width: Степень алгоритма, выраженная в битах. Она всегда на единицу меньше длины полинома, но равна его степени.

Poly: Собственно полином. Это битовая величина, которая для удобства может быть представлена шестнадцатеричным числом. Старший бит при этом опускается (он всегда 1). Например, если используется полином 10110, то он обозначается числом «06h». Важной особенностью данного параметра является то, что он всегда представляет собой необращенный полином, младшая часть этого параметра во время вычислений всегда является наименее значащими битами делителя.

Init: Этот параметр определяет исходное содержимое регистра на момент запуска вычислений. Данный параметр указывается шестнадцатеричным числом.

RefIn(Revert): Логический параметр. Если он имеет значение False, байты сообщения обрабатываются, начиная с 7 бита, который считается наиболее значащим, а наименее значащим считается бит 0 (сдвиг налево). Если параметр имеет значение True («Истина»), то каждый байт перед обработкой обращается (сдвиг направо).

RefOut: Логический параметр. Если он имеет значение False, то конечное содержимое регистра сразу передается на стадию XorOut, в противном случае, когда параметр имеет значение True, содержимое регистра обращается перед передачей на следующую стадию вычислений. в приведённых алгоритмах, по-видимому, False).

XorOut: W битное значение, обозначаемое шестнадцатеричным числом. Оно комбинируется с конечным содержимым регистра (после стадии RefOut), прежде чем будет получено окончательное значение контрольной суммы.

После определения всех этих параметров, можно точно описать особенности применённого CRC алгоритма.

Примеры спецификаций некоторых алгоритмов CRC:

Циклический избыточный код CRC-4

При передаче потока Е1 по сети связи, включающей в себя ряд систем передачи плезиохронной и синхронной цифровых иерархий, прозрачных для его прохождения, возникает необходимость проверки качественных показателей первичного цифрового канала на всём его протяжении.

Из 256 бит, образующих стандартный цикл 2-мегабитного сигнала, сигналы с 1-ого по 31-й КИ (канальный интервал) являются случайными. Поэтому из всего группового сигнала можно идентифицировать только 7 бит циклового синхросигнала, что позволяет обнаруживать битовые ошибки без остановки связи, однако указанные 7 бит составляют только 1,4 % от общего объёма передаваемой информации. Проблема обеспечения контроля ошибок в остальных 31 каналах оптимально решается путём использования метода контроля с использованием избыточности циклического сигнала CRC-4.

CRC-4 был определён в 1980-х годах рекомендацией МСЭ-Т, но широкое распространение получил только в последнее время вследствие трудностей схемотехнической реализации, которую можно осуществить только методами микросхемотехники.

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

16 следующих друг за другом циклов образуют сверхцикл, который, в свою очередь, делится на два субсверхцикла (1-й и 2-й) по 8 циклов каждый. Таким образом, временной интервал CRC-4 равен 16 × 125 мкс = 2 мс.

Для формирования сигнала CRC-4 сумма бинарных символов каждого субсверхцикла делится на полином четвертой степени (х4 + х + 1). Результат деления, представляющий собой 4 бинарных символа, вводится в групповой сигнал в позициях от С1 до С4. Приёмная сторона использует аналогичный метод для того, чтобы затем сравнить кодовое слово, поступающее от передатчика, с результатом, полученным на приёмном конце. Если указанные слова различны, значит субсверхцикл, равный 2048 битам, был передан с ошибками.

Преимуществом этого метода является то, что с его помощью можно контролировать цифровой поток без остановки связи и независимо от его содержания.

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

Сверхцикловый сигнал CRC-4 служит для того, чтобы можно было обеспечить синхронизацию по битам от С1 до С4. Биты Е (Е1 и Е2 для 1-го и 2-го субсверхциклов) инвертируются для сохранения структуры сверхцикла в моменты обнаружения ошибок. Таким образом, приёмная сторона может информировать передающую сторону об обнаружении ошибок передачи. После того, как установится цикловая синхронизация, сигналы CRC-4 будут передаваться непрерывно. Потеря синхронизации CRC-4 происходит тогда, когда более чем 914 сигналов CRC-4, передаваемые в течение 1 секунды, не будут соответствовать нормированным.

Аналогично организуется и проверка цифровых трактов других ступеней иерархии. Меняется только величина блоков и степень полинома: 6-я степень для CRC-6, используемого для контроля ИКМ-120, 8-я — для CRC-8, используемого для контроля ИКМ-480.

[править] Литература

• Элементарное руководство по CRC алгоритмам обнаружения ошибок
• CRC, и как его восстановить
• Восстановление CRC
• CRC-калькулятор
• Генератор CRC-функций на языках VHDL и Verilog
• Ross N. Williams/Anarchriz. Всё о CRC32 // Ross N. Williams. Элементарное руководство по CRC алгоритмам обнаружения ошибок
• Ross N. Williams. A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS

Эта статья — о коде. О методе мозгового штурма см. CRC-карта.

[править] Введение

Первые попытки создания кодов с избыточной информацией начались задолго до появление современных ПК. К примеру, ещё в шестидесятых годах прошлого века Ридом и Соломоном была разработана эффективная методика кодирования — Код Рида-Соломона. Использование её в те времена не представлялось возможным, так как произвести операцию декодирования за разумное время первыми алгоритмами не удавалось. Точку в этом вопросе поставила фундаментальная работа Берлекампа, опубликованная в 1968 году. Эта методика, на практическое применение которой указал через год Мэсси, и по сей день используется в цифровых устройствах, обеспечивающих прием RS-кодированных данных. Более того: данная система позволяет не только определять позиции, но и исправлять неверные кодовые символы (чаще всего октеты).

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

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

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

[править] Математическое описание

взаимно однозначно сопоставляется двоичный полином

Значение контрольной суммы в алгоритме с порождающим многочленом G(x) степени N определяется как битовая последовательность длины N, представляющая многочлен R(x), получившийся в остатке при делении многочлена P(x), представляющего входной поток бит, на многочлен G(x):

При делении с остатком исходного многочлена на порождающий полином G(x) степени N можно получить 2N различных остатков от деления. G(x) всегда является неприводимым многочленом. Обычно его подбирают в соответствии с требованиями к хэш-функции в контексте каждого конкретного применения.

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