Аппаратная реализация вычислителя 32-разрядной циклической контрольной суммы CRC

Аппаратная реализация вычислителя 32-разрядной циклической контрольной суммы CRC

Министерство образования Российской Федерации

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

им. Н.Э. БАУМАНА

Курсовая работа по дисциплине

«Электроника и схемотехника»

Москва

Содержание

Введение

. Операция деление по модулю 2

. Табличный метод вычисления CRC

3. Аппаратная реализация вычисления CRC в параллельном и последовательном коде

. Математическое описание алгоритма вычисления CRC

. Вычисление CRC. Параметры алгоритма

. Описание процедуры алгоритма вычисления CRC

. Стандартизованные полиномы

. Аппаратная реализация CRC32

Заключение

Введение

Для осуществления контроля правильности хранимой и передаваемой информации в цифровой электронике широко применяются так называемые контрольные суммы.

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

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

Существует ряд способов вычисления контрольной суммы, отличающихся по степени сложности и надежности обнаружения ошибок. Наиболее распространенным в настоящее время является - циклический метод контроля по избыточности или CRC (Cyclic Redundancy Check), при котором применяется циклическая контрольная сумма.

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

N - разрядное двоичное число делится по модулю два (операция XOR) на некоторое постоянное двоичное число (полином), которое специальным образом выбирается. Остаток этого деления и является вычисляемой контрольной суммой.

Этим методом определяются одиночные ошибки в информационном массиве с достоверностью 100%, остальные ошибки находятся с вероятностью, приблизительно равной 1-2^-n, где n - число разрядов контрольного кода (утверждение верно лишь при условии, что N намного больше n, что, впрочем, практически всегда выполняется). К примеру, при n = 8 такая вероятность составит 0.996, для n = 16 ее значение будет равно 0.999985, а для n = 32 она составит 0.9999999997672. Другими словами практически все ошибки будут обнаружены.

1.      Операция деление по модулю 2

Пусть массив (последовательность бит) имеет следующий вид: 101111001110 (для простоты примера берем небольшую разрядность). Число, на которое выполняется деление по модулю (носит название образующего полинома ) для примера будет 10011. Выбирается это число с учетом тех свойств, что оно должно делиться по модулю 2 без остатка только на единицу и само на себя. Образующий полином имеет разрядность на единицу больше чем разрядность контрольного кода. К примеру, если требуется получить 8 - разрядный контрольный код необходимо взять образующий полином 9 - разрядный.

В рассматриваемом примере это полином 5-го разряда, а контрольная сумма (остаток от деления) будет 4-х разрядной. Если бы требовалось получить 8-разрядный остаток то можно, к примеру, было бы взять образующий полином равным 100011101 в шестнадцатеричном коде 11D.

