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

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

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

04.11.2018 16:14

Polaris99 113 12100 Источник

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

У нас имеется устройство, которое осуществляет интенсивный обмен по внутренней шине 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, в большей степени потому, что ее реализация была доступна в аппаратной части используемого микроконтроллера.

Комментарии (113)

cheblin
04.11.2018 20:24
#19323424
как низко пал… Modbus
1. Anton131313
  06.11.2018 01:19
  #19326606
  Причем тут modbus?

netricks
04.11.2018 20:59
#19323502
+3
Насколько хороша повторяемость этого эксперимента? Я имею ввиду, получу ли я схожие результаты, если прогоню еще 100 000 000 пакетов? Может это просто дикая дисперсия?
1. Polaris99 Автор
  04.11.2018 21:14
  #19323524
  Все достаточно повторяемо
  1. Inanity
    04.11.2018 21:34
    #19323574
    Известно, что числа, полученные остатком от деления rand(), вообще говоря имеют плохое равномерное распределение. Хотя с другой стороны я не возьмусь утверждать, что результат сильно изменится, если взять генератор получше, но было интересно исключить этот фактор.
    
    olartamonov
    05.11.2018 00:25
    #19323864
    +3
    Это, на самом деле, не играет большой роли.
    
    Штука, у которой гарантированно не больше 65536 уникальных значений, в любом случае плохо подходит для того, для чего её авторы поста использовали. Алгоритм, по которому она вычисляется, здесь влияет только на то, насколько быстро вы встретитесь с этой проблемой.
    
    Авторам повезло, они взяли плохой алгоритм и встретились быстро.

olartamonov
04.11.2018 21:28
#19323558
+9
Мне так сдаётся, что подсчёт числа коллизий на полностью случайных данных при условии, что у контрольной суммы совершенно точно никак не больше 65536 возможных значений, является задачей чисто умозрительной и не требующей написания какого-либо кода, а дизайн системы, в котором на отсутствие таких коллизий полагались, — странным.

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

Некоторый интерес может представлять собой проверка, действительно ли у всех представленных алгоритмов 65536 возможных значений CRC16, и насколько равномерно они распределены — это сразу позволит отделить хорошие алгоритмы от плохих, без привязки к конкретным данным.
1. SegreyBorovkov
  04.11.2018 23:21
  #19323768
  +1
  не согласен. Алгоритм должен быть еще стоек к некоторым модификациям данных. К примеру — изменению порядка байтов. Если в качестве crc взять sum(X) % 65536, где X — вектор из двухбайтовых значений, то он будет давать достаточно ровное распределение, но порядок двухбайтовых блоков можно будет менять как угодно.
  1. olartamonov
    04.11.2018 23:52
    #19323812
    Это так для совсем простых алгоритмов, вычислять это специальной программой в общем не требуется, можно просто указать.
  1. ZyXI
    04.11.2018 23:57
    #19323822
    +3
    Зачем? Я не очень представляю себе, как можно реализовывать что?то поверх протокола уровня UART и получить случайное изменение порядка байтов (если только у вас нет ошибки в программе). Получить мусорный бит в середине на том же SPI при помехах на линии тактирования — можно. Получить инверсию бита из?за помех — можно. Получить байт(ы) посылки от другого устройства между байтами посылки от первого — можно, но такие проблемы разруливаются не CRC, если только инверсия произошла не при передаче адреса отправителя. А что может привести к изменению порядка байтов кроме ошибки в программе? У того же TCP ожидается произвольный порядок приёма, но пакетов и по очень хорошей причине.
    
    SegreyBorovkov
    05.11.2018 01:23
    #19323952
    +1
    Предположим, что CRC — XOR данных. К примеру, двухбайтовый.
    Теперь представим, что пакет содержит 6 байт. Первые два байта меняются редко, потом 2 байта данных и два байта CRC. По факту это означает, что XOR от всего пакета включая CRC должен быть 0 (ноль). Это похоже на то, что у автора? Вроде да, но там функция CRC чуть другая.
    
    А теперь смещаем окно на 2 байта вправо. Как думаете, CRC сойдется? Мне почему-то кажется, что да. Даже при смещении на 1 байт — тоже сойдется.
    
    Вот и все :-)
    
    ZyXI
    05.11.2018 01:51
    #19323994
    Хорошо, вы правы. Я почему?то решил, что вы написали про абсолютно произвольное изменение порядка, а не более конкретный циклический сдвиг — моя способность «додумать» без уточнения несколько промахнулась :)
  1. sim31r
    05.11.2018 02:18
    #19324014
    Порядок байт вряд ли может изменится в обычном канале связи. Но может произойти двойная ошибка, один бит меняется с 1 на 0, другой бит в том же месте байта с 0 на 1, и ошибка проходит незамеченной. Такое очень вероятно, и вероятность выше чем 1 к 65535. А при CRC обычной, чтобы ошибка прошла незамеченной, нужно достаточно необычные комбинации формировать. Если один бит меняется с 1 на 0, то для прохождения контрольной суммы должны изменится еще несколько бит в разных байтах в разных местах.
  1. esaulenka
    06.11.2018 01:32
    #19326614
    А мы тут что обсуждаем, пардон? CRC с различными полиномами или «в качестве CRC взять абстрактную f(x)»?
    Давайте так: CRC это циклический избыточный код (см. в википедии), абстрактная f(x) — это некая контрольная сумма (checksum). Просто, понятно, общепринято.

