реклама на сайте
подробности

 
 
6 страниц V  « < 3 4 5 6 >  
Reply to this topicStart new topic
> Алгоритм CRC16
vallav
сообщение Apr 18 2010, 13:17
Сообщение #61


Частый гость
**

Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977



Цитата(zltigo @ Apr 17 2010, 19:26) *
Зачем повторяться? Но если хотите, то последний раз - Вы, и продолжаете бездумствовать sad.gif, даже после лобовых указаний. Ну так имеющий разум да поймет, ну хотя-бы со временем.
Я все сказал.

Притчу про повторение слова халва слышать приходилось? Можете продолжать, но мне надоело.

Не то. В данном случае речь идет просто о банальной вероятности обнаружения ошибки.


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

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

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



Цитата(mdmitry @ Apr 17 2010, 19:20) *
В этом случае требуется помехоустойчивое кодирование. Битовый поток кодируют и перемежают, а потом передают по каналу связи.


Помехоустойчивое кодирование требуется в случае, если или 90% пакетов сбойные или повторная посылка сбойного
пакета затруднена.
Если сбойных пакетов ~10% и нет проблем повторить посылку пакета - зачем нам паровоз?
А вот между велосипедом и самокатом повыбирать стоит...
Go to the top of the page
 
+Quote Post
Палыч
сообщение Apr 18 2010, 14:22
Сообщение #62


Гуру
******

Группа: Свой
Сообщений: 2 399
Регистрация: 10-05-06
Из: г. Новочеркасск
Пользователь №: 16 954



Цитата(vallav @ Apr 18 2010, 16:32) *
Если сбойных пакетов ~10% ...
Это - результат Вашего неправильного проектирования...
Go to the top of the page
 
+Quote Post
vallav
сообщение Apr 18 2010, 14:32
Сообщение #63


Частый гость
**

Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977



Цитата(Палыч @ Apr 18 2010, 18:37) *
Это - результат Вашего неправильного проектирования...


Полагаете, работать не будет?
А как должно быть правильно?
И каков ответ - что лучше?
Go to the top of the page
 
+Quote Post
Палыч
сообщение Apr 18 2010, 15:03
Сообщение #64


Гуру
******

Группа: Свой
Сообщений: 2 399
Регистрация: 10-05-06
Из: г. Новочеркасск
Пользователь №: 16 954



Цитата(vallav @ Apr 18 2010, 17:47) *
Полагаете, работать не будет?
А как должно быть правильно?
Работать - будет. Но - плохо... Если каждый десятый пакет - сбойный, это - просто отвратительно... Скорее всего, при проектировании канала передачи информации приняты неправильные технические решения.
Go to the top of the page
 
+Quote Post
VslavX
сообщение Apr 18 2010, 20:13
Сообщение #65


embarrassed systems engineer
*****

Группа: Свой
Сообщений: 1 083
Регистрация: 24-10-05
Из: Осокорки
Пользователь №: 10 038



Цитата(vallav @ Apr 18 2010, 16:32) *
Что пропустит CRC?

Ничего не пропустит - все обнаружит. Описанная ошибка это некоторое K разрядностью менее длины проверочного слова умноженное на X^n + 1, где n - число бит между ошибками. А X^n + 1 гарантировано без останка не делится для выбранного полинома для достаточно большого n (которое не может превышать общую длину блока, для которого кодовое расстояние 2+). А раз не делится - значит CRC при такой ошибке гарантировано изменится и такую ошибку обнаружит - то есть любое инвертирование бит (менее длины проверочного кода) подряд дважды в любом месте блока будет обнаружено.
Go to the top of the page
 
+Quote Post
vallav
сообщение Apr 19 2010, 04:22
Сообщение #66


Частый гость
**

Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977



Цитата(Палыч @ Apr 18 2010, 19:18) *
Работать - будет. Но - плохо... Если каждый десятый пакет - сбойный, это - просто отвратительно... Скорее всего, при проектировании канала передачи информации приняты неправильные технические решения.


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



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


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

