RomeoGolf

Пт 25 Май 2018

USB-polygon-19: CRC-7

Введение

В предыдущем опусе описывалось подключение SD-карты к устройству. Там встречались моменты, связанные с использованием CRC-7, в которой хотелось бы разобраться чуть подробнее.

Как следует из раздела 4.5 спецификации на SD-карты памяти, CRC-7 используется для всех команд, для всех откликов, кроме R3, для регистров CSD и CID. При использовании одной линии данных в режиме поблочной передачи данных применяется CRC-16.

При этом в режиме SPI вычисление CRC отключено. Однако его можно включить, что повысит надежность информационного обмена с картой, особенно при посредственно реализованной линии передачи, например, длинными неэкранированными проводами. Кроме того, можно при желании попробовать перейти от SPI-режима к «родному». Ну и в конце концов, при инициализации карты первая команда подается в «родном» режиме и требует CRC. Там, конечно, уже все вычислено до нас, но желательно не тупо использовать чужие результаты, а разобраться в том, как эти результаты были получены.

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

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

Немного о контроле ошибок

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

Уверенность в том, что информация на приеме соответствует информации на передаче, достигается разными способами. Самый надежный — помехоустойчивое кодирование. Наверное, многие слышали хотя бы названия кодов Хэмминга или Рида-Соломона. При их использовании мало того, что ошибку можно локализовать, ее можно даже исправить (с оговорками, конечно), и приемнику не нужно запрашивать повтор битых данных. Но такое кодирование имеет два серьезных недостатка: увеличенный объем данных для передачи (кодирование-то с избыточностью), и требование вычислительных ресурсов для декодирования, локализации сбоя и восстановления ошибочной информации.

Самый дурацкий вариант, практически бесполезный — установка в определенных местах определенных «магических» констант, типа 55 aa в конце MBR. Вычислительных ресурсов не требует вообще, но уверенности в том, что данные между такими константами целые, не дает никакой. Правда, позволяет определить, не пропали ли некоторые биты-байты при передаче, не стало ли сообщение короче. Так что «магические» константы используются не в этих целях. По крайней мере, не только в этих, и если и в этих, то вместе с другими способами.

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

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

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

Таким образом, приемник получает сообщение и КС. Алгоритм вычисления КС приемнику известен. Приемник вычисляет КС полученных данных и сравнивает с той, что принял вместе с сообщением. Если посчитанная и принятая КС не совпадают, значит и сообщение отличается от того, которое должно быть. Дальнейшее поведение приемника определяется разработчиком в зависимости от назначения прибора: отбросить и забыть, сообщить передатчику об ошибке, запросить повтор, записать в память с признаком сбоя.

Простейший вариант КС — разряд контроля четности. Одноразрядная КС, дополняющая число единиц в двоичном представлении данных до нечетного. По сути, это сумма битов данных по модулю 2, инициализированная единицей. Занимает всего один разряд, требует мало вычислений (операция XOR довольно дешевая), но не помогает обнаружить четную ошибку. Например, если где-то нолик стал единицей, а в другом месте единица — ноликом, или две единицы обнулились.

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

Один из самых сложных вариантов — хеш-функции типа SHA-1 или MD5. Это вовсе не сумма (как и CRC), но суть та же: возможность контроля целостности данных, обработанных соответствующей функцией.

CRC посложнее и понадежнее простого суммирования, но не такое сложное и надежное, как MD5. Имеет массу разновидностей, объединенных принципом вычисления и отличающихся длиной поля, отведенного под результат и порождающим многочленом. Не обеспечивает 100% защиты от допуска сбойного сообщения, но надо очень постараться, чтобы изувечить данные, сохранив CRC. От непреднамеренных сбоев, например, при передаче по не особенно качественным линиям связи, защищает неплохо.

Суть CRC

В общих чертах про это дело написано в Википедии, но кое-что в собственном сжатом пересказе запишу.

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

Короче, CRC — это остаток от деления по модулю 2 исходного сообщения на образующий полином. Число при буквах CRC (CRC-7, например, или CRC-32) указывает на степень полинома, а по сути — на длину делителя (делимым будет сообщение), и, как следствие, на длину результата операции, который будет дописан к сообщению.

