Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Алгоритм CRC16
Форум разработчиков электроники ELECTRONIX.ru > Сайт и форум > В помощь начинающему > Программирование
Страницы: 1, 2
athlon64
Устройство на sam7x должно обмениваться по uart пакетами длинной 76 байт + 2 байта CRC16 с программой на компьютере.
Исходника программы компа нет, но есть исходник (в icc) предыдущей версии рабочего устройства (правильно рассчитываеющего CRC и успешно обменивающегося с программой), из которого был взят фрагмент рассчёта CRC. По какой то причине CRC рассчитывается неверно.

Фрагмент для IAR:
Код
// пакет лежит в uart1_buffer
// len - длина пакета, по которому считается CRC (76 байт)
void CRC16(unsigned int len)
{   unsigned char i;
    unsigned int k;
    unsigned int CRC;

    CRC=k=0;
    while(k<len){
        CRC=CRC^((unsigned int)uart1_buffer[k++]<<8);
        i=8;
        do{
            if(CRC & 0x8000) CRC=(CRC<<1)^0x1021;
            else CRC=CRC<<1;
        } while(--i);
    }
// дописываем в конец буфера CRC16
    uart1_buffer[76]=CRC & 0xff;
    uart1_buffer[77]=(CRC>>8) & 0xff;
}


Для пакета
Код
0A 90 00 00 00 00 00 00 00 00 4F 33 40 40 05 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00

CRC16 должна быть равна A1 01, а рассчитывается 0B D1, перепробовал ещё кучу стандартных алгоритмов, все рассчитывают новые CRC, но ни одна не посчитала A1 01. Голову сломал на этом затыке. Буду благодарен за любые мысли по проблеме
AHTOXA
Видимо то устройство, что работало, было 16-битное? smile.gif
Попробуйте заменить unsigned int на unsigned short.
demiurg_spb
Код
//==============================================================
static uint16_t crc_xmodem_update(uint16_t crc, uint8_t data)
{
    crc = crc ^ ((uint16_t)data << 8);

    for (int i=0; i<8; ++i)
    {
        if (crc & 0x8000) crc = (crc << 1) ^ 0x1021;
        else              crc <<= 1;
    }

    return (crc);
}
//==============================================================
uint16_t crc_xmodem(uint8_t *p, uint16_t len)
{
    uint16_t crc = 0;

    while (len--)
    {
        crc = crc_xmodem_update(crc, *p++);
    }

    return (crc);
}
//==============================================================
static uint16_t crc16_update(uint16_t crc, uint8_t data)
{
    crc ^= data;

    for (int i=0; i<8; ++i)
    {
        if (crc & 1)  crc = (crc >> 1) ^ 0xA001;
        else          crc = (crc >> 1);
    }

    return (crc);
}
//==============================================================
uint16_t crc16(uint8_t *p, uint16_t len)
{
    uint16_t crc = 0xffff;

    while (len--)
    {
        crc = crc16_update(crc, *p++);
    }

    return (crc);
}
Привыкайте писать исходники структурировано и прозрачно....
baralgin
Если перед расчётом CRC проинициализировать 0x6DA5 (вместо 0), то получится как-раз "A1 01" . Просто брутфорс smile.gif . Исходник один в один скопировали?
zltigo
Цитата(AHTOXA @ Apr 10 2010, 10:24) *
Видимо то устройство, что работало, было 16-битное? smile.gif

Не видимо, а именно так. Только не устройство, а int был 16 бит. Ну а у писателей с писательством было туго, вот и напхали интов, где ни поподя sad.gif.
Цитата(demiurg_spb @ Apr 10 2010, 10:28) *
Привыкайте...

Бездумная декомпозиция исходников не поможет. Ну и в Ваших образцах стиля есть еще и проблема обратная использованию int, где попало - неиспользование int, вот и заставляете, например, 32 битовик работать с 16бит переменными без всякой на то надобности sad.gif.
Код
    for (int i=0; i<8; ++i)

Тут восьмибитовик будет маяться с 16 битами у i.
Код
uint16_t crc16(uint8_t *p, uint16_t len)

А тут 32битовик с теми-же 16 битами у len.
athlon64
Цитата(AHTOXA @ Apr 10 2010, 14:24) *
Видимо то устройство, что работало, было 16-битное? smile.gif
Попробуйте заменить unsigned int на unsigned short.

Устройство было на меге2561 smile.gif

Цитата(baralgin @ Apr 10 2010, 14:40) *
Если перед расчётом CRC проинициализировать 0x6DA5 (вместо 0), то получится как-раз "A1 01" . Просто брутфорс smile.gif . Исходник один в один скопировали?

да, брал исходник как есть

Всё разобрался, рядом с этой функцией лежала такая же с постфиксом New в имени smile.gif, в которой алгоритм гораздо проще, опробовал - считает правильно:
Код
void SumCRCNew(unsigned int len)
{   unsigned char i;
    unsigned int CRC;

    CRC=0;
    for(i=0;i<76;i++) CRC+=uart1_buffer[i];
    uart1_buffer[76]=CRC & 0xff;
    uart1_buffer[77]=(CRC>>8) & 0xff;
}