Кстати, чтобы CRC обнаруживало все двойные ошибки, нужно чтобы в конце была выполнена холостая прокрутка.
Иначе двойная ошибка - бит в последнем слове и бит в слове CRC может быть пропущена.
Go to the top of the page
 
+Quote Post
VslavX
сообщение Apr 19 2010, 05:26
Сообщение #67


embarrassed systems engineer
*****

Группа: Свой
Сообщений: 1 083
Регистрация: 24-10-05
Из: Осокорки
Пользователь №: 10 038



Цитата(vallav @ Apr 19 2010, 07:37) *
Да, двойные ошибки будут все обнаружены.
Но интересует обнаружение четверных ошибок, пропущенных байтовым контролем по четности ( то есть, два сбойных байта в блоке,
в каждом байте двухбитовая ошибка ).

Вы не поняли что я написал. Будет обнаружена двойная ошибка для ЛЮБОЙ последовательности в 'к' бит, если 'к' меньше длины проверочного кода. Длина байта - 8 бит, длина CRC-16 - 16 бит. Причем между сбойными последовательностями может быть произвольное количество битов, не обязательно выравнено на байт. То есть, если одинаково сбоят, например биты 1 и 5 в любых даух байтах - это обнаруживается. Даже если одинаково сбоят биты 0..14 в любых 15 битах - то есть правильная последовательность в двух местах по-XOR-ена с одной и той же 15-битовой комбинацией - то такое тоже 100% обнаруживается.
Если же ошибки в байтах разные, то может уже и пропустить.
Go to the top of the page
 
+Quote Post
vallav
сообщение Apr 19 2010, 05:52
Сообщение #68


Частый гость
**

Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977



Вы хоть в курсе - что это такое - CRC и как именно это делается?
Похоже, что нет.
У Вас - просто наоборот, чем получается при простом XOR без сдвига.
Но это не CRC, это что то другое...
Причина редактирования: Бездумное цитирование
Go to the top of the page
 
+Quote Post
VslavX
сообщение Apr 19 2010, 06:21
Сообщение #69


embarrassed systems engineer
*****

Группа: Свой
Сообщений: 1 083
Регистрация: 24-10-05
Из: Осокорки
Пользователь №: 10 038



Цитата(vallav @ Apr 19 2010, 09:07) *
Вы хоть в курсе - что это такое - 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 бит включительно.
Go to the top of the page
 
+Quote Post
vallav
сообщение Apr 19 2010, 07:03
Сообщение #70


Частый гость
**

Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977



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

На самом деле, CRC заточена на отлавливание двух битовых ошибок произвольно расположенных в передаваемогм пакете
( двухкратная ошибка ).
Но это не дается даром.
CRC довольно плох при отлавливания многобитовых ошибок.
В часности, в данном случае нужно ловить четырехкратную ошибку.
Причина редактирования: Бездумное цитирование
Go to the top of the page
 
+Quote Post
VslavX
сообщение Apr 19 2010, 07:26
Сообщение #71


embarrassed systems engineer
*****

Группа: Свой
Сообщений: 1 083
Регистрация: 24-10-05
Из: Осокорки
Пользователь №: 10 038



Цитата(vallav @ Apr 19 2010, 10:18) *
Ну что Вам сказать.
Вы настолько в этм всем уверены, что ...

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

Цитата(vallav @ Apr 19 2010, 10:18) *
На самом деле, CRC заточена на отлавливание двух битовых ошибок произвольно расположенных в передаваемогм пакете
( двухкратная ошибка ).

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

Цитата(vallav @ Apr 19 2010, 10:18) *
Но это не дается даром.

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

Цитата(vallav @ Apr 19 2010, 10:18) *
CRC довольно плох при отлавливания многобитовых ошибок.

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

