caxapa.ru :: Знатоки CRC!

ASDFS, USB-гуру (12.10.2010 22:18, просмотров: 15070)

Знатоки CRC! У меня смутные подозрения что если в сдвиговом регистре и на его входе одинаковое значение - то на выходе будет одна и та же константа независимо от этого значения. То есть смысл деяния таков: я посчитал CRC некоего массива и пришпандорил результат в конец этого массива. При проверке я могу посчитать CRC массива вместе с контрольным полем и на выходе будет одна и та же константа для любых исходных данных. Константа эта зависит лишь от типа полинома. Я брежу или нет?

Ответить

- если обобщить - то любой алгоритм получив на вход массив констант выдаст константу, независимо полином или, например, метроном в алгоритме используется. по поводу CRC - с целочисленным делением с остатком хорошая аналогия - если взять остаток от ыыыы(66 знак., 14.10.2010 18:59, )
  - Это не тот случай обобщения. Мы обсуждаем ситуацию приводящую к одной константе независимо от входных данных. - ФЫВАЫ(14.10.2010 19:11, )
    - Именно тот. CRC есть остаток от деления полинома входной последовательности на образующий полином. - Cepгeй Бopщ(14.10.2010 23:43)
- Недавно натолкнулся на интересные варианты коротких хешей типа CRC - Adler32. У них немного другие свойства. - AlexandrY(13.10.2010 23:53, ссылка)
  - Коллизии ФЫВАЫ(1148 знак., 14.10.2010 12:37, )
    - Рулезная статья по теме c исходниками -> - Evgeny_CD(15.10.2010 00:01, ссылка)
      - Спасибо за ссылку. Очень любопытный сайт. - Vallav(15.10.2010 09:34)
      - К этой статье еще бы таблицу с временем исполнения - цены ей бы не было! - Evgeny_CD(15.10.2010 00:12)
    - +1. Когда народ вначале сделал Stream Control Transmission Protocol, они тоже на Adler запали. А потом им пришлось резко патчить протокол и бежать на CRC-32 --> - Evgeny_CD(14.10.2010 23:54, ссылка, ссылка)
      - Да я потому и припомнил Adler что его поначалу юзали в zlib-е, а потом перестали, отчего старые файлы сжатые zlib не распаковываются в Windows. - AlexandrY(15.10.2010 01:04)
  - судя по статье по ссылке никаких преимуществ над CRC у Адлера практически нет, скорее наоборот - Snaky(14.10.2010 03:13)
- так и есть. удобно когда на выходе получается 0 -- проверять легче. - bialix(13.10.2010 15:41)
- хм blackbit(253 знак., 13.10.2010 09:51)
  - Неправда. Применял такую проверку CRC на практике в загрузчиках. Результат - ненулевая константа. - SciFi(13.10.2010 10:01)
    - ..значит инициализировал 0xFFFF, а не нулем. blackbit(263 знак., 13.10.2010 10:41 - 10:44)
      - "используют дополнение до 1 CRC-аккумулятора прежде чем пропустить контрольный код" - а можно расшифровать? - ASDFS(13.10.2010 16:10)
        
        xor 0xFFFF (для CRC16) - blackbit(13.10.2010 19:32)
        
        На практике можно посчитать контрольную сумму 1 раз и подсмотреть эту константу. Потом с ней и сравнивать. - SciFi(13.10.2010 16:27)
        
        Это понятно. Я хотел выяснить есть ли дополнительные условия при которых этот метод (не)работает. ASDFS(95 знак., 13.10.2010 16:57)
        
        Вообще то достоверность проверки по CRC не такая уж и большая. Она только тем лучше от обычной контрольной суммы по модулю, что полином распределяет ошибку по диапазону чисел равномерно. Dir(295 знак., 13.10.2010 17:26)
        
        Не только тем, "что полином распределяет ошибку по диапазону чисел равномерно". Vallav(397 знак., 14.10.2010 14:42)
        
        Оба не правы. CRC обнаруживает столько ошибок, насколько была рассчитана. blackbit(412 знак., 15.10.2010 01:42)
        
        И что? Речь шла про CRC определенной длины. Vallav(154 знак., 15.10.2010 09:11)
        
        ..где шла речь "про CRC определенной длины"? и какой конкретно длины? - blackbit(15.10.2010 17:54)
        
        Так Вы про CRC с неограниченной длиной? Vallav(85 знак., 15.10.2010 20:07)
        
        ..длина CRC не имеет значения. Важно отношение длины блока к длине CRC. - blackbit(15.10.2010 21:36, ссылка)
        
        Интересно, в чем я неправ? Dir(1053 знак., 15.10.2010 03:57)
        
        CRC в давние времена были в фаворе по другой причине - на рассыпухе контроллер CRC проще, чем Vallav(37 знак., 15.10.2010 09:14)
        
        Примеры есть? Не припомню контроллера CRC на рассыпухе - делали сразу Хэмминга. - blackbit(15.10.2010 21:20)
        
        Как раз для такого случая и применяют инициализацию сдвигового регистра каким-либо значением. Инициализируйте единицами (0xFFFF) и наслаждайтесь изменением значения при задвигании нулей. - teap0t(13.10.2010 20:03)
        
        Да какая разница. При инициализации 0xFFFF задвигания "1" не видно, что равновероятно с "0". Пример был только для того, чтобы наглядно показать , что для разных последовательностей КС (или CRC) нередко одинакова. - Dir(13.10.2010 20:32)
        
        Это вопрос к теме не относящийся. У любого метода есть критерии и границы применимости. ASDFS(69 знак., 13.10.2010 20:43)
        
        С точки зрения теории вероятности (при равновероятном значении всех последовательностей) разницы нет. Другое дело, что ПРАКТИЧЕСКИ все "0" или все "1" встречаются гораздо чаще, чем другие последовательности. Dir(308 знак., 13.10.2010 21:09)
- Есть старенькое руководство по СRC. Ruslan(13.10.2010 08:13)
- И от того, каким значением инициализируется CRC перед рассчётом. - ReAl(12.10.2010 22:50)

Микроконтроллеры