Видимо для обмена по uart прошлым разработчикам пришлось упростить контроль целостности пакета, а я эту функцию проморгал smile.gif
Всем отписавшимся огромное спасибо smile.gif
demiurg_spb
zltigo, нет предела совершенству, можно и так:
Код
uint16_t crc16(uint8_t *p, size_t len)

А тут
Код
for (int i=0; i<8; ++i)
никто маяться не будет, т.к. индекс не используется в теле цикла и оптимизатор всё подчиститsmile.gif
ASN
athlon64
Видимо, это стандартный CRC16 для обмена по стыку IRDA. В Linux есть исходники расчёта CRC на С.Считается табличным методом.
Замена на сложение принципиально ухудшает обнаруживающую ошибки способность.
zltigo
Цитата(demiurg_spb @ Apr 10 2010, 11:52) *
zltigo, нет предела совершенству, можно и так:
Код
uint16_t crc16(uint8_t *p, size_t len)

Слишком правильно smile.gif. Если Вы обладаете некими дополнительными знаниями о размерностях массивов, то можно дать подсказку и облегчить жизнь 8 и 16 битовикам.
Цитата
и оптимизатор всё подчиститsmile.gif

Или да, или нет. А дабы всегда было да - int_fast8_t
defunct
Цитата(demiurg_spb @ Apr 10 2010, 11:28) *
Код
if (crc & 0x8000) crc = (crc << 1) ^ 0x1021;
else              crc <<= 1;
Привыкайте писать исходники структурировано и прозрачно....

И это Вы назваете "прозрачно"?

Еще б вот такое назвали "прозрачно":
Код
if (crc & 1)  crc = (crc >> 1) ^ 0xA001; else      crc = (crc >> 1);
demiurg_spb
Цитата(defunct @ Apr 11 2010, 03:22) *
И это Вы назваете "прозрачно"?
Да. Называю. Приведите Вашу альтернативу. И укажите, что конкретно Вам не понравилось.

Цитата(defunct @ Apr 11 2010, 03:22) *
Еще б вот такое назвали...
Но ведь это Ваш пример а не мой...
vallav
Цитата(ASN @ Apr 10 2010, 16:22) *
athlon64
Видимо, это стандартный CRC16 для обмена по стыку IRDA. В Linux есть исходники расчёта CRC на С.Считается табличным методом.
Замена на сложение принципиально ухудшает обнаруживающую ошибки способность.


Всегда интересовало - почему "Замена на сложение принципиально ухудшает обнаруживающую ошибки способность"?
Одиночные ошибки - одинаково. Обнаруживаются всегда.
Двойные - от статистики зависит. Если они часто в одном разряде, CRC лучше, если они независимы, сложение лучше.
ASN
vallav
Теорию не помню.
По опыту. Работаем в очень сложной помеховой обстановке. Сложение ошибок не обнаруживало, CRC - обнаруживало.
vallav
Цитата(ASN @ Apr 13 2010, 20:43) *
vallav
Теорию не помню.
По опыту. Работаем в очень сложной помеховой обстановке. Сложение ошибок не обнаруживало, CRC - обнаруживало.


Не очень понятно. Может - сложение иногда многкратных ошибок не обнаруживало ( пропускало пакет с ошибками ).
CRC пропускало пакет с ошибками в несколько раз реже.
Такое может быть, если многократные ошибки сильно и специфически коррелированы.

А вот чтобы - сложение всех ошибок не обнаруживало а CRC все ошибки обнаруживало - такое вряд ли.
demiurg_spb
Цитата(vallav @ Apr 13 2010, 21:16) *
Не очень понятно...

crcguide.pdf
defunct
Цитата(demiurg_spb @ Apr 13 2010, 10:02) *
Приведите Вашу альтернативу. И укажите, что конкретно Вам не понравилось.

Не понравилось то, что в одной строке и условие и действие. Читать - не наглядно, править неудобно (например при правке условия съедет форматирование), а отлаживать - совсем никак (ни printf не вставить, ни точку останова не поставить).

Цитата(demiurg_spb @ Apr 13 2010, 10:02) *
Но ведь это Ваш пример а не мой...

Сходство в том, что навалено в одну строку много несвязанных действий.
Так наглядней видно насколько НЕпрозрачным при этом становится код.
demiurg_spb
Цитата(defunct @ Apr 13 2010, 23:31) *
Не понравилось то, что в одной строке и условие и действие. Читать - не наглядно, править неудобно (например при правке условия съедет форматирование), а отлаживать - совсем никак (ни printf не вставить, ни точку останова не поставить).
С этим можно согласится и я очень часто выношу тело условия в отдельный блок со скобками, но когда есть нечто схожее в ветвях условий (например присвоение одной и той же переменной (crc в данном случае) значения и после if, и после else) и само тело мизерно, то я всегда предпочитаю не раздувать строки. Этот случай типичный, т.к. мизерное тело условия и отлаживать и править не надо. Всё дело вкуса и привычки. А аргументацию всегда найти несложно.
defunct
Цитата(demiurg_spb @ Apr 13 2010, 22:43) *
то я всегда предпочитаю не раздувать строки.

