vallav
А вот с тем, что посчитать 16 битную сумму намного проще и быстрее, чем правильное 16 битное CRC несогласен.
На аппаратной логике практически любая CRC считается (и проверяется) "влёт". Не факт, что 16 битное сложение (и выше) будет легче.
Для быстрого расчёта на ЭВМ есть эффективные табличные методы вообще без арифметических операций (кроме XOR).

Действительно - есть методы ускоряющие расчет CRC... Но, имхо, скорость их работы не превысит скорости выполнения операции типа: Sum+=Data[i];
Впрочем, могу изменить своё мнение, если Вы приведете исходный текст и временные характеристики программ подсчета CRC, и программы подсчета простой суммы.

На аппаратной логике и БПФ делается влет.

Палыч
Пример на аппаратной логике расчёта обсуждаемой CRC16 для однобитного входного потока:

Требуется 16 триггеров. Не больше чем для простой суммы.

Расчёт для 8-ми битной ЭВМ табличным способом:

Сложение 8 битного числа с 16 битным Sum+=*Data++ чуть быстрее.
Именно поэтому и не согласен, что посчитать 16 битную сумму намного проще и быстрее, чем правильное 16 битное CRC.
Поскольку особого преимущества нет, IMHO, лучше использовать проверенные алгоритмы.

Есть такое понятие - кодовое расстояние. Это число разрядов в двух битовых последовательностях которые отличается. Если у Вас в принимаемой последовательности сбойнул один бит, то кодовое расстояние между правильной и ошибочно принятой последовательности равно 1, если два бита - то 2 и т.д. Так вот, математически доказано, что CRC (которое является фактически делением на определенные полиномы) покрывает максимально возможное кодовое расстояние ошибок для данной длины корректирующего кода . То есть, обнаруживает максимально возможно количество единичных искажений. Если принято какое-то значение CRC, то для получения того же значения CRC нужно исказить некоторое количество бит (ЕМНИП, 14 битов минимум для приведенной CRC-16). Если же у Вас просто сумма, то достаточно исказить всего два бита (например, инвертировать младшие биты в байтах в которых эти биты несовпадают) и ошибка уже не будет обнаружена. Вот поэтому CRC намного лучше простой суммы.

Имхо, Вам память - изменяет. Насколько помню: кодовое расстояние CRC уменьшается с увеличением длины блока данных, и для приведенной CRC16-CCITT при длине блока данных 256 байт оно равно 3.

Очень может быть - я лет 10 назад про выбор CRC читал, возможно, цифра была приведена для более коротких блоков, и, может быть, вообще не для полинома выбранного CCITT (он вроде как не самый удачный). Но то что CRC обеспечивает максимально возможное для линейных кодов минимальное кодовое расстояние - это вроде бы на сегодня так.

Одиночные ошибки обоими способами обнаруживаются все.
Для двойных - зависит от статистики ошибок. Вполне допускаю, что есть такие CRC, которые обнаруживают их все.
Но ничто не дается даром. Эти CRC будут проигрывать простой сумме в обнаружении достаточно типичных ошибок, вызванных помехой -
одиночных многобитных сбоев. Прямая сумма будет обнаруживать все такие сбои длиной меньше или равной длине контрольного слова.
CRC, заточенная на двойные разнесенные ошибки, часть из таких сбоев не заметит.
И больше похоже на правду, что для такого CRC число это не 14 а 3.
Так что, что лучше - зависит от того - а какие именно ошибки нужно обнаруживать.



А разве ктот то утверждал, что на плиске алгоритм CRC нереализуем?



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

А то, что одна из причин использования CRC ( если не единственная ) -
Поскольку особого преимущества нет, IMHO, лучше использовать проверенные алгоритмы - с этим тоже вроде никто не спорит.

Речь о другом - в чем преимущества CRC при обнаружении ошибок при блочной передаче.
И стьль ли они подавляющи ( если есть ) чтобы принебрегать вариантом с простой суммой?

