У нас имеется устройство, которое осуществляет интенсивный обмен по внутренней шине 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)
netricks
04.11.2018 20:59+3Насколько хороша повторяемость этого эксперимента? Я имею ввиду, получу ли я схожие результаты, если прогоню еще 100 000 000 пакетов? Может это просто дикая дисперсия?
Polaris99 Автор
04.11.2018 21:14Все достаточно повторяемо
Inanity
04.11.2018 21:34Известно, что числа, полученные остатком от деления rand(), вообще говоря имеют плохое равномерное распределение. Хотя с другой стороны я не возьмусь утверждать, что результат сильно изменится, если взять генератор получше, но было интересно исключить этот фактор.
olartamonov
05.11.2018 00:25+3Это, на самом деле, не играет большой роли.
Штука, у которой гарантированно не больше 65536 уникальных значений, в любом случае плохо подходит для того, для чего её авторы поста использовали. Алгоритм, по которому она вычисляется, здесь влияет только на то, насколько быстро вы встретитесь с этой проблемой.
Авторам повезло, они взяли плохой алгоритм и встретились быстро.
olartamonov
04.11.2018 21:28+9Мне так сдаётся, что подсчёт числа коллизий на полностью случайных данных при условии, что у контрольной суммы совершенно точно никак не больше 65536 возможных значений, является задачей чисто умозрительной и не требующей написания какого-либо кода, а дизайн системы, в котором на отсутствие таких коллизий полагались, — странным.
Задача же определения числа коллизий для пакетов конкретного вида и содержания не имеет практической ценности в отрыве от конкретной задачи, определяющей этот вид и содержание.
Некоторый интерес может представлять собой проверка, действительно ли у всех представленных алгоритмов 65536 возможных значений CRC16, и насколько равномерно они распределены — это сразу позволит отделить хорошие алгоритмы от плохих, без привязки к конкретным данным.SegreyBorovkov
04.11.2018 23:21+1не согласен. Алгоритм должен быть еще стоек к некоторым модификациям данных. К примеру — изменению порядка байтов. Если в качестве crc взять sum(X) % 65536, где X — вектор из двухбайтовых значений, то он будет давать достаточно ровное распределение, но порядок двухбайтовых блоков можно будет менять как угодно.
olartamonov
04.11.2018 23:52Это так для совсем простых алгоритмов, вычислять это специальной программой в общем не требуется, можно просто указать.
ZyXI
04.11.2018 23:57+3Зачем? Я не очень представляю себе, как можно реализовывать что?то поверх протокола уровня UART и получить случайное изменение порядка байтов (если только у вас нет ошибки в программе). Получить мусорный бит в середине на том же SPI при помехах на линии тактирования — можно. Получить инверсию бита из?за помех — можно. Получить байт(ы) посылки от другого устройства между байтами посылки от первого — можно, но такие проблемы разруливаются не CRC, если только инверсия произошла не при передаче адреса отправителя. А что может привести к изменению порядка байтов кроме ошибки в программе? У того же TCP ожидается произвольный порядок приёма, но пакетов и по очень хорошей причине.
SegreyBorovkov
05.11.2018 01:23+1Предположим, что CRC — XOR данных. К примеру, двухбайтовый.
Теперь представим, что пакет содержит 6 байт. Первые два байта меняются редко, потом 2 байта данных и два байта CRC. По факту это означает, что XOR от всего пакета включая CRC должен быть 0 (ноль). Это похоже на то, что у автора? Вроде да, но там функция CRC чуть другая.
А теперь смещаем окно на 2 байта вправо. Как думаете, CRC сойдется? Мне почему-то кажется, что да. Даже при смещении на 1 байт — тоже сойдется.
Вот и все :-)ZyXI
05.11.2018 01:51Хорошо, вы правы. Я почему?то решил, что вы написали про абсолютно произвольное изменение порядка, а не более конкретный циклический сдвиг — моя способность «додумать» без уточнения несколько промахнулась :)
sim31r
05.11.2018 02:18Порядок байт вряд ли может изменится в обычном канале связи. Но может произойти двойная ошибка, один бит меняется с 1 на 0, другой бит в том же месте байта с 0 на 1, и ошибка проходит незамеченной. Такое очень вероятно, и вероятность выше чем 1 к 65535. А при CRC обычной, чтобы ошибка прошла незамеченной, нужно достаточно необычные комбинации формировать. Если один бит меняется с 1 на 0, то для прохождения контрольной суммы должны изменится еще несколько бит в разных байтах в разных местах.
esaulenka
06.11.2018 01:32А мы тут что обсуждаем, пардон? CRC с различными полиномами или «в качестве CRC взять абстрактную f(x)»?
Давайте так: CRC это циклический избыточный код (см. в википедии), абстрактная f(x) — это некая контрольная сумма (checksum). Просто, понятно, общепринято.
datacompboy
04.11.2018 21:29+7Контрольная сумма она для защиты от ошибки первого рода (узнать что она была).
Почти все указанные тут по сути защищают от 1 бита ошибки.
Полиномы еще дополнительно защищают от перестановки бит, в пределах ширины.
Но таки да, всегда можно подобрать набор данных чтоб получить любую наперёд заданную CRC по любому из алгоритмов.
И таки да, перестановка байт/слов вполне может пройти незаметно для CRC.
Любой протокол обмена крайне рекомендовано завязывать на фиксированные начало и конец (или длину), а CRC использовать для проверки что принятое — не случайный шум.
ilynxy
04.11.2018 23:30+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.
Это даёт неплохую оценку, но, как показывает брутфорс эта оценка справедлива только для малых значений расстояний Хэмминга.Polaris99 Автор
05.11.2018 17:28Вот за эти ссылки спасибо, ведь реально автор пришел, пусть и более осознанным и подкрепленным вычислениями путем, к выводу, что не все полиномы одинаково хороши.
TimsTims
05.11.2018 01:26-1но дело оказалось в другом – время от времени в буфере, где собирались полученные данные, оказывался пакет, состоящий из конца предыдущего пакета и начала следующего
Ну вот вы же нашли проблему — брались неверные данные. Правильнее было бы искать ошибку в драйвере отправки данных (ок, не в драйвере, а в коде, формирующим пакеты), понять почему так происходит, что вообще берутся данные из ненужных сейчас к отправке пакетов. А пытаться применить другой CRC16 — это как наливать всё больше воды в дырявое ведро, вместо латания дыр.datacompboy
05.11.2018 02:13Нет никакой ошибки в отправке. И на приёме нет. Есть проблема в отсутствии маркера фрейма.
То есть пакеты идут: D0-D1-D2-D3-D4-C1-C2 где C1 и C2 — контрольная сумма.
Определением пакета было «контрольная сумма сошлась». При этом обрабатывался циклический буфер. То есть спустя несколько байт получалось:
D2-D3-D4-C1-C2-N0-N1
где N0 и N1 это байты от следующего пакета, но на приёмнике они рассматриваются как CRC16 и дают схождение суммы для всего пакета.
Что немаловероятно.sim31r
05.11.2018 02:22Тут надо было делать 64-битную контрольную сумму, проблемы бы не было.
datacompboy
05.11.2018 02:25Достаточно добавить фиксированный байт начала пакета. В идеале — такой, который не может быть в данных. Это даст накладные расходы в 1 байт и стабилизирует систему (останутся только ошибки порядка 1 на ~1e-10 байт).
64битная сумма (то есть 8 байт сумма на 5 байт данных, кхе кхе) создаст больше проблем.
проще уж тогда присылать инверсные данные, всего 5 байт понадобится.sim31r
05.11.2018 02:3464 битная контрольная сумма сделает невозможной прием сбойного пакета данных, вероятностью 1 / 2^64 можно пренебречь.
Все остальные варианты проще программно, но повышают вероятность ошибки. Хотя если речь о 1 на ~1e-10 байт то не важно, конечно, это почти идеальная линия связи.
Инверсные дополнительные данные тоже имеют очень высокую вероятность ошибки, по сравнению с CRC64, достаточно двойной ошибки.datacompboy
05.11.2018 02:58Я говорю про ошибки "обработка сбойного пакета". Приём сбойного пакета возможен всегда, задача как раз его проигнорировать, иногда — ещё узнать что он вообще был.
sim31r
06.11.2018 01:51Приём сбойного пакета возможен всегда, задача как раз его проигнорировать
Эту задачу решает CRC, он для этого и придуман.
esaulenka
06.11.2018 01:42Вы статью-то прочитали? Вероятность ошибки у автора не 1/2**16, а на порядок (десятичный!) бОльшая. Не, для 2**64 порядок туда — порядок сюда — уже неважно, но всё ж таки…
sim31r
06.11.2018 01:49По таблице, где тестировалось 100 000 000 переданных кадров данных с ошибкой порядок величины не распознанных ошибок как-раз 1/2^16 или 1/65536, плюс девиации в зависимости от алгоритма и типа ошибки.
Пример 2000 не распознанных ошибок из 100 000 000 кадров это 1/50 000, что достаточно точно совпадает с теорией.
Polaris99 Автор
05.11.2018 11:06Почитайте еще раз статью, длина всего пакета с CRC16 — 7 байт, степень заполнения канала при этом порядка 70%. А теперь добавьте сюда еще 6 байт CRC64.
sim31r
05.11.2018 02:11CCITT, в большей степени потому, что ее реализация была доступна в аппаратной части используемого микроконтроллера.
Можно было на операции перемножения сделать расчет контрольной суммы, умножение микроконтроллеры обычно поддерживают. Вот тут описал
habr.com/post/278171
И разрядность побайтно подбирать, 16 бит контрольная сумма может быть недостаточной, есть возможность выбрать 24 бита или 32. В идеале 64 бит, но канал связи может ограничить прохождение избыточных данных. Чем хуже канал передачи данных, выше вероятность помехи, тем больше разрядов должно быть в контрольной сумме. В самых тяжелых случаях можно избыточную информацию передавать, для восстановления данных без перезапроса.
datacompboy
05.11.2018 02:14недостаточной для чего?
я вообще считаю что даже на 57600 на расстояниях в 50 метров достаточно однобайтного дополнения до нуля.
при условиях:
— линия согласована
— токовая петля
— приемопередатчик с корректной обработкой мажоритарности в центре бита
— бит четности используется
— пакеты имеют начало и конец
— все байты на передаче — ASCII.sim31r
05.11.2018 02:27Смотря какой процент сбойных бит и что за информация. Если телеметрия с датчиков, то информация не так важна, единичные сбои пройдут незамеченными ни как и всегда можно перезапросить данные повторно. Если управление исполнительными механизмами, то ошибки недопустимы.
datacompboy
05.11.2018 02:31Что значит «ошибки недопустимы»? Какого рода ошибки?
Если надо минимизировать вероятность повреждения и необходимость переотправки команды — то надо использовать рида-соломона а не CRC. Или вообще сразу посылать команду трижды, и пусть исполительный отрабатывает только две совпавшие команды из последних трёх.sim31r
05.11.2018 02:40-1CRC64 снижает вероятность ошибки в 2^64 раз, а тройная отправка команды намного менее надежна, достаточно чтобы одинаковая ошибка возникла в двух командах из трех. Если команда 1 байт, то вероятность ошибки в той же команде при двойной отправке ниже всего в ~2^8 раз, что не так много. В зашумленном канале связи, например, радиоканале, вообще, недопустимо.
datacompboy
05.11.2018 02:56Вы не понимаете сути, контрольных сумм как таковых.
Они позволяют оценить корректность передачи большого пакета за счёт небольшого количества данных.
Это размен вычислительной на канальную мощности.
Передача контрольной суммы больше чем пакет данных означает, что вы можете передать пакет энное число раз. А дальше хотите — любое отклонение = ошибка. Хотите — мажоритарный принцип, что позволит игнорировать часть ошибок.
Платить же И вычислительной сложностью И данными в канале — это как "ты что, дурак? За углом можно вдвое дороже купить!".sim31r
05.11.2018 03:35-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Вы во всех расчётах упускаете факт, что ошибка влияет на контрольную сумму в том ЧИСЛЕ.
Собственно, вы все равно посылаете две фиксированные последовательности.
У вас 2^65 возможных данных на приёме, из которых корректны только два. (кстати, не факт что равноудалённые, но это и не важно).
Не 50%/264, ошибки, а 1/265 что вообще хоть что-то будет приятно приёмником, так как црц не даёт возможности восстановить в случае ошибки, только информацию о наличии ошибки.
Передать при шуме выше сигнала можно только статистическими методами. Например — передача единицы как меандра со скважностью 3, а нуля как меандра со скважностью 7. Добавляем заголовок со скважностью 5 для синхронизации и замера базовой линии. Вот это даст возможность принять даже на зашумленной линии.
А все что вы выше написали — не имеет ничего общего с действительностью.
sim31r
05.11.2018 04:31-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:461/2^65, а не 1/265. Хабр съел две звёздочки.
Так вот. Сколько надо пакетов передать, чтоб хоть один дошёл?sim31r
05.11.2018 05:04Каждый бит данных удваивает число попыток передачи данных. Чем больше пакет, тем сложнее по экспоненте. Тут да, 50% ошибка на бит это перебор, надо снижать сложность условий. Хотя бы 50% на байт или на весь кадр данных.
Если линия шумная, то выход один, повторять кадр с данными N раз (или каждый бит сразу повторять N раз), причем с преамбулой, чтобы алгоритмом хоть как-то «зацепится» за начало данных. Далее по мере получения данных N раз полезный сигнал суммируется линейно, а шум не так интенсивно. Через 5-10 итераций уже можно суммировать биты, приходящиеся на одно положение и считать контрольную сумму.
По сути просто увеличиваем энергию полезного сигнала, чтобы он стал статистически выделяться на фоне шума. Ценой более длительной передачи данных…datacompboy
05.11.2018 05:2050% на байт? Выкидываем в мусор crc и берём нормальный код коррекции, который позволит исправлять 3, детектировать 4 бита ошибки. Получим гарантию доставки или фильтрацию ошибки на 15 битах вместо 72 для передачи байта.
Причем напомню, что передача 72 бит будет включать в себя вероятность изменения до 18 бит, то есть до 12х байт. Вы точно уверены что crc64 это хороший метод для раздувания?
Сколько бит ошибки на пакет он позволит гарантированно оценить и сколько — исправить?sim31r
05.11.2018 06:00CRC не исправляет же ошибки, но можно из нескольких сбойных пакетов собрать один правдоподобный, выше уровень шума, больше нужно передавать информации.
Детектировать же с 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Нет, вы не правы, Прочитайте учебник еще раз.
sim31r
05.11.2018 17:35Я моделировал CRC-64 еще когда статью на Хабр писал, не дождался ни одной ошибки за многочасовое тестирование. Если вы о надежности CRC-64. Если в контексте статьи изначальной то 0 сбоев будет при любом виде тестирования.
datacompboy
05.11.2018 22:15Хорошо. Скажите, пожалуйста, сколько бит в CRC-64 меняется когда вы меняете один бит входных данных?
sim31r
06.11.2018 00:53Меняются все данные, пересчитаваются заново. Но, если искать отличия, то будет 50% измененных бит, в силу вероятности совпадения старого бита и нового. Матожидание изменения 32 бит из 64 бит. Минимум 1 бит, максимум все биты, в среднем 32 бита.
datacompboy
06.11.2018 01:15И снова нет.
sim31r
06.11.2018 01:26Интересно вашу гипотезу узнать…
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Правильный ответ — в зависимости от полинома.
Та же классическая 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> Нафига?
Очевидно, 64/72 больше, чем 16/32, и много больше, чем 16/17. Вероятность прохождения сбойного пакета, соответственно, меньше.
Вы как определяете размер необходимой КС? Какой процент доставки (и процент доставки недостоверного пакета) осмысленный и очень нужный?
> (1-0.5^9)=99.8%?
У вас «линия с ожиданием до 1 ошибки на байт» или " линия с ожиданием в среднем 1 ошибки на байт"?datacompboy
06.11.2018 15:20Речь выше шла про 1 ошибку на байт в среднем.
64/72 много меньше чем 16/17 :)
Но еще раз — большая CRC бесполезна. Как и любая свертка она нужна чтобы проверить наличие ошибок в большом пакете, и она должна быть чуть-чуть больше чем ожидаемое число ошибок. Всё сверх этого лучше потратить на коды которые позволят восстановить ошибки, иначе мы тратим место впустую.
Ну как впустую, мы увеличиваем вероятность недоставки в принципе.
Передача данных это всегда многопараметрическая оптимизационная задача, поэтому никогда экстремумы не будут оптимумом — нельзя бездумно увеличивать что-то одно (например, длину сообщения или длину контрольной суммы) без учета остальных параметров, и всегда любое действие будет давать еще и негативные последствия.
Увеличение длины контрольной суммы снижает вероятность пропуска каких-то астрономических ситуаций, но при этом увеличивает вероятность возникновения этих самых ситуаций.
Когда у нас 8 бит данных, нам не надо чтоб мы могли отловить изменение 64 бит!nafikovr
06.11.2018 16:04Увеличение длины контрольной суммы снижает вероятность пропуска каких-то астрономических ситуаций, но при этом увеличивает вероятность возникновения этих самых ситуаций.
вот это я и пытался в соседней ветке сказать
areht
06.11.2018 18:25> 64/72 много меньше чем 16/17 :)
Я не про результат деления, ну да не суть
> она должна быть чуть-чуть больше чем ожидаемое число ошибок.
Но тут то максмальное, а не среднее?
> Когда у нас 8 бит данных, нам не надо чтоб мы могли отловить изменение 64 бит!
Если у вас бывает изменение 64 бит, то с передачей 8 бит у вас будут проблемы.
Хотя да, коды с восстановлением — это хорошо, если применимо. Но тогда вам надо иметь кроме 64 поврежденных минимум 64 неповрежденных бита в пакете, т.е. всего 128+
sim31r
06.11.2018 18:57Увеличение длины контрольной суммы снижает вероятность пропуска каких-то астрономических ситуаций, но при этом увеличивает вероятность возникновения этих самых ситуаций.
Вероятность роста этих ситуаций линейная (это тоже плохо безусловно), а повышение надежности идет по экспоненциальному закону, каждый бит CRC снижает вероятность пропущенной ошибки в 2 раза.
Далее разрядность CRC выбирается по ситуации. В RS-485 Modbus 16 бит, что иногда и мало, а в Ethernet кадры с 32-битной CRC (ранее на пассивных хабах вероятны были коллизии), ну так же там и кадры килобайтные, CRC особо не увеличивает нагрузку.
sim31r
06.11.2018 19:11Но еще раз — большая CRC бесполезна. Как и любая свертка она нужна чтобы проверить наличие ошибок в большом пакете, и она должна быть чуть-чуть больше чем ожидаемое число ошибок.
В некоторых случаях полезна. Например гипотетический случай команды на самоликвидацию оборудования какого-то на шумной линии, например радиоканале. Ложное срабатывание не допустимо в принципе. Прикидываем, что вероятность ложного срабатывания недопустима свыше 1/2^64 и выход напрашивается применить 64-битную контрольную сумму, даже при передаче 1 бита полезных данных.
Обратный пример мигание цветомузыкой на мероприятиях, есть специфический протокол
ru.wikipedia.org/wiki/DMX-512
и по моему там нет вообще никакой контрольной суммы, мигнет лампочка не в такт, этого ни кто не заметит. Зато данные передаются максимально быстро, это главное.nafikovr
06.11.2018 23:35Прикидываем, что вероятность ложного срабатывания недопустима свыше 1/2^64 и выход напрашивается применить 64-битную контрольную сумму, даже при передаче 1 бита полезных данных.
но вероятность ненулевая. вам вроде как объясняют что эти 64 бита можно потратить полезнее.sim31r
06.11.2018 23:43но вероятность ненулевая. вам вроде как объясняют что эти 64 бита можно потратить полезнее.
«Полезнее» зависит только от задачи. Если требуется максимальная защита от приема сбойного кадра данных, то я не знаю, что может быть полезнее. Другие приемы дают другие преимущества, но надежность существенно снижают, вероятности пропуска сбойного кадра 1/2^64 они не дадут.datacompboy
07.11.2018 01:06Если нужна максимальная защита от приёма сбойного кадра, то лучше его вообще не отправлять, будет 100% защита.
А так, почему ограничиваемся жалкими CRC64? Давайте sha-512!sim31r
07.11.2018 02:44А так, почему ограничиваемся жалкими CRC64? Давайте sha-512!
CRC64 вполне нормальный вариант. CRC32 может давать коллизии, например если передаем пакеты радиоканалу типа WiFi, при 10 000 пакетах в секунду содержащих ошибку, сбой будет происходить каждые 27 часов.
sim31r
06.11.2018 19:28-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с 32-битной командой (например задаем напряжение для ЦАП какого-то исполнительного механизма), 64-битная контрольная сумма нормальный вариант
ну да, конечно. имеет пакет 32 + 64 бит. полезные данные имеют 2^32 вариантов. а какое количество вариантов имеет 64-битная контрольная сумма в данном пакете?sim31r
05.11.2018 19:44Такое же. Из всего подмножества 2^96 вариантов данных валидными будут 2^32, остальные будут отброшены по ошибке CRC.
Еще интереснее предельный случай с 1 передаваемым битом и CRC64, из подмножества 2^65 данных, валидными будут всего 2, лог 0 и лог 1 с контрольной суммой. Очень похоже на коды Баркера и автокореляционные функции в каком-то виде, пусть и не самом оптимальном.nafikovr
05.11.2018 20:49накладываем на это вероятность ошибки и понимаем что лишние 32 бита контрольной суммы не только бесполезны, но и вредны
sim31r
05.11.2018 20:59Нету «лишних» 32 бит, каждый бит CRC в 2 раза снижает вероятность получения сбойной информации.
Если применить CRC32 вместо CRC64, то алгоритм пропустит примерно из миллиарда сбойных пакетов один. А CRC64 один из 2^64, о таком можно не беспокоится, в связи с ограниченностью срока существования вселенной.nafikovr
05.11.2018 21:06у вас вероятность сбойных пакетов повышается с увеличением пакета. при этом возможных комбинаций контрольной суммы при 64 битах получается больше чем комбинаций полезных данных
sim31r
06.11.2018 01:15вероятность сбойных пакетов повышается с увеличением пакета
Вероятность сбойных пакетов повышается линейно, но вероятность приемнику распознать сбойный пакет повышается по экспоненте.
Пример
контрольная сумма (КС) 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
Polaris99 Автор
06.11.2018 12:46Кстати, спасибо за статью, в свое время очень интересно было ее почитать!
Afterk
05.11.2018 09:25+3CRC не должен использоваться для идентификации пакета. Это для проверки целостности после идентификации пакета (полем длины в заголовке, маркером конца, форматом, задержками итд). Такая проверка не должна встречаться (если нет ошибки в данных), данные предыдущего пакета должны быть уже обработаны и исключены.
Polaris99 Автор
05.11.2018 11:09Я это прекрасно понимаю, но систему проектировал не я, от меня требовалось найти и исправить ошибку.
Aquahawk
05.11.2018 13:05+2Вы её нашли, но не исправили. Вы её замаскировали, сделали более редкой, про неё будут думать что она исправлена, а потом что-то долбанёт. Взорвётся или сгорит. Вас скорее всего не найдут, спишут на техническую неисправность, но кто-то потеряет тонны денег а кто-то, возможно, жизни.
Polaris99 Автор
05.11.2018 14:30Ок, и каким образом я должен был ее исправить так, чтобы исключить ее полностью? У Вас есть пути решения, или Вы просто за все хорошее и против всего плохого?
Aquahawk
05.11.2018 15:31Любым способом отделить сообщения в протоколе. Задержкой, маркером начала и конца, маркером начала с префексированием длиной. Просто разделителем, наличие которого явно исключено из допустимых значений содержимого пакета
Polaris99 Автор
05.11.2018 15:49введение дополнительного байта-заголовка свело количество ошибок до недетектируемого уровня, но этого мне показалось мало. Я решил проверить, насколько различные виды 16-битных контрольных сумм отличаются друг от друга в реальных условиях.
Длина у всех пакетов одинакова. При отсутствии заголовка в нулевой позиции контрольная сумма теперь вообще не считается, пакет отбраковывается.
Дополнительно к этому продублировал данные в рамках пакета для особо важных (было место). Время работы наших устройств на отказ — порядка сотен часов.
Ну и вообще, речь не об этом, речь о том, что контрольные суммы даже в рамках CRC16 довольно неодинаково детектируют ошибки, и, зная структуру передаваемых данных и возможные причины их повреждения, вполне можно улучшить результаты детектирования ошибок простой сменой контрольной суммы.sim31r
05.11.2018 17:53Так же важно знать тип помех на линии. Это или инвертирование одиночного бита, или сразу группы бит. Или рассинхронизация приемника и передатчика и пропадание бита данных, или наоборот, появление лишнего бита данных. Тут уже нужен эксперимент с реальной линией связи.
Если на линии появляются только одиночные ошибки, то хватит и CRC1 он же бит четности/нечетности, аппаратно поддерживается на уровне UART интерфейса. И наоборот, в «тяжелых» случаях без CRC32, CRC64 вообще ни как.
areht
05.11.2018 17:55> контрольные суммы даже в рамках CRC16 довольно неодинаково детектируют ошибки
0.010% против 0.024%? А какая практическая разница?Polaris99 Автор
05.11.2018 18:11+1Мне кажется, что более уместно не долями процентов оперировать, а разами. Снижение вероятности ошибки в 2,5 раза минимальными усилиями — это плохо?
areht
05.11.2018 18:59То есть раньше у вас раз в 5 секунд, а теперь раз в 12? Ну поздравляю, чо.
И это ещё если вам вообще повезло с попаданием алгоритма в специфический тип ошибок у вас (а этого вы не знаете), а то может и наоборот. Так что пока вы даже не измерили и не подтвердили практикой у себя эти 2.5 раза, то результат — преждевременная оптимизация с теоретическим улучшением в пределах погрешности.
И ничего в этом хорошего. Зато движуха.sim31r
05.11.2018 19:52Исходный код же открыт. Ничего не мешает улучшить эксперимент. Я бы посмотрел на ошибки по мере увеличения уровня шума в линии связи, самый первый эксперимент, но более развернутый.
Кроме CRC часто применяется просто сумма побайтовая, протокол DCON, например, там эффективность алгоритма в разы ниже, чем у CRC. Тоже легко проверить экспериментом.areht
05.11.2018 21:04Вы не поняли. Если у автора при передаче сейчас происходят в 90% ошибки класса Roll packet, то CCITT далеко не оптимальный выбор.
Я же не знаю какие ошибки реально происходят на линии автора, так что ничего улучшить не могу. И даже он не знает, так что выиграл ли он от перехода на CCITT — загадка.
А при таких вводных, ковыряние в исходниках — полировка сферического коня в вакуумеPolaris99 Автор
06.11.2018 15:25Выиграл в большей степени время, так как CCITT — единственно доступный аппаратный алгоритм в использованном контроллере. И так как ошибка с накатыванием была исправлена другими методами, большую актуальность получили повреждения пакетов в результате физических коллизий.
sim31r
05.11.2018 19:482,5 раза так же соответствуют 1 биту избыточных данных. «Плохая» CRC16 на самом деле эквивалентна CRC15.
А если считать контрольную сумму по просто XOR, вероятность ошибки растет в десятки и сотни раз.
На практике обычно требуется более существенное снижение вероятности ошибки, и, соответственно переход на CRC32 и более высокие.
WildLynxDev
05.11.2018 16:40После целой простыни комментариев, Наконец-то кто-то это написал :)
Если можно изменить алгоритм контрольной суммы, то наверно можно изменить и весь протокол? ENQ?Polaris99 Автор
05.11.2018 16:54Почитайте внимательно начало статьи. Протокол был изменен, все остальное — попытка понять, почему контрольные суммы дают настолько отличающиеся значения для количества ошибок.
olartamonov
05.11.2018 17:00-2все остальное — попытка понять, почему контрольные суммы дают настолько отличающиеся значения для количества ошибок
Так вы этого не только поняли, но даже не пытались. Вы только экспериментальным путём установили факт (научной новизны в котором нет).Polaris99 Автор
05.11.2018 17:07+1А я и не знал, что на хабре все статьи требуют наличия научной новизны. Извините!
olartamonov
05.11.2018 17:09Я не сказал, что ваша статья тут неуместна, но
1) если вы хотели для себя уяснить наличие проблемы с CRC — достаточно было спросить у гугля что-нибудь про crc collision rate. Ну вот про Modbus я нашёл за три секунды, это сильно быстрее, чем проверять самому;
2) если вы сами себе ставили задачу «понять, почему», то вы с ней не справились.Polaris99 Автор
05.11.2018 17:15И что говорит Ваша ссылка о зависимости надежности контрольной суммы от структуры данных? Про расчет для случайного набора данных я и сам прекрасно знаю.
olartamonov
05.11.2018 17:20Так ваша статья об этом тоже ничего полезного не говорит — знание, что для вот такой ошибки CCITT хуже, а для другой — Xmodem, не имеет ценности, потому что применительно к вашей задаче единственная разумная формулировка — это «оба хуже».
sergun_74rus
05.11.2018 11:08Модбас, который вы слегка изменили, предполагает помимо контрольной суммы CRC16, контроль битов четности в каждом байте + маркеры начала/конца пакетов в виде временных задержек. Может не стоит изобретать велосипед, а использовать проверенные временем протоколы?
sim31r
05.11.2018 11:59Контроль битов четности каждого байта опционален. Сколько использовал промышленных контроллеров, только в одном был жестко установлен бит четности edge/mark, в остальных none. Использование битов четности эквиваленто увеличению разрядности CRC на 1 бит, эффективность невысокая, а добавляет ~10% избыточных данных в канал.
vadimr
05.11.2018 11:16+1Обычно в таких случаях (при использовании именно UART) проще всего делать пакеты 7-разрядных данных, в первом байте установлен 8-й бит, формирующий начало пакета, значение первого байта представляет тип пакета (из которого понятна длина), в двух последних — CRC14. Соглашусь с предыдущим замечанием, что пакеты нельзя идентифицировать по CRC.
amarao
05.11.2018 14:45Тест shuffle крайне странный, потому что очевидно, что для числа заменённых байтов больше 16, никакой алгоритм не может показать эффективность выше 50%. Я бы ограничил верхнюю границу числа заменяемых битов 16ю.
А ещё, чисто для интереса, можно было бы попробовать криптоалгоритмы. Например, первые 2 байта от md5. Они себя лучше покажут, чем спец.алгоритмы для CRC16 или хуже?sim31r
05.11.2018 17:46Да, в случае с линией RS-485 и подобных самый реалистичный сценарий это Shuffle режим. Соответственно хотелось бы видеть Shuffle 1 бит, Shuffle 2 бит и так до Shuffle 16 бит, Shuffle нормально распределенный, Shuffle равномерно распределенный.
Кроме сложно алгоритма криптографического, на основе сети Фейстеля например, есть простые эффективные алгоритмы на основе операции умножения, я их тестировал, прекрасный результат, причем аппаратная поддержка это операция умножения habr.com/post/278171
CryptoPirate
05.11.2018 15:33Это очень маловероятно, но некоторые из эмуляций повреждений пакетов могут не изменить изначальные данные. Самый простой пример: замена байта на ноль если байт изначально равен нулю. Я мог и пропустить, но у вас вроде нет проверки что «повреждение» по натсоящему что-то изменило.
Polaris99 Автор
05.11.2018 15:44Вот эта функция: compare_buf.
Вызывается в каждом методе. А потом в цикле вот:
if (!methods[m].fn(packet))
continue;
IBAH_II
05.11.2018 16:41+1Несложно сообразить, что
- при неприводимом полиноме (а популярные CRC полиномы не являются неприводимыми)
- при случайных данных
вероятность ложного приема c CRC16 будет
1/(2^16)= 0,0000152587890625 или
при скорости 9600 интервал ложного приема
(2^16)/9600=6,82 секунды
Большее значение интервала ложного приема говорит о том, что данные коррелированны. Меньшее значение говорит о короткой последовательности образуемой полиномом CRC, короче дерьмовый полином.
ob1
05.11.2018 21:23Т.е. вместо того, чтобы исправить алгоритм приёма данных была сделана попытка замаскировать проблему. Печально.
Polaris99 Автор
05.11.2018 21:25Интересно, где Вы это увидели?
ob1
05.11.2018 22:11К сожалению, в Вашей заметке и увидел. От того, что Вы сменили алгоритм формирования CRC на другой, что изменилось?
datacompboy
05.11.2018 22:14Прочитайте еще раз. Проблема была устранена добавлением заголовка пакета.
А смена полинома — просто потому что ничего не стоит.ob1
05.11.2018 22:19Самоуспокоение. :)
datacompboy
05.11.2018 22:40Не совсем. Полиномы действительно разные.
Правда, они и заточены для разного, но кто уже упомнит? :D
Polaris99 Автор
06.11.2018 00:47Вы вот реально думаете, что проблема решалась абы как, не глядя? Заголовок уже исключал все возможные причины слияния пакетов, так как структура пакета была действительно крайне неудачной, с большим количеством нулей в теле. Помимо этого я еще и продублировал важные данные вместо этих нулей, а уж смена CRC — это просто для души, собственно, об этом и была статья, сама проблема и ее решение просто для затравки.
esaulenka
06.11.2018 01:49Имхо, было бы любопытно отнормировать количество ошибок к идеальной 16-битной контрольной сумме — у которой ошибки возникают ровно каждый 65536 раз.
У меня получилось, что на этом тесте реальные алгоритмы пропускают в 6..15 раз больше ошибок, чем этот «сферически вакуумный».
Занятная цифра, надо будет её запомнить…sim31r
06.11.2018 01:56Byte injection наоборот, в 1.5 раза меньше пропустил ошибок, чем должен теоретически, на первый взгляд.
Тут многое зависит от алгоритма по которому ошибка имитируется.esaulenka
06.11.2018 10:29О, прошу прощения, я с арифметикой напутал.
100 млн. — это не суммарная цифра, это каждый тест запускался 1e8 раз. Т.е. вывод «CRC хуже идеального хэша на порядок» неверный. Хуже только в два раза в самом худшем случае. Ок, дядьки-математики, которые это когда-то придумали, реабилитированы :-)
emmibox
06.11.2018 17:28Не надо было изобретать велосипед.
Берете обычный HDLC
Начало и конец пакета префиксируется байтом 7E (старт-стоп).
внутри пакета 7E заменяется на 7D 5E, 7D на 7D 5D.
перед концом CRC16-CCITT (просто потому что так заведено)…
Далее длинна пакета внутри известна… Битые отбрасываете по критерию длинны и по критерию не соответствия CRC16. Это десятилетиями работает в миллиардах приложений.
datacompboy
06.11.2018 17:39длина пакета неизвестна, если есть раздувающие замены.
Polaris99 Автор
06.11.2018 17:48+1Кого ж такие мелочи уже волнуют. Тем более, что по сути вышел тот самый велосипед — уникальный байт-заголовок и CCITT в конце.
emmibox
06.11.2018 18:14При проектировании этого можно избежать используя уникальный «адрес» в рамках того же HDLC исключительно для пакетов длинна которых может быть неизвестна и другие уникальные адреса для пакетов фиксированных известных длин.
cheblin
как низко пал… Modbus
Anton131313
Причем тут modbus?