По крайней мере можно так:
Код
if (crc & 1)  
    crc = (crc >> 1) ^ 0xA001;
else
    crc = (crc >> 1);


printf все еще поставить нельзя, но все остальное мной перечисленное - убирается. в т.ч. не придется изначально вручную с помощью пробелов форматировать строку с else.
vallav
Цитата(demiurg_spb @ Apr 13 2010, 23:23) *



Вы к чему эту ссылку привели?
Там есть - как считать CRC, но там нет - чем CRC лучше простой суммы с той же разрядностью.
Кроме одного случая - в случае, когда двойные ошибки в одном разряде, CRC лучше.
А разве с этим кто либо спорил?
mdmitry
О CRC
Считая CRC верным можно пытаться восстановить данные, по простой сумме это делать бессмысленно. Далее можно смотреть кодирование/декодирование.
IMHO, CRC это кодирование, но редко делается декодирование с исправлением ошибок.
vallav
Цитата(mdmitry @ Apr 14 2010, 15:49) *
О CRC
Считая CRC верным можно пытаться восстановить данные, по простой сумме это делать бессмысленно. Далее можно смотреть кодирование/декодирование.
IMHO, CRC это кодирование, но редко делается декодирование с исправлением ошибок.


Как это?
При простой сумме, если ошибка одиночная - неизвестно в каком слове ошибка, но хоть известно, в каком разряде.
При CRC не известно ни в каком слове, ни в каком разряде.
CRC лучше простой суммы на маленьких блоках - при правильном перемешивании можно отловить больше двойных ошибок.
Но вот какое из перемешиваний - правильное?
Да и двойная ошибка на маленьком блоке - явление редкое.
Обычно или одиночные ошибки или сразу много.
А тут, что CRC, что простая сумма - примерно одинаковы.
Только простая сумма считается несравненно проще.

Кодирование и декодирование с исправлением ошибок делается довольно часто - например, все CD-ROM работают только благодаря
этому. Редко можно найти CD-диск, у которого нет хотя бы десятка исправленных C1 ошибок при чтении.
Обычно же их на диск несколько десятков тысяч.
demiurg_spb
Цитата(vallav @ Apr 14 2010, 14:28) *
Там есть - как считать CRC, но там нет - чем CRC лучше простой суммы с той же разрядностью.
Вы что смеётесь? Вероятность пропуска ошибки CRC16 1 к 2^16, CRC32 1 к 2^32, а для простой суммы на ПОРЯДКИ больше!!!
Вы что ещё до сих пор верите в благотворительность? То что просто заXORить массив намного менее затратно чем посчитать CRC я не спорю, но что-то мне подсказывает, что и вероятность пропуска ошибки примерно (прюс-минус трамвайная остановка, конечно)smile.gif во столько же раз больше.
За всё надо платить - закон сохранения энергии, однако!


Цитата(defunct @ Apr 14 2010, 02:19) *
По крайней мере можно так:
Код
if (crc & 1)  
    crc = (crc >> 1) ^ 0xA001;
else
    crc = (crc >> 1);
Не, не моё это:-) Я либо в строку форматирую, либо уж по полной программе со скобочками.
К полумерам не привык! Два по сто в одной посуде!:)
vallav
Цитата(demiurg_spb @ Apr 14 2010, 23:20) *
Вы что смеётесь? Вероятность пропуска ошибки CRC16 1 к 2^16, CRC32 1 к 2^32, а для простой суммы на ПОРЯДКИ больше!!!
Вы что ещё до сих пор верите в благотворительность? То что просто заXORить массив намного менее затратно чем посчитать CRC я не спорю, но что-то мне подсказывает, что и вероятность пропуска ошибки примерно (прюс-минус трамвайная остановка, конечно)smile.gif во столько же раз больше.
За всё надо платить - закон сохранения энергии, однако!


Вы полагаете, это аргумент - все так делают, поэтому так делать - правильно?

Закон сохранения энергия вроде не гласит - чем больше энергии затрачено, тем лучше вещь получается...

Вероятность пропуска ошибки CRC16 1 к 2^16, CRC32 1 к 2^32 - знаете, как считается?
Всего разных значений у 16 битного числа 2^16, если ошибка равновероятно порождает одно из значений, то вероятность, что она
породит нужное, равна 1 к 2^16.
Это справедливо для многобитной ошибки ( например, от мощной импульсной помехи ), но справедливо как для CRC, так и для прямой суммы.

Исторически CRC появилась по простой причине - в механических телетайпах основной ошибкой были сбои в одном из реле, что порождало
многократные ошибки в одном из разрядов. СRC тут намного лучше прямой суммы.
Но времена те ушли, а CRC осталось...