vallav
Пример на VHDL приведён как подтверждение того факта, что реализация на аппаратной логике вычисления CRC как минимум не уступает по производительности и ресурсам вычислению прямой суммы.
Пример кода на С приведёт как подтверждение того факта, что реализация табличным способом не намного сложнее и медленнее, чем прямая сумма. Для данного конкретного случая он в разы не медленнее.
Поясните почему специалисты, разработавшие STANAG5066, не стали использовать обычное сложение, а применили для контроля целостности пакета CRC16 и CRC32. Поскольку STANAG5066 использует в качестве основы STANAG4285, где применён свёрточный код, ошибки при его декодировании пакетные (длина искажённой последовательности как больше длины проверочного слова, так и меньше).

Вообще то реализация сумматора на логике заметно сложнее реализации CRC.
Речь о ситуации, когда сумматор в системе уже есть. И реализован достаточно эффективно.

То есть, там не важно обнаружение двойных разрозненных ошибок а важно определение еденичных поражений порядка длины поверочного
слова? Тогда не знаю почему.
Может исходя из - поскольку особого преимущества нет, IMHO, лучше использовать проверенные алгоритмы.

Сообщение отредактировал vallav - Apr 16 2010, 05:24

ИМО, "единичные поражения порядка длины поверочного слова" CRC выловит ничуть не хуже простой суммы. Ну и как бонус выловит _ВСЕ_ единичные ошибки числом менее или равное кодовому расстоянию для данных длин блока и суммы.
Можно сделать простой эксперимент - берем блок, вычисляем сумму и CRC. Потом вносим определенное "поражение длиной в кодовое слово" - и смотрим сколько вариантов "поражения" не поймает сумма и сколько CRC. Если сумма 16-битная, сложение побайтовое и 16-битовое "поражение" выровнять на границе байта, то будет 255 "непойманных" вариантов для простой суммы, для CRC-16, думаю, будут единичные значения (так как CRC это остаток от деления - нужно будет подобрать такое значение искажения чтобы делилось на образующий полином с нулевым остатком, а таких значений для полиномов применяемых для CRC может быть одно-два).

А что не побитовое сложение?
Разница еще разительнее получится.
Вы где то нашли микроконтроллер, в котором затруднительно делать 16 битные сложения?
Полная сумма не пропустит ни одного еденичного многобитового поражения длиной меньше или равного 16 бит.
CRC же, в зависимости от вида перемешивания битов.
Чем лучше заточена на отлов двойных разрозненных ошибок, тем более короткие еденичные многобитные будет пропускать.

А Вы где-то четко указали что сложения идут 16-битными словами? Обычно программа упрощена - идет поток байтов и складываются байты - не надо рассматривать случаи с нечетным количеством и т.д. И не уводите ситуацию в сторону - я просто привел Вам пример когда простая сумма оказалась многократно хуже CRC. Разумеется и наоборот, можно натянуть условия, и показать что CRC хуже суммы для каких-то конкретных условий, но все равно - не столь кратно. И тут еще вопрос - насколько типично такое "многобитовое поражение", исследования проводили? Линии передачи ведь разные бывают, и вероятности возникновения различных ошибок тоже разные. Я думаю, CCITT несколько более осведомлен в этом вопросе, раз уж выбрана CRC (как я понимаю - для модемных соединений).

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

Я разве говорил, что многобитовая помеха - это когда все 16 бит перевернуты?
Не, не обязательно, часть бит из этих 16 может быть не перевернутой.
На то она и помеха.





Дык если не указано, из примерно одинакового рассматривать надо лучшее а не худшее.
Или Вы все же настаиваете, что для микроконтроллеров 16 битное сложение реализуется существенно сложнее 8 битного?
А с нечетным числом байт в блоке фиксированной длины - полагаете, непреодолимо?

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