Я делаю некоторую передачу данных от dsPIC к ПК, и я делаю 8-битный CRC для каждого блока 512 байтов, чтобы убедиться, что нет ошибок. При включенном коде CRC я получаю около 33 КБ / с, без него - 67 КБ / с.
Какие есть альтернативные алгоритмы обнаружения ошибок, чтобы проверить, что будет быстрее?
Ответы:
Хотя могут быть более быстрые варианты, чем CRC, если вы их используете, вы, вероятно, в конечном итоге пожертвуете некоторой степенью возможности обнаружения ошибок. В зависимости от ваших требований к обнаружению ошибок, альтернативой может быть использование кода CRC, оптимизированного для вашего приложения.
Сравнение CRC с другими вариантами приведено в превосходном ответе Мартина Томпсона .
Одним из способов помочь с этим является pycrc - инструмент (написанный на python 1 ), который может генерировать исходный код на C для десятков комбинаций модели и алгоритма crc . Это позволяет оптимизировать скорость и размер для вашего собственного приложения, выбирая и сравнивая различные комбинации. 1: требуется Python 2.6 или более поздняя версия.
Она поддерживает
crc-8
модель , но и поддерживаетcrc-5
,crc-16
иcrc-32
среди других. Что касается алгоритмов , он поддерживаетbit-by-bit
,bit-by-bit-fast
иtable-driven
.Например (загрузка архива):
Вы можете даже делать такие вещи, как указание, используя двойной поиск (с 16-байтовой таблицей поиска), а не однобайтовый поиск с 256-байтовой таблицей поиска.
Например (клонирование репозитория git):
Учитывая ограничения памяти и скорости, эта опция может быть лучшим компромиссом между скоростью и размером кода. Единственный способ быть уверенным в том, чтобы проверить это, хотя.
Pycrc репозиторий на GitHub , как его отслеживания проблем , но он также может быть загружена с сайта SourceForge .
источник
Простая однобитовая четность (в основном, XOR данных поверх себя снова и снова) - это почти так быстро, как только можно. Вы теряете много ошибок при проверке CRC.
В псевдокоде:
источник
Действительно хорошая статья, сравнивающая производительность различных контрольных сумм и CRC во встроенном контексте:
Эффективность контрольных сумм для встраиваемых сетей
Некоторые цитаты из выводов (на основе их исследований вероятностей необнаруженных ошибок):
Когда доминируют пакетные ошибки
В других приложениях
Если стоимость вычислений очень ограничена
(как в вашем случае) используйте (в порядке эффективности):
Другие цитаты:
а также
источник
Контрольная сумма Адлера должна быть достаточной для проверки искажений при передаче. Он используется библиотекой сжатия Zlib и принят стандартом мобильной графики 3D Java для быстрой, но эффективной проверки целостности данных.
Со страницы википедии :
источник
Я не знаю ничего, что было бы столь же эффективно при обнаружении ошибок, как CRC и быстрее - если бы оно было, люди использовали бы его вместо этого.
Вы можете попробовать простую контрольную сумму, но вероятность обнаружения ошибок гораздо ниже.
источник
Ну, сама логика контрольной суммы хороша, и люди могут помочь с более быстрыми алгоритмами.
Если вы хотите повысить скорость работы вашего компонента, вам может потребоваться изменить общую технику, чтобы отделить компонент передачи от компонента проверки.
Если у вас есть эти два независимых элемента (в разных потоках), вы можете получить полную скорость передачи и пересылать только ошибочные пакеты.
Алгоритм будет выглядеть примерно так:
Это позволит вам передавать с максимально возможной скоростью, а если вы играете с размером пакета, вы можете определить оптимальную частоту отказов VS, а также скорость проверки / повторной отправки.
источник
Контрольные суммы традиционные
(уменьшить # '+ поток)
XOR, как указано выше, будет также работать
(уменьшить # 'поток XOR)
Немного более сложной (более медленной) схемой является стандартная проверка четности для последовательных соединений.
На этом уровне вы торгуете правильно для скорости. Они иногда терпят неудачу.
На следующем, более сложном уровне вы можете использовать некоторые вещи типа crc / hash.
Другой дизайн должен был бы увеличить размер блока, используемого для потока.
У вас должна быть оценка фактической частоты ошибок, чтобы настроить ваш алгоритм выбора и параметры для размера блока.
источник