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

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

RS-485, ProfiBUS, 4-20 mA, Wi-Fi, GSM и так далее

Автор темы
Yuriy48
здесь недавно
здесь недавно
Сообщения: 4
Зарегистрирован: 04 мар 2015, 00:38
Ф.И.О.: Шульгин Юрий Николаевичь

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

Сообщение Yuriy48 » 04 мар 2015, 01:25

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

Аватара пользователя

Exactamente
частый гость
частый гость
Сообщения: 409
Зарегистрирован: 20 ноя 2012, 12:45
Ф.И.О.: :.О.N.Ф
Благодарил (а): 3 раза
Поблагодарили: 3 раза

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

Сообщение Exactamente » 04 мар 2015, 10:36

А там разве побайтово биты задом наперёд передаются, а не вся посылка?
«Сразу видно внимание к каждой мелочи, неиспорченным не осталось ничто».


Автор темы
Yuriy48
здесь недавно
здесь недавно
Сообщения: 4
Зарегистрирован: 04 мар 2015, 00:38
Ф.И.О.: Шульгин Юрий Николаевичь

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

Сообщение Yuriy48 » 04 мар 2015, 10:47

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

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

Аватара пользователя

MuadDib
не первый раз у нас
не первый раз у нас
Сообщения: 359
Зарегистрирован: 31 июл 2010, 08:12
Ф.И.О.: Журавлев Павел Евгеньевич
Поблагодарили: 1 раз

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

Сообщение MuadDib » 04 мар 2015, 16:36

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


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

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

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

Аватара пользователя

Exactamente
частый гость
частый гость
Сообщения: 409
Зарегистрирован: 20 ноя 2012, 12:45
Ф.И.О.: :.О.N.Ф
Благодарил (а): 3 раза
Поблагодарили: 3 раза

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

Сообщение Exactamente » 05 мар 2015, 00:29

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

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

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

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

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

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


>Можно поподробнее? Приведите, пожалуйста, пример такого алгоритма
Ну так... :oops:
«Сразу видно внимание к каждой мелочи, неиспорченным не осталось ничто».


Автор темы
Yuriy48
здесь недавно
здесь недавно
Сообщения: 4
Зарегистрирован: 04 мар 2015, 00:38
Ф.И.О.: Шульгин Юрий Николаевичь

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

Сообщение Yuriy48 » 05 мар 2015, 00:49

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

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

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

Аватара пользователя

MuadDib
не первый раз у нас
не первый раз у нас
Сообщения: 359
Зарегистрирован: 31 июл 2010, 08:12
Ф.И.О.: Журавлев Павел Евгеньевич
Поблагодарили: 1 раз

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

Сообщение MuadDib » 05 мар 2015, 05:42

В статье по второй ссылке есть раздел:
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, причем обработка идет от старшего разряда к младшему. Как этот пример связан с вашим исходным утверждением?
Yuriy48 писал(а):При вычислении CRC используется как прямое значение полинома, так и зеркальное (обратное).

Аватара пользователя

MuadDib
не первый раз у нас
не первый раз у нас
Сообщения: 359
Зарегистрирован: 31 июл 2010, 08:12
Ф.И.О.: Журавлев Павел Евгеньевич
Поблагодарили: 1 раз

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

Сообщение MuadDib » 05 мар 2015, 06:12

Exactamente писал(а):ну, для определённости пусть настройки с 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
здесь недавно
здесь недавно
Сообщения: 4
Зарегистрирован: 04 мар 2015, 00:38
Ф.И.О.: Шульгин Юрий Николаевичь

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

Сообщение Yuriy48 » 05 мар 2015, 10:53

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


Вернуться в «Интерфейсы, протоколы, связь»



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 0 гостей