Операция деления по модулю два выполняется практически так же как обычное деление в столбик (рис. 1 <#"872077.files/image001.gif">

Рис. 1

2.      Табличный метод вычисления CRC

Реализация на практике вычисления циклического контрольного кода, выполняется параллельным и последовательным методами. Практическая реализация вычисления этого остатка возможна по приведенному здесь примеру аппаратным или программным способом, но этот способ считается медленным. Увеличить скорость вычисления контрольного кода можно, прибегнув, к так называемому табличному методу. Суть метода такова создается таблица чисел размером 2ⁿхn, где n - разрядность контрольной суммы. Метод вычисления чисел в таблице следующий (табл. 1 <#"872077.files/image002.gif">

Рис. 2. Параллельный вычислитель 8-разрядной циклической контрольной суммы на ПЗУ.

В случае если разрядность контрольной суммы n>=16 применяют вычисление в последовательном коде. При этом методе вычисления все биты информационного массива начиная с первого, поступают на вход вычисляющего устройства последовательно бит за битом.

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

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

Рис.3 Последовательный вычислитель 16-разрядной циклической контрольной суммы на регистре сдвига.

На рис.  <#"872077.files/image004.gif"> взаимно однозначно <https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%B5%D0%BA%D1%86%D0%B8%D1%8F> соответствует двоичный полином [1]  его коэффициенты представляют собой исходную последовательность. К примеру, последовательности бит 1011010 соответствует многочлен:

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

Где

R(x) - многочлен, представляющий значение CRC;

P(x) - многочлен, коэффициенты которого представляют входные данные;

G(x) - порождающий многочлен;

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

При делении с остатком <https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BA%D0%BE%D0%BC> исходного многочлена (представляющего входной массив бит) на порождающий многочлен G(x) степени N можно получить 2^N различных остатков от деления. Многочлен G(x) как часто бывает является неприводимым <https://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%BF%D1%80%D0%B8%D0%B2%D0%BE%D0%B4%D0%B8%D0%BC%D1%8B%D0%B9_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%87%D0%BB%D0%B5%D0%BD>. Порождающий многочлен подбирают обычно в соответствии с требованиями к хэш-функции <https://ru.wikipedia.org/wiki/%D0%A5%D1%8D%D1%88-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F> в для каждого конкретного применения.

Однако следует отметить, что существует множество стандартизованных образующих полиномов, имеющих хорошие математические и корреляционные свойства (минимальное число коллизий <https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BB%D0%BB%D0%B8%D0%B7%D0%B8%D1%8F_%D1%85%D0%B5%D1%88-%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8>, простота вычисления) в таблице 2 перечислены некоторые стандартные порождающие полиномы.

5.      Вычисление CRC. Параметры алгоритма

Одним из основных параметров CRC является порождающий полином.

С порождающим полиномом связан другой параметр - его степень <https://ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%BF%D0%B5%D0%BD%D1%8C_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%87%D0%BB%D0%B5%D0%BD%D0%B0>, она определяется количеством бит <https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D1%82>, используемых для вычисления значения CRC. На практике наиболее распространены 8-ми, 16-ти и 32-х битовые слова, что обусловлено особенностью архитектуры <https://ru.wikipedia.org/wiki/%D0%9C%D0%B8%D0%BA%D1%80%D0%BE%D0%B0%D1%80%D1%85%D0%B8%D1%82%D0%B5%D0%BA%D1%82%D1%83%D1%80%D0%B0> современной вычислительной техники.

Ещё одним параметром является начальное (стартовое) значение слова. Указанные параметры полностью определяют «традиционный» алгоритм вычисления CRC. Существуют также модификации алгоритма, например, использующие обратный порядок <https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D1%80%D1%8F%D0%B4%D0%BE%D0%BA_%D0%B1%D0%B0%D0%B9%D1%82%D0%BE%D0%B2> обработки битов.

6.      Описание процедуры алгоритма вычисления CRC

Из файла берётся первое слово - это может быть битовый (CRC-1), байтовый (CRC-8) или любой другой элемент. Если старший бит в слове «1», то слово сдвигается влево на один разряд с последующим выполнением операции XOR <https://ru.wikipedia.org/wiki/%D0%98%D1%81%D0%BA%D0%BB%D1%8E%D1%87%D0%B0%D1%8E%D1%89%D0%B5%D0%B5_%D0%B8%D0%BB%D0%B8>. Соответственно, если старший бит в слове «0», то после сдвига <https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D1%82%D0%BE%D0%B2%D1%8B%D0%B9_%D1%81%D0%B4%D0%B2%D0%B8%D0%B3> операция XOR не выполняется. После сдвига теряется старый старший бит, а младший бит освобождается - его значение устанавливается равным нулю. На место младшего бита загружается очередной бит из файла, и операция повторяется до тех пор, пока не загрузится последний бит файла. После прохождения всего файла, в слове остается остаток, который и является контрольной суммой.

7.      Стандартизованные полиномы

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

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

Самый популярный и рекомендуемый IEEE <https://ru.wikipedia.org/wiki/IEEE> полином для CRC-32 используется в Ethernet <https://ru.wikipedia.org/wiki/Ethernet>, FDDI <https://ru.wikipedia.org/wiki/FDDI>, а также этот многочлен является генератором кода Хемминга <https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%B4_%D0%A5%D0%B5%D0%BC%D0%BC%D0%B8%D0%BD%D0%B3%D0%B0>. Использование другого полинома CRC-32C позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения может быть даже выше - поэтому в наши дни он тоже пользуется популярностью.

К примеру, стандарт ITU-T G.hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке. В таблице 2 перечислены наиболее часто используемые полиномы - генераторы CRC. На практике вычисление CRC может включать пре- и пост-инверсию, а также обратный порядок обработки битов. В некоторых реализациях <https://ru.wikipedia.org/wiki/%D0%90%D0%B2%D1%82%D0%BE%D1%80%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%B0%D0%B2%D0%BE> CRC с целью усложнения анализа кода используют некоторые ненулевые начальные значения регистров.

Таблица 2. Стандартизованные полиномы.

8.      Аппаратная реализация CRC32

В качестве порождающего многочлена возьмем CRC-32-IEEE 802.3 <https://ru.wikipedia.org/wiki/IEEE_802.3>.

Синтез схемы вычислителя 32-х разрядной контрольной суммы в последовательном коде произведем по описанному выше алгоритму. Результат построения схемы представлен на рис.4.

Рис. 4. Аппаратная реализация CRC32.

Заключение

вычислитель аппаратный контрольный код

В ходе курсовой работы нами была разработана аппаратная реализация вычислителя 32-разрядной циклической контрольной суммы CRC, с приемом данных в последовательном коде. При проектировании устройства, в качестве порождающего использован стандартизованный полином CRC -32-IEEE 802.3 <https://ru.wikipedia.org/wiki/IEEE_802.3>.