datacompboy
04.11.2018 21:29
#19323560
+7
Контрольная сумма она для защиты от ошибки первого рода (узнать что она была).
Почти все указанные тут по сути защищают от 1 бита ошибки.
Полиномы еще дополнительно защищают от перестановки бит, в пределах ширины.
Но таки да, всегда можно подобрать набор данных чтоб получить любую наперёд заданную CRC по любому из алгоритмов.
И таки да, перестановка байт/слов вполне может пройти незаметно для CRC.

Любой протокол обмена крайне рекомендовано завязывать на фиксированные начало и конец (или длину), а CRC использовать для проверки что принятое — не случайный шум.

ilynxy
04.11.2018 23:30
#19323782
+4
Писать связно и по-порядку несколько лениво. Но вот ключевые термины и моменты.
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.
Это даёт неплохую оценку, но, как показывает брутфорс эта оценка справедлива только для малых значений расстояний Хэмминга.
1. Polaris99 Автор
  05.11.2018 17:28
  #19325556
  Вот за эти ссылки спасибо, ведь реально автор пришел, пусть и более осознанным и подкрепленным вычислениями путем, к выводу, что не все полиномы одинаково хороши.

TimsTims
05.11.2018 01:26
#19323964
-1
но дело оказалось в другом – время от времени в буфере, где собирались полученные данные, оказывался пакет, состоящий из конца предыдущего пакета и начала следующего
Ну вот вы же нашли проблему — брались неверные данные. Правильнее было бы искать ошибку в драйвере отправки данных (ок, не в драйвере, а в коде, формирующим пакеты), понять почему так происходит, что вообще берутся данные из ненужных сейчас к отправке пакетов. А пытаться применить другой CRC16 — это как наливать всё больше воды в дырявое ведро, вместо латания дыр.
1. datacompboy
  05.11.2018 02:13
  #19324006
  Нет никакой ошибки в отправке. И на приёме нет. Есть проблема в отсутствии маркера фрейма.
  То есть пакеты идут: D0-D1-D2-D3-D4-C1-C2 где C1 и C2 — контрольная сумма.
  Определением пакета было «контрольная сумма сошлась». При этом обрабатывался циклический буфер. То есть спустя несколько байт получалось:
  D2-D3-D4-C1-C2-N0-N1
  где N0 и N1 это байты от следующего пакета, но на приёмнике они рассматриваются как CRC16 и дают схождение суммы для всего пакета.
  Что немаловероятно.
  1. sim31r
    05.11.2018 02:22
    #19324018
    Тут надо было делать 64-битную контрольную сумму, проблемы бы не было.
    
    datacompboy
    05.11.2018 02:25
    #19324020
    Достаточно добавить фиксированный байт начала пакета. В идеале — такой, который не может быть в данных. Это даст накладные расходы в 1 байт и стабилизирует систему (останутся только ошибки порядка 1 на ~1e-10 байт).
    64битная сумма (то есть 8 байт сумма на 5 байт данных, кхе кхе) создаст больше проблем.
    проще уж тогда присылать инверсные данные, всего 5 байт понадобится.
    
    sim31r
    05.11.2018 02:34
    #19324032
    64 битная контрольная сумма сделает невозможной прием сбойного пакета данных, вероятностью 1 / 2^64 можно пренебречь.
    Все остальные варианты проще программно, но повышают вероятность ошибки. Хотя если речь о 1 на ~1e-10 байт то не важно, конечно, это почти идеальная линия связи.
    Инверсные дополнительные данные тоже имеют очень высокую вероятность ошибки, по сравнению с CRC64, достаточно двойной ошибки.
    
    datacompboy
    05.11.2018 02:58
    #19324072
    Я говорю про ошибки "обработка сбойного пакета". Приём сбойного пакета возможен всегда, задача как раз его проигнорировать, иногда — ещё узнать что он вообще был.
    
    sim31r
    06.11.2018 01:51
    #19326644
    Приём сбойного пакета возможен всегда, задача как раз его проигнорировать
    
    Эту задачу решает CRC, он для этого и придуман.
    
    esaulenka
    06.11.2018 01:42
    #19326632
    Вы статью-то прочитали? Вероятность ошибки у автора не 1/2**16, а на порядок (десятичный!) бОльшая. Не, для 2**64 порядок туда — порядок сюда — уже неважно, но всё ж таки…
    
    sim31r
    06.11.2018 01:49
    #19326642
    По таблице, где тестировалось 100 000 000 переданных кадров данных с ошибкой порядок величины не распознанных ошибок как-раз 1/2^16 или 1/65536, плюс девиации в зависимости от алгоритма и типа ошибки.
    Пример 2000 не распознанных ошибок из 100 000 000 кадров это 1/50 000, что достаточно точно совпадает с теорией.
    
    Polaris99 Автор
    05.11.2018 11:06
    #19324538
    Почитайте еще раз статью, длина всего пакета с CRC16 — 7 байт, степень заполнения канала при этом порядка 70%. А теперь добавьте сюда еще 6 байт CRC64.
    
    arcman
    06.11.2018 12:37
    #19328178
    CRC64 8 же байт.
    
    Polaris99 Автор
    06.11.2018 12:45
    #19328236
    Да, но CRC16 длиной 2 байта в пакете уже есть, ее ж менять собрались

sim31r
05.11.2018 02:11
#19324004
CCITT, в большей степени потому, что ее реализация была доступна в аппаратной части используемого микроконтроллера.

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