То есть, CRC-7 добавит к сообщению 7 разрядов, а CRC-32 — 32 разряда. А степень полинома в практическом применении означает максимальную степень двойки в делителе, то есть, число двоичных разрядов. Таким образом, для CRC-7 степень полинома равна 7, значит, ненулевой старший двоичный разряд делителя — седьмой (начиная с нуля), итого 8 разрядов. Да, результат вычисления CRC на один двоичный разряд короче образующего делителя.

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

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

В этом плане CRC-7 хорош: я не встречал в литературе полинома седьмой степени, отличающегося от x7 + x3 + 1.

Кстати, упомянутый выше бит четности — это также и CRC-1, так как его можно посчитать не только суммированием, но и по общему для других CRC алгоритму с образующим полиномом x + 1.

Подробнее о вычислении CRC-7

Стало быть, CRC-7 — это остаток от деления по модулю 2 некоторого блока данных на образующий полином седьмой степени.

Сперва о блоке данных. Он может быть произвольной длины, но в разумных пределах. Во-первых, чем длиннее блок, тем больше вероятность получения разных блоков с одинаковой КС. Впрочем, для контроля ошибок это не очень критично. Во-вторых, чем длиннее блок, тем больше информации придется повторять, если он окажется сбойным. Обидно, если ошибка в одном бите, а заново пересылать нужно несколько мегабайтов. Блок данных рассматривается как одно длинное двоичное число, последовательность двоичных разрядов. При расчете блок в конце дополняется нулями в количестве, равном степени полинома, для CRC-7 надо дописать 7 нулей. Это для того, чтобы при делении на полином в операции смогли поучаствовать все разряды.

Теперь о полиноме. В нашем случае это x7 + x3 + 1. Не вдаваясь в подробности, можно вместо x подставить двойку. При этом не забываем, что 1 = 20. Тогда получится число 0b10001001 или 0x89. Вот это число будет использоваться в качестве делителя по модулю 2. В разного рода справочных данных пишут, что образующий полином CRC-7 равен 9. Это потому, что старший разряд любого образующего полинома всегда равен 1, стало быть, его можно не учитывать, а подразумевать. Если из полинома CRC-7 выкинуть старший разряд, останется 0b1001 = 0d9 = 0x9.

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

Вот пример десятичного деления столбиком:

  2825 | 7   
  0    | 0403
  28
  28 
   02
   00 
    25
    21
     4

Сперва выделяем старшую двойку. Из нее можно вычесть 7, умноженную только на 0. К полученной в результате вычитания двойке дописываем следующий разряд, получаем 28. Из 28 можно вычесть 7, умноженное на 4 (четверка пойдет очередным разрядом частного). В результате вычитания получаем 0, дописываем из следующего разряда делимого цифру 2, а из нее можно вычесть 7, умноженную на 0 (ноль будет следующим разрядом частного). И так далее, пока не получим в результате вычитания четверку, из которой 7 не вычесть, и дописывать из делимого уже нечего. Итого, частное равно 403, и остаток равен 4.

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

  2825 | 7   
  28   | 403
    25
    21
     4

Деление двоичных чисел по модулю 2 выполняется почти так же. Но есть несколько особенностей.

Во-первых, сложение по модулю 2 и вычитание по модулю 2 — это одна и та же операция, «исключающее ИЛИ» (XOR) поразрядно. Напомню, почему. Вот таблица истинности для операции X1 xor X2 = R:

X1 X2 R
0 0 0
0 1 1
1 0 1
1 1 0

То есть, как «ИЛИ», но исключая последнюю строчку.

При сложении по модулю 2 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1, как и при любом другом сложении, а вот 1 + 1 = 10, но по модулю 2 займов и переносов нет, поэтому старший разряд результата — разряд переноса — отбрасывается, остается 0.

Примерно то же самое с вычитанием. 0 - 0 = 0, 1 - 0 = 0, 1 - 1 = 0, тут все стандартно и понятно. 0 - 1 = -1, а -1 в двоичном представлении — это заполненная единицами разрядная сетка, например, 0xFF для байтового результата операции. В данном случае результат одноразрядный, и 0 - 1 = 1.