Кстати, прямая сумма чуть лучше побитового XOR - пропускает в два раза меньше двойных ошибок в одном разряде.
Палыч
Цитата(vallav @ Apr 15 2010, 08:25) *
Всего разных значений у 16 битного числа 2^16, если ошибка равновероятно порождает одно из значений, то вероятность, что она
породит нужное, равна 1 к 2^16.
Это справедливо для многобитной ошибки ( например, от мощной импульсной помехи ), но справедливо как для CRC, так и для прямой суммы.

Забыли добавить, что для простой суммы равновероятность пораждения одного из значений CRC имеет место при очень больших размерах блока
vallav
Цитата(Палыч @ Apr 15 2010, 10:26) *
Забыли добавить, что для простой суммы равновероятность пораждения одного из значений CRC имеет место при очень больших размерах блока


Вы хотели сказать, при размерах поражения порядка длины контрольного слова?
То есть когда поражено несколько бит?

Повторюсь - CRC лучше для двойных регулярных ошибок ( когда они в одном разряде ).
В остальных случаях - надо специально разбираться.
Палыч
Цитата(vallav @ Apr 15 2010, 09:37) *
Повторюсь - CRC лучше для двойных регулярных ошибок ( когда они в одном разряде ).
Интуитивно понятно, и - спору нет.
Цитата(vallav @ Apr 15 2010, 09:37) *
В остальных случаях - надо специально разбираться.
При длине блока даже в 256 байт простая сумма будет менее 2^16. Даже при бОльшей длине блока не будет выполняться равновероятность пораждения одного из значений CRC (ситуацию нЕсколько спасёт циклическая сумма). Для суммы: только при очень большой длине блока (строго говоря - бесконечной) это условие выполнится.
vallav
Цитата(Палыч @ Apr 15 2010, 11:12) *
Интуитивно понятно, и - спору нет.
При длине блока даже в 256 байт простая сумма будет менее 2^16. Даже при бОльшей длине блока не будет выполняться равновероятность пораждения одного из значений CRC (ситуацию нЕсколько спасёт циклическая сумма). Для суммы: только при очень большой длине блока (строго говоря - бесконечной) это условие выполнится.


При длине блока в 4 байта простая сумма может быть больше, чем 2^16.
Или Вы хотите суммировать байты для получения 16 разрядной контрольной суммы?
Какой смысл - складывать в старший байт переносы?
Вроде при этом надо суммировать 16 разрядные слова.

Кстати, простая сумма не пропустит ни одного едеичного поражения длиной менее 17 бит.
CRC может пропустить ( от конкретного способа перемешивания бит зависит ).
Палыч
Цитата(vallav @ Apr 15 2010, 10:34) *
Или Вы хотите суммировать байты для получения 16 разрядной контрольной суммы?
Извините, но Вы так и делаете: получаете сумму значений 76 байт, а не 38 слов (см. функцию void SumCRCNew(unsigned int len) ).

P.S.Поправка: делает это athlon64, но Вы его решения защищаете
vallav
Цитата(Палыч @ Apr 15 2010, 12:19) *
Извините, но Вы так и делаете: получаете сумму значений 76 байт, а не 38 слов (см. функцию void SumCRCNew(unsigned int len) ).

P.S.Поправка: делает это athlon64, но Вы его решения защищаете


С чего Вы взяли, что я настаиваю именно на таком вычислении контрольной суммы?
Я просто спросил - почему CRC лучше прямой суммы.
Вы согласны, что посчитать 16 битную сумму столь же просто, как и 8 битную?
И намного проще и быстрее, чем правильное 16 битное CRC?

Так что скажите для случая 16 битной суммы?
Палыч
Цитата(vallav @ Apr 15 2010, 12:49) *
Вы согласны, что посчитать 16 битную сумму столь же просто, как и 8 битную?
И намного проще и быстрее, чем правильное 16 битное CRC?

Конечно - проще!

Цитата(vallav @ Apr 15 2010, 12:49) *
Я просто спросил - почему CRC лучше прямой суммы... Так что скажите для случая 16 битной суммы?

Потому, что при случайных с равномерным распределением данных (общий случай) распределение значений простой суммы далека от равномерного (P.S. при длине блока данных больше 6 можно считать, что имеем близкий к нормальному закон распределения), особенно при "малых" значениях длины блока данных. В CRC с распределением значений - тоже не всё гладко, но гораздо лучше, чем у суммы.
ASN
vallav
А вот с тем, что посчитать 16 битную сумму намного проще и быстрее, чем правильное 16 битное CRC несогласен.
На аппаратной логике практически любая CRC считается (и проверяется) "влёт". Не факт, что 16 битное сложение (и выше) будет легче.
Для быстрого расчёта на ЭВМ есть эффективные табличные методы вообще без арифметических операций (кроме XOR).
Палыч
Цитата(ASN @ Apr 15 2010, 13:22) *
А вот с тем, что посчитать 16 битную сумму намного проще и быстрее, чем правильное 16 битное CRC несогласен.

