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

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

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

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

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

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

Москва

• Введение
• 1. Операция деление по модулю 2
• 2. Табличный метод вычисления CRC
• 3. Аппаратная реализация вычисления CRC в параллельном и последовательном коде
• 4. Математическое описание алгоритма вычисления CRC

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

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

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

8. Аппаратная реализация 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.999 985, а для n = 32 она составит 0.9 999 999 997 672. Другими словами практически все ошибки будут обнаружены.

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

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

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

Операция деления по модулю два выполняется практически так же как обычное деление в столбик (рис. 1), но вместо вычитания выполняется поразрядное сложение по модулю 2, где каждый полученный бит есть результат выполнения функции исключающее ИЛИ (XOR) от соответствующих слагаемых битов. Остаток от деления в данном примере 1000 есть циклическая контрольная сумма (частное отбрасывается).

Рис. 1

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

Реализация на практике вычисления циклического контрольного кода, выполняется параллельным и последовательным методами. Практическая реализация вычисления этого остатка возможна по приведенному здесь примеру аппаратным или программным способом, но этот способ считается медленным. Увеличить скорость вычисления контрольного кода можно, прибегнув, к так называемому табличному методу. Суть метода такова создается таблица чисел размером 2ⁿхn, где n — разрядность контрольной суммы. Метод вычисления чисел в таблице следующий (табл. 1).

Таблица 1. Табличный метод вычисления контрольной суммы.

Числа являются остатком от деления по модулю 2 числа с n конечными нулями (в нашем примере n = 8) и с n начальными разрядами, равными номеру числа (его адресу) в таблице. Выполняется деление на 9-разрядный образующий полином. Вычисление таблицы производится однократно, и она хранится в ПЗУ или на диске.

Алгоритм вычисления контрольного кода при помощи данной таблицы следующий (рассматриваем случай n = 8). Выбирается первый байт массива, который рассматривается как адрес в таблице (номер числа). Выбираем в таблице число с данным номером — получаем остаток О¹. Берем второй байт информационного массива и суммируем его по модулю 2 с остатком О¹. Полученное число есть адрес в таблице. Для этого адреса берем из таблицы остаток О². Выбираем третий байт массива, суммируем его по модулю 2 с остатком О². Полученное число есть адрес в таблице, выбираем из нее остаток О³ и так далее до конца массива.

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

Аппаратная реализация этого алгоритма при помощи цифровых микросхем требует ПЗУ с организацией 2ⁿхn (256×8 при 8-разрядной контрольной сумме), n-разрядного регистра и n элементов исключающее ИЛИ (рис. 2).

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

Перед тем, как начинается вычисление контрольного кода, регистр обнуляется подачей на соответствующий вход сигнала сброса. После того как обработан последний байт массива в выходном регистре получается значение циклической контрольной суммы. У данной схемы имеется один существенный недостаток, который имеет место при параллельном вычислении. Если число разрядов контрольной суммы велико, может потребоваться очень большой объем памяти ПЗУ (64Кх16 для 16-разрядной суммы и 4Гх32 для 32-разрядной суммы). Как видно из приведенных цифр применение данной схемы может быть целесообразно при числе разрядов контрольной суммы n<=16, в связи с чем она применяется редко. Достоинством метода параллельного вычисления является его быстродействие (байты могут поступать с периодом, равным сумме задержки выходного регистра, времени выборки адреса ПЗУ и задержки элемента Исключающее ИЛИ).

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

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

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

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

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

На рис. 3 представлена принципиальная схема устройства вычисления 16-разрядной циклической контрольной суммы в последовательном коде. Образующий полином в рассматриваемом примере взят следующий: 1 0001 0000 0010 0001 или 11 021 в шестнадцатеричной системе. Как видно в коде образующего полинома три единицы не учитывая младшего разряда, следовательно, в схеме вычислителя необходимо взять три точки включения обратной связи. Обратные связи подключаются к номерам тех разрядов сдвигового регистра, которые соответствуют номерам единиц в образующем полиноме.

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

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

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

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

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

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

Где

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

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

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

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

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

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

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

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

С порождающим полиномом связан другой параметр — его степень, она определяется количеством бит, используемых для вычисления значения CRC. На практике наиболее распространены 8-ми, 16-ти и 32-х битовые слова, что обусловлено особенностью архитектуры современной вычислительной техники.

Ещё одним параметром является начальное (стартовое) значение слова. Указанные параметры полностью определяют «традиционный» алгоритм вычисления CRC. Существуют также модификации алгоритма, например, использующие обратный порядок обработки битов.

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

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

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

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

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

Самый популярный и рекомендуемый IEEE полином для CRC-32 используется в Ethernet, FDDI, а также этот многочлен является генератором кода Хемминга. Использование другого полинома CRC-32C позволяет достичь такой же производительности при длине исходного сообщения от 58 бит до 131 кбит, а в некоторых диапазонах длины входного сообщения может быть даже выше — поэтому в наши дни он тоже пользуется популярностью.

К примеру, стандарт ITU-T G. hn использует CRC-32C с целью обнаружения ошибок в полезной нагрузке. В таблице 2 перечислены наиболее часто используемые полиномы — генераторы CRC. На практике вычисление CRC может включать преи пост-инверсию, а также обратный порядок обработки битов. В некоторых реализациях CRC с целью усложнения анализа кода используют некоторые ненулевые начальные значения регистров.

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

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

В качестве порождающего многочлена возьмем CRC-32-IEEE 802.3.

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

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

Заключение

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