И разрядность побайтно подбирать, 16 бит контрольная сумма может быть недостаточной, есть возможность выбрать 24 бита или 32. В идеале 64 бит, но канал связи может ограничить прохождение избыточных данных. Чем хуже канал передачи данных, выше вероятность помехи, тем больше разрядов должно быть в контрольной сумме. В самых тяжелых случаях можно избыточную информацию передавать, для восстановления данных без перезапроса.
1. datacompboy
  05.11.2018 02:14
  #19324010
  недостаточной для чего?
  я вообще считаю что даже на 57600 на расстояниях в 50 метров достаточно однобайтного дополнения до нуля.
  при условиях:
  — линия согласована
  — токовая петля
  — приемопередатчик с корректной обработкой мажоритарности в центре бита
  — бит четности используется
  — пакеты имеют начало и конец
  — все байты на передаче — ASCII.
  1. sim31r
    05.11.2018 02:27
    #19324022
    Смотря какой процент сбойных бит и что за информация. Если телеметрия с датчиков, то информация не так важна, единичные сбои пройдут незамеченными ни как и всегда можно перезапросить данные повторно. Если управление исполнительными механизмами, то ошибки недопустимы.
    
    datacompboy
    05.11.2018 02:31
    #19324028
    Что значит «ошибки недопустимы»? Какого рода ошибки?
    Если надо минимизировать вероятность повреждения и необходимость переотправки команды — то надо использовать рида-соломона а не CRC. Или вообще сразу посылать команду трижды, и пусть исполительный отрабатывает только две совпавшие команды из последних трёх.
    
    sim31r
    05.11.2018 02:40
    #19324042
    -1
    CRC64 снижает вероятность ошибки в 2^64 раз, а тройная отправка команды намного менее надежна, достаточно чтобы одинаковая ошибка возникла в двух командах из трех. Если команда 1 байт, то вероятность ошибки в той же команде при двойной отправке ниже всего в ~2^8 раз, что не так много. В зашумленном канале связи, например, радиоканале, вообще, недопустимо.
    
    datacompboy
    05.11.2018 02:56
    #19324068
    Вы не понимаете сути, контрольных сумм как таковых.
    Они позволяют оценить корректность передачи большого пакета за счёт небольшого количества данных.
    Это размен вычислительной на канальную мощности.
    Передача контрольной суммы больше чем пакет данных означает, что вы можете передать пакет энное число раз. А дальше хотите — любое отклонение = ошибка. Хотите — мажоритарный принцип, что позволит игнорировать часть ошибок.
    Платить же И вычислительной сложностью И данными в канале — это как "ты что, дурак? За углом можно вдвое дороже купить!".
    
    sim31r
    05.11.2018 03:35
    #19324090
    -1
    Ну пример с 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 попыток.
    
    datacompboy
    05.11.2018 03:49
    #19324102
    Вы во всех расчётах упускаете факт, что ошибка влияет на контрольную сумму в том ЧИСЛЕ.
    Собственно, вы все равно посылаете две фиксированные последовательности.
    У вас 2^65 возможных данных на приёме, из которых корректны только два. (кстати, не факт что равноудалённые, но это и не важно).
    
    Не 50%/264, ошибки, а 1/265 что вообще хоть что-то будет приятно приёмником, так как црц не даёт возможности восстановить в случае ошибки, только информацию о наличии ошибки.
    
    Передать при шуме выше сигнала можно только статистическими методами. Например — передача единицы как меандра со скважностью 3, а нуля как меандра со скважностью 7. Добавляем заголовок со скважностью 5 для синхронизации и замера базовой линии. Вот это даст возможность принять даже на зашумленной линии.
    
    А все что вы выше написали — не имеет ничего общего с действительностью.
    
    sim31r
    05.11.2018 04:31
    #19324120
    -1
    У вас 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
    
    И наглядно на Хабре, автокорреляционная функция. Коды Баркера
    
    Вообще интересная тема. Но следующий шаг в обсуждении это очень крутой матан с интегральными оценками энергий сигнала, шума, эффективности, спектра )
    
    datacompboy
    05.11.2018 04:46
    #19324130
    1/2^65, а не 1/265. Хабр съел две звёздочки.
    Так вот. Сколько надо пакетов передать, чтоб хоть один дошёл?
    
    sim31r
    05.11.2018 05:04
    #19324154
    Каждый бит данных удваивает число попыток передачи данных. Чем больше пакет, тем сложнее по экспоненте. Тут да, 50% ошибка на бит это перебор, надо снижать сложность условий. Хотя бы 50% на байт или на весь кадр данных.
    
    Если линия шумная, то выход один, повторять кадр с данными N раз (или каждый бит сразу повторять N раз), причем с преамбулой, чтобы алгоритмом хоть как-то «зацепится» за начало данных. Далее по мере получения данных N раз полезный сигнал суммируется линейно, а шум не так интенсивно. Через 5-10 итераций уже можно суммировать биты, приходящиеся на одно положение и считать контрольную сумму.
    По сути просто увеличиваем энергию полезного сигнала, чтобы он стал статистически выделяться на фоне шума. Ценой более длительной передачи данных…
    
    datacompboy
    05.11.2018 05:20
    #19324170
    50% на байт? Выкидываем в мусор crc и берём нормальный код коррекции, который позволит исправлять 3, детектировать 4 бита ошибки. Получим гарантию доставки или фильтрацию ошибки на 15 битах вместо 72 для передачи байта.
    Причем напомню, что передача 72 бит будет включать в себя вероятность изменения до 18 бит, то есть до 12х байт. Вы точно уверены что crc64 это хороший метод для раздувания?
    Сколько бит ошибки на пакет он позволит гарантированно оценить и сколько — исправить?
    
    sim31r
    05.11.2018 06:00
    #19324192
    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%? Это весьма символическая защита.
    
    datacompboy
    05.11.2018 12:47
    #19324778
    Нет, вы не правы, Прочитайте учебник еще раз.
    
    sim31r
    05.11.2018 17:35
    #19325574
    Я моделировал CRC-64 еще когда статью на Хабр писал, не дождался ни одной ошибки за многочасовое тестирование. Если вы о надежности CRC-64. Если в контексте статьи изначальной то 0 сбоев будет при любом виде тестирования.
    
    datacompboy
    05.11.2018 22:15
    #19326270
    Хорошо. Скажите, пожалуйста, сколько бит в CRC-64 меняется когда вы меняете один бит входных данных?
    
    sim31r
    06.11.2018 00:53
    #19326550
    Меняются все данные, пересчитаваются заново. Но, если искать отличия, то будет 50% измененных бит, в силу вероятности совпадения старого бита и нового. Матожидание изменения 32 бит из 64 бит. Минимум 1 бит, максимум все биты, в среднем 32 бита.
    
    datacompboy
    06.11.2018 01:15
    #19326598
    И снова нет.
    
    sim31r
    06.11.2018 01:26
    #19326610
    Интересно вашу гипотезу узнать…
    
    crccalc.com
    CRC 32
    1 -> 0x83DCEFB7 -> 10000011110111001110111110110111
    2 -> 0x1AD5BE0D ->
    11010110101011011111000001101
    
    делаем XOR
    10011001000010010101000110111010
    
    убираем нули, получаем количество отличающихся бит
    1111 1111 1111 11
    14 бит отличается, 18 бит совпадает. Примерное 50% бит CRC поменялось при изменении исходных данных на 1 бит. Могу смоделировать, но непонятно зачем, и так всё очевидно. Если бы CRC не менялась максимально возможно при изменении каждого бита данных, она бы потеряла свою ценность.
    
    datacompboy
    06.11.2018 02:23
    #19326690
    Правильный ответ — в зависимости от полинома.
    
    Та же классическая 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%?
    Ну то есть мы добавляем контрольную сумму, и вместо гарантированной доставки получаем гарантированную недоставку.
    Прекрасное решение! Осмысленное и очень прям нужное!
    
    areht
    06.11.2018 15:12
    #19329080
    > Нафига?
    
    Очевидно, 64/72 больше, чем 16/32, и много больше, чем 16/17. Вероятность прохождения сбойного пакета, соответственно, меньше.
    
    Вы как определяете размер необходимой КС? Какой процент доставки (и процент доставки недостоверного пакета) осмысленный и очень нужный?
    
    > (1-0.5^9)=99.8%?
    
    У вас «линия с ожиданием до 1 ошибки на байт» или " линия с ожиданием в среднем 1 ошибки на байт"?
    
    datacompboy
    06.11.2018 15:20
    #19329110
    Речь выше шла про 1 ошибку на байт в среднем.
    64/72 много меньше чем 16/17 :)
    
    Но еще раз — большая CRC бесполезна. Как и любая свертка она нужна чтобы проверить наличие ошибок в большом пакете, и она должна быть чуть-чуть больше чем ожидаемое число ошибок. Всё сверх этого лучше потратить на коды которые позволят восстановить ошибки, иначе мы тратим место впустую.
    
    Ну как впустую, мы увеличиваем вероятность недоставки в принципе.
    
    Передача данных это всегда многопараметрическая оптимизационная задача, поэтому никогда экстремумы не будут оптимумом — нельзя бездумно увеличивать что-то одно (например, длину сообщения или длину контрольной суммы) без учета остальных параметров, и всегда любое действие будет давать еще и негативные последствия.
    
    Увеличение длины контрольной суммы снижает вероятность пропуска каких-то астрономических ситуаций, но при этом увеличивает вероятность возникновения этих самых ситуаций.
    
    Когда у нас 8 бит данных, нам не надо чтоб мы могли отловить изменение 64 бит!
    
    nafikovr
    06.11.2018 16:04
    #19329374
    Увеличение длины контрольной суммы снижает вероятность пропуска каких-то астрономических ситуаций, но при этом увеличивает вероятность возникновения этих самых ситуаций.
    
    вот это я и пытался в соседней ветке сказать
    
    areht
    06.11.2018 18:25
    #19330464
    > 64/72 много меньше чем 16/17 :)
    
    Я не про результат деления, ну да не суть
    
    > она должна быть чуть-чуть больше чем ожидаемое число ошибок.
    
    Но тут то максмальное, а не среднее?
    
    > Когда у нас 8 бит данных, нам не надо чтоб мы могли отловить изменение 64 бит!
    
    Если у вас бывает изменение 64 бит, то с передачей 8 бит у вас будут проблемы.
    
    Хотя да, коды с восстановлением — это хорошо, если применимо. Но тогда вам надо иметь кроме 64 поврежденных минимум 64 неповрежденных бита в пакете, т.е. всего 128+
    
    sim31r
    06.11.2018 18:57
    #19330662
    Увеличение длины контрольной суммы снижает вероятность пропуска каких-то астрономических ситуаций, но при этом увеличивает вероятность возникновения этих самых ситуаций.
    
    Вероятность роста этих ситуаций линейная (это тоже плохо безусловно), а повышение надежности идет по экспоненциальному закону, каждый бит CRC снижает вероятность пропущенной ошибки в 2 раза.
    Далее разрядность CRC выбирается по ситуации. В RS-485 Modbus 16 бит, что иногда и мало, а в Ethernet кадры с 32-битной CRC (ранее на пассивных хабах вероятны были коллизии), ну так же там и кадры килобайтные, CRC особо не увеличивает нагрузку.
    
    sim31r
    06.11.2018 19:11
    #19330734
    Но еще раз — большая CRC бесполезна. Как и любая свертка она нужна чтобы проверить наличие ошибок в большом пакете, и она должна быть чуть-чуть больше чем ожидаемое число ошибок.
    
    В некоторых случаях полезна. Например гипотетический случай команды на самоликвидацию оборудования какого-то на шумной линии, например радиоканале. Ложное срабатывание не допустимо в принципе. Прикидываем, что вероятность ложного срабатывания недопустима свыше 1/2^64 и выход напрашивается применить 64-битную контрольную сумму, даже при передаче 1 бита полезных данных.
    Обратный пример мигание цветомузыкой на мероприятиях, есть специфический протокол
    ru.wikipedia.org/wiki/DMX-512
    и по моему там нет вообще никакой контрольной суммы, мигнет лампочка не в такт, этого ни кто не заметит. Зато данные передаются максимально быстро, это главное.
    
    nafikovr
    06.11.2018 23:35
    #19331668
    Прикидываем, что вероятность ложного срабатывания недопустима свыше 1/2^64 и выход напрашивается применить 64-битную контрольную сумму, даже при передаче 1 бита полезных данных.
    но вероятность ненулевая. вам вроде как объясняют что эти 64 бита можно потратить полезнее.
    
    sim31r
    06.11.2018 23:43
    #19331692
    но вероятность ненулевая. вам вроде как объясняют что эти 64 бита можно потратить полезнее.
    
    «Полезнее» зависит только от задачи. Если требуется максимальная защита от приема сбойного кадра данных, то я не знаю, что может быть полезнее. Другие приемы дают другие преимущества, но надежность существенно снижают, вероятности пропуска сбойного кадра 1/2^64 они не дадут.
    
    datacompboy
    07.11.2018 01:06
    #19331842
    Если нужна максимальная защита от приёма сбойного кадра, то лучше его вообще не отправлять, будет 100% защита.
    А так, почему ограничиваемся жалкими CRC64? Давайте sha-512!
    
    sim31r
    07.11.2018 02:44
    #19331994
    А так, почему ограничиваемся жалкими CRC64? Давайте sha-512!
    
    CRC64 вполне нормальный вариант. CRC32 может давать коллизии, например если передаем пакеты радиоканалу типа WiFi, при 10 000 пакетах в секунду содержащих ошибку, сбой будет происходить каждые 27 часов.
    
    nafikovr
    07.11.2018 10:04
    #19332610
    не путайте будет и может.
    
    sim31r
    06.11.2018 19:28
    #19330816
    -1
    как видите, в результате изменился ОДИН бит плюс сдвиг на один бит.
    
    При чем тут сдвиг?
    Изменилось 5 бит из 16, чуть менее половины. Сдвиг это уже не имеет значения. Еще может быть зеркальное отражение полубайта, инвертирование четных бит и т.п. Опять же это единичный случай, по хорошему нужна статистика, а она, скорее всего, даст матожидание изменения 8 бит из 16.
    
    Итак, вопрос, нахрена нам тут 64 бита контрольной суммы, которые гарантируют вероятность ошибки в (1-0.5^9)=99.8%?
    Ну то есть мы добавляем контрольную сумму, и вместо гарантированной доставки получаем гарантированную недоставку.
    Прекрасное решение! Осмысленное и очень прям нужное!
    
    Именно так, хорошее, рабочее решение. Пусть дойдет 2 пакета из 1000, но это гарантированная информация. По вашему методу будет 1-2% мусора в информации. Я не могу представить себе систему, в которой при обмене данными попадает 2% рандомных данных.
    Про управление реактором вообще речи нет.
    И при получении телеметрии от датчика температуры будет рваный шумный график, не отследишь там минимум за сутки или максимум и постоянно будут всплывать ошибки типа аварийное значение параметра (вызывайте пожарных и МЧС), а потом раз и опять нормальное показание. Даже статистику скучную не собрать.
    Могу допустить что 64 бита избыточно, возможно что хватит 48 бит. Но предпочел бы перестраховаться и вообще не думать о вероятности попадания рандомных значений в систему.
    Есть способы оптимизировать протокол, если нужно чтобы проходило более чем 2 пакета из 1000, например повторять один и тот же кадр данных 20 раз и на приемной стороне статистически анализировать по каждому биту и собирать кадр из шумоподобного сигнала, ориентируясь на результат, совпадение контрольной суммы. Есть конечно и более эффективные алгоритмы, но то утверждать что длинна контрольная сумма не нужна тоже нельзя. Все таки самый простой способ обеспечить «астрономически» точную передачу данных, пусть и высокой ценой.
    
    nafikovr
    05.11.2018 19:10
    #19325816
    с 32-битной командой (например задаем напряжение для ЦАП какого-то исполнительного механизма), 64-битная контрольная сумма нормальный вариант
    
    ну да, конечно. имеет пакет 32 + 64 бит. полезные данные имеют 2^32 вариантов. а какое количество вариантов имеет 64-битная контрольная сумма в данном пакете?
    
    sim31r
    05.11.2018 19:44
    #19325880
    Такое же. Из всего подмножества 2^96 вариантов данных валидными будут 2^32, остальные будут отброшены по ошибке CRC.
    Еще интереснее предельный случай с 1 передаваемым битом и CRC64, из подмножества 2^65 данных, валидными будут всего 2, лог 0 и лог 1 с контрольной суммой. Очень похоже на коды Баркера и автокореляционные функции в каком-то виде, пусть и не самом оптимальном.
    
    nafikovr
    05.11.2018 20:49
    #19326032
    накладываем на это вероятность ошибки и понимаем что лишние 32 бита контрольной суммы не только бесполезны, но и вредны
    
    sim31r
    05.11.2018 20:59
    #19326090
    Нету «лишних» 32 бит, каждый бит CRC в 2 раза снижает вероятность получения сбойной информации.
    Если применить CRC32 вместо CRC64, то алгоритм пропустит примерно из миллиарда сбойных пакетов один. А CRC64 один из 2^64, о таком можно не беспокоится, в связи с ограниченностью срока существования вселенной.
    
    nafikovr
    05.11.2018 21:06
    #19326104
    у вас вероятность сбойных пакетов повышается с увеличением пакета. при этом возможных комбинаций контрольной суммы при 64 битах получается больше чем комбинаций полезных данных
    
    sim31r
    06.11.2018 01:15
    #19326600
    вероятность сбойных пакетов повышается с увеличением пакета
    
    Вероятность сбойных пакетов повышается линейно, но вероятность приемнику распознать сбойный пакет повышается по экспоненте.
    Пример
    контрольная сумма (КС) 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. Polaris99 Автор
  06.11.2018 12:46
  #19328244
  Кстати, спасибо за статью, в свое время очень интересно было ее почитать!