Во-вторых (и это следует из первого), с точки зрения арифметики по модулю 2 трудно однозначно сказать, какое число больше, а какое меньше. В обычной десятичной арифметике 9 + 3 = 12, а 9 - 3 = 6, значит, девять на три меньше, чем двенадцать, и на три больше, чем шесть. В арифметике по модулю 2 операции 9 - 3 и 9 + 3 дают одинаковый результат 10.

Далее по тексту применительно к арифметике по модулю два термины «сложение», «вычитание» и «исключающее ИЛИ (xor)» равнозначны и взаимозаменяемы.

В-третьих, раз арифметика двоичная, делитель для вычитания при выполнении деления можно умножать только на цифры 0 и 1. На 0 умножается, если делитель меньше уменьшаемого, и на 1, если больше или равен. А определить «больше» или «меньше» затруднительно. Можно ориентироваться на порядок. У делителя старший разряд равен 1. Если у очередной порции старших разрядов делимого самый старший разряд равен нулю, то делитель умножается на 0, и очередным разрядом результата будет 0, а если единица, то делитель умножается на 1 (то есть, пишется под этой порцией разрядов делимого и вычитается из нее), и очередным разрядом результата будет 1.

Пример ручного расчета для 40 байтов

Возьму образец, используемый в спецификации, в разделе, посвященном CRC-7:

CMD17 (Argument=0) –>
01 010001 00000000000000000000000000000000 “0101010”1

Префикс команды (0b01), код команды (0b010001 = 0x11 = 17), 4 байта аргумента, 7 разрядов КС (выделено полужирным и взято в кавычки) и последний разряд, обязательно равный единице. Можно попробовать пересчитать вручную КС, а потом сравнить ее с приведенной в примере.

Начинаю расчет столбиком. Вместо последнего байта с КС и единицей пишу 7 нулей после аргумента — это делимое. Образующий полином — это делитель:

  01010001000000000000000000000000000000000000000 | 10001001 
  00000000                                        | 0
   10100010

Старшие 8 разрядов делимого начинаются на 0. Значит, первым (старшим) разрядом частного будет 0. Под старшими разрядами делимого пишем 8 нулей, производим вычитание (точнее, xor), игнорируем старший ноль, к получившимся семи разрядам добавляем очередной разряд из делимого, а там ноль.

  01010001000000000000000000000000000000000000000 | 10001001 
  00000000                                        | 01
   10100010
   10001001 
    01010110

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

Процедуру можно чуть-чуть упростить по аналогии с делением «школьным» столбиком. Вычитания делителя, умноженного на 0, не вносят никаких изменений, кроме сдвига для следующего вычитания и добавления еще одного нуля к разрядам частного. Значит, их можно не записывать, чтобы не увеличивать высоту «столбика», а только добавлять нужное количество разрядов из делимого до длины делителя. Кроме того, нас интересует только остаток от деления, а частное никому не нужно, поэтому его тоже можно не записывать. Вот, что получается:

  01010001000000000000000000000000000000000000000 | 10001001 
   10001001                                     .
    010101100                                   .
     10001001                                   .
     0010010100                                 .
       10001001                                 .
        0011101000                              .
          10001001                              .
           11000010                             .
           10001001                             .
            10010110                            .
            10001001                            .
             0011111000                         .
               10001001                         .
                11100010                        .
                10001001                        .
                 11010110                       .
                 10001001                       .
                  10111110                      .
                  10001001                      .
                   011011100                    .
                    10001001                    .
                     10101010                   .
                     10001001                   .
                      010001100                 .
                       10001001                 .
                        000010100000            .
                            10001001            .
                             010100100          .
                              10001001          .
                               010110100        .
                                10001001        .
                                 011110100      .
                                  10001001      .
                                   11111010     .
                                   10001001     .
                                    11100110    .
                                    10001001    .
                                     11011110   .
                                     10001001   .
                                      10101110  .
                                      10001001  .
                                       010011100.
                                        10001001.
                                         00101010

