Циклическая проверка избыточности (CRC): поиск и даже исправление ошибок в цифровых данных
В этом техническом резюме объясняется, что такое CRC, и как вы можете использовать его, чтобы сделать вашу цифровую связь более надежной.
Связанная информация
Серый код
Мир теперь полностью зависит от хранения и передачи цифровых данных. Самолеты, фондовые рынки, системы безопасности, скороварки - факт, современная жизнь быстро опустится в хаос, если мы не сможем обеспечить точность в постоянно текущем и необъятно огромном потоке из них и нулей.
Есть две основные задачи, связанные с поддержанием целостности наших цифровых данных. Номер один избегает ошибок в первую очередь; эта цель включает в себя множество инженерных практик, которые способствуют надежной передаче и приему цифровых данных. Но, несмотря на все наши усилия, возможны ошибки, и это приводит нас к второй задаче: обнаружение ошибок. Если система может обнаруживать ошибки, она также может компенсировать эти ошибки, просто выкинув сомнительные данные или запросив дубликат передачи.
Метод обнаружения ошибок при выборе
Если вы знакомы с битом четности, который иногда используется в связи с UART, вы знаете что-то об обнаружении ошибок. Но бит четности является довольно жалким механизмом обнаружения ошибок; на самом деле, насколько я могу судить, большинство методов обнаружения ошибок более или менее трогательны по сравнению с циклической проверкой избыточности (CRC), которая явно стала доминирующим подходом - некоторые крупные имена в цифровой связи (включая CAN, USB и Ethernet) используют CRC как часть своего протокола передачи данных.
Структура пакета данных USB
Эффективный, но не простой
Эта короткая статья не является местом для изучения деталей вычислений CRC и производительности, и, кроме того, я не имею возможности излагать эту тему. Суть в том, что двоичный «многочлен» применяется к потоку данных таким образом, чтобы генерировать контрольную сумму, которая, скорее всего, изменится, если один или несколько битов в сообщении изменились.
Этот «многочленный» бизнес представляет собой просто математически удобный способ обращения к определенной последовательности бит. Например:
$$ x ^ {16} + x ^ {12} + x ^ 5 + 1 = 0001 \ 0000 \ 0010 \ 0001 $$
Это широко используемый полином «CCITT». Это полином 16-го порядка, что означает, что соответствующее двоичное число имеет ширину 16 бит и что итоговая контрольная сумма CRC будет иметь ширину 16 бит. (Обратите внимание, что коэффициент для члена высшего порядка считается равным 1 и опускается в двоичной версии.) Термины, которые не отображаются в математическом выражении, имеют двоичный код 0 в качестве коэффициента.
Обнаружение ошибок проще и эффективнее с аппаратным CRC-модулем; эта диаграмма из справочного руководства EFM8LB1 передает функции периферийного устройства CRC в микроконтроллере EFM8 Laser Bee
Два CRC, не один
Создание CRC только для исходного сообщения не поможет вам. Ключом к реализации обнаружения ошибок CRC является обеспечение того, чтобы и передатчик, и приемник генерировали контрольную сумму и точно так же.
Передатчик генерирует контрольную сумму для передаваемых данных и включает ее в исходное сообщение, а получатель генерирует собственную контрольную сумму с использованием полученных данных. Если сообщение получателя не соответствует сообщению передатчика, весьма вероятно, что контрольные суммы будут отличаться; таким образом, приемник считает данные ошибочными, если контрольные суммы CRC не совпадают.
Дальнейшее продвижение
Вы должны знать, что обработка CRC может фактически использоваться для исправления ошибок, а не просто для их обнаружения. Здесь мы имеем дело с двоичными данными, поэтому, если CRC позволяет нам идентифицировать ошибочный бит, мы можем восстановить исходную информацию, просто перевернув бит.
Детали исправления ошибок на основе CRC находятся за пределами моей интеллектуальной зоны комфорта. Если вам нужна дополнительная информация, вам нужно продолжить исследования в другом месте или надеяться, что эта тема скоро будет рассмотрена в новой статье AAC!