Afterk
05.11.2018 09:25
#19324348
+3
CRC не должен использоваться для идентификации пакета. Это для проверки целостности после идентификации пакета (полем длины в заголовке, маркером конца, форматом, задержками итд). Такая проверка не должна встречаться (если нет ошибки в данных), данные предыдущего пакета должны быть уже обработаны и исключены.
1. Polaris99 Автор
  05.11.2018 11:09
  #19324548
  Я это прекрасно понимаю, но систему проектировал не я, от меня требовалось найти и исправить ошибку.
  1. Aquahawk
    05.11.2018 13:05
    #19324802
    +2
    Вы её нашли, но не исправили. Вы её замаскировали, сделали более редкой, про неё будут думать что она исправлена, а потом что-то долбанёт. Взорвётся или сгорит. Вас скорее всего не найдут, спишут на техническую неисправность, но кто-то потеряет тонны денег а кто-то, возможно, жизни.
    
    Polaris99 Автор
    05.11.2018 14:30
    #19325034
    Ок, и каким образом я должен был ее исправить так, чтобы исключить ее полностью? У Вас есть пути решения, или Вы просто за все хорошее и против всего плохого?
    
    Aquahawk
    05.11.2018 15:31
    #19325238
    Любым способом отделить сообщения в протоколе. Задержкой, маркером начала и конца, маркером начала с префексированием длиной. Просто разделителем, наличие которого явно исключено из допустимых значений содержимого пакета
    
    Polaris99 Автор
    05.11.2018 15:49
    #19325284
    введение дополнительного байта-заголовка свело количество ошибок до недетектируемого уровня, но этого мне показалось мало. Я решил проверить, насколько различные виды 16-битных контрольных сумм отличаются друг от друга в реальных условиях.
    Длина у всех пакетов одинакова. При отсутствии заголовка в нулевой позиции контрольная сумма теперь вообще не считается, пакет отбраковывается.
    Дополнительно к этому продублировал данные в рамках пакета для особо важных (было место). Время работы наших устройств на отказ — порядка сотен часов.
    
    Ну и вообще, речь не об этом, речь о том, что контрольные суммы даже в рамках CRC16 довольно неодинаково детектируют ошибки, и, зная структуру передаваемых данных и возможные причины их повреждения, вполне можно улучшить результаты детектирования ошибок простой сменой контрольной суммы.
    
    sim31r
    05.11.2018 17:53
    #19325626
    Так же важно знать тип помех на линии. Это или инвертирование одиночного бита, или сразу группы бит. Или рассинхронизация приемника и передатчика и пропадание бита данных, или наоборот, появление лишнего бита данных. Тут уже нужен эксперимент с реальной линией связи.
    Если на линии появляются только одиночные ошибки, то хватит и CRC1 он же бит четности/нечетности, аппаратно поддерживается на уровне UART интерфейса. И наоборот, в «тяжелых» случаях без CRC32, CRC64 вообще ни как.
    
    areht
    05.11.2018 17:55
    #19325636
    > контрольные суммы даже в рамках CRC16 довольно неодинаково детектируют ошибки
    
    0.010% против 0.024%? А какая практическая разница?
    
    Polaris99 Автор
    05.11.2018 18:11
    #19325680
    +1
    Мне кажется, что более уместно не долями процентов оперировать, а разами. Снижение вероятности ошибки в 2,5 раза минимальными усилиями — это плохо?
    
    areht
    05.11.2018 18:59
    #19325806
    То есть раньше у вас раз в 5 секунд, а теперь раз в 12? Ну поздравляю, чо.
    
    И это ещё если вам вообще повезло с попаданием алгоритма в специфический тип ошибок у вас (а этого вы не знаете), а то может и наоборот. Так что пока вы даже не измерили и не подтвердили практикой у себя эти 2.5 раза, то результат — преждевременная оптимизация с теоретическим улучшением в пределах погрешности.
    
    И ничего в этом хорошего. Зато движуха.
    
    sim31r
    05.11.2018 19:52
    #19325898
    Исходный код же открыт. Ничего не мешает улучшить эксперимент. Я бы посмотрел на ошибки по мере увеличения уровня шума в линии связи, самый первый эксперимент, но более развернутый.
    Кроме CRC часто применяется просто сумма побайтовая, протокол DCON, например, там эффективность алгоритма в разы ниже, чем у CRC. Тоже легко проверить экспериментом.
    
    areht
    05.11.2018 21:04
    #19326102
    Вы не поняли. Если у автора при передаче сейчас происходят в 90% ошибки класса Roll packet, то CCITT далеко не оптимальный выбор.
    
    Я же не знаю какие ошибки реально происходят на линии автора, так что ничего улучшить не могу. И даже он не знает, так что выиграл ли он от перехода на CCITT — загадка.
    
    А при таких вводных, ковыряние в исходниках — полировка сферического коня в вакууме
    
    Polaris99 Автор
    06.11.2018 15:25
    #19329126
    Выиграл в большей степени время, так как CCITT — единственно доступный аппаратный алгоритм в использованном контроллере. И так как ошибка с накатыванием была исправлена другими методами, большую актуальность получили повреждения пакетов в результате физических коллизий.
    
    areht
    06.11.2018 23:26
    #19331652
    То есть исследование даже на переход на CCITT не повлияло…
    
    sim31r
    05.11.2018 19:48
    #19325888
    2,5 раза так же соответствуют 1 биту избыточных данных. «Плохая» CRC16 на самом деле эквивалентна CRC15.
    А если считать контрольную сумму по просто XOR, вероятность ошибки растет в десятки и сотни раз.
    На практике обычно требуется более существенное снижение вероятности ошибки, и, соответственно переход на CRC32 и более высокие.
1. WildLynxDev
  05.11.2018 16:40
  #19325418
  После целой простыни комментариев, Наконец-то кто-то это написал :)
  Если можно изменить алгоритм контрольной суммы, то наверно можно изменить и весь протокол? ENQ?
  1. Polaris99 Автор
    05.11.2018 16:54
    #19325456
    Почитайте внимательно начало статьи. Протокол был изменен, все остальное — попытка понять, почему контрольные суммы дают настолько отличающиеся значения для количества ошибок.
    
    olartamonov
    05.11.2018 17:00
    #19325476
    -2
    все остальное — попытка понять, почему контрольные суммы дают настолько отличающиеся значения для количества ошибок
    
    Так вы этого не только поняли, но даже не пытались. Вы только экспериментальным путём установили факт (научной новизны в котором нет).
    
    Polaris99 Автор
    05.11.2018 17:07
    #19325494
    +1
    А я и не знал, что на хабре все статьи требуют наличия научной новизны. Извините!
    
    olartamonov
    05.11.2018 17:09
    #19325504
    Я не сказал, что ваша статья тут неуместна, но
    
    1) если вы хотели для себя уяснить наличие проблемы с CRC — достаточно было спросить у гугля что-нибудь про crc collision rate. Ну вот про Modbus я нашёл за три секунды, это сильно быстрее, чем проверять самому;
    
    2) если вы сами себе ставили задачу «понять, почему», то вы с ней не справились.
    
    Polaris99 Автор
    05.11.2018 17:15
    #19325522
    И что говорит Ваша ссылка о зависимости надежности контрольной суммы от структуры данных? Про расчет для случайного набора данных я и сам прекрасно знаю.
    
    olartamonov
    05.11.2018 17:20
    #19325538
    Так ваша статья об этом тоже ничего полезного не говорит — знание, что для вот такой ошибки CCITT хуже, а для другой — Xmodem, не имеет ценности, потому что применительно к вашей задаче единственная разумная формулировка — это «оба хуже».

sergun_74rus
05.11.2018 11:08
#19324542
Модбас, который вы слегка изменили, предполагает помимо контрольной суммы CRC16, контроль битов четности в каждом байте + маркеры начала/конца пакетов в виде временных задержек. Может не стоит изобретать велосипед, а использовать проверенные временем протоколы?
1. sim31r
  05.11.2018 11:59
  #19324662
  Контроль битов четности каждого байта опционален. Сколько использовал промышленных контроллеров, только в одном был жестко установлен бит четности edge/mark, в остальных none. Использование битов четности эквиваленто увеличению разрядности CRC на 1 бит, эффективность невысокая, а добавляет ~10% избыточных данных в канал.

vadimr
05.11.2018 11:16
#19324556
+1
Обычно в таких случаях (при использовании именно UART) проще всего делать пакеты 7-разрядных данных, в первом байте установлен 8-й бит, формирующий начало пакета, значение первого байта представляет тип пакета (из которого понятна длина), в двух последних — CRC14. Соглашусь с предыдущим замечанием, что пакеты нельзя идентифицировать по CRC.

amarao
05.11.2018 14:45
#19325078
Тест shuffle крайне странный, потому что очевидно, что для числа заменённых байтов больше 16, никакой алгоритм не может показать эффективность выше 50%. Я бы ограничил верхнюю границу числа заменяемых битов 16ю.

А ещё, чисто для интереса, можно было бы попробовать криптоалгоритмы. Например, первые 2 байта от md5. Они себя лучше покажут, чем спец.алгоритмы для CRC16 или хуже?
1. datacompboy
  05.11.2018 15:01
  #19325140
  Так же покажут.
1. sim31r
  05.11.2018 17:46
  #19325606
  Да, в случае с линией RS-485 и подобных самый реалистичный сценарий это Shuffle режим. Соответственно хотелось бы видеть Shuffle 1 бит, Shuffle 2 бит и так до Shuffle 16 бит, Shuffle нормально распределенный, Shuffle равномерно распределенный.
  Кроме сложно алгоритма криптографического, на основе сети Фейстеля например, есть простые эффективные алгоритмы на основе операции умножения, я их тестировал, прекрасный результат, причем аппаратная поддержка это операция умножения habr.com/post/278171

CryptoPirate
05.11.2018 15:33
#19325248
Это очень маловероятно, но некоторые из эмуляций повреждений пакетов могут не изменить изначальные данные. Самый простой пример: замена байта на ноль если байт изначально равен нулю. Я мог и пропустить, но у вас вроде нет проверки что «повреждение» по натсоящему что-то изменило.
1. Polaris99 Автор
  05.11.2018 15:44
  #19325270
  Вот эта функция: compare_buf.
  Вызывается в каждом методе. А потом в цикле вот:
  if (!methods[m].fn(packet))
  continue;

