Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Микроконтроллеры (MCU) и микропроцессоры (MPU) > CRC и LRC - алгоритмы

Автор: bagira 24.12.2003, 17:49

Извините, может быть я спрашиваю очевидные вещи, но подскажите пожалуйста, что такое CRC и LRC алгоритмы? Я только знаю, что это алгоритмы подсчета контрольных сумм при передаче данных. Именно так написано в задании, а литературы нет. Речь идет о MCS-51. Т.е. у меня была сделана программа (пересылающая данные) без этих сумм, и она работала. Теперь человек, разрабатывающий контроллер-получатель моих данных (условно), требует включить их (либо CRC, либо LRC) в мою программу, а я не могу нигде прочитать, что это такое. Задание было дано сегодня вечером, сейчас еще в Интернете поищу...
Помогите, пожалуйста, разобраться. Заранее благодарна.

Автор: бывший 24.12.2003, 18:27

Код

            
                       //    0     1     2     3     4     5     6     7
                       //    8     9     A     B     C     D     E     F
char _crc [] = {  0x00, 0x31, 0x62, 0x53, 0xC4, 0xF5, 0xA6, 0x97,   //00
                          0xB9, 0x88, 0xDB, 0xEA, 0x7D, 0x4C, 0x1F, 0x2E,   //08
                          0x43, 0x72, 0x21, 0x10, 0x87, 0xB6, 0xE5, 0xD4,   //10
                          0xFA, 0xCB, 0x98, 0xA9, 0x3E, 0x0F, 0x5C, 0x6D,   //18
                          0x86, 0xB7, 0xE4, 0xD5, 0x42, 0x73, 0x20, 0x11,   //20
                          0x3F, 0x0E, 0x5D, 0x6C, 0xFB, 0xCA, 0x99, 0xA8,   //28
                          0xC5, 0xF4, 0xA7, 0x96, 0x01, 0x30, 0x63, 0x52,   //30
                          0x7C, 0x4D, 0x1E, 0x2F, 0xB8, 0x89, 0xDA, 0xEB,   //38
                          0x3D, 0x0C, 0x5F, 0x6E, 0xF9, 0xC8, 0x9B, 0xAA,   //40
                          0x84, 0xB5, 0xE6, 0xD7, 0x40, 0x71, 0x22, 0x13,   //48
                          0x7E, 0x4F, 0x1C, 0x2D, 0xBA, 0x8B, 0xD8, 0xE9,   //50
                          0xC7, 0xF6, 0xA5, 0x94, 0x03, 0x32, 0x61, 0x50,   //58
                          0xBB, 0x8A, 0xD9, 0xE8, 0x7F, 0x4E, 0x1D, 0x2C,   //60
                          0x02, 0x33, 0x60, 0x51, 0xC6, 0xF7, 0xA4, 0x95,   //68
                          0xF8, 0xC9, 0x9A, 0xAB, 0x3C, 0x0D, 0x5E, 0x6F,   //70
                          0x41, 0x70, 0x23, 0x12, 0x85, 0xB4, 0xE7, 0xD6,   //78
                          0x7A, 0x4B, 0x18, 0x29, 0xBE, 0x8F, 0xDC, 0xED,   //80
                          0xC3, 0xF2, 0xA1, 0x90, 0x07, 0x36, 0x65, 0x54,   //88
                          0x39, 0x08, 0x5B, 0x6A, 0xFD, 0xCC, 0x9F, 0xAE,   //90
                          0x80, 0xB1, 0xE2, 0xD3, 0x44, 0x75, 0x26, 0x17,   //98
                          0xFC, 0xCD, 0x9E, 0xAF, 0x38, 0x09, 0x5A, 0x6B,   //A0
                          0x45, 0x74, 0x27, 0x16, 0x81, 0xB0, 0xE3, 0xD2,   //A8
                          0xBF, 0x8E, 0xDD, 0xEC, 0x7B, 0x4A, 0x19, 0x28,   //B0
                          0x06, 0x37, 0x64, 0x55, 0xC2, 0xF3, 0xA0, 0x91,   //B8
                          0x47, 0x76, 0x25, 0x14, 0x83, 0xB2, 0xE1, 0xD0,   //C0
                          0xFE, 0xCF, 0x9C, 0xAD, 0x3A, 0x0B, 0x58, 0x69,   //C8
                          0x04, 0x35, 0x66, 0x57, 0xC0, 0xF1, 0xA2, 0x93,   //D0
                          0xBD, 0x8C, 0xDF, 0xEE, 0x79, 0x48, 0x1B, 0x2A,   //D8
                          0xC1, 0xF0, 0xA3, 0x92, 0x05, 0x34, 0x67, 0x56,   //E0
                          0x78, 0x49, 0x1A, 0x2B, 0xBC, 0x8D, 0xDE, 0xEF,   //E8
                          0x82, 0xB3, 0xE0, 0xD1, 0x46, 0x77, 0x24, 0x15,   //F0
                          0x3B, 0x0A, 0x59, 0x68, 0xFF, 0xCE, 0x9D, 0xAC }; //F8

