Хорошо, вот Вам конкретика.
По зашумленному каналу передаются данные.
Передача идет пакетами по 256 байт.
Примерно каждый десятый пакет сбойный - одиночная ошибка.
Многократные ошибки соответственно реже.
Обнаруженные сбойные пакеты пересылаются повторно.
Естественно включен побайтовый контроль четности.
Вопрос - какой метод лучше для обнаружения сбойных пакетов, пропущенных
побайтовым контролем четности?
Прямая 16 битная сумма пропустит сбойный пакет, у которого в одном байте две ошибки и в другом, отстоящем от первого
на четное число байт две ошибки в тех же разрядах. В среднем одну из 4х таких ошибок.
То есть, четверную ошибку достаточно специального вида.
Что пропустит CRC?
Хуже в такой достаточно типичной ситуации CRC или лучше.

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

Как Вам такая конкретика?
Жду Вашего обоснованого выбора.





Помехоустойчивое кодирование требуется в случае, если или 90% пакетов сбойные или повторная посылка сбойного
пакета затруднена.
Если сбойных пакетов ~10% и нет проблем повторить посылку пакета - зачем нам паровоз?
А вот между велосипедом и самокатом повыбирать стоит...

Это - результат Вашего неправильного проектирования...

Полагаете, работать не будет?
А как должно быть правильно?
И каков ответ - что лучше?

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

Ничего не пропустит - все обнаружит. Описанная ошибка это некоторое K разрядностью менее длины проверочного слова умноженное на X^n + 1, где n - число бит между ошибками. А X^n + 1 гарантировано без останка не делится для выбранного полинома для достаточно большого n (которое не может превышать общую длину блока, для которого кодовое расстояние 2+). А раз не делится - значит CRC при такой ошибке гарантировано изменится и такую ошибку обнаружит - то есть любое инвертирование бит (менее длины проверочного кода) подряд дважды в любом месте блока будет обнаружено.

Полагаете, удлинение времени передачи на 10% - категорически неприемлимо?
Но если так уж случилось - что выбрать - прямую сумму или CRC?
Вариант - вообще не пользоваться этим каналом - не интересен.





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

Кстати, чтобы CRC обнаруживало все двойные ошибки, нужно чтобы в конце была выполнена холостая прокрутка.
Иначе двойная ошибка - бит в последнем слове и бит в слове CRC может быть пропущена.

Вы не поняли что я написал. Будет обнаружена двойная ошибка для ЛЮБОЙ последовательности в 'к' бит, если 'к' меньше длины проверочного кода. Длина байта - 8 бит, длина CRC-16 - 16 бит. Причем между сбойными последовательностями может быть произвольное количество битов, не обязательно выравнено на байт. То есть, если одинаково сбоят, например биты 1 и 5 в любых даух байтах - это обнаруживается. Даже если одинаково сбоят биты 0..14 в любых 15 битах - то есть правильная последовательность в двух местах по-XOR-ена с одной и той же 15-битовой комбинацией - то такое тоже 100% обнаруживается.
Если же ошибки в байтах разные, то может уже и пропустить.

Вы хоть в курсе - что это такое - CRC и как именно это делается?
Похоже, что нет.
У Вас - просто наоборот, чем получается при простом XOR без сдвига.
Но это не CRC, это что то другое...

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

"Пакет" = "Передаваемые данные" + "Ошибка"

В этом тождестве все переменные - полиномы, а операция сложения выполняется полиномиально - именно "простым XOR-ом". CRC- это остаток от полиномиального деления:

CRCp = "Пакет" % "проверочный полином"

Для правильный данных:

CRCd = "Передаваемые данные" % "проверочный полином"

CRCp будет равно CRCd (пакет ошибочно считается правильным) тогда и только тогда, когда

CRCe = "Ошибка" % "проверочный полином" = 0 (равно нулю, то есть делится без остатка на проверочный полином)