Действительно - есть методы ускоряющие расчет CRC... Но, имхо, скорость их работы не превысит скорости выполнения операции типа: Sum+=Data[i];
Впрочем, могу изменить своё мнение, если Вы приведете исходный текст и временные характеристики программ подсчета CRC, и программы подсчета простой суммы.
vallav
Цитата(ASN @ Apr 15 2010, 14:22) *
vallav
А вот с тем, что посчитать 16 битную сумму намного проще и быстрее, чем правильное 16 битное CRC несогласен.
На аппаратной логике практически любая CRC считается (и проверяется) "влёт". Не факт, что 16 битное сложение (и выше) будет легче.
Для быстрого расчёта на ЭВМ есть эффективные табличные методы вообще без арифметических операций (кроме XOR).


На аппаратной логике и БПФ делается влет.
ASN
Палыч
Пример на аппаратной логике расчёта обсуждаемой CRC16 для однобитного входного потока:
Код
function nextCRC16
    (Data: std_logic;
       crc:  std_logic_vector(15 downto 0))
return std_logic_vector is

    variable d:      std_logic_vector(0 downto 0);
    variable c:      std_logic_vector(15 downto 0);
    variable newcrc: std_logic_vector(15 downto 0);

  begin
    d(0) := Data;
    c      := crc;
    newcrc(0) := d(0) xor c(15);
    newcrc(1) := c(0);
    newcrc(2) := c(1);
    newcrc(3) := c(2);
    newcrc(4) := c(3);
    newcrc(5) := d(0) xor c(4) xor c(15);
    newcrc(6) := c(5);
    newcrc(7) := c(6);
    newcrc(8) := c(7);
    newcrc(9) := c(8);
    newcrc(10) := c(9);
    newcrc(11) := c(10);
    newcrc(12) := d(0) xor c(11) xor c(15);
    newcrc(13) := c(12);
    newcrc(14) := c(13);
    newcrc(15) := c(14);
    return newcrc;
  end nextCRC16;

Требуется 16 триггеров. Не больше чем для простой суммы.

Расчёт для 8-ми битной ЭВМ табличным способом:
Код
void set_fcs(uint16 fcs_init, uint8 *buff, uint16 len)
{
while(len--)
     fcs_init = (fcs_init >> 8) ^ fcs_table[(fcs_init ^ *buff++)];
fcs_init ^= 0xFFFF;
*buff++ = (uint8)fcs_init;
*buff     = (uint8)(fcs_init>>8);}

Сложение 8 битного числа с 16 битным Sum+=*Data++ чуть быстрее.
Именно поэтому и не согласен, что посчитать 16 битную сумму намного проще и быстрее, чем правильное 16 битное CRC.
Поскольку особого преимущества нет, IMHO, лучше использовать проверенные алгоритмы.
VslavX
Цитата(vallav @ Apr 15 2010, 12:49) *
С чего Вы взяли, что я настаиваю именно на таком вычислении контрольной суммы?
Я просто спросил - почему CRC лучше прямой суммы.
...
Так что скажите для случая 16 битной суммы?

Есть такое понятие - кодовое расстояние. Это число разрядов в двух битовых последовательностях которые отличается. Если у Вас в принимаемой последовательности сбойнул один бит, то кодовое расстояние между правильной и ошибочно принятой последовательности равно 1, если два бита - то 2 и т.д. Так вот, математически доказано, что CRC (которое является фактически делением на определенные полиномы) покрывает максимально возможное кодовое расстояние ошибок для данной длины корректирующего кода . То есть, обнаруживает максимально возможно количество единичных искажений. Если принято какое-то значение CRC, то для получения того же значения CRC нужно исказить некоторое количество бит (ЕМНИП, 14 битов минимум для приведенной CRC-16). Если же у Вас просто сумма, то достаточно исказить всего два бита (например, инвертировать младшие биты в байтах в которых эти биты несовпадают) и ошибка уже не будет обнаружена. Вот поэтому CRC намного лучше простой суммы.
Палыч
Цитата(VslavX @ Apr 15 2010, 16:49) *
для получения того же значения CRC нужно исказить некоторое количество бит (ЕМНИП, 14 битов минимум для приведенной CRC-16)
Имхо, Вам память - изменяет. Насколько помню: кодовое расстояние CRC уменьшается с увеличением длины блока данных, и для приведенной CRC16-CCITT при длине блока данных 256 байт оно равно 3.
VslavX
Цитата(Палыч @ Apr 15 2010, 17:21) *
Имхо, Вам память - изменяет. Насколько помню: кодовое расстояние CRC уменьшается с увеличением длины блока данных, и для приведенной CRC16-CCITT при длине блока данных 256 байт оно равно 3.

Очень может быть - я лет 10 назад про выбор CRC читал, возможно, цифра была приведена для более коротких блоков, и, может быть, вообще не для полинома выбранного CCITT (он вроде как не самый удачный). Но то что CRC обеспечивает максимально возможное для линейных кодов минимальное кодовое расстояние - это вроде бы на сегодня так.
vallav
Цитата(VslavX @ Apr 15 2010, 17:49) *
Есть такое понятие - кодовое расстояние. Это число разрядов в двух битовых последовательностях которые отличается. Если у Вас в принимаемой последовательности сбойнул один бит, то кодовое расстояние между правильной и ошибочно принятой последовательности равно 1, если два бита - то 2 и т.д. Так вот, математически доказано, что CRC (которое является фактически делением на определенные полиномы) покрывает максимально возможное кодовое расстояние ошибок для данной длины корректирующего кода . То есть, обнаруживает максимально возможно количество единичных искажений. Если принято какое-то значение CRC, то для получения того же значения CRC нужно исказить некоторое количество бит (ЕМНИП, 14 битов минимум для приведенной CRC-16). Если же у Вас просто сумма, то достаточно исказить всего два бита (например, инвертировать младшие биты в байтах в которых эти биты несовпадают) и ошибка уже не будет обнаружена. Вот поэтому CRC намного лучше простой суммы.


Одиночные ошибки обоими способами обнаруживаются все.
Для двойных - зависит от статистики ошибок. Вполне допускаю, что есть такие CRC, которые обнаруживают их все.
Но ничто не дается даром. Эти CRC будут проигрывать простой сумме в обнаружении достаточно типичных ошибок, вызванных помехой -
одиночных многобитных сбоев. Прямая сумма будет обнаруживать все такие сбои длиной меньше или равной длине контрольного слова.
CRC, заточенная на двойные разнесенные ошибки, часть из таких сбоев не заметит.
И больше похоже на правду, что для такого CRC число это не 14 а 3.
Так что, что лучше - зависит от того - а какие именно ошибки нужно обнаруживать.

Цитата(ASN @ Apr 15 2010, 15:48) *
Палыч
Пример на аппаратной логике расчёта обсуждаемой CRC16 для однобитного входного потока:
Требуется 16 триггеров. Не больше чем для простой суммы.


А разве ктот то утверждал, что на плиске алгоритм CRC нереализуем?

Цитата(ASN @ Apr 15 2010, 15:48) *
Расчёт для 8-ми битной ЭВМ табличным способом:
Сложение 8 битного числа с 16 битным Sum+=*Data++ чуть быстрее.
Именно поэтому и не согласен, что посчитать 16 битную сумму намного проще и быстрее, чем правильное 16 битное CRC.
Поскольку особого преимущества нет, IMHO, лучше использовать проверенные алгоритмы.


А расзве кто то утверждал, что табличного алгоритма вычисления CRC не существует?
Он есть, и он в разы медленнее и больше по объему кода, чем вычисление простой суммы.

А то, что одна из причин использования CRC ( если не единственная ) -
Поскольку особого преимущества нет, IMHO, лучше использовать проверенные алгоритмы - с этим тоже вроде никто не спорит.

Речь о другом - в чем преимущества CRC при обнаружении ошибок при блочной передаче.
И стьль ли они подавляющи ( если есть ) чтобы принебрегать вариантом с простой суммой?
ASN
vallav
Пример на VHDL приведён как подтверждение того факта, что реализация на аппаратной логике вычисления CRC как минимум не уступает по производительности и ресурсам вычислению прямой суммы.
Пример кода на С приведёт как подтверждение того факта, что реализация табличным способом не намного сложнее и медленнее, чем прямая сумма. Для данного конкретного случая он в разы не медленнее.
Поясните почему специалисты, разработавшие STANAG5066, не стали использовать обычное сложение, а применили для контроля целостности пакета CRC16 и CRC32. Поскольку STANAG5066 использует в качестве основы STANAG4285, где применён свёрточный код, ошибки при его декодировании пакетные (длина искажённой последовательности как больше длины проверочного слова, так и меньше).
vallav
Цитата(ASN @ Apr 15 2010, 21:54) *
vallav
Пример на VHDL приведён как подтверждение того факта, что реализация на аппаратной логике вычисления CRC как минимум не уступает по производительности и ресурсам вычислению прямой суммы.
Пример кода на С приведёт как подтверждение того факта, что реализация табличным способом не намного сложнее и медленнее, чем прямая сумма. Для данного конкретного случая он в разы не медленнее.
Поясните почему специалисты, разработавшие STANAG5066, не стали использовать обычное сложение, а применили для контроля целостности пакета CRC16 и CRC32. Поскольку STANAG5066 использует в качестве основы STANAG4285, где применён свёрточный код, ошибки при его декодировании пакетные (длина искажённой последовательности как больше длины проверочного слова, так и меньше).


Вообще то реализация сумматора на логике заметно сложнее реализации CRC.
Речь о ситуации, когда сумматор в системе уже есть. И реализован достаточно эффективно.

То есть, там не важно обнаружение двойных разрозненных ошибок а важно определение еденичных поражений порядка длины поверочного
слова? Тогда не знаю почему.
Может исходя из - поскольку особого преимущества нет, IMHO, лучше использовать проверенные алгоритмы.
VslavX
Цитата(vallav @ Apr 16 2010, 08:35) *
То есть, там не важно обнаружение двойных разрозненных ошибок а важно определение еденичных поражений порядка длины поверочного слова? Тогда не знаю почему.

ИМО, "единичные поражения порядка длины поверочного слова" CRC выловит ничуть не хуже простой суммы. Ну и как бонус выловит _ВСЕ_ единичные ошибки числом менее или равное кодовому расстоянию для данных длин блока и суммы.
Можно сделать простой эксперимент - берем блок, вычисляем сумму и CRC. Потом вносим определенное "поражение длиной в кодовое слово" - и смотрим сколько вариантов "поражения" не поймает сумма и сколько CRC. Если сумма 16-битная, сложение побайтовое и 16-битовое "поражение" выровнять на границе байта, то будет 255 "непойманных" вариантов для простой суммы, для CRC-16, думаю, будут единичные значения (так как CRC это остаток от деления - нужно будет подобрать такое значение искажения чтобы делилось на образующий полином с нулевым остатком, а таких значений для полиномов применяемых для CRC может быть одно-два).
vallav
Цитата(VslavX @ Apr 16 2010, 10:17) *
ИМО, "единичные поражения порядка длины поверочного слова" CRC выловит ничуть не хуже простой суммы. Ну и как бонус выловит _ВСЕ_ единичные ошибки числом менее или равное кодовому расстоянию для данных длин блока и суммы.
Можно сделать простой эксперимент - берем блок, вычисляем сумму и CRC. Потом вносим определенное "поражение длиной в кодовое слово" - и смотрим сколько вариантов "поражения" не поймает сумма и сколько CRC. Если сумма 16-битная, сложение побайтовое и 16-битовое "поражение" выровнять на границе байта, то будет 255 "непойманных" вариантов для простой суммы, для CRC-16, думаю, будут единичные значения (так как CRC это остаток от деления - нужно будет подобрать такое значение искажения чтобы делилось на образующий полином с нулевым остатком, а таких значений для полиномов применяемых для CRC может быть одно-два).


А что не побитовое сложение?
Разница еще разительнее получится.
Вы где то нашли микроконтроллер, в котором затруднительно делать 16 битные сложения?
Полная сумма не пропустит ни одного еденичного многобитового поражения длиной меньше или равного 16 бит.
CRC же, в зависимости от вида перемешивания битов.
Чем лучше заточена на отлов двойных разрозненных ошибок, тем более короткие еденичные многобитные будет пропускать.
VslavX
Цитата(vallav @ Apr 16 2010, 10:50) *
А что не побитовое сложение?
...
Вы где то нашли микроконтроллер, в котором затруднительно делать 16 битные сложения?

А Вы где-то четко указали что сложения идут 16-битными словами? Обычно программа упрощена - идет поток байтов и складываются байты - не надо рассматривать случаи с нечетным количеством и т.д. И не уводите ситуацию в сторону - я просто привел Вам пример когда простая сумма оказалась многократно хуже CRC. Разумеется и наоборот, можно натянуть условия, и показать что CRC хуже суммы для каких-то конкретных условий, но все равно - не столь кратно. И тут еще вопрос - насколько типично такое "многобитовое поражение", исследования проводили? Линии передачи ведь разные бывают, и вероятности возникновения различных ошибок тоже разные. Я думаю, CCITT несколько более осведомлен в этом вопросе, раз уж выбрана CRC (как я понимаю - для модемных соединений).
Палыч
Цитата(VslavX @ Apr 16 2010, 11:32) *
И тут еще вопрос - насколько типично такое "многобитовое поражение", исследования проводили?
Присоединюсь к мнению, что единичное многобитовое поражение - скорее, нетипичная ситуация. А то у Вас прям какая-то интеллектуальная помеха: строго инвертирует последовательность бит в данных... Такая ситуация вероятнее всего, если в потоке данных имеется большая последовательность нулей (или единиц), а помеха привела к декодированию на приёмнике единиц (нулей). Но, это - уже недостатки кодирования данных, а не проверки их целостности.
vallav
Цитата(Палыч @ Apr 16 2010, 13:17) *
Присоединюсь к мнению, что единичное многобитовое поражение - скорее, нетипичная ситуация. А то у Вас прям какая-то интеллектуальная помеха: строго инвертирует последовательность бит в данных... Такая ситуация вероятнее всего, если в потоке данных имеется большая последовательность нулей (или единиц), а помеха привела к декодированию на приёмнике единиц (нулей). Но, это - уже недостатки кодирования данных, а не проверки их целостности.


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



Цитата(VslavX @ Apr 16 2010, 12:32) *
А Вы где-то четко указали что сложения идут 16-битными словами? Обычно программа упрощена - идет поток байтов и складываются байты - не надо рассматривать случаи с нечетным количеством и т.д. И не уводите ситуацию в сторону - я просто привел Вам пример когда простая сумма оказалась многократно хуже CRC. Разумеется и наоборот, можно натянуть условия, и показать что CRC хуже суммы для каких-то конкретных условий, но все равно - не столь кратно. И тут еще вопрос - насколько типично такое "многобитовое поражение", исследования проводили? Линии передачи ведь разные бывают, и вероятности возникновения различных ошибок тоже разные. Я думаю, CCITT несколько более осведомлен в этом вопросе, раз уж выбрана CRC (как я понимаю - для модемных соединений).


Дык если не указано, из примерно одинакового рассматривать надо лучшее а не худшее.
Или Вы все же настаиваете, что для микроконтроллеров 16 битное сложение реализуется существенно сложнее 8 битного?
А с нечетным числом байт в блоке фиксированной длины - полагаете, непреодолимо?

И еще раз - я не утверждаю, что CRC хуже прямой суммы, я утверждаю, что прямая сумма не хуже CRC во многих случаях но много
проще в реализации.
По поводу - какие ошибки - как раз сторонники CRC должны привести обоснование, что в данной конкретной ситуации ( где применен
более сложный в реализации метод ) ошибки таковы, что усложнение оправдано.
VslavX
Цитата(vallav @ Apr 16 2010, 13:40) *
Или Вы все же настаиваете, что для микроконтроллеров 16 битное сложение реализуется существенно сложнее 8 битного?

Не-а, я такого не говорил - это Вы все мне упорно пытаетесь приписать данное утверждение smile.gif
Цитата(vallav @ Apr 16 2010, 13:40) *
И еще раз - я не утверждаю, что CRC хуже прямой суммы, я утверждаю, что прямая сумма не хуже CRC во многих случаях но много
проще в реализации.

Что значит "лучше-хуже"? Давайте уж разговаривать как инженеры а не как "гумонетарии" - в цифрах. Как можно разговаривать в цифрах? А очень просто - в нашем конкретном случае цифра заключена в величине вероятности что прийдет ошибочный пакет и эта ошибка не будет распознана. Такая вероятность вычисляется как сумма произведений вероятности возникновения на данной линии ошибка данного типа (распределение ошибок) на вероятость необнаружения данной ошибки проверочным кодом (определяется самим типом кода). Чтобы подсчитать конкретную цифру надо хорошо владеть теорией линейных кодов. Я эту теорию глубоко не изучал, но как инженер, просто готов воспользоваться выводами математиков - они уверяют что CRC обеспечит одну из наименьших вероятостей (при каких условиях врать не буду- при нормальном ли распределении, или при равномерном - не знаю). Поэтому, у Вас есть два варианта - изучить теорию линейных кодов и подсчитать эти вероятности для Ваших линий самому (и поделиться с нами результатами smile.gif) для случаев арифметической суммы и для CRC, или просто поверить в готовые теоретические выводы, как это сделал я и многие другие. Возможно, у нас на форуме есть люди более глубоко владеющие математической стороной вопроса - они меня поправят или даже приведут цифры. Я, увы, за разумное (как для форумной дискусcии) время сделать этого не могу.
Палыч
Цитата(vallav @ Apr 16 2010, 13:40) *
Я разве говорил, что многобитовая помеха - это когда все 16 бит перевернуты?
Не, не обязательно, часть бит из этих 16 может быть не перевернутой.
Ну, дык - извините! Если передавали:
1010101010101010, а приняли:
1110100010101110 в результате действия помехи при передачи всей этой информации, то это - три одиночные ошибки, а не - "множественное поражение шестнадцати бит".

PS. Вы этим термином, наверно, именуете, любую последовательность из 16 бит, в которой несколько битов приняты неверно?
zltigo
Цитата(@Ark @ Apr 16 2010, 17:56) *
1) ...но и исправление ошибок.

Обалдеть. Исправление ошибки по остатку от деления smile.gif. Ну и остальные размышлизмы тем более можно не читать, ибо все в принципе с точностью до наоборот.
Матаппарат деления давно достаточно, для практического применения, исследован. Есть и результирующие рекомендации по выбору полиномов с оценками условий применения.
vallav
Цитата(Палыч @ Apr 16 2010, 16:04) *
Ну, дык - извините! Если передавали:
1010101010101010, а приняли:
1110100010101110 в результате действия помехи при передачи всей этой информации, то это - три одиночные ошибки, а не - "множественное поражение шестнадцати бит".

Ну да, это три одиночные ошибки, расположенные компактно.
Или это - множественное однократное поражение длиной не более 16 бит.
Вы похоже с помехами никогда не сталкивались, если решили, что помеха аккуратненько переворачивает все 16 бит в передаваемом пакете.


Цитата(Палыч @ Apr 16 2010, 16:04) *
PS. Вы этим термином, наверно, именуете, любую последовательность из 16 бит, в которой несколько битов приняты неверно?


Я этим термином именую ситуацию, когда ошибок много, но все ни в пределах 16 последовательных бит.
Много - это от одной до 16, сколько точно - не известно.
Это типичная ситуация, когда на линии возможна редкая мощная помеха.
zltigo
Цитата(vallav @ Apr 16 2010, 13:40) *
И еще раз - я не утверждаю, что CRC хуже прямой суммы, я утверждаю, что прямая сумма не хуже CRC во многих случаях..

Вероятностно ХУЖЕ во всех случаях, кроме одного единственного - одиночная ошибка. В этом случае она ЛУЧШЕ. Все, достаточно толочь воду в ступе.

Цитата(vallav @ Apr 16 2010, 19:11) *
Я этим термином именую ситуацию, когда ошибок много, но все ни в пределах 16 последовательных бит.

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