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, что и требовалось получить.