Надежность контрольной суммы CRC16

    Не так давно по долгу службы столкнулся с довольно интересной проблемой.

    У нас имеется устройство, которое осуществляет интенсивный обмен по внутренней шине RS485, число проходящих пакетов составляет порядка нескольких тысяч в секунду, каждый пакет имеет длину в 7 байт, два из которых предназначены для хранения контрольной суммы CRC16 в ее CMS варианте (полином = 0x8005, стартовое значение = 0xFFFF). Прием осуществляется в FIFO-буфер, который сдвигается вверх с вытеснением после приема каждого последующего байта. Индикатором получения реального пакета является факт совпадения его контрольной суммы со значением, переданным в самом пакете. Никаких заголовков или дополнительных параметров.

    Проблема заключалась в следующем – периодически, примерно раз в 5 минут, при передаче данных проскакивал пакет, данные которого давали выброс данных для одного из каналов, причем чаще всего выброс происходил до одного и того же значения. Сначала мы смотрели в сторону физических коллизий, но дело оказалось в другом – время от времени в буфере, где собирались полученные данные, оказывался пакет, состоящий из конца предыдущего пакета и начала следующего, причем контрольная сумма у такого комбинированного пакета оказывалась верной. То есть, налицо коллизия контрольной суммы: пакет не имеет смысла, но дает верную контрольную сумму.

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

    Для сравнения я выбрал несколько наиболее часто используемых 16-битных контрольных сумм с различными полиномами, стартовыми значениями и механизмом поступления битов. Выбранные мной суммы сведены в следующую таблицу:
    Обозначение Polynomial Init RefIn RefOut XorOut
    CMS 0x8005 0xFFFF false false 0x0000
    CCITT 0x1021 0xFFFF false false 0x0000
    AUG-CCITT 0x1021 0x1D0F false false 0x0000
    BYPASS 0x8005 0x0000 false false 0x0000
    CDMA2000 0xC867 0xFFFF false false 0x0000
    DDS-110 0x8005 0x800D false false 0x0000
    DECT-X 0x0589 0x0000 false false 0x0000
    EN-13757 0x3D65 0x0000 false false 0xFFFF
    Modbus 0x8005 0xFFFF true true 0x0000
    T10-DIF 0x8BB7 0x0000 false false 0x0000
    TELEDISK 0xA097 0x0000 false false 0x0000
    XMODEM 0x1021 0x0000 false false 0x0000

    В данном случае:

    • RefIn — порядок поступления битов из буфера данных: false — начиная со старшего значащего бита (MSB first), true – LSB first;
    • RefOut – признак инвертирования порядка битов на выходе: true – инвертировать.

    При эмуляции повреждения пакетов я реализовал следующие модели:

    • Shuffle: заполнение случайного количества байт в пакете случайными значениями
    • Bit shift: сдвиг случайных байт в пакете влево
    • Roll packet: кольцевой сдвиг байт в пакете влево
    • Right shift: сдвиг пакета вправо на один байт, слева дописывается 0xFF (передача идет посредством UART)
    • Left shift: сдвиг пакета влево на один байт, справа дописывается 0xFF
    • Fill zeros: заполнение случайного количества байт в пакете байтами 0x00 (все нули)
    • Fill ones: заполнение случайного количества байт в пакете байтами 0xFF (все единицы)
    • Byte injection: вставка в пакет случайного байта в случайном месте, байты за вставленным сдвигаются в направлении хвоста
    • Single bit: повреждение единственного случайного бита

    Затем программой были сгенерированы случайным образом 100.000.000 пакетов, над каждым из них была проведены указанные выше операции, после чего сравнивались контрольные суммы исходного и модернизированного пакета. Пакеты, которые не изменились при преобразовании, отбрасывались. Если контрольная сумма совпадала, то регистрировалась ошибка.

    В итоге была получена следующая таблица с количеством ошибок:
    Обозначение Shuffle Bit shift Roll packet Right shift Left shift Fill zeros Fill ones Byte injection Sum
    CMS 5101 3874 2937 1439 1688 3970 4010 1080 24099
    CCITT 2012 1127 3320 1494 1486 1063 1096 1130 12728
    AUG-CCITT 2012 1127 3320 1494 1486 1063 1096 1130 12728
    BYPASS 5101 3874 2937 1439 1688 3970 4010 1080 24099
    CDMA2000 1368 1025 1946 1462 1678 1043 1028 1112 10662
    DDS-110 5101 3874 2937 1439 1688 3970 4010 1080 24099
    DECT-X 1432 1189 5915 1779 1580 1215 1209 1093 15412
    EN-13757 1281 2209 3043 1520 1528 2193 2187 1039 15000
    Modbus 5090 3888 3086 1282 1582 3947 3897 1073 23845
    T10-DIF 1390 922 1424 1421 1630 994 938 1093 9812
    TELEDISK 1394 1049 5398 1451 1512 1096 1066 1065 14031
    XMODEM 2012 1127 3320 1494 1486 1063 1096 1130 12728

    Очевидно, что стартовое значение алгоритма никак не влияет на полученный результат, что логично, стартовое значение дает нам лишь иное значение контрольной суммы, но сам механизм расчета никак не меняется. Поэтому эти контрольные суммы я исключил из дальнейшего рассмотрения. Точно так же не имеет смысла рассматривать ошибки в одиночных битах, все контрольные суммы справились с этим безошибочно, что, собственно, от них и требовалось при создании.

    Ну и итоговая таблица качества контрольной суммы, уже без учета дублирующих алгоритмов:
    Обозначение Number of collisions Place
    CMS 24099 8
    CCITT 12728 3
    CDMA2000 10662 2
    DECT-X 15412 6
    EN-13757 15000 5
    Modbus 23845 7
    T10-DIF 9812 1
    TELEDISK 14031 4

    Остальные выводы оставляю читателям. От себя замечу лишь, что определенное влияние на результаты оказывает число единиц в полиноме контрольной суммы. Но это всего лишь мое личное субъективное мнение. Буду рад выслушать иные объяснения.

    Исходный код программы приведен ниже.

    Исходный код
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdint.h>
    #include <stdbool.h>
    #include <string.h>
    #include <time.h>
    
    #define PACKET_LEN    (7)
    #define NUM_OF_CYCLES (100000)
    
    static unsigned char reverse_table[16] =
    {
      0x0, 0x8, 0x4, 0xC, 0x2, 0xA, 0x6, 0xE,
      0x1, 0x9, 0x5, 0xD, 0x3, 0xB, 0x7, 0xF
    };
    
    uint8_t reverse_bits(uint8_t byte)
    {
      // Reverse the top and bottom nibble then swap them.
      return (reverse_table[byte & 0b1111] << 4) | reverse_table[byte >> 4];
    }
    
    uint16_t reverse_word(uint16_t word)
    {
      return ((reverse_bits(word & 0xFF) << 8) | reverse_bits(word >> 8));
    }
    
    uint16_t crc16_common(uint8_t *data, uint8_t len, uint16_t poly, uint16_t init,
                          uint16_t doXor, bool refIn, bool refOut)
    {
      uint8_t y;
      uint16_t crc;
    
      crc = init;
    	while (len--)
      {
        if (refIn)
          crc = ((uint16_t)reverse_bits(*data++) << 8) ^ crc;
        else
    	    crc = ((uint16_t)*data++ << 8) ^ crc;
        for (y = 0; y < 8; y++)
        {
          if (crc & 0x8000)
            crc = (crc << 1) ^ poly;
          else
            crc = crc << 1;
        }
    	}
    
      if (refOut)
        crc = reverse_word(crc);
      return (crc ^ doXor);
    }
    
    uint16_t crc16_ccitt(uint8_t *data, uint8_t len)
    {
      return crc16_common(data, len, 0x1021, 0xFFFF, 0x0000, false, false);
    }
    
    uint16_t crc16_bypass(uint8_t *data, uint8_t len)
    {
      return crc16_common(data, len, 0x8005, 0x0000, 0x0000, false, false);
    }
    
    uint16_t crc16_xmodem(uint8_t *data, uint8_t len)
    {
      return crc16_common(data, len, 0x1021, 0x0000, 0x0000, false, false);
    }
    
    uint16_t crc16_teledisk(uint8_t *data, uint8_t len)
    {
      return crc16_common(data, len, 0xA097, 0x0000, 0x0000, false, false);
    }
    
    uint16_t crc16_augccitt(uint8_t *data, uint8_t len)
    {
      return crc16_common(data, len, 0x1021, 0x1d0f, 0x0000, false, false);
    }
    
    uint16_t crc16_cdma2000(uint8_t *data, uint8_t len)
    {
      return crc16_common(data, len, 0xc867, 0xffff, 0x0000, false, false);
    }
    
    uint16_t crc16_dds110(uint8_t *data, uint8_t len)
    {
      return crc16_common(data, len, 0x8005, 0x800d, 0x0000, false, false);
    }
    
    uint16_t crc16_dect(uint8_t *data, uint8_t len)
    {
      return crc16_common(data, len, 0x0589, 0x0000, 0x0000, false, false);
    }
    
    uint16_t crc16_en13757(uint8_t *data, uint8_t len)
    {
      return crc16_common(data, len, 0x3d65, 0x0000, 0xffff, false, false);
    }
    
    uint16_t crc16_t10dif(uint8_t *data, uint8_t len)
    {
      return crc16_common(data, len, 0x8bb7, 0x0000, 0x0000, false, false);
    }
    
    uint16_t crc16_cms(uint8_t *data, uint8_t len)
    {
      return crc16_common(data, len, 0x8005, 0xFFFF, 0x0000, false, false);
    }
    
    uint16_t crc16_modbus(uint8_t *data, uint8_t len)
    {
      return crc16_common(data, len, 0x8005, 0xFFFF, 0x0000, true, true);
    }
    
    bool compare_buf(uint8_t *buf1, uint8_t *buf2)
    {
      uint8_t x;
    
      for (x = 0; x < PACKET_LEN; x++)
      {
        if (buf1[x] != buf2[x])
          return true;
      }
    
      return false;
    }
    
    bool method_shuffle(uint8_t *buf)
    {
      uint8_t i, j;
      uint16_t rnd;
      uint8_t copy[PACKET_LEN];
    
      memcpy(copy, buf, PACKET_LEN);
    
      for (i = 0; i < PACKET_LEN; i++)
      {
        for (j = 0; j < 10; j++)
        {
          rnd = (uint16_t)rand();
          if (rnd % 7 == 0)
            buf[i] ^= (1 << (rnd % 8));
        }
      }
    
      return compare_buf(buf, copy);
    }
    
    bool method_bitshift(uint8_t *buf)
    {
      uint8_t x, i, j;
      uint8_t copy[PACKET_LEN];
    
      memcpy(copy, buf, PACKET_LEN);
    
      x = (uint8_t)(rand() % PACKET_LEN) + 1;
      for (j = 0; j < x; j++)
      {
        i = (uint8_t)(rand() % PACKET_LEN);
        if (buf[i] == 0)
          buf[i] = 0x01;
        else
          buf[i] <<= 1;
      }
    
      return compare_buf(buf, copy);
    }
    
    bool method_packetroll(uint8_t *buf)
    {
      uint8_t x, i, j;
      uint8_t temp;
      uint8_t copy[PACKET_LEN];
    
      memcpy(copy, buf, PACKET_LEN);
    
      x = (uint8_t)(rand() % (PACKET_LEN - 1)) + 1;
      for (j = 0; j < x; j++)
      {
        temp = buf[0];
        for (i = 0; i < PACKET_LEN - 1; i++)
          buf[i] = buf[i + 1];
        buf[PACKET_LEN - 1] = temp;
      }
    
      return compare_buf(buf, copy);
    }
    
    bool method_shiftright(uint8_t *buf)
    {
      uint8_t i;
      uint8_t copy[PACKET_LEN];
    
      memcpy(copy, buf, PACKET_LEN);
    
      for (i = 0; i < PACKET_LEN - 1; i++)
          buf[i + 1] = buf[i];
      buf[0] = 0xff;
    
      return compare_buf(buf, copy);
    }
    
    bool method_shiftleft(uint8_t *buf)
    {
      uint8_t i;
      uint8_t copy[PACKET_LEN];
    
      memcpy(copy, buf, PACKET_LEN);
    
      for (i = 0; i < PACKET_LEN - 1; i++)
          buf[i] = buf[i + 1];
      buf[PACKET_LEN - 1] = 0xff;
    
      return compare_buf(buf, copy);
    }
    
    bool method_zero(uint8_t *buf)
    {
      uint8_t x, i, j;
      uint8_t copy[PACKET_LEN];
    
      memcpy(copy, buf, PACKET_LEN);
    
      x = (uint8_t)(rand() % PACKET_LEN) + 1;
      for (j = 0; j < x; j++)
      {
        i = (uint8_t)(rand() % PACKET_LEN);
        if (buf[i] != 0x00)
          buf[i] = 0x00;
        else
          buf[i] = 0xFF;
      }
    
      return compare_buf(buf, copy);
    }
    
    bool method_one(uint8_t *buf)
    {
      uint8_t x, i, j;
      uint8_t copy[PACKET_LEN];
    
      memcpy(copy, buf, PACKET_LEN);
    
      x = (uint8_t)(rand() % PACKET_LEN) + 1;
      for (j = 0; j < x; j++)
      {
        i = (uint8_t)(rand() % PACKET_LEN);
        if (buf[i] != 0xFF)
          buf[i] = 0xFF;
        else
          buf[i] = 0x00;
      }
    
      return compare_buf(buf, copy);
    }
    
    bool method_injection(uint8_t *buf)
    {
      uint8_t x, i;
      uint8_t copy[PACKET_LEN];
    
      memcpy(copy, buf, PACKET_LEN);
    
      x = (uint8_t)(rand() % PACKET_LEN);
      for (i = PACKET_LEN - 1; i > x; i--)
      {
        buf[i] = buf[i - 1];
      }
      buf[x] = (uint8_t)rand();
    
      return compare_buf(buf, copy);
    }
    
    bool method_single(uint8_t *buf)
    {
      uint8_t x;
    
      x = (uint8_t)(rand() % (PACKET_LEN * 8));
      buf[(uint8_t)(x / 8)] ^= (1 << (x % 8));
    
      return true;
    }
    
    typedef struct
    {
      uint16_t crc1;
      uint16_t crc2;
      uint32_t errors;
      uint16_t (*fn)(uint8_t *data, uint8_t len);
      char name[32];
    } tCRC;
    
    typedef struct
    {
      bool (*fn)(uint8_t *buf);
      char name[32];
    } tMethod;
    
    static tMethod methods[] =
    {
      {method_shuffle, "Shuffle"},
      {method_bitshift, "Bit shift"},
      {method_packetroll, "Roll packet"},
      {method_shiftright, "Right shift"},
      {method_shiftleft, "Left shift"},
      {method_zero, "Fill zeros"},
      {method_one, "Fill ones"},
      {method_injection, "Byte injection"},
      {method_single, "Single bit"}
    };
    
    static tCRC crcs[] =
    {
      {0, 0, 0, crc16_cms, "CMS"},
      {0, 0, 0, crc16_ccitt, "CCITT"},
      {0, 0, 0, crc16_augccitt, "AUG-CCITT"},
      {0, 0, 0, crc16_bypass, "BYPASS"},
      {0, 0, 0, crc16_cdma2000, "CDMA2000"},
      {0, 0, 0, crc16_dds110, "DDS-110"},
      {0, 0, 0, crc16_dect, "DECT-X"},
      {0, 0, 0, crc16_en13757, "EN-13757"},
      {0, 0, 0, crc16_modbus, "Modbus"},
      {0, 0, 0, crc16_t10dif, "T10-DIF"},
      {0, 0, 0, crc16_teledisk, "TELEDISK"},
      {0, 0, 0, crc16_xmodem, "XMODEM"}
    };
    
    int main(int argc, char * argv[])
    {
      uint32_t num_of_cycle;
      uint32_t num_of_sums;
      uint8_t packet[PACKET_LEN];
      uint8_t i;
      uint8_t m;
      //uint8_t buf[8] = {0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17};
    
      srand(time(NULL));
    
      printf("------------------------- CRC16 comparison -------------------------\n");
    
      num_of_sums = sizeof(crcs) / sizeof(tCRC);
      for (m = 0; m < sizeof(methods) / sizeof(tMethod); m++)
      {
        printf("\r%s:\n", methods[m].name);
    
        for (i = 0; i < num_of_sums; i++)
        {
          crcs[i].errors = 0;
        }
        for (num_of_cycle = 0; num_of_cycle < NUM_OF_CYCLES; num_of_cycle++)
        {
          for (i = 0; i < PACKET_LEN; i++)
            packet[i] = (uint8_t)rand();
    
          for (i = 0; i < num_of_sums; i++)
            crcs[i].crc1 = crcs[i].fn(packet, PACKET_LEN);
    
          if (!methods[m].fn(packet))
            continue;
    
          for (i = 0; i < num_of_sums; i++)
          {
            crcs[i].crc2 = crcs[i].fn(packet, PACKET_LEN);
            if (crcs[i].crc1 == crcs[i].crc2)
              crcs[i].errors++;
          }
          if (num_of_cycle % 1000 == 0)
            printf("\r%.2f%%", (float)num_of_cycle / NUM_OF_CYCLES * 100);
        }
    
        for (i = 0; i < num_of_sums; i++)
          printf("\r  %20s: %10d\n", crcs[i].name, crcs[i].errors);
      }
    
      return 0;
    }
    


    В итоге в следующей версии изделия для внутренней шины была выбрана контрольная сумма CCITT, в большей степени потому, что ее реализация была доступна в аппаратной части используемого микроконтроллера.
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 121

      +1
      как низко пал… Modbus
        0

        Причем тут modbus?

        +3
        Насколько хороша повторяемость этого эксперимента? Я имею ввиду, получу ли я схожие результаты, если прогоню еще 100 000 000 пакетов? Может это просто дикая дисперсия?
          0
          Все достаточно повторяемо
            0
            Известно, что числа, полученные остатком от деления rand(), вообще говоря имеют плохое равномерное распределение. Хотя с другой стороны я не возьмусь утверждать, что результат сильно изменится, если взять генератор получше, но было интересно исключить этот фактор.
              +8
              Это, на самом деле, не играет большой роли.

              Штука, у которой гарантированно не больше 65536 уникальных значений, в любом случае плохо подходит для того, для чего её авторы поста использовали. Алгоритм, по которому она вычисляется, здесь влияет только на то, насколько быстро вы встретитесь с этой проблемой.

              Авторам повезло, они взяли плохой алгоритм и встретились быстро.
          +18
          Мне так сдаётся, что подсчёт числа коллизий на полностью случайных данных при условии, что у контрольной суммы совершенно точно никак не больше 65536 возможных значений, является задачей чисто умозрительной и не требующей написания какого-либо кода, а дизайн системы, в котором на отсутствие таких коллизий полагались, — странным.

          Задача же определения числа коллизий для пакетов конкретного вида и содержания не имеет практической ценности в отрыве от конкретной задачи, определяющей этот вид и содержание.

          Некоторый интерес может представлять собой проверка, действительно ли у всех представленных алгоритмов 65536 возможных значений CRC16, и насколько равномерно они распределены — это сразу позволит отделить хорошие алгоритмы от плохих, без привязки к конкретным данным.
            +2
            не согласен. Алгоритм должен быть еще стоек к некоторым модификациям данных. К примеру — изменению порядка байтов. Если в качестве crc взять sum(X) % 65536, где X — вектор из двухбайтовых значений, то он будет давать достаточно ровное распределение, но порядок двухбайтовых блоков можно будет менять как угодно.
              +1
              Это так для совсем простых алгоритмов, вычислять это специальной программой в общем не требуется, можно просто указать.
                +5

                Зачем? Я не очень представляю себе, как можно реализовывать что‐то поверх протокола уровня UART и получить случайное изменение порядка байтов (если только у вас нет ошибки в программе). Получить мусорный бит в середине на том же SPI при помехах на линии тактирования — можно. Получить инверсию бита из‐за помех — можно. Получить байт(ы) посылки от другого устройства между байтами посылки от первого — можно, но такие проблемы разруливаются не CRC, если только инверсия произошла не при передаче адреса отправителя. А что может привести к изменению порядка байтов кроме ошибки в программе? У того же TCP ожидается произвольный порядок приёма, но пакетов и по очень хорошей причине.

                  +2
                  Предположим, что CRC — XOR данных. К примеру, двухбайтовый.
                  Теперь представим, что пакет содержит 6 байт. Первые два байта меняются редко, потом 2 байта данных и два байта CRC. По факту это означает, что XOR от всего пакета включая CRC должен быть 0 (ноль). Это похоже на то, что у автора? Вроде да, но там функция CRC чуть другая.

                  А теперь смещаем окно на 2 байта вправо. Как думаете, CRC сойдется? Мне почему-то кажется, что да. Даже при смещении на 1 байт — тоже сойдется.

                  Вот и все :-)
                    0

                    Хорошо, вы правы. Я почему‐то решил, что вы написали про абсолютно произвольное изменение порядка, а не более конкретный циклический сдвиг — моя способность «додумать» без уточнения несколько промахнулась :)

                  +1
                  Порядок байт вряд ли может изменится в обычном канале связи. Но может произойти двойная ошибка, один бит меняется с 1 на 0, другой бит в том же месте байта с 0 на 1, и ошибка проходит незамеченной. Такое очень вероятно, и вероятность выше чем 1 к 65535. А при CRC обычной, чтобы ошибка прошла незамеченной, нужно достаточно необычные комбинации формировать. Если один бит меняется с 1 на 0, то для прохождения контрольной суммы должны изменится еще несколько бит в разных байтах в разных местах.
                    0
                    А мы тут что обсуждаем, пардон? CRC с различными полиномами или «в качестве CRC взять абстрактную f(x)»?
                    Давайте так: CRC это циклический избыточный код (см. в википедии), абстрактная f(x) — это некая контрольная сумма (checksum). Просто, понятно, общепринято.
                  +9
                  Контрольная сумма она для защиты от ошибки первого рода (узнать что она была).
                  Почти все указанные тут по сути защищают от 1 бита ошибки.
                  Полиномы еще дополнительно защищают от перестановки бит, в пределах ширины.
                  Но таки да, всегда можно подобрать набор данных чтоб получить любую наперёд заданную CRC по любому из алгоритмов.
                  И таки да, перестановка байт/слов вполне может пройти незаметно для CRC.

                  Любой протокол обмена крайне рекомендовано завязывать на фиксированные начало и конец (или длину), а CRC использовать для проверки что принятое — не случайный шум.
                    +7
                    Писать связно и по-порядку несколько лениво. Но вот ключевые термины и моменты.
                    CRC является подмножеством циклических кодов (keywords: поля Галуа, коды БЧХ, порождающий полином, синдром, расстояние Хэмминга).
                    Вероятность не/обнаружения ошибки вычисляется достаточно нетривиально (насколько я знаю на данный момент только брутфорс и товарищ Koopman уже отбрутфорсил много полиномов для разных длин сообщений и расстояний Хэмминга (можно ознакомиться с результатами здесь: users.ece.cmu.edu/~koopman/crc).

                    Конкретно про 16-битные полиномы: users.ece.cmu.edu/~koopman/crc/crc16.html (в шапке есть ссылка где поясняется, что значат все эти цифры)

                    Конкретно про CRC-CCITT

                    (0x8810; 0x11021) <=> (0x8408; 0x10811) {32751,32751} | gold | (*op) CCITT-16

                    *о — это значит полином содержит множитель x+1 (keywords бит чётности) и, следовательно, детектирует все «нечётные ошибки», это когда нечётное количество бит поменяло своё значение.

                    Из простых рабоче-крестьянских предположений можно рассуждать так: для 16-битного CRC число возможных состояний 2^16 — 1 = 65 535. И, следовательно мы должны обнаруживать однократные ошибки для сообщений длиной 2^16 — 1 — 16 (длина CRC) = 65519 бит. (на самом деле, мы знаем, что нечётные ошибки будут обнаружены при любой длине сообщения). Для ошибок большей кратности можно ожидать что, верхняя граница длины сообщения должна быть такой, чтобы число возможных перестановок ошибочных бит (keywords биноминальный коэффициент) не превышвало число возможных состояний CRC.
                    Это даёт неплохую оценку, но, как показывает брутфорс эта оценка справедлива только для малых значений расстояний Хэмминга.
                      0
                      Вот за эти ссылки спасибо, ведь реально автор пришел, пусть и более осознанным и подкрепленным вычислениями путем, к выводу, что не все полиномы одинаково хороши.
                      –1
                      но дело оказалось в другом – время от времени в буфере, где собирались полученные данные, оказывался пакет, состоящий из конца предыдущего пакета и начала следующего
                      Ну вот вы же нашли проблему — брались неверные данные. Правильнее было бы искать ошибку в драйвере отправки данных (ок, не в драйвере, а в коде, формирующим пакеты), понять почему так происходит, что вообще берутся данные из ненужных сейчас к отправке пакетов. А пытаться применить другой CRC16 — это как наливать всё больше воды в дырявое ведро, вместо латания дыр.
                        0
                        Нет никакой ошибки в отправке. И на приёме нет. Есть проблема в отсутствии маркера фрейма.
                        То есть пакеты идут: D0-D1-D2-D3-D4-C1-C2 где C1 и C2 — контрольная сумма.
                        Определением пакета было «контрольная сумма сошлась». При этом обрабатывался циклический буфер. То есть спустя несколько байт получалось:
                        D2-D3-D4-C1-C2-N0-N1
                        где N0 и N1 это байты от следующего пакета, но на приёмнике они рассматриваются как CRC16 и дают схождение суммы для всего пакета.
                        Что немаловероятно.
                          –1
                          Тут надо было делать 64-битную контрольную сумму, проблемы бы не было.
                            +3
                            Достаточно добавить фиксированный байт начала пакета. В идеале — такой, который не может быть в данных. Это даст накладные расходы в 1 байт и стабилизирует систему (останутся только ошибки порядка 1 на ~1e-10 байт).
                            64битная сумма (то есть 8 байт сумма на 5 байт данных, кхе кхе) создаст больше проблем.
                            проще уж тогда присылать инверсные данные, всего 5 байт понадобится.
                              0
                              64 битная контрольная сумма сделает невозможной прием сбойного пакета данных, вероятностью 1 / 2^64 можно пренебречь.
                              Все остальные варианты проще программно, но повышают вероятность ошибки. Хотя если речь о 1 на ~1e-10 байт то не важно, конечно, это почти идеальная линия связи.
                              Инверсные дополнительные данные тоже имеют очень высокую вероятность ошибки, по сравнению с CRC64, достаточно двойной ошибки.
                                +1

                                Я говорю про ошибки "обработка сбойного пакета". Приём сбойного пакета возможен всегда, задача как раз его проигнорировать, иногда — ещё узнать что он вообще был.

                                  0
                                  Приём сбойного пакета возможен всегда, задача как раз его проигнорировать

                                  Эту задачу решает CRC, он для этого и придуман.
                                  0
                                  Вы статью-то прочитали? Вероятность ошибки у автора не 1/2**16, а на порядок (десятичный!) бОльшая. Не, для 2**64 порядок туда — порядок сюда — уже неважно, но всё ж таки…
                                    0
                                    По таблице, где тестировалось 100 000 000 переданных кадров данных с ошибкой порядок величины не распознанных ошибок как-раз 1/2^16 или 1/65536, плюс девиации в зависимости от алгоритма и типа ошибки.
                                    Пример 2000 не распознанных ошибок из 100 000 000 кадров это 1/50 000, что достаточно точно совпадает с теорией.
                                0
                                Почитайте еще раз статью, длина всего пакета с CRC16 — 7 байт, степень заполнения канала при этом порядка 70%. А теперь добавьте сюда еще 6 байт CRC64.
                                  0
                                  CRC64 8 же байт.
                                    0
                                    Да, но CRC16 длиной 2 байта в пакете уже есть, ее ж менять собрались
                            0
                            CCITT, в большей степени потому, что ее реализация была доступна в аппаратной части используемого микроконтроллера.


                            Можно было на операции перемножения сделать расчет контрольной суммы, умножение микроконтроллеры обычно поддерживают. Вот тут описал
                            habr.com/post/278171

                            И разрядность побайтно подбирать, 16 бит контрольная сумма может быть недостаточной, есть возможность выбрать 24 бита или 32. В идеале 64 бит, но канал связи может ограничить прохождение избыточных данных. Чем хуже канал передачи данных, выше вероятность помехи, тем больше разрядов должно быть в контрольной сумме. В самых тяжелых случаях можно избыточную информацию передавать, для восстановления данных без перезапроса.

                              0
                              недостаточной для чего?
                              я вообще считаю что даже на 57600 на расстояниях в 50 метров достаточно однобайтного дополнения до нуля.
                              при условиях:
                              — линия согласована
                              — токовая петля
                              — приемопередатчик с корректной обработкой мажоритарности в центре бита
                              — бит четности используется
                              — пакеты имеют начало и конец
                              — все байты на передаче — ASCII.
                                0
                                Смотря какой процент сбойных бит и что за информация. Если телеметрия с датчиков, то информация не так важна, единичные сбои пройдут незамеченными ни как и всегда можно перезапросить данные повторно. Если управление исполнительными механизмами, то ошибки недопустимы.
                                  0
                                  Что значит «ошибки недопустимы»? Какого рода ошибки?
                                  Если надо минимизировать вероятность повреждения и необходимость переотправки команды — то надо использовать рида-соломона а не CRC. Или вообще сразу посылать команду трижды, и пусть исполительный отрабатывает только две совпавшие команды из последних трёх.
                                    0
                                    CRC64 снижает вероятность ошибки в 2^64 раз, а тройная отправка команды намного менее надежна, достаточно чтобы одинаковая ошибка возникла в двух командах из трех. Если команда 1 байт, то вероятность ошибки в той же команде при двойной отправке ниже всего в ~2^8 раз, что не так много. В зашумленном канале связи, например, радиоканале, вообще, недопустимо.
                                      +2

                                      Вы не понимаете сути, контрольных сумм как таковых.
                                      Они позволяют оценить корректность передачи большого пакета за счёт небольшого количества данных.
                                      Это размен вычислительной на канальную мощности.
                                      Передача контрольной суммы больше чем пакет данных означает, что вы можете передать пакет энное число раз. А дальше хотите — любое отклонение = ошибка. Хотите — мажоритарный принцип, что позволит игнорировать часть ошибок.
                                      Платить же И вычислительной сложностью И данными в канале — это как "ты что, дурак? За углом можно вдвое дороже купить!".

                                        0
                                        Ну пример с 1 байтом полезной информации упрощенный, чтобы оценить вероятность ошибки при тройной передаче данных. Реальные протоколы сложнее, Modbus ASCI например, там не все символы разрешены для передачи, поэтому появляется дополнительная защита от ошибки в кадре данных.
                                        «Большой пакет данных» не обязателен, это просто способ проверки корректности передачи (да и хранения) данных. По возрастастающей, от 1-битной контрольной суммы в RS232 (бит четности, в том числе в модулях памяти), до 8-битной, 16-битной из статьи, 32-битной в Etherner, 64-битной даже не знаю где, бОльшие разрядности это уже скорее ключи подписи из криптографии, 128 бит и более.
                                        Можно рассмотреть «странные» варианты, когда надо передать 1 бит, включить/выключить ответственный объект, зашумленный канал связи, например 50% ошибок в каждом бите. Тут вполне разумным кажется передать 1 бит данных и контрольную сумм в 64 бита, вероятность ошибки даже при одиночном кадре данных 50% / (2^64).
                                        А если 3 раза передать команду включения/выключения, то вероятность ошибки будет всего ~30%, это лучше чем однократная отправка данных, но по сравнению с защитой 64-битной контрольной суммой не сравнимо в принципе.
                                        Данные в канале не заменяют контрольную сумму ни в коем случае. Если с 1 битом это не очевидно (можно 64 раза команду передать), то с 32-битной командой (например задаем напряжение для ЦАП какого-то исполнительного механизма), 64-битная контрольная сумма нормальный вариант, а сравнимая по надежности 64-кратная передача данных уже за пределами разумного по нагрузке на канал, вместо 32+64 бит, передали 4096 бит.
                                        Просто передать данные 3 раза допустимо только в вашем частном случае, а в случаях с высокой вероятностью ошибки нужны только длинные контрольные суммы, иначе ни как. Зато можно передавать данные даже в каналах где шум выше полезного сигнала, делая N попыток.
                                          +1

                                          Вы во всех расчётах упускаете факт, что ошибка влияет на контрольную сумму в том ЧИСЛЕ.
                                          Собственно, вы все равно посылаете две фиксированные последовательности.
                                          У вас 2^65 возможных данных на приёме, из которых корректны только два. (кстати, не факт что равноудалённые, но это и не важно).


                                          Не 50%/264, ошибки, а 1/265 что вообще хоть что-то будет приятно приёмником, так как црц не даёт возможности восстановить в случае ошибки, только информацию о наличии ошибки.


                                          Передать при шуме выше сигнала можно только статистическими методами. Например — передача единицы как меандра со скважностью 3, а нуля как меандра со скважностью 7. Добавляем заголовок со скважностью 5 для синхронизации и замера базовой линии. Вот это даст возможность принять даже на зашумленной линии.


                                          А все что вы выше написали — не имеет ничего общего с действительностью.

                                            0
                                            У вас 2^65 возможных данных на приёме, из которых корректны только два. (кстати, не факт что равноудалённые, но это и не важно).

                                            Да, остальные будут отброшены автоматически на приемной стороне по причине детектирования ошибки CRC-64. В итоге вероятность принять сбойную команду управления можно оценить как 2/(2^64), это очень мало. Если передавать по 1 сообщению в секунду, по линии что искажает каждый второй бит, сбойный пакет ожидается что примется в течение 576929507528,29 лет, что выше возраста вселенной.

                                            Не 50%/264, ошибки, а 1/265 что вообще хоть что-то будет приятно приёмником, так как црц не даёт возможности восстановить в случае ошибки, только информацию о наличии ошибки.


                                            264 раза отправить данные вообще не проблема, речь то о канале где сигнал и шум имеют одинаковую вероятность, или по сути энергию. А тут достоверно передаем данные используя всего лишь простую контрольную сумму, ни каких сложных алгоритмов восстановления. Простым дублированием информации такого не добиться. Не будет столь высокой достоверности переданных данных.

                                            Передать при шуме выше сигнала можно только статистическими методами. Например — передача единицы как меандра со скважностью 3, а нуля как меандра со скважностью 7. Добавляем заголовок со скважностью 5 для синхронизации и замера базовой линии. Вот это даст возможность принять даже на зашумленной линии.


                                            1. Высока избыточность, расширение спектра в 3-7 раз.
                                            2. Не высока вероятность передачи данных, но растет по мере удлинения количества данных, длительности логического 0 и 1.
                                            3. Высока вероятность ошибки в переданных данных.
                                            4. Нужна все равно контрольная сумма типа CRC32 или CRC64

                                            Вы описали алгоритм который применяют простые модемы. Но эффективность такого метода под вопросом. Есть автокорреляционные последовательности для подобного, требующие минимальной энергии для передачи бита данных, очень абстрактно
                                            moluch.ru/archive/108/25965

                                            И наглядно на Хабре, автокорреляционная функция. Коды Баркера

                                            Вообще интересная тема. Но следующий шаг в обсуждении это очень крутой матан с интегральными оценками энергий сигнала, шума, эффективности, спектра )
                                              0

                                              1/2^65, а не 1/265. Хабр съел две звёздочки.
                                              Так вот. Сколько надо пакетов передать, чтоб хоть один дошёл?

                                                0
                                                Каждый бит данных удваивает число попыток передачи данных. Чем больше пакет, тем сложнее по экспоненте. Тут да, 50% ошибка на бит это перебор, надо снижать сложность условий. Хотя бы 50% на байт или на весь кадр данных.

                                                Если линия шумная, то выход один, повторять кадр с данными N раз (или каждый бит сразу повторять N раз), причем с преамбулой, чтобы алгоритмом хоть как-то «зацепится» за начало данных. Далее по мере получения данных N раз полезный сигнал суммируется линейно, а шум не так интенсивно. Через 5-10 итераций уже можно суммировать биты, приходящиеся на одно положение и считать контрольную сумму.
                                                По сути просто увеличиваем энергию полезного сигнала, чтобы он стал статистически выделяться на фоне шума. Ценой более длительной передачи данных…
                                                  +1

                                                  50% на байт? Выкидываем в мусор crc и берём нормальный код коррекции, который позволит исправлять 3, детектировать 4 бита ошибки. Получим гарантию доставки или фильтрацию ошибки на 15 битах вместо 72 для передачи байта.
                                                  Причем напомню, что передача 72 бит будет включать в себя вероятность изменения до 18 бит, то есть до 12х байт. Вы точно уверены что crc64 это хороший метод для раздувания?
                                                  Сколько бит ошибки на пакет он позволит гарантированно оценить и сколько — исправить?

                                                    0
                                                    CRC не исправляет же ошибки, но можно из нескольких сбойных пакетов собрать один правдоподобный, выше уровень шума, больше нужно передавать информации.

                                                    Детектировать же с 64 битами нет проблем.
                                                    1-бит CRC детектирует 50% ошибок, гарантия обнаружения 1 сбойного бита

                                                    8-бит пропустит 1/256, гарантия обнаружения до 8 бит сбойных

                                                    16-бит 1/65536

                                                    32-бит 1/миллиарду

                                                    64-бит 1 / 2^64 (можно за 0 считать в обычных условиях, я моделировал и не дождался ни одной пропущенной ошибки при 10^12 пакетах примерно такой порядок величины), по сути гарантия обнаружения любого числа сбойных бит, от 1 до триллиона. «Сила» контрольной суммы растет экспоненциально с увеличением разрядности.

                                                    По коду коррекции ошибок, нужно разбираться. У нас нет гарантии того, что изменено всего 3 бита информации, могут быть изменены все сразу. В итоге 4 сбойных бита пройдут с высокой вероятностью, существенно выше 1/16, на длинных пакетах 50%? Это весьма символическая защита.
                                                      0
                                                      Нет, вы не правы, Прочитайте учебник еще раз.
                                                        –1
                                                        Я моделировал CRC-64 еще когда статью на Хабр писал, не дождался ни одной ошибки за многочасовое тестирование. Если вы о надежности CRC-64. Если в контексте статьи изначальной то 0 сбоев будет при любом виде тестирования.
                                                          0
                                                          Хорошо. Скажите, пожалуйста, сколько бит в CRC-64 меняется когда вы меняете один бит входных данных?
                                                            0
                                                            Меняются все данные, пересчитаваются заново. Но, если искать отличия, то будет 50% измененных бит, в силу вероятности совпадения старого бита и нового. Матожидание изменения 32 бит из 64 бит. Минимум 1 бит, максимум все биты, в среднем 32 бита.
                                                              0
                                                              И снова нет.
                                                                0
                                                                Интересно вашу гипотезу узнать…

                                                                crccalc.com
                                                                CRC 32
                                                                1 -> 0x83DCEFB7 -> 10000011110111001110111110110111
                                                                2 -> 0x1AD5BE0D ->
                                                                11010110101011011111000001101

                                                                делаем XOR
                                                                10011001000010010101000110111010

                                                                убираем нули, получаем количество отличающихся бит
                                                                1111 1111 1111 11
                                                                14 бит отличается, 18 бит совпадает. Примерное 50% бит CRC поменялось при изменении исходных данных на 1 бит. Могу смоделировать, но непонятно зачем, и так всё очевидно. Если бы CRC не менялась максимально возможно при изменении каждого бита данных, она бы потеряла свою ценность.
                                                                  0
                                                                  Правильный ответ — в зависимости от полинома.

                                                                  Та же классическая CRC-16 с полиномом 0x8005 даёт следующее:
                                                                  FF => 0x4040
                                                                  FE => 0x8081
                                                                  как видите, в результате изменился ОДИН бит плюс сдвиг на один бит.

                                                                  Но посмотрим иначе. В целом, CRC-N сконструированы так, чтобы детектировались изменение до N бит в сообщении, включая саму контрольную сумму.
                                                                  Когда у нас сообщение 8 бит, а контрольная сумма 64 бита, мы должны мочь детектировать изменение до 64 бит из этих самых 72 бит сообщения. Вопрос. Нафига?

                                                                  Если у нас линия с ожиданием до 1 ошибки на байт (по крайней мере это последнее вами предложенное было), то нам достаточно 2 бит контрольной суммы на эти самые 8 бит данных, чтобы отлавливать эту ошибку!
                                                                  4 бита дадут возможность детектировать ситуацию когда на эти 12 бит передачи было две ошибки (возможная ситуация) и корректно принять пакет в котором будет одна ошибка (которая там как раз и ожидается).
                                                                  Если мы возьмём код в 6 бит, это нам даст пакет в 14 бит, на который почти точно будет 1 ошибка, возможно две — а у нас достаточно информации чтоб исправить их.

                                                                  Итак, вопрос, нахрена нам тут 64 бита контрольной суммы, которые гарантируют вероятность ошибки в (1-0.5^9)=99.8%?
                                                                  Ну то есть мы добавляем контрольную сумму, и вместо гарантированной доставки получаем гарантированную недоставку.
                                                                  Прекрасное решение! Осмысленное и очень прям нужное!
                                                                    0
                                                                    > Нафига?

                                                                    Очевидно, 64/72 больше, чем 16/32, и много больше, чем 16/17. Вероятность прохождения сбойного пакета, соответственно, меньше.

                                                                    Вы как определяете размер необходимой КС? Какой процент доставки (и процент доставки недостоверного пакета) осмысленный и очень нужный?

                                                                    > (1-0.5^9)=99.8%?

                                                                    У вас «линия с ожиданием до 1 ошибки на байт» или " линия с ожиданием в среднем 1 ошибки на байт"?
                                                                      0
                                                                      Речь выше шла про 1 ошибку на байт в среднем.
                                                                      64/72 много меньше чем 16/17 :)

                                                                      Но еще раз — большая CRC бесполезна. Как и любая свертка она нужна чтобы проверить наличие ошибок в большом пакете, и она должна быть чуть-чуть больше чем ожидаемое число ошибок. Всё сверх этого лучше потратить на коды которые позволят восстановить ошибки, иначе мы тратим место впустую.

                                                                      Ну как впустую, мы увеличиваем вероятность недоставки в принципе.

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

                                                                      Увеличение длины контрольной суммы снижает вероятность пропуска каких-то астрономических ситуаций, но при этом увеличивает вероятность возникновения этих самых ситуаций.

                                                                      Когда у нас 8 бит данных, нам не надо чтоб мы могли отловить изменение 64 бит!
                                                                        0
                                                                        Увеличение длины контрольной суммы снижает вероятность пропуска каких-то астрономических ситуаций, но при этом увеличивает вероятность возникновения этих самых ситуаций.

                                                                        вот это я и пытался в соседней ветке сказать
                                                                          0
                                                                          > 64/72 много меньше чем 16/17 :)

                                                                          Я не про результат деления, ну да не суть

                                                                          > она должна быть чуть-чуть больше чем ожидаемое число ошибок.

                                                                          Но тут то максмальное, а не среднее?

                                                                          > Когда у нас 8 бит данных, нам не надо чтоб мы могли отловить изменение 64 бит!

                                                                          Если у вас бывает изменение 64 бит, то с передачей 8 бит у вас будут проблемы.

                                                                          Хотя да, коды с восстановлением — это хорошо, если применимо. Но тогда вам надо иметь кроме 64 поврежденных минимум 64 неповрежденных бита в пакете, т.е. всего 128+
                                                                            0
                                                                            Увеличение длины контрольной суммы снижает вероятность пропуска каких-то астрономических ситуаций, но при этом увеличивает вероятность возникновения этих самых ситуаций.

                                                                            Вероятность роста этих ситуаций линейная (это тоже плохо безусловно), а повышение надежности идет по экспоненциальному закону, каждый бит CRC снижает вероятность пропущенной ошибки в 2 раза.
                                                                            Далее разрядность CRC выбирается по ситуации. В RS-485 Modbus 16 бит, что иногда и мало, а в Ethernet кадры с 32-битной CRC (ранее на пассивных хабах вероятны были коллизии), ну так же там и кадры килобайтные, CRC особо не увеличивает нагрузку.
                                                                              0
                                                                              Но еще раз — большая CRC бесполезна. Как и любая свертка она нужна чтобы проверить наличие ошибок в большом пакете, и она должна быть чуть-чуть больше чем ожидаемое число ошибок.

                                                                              В некоторых случаях полезна. Например гипотетический случай команды на самоликвидацию оборудования какого-то на шумной линии, например радиоканале. Ложное срабатывание не допустимо в принципе. Прикидываем, что вероятность ложного срабатывания недопустима свыше 1/2^64 и выход напрашивается применить 64-битную контрольную сумму, даже при передаче 1 бита полезных данных.
                                                                              Обратный пример мигание цветомузыкой на мероприятиях, есть специфический протокол
                                                                              ru.wikipedia.org/wiki/DMX-512
                                                                              и по моему там нет вообще никакой контрольной суммы, мигнет лампочка не в такт, этого ни кто не заметит. Зато данные передаются максимально быстро, это главное.
                                                                                +1
                                                                                Прикидываем, что вероятность ложного срабатывания недопустима свыше 1/2^64 и выход напрашивается применить 64-битную контрольную сумму, даже при передаче 1 бита полезных данных.
                                                                                но вероятность ненулевая. вам вроде как объясняют что эти 64 бита можно потратить полезнее.
                                                                                  0
                                                                                  но вероятность ненулевая. вам вроде как объясняют что эти 64 бита можно потратить полезнее.

                                                                                  «Полезнее» зависит только от задачи. Если требуется максимальная защита от приема сбойного кадра данных, то я не знаю, что может быть полезнее. Другие приемы дают другие преимущества, но надежность существенно снижают, вероятности пропуска сбойного кадра 1/2^64 они не дадут.
                                                                                    0
                                                                                    Если нужна максимальная защита от приёма сбойного кадра, то лучше его вообще не отправлять, будет 100% защита.
                                                                                    А так, почему ограничиваемся жалкими CRC64? Давайте sha-512!
                                                                                      0
                                                                                      А так, почему ограничиваемся жалкими CRC64? Давайте sha-512!

                                                                                      CRC64 вполне нормальный вариант. CRC32 может давать коллизии, например если передаем пакеты радиоканалу типа WiFi, при 10 000 пакетах в секунду содержащих ошибку, сбой будет происходить каждые 27 часов.
                                                                                        0
                                                                                        не путайте будет и может.
                                                                            –1
                                                                            как видите, в результате изменился ОДИН бит плюс сдвиг на один бит.

                                                                            При чем тут сдвиг?
                                                                            Изменилось 5 бит из 16, чуть менее половины. Сдвиг это уже не имеет значения. Еще может быть зеркальное отражение полубайта, инвертирование четных бит и т.п. Опять же это единичный случай, по хорошему нужна статистика, а она, скорее всего, даст матожидание изменения 8 бит из 16.

                                                                            Итак, вопрос, нахрена нам тут 64 бита контрольной суммы, которые гарантируют вероятность ошибки в (1-0.5^9)=99.8%?
                                                                            Ну то есть мы добавляем контрольную сумму, и вместо гарантированной доставки получаем гарантированную недоставку.
                                                                            Прекрасное решение! Осмысленное и очень прям нужное!


                                                                            Именно так, хорошее, рабочее решение. Пусть дойдет 2 пакета из 1000, но это гарантированная информация. По вашему методу будет 1-2% мусора в информации. Я не могу представить себе систему, в которой при обмене данными попадает 2% рандомных данных.
                                                                            Про управление реактором вообще речи нет.
                                                                            И при получении телеметрии от датчика температуры будет рваный шумный график, не отследишь там минимум за сутки или максимум и постоянно будут всплывать ошибки типа аварийное значение параметра (вызывайте пожарных и МЧС), а потом раз и опять нормальное показание. Даже статистику скучную не собрать.
                                                                            Могу допустить что 64 бита избыточно, возможно что хватит 48 бит. Но предпочел бы перестраховаться и вообще не думать о вероятности попадания рандомных значений в систему.
                                                                            Есть способы оптимизировать протокол, если нужно чтобы проходило более чем 2 пакета из 1000, например повторять один и тот же кадр данных 20 раз и на приемной стороне статистически анализировать по каждому биту и собирать кадр из шумоподобного сигнала, ориентируясь на результат, совпадение контрольной суммы. Есть конечно и более эффективные алгоритмы, но то утверждать что длинна контрольная сумма не нужна тоже нельзя. Все таки самый простой способ обеспечить «астрономически» точную передачу данных, пусть и высокой ценой.
                                                                              0
                                                                              отвечаю на «причем тут сдвиг».

                                                                              передача по последовательному каналу (rs-XXX):
                                                                              11100100000011...
                                                                              ^^^ линия спокойная
                                                                                 ^ стартовый ноль
                                                                                  ^^^^ =4
                                                                                      ^^^^ =0
                                                                                          ^^ стоповая единица
                                                                              


                                                                              а теперь происходит сбой…

                                                                              111101000000110010000001
                                                                              ^^^ линия спокойная
                                                                                 ^ сбойный бит, единица
                                                                                  ^ воспринимается как стартовый ноль
                                                                                   ^^^^ = 8   
                                                                                       ^^^^ =1, воспринята стоповая единица
                                                                                           ^ и после неё воспринято как нормальный стоп
                                                                              


                                                                              Оппа, и 0x40 превратилось в 0x81 за один бит ошибки.
                                                                                0
                                                                                Оппа, и 0x40 превратилось в 0x81 за один бит ошибки.

                                                                                Тем не менее CRC эту ошибку распознает успешно, что и требовалось от нее.
                                                                                Но тема интересная, с учетом таких ошибок, нужно выбирать полином устойчивый к смещению данных. Что повышает ценность статьи, так как там есть тестирование «режима смещения» принимаемых данных.
                                                                                  +1
                                                                                  Статья оперирует байтами данных, полностью упуская из рассмотрения битовые сдвиги, возможные потери синхронизации и множество других реальных ошибок в линиях связи.
                                                                                  Плюс «разовая» ошибка на больших скоростях легко и просто превращается в 5-6 бит последовательно занулённых или объедениченных. Хотя «шило» было одно.

                                                                                  Плюс такой «сбой» синхронизации может легко и просто вызвать сдвиг на несколько байт подряд.
                                                                                  Чтоб такого не было, используют 2 стоп-бита (а то и еще и бит четности как дополнительный стоп-бит).
                                                                              0
                                                                              В целом, CRC-N сконструированы так, чтобы детектировались изменение до N бит в сообщении, включая саму контрольную сумму.

                                                                              не согласен.


                                                                              самое похожее свойство CRC, которое приходит в голову: CRC-N может определить инвертирование N последовательных бит.


                                                                              Посмотрите у Купмана про те же 16-битные коды: вы видите хоть один код с HD>16 (то есть определяющий до 16 бит ошибки)?
                                                                              https://users.ece.cmu.edu/~koopman/crc/index.html
                                                                              Лучшее, что есть применительно к пакетам длиной 7 байт — HD=6 (то есть код гарантированно детектирует до 5 битовых ошибок)

                                                                                0
                                                                                Верно, чет я о другом думал когда писал. Посыпаю голову пеплом.
                                                                                Впрочем, ситуацию это не меняет — мы удлиняем сообщение в разы больше чем исходное, тем самым доводим до непередаваемого вообще
                                                      0
                                                      с 32-битной командой (например задаем напряжение для ЦАП какого-то исполнительного механизма), 64-битная контрольная сумма нормальный вариант

                                                      ну да, конечно. имеет пакет 32 + 64 бит. полезные данные имеют 2^32 вариантов. а какое количество вариантов имеет 64-битная контрольная сумма в данном пакете?
                                                        0
                                                        Такое же. Из всего подмножества 2^96 вариантов данных валидными будут 2^32, остальные будут отброшены по ошибке CRC.
                                                        Еще интереснее предельный случай с 1 передаваемым битом и CRC64, из подмножества 2^65 данных, валидными будут всего 2, лог 0 и лог 1 с контрольной суммой. Очень похоже на коды Баркера и автокореляционные функции в каком-то виде, пусть и не самом оптимальном.
                                                          0
                                                          накладываем на это вероятность ошибки и понимаем что лишние 32 бита контрольной суммы не только бесполезны, но и вредны
                                                            0
                                                            Нету «лишних» 32 бит, каждый бит CRC в 2 раза снижает вероятность получения сбойной информации.
                                                            Если применить CRC32 вместо CRC64, то алгоритм пропустит примерно из миллиарда сбойных пакетов один. А CRC64 один из 2^64, о таком можно не беспокоится, в связи с ограниченностью срока существования вселенной.
                                                              0
                                                              у вас вероятность сбойных пакетов повышается с увеличением пакета. при этом возможных комбинаций контрольной суммы при 64 битах получается больше чем комбинаций полезных данных
                                                                0
                                                                вероятность сбойных пакетов повышается с увеличением пакета

                                                                Вероятность сбойных пакетов повышается линейно, но вероятность приемнику распознать сбойный пакет повышается по экспоненте.
                                                                Пример
                                                                контрольная сумма (КС) 0 бит, вероятность принять 1 бит данных максимальная 100%, но и распознать что на линии ошибка невозможно, в случае возникновения ошибки примется 100% ошибочных пакетов.
                                                                КС 1 бит, вероятность принять данные уже ниже (зависит от вероятности помехи), и вероятность пропустить ошибку 50%.
                                                                КС 2 бита, вероятность пропустить ошибку 25%

                                                                КС 64 бита, вероятность пропустить ошибку 1 / (2^64)

                                                                На самом деле чуть ниже, из-за вероятности ошибки в КС, но это нужно, чтобы в среднем ошибка инвертировал бит данных и 32 бита из 64 бит контрольной суммы, это маловероятное событие. Пусть даже в 2 раза снижается надежность КС это 1 / 2^63, исчезающе малая вероятность, допустимая только теоретически.

                                                                По вероятности ошибки в кадре данных. Если передаем 1 бит без КС, пусть вероятность ошибки 0.1%, 2 бита — вероятность ошибки 0.2%… 65 бит 6.5% (ну примерно для оценки порядка величны). Но это плата за снижение вероятности ошибки в принятых данных до величин порядка 1/ 2^64
                                            +1
                                            Кстати, спасибо за статью, в свое время очень интересно было ее почитать!
                                            +4
                                            CRC не должен использоваться для идентификации пакета. Это для проверки целостности после идентификации пакета (полем длины в заголовке, маркером конца, форматом, задержками итд). Такая проверка не должна встречаться (если нет ошибки в данных), данные предыдущего пакета должны быть уже обработаны и исключены.
                                              0
                                              Я это прекрасно понимаю, но систему проектировал не я, от меня требовалось найти и исправить ошибку.
                                                +3
                                                Вы её нашли, но не исправили. Вы её замаскировали, сделали более редкой, про неё будут думать что она исправлена, а потом что-то долбанёт. Взорвётся или сгорит. Вас скорее всего не найдут, спишут на техническую неисправность, но кто-то потеряет тонны денег а кто-то, возможно, жизни.
                                                  0
                                                  Ок, и каким образом я должен был ее исправить так, чтобы исключить ее полностью? У Вас есть пути решения, или Вы просто за все хорошее и против всего плохого?
                                                    0

                                                    Любым способом отделить сообщения в протоколе. Задержкой, маркером начала и конца, маркером начала с префексированием длиной. Просто разделителем, наличие которого явно исключено из допустимых значений содержимого пакета

                                                      +1
                                                      введение дополнительного байта-заголовка свело количество ошибок до недетектируемого уровня, но этого мне показалось мало. Я решил проверить, насколько различные виды 16-битных контрольных сумм отличаются друг от друга в реальных условиях.
                                                      Длина у всех пакетов одинакова. При отсутствии заголовка в нулевой позиции контрольная сумма теперь вообще не считается, пакет отбраковывается.
                                                      Дополнительно к этому продублировал данные в рамках пакета для особо важных (было место). Время работы наших устройств на отказ — порядка сотен часов.

                                                      Ну и вообще, речь не об этом, речь о том, что контрольные суммы даже в рамках CRC16 довольно неодинаково детектируют ошибки, и, зная структуру передаваемых данных и возможные причины их повреждения, вполне можно улучшить результаты детектирования ошибок простой сменой контрольной суммы.
                                                        0
                                                        Так же важно знать тип помех на линии. Это или инвертирование одиночного бита, или сразу группы бит. Или рассинхронизация приемника и передатчика и пропадание бита данных, или наоборот, появление лишнего бита данных. Тут уже нужен эксперимент с реальной линией связи.
                                                        Если на линии появляются только одиночные ошибки, то хватит и CRC1 он же бит четности/нечетности, аппаратно поддерживается на уровне UART интерфейса. И наоборот, в «тяжелых» случаях без CRC32, CRC64 вообще ни как.
                                                          +1
                                                          > контрольные суммы даже в рамках CRC16 довольно неодинаково детектируют ошибки

                                                          0.010% против 0.024%? А какая практическая разница?
                                                            +1
                                                            Мне кажется, что более уместно не долями процентов оперировать, а разами. Снижение вероятности ошибки в 2,5 раза минимальными усилиями — это плохо?
                                                              +1
                                                              То есть раньше у вас раз в 5 секунд, а теперь раз в 12? Ну поздравляю, чо.

                                                              И это ещё если вам вообще повезло с попаданием алгоритма в специфический тип ошибок у вас (а этого вы не знаете), а то может и наоборот. Так что пока вы даже не измерили и не подтвердили практикой у себя эти 2.5 раза, то результат — преждевременная оптимизация с теоретическим улучшением в пределах погрешности.

                                                              И ничего в этом хорошего. Зато движуха.
                                                                0
                                                                Исходный код же открыт. Ничего не мешает улучшить эксперимент. Я бы посмотрел на ошибки по мере увеличения уровня шума в линии связи, самый первый эксперимент, но более развернутый.
                                                                Кроме CRC часто применяется просто сумма побайтовая, протокол DCON, например, там эффективность алгоритма в разы ниже, чем у CRC. Тоже легко проверить экспериментом.
                                                                  0
                                                                  Вы не поняли. Если у автора при передаче сейчас происходят в 90% ошибки класса Roll packet, то CCITT далеко не оптимальный выбор.

                                                                  Я же не знаю какие ошибки реально происходят на линии автора, так что ничего улучшить не могу. И даже он не знает, так что выиграл ли он от перехода на CCITT — загадка.

                                                                  А при таких вводных, ковыряние в исходниках — полировка сферического коня в вакууме
                                                                    0
                                                                    Выиграл в большей степени время, так как CCITT — единственно доступный аппаратный алгоритм в использованном контроллере. И так как ошибка с накатыванием была исправлена другими методами, большую актуальность получили повреждения пакетов в результате физических коллизий.
                                                                      0
                                                                      То есть исследование даже на переход на CCITT не повлияло…
                                                                0
                                                                2,5 раза так же соответствуют 1 биту избыточных данных. «Плохая» CRC16 на самом деле эквивалентна CRC15.
                                                                А если считать контрольную сумму по просто XOR, вероятность ошибки растет в десятки и сотни раз.
                                                                На практике обычно требуется более существенное снижение вероятности ошибки, и, соответственно переход на CRC32 и более высокие.
                                                    0
                                                    После целой простыни комментариев, Наконец-то кто-то это написал :)
                                                    Если можно изменить алгоритм контрольной суммы, то наверно можно изменить и весь протокол? ENQ?
                                                      +1
                                                      Почитайте внимательно начало статьи. Протокол был изменен, все остальное — попытка понять, почему контрольные суммы дают настолько отличающиеся значения для количества ошибок.
                                                        –1
                                                        все остальное — попытка понять, почему контрольные суммы дают настолько отличающиеся значения для количества ошибок


                                                        Так вы этого не только поняли, но даже не пытались. Вы только экспериментальным путём установили факт (научной новизны в котором нет).
                                                          +1
                                                          А я и не знал, что на хабре все статьи требуют наличия научной новизны. Извините!
                                                            0
                                                            Я не сказал, что ваша статья тут неуместна, но

                                                            1) если вы хотели для себя уяснить наличие проблемы с CRC — достаточно было спросить у гугля что-нибудь про crc collision rate. Ну вот про Modbus я нашёл за три секунды, это сильно быстрее, чем проверять самому;

                                                            2) если вы сами себе ставили задачу «понять, почему», то вы с ней не справились.
                                                              0
                                                              И что говорит Ваша ссылка о зависимости надежности контрольной суммы от структуры данных? Про расчет для случайного набора данных я и сам прекрасно знаю.
                                                                0
                                                                Так ваша статья об этом тоже ничего полезного не говорит — знание, что для вот такой ошибки CCITT хуже, а для другой — Xmodem, не имеет ценности, потому что применительно к вашей задаче единственная разумная формулировка — это «оба хуже».
                                                    +1
                                                    Модбас, который вы слегка изменили, предполагает помимо контрольной суммы CRC16, контроль битов четности в каждом байте + маркеры начала/конца пакетов в виде временных задержек. Может не стоит изобретать велосипед, а использовать проверенные временем протоколы?
                                                      0
                                                      Контроль битов четности каждого байта опционален. Сколько использовал промышленных контроллеров, только в одном был жестко установлен бит четности edge/mark, в остальных none. Использование битов четности эквиваленто увеличению разрядности CRC на 1 бит, эффективность невысокая, а добавляет ~10% избыточных данных в канал.
                                                      +1
                                                      Обычно в таких случаях (при использовании именно UART) проще всего делать пакеты 7-разрядных данных, в первом байте установлен 8-й бит, формирующий начало пакета, значение первого байта представляет тип пакета (из которого понятна длина), в двух последних — CRC14. Соглашусь с предыдущим замечанием, что пакеты нельзя идентифицировать по CRC.
                                                        0
                                                        Тест shuffle крайне странный, потому что очевидно, что для числа заменённых байтов больше 16, никакой алгоритм не может показать эффективность выше 50%. Я бы ограничил верхнюю границу числа заменяемых битов 16ю.

                                                        А ещё, чисто для интереса, можно было бы попробовать криптоалгоритмы. Например, первые 2 байта от md5. Они себя лучше покажут, чем спец.алгоритмы для CRC16 или хуже?
                                                          +1

                                                          Так же покажут.

                                                            0
                                                            Да, в случае с линией RS-485 и подобных самый реалистичный сценарий это Shuffle режим. Соответственно хотелось бы видеть Shuffle 1 бит, Shuffle 2 бит и так до Shuffle 16 бит, Shuffle нормально распределенный, Shuffle равномерно распределенный.
                                                            Кроме сложно алгоритма криптографического, на основе сети Фейстеля например, есть простые эффективные алгоритмы на основе операции умножения, я их тестировал, прекрасный результат, причем аппаратная поддержка это операция умножения habr.com/post/278171
                                                            0
                                                            Это очень маловероятно, но некоторые из эмуляций повреждений пакетов могут не изменить изначальные данные. Самый простой пример: замена байта на ноль если байт изначально равен нулю. Я мог и пропустить, но у вас вроде нет проверки что «повреждение» по натсоящему что-то изменило.
                                                              0
                                                              Вот эта функция: compare_buf.
                                                              Вызывается в каждом методе. А потом в цикле вот:
                                                              if (!methods[m].fn(packet))
                                                              continue;
                                                              +1
                                                              Несложно сообразить, что
                                                              • при неприводимом полиноме (а популярные CRC полиномы не являются неприводимыми)
                                                              • при случайных данных

                                                              вероятность ложного приема c CRC16 будет
                                                              1/(2^16)= 0,0000152587890625 или
                                                              при скорости 9600 интервал ложного приема
                                                              (2^16)/9600=6,82 секунды

                                                              Большее значение интервала ложного приема говорит о том, что данные коррелированны. Меньшее значение говорит о короткой последовательности образуемой полиномом CRC, короче дерьмовый полином.
                                                                0
                                                                Т.е. вместо того, чтобы исправить алгоритм приёма данных была сделана попытка замаскировать проблему. Печально.
                                                                  0
                                                                  Интересно, где Вы это увидели?
                                                                    0
                                                                    К сожалению, в Вашей заметке и увидел. От того, что Вы сменили алгоритм формирования CRC на другой, что изменилось?
                                                                      0
                                                                      Прочитайте еще раз. Проблема была устранена добавлением заголовка пакета.
                                                                      А смена полинома — просто потому что ничего не стоит.
                                                                        0
                                                                        Самоуспокоение. :)
                                                                          0
                                                                          Не совсем. Полиномы действительно разные.
                                                                          Правда, они и заточены для разного, но кто уже упомнит? :D
                                                                            0
                                                                            Вы вот реально думаете, что проблема решалась абы как, не глядя? Заголовок уже исключал все возможные причины слияния пакетов, так как структура пакета была действительно крайне неудачной, с большим количеством нулей в теле. Помимо этого я еще и продублировал важные данные вместо этих нулей, а уж смена CRC — это просто для души, собственно, об этом и была статья, сама проблема и ее решение просто для затравки.
                                                                    0
                                                                    Имхо, было бы любопытно отнормировать количество ошибок к идеальной 16-битной контрольной сумме — у которой ошибки возникают ровно каждый 65536 раз.
                                                                    У меня получилось, что на этом тесте реальные алгоритмы пропускают в 6..15 раз больше ошибок, чем этот «сферически вакуумный».
                                                                    Занятная цифра, надо будет её запомнить…
                                                                      0
                                                                      Byte injection наоборот, в 1.5 раза меньше пропустил ошибок, чем должен теоретически, на первый взгляд.
                                                                      Тут многое зависит от алгоритма по которому ошибка имитируется.
                                                                        0
                                                                        О, прошу прощения, я с арифметикой напутал.
                                                                        100 млн. — это не суммарная цифра, это каждый тест запускался 1e8 раз. Т.е. вывод «CRC хуже идеального хэша на порядок» неверный. Хуже только в два раза в самом худшем случае. Ок, дядьки-математики, которые это когда-то придумали, реабилитированы :-)
                                                                      0
                                                                      Не надо было изобретать велосипед.

                                                                      Берете обычный HDLC
                                                                      Начало и конец пакета префиксируется байтом 7E (старт-стоп).
                                                                      внутри пакета 7E заменяется на 7D 5E, 7D на 7D 5D.
                                                                      перед концом CRC16-CCITT (просто потому что так заведено)…
                                                                      Далее длинна пакета внутри известна… Битые отбрасываете по критерию длинны и по критерию не соответствия CRC16. Это десятилетиями работает в миллиардах приложений.

                                                                        0
                                                                        длина пакета неизвестна, если есть раздувающие замены.
                                                                          +1
                                                                          Кого ж такие мелочи уже волнуют. Тем более, что по сути вышел тот самый велосипед — уникальный байт-заголовок и CCITT в конце.
                                                                            0
                                                                            При проектировании этого можно избежать используя уникальный «адрес» в рамках того же HDLC исключительно для пакетов длинна которых может быть неизвестна и другие уникальные адреса для пакетов фиксированных известных длин.
                                                                              0
                                                                              Пардон, как это неизвестна? В том и суть, что сканер канала собирает кадр, откатив все замены, а затем передает его парсеру, который уже говорит — «фуфуфу, длина не та, и адрес странный, а уж про CRC вообще молчу». Если кадр собрать не удалось — ок, ошибка кадрирования, сбрасываем канал до следующего стартового байта.
                                                                            0
                                                                            Автор просто сделал классическую ошибку, к-рую часто делают начинающие. Типа, а зачем нам заголовок вообще, если есть КС? Тут ошибка метедологическая: если вы хотите заменить заголовок на КС, то нужно переходить к свёрточным кодам. А тут попытка вместо свёрточного кода применить блочный циклический, да ещё и неполноценный. Тут даже не надо знать ничего про «полиномы над полями Галуа», просто элементарную логику включить: что даёт второй контрольный бит в данном случае в сравнении с обычным битом чётности? Да мало что даёт, по-сути. И, соотвественно, нарваться на комбинацию, когда два куска пакетов (с точностью, кстати, до кратности ошибки) дают правильную двухбитную КС — элементарно. Даже странно, что это только раз в 5 минут происходит.
                                                                              0
                                                                              К автору это отношения не имеет, автор разгребал чужие ошибки.

                                                                            Only users with full accounts can post comments. Log in, please.