Последняя операция вычитания (xor) дает в результате число 0b10101. Добавляем к нему справа последний нолик, оставшийся от делимого, получаем 0b101010. Больше с ним ничего сделать нельзя — кончились неиспользованные разряды делимого. Этого числа явно недостаточно для того, чтобы вычесть из него делитель — оно короткое. Стало быть, это и есть искомый остаток. Его следует при необходимости дополнить слева нулями до семи разрядов. Нули слева все равно ничего не значат, а результат должен быть семиразрядным. В итоге получается "0101010", что полностью совпадает с КС в примере. Дописываем справа обязательную единицу и получаем последний байт сообщения, содержащего команду 17.

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

Если в случае обычного деления из делимого вычесть остаток, а результат поделить на тот же делитель, то остатком от деления будет ноль — это очевидно. При делении по модулю два получится примерно то же самое. Если из сообщения, дополненного семью нулями, вычесть по модулю 2 остаток от деления на образующий полином (то есть, CRC-7), то получится отправленное сообщение (без учета последней единички), потому что «исключающее ИЛИ» хвостовых нулей и CRC даст в результате CRC. Остаток от деления в этом случае тоже должен быть ноль:

  01010001000000000000000000000000000000000101010 | 10001001 
                              ...
                                   11111010     .
                                   10001001     .
                                    11100111    .
                                    10001001    .
                                     11011100   .
                                     10001001   .
                                      10101011  .
                                      10001001  .
                                       010001001.
                                        10001001.
                                         00000000

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

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

Автоматизация

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

Расчет CRC-7 вручную выполнен успешно, принцип понятен. Можно поручить это дело программному автомату или схеме, построенной на логических элементах.

Для этого понадобится буферный сдвиговый регистр, аппаратный или программная переменная, к которой периодически применяется оператор арифметического сдвига влево.

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

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

Сообщение, для которого рассчитывается КС, лежит наготове для постепенного поразрядного захода в этот регистр:

  |0000000| <- 0101000100000000...

Запускаем цикл задвигания сообщения в регистр поразрядно. На каждом сдвиге проверяем бит переноса. Если из регистра выталкивается 0, то ничего не надо делать, продолжаем цикл:

  0 <- |0000000| <- 101000100000000...
  0 <- |0000001| <- 01000100000000...
  0 <- |0000010| <- 1000100000000...

  0 <- |1010001| <- 00000000...

И вот наступает момент, когда из регистра выдвигается 1. Это соответствует ситуации при делении столбиком, когда пора вычитать делитель:

  1 <- |0100010| <- 0000000...

Но делитель вычитался из 10100010, а здесь, в регистре, осталось 0100010. Старшая единица у операндов в тот момент, когда требуется вычитание, есть всегда, поэтому используется только для обнаружения этого момента, а результатом вычитания старшего разряда все равно всегда был 0. Поэтому для операции вычитания можно использовать не весь делитель, который был при делении столбиком, а тоже обрезанный на старшую единицу. Эту единицу будем подразумевать. От образующего полинома CRC-7 после отбрасывания старшей единицы и незначащих старших нулей остается 1001 двоичное, то есть, 9 десятичное и шестнадцатеричное.

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

Итак, применяем «исключающее ИЛИ» с константой 9 к регистру

  1 <- |0100010| <- 0000000...
    xor 0001001

Получаем

       |0101011| <- 0000000...

И продолжаем сдвигать:

  0 <- |1010110| <- 000000...

На этом шаге снова делать ничего не надо, бит переноса равен нулю. А на следующем надо будет снова вычитать. И так до тех пор, пока не закончится счетчик цикла. В спецификации указано, что для команд защищается 40 разрядов, а для регистров CID и CSD — 120. И не забываем добавить к этому семь ноликов на хвосте, как при делении столбиком.

Это принято называть «прямым алгоритмом». Для аппаратной реализации вполне сносная штука. Для программной имеет серьезный недостаток. Дело в том, что процессор оперирует минимально адресуемой единицей, которая редко бывает меньше восьми разрядов, а бывает и существенно больше. А в данном случае надо сдвигать по одному битику, затрачивая на чуть-чуть сдвинутые данные столько же, сколько на целый байт. Вот если бы сдвигать сразу байтами, то даже сдвигать не надо было бы — просто выполнять операции над последовательными байтами, образующими массив данных.

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

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

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

