Прочтите это и убедитесь, что Вы не правы («Телесистемы»: Конференция «Микроконтроллеры и их применение»)

Разработка, производство и продажа радиоэлектронной аппаратуры

| Карта сайта | Пишите нам | В избранное

Требуется программист в Зеленограде
- обработка данных с датчиков; ColdFire; 40 тыс.
e-mail:jobsmp@pochta.ru

Телесистемы | Электроника | Конференция «Микроконтроллеры и их применение»

Прочтите это и убедитесь, что Вы не правы

Отправлено Цивилизатор 03 апреля 2008 г. 11:39
В ответ на: А вообще у вас там ошибка в программе. CRC не имеет "слепых" мест, кроме как нули в начале при инициализации нулем. отправлено SM 03 апреля 2008 г. 11:14

Приведу пример для CRC2

Берём неприводимый полином 111

Попробуем сформировать CRC2 для 10.
Дописываем слева 11 получаем 1110. "Делим" по алгоритму CRC 1110 на 111 получам 0.

И сколько бы не было нулей в конце если начало блока равно 10 CRC2 всегда будет 0

Смысл такой: если в некотором блоке данных на некотором этапе CRC-деления на полином остаток стал равен нулю, то с этого момента можете пихать в блок сколько угодно нулей, CRC не измениться

И мой вопрос: ка избавиться от этой неприятной фигни

Составить ответ | Вернуться на конференцию

Ответы

Доктор, добавьте вторую, третью и т.д. CRC с другими полиномами и начальными значениями. Не мучите себя и других — argus98 (03.04.2008 11:49:53 81.22.205.230, пустое)
- А все равно будет бесконечное кол-во последовавтельностей, дающий одинаковый результат :) :) — SM (03.04.2008 12:00:21 80.92.255.53, пустое)
  - Так с этим кто спорит?! Вероятность - она и в Африке вероятность... Зато при 4х CRC доктору будет труднее откопать такую последовательность.... и нам опять же спокойнее :) — argus98 (03.04.2008 12:05:41 81.22.205.230, пустое)
    - :-))) — Цивилизатор (03.04.2008 12:15:29 217.118.66.20, пустое)
- Ответ: Т.е. так реально все и делают на практике? Вы так делали? — Цивилизатор (03.04.2008 11:56:54 217.118.66.35, пустое)
  - 1) за всех не отвечу. 2) было дело — argus98 (03.04.2008 11:59:8 81.22.205.230, пустое)
