Вопросы и свойства циклической проверки избыточности (CRC)?

У меня есть несколько вопросов об алгоритме crc, в данном случае о crc8.

  1. стандарт CRC? Я имею в виду, если я скажу кому-нибудь, что использую crc8 в своем фрейме, должен ли я дать ему свой код crc8 или он может найти его в Интернете, потому что это стандарт?

  2. обратима ли CRC? это означает, что если crc(x)=y я могу найти x, если у меня есть y?

  3. если crc(A)=a и crc(B)=b, могу ли я использовать a и b, чтобы найти crc(AB)?

  4. имеет ли crc какие-либо алгебраические свойства?

  5. Я нашел в сети код crc8 в C , как я могу проверить правильность кода ? Я нашел несколько онлайн-калькуляторов, но ни один из них не соответствует моему коду, почему? Вот сайты, которые я использовал:
    Сайт: 1
    Сайт: 2
    и вот мой код для crc8 в C:

char crc8(char arr[], char arrLen){
    char crc=0;
    char i;
    char shift;
  for (i = 0; i < arrLen; i++){
      crc ^= (arr[i]);
      for (shift = 8; shift > 0; shift--){
          if (crc & 10000000) crc = (crc << 1) ^ 0x131;
          else crc = (crc << 1);
      }
  }
  return crc;
}

c crc algorithm
person user3791563    schedule 01.07.2014    source источник
comment
Почему бы просто не погуглить, например en.wikipedia.org/wiki/Cyclic_redundancy_check.   -  person Ed Heal    schedule 01.07.2014
comment
@EdHeal Да, но я не нашел всех своих вопросов или, может быть, не получил их объяснений.   -  person user3791563    schedule 01.07.2014

Ответы (2)


arrow_upward
4
arrow_downward

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

Ниже приведены простые ответы на некоторые из ваших вопросов.

является стандартом crc? Я имею в виду, если я скажу кому-нибудь, что использую crc8 в своем фрейме, должен ли я дать ему свой код crc8 или он может найти его в Интернете, потому что это стандарт?

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

является ли обратимой CRC? это означает, что если crc(x)=y, могу ли я найти x, если у меня есть y?

No

если crc(A)=a и crc(B)=b , могу ли я использовать a и b, чтобы найти crc(AB) ?

No

имеет ли crc какие-либо алгебраические свойства?

Вы имели в виду ассоциативный, коммутативный и т.д.? Это хэш-функция. То же самое относится и к CRC-8, и к MD5 и т. д. Из Википедии (http://en.wikipedia.org/wiki/Cyclic_redundancy_check#CRCs_and_data_integrity), CRC имеет следующее свойство:

CRC(x^y^z) == crc(x) ^ crc(y) ^ crc(z)

Я нашел в Интернете код crc8 на C, как я могу проверить правильность кода?

Я попытался запустить код, который вы разместили, и другой код crc8, найденный здесь: https://chromium.googlesource.com/chromiumos/platform/vboot_reference/+/d96b25d0c0a739d351b8f09b128782ca12b7b0e1/firmware/lib/crc8.c. Оба, кажется, дают одинаковый результат для одного и того же полинома (0x1310 вместо 0x1070 в связанном коде). Что касается сравнения с результатами сайтов, с которыми вы сравнивали, вы можете рассмотреть возможность настройки части polynomial. Я обновлю здесь, если найду время, чтобы исследовать это позже сегодня.

Обновить

Калькулятор CRC http://depa.usst.edu.cn/chenjq/www2/software/crc/CRC_Javascript/CRCcalculation.htm принимает 8-битный полином и предполагает, что девятый бит всегда установлен. Полином, используемый в вашем опубликованном коде, равен 0x131. Если обнулить девятый бит, то он станет 0x31. Итак, если вы используете 31 в качестве многочлена в калькуляторе CRC, вы получите тот же ответ.

Также сравнивая код, который вы разместили, с алгоритмом CRC, он выглядит нормально.

Надеюсь, поможет :)

person bytefire    schedule 01.07.2014
comment
спасибо за ваш ответ и ваши усилия, я не смог протестировать код, который вы найдете на этом сайте, потому что у меня нет используемых там библиотек. но как возможно, чтобы выход был равен моему, даже если два кода используют два разных многочлена? - person user3791563; 01.07.2014
comment
Чтобы запустить связанный код, #include <stdint.h>. Этот код сдвигает полином влево, а ваш — нет. Я обновлю больше, как только у меня будет время изучить это. - person bytefire; 01.07.2014
comment
Я не получаю такой же вывод, вот код основного int main() { unsigned char a[]={1}; printf("%d\n", crc8(a,1)); printf("%d\n", Crc8(a,1)); return 0; } - person user3791563; 01.07.2014
comment
Вместо этого я бы использовал printf("%x\n", crc8(a,1));. Не уверен, почему он отличается. Можно попробовать запустить их в двух разных программах. Возможно, одна функция изменяет общую переменную. - person bytefire; 01.07.2014
comment
Я разделил их, но всегда получаю разные результаты. - person user3791563; 01.07.2014
comment
@ user3791563 мой плохой. Ты прав. Два выхода разные. И это из-за разных полиномов. Полином, используемый в опубликованном мной коде, фактически равен 0x107 (0x1070 в коде). Результат для этого многочлена правильный. Если мы заменим 0x1070 на 0x1310 (фактически 0x131, который является полиномиальным в вашем опубликованном коде), мы получим тот же ответ. Обновил пост выше. - person bytefire; 01.07.2014
comment
спасибо за обновление об онлайн-калькуляторе, вы разрешили для меня большую загадку :) - person user3791563; 01.07.2014

arrow_upward
2
arrow_downward

Чтобы исправить один из ответов @bytefire:

если crc(A)=a и crc(B)=b , могу ли я использовать a и b, чтобы найти crc(AB) ?

Да, если у вас также есть длина A. Вы можете посмотреть crc32_combine_() в zlib для примера того, как это делается.

См. этот ответ для кода CRC-8 с использованием оптимального полинома.

person Mark Adler    schedule 02.07.2014