Итак, понимая принцип вычисления CRC, можно реализовать ее на используемой архитектуре процессора/контроллера или ПЛИС, пользуясь предпочитаемым языком программирования/описания или просто паяльником. А сверить правильность работы реализованного автомата можно с помощью упомянутой уже страницы Википедии, на которой приведены результаты вычисления различных CRC для строки «123456789», которая в шестнадцатеричном виде выглядит, как 31 32 33 34 35 36 37 38 39.

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

Еще один пример — CID

В предыдущем опусе я упомянул, что при отработке получения регистров CID и CSD я посчитал вручную CRC-7 для CID. Это, собственно, и послужило темой для нынешнего опуса. А вот, собственно, и расчет CRC-7 для конкретного полученного регистра, выполненный столбиком вручную.

Логичнее на стороне приема вычислить остаток от деления на образующий многочлен и получить ноль. Но я буду вычислять именно контрольную сумму.

Для начала вот строчка, содержащая считанный CID:

00000000: 13 4b 47 53 44 35 31 32 10 f7 02 80 11 00 68 e9  .KGSD512......h.

Байт с контрольной суммой 0xe9 = 0b11101001.

Дальше идет разложенный в двоичное представление регистр и операции с ним. Получилось очень длинно, поэтому в два приема, с переносом. Первая половина регистра:

    13  |   4b  |   47  |   53  |   44  |   35  |   31  |   32  |
 0001001101001011010001110101001101000100001101010011000100110010
    10001001   
     0010011010
       10001001   
        0010011110
          10001001   
           0010111100
             10001001  
              011010101
               10001001 
                10111001
                10001001  
                 011000010
                  10001001 
                   10010111
                   10001001   
                    0011110010
                      10001001 
                       11110110
                       10001001 
                        11111111
                        10001001 
                         11101101
                         10001001 
                          11001000
                          10001001 
                           10000011
                           10001001    
                            00010100001
                               10001001  
                                010100000
                                 10001001  
                                  010100100
                                   10001001  
                                    010110111
                                     10001001  
                                      011111001
                                       10001001 
                                        11100000
                                        10001001 
                                         11010011
                                         10001001 
                                          10110100
                                          10001001  
                                           011110101
                                            10001001 
                                             11111001
                                             10001001 
                                              11100000
                                              10001001 
                                               11010010
                                               10001001 
                                                10110110
                                                10001001  
                                                 011111110
                                                  10001001 
                                                   11101110
                                                   10001001 
                                                    11001111
                                                    10001001 
                                                     10001101
                                                     10001001    
                                                      00001000010

Вторая половина регистра, дополненная слева переносом от первой половины, а справа отрезан байт с КС, но дописаны 7 нулей:

 перенос   |   10  |   f7  |   02  |   80  |   11  |   00  |   68  |  CRC  |
 00001000010000100001111011100000010100000000001000100000000011010000000000
     10001001    
      00011010010
         10001001 
          10110110
          10001001  
           011111100
            10001001 
             11101011
             10001001 
              11000101
              10001001 
               10011001
               10001001   
                0010000101
                  10001001    
                   00011001100
                      10001001 
                       10001010
                       10001001      
                        0000011000101
                             10001001 
                              10011000
                              10001001   
                               0010001000
                                 10001001       
                                  00000010000001
                                        10001001    
                                         00010000001
                                            10001001    
                                             00010000000
                                                10001001    
                                                 00010010000
                                                    10001001   
                                                     0011001011
                                                       10001001 
                                                        10000100
                                                        10001001    
                                                         00011011000
                                                            10001001 
                                                             10100010
                                                             10001001  
                                                              010101100
                                                               10001001  
                                                                010010100
                                                                 10001001  
                                                                  001110100

Берем остаток: 1110100 и приклеиваем справа обязательную единицу. Получаем 11101001, то есть 0xE9, что и требовалось получить.


Теги: