Вычисление CRC с зеркальным значением полинома.

[Yuriy48]

При вычислении CRC используется как прямое значение полинома, так и зеркальное (обратное). Везде пишется, что зеркальное значение применяется там, где биты из байта передаются младшим разрядом вперёд. Сама по себе такая связка понятна, вычислений меньше. Но для меня не понятна следующая ситуация. Вот UART передаёт младшие биты вперёд, но, если на другом конце стоит тоже UART, то принятый байт будет правильным и при его использовании в вычислении CRC биты будут в том же порядке, как и исходного байта и, соответственно, зеркального вычисления не требуется. Вывод один (может он и не правилен): зеркальное вычисление нужно там, где приёмник и передатчик имеют разные способы передачи бит из байта. Например: одно из устройств имеет UART, а другое нет и организовывает передачу или приём бит программным способом, при чём старшими битами вперёд.
Подскажите, правильно ли я мыслю, или что-то ещё не учитываю?

[Exactamente]

А там разве побайтово биты задом наперёд передаются, а не вся посылка?

[Yuriy48]

А там разве побайтово биты задом наперёд передаются, а не вся посылка?

Конечно, вся посылка передаётся целиком, но побайтно, вспомните: стартовый и стоповый биты, бит паритета. В общем слчае строка может передаваться и частями, если нет временных разделителей посылок, как в ModBus-е.

[MuadDib]

При вычислении CRC используется как прямое значение полинома, так и зеркальное (обратное).

Можно поподробнее? Приведите, пожалуйста, пример такого алгоритма. И, желательно, ссылку на код. Лично мне алгоритмы CRC с "зеркальным" значением не попадались.

Везде пишется, что зеркальное значение применяется там, где биты из байта передаются младшим разрядом вперёд. Сама по себе такая связка понятна, вычислений меньше. Но для меня не понятна следующая ситуация. Вот UART передаёт младшие биты вперёд, но, если на другом конце стоит тоже UART, то принятый байт будет правильным и при его использовании в вычислении CRC биты будут в том же порядке, как и исходного байта и, соответственно, зеркального вычисления не требуется. Вывод один (может он и не правилен): зеркальное вычисление нужно там, где приёмник и передатчик имеют разные способы передачи бит из байта. Например: одно из устройств имеет UART, а другое нет и организовывает передачу или приём бит программным способом, при чём старшими битами вперёд.
Подскажите, правильно ли я мыслю, или что-то ещё не учитываю?

Ваш вывод вполне логичен, но сама по себе система, где узлы используют UART с разным порядком бит, будет выполнять большой объем лишней работы. Ведь CRC обычно составляет малую часть от длины сообщения. Ну, допустим, получили вы зеркальное отражение контрольной суммы "бесплатно", прямо из алгоритма. Но вам все равно придется делать зеркальное отражение каждого байта полезной нагрузки - или при приеме, или при передаче. Выглядит как экономия "на спичках".
Может, речь идет о каких-то трюках с аппаратными вычислителями CRC?

[Exactamente]

А там разве побайтово биты задом наперёд передаются, а не вся посылка?

Конечно, вся посылка передаётся целиком, но побайтно, вспомните: стартовый и стоповый биты, бит паритета. В общем слчае строка может передаваться и частями, если нет временных разделителей посылок, как в ModBus-е.

ну, для определённости пусть настройки с 8 databits, остальное неважно, тогда если пакет у отправителя (цифры - сквозная нумерация битов):
[0..7][8..16]...

то отправляется, насколько я понимаю, в таком порядке:
[16..8][stop][7..0]

а вы предполагаете, что отправляется так:
[7..0][stop][16..8]

В последнем случае, похоже, трюк с зеркальным полиномом не имеет смысла.


>Можно поподробнее? Приведите, пожалуйста, пример такого алгоритма
Ну так...

[Yuriy48]

При вычислении CRC используется как прямое значение полинома, так и зеркальное (обратное).

Можно поподробнее? Приведите, пожалуйста, пример такого алгоритма. И, желательно, ссылку на код. Лично мне алгоритмы CRC с "зеркальным" значением не попадались.

http://bookfi.org/book/594892
https://ru.wikipedia.org/wiki/%D6%E8%EA ... te_note-25
https://ru.wikibooks.org/wiki/%D0%A0%D0 ... 0%B4#CRC-4

Везде пишется, что зеркальное значение применяется там, где биты из байта передаются младшим разрядом вперёд. Сама по себе такая связка понятна, вычислений меньше. Но для меня не понятна следующая ситуация. Вот UART передаёт младшие биты вперёд, но, если на другом конце стоит тоже UART, то принятый байт будет правильным и при его использовании в вычислении CRC биты будут в том же порядке, как и исходного байта и, соответственно, зеркального вычисления не требуется. Вывод один (может он и не правилен): зеркальное вычисление нужно там, где приёмник и передатчик имеют разные способы передачи бит из байта. Например: одно из устройств имеет UART, а другое нет и организовывает передачу или приём бит программным способом, при чём старшими битами вперёд.
Подскажите, правильно ли я мыслю, или что-то ещё не учитываю?

Ваш вывод вполне логичен, но сама по себе система, где узлы используют UART с разным порядком бит, будет выполнять большой объем лишней работы. Ведь CRC обычно составляет малую часть от длины сообщения. Ну, допустим, получили вы зеркальное отражение контрольной суммы "бесплатно", прямо из алгоритма. Но вам все равно придется делать зеркальное отражение каждого байта полезной нагрузки - или при приеме, или при передаче. Выглядит как экономия "на спичках".
Может, речь идет о каких-то трюках с аппаратными вычислителями CRC?

Ну кто хочет все эти зеркальные отображения, они только жизнь портят. Реально я с такими случаями не сталкивался, но в вопросе разобраться хочется. Получается так, что, если приёмник и передатчик биты передают по разному, то хочешь - не хочешь, экономь - не экономь, а программно их переставлять придётся, б-р-р-р-р. А вот контрольную сумму можно подсчитать без перестановки и до этой операции, используя простые алгоритмы с зеркальным значением полинома (см. ссылки выше). И, если всё будет ОК, то можно перейти и к перестановке. Практически все широко применяемые микросхемы, реализующие UART, биты передают младшими разрядами вперёд.

[MuadDib]

В статье по второй ссылке есть раздел:

11. "Reflected" Table-Driven Implementations

Вы об этом аспекте спрашиваете?

Книжка по первой ссылке не качается. По третьей ссылке, в разделе CRC-4 мы видим такой код:

Код: Выделить всё

        string CRCTableCell(int value)
        {
          int r;
 
          r = (value << 8) & 0xFF00;
          int shifted_Polinom = Polinom << (3+8); // 3 сдвига для дополнения полинома до размера 1 байта, 8 сдв. для заполнения нулями
 
 
          for(byte j=0; j<8; j++)
          {
              if ((r & (1 << 15)) == 0x8000)
              {
                  r ^= shifted_Polinom;
                  r = (r << 1);
              }
              else r = r << 1;
          }
 
          r = r >> 8;
          return String.Format("0x{0:X2}", r);
        }

Этот алгоритм обрабатывает младшие 8 разрядов параметра value, причем обработка идет от старшего разряда к младшему. Как этот пример связан с вашим исходным утверждением?

При вычислении CRC используется как прямое значение полинома, так и зеркальное (обратное).

[MuadDib]

ну, для определённости пусть настройки с 8 databits, остальное неважно, тогда если пакет у отправителя (цифры - сквозная нумерация битов):
[0..7][8..16]...

то отправляется, насколько я понимаю, в таком порядке:
[16..8][stop][7..0]

а вы предполагаете, что отправляется так:
[7..0][stop][16..8]

Боюсь, тут возникла некоторая путаница. Алгоритмы CRC трактуют сообщение как некое очень большое число. Начальный (нулевой) байт содержит старшие разряды этого числа, последний (n-1) байт - младшие. Иными словами, самый старший бит начального байта - это старший бит всего сообщения. Корректно было бы записать ваш пример с двухбайтовым сообщением так:

В памяти у отправителя:
[15..8][7..0]
Порядок битов в памяти не играет роли

Передача осуществляется в таком порядке:
[start-bit] [8..15] [stop-bit] [start-bit] [0..7] [stop-bit]

При передаче последовательности байтов через UART порядок байтов не меняется, но биты каждого байта передаются, как правило, начиная с младшего. Иными словами, чередование битов в линии передачи нарушается по сравнению с исходным числом-сообщением. Если используется аппаратная схема вычисления CRC, нарушение порядка передачи битов может вызывать нестыковки с традиционным "софтовым" алгоритмом.

[Yuriy48]

Во вложении дана статья не читающаяся по первой ссылке. Там всё довольно подробно описано про расчёт CRC.
Чвствую, что MuadDib суть проблемы ухватил. Теперь, двигаясь в этом же русле, принять бы окончательное решение по поставленном вопросу. С другой стороны, похоже, что вопрос перетекает в следующую плоскость: "А кто ни будь реально сталкивался с такой ситуацией?".