Аппаратная реализация вычисления 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 или 11021 в шестнадцатеричной системе. Как видно в коде образующего полинома три единицы не учитывая младшего разряда, следовательно, в схеме вычислителя необходимо взять три точки включения обратной связи. Обратные связи подключаются к номерам тех разрядов сдвигового регистра, которые соответствуют номерам единиц в образующем полиноме.

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

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

Дата добавления: 2015-08-31