IBAH_II
05.11.2018 16:41
#19325420
+1
Несложно сообразить, что
- при неприводимом полиноме (а популярные CRC полиномы не являются неприводимыми)
- при случайных данных
вероятность ложного приема c CRC16 будет
1/(2^16)= 0,0000152587890625 или
при скорости 9600 интервал ложного приема
(2^16)/9600=6,82 секунды

Большее значение интервала ложного приема говорит о том, что данные коррелированны. Меньшее значение говорит о короткой последовательности образуемой полиномом CRC, короче дерьмовый полином.

ob1
05.11.2018 21:23
#19326142
Т.е. вместо того, чтобы исправить алгоритм приёма данных была сделана попытка замаскировать проблему. Печально.
1. Polaris99 Автор
  05.11.2018 21:25
  #19326150
  Интересно, где Вы это увидели?
  1. ob1
    05.11.2018 22:11
    #19326256
    К сожалению, в Вашей заметке и увидел. От того, что Вы сменили алгоритм формирования CRC на другой, что изменилось?
    
    datacompboy
    05.11.2018 22:14
    #19326264
    Прочитайте еще раз. Проблема была устранена добавлением заголовка пакета.
    А смена полинома — просто потому что ничего не стоит.
    
    ob1
    05.11.2018 22:19
    #19326280
    Самоуспокоение. :)
    
    datacompboy
    05.11.2018 22:40
    #19326322
    Не совсем. Полиномы действительно разные.
    Правда, они и заточены для разного, но кто уже упомнит? :D
    
    Polaris99 Автор
    06.11.2018 00:47
    #19326536
    Вы вот реально думаете, что проблема решалась абы как, не глядя? Заголовок уже исключал все возможные причины слияния пакетов, так как структура пакета была действительно крайне неудачной, с большим количеством нулей в теле. Помимо этого я еще и продублировал важные данные вместо этих нулей, а уж смена CRC — это просто для души, собственно, об этом и была статья, сама проблема и ее решение просто для затравки.

esaulenka
06.11.2018 01:49
#19326640
Имхо, было бы любопытно отнормировать количество ошибок к идеальной 16-битной контрольной сумме — у которой ошибки возникают ровно каждый 65536 раз.
У меня получилось, что на этом тесте реальные алгоритмы пропускают в 6..15 раз больше ошибок, чем этот «сферически вакуумный».
Занятная цифра, надо будет её запомнить…
1. sim31r
  06.11.2018 01:56
  #19326658
  Byte injection наоборот, в 1.5 раза меньше пропустил ошибок, чем должен теоретически, на первый взгляд.
  Тут многое зависит от алгоритма по которому ошибка имитируется.
  1. esaulenka
    06.11.2018 10:29
    #19327396
    О, прошу прощения, я с арифметикой напутал.
    100 млн. — это не суммарная цифра, это каждый тест запускался 1e8 раз. Т.е. вывод «CRC хуже идеального хэша на порядок» неверный. Хуже только в два раза в самом худшем случае. Ок, дядьки-математики, которые это когда-то придумали, реабилитированы :-)

emmibox
06.11.2018 17:28
#19329990
Не надо было изобретать велосипед.

Берете обычный HDLC
Начало и конец пакета префиксируется байтом 7E (старт-стоп).
внутри пакета 7E заменяется на 7D 5E, 7D на 7D 5D.
перед концом CRC16-CCITT (просто потому что так заведено)…
Далее длинна пакета внутри известна… Битые отбрасываете по критерию длинны и по критерию не соответствия CRC16. Это десятилетиями работает в миллиардах приложений.
1. datacompboy
  06.11.2018 17:39
  #19330094
  длина пакета неизвестна, если есть раздувающие замены.
  1. Polaris99 Автор
    06.11.2018 17:48
    #19330184
    +1
    Кого ж такие мелочи уже волнуют. Тем более, что по сути вышел тот самый велосипед — уникальный байт-заголовок и CCITT в конце.
  1. emmibox
    06.11.2018 18:14
    #19330404
    При проектировании этого можно избежать используя уникальный «адрес» в рамках того же HDLC исключительно для пакетов длинна которых может быть неизвестна и другие уникальные адреса для пакетов фиксированных известных длин.

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

Комментарии (113)

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор

Polaris99 Автор