Для Вашего примера ошибка представляется так:

"Ошибка" = (00..00100..n-bit...00100..00) x K, битовая длина произвольного K меньше длины проверочного полинома

CRCe будет нулевым если K или (00..100..n-bit..00100..00) делится на полином без остатка
К - не делится, так как его длина меньше чем длина полинома
(00..1..1..00) - не делится для любой возможной комбинации в пакете, так как полином и разрядность CRC всегда выбирается такой чтобы мин кодовое расстояние было не менее 2.
Поэтому ошибка того типа про которую Вы толкуете ловится CRC "влет". Компрене?

Upd: Для CRC-16 длина проверочного полинома на самом деле 17 бит, поэтому длина К может быть до 16 бит включительно.

Ну что Вам сказать.
Вы настолько в этм всем уверены, что ...

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

Ясно, значит будем сомневаться в арифметике. Более просто и строго я объяснить не в силах.


Да, btw, выше показано что не только двухкратная однобитовая но и двухкратная многобитовая, не говоря уже об однократных многобитовых.


Чем надо платить?
На самом деле, CRC в "железе" реализуется намного проще чем упомянутая Вами обычная арифметическая сумма. Программная реализация CRC тоже не особо сложна - если понять принцип. Я Вам даже открою "секрет" - в криптографии, там где очень длинные числа, полиномиальное деление и сложение как правило работают быстрее обычных - так как нет этого дурацкого распространяемого между словами переноса. Медленее работает умножение - и то исключительно потому что у большинства процессоров нет инструкции полиномиального умножения.


Любую однократную в "k бит подряд" CRC отлавливает. Ну а умеючи-то - все что хошь сломать можно


Мне тоже уже надоело. Импульс в нужную сторону - полиномиальная арифметика в частности, и теория линейных кодов в общем - Вам придали, а дальше - "имеющий уши да услышит". За сим разрешите откланяться.

Значит Ваша версия - в приведенном примере лучше использовать CRC.
Так как Вы уверены, что она отлавливает все четверные ошибки.
Так?

И даже отлавливает все ошибки большей кратности, вплоть до 16.
И зыждется эта уверенность на том, что "полиномиальная арифметика в частности, и теория линейных кодов в общем".
Если не секрет, CRC с каким полиномом обладает таким замечательным свойством?
Для пакета длиной в 256 байт и контрольном слове длиной 16 бит.
Можно попробовать проверить это замечательное свойство прямым вычислением
( если полином приведете ).

Кстати, на поясните Ваше - "Да, btw, выше показано что не только двухкратная однобитовая но и двухкратная многобитовая, не говоря уже об однократных многобитовых".
Чем именно двухкратная многобитовая ошибка отличается от однократной многобитовой?

Про _все_ я не говорил, имелся в виду Ваш пример, где искажены два байта, по два бита в каждом, на одних и тех же позициях.


Да, если эти 16 бит расположены подряд.


Э-э... Стесняюсь cпросить, у Вас гугль недоступен? Первая ссылка
OK, сейчас я занят, но вечером потрачу 15 минут и накатаю тестик CRC-16 на блоке 256 байт.

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





Вы про
http://rsdn.ru/article/files/classes/SelfCheck/crcguide.pdf

И что именно Вы там обнаружили?
Или Вы туда даже не заглядывали...

- несомненно ваша арифметическая сумма гораздо лучше.

Вероятность того, что CRC32 пропустит серьезную ошибку - например весь пакет искажен нафиг - равна 1 / 2^32.
Вероятность же, что такую ошибку пропустит ваша сумма равна - 1/2. --> если пакет будет занулен - пропустит, если "заединичен" - непропустит.
Вот собсно и вся надежность децкой суммы - 50/50.



Чтобы Вам не быть голословным, можете привести конкретный пример, - когда CRC16 пропускает искажение любых 4-х битов сообщения?
А мы потом пообсуждаем.