static inline byte crc8 ( byte i ) {

  return pgm_read_byte ( &_crc[i] );
}

        d = read();  // MSB
        crc = crc8 ( crc ^ d );
        d = read();  // LSB
        crc = crc8 ( crc ^ d );
        d = rеаd();
        if ( crc != d ) {} // here we have bad crc!

CRC - контрольная сумма.
Пример читает слово (2 байта и 3й байт как контрольный)

Автор: bagira 24.12.2003, 19:54

Спасибо! А как вычисляется LRC?

Автор: бывший 24.12.2003, 20:07

http://www.usefulcontent.org/adlocum/dest/foldoc/foldoc.cgi?Longitudinal+Redundancy+Check

Автор: bagira 24.12.2003, 20:21

Благодарю!

Автор: zemfir 24.12.2003, 21:04

на этом сайте лежит хороший перевод описания црц зачем это нужно и т.п., имеет смысл прочитать.
http://bialix.narod.ru/

алгоритмов вычисления црц великое множество, довольно распространённый: сложения защищаемых байт по модулю 256(контрольная сумма), сам crc это циклический проверочный код.
Как я понимаю разработка велась для какого-то определённого контроллера, все производители выпускают своих процов примеры применения, очень часто в них есть и алгоритм какой-либо црц для конкретного проца на конкретном языке.

Автор: бывший 24.12.2003, 21:29

Подсчет контрольной суммы может быть осуществлен произвольным образом, а вот CRC (cyclic redundancy check) это определенный и подробно описанный алгоритм, неподлежащий переделке и независящий от используемого железа. Потому, я и привел таблицу для CRC8.
http://www2.rad.com/networks/1994/err_con/crc.htm

Автор: bagira 24.12.2003, 21:41

zemfir, спасибо, классная статья!
Проблема стала понемногу проясняться.

Автор: zemfir 24.12.2003, 21:44

Цитата(bagira @ 24.12.2003, 21:41)

zemfir, спасибо, классная статья!
Проблема стала понемногу проясняться.

Вот когда она прояснится, будет совсем хорошо

Автор: zemfir 24.12.2003, 21:59

Цитата

Подсчет контрольной суммы может быть осуществлен произвольным образом, а вот CRC (cyclic redundancy

Посмотрите ссылку которую я дал для багиры.

Автор: бывший 24.12.2003, 23:11

Прочитал.
Рекомендую. Код и таблица были приведены.

Цитата

Theory
CRC stands for Cyclic Redundancy Check. It is one of the most effective error detection schemes and requires a minimal
amount of hardware.
For in-depth information on CRC we recommend the comprehensive: A painless guide to CRC error detection algorithms
available at: http://www.repairfaq.org/filipg/LINK/F_crc_v3.html
The types of errors that are detectable with polynomial x8+ x5+ x4 are:
1. Any odd number of errors anywhere within the transmission.
2. All double-bit errors anywhere within the transmission.
3. Any cluster of errors that can be contained within an 8-bit window (1-8 bits incorrect).
4. Most larger clusters of errors.

Автор: zemfir 24.12.2003, 23:52

црц бывают разные в разных приложениях, некоторые из них стандартизованы, как указано в вашей ссылке.
Например, для 16ти бытовых црц есть X25, CRC16, они оба являются стандартными, но они не одно и тоже, и они дадут разный результат.
Как замечено в статье разные алгоритмы служат для разных целей.

Я не хочу продолжать этот, на мой взгляд, бессмысленный спор

Если Вы сочтёте, что я в очередной раз не прав, уж очень Вы уверенно говорите

, то я посмотрю литературу и уточню что именно на самом деле имели ввиду Вы, и что я, возможно мы говорим про что-то одно.

Автор: zemfir 24.12.2003, 23:53

Цитата(zemfir @ 24.12.2003, 23:52)

Я не хочу продолжать этот, на мой взгляд, бессмысленный спор

Если Вы сочтёте, что я в очередной раз не прав, уж очень Вы уверенно говорите

посмотреть смогу только на выходных.

Автор: бывший 25.12.2003, 03:39

zemfir,
А вот спора не было - было обсуждение и это нормально. Я привел ссылку, таблицу и код для микроконтроллера, где решающими факторами являются

Цитата

a minimal amount of hardware.

и не более софта. Такие условия я прочитал между строк Багиры. Может это и не оптимальный вариант. Чтож, каждый выберет то, что сочтет нужным.
Успехов!

Автор: Guest 27.12.2003, 02:12

Автор: bagira 18.1.2004, 22:07

Снова возвращаюсь к этой давней теме.

Может быть кто-нибудь подскажет, как рассчитывается LRC? В приведенной ссылке не все понятно. Спасибо.

Автор: Unregistered 23.1.2004, 00:49

Longitudinal Redundancy Checking (LRC) more commonly called a checksum, is a character that is the sum of the binary values for each bit position for all transmitted bytes. LRC requires the addition of a single byte (one character) after each string of transmitted bytes (characters).