Я об этом и написал, что единственный случай - начальное значение ноль и последовательность нулей. А избавиться другой хэш-функцией, не CRC. Например MD5 или SHA-1 — SM (03.04.2008 11:44:39 80.92.255.53, пустое)
- Ответ: MD5? Хотелось бы малой "кровью". А если зделать как Argus (+) — Цивилизатор (03.04.2008 12:00:25 217.118.66.35, 320 байт)
  - С точки зрения попадания на серию "0" все CRC одинаковы (естественно с разной вероятностью). В принципе если волнуют серии "0", то СRC неподходящая для этого вещь, т.к. CRC хороша для (примерно)равновероятных последовательностей — argus98 (03.04.2008 12:39:28 81.22.205.230, пустое)
  - Ответ: (+) — SM (03.04.2008 12:06:0 80.92.255.53, 417 байт)
    - Ответ: А подробней про "неприводимый полином вреден"..А? — Цивилизатор (03.04.2008 12:15:13 217.118.66.20, пустое)
      - с точки зрения теории, CRC (+): — argus98 (03.04.2008 13:04:42 81.22.205.230, 501 байт)
        
        Что за бред? ;) — Oldring (03.04.2008 16:37:48 91.76.18.68, пустое)
      - Подробнее (+) — SM   (03.04.2008 12:51:8 80.92.255.53, 486 байт)
        
        Ответ: Т.е. если этот полином оптимален для пакета в 128 байт, то он (+) — Цивилизатор   (03.04.2008 13:55:33 217.118.66.48, 147 байт)
        
        Да оставьте как есть. И так будет хорошо. — Oldring   (03.04.2008 14:52:16 91.76.18.68, 64 байт)
        
        Да неохота, чтобы при перезаливке 100 килобайтной прошивки (+) — Цивилизатор   (03.04.2008 16:20:22 217.118.66.45, 96 байт)
        
        А один битик из 100-килобайтной прошивки потеряться и так не может. — Oldring   (03.04.2008 16:26:34 91.76.18.68, пустое)
        
        Ответ: Мне бы Ваш оптимизм (+) — Цивилизатор   (03.04.2008 16:36:36 217.118.66.45, 270 байт)
        
        Это не оптимизм, это элементарная математика. — Oldring   (03.04.2008 16:43:37 91.76.18.68, 443 байт)
        
        Вот именно, что за доли секунды, а у меня этот Гигабайт будет (+) — Цивилизатор   (03.04.2008 17:53:5 217.118.66.45, 325 байт)
        
        Хонечно за 0.5 секунд. Там ведь СВЧ... — Oldring   (03.04.2008 17:57:24 91.76.18.68, пустое)
        
        Ответ: А насчёт битика Вы правы... Он обнаружиться.. Но ведь (+) — Цивилизатор   (03.04.2008 17:55:15 217.118.66.45, 260 байт)
        
        Ну а если всю прошивку электромагнитный импульс выкосит вместе с заливальщиком на пару с программописателем? — Oldring   (03.04.2008 17:59:25 91.76.18.68, пустое)
        
        Ответ: "Против лома нет приёма"(с) :-))) — Цивилизатор   (03.04.2008 18:03:25 217.118.66.45, пустое)
        
        Для 128 байт (1024 бит) нужен CRC10, для 128К - соответственно CRC20. Если длины CRC не хватает для помехоустойчивости - брать несколько разных — argus98   (03.04.2008 14:02:15 81.22.205.230, пустое)
        
        Ответ: А если я возьму для 64 байт CRC16 это есть не "зер гуд"??? (+) — Цивилизатор   (03.04.2008 16:22:11 217.118.66.45, 86 байт)
        
        log2(64*8) = 9, т.е. CRC9. Если вероятности необнаружения ошибки 1/512 не хватает, надо взять несколько CRC9. Если же использовать CRC16, то лучше прогнать блок через вычислитель CRC 65536/512 = 128 раз — argus98   (03.04.2008 16:47:1 81.22.205.230, пустое)
        
        Т.е...Вы хотите сказать, что для маленьких блоков CRC высоких степеней (+) — Цивилизатор   (03.04.2008 17:57:14 217.118.66.45, 103 байт)
        
        Это вовсе не нужно. Надо применить более подходящий полином. — SM   (03.04.2008 16:50:10 80.92.255.53, пустое)
        
        Не "Да", а в принципе достаточно. Она покажет ошибку с той же вероятностью, как и 16 в более большом блоке. Это если исходить из равенства вероятности необнаружения ошибки. А если из максимума вероятности - так чем жирнее CRC, тем она больше. Однако, если выбирать полином для CRC16, то его нужно выбрать исходя из априорных знаний о данных, включая и длину блока. — SM   (03.04.2008 16:46:0 80.92.255.53, пустое)
        
        Вы не учли главного - требований к качеству обнаружения ошибки и количества обнаруживаемых ошибок. Которые нам не озвучили. — SM   (03.04.2008 14:09:13 80.92.255.53, пустое)
        
        Чем больше тем лучше...Но "малой кровью"..-) ===>>>> — Цивилизатор   (03.04.2008 16:29:28 217.118.66.45, пустое, ссылка)
        
        малой кровью.... Возьмите какой нить подходящий по параметрам блочный код, им при желании даже скорректировать ошибки сможете, а не только обнаружить. — SM   (03.04.2008 16:47:56 80.92.255.53, пустое)
        
        Ответ: Какой посоветуете? Только не шибко жручий выч.ресурсы — Цивилизатор   (03.04.2008 17:48:11 217.118.66.45, пустое)
        
        Я не знаю особенностей ошибок этого случая, по этому конкретного совета давать не буду. А то опять еще нарвусь по незнанию какой-нить тонкости, навроде типа процессора. — SM   (03.04.2008 18:01:30 80.92.255.53, пустое)
        
        Ответ: Хочу универсальный алгоритм для пакетов, Флеши и Епрома (+) — Цивилизатор   (03.04.2008 18:13:11 217.118.66.45, 157 байт)
        
        Универсального и одинаково хорошего на все случаи не бывает (+) — SM   (03.04.2008 18:37:21 80.92.255.53, 727 байт)
        
        ето пусть Доктор учитывает. Пусть тоже потрудится, ему полезно :) — argus98   (03.04.2008 14:18:22 81.22.205.230, пустое)
        
        Боюсь, что трудилка у него отвалится от такой сложной задачи. Иначе бы и вопроса не задавал. — SM   (03.04.2008 14:28:33 80.92.255.53, пустое)
        
        Ну а вдруг?! Вода камень точит.. Глядишь, лет через ХХ-цать человеком станет. — argus98   (03.04.2008 14:37:30 81.22.205.230, пустое)
        
        камень-то точит, а вот оно на ней плавает, сколько не лей - все равно плавает. — SM   (03.04.2008 14:40:37 80.92.255.53, пустое)
        
        Ответ: Злой Вы какой-та.. Сергей Михалыч... Низзя так.. — Цивилизатор   (03.04.2008 16:30:39 217.118.66.45, пустое)
        
        Я не Михалычь. — SM   (03.04.2008 16:42:36 80.92.255.53, пустое)
        
        Ответ: Моисеич?......>)8- ( ) — Цивилизатор   (03.04.2008 18:21:28 217.118.66.32, пустое)
        
        Направление озвучить? — SM   (03.04.2008 18:41:29 80.92.255.53, пустое)
        
        Да, именно так. Что делать - для каждого случая рассчитывать оптимальный код, обнаруживающий (или корректирующий) ошибки. Тупое следование стандартам не всегда лучшее решение. — SM   (03.04.2008 14:02:1 80.92.255.53, пустое)
        
        Пля :-(((.. Вот я попал... Т.е. "малой кровью" не получиться? :-((( — Цивилизатор   (03.04.2008 16:17:32 217.118.66.45, пустое)
        
        Получится. Оптимальный код выбирается расчитывается на PC, а в МК он уже реализуется как правило малой кровью. — SM   (03.04.2008 16:51:30 80.92.255.53, пустое)
        
        И вообще, я уже достаточно рассказал, чтобы самостоятельно понять, куда идти дальше. Если обсуждение в таком стиле пойдет и дальше, я направление озвучу вслух и конкретно. — SM   (03.04.2008 17:04:22 80.92.255.53, пустое)
        
        Ответ: ==========>>>>>>>>>>> — Цивилизатор   (03.04.2008 17:59:59 217.118.66.45, пустое, ссылка)
- Ответ: MD5? В микроконтроллере ATmega8515 4МГц 512 Байт ОЗУ ? — Цивилизатор (03.04.2008 11:47:36 217.118.66.35, пустое)
  - Опять туесосишь? В исходном посте ни слова про ресурсы не было. А я например в TMS320-ом спокойно MD5 считаю не напрягаясь. — SM (03.04.2008 11:52:36 80.92.255.53, пустое)
  - Ответ: Это не единственный случай. Можно вместо нулей (+) — Цивилизатор (03.04.2008 11:49:13 217.118.66.35, 80 байт)
    - можно. И с этим ничего не поделаешь, такова математика, и существует бесконечное число последовательностей, дающий одинаковую CRC. И одинаковую MD5. И одинаковую SHA. Вопрос только в вероятности этой одинаковости. — SM (03.04.2008 11:51:12 80.92.255.53, пустое)
      - Вот, придумал отличный вариант. — Oldring   (03.04.2008 17:15:54 91.76.18.68, 303 байт)
        
        У него найдется такой очень частый случай, когда во всех копиях один и тот же бит испортится. И этот вариант, как все остальные на свете, кроме какого-то, им лично придуманного, не подойдут. Это же доктор! — SM   (03.04.2008 17:34:25 80.92.255.53, пустое)
        
        Да это же целых 20000 битиков должны испортиться - никие CRC и рядом не валялись :) — Oldring   (03.04.2008 17:37:28 91.76.18.68, 65 байт)
        
        А чтобы доктор гарантированно не смог ничего найти - нужно предлагать шифр включенный в режиме хеш-функции. — Oldring   (03.04.2008 17:40:12 91.76.18.68, 78 байт)