Цитата(vallav @ Apr 19 2010, 10:18) *
В часности, в данном случае нужно ловить четырехкратную ошибку.

Мне тоже уже надоело. Импульс в нужную сторону - полиномиальная арифметика в частности, и теория линейных кодов в общем - Вам придали, а дальше - "имеющий уши да услышит". За сим разрешите откланяться.
Go to the top of the page
 
+Quote Post
vallav
сообщение Apr 19 2010, 10:35
Сообщение #72


Частый гость
**

Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977



Цитата(VslavX @ Apr 19 2010, 11:41) *
Мне тоже уже надоело. Импульс в нужную сторону - полиномиальная арифметика в частности, и теория линейных кодов в общем - Вам придали, а дальше - "имеющий уши да услышит". За сим разрешите откланяться.


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

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

Кстати, на поясните Ваше - "Да, btw, выше показано что не только двухкратная однобитовая но и двухкратная многобитовая, не говоря уже об однократных многобитовых".
Чем именно двухкратная многобитовая ошибка отличается от однократной многобитовой?
Go to the top of the page
 
+Quote Post
VslavX
сообщение Apr 19 2010, 11:27
Сообщение #73


embarrassed systems engineer
*****

Группа: Свой
Сообщений: 1 083
Регистрация: 24-10-05
Из: Осокорки
Пользователь №: 10 038



Цитата(vallav @ Apr 19 2010, 13:50) *
Так как Вы уверены, что она отлавливает все четверные ошибки.

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

Цитата(vallav @ Apr 19 2010, 13:50) *
И даже отлавливает все ошибки большей кратности, вплоть до 16.

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

Цитата(vallav @ Apr 19 2010, 13:50) *
Если не секрет, CRC с каким полиномом обладает таким замечательным свойством?
Для пакета длиной в 256 байт и контрольном слове длиной 16 бит.
Можно попробовать проверить это замечательное свойство прямым вычислением
( если полином приведете ).

Э-э... Стесняюсь cпросить, у Вас гугль недоступен? Первая ссылка
OK, сейчас я занят, но вечером потрачу 15 минут и накатаю тестик CRC-16 на блоке 256 байт.
Go to the top of the page
 
+Quote Post
vallav
сообщение Apr 19 2010, 12:37
Сообщение #74


Частый гость
**

Группа: Участник
Сообщений: 197
Регистрация: 8-04-05
Пользователь №: 3 977



Цитата(VslavX @ Apr 19 2010, 15:42) *
Про _все_ я не говорил, имелся в виду Ваш пример, где искажены два байта, по два бита в каждом, на одних и тех же позициях.


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



Цитата(VslavX @ Apr 19 2010, 15:42) *
Э-э... Стесняюсь cпросить, у Вас гугль недоступен? Первая ссылка
OK, сейчас я занят, но вечером потрачу 15 минут и накатаю тестик CRC-16 на блоке 256 байт.


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

И что именно Вы там обнаружили?
Или Вы туда даже не заглядывали...
Go to the top of the page
 
+Quote Post
defunct
сообщение Apr 19 2010, 14:28
Сообщение #75


кекс
******

Группа: Свой
Сообщений: 3 825
Регистрация: 17-12-05
Из: Киев
Пользователь №: 12 326



Цитата(vallav @ Apr 19 2010, 10:18) *
CRC довольно плох при отлавливания многобитовых ошибок.

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

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


Цитата
А CRC может пропустить не эти, а другие, удовлетворяющие исходному условию.

Чтобы Вам не быть голословным, можете привести конкретный пример, - когда CRC16 пропускает искажение любых 4-х битов сообщения?
А мы потом пообсуждаем.
Go to the top of the page
 
+Quote Post

6 страниц V  « < 3 4 5 6 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 10th July 2025 - 07:38
Рейтинг@Mail.ru


Страница сгенерированна за 0.01588 секунд с 7
ELECTRONIX ©2004-2016