Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: CRC вопрос!
Форум разработчиков электроники ELECTRONIX.ru > Микроконтроллеры (MCs) > AVR
bezobraznic
Необходимо гонять между контроллером и PC через уарт большие пакеты данных. Надо проверять целостность и если что повторять передачу. Кто реализовывал подобные задачи подскажите пожалуйста идею реализации!! Спасибо!!!
rezident
Дык, а в чем собственно вопрос-то? Есть CRC8, CRC16, CRC32, LRC даже. В каждой может быть свой образующий полином, который выбирается, исходя из условий: среды передачи, вероятностей тех или иных ошибок и пр.
Кстати, если вероятность ошибки высокая, то разумнее "гонять" наоборот НЕбольшие пакеты данных. Чтобы в случае ошибки повторять более короткий пакет, повторная передача которого займет меньше времени.
PSP
В общем случае в зависимости от вероятности ошибки и ее характера (например портятся отдельные биты, а не сплошные блоки данных) использование корректирующих кодов может оказаться эффективнее чем просто контроль целостности и перепосылка. Правда если речь идет о метровом кабеле RS232 не в заводском цеху, то скорее всего одиночную ошибку можно ждать неделями.
mdmitry
Посмотрите стандартные протоколы: xmodem, zmodem, WAKE и другие. Возможно, что-то подойдет, а можете и стандартный модефицировать под свою задачу.
rezident
Ну тогда еще один вариант CRC16. С начальным входным значением, чтобы можно было посчитать общую CRC16 блочных данных.
Код
//==============================================//
// Функция подсчета СRC16 по алгоритму          //
//----------------------------------------------//
//аргументы: указатель на буфер,                //
//           размер буфера,                     //
//           стартовое значение СRC16           //
//возвращает:подсчитанное значение СRC16        //
//----------------------------------------------//
//ВНИМАНИЕ! Стартовому значению CRC16 необходимо//
//          присвоить значение 0xFFFF,          //
//          размер массива для подсчета CRC16   //
//          не более 65535 байт                 //
//==============================================//
#ifndef _POLINOME_CRC16_
  #define _POLINOME_CRC16_  0xA001
#endif

unsigned int f_CRC16Calc(unsigned char *buf, unsigned int sizeBuf, unsigned int crc)
{ unsigned int i, j;
  for(i=0;i<sizeBuf;i++)
  { crc=crc^buf[i];
    for (j=0;j<8;j++)
    { if ((crc&0x0001)!=0x0000) crc=(crc>>1)^_POLINOME_CRC16_;
      else crc>>=1;
    }
  }
  return (crc);
}
CD_Eater
Для больших пакетов рулит Adler32 (скорость вычислений на порядок выше CRC). Если Вам 32 бита много, то можно по аналогии со стандартным Adler32 сделать "Adler16".
Коротко: Adler - это Флетчер, но по простому модулю.
Kuzmi4
2 PSP - а про корректирующие коды - можно поподробнее??
bezobraznic
Спасибо за ответы! Последний вопрос!
Я понял так:
Вышепреведённую функцию crc16 необходимо высчитать на передающей стороне.
Затем результат передать вместе с данными.
На принимающей стороне опять считаем crc16 и сравниваем результат с переданным.
В зависимости от результата принимаем решение о повторной передаче.

Подкоректируйте если чё-нить не правильно!!!!
Kuzmi4
2 bezobraznic - правильно..
DiMomite
Цитата
Спасибо за ответы! Последний вопрос!
Я понял так:
Вышепреведённую функцию crc16 необходимо высчитать на передающей стороне.
Затем результат передать вместе с данными.
На принимающей стороне опять считаем crc16 и сравниваем результат с переданным.
В зависимости от результата принимаем решение о повторной передаче.


Еще небольшое уточнение.
Есть 2 варианта определения того, что передача прошла без ошибок: первый описали вы, а второй - CRC считается для всех данных+поле CRC, в этом случае результат должен быть равен нулю при отсутствии ошибок (либо если их больше, чем может обнаружить код). Это никак не влияет на саму идею вычисления CRC, но если вы когда то столкнетесь со вторым вариантом реализации, так что бы это вас не смутило.
sensor_ua
Цитата
второй - CRC считается для всех данных+поле CRC, в этом случае результат должен быть равен нулю при отсутствии ошибок

Как раз это первый и правильный способ, но именно для CRC, так как он когда-то реализовывался аппаратноwink.gif Варианты же образования контрольных сумм с отклонением от этого правила действительно требуют сравнения результатов параллельного подсчёта и переданного значения
bezobraznic
Цитата(DiMomite @ Oct 6 2007, 14:10) *
Еще небольшое уточнение.
Есть 2 варианта определения того, что передача прошла без ошибок: первый описали вы, а второй - CRC считается для всех данных+поле CRC, в этом случае результат должен быть равен нулю при отсутствии ошибок (либо если их больше, чем может обнаружить код). Это никак не влияет на саму идею вычисления CRC, но если вы когда то столкнетесь со вторым вариантом реализации, так что бы это вас не смутило.



Я не понимаю почему црц должно быть равно 0 во втором варианте(данные+поле CRC) поясните если можно!!!

И ещё, В передатчике,если использовать 2 вариант, то я должен сначала посчитать црц по данным,
затем дополнить поле данных результатом црц, и потом опять считать црц !? И куда мне деть результат второго црц?
В приёмнике чё делать?

Распишите плиз 2й вариант а то я запутался!! Спасибо!!
sensor_ua
В передатчике ничего не правим. В приёмнике подсчёт контрольной суммы ведётся не "для всего до контрольной суммы", а на 2 байта (для CRC16) больше - результат вычисления в таком случае должен быть равен нулю если ошибок не было.
PSP
Цитата(Kuzmi4 @ Oct 6 2007, 11:24) *
2 PSP - а про корректирующие коды - можно поподробнее??


В самых общих чертах примерно так. Вычисляется хитрая контрольная сумма по блоку данных и передается вместе с данными. На приемной стороне опять считается контрольная сумма, и при ошибке можно вычислить какие биты искажены и восстановить их. В простейшем случае восстанавливается 1 бит, а большее количество ошибок только обнаруживается. Пример такого кода - ECC используемое в NAND flash, которые могут иметь одиночные сбои. Там на каждую страницу в 512 байт используется 3-х байтовое ECC и есть специальная область данных (spare) для его хранения. Алгоритм с примерами описан в appnote у Samsung. Подобная, но более сложная система, которая восстанавливает больше ошибок используется на всех CD и DVD дисках.
Сергей Борщ
Цитата(bezobraznic @ Oct 6 2007, 15:20) *
Я не понимаю почему црц должно быть равно 0 во втором варианте(данные+поле CRC) поясните если можно!!!
CRC - это остаток от деления массива данных (который берется как очень длинное число) на полином. По аналогии с простым делением - если A/B дает в остатке C, то (A-C)/B дадут в остатке ноль. При выполнении обычного деления используется вычитание делителя из делимого. Деление полиномов аналогично, только используется вычитание по модулю два. Которорое обладает таким свойством, что дает тот же самый результат, что и суммирование по модулю два. Когда мы добавляем рассчитанное CRC к массиву - мы фактически приписываем к делимому N нулей в конец (умножаем его на 2^N) и прибавляем CRC по модулю два к добавленным нулевым битам, или же, что тождественно, вычитаем его по модулю два. Получается, что мы из исходного данного вычли остаток и теперь деление на приемной стороне должно будет дать в остатке (т.е. в результате вычисления CRC) ноль.
Попытался, как смог, объяснить "на пальцах". Более подробно с выкладками у Скляра в "цифровой связи", ну и в других книгах.
AVR
Есть одна интересная страница, которая сгенерирует код для рассчета CRC для требуемого полинома: crctool smile.gif Правда там на verilog генерируется, но не составляет труда переписать на Си.
DiMomite
Позволю себе немного дополнить и уточнить пост Сергея для придания ему математической точности.

Цитата
CRC - это остаток от деления массива данных (который берется как очень длинное число) на полином. По аналогии с простым делением - если A/B дает в остатке C, то (A-C)/B дадут в остатке ноль.


Здесь под А нужно понимать не исходный массив данных как он есть, а массив исходных данных с дописанными к нему в конце нулевыми байтами (для CRC-16 - это 2 байта). Простое деление исходного массива без дополнения его сзади нулями на порождающий полином не есть циклический код.
Во всех готовых реализациях (аппаратных и программных) это "дописывание" происходит само собой.

Это на случай, если кто-то захочет проверить код "на бумажке", а у него не будет сходиться ответ.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.