Сети‎ > ‎Modbus‎ > ‎

CRC16

Метод CRC (Cyclic Redundancy Check) - один із методів розрахунку контрольної суми. В основі методу лежить представлення бітових послідовностей у вигляді многочленів з коефіцієнтами 0 або 1, де порядок біту відповідає степені доданка (починаючи з 0-го), а значення біту – його коефіцієнту. Використовується метод наступним чином. Вибирається утворюючий многочлен (назвемо його G(x)), який буде спільний для всіх вузлів мережі. Старший і молодший біт даного многочлену повинен дорівнювати 1. Послідовність всіх інформаційних бітів кадру формують многочлен кадру (назвемо M(x)). Кількість біт даного кадру m повинно бути більше кількості біт утворюючого многочлену r. Ідея полягає в тому, щоб в кінець кадру добавлялася така послідовність бітів, яка разом з іншими бітами кадру ділилася по модулю 2 на утворюючий многочлен без остачі. Отримувач, отримавши кадр, який містить контрольну суму, розділить його на G(x). Ненульова остача буде означати помилку.

Ділення по модулю 2 - означає використання при діленні арифметичних дій додавання без використання переносів, та віднімання без використання позичання, тобто заміняються на логічну операцію XOR.

Детальний алгоритм:

-       при степені r многочлену G(x), добавляється r нульових бітів до останнього, щоб він мав m+r бітів, тобто відповідав многочлену xr·M(x);

-       ділиться бітова послідовність по модулю 2, яка відповідає многочлену xr·M(x) на бітову послідовність утворюючого многочлену G(x);

-       остача від ділення і буде являти собою контрольну суму, яка добавляється в кінець кадру.

Розглянемо приклад. Вираховується контрольна сума для кадру 1101011011 при утворюючому многочлені G(x)=x4+x+1 (10011) (рис.3.6). Відповідно до умови будемо ділити 1101011011, які доповнюються 4-ма логічними нулями на 10011. На рисунку показано, що при бінарному діленні, замість операції віднімання використовується операція виключаючого АБО (XOR). Остача і відповідно контрольна сума буде 1110. В мережу буде відправлений кадр 11010110111110.

 Контрольна сума CRC використовується в багатьох мережних протоколах з різними утворюючими многочленами. Наприклад в Modbus використовується метод CRC16 з використанням 16-бітної контрольної суми і утворюючим многочленом G(x)=x15+x13+1 (тобто 10100000 00000001). Популярним також є CRC32, який має 32-бітну контрольну суму.

Алгоритм обрахунку CRC, наведений вище, доволі складний, тому на практиці часто використовують більш простіші. Наприклад, в мережному обладнані застосовують алгоритм з використанням регістру зсуву, який апаратно простіше реалізовується. Інколи для швидшого обрахунку використовують попередньо створені таблиці всіх можливих комбінацій CRC для старшого і молодшого регістрів. 

 

ДОДАТОК 1. Програма розрахунку CRC16.

 

Алгоритм обрахунку для CRC, який наведений вище як правило не використовується. На практиці користуються алгоритмом, який базується на закладених даних готових результатів обчислень CRC по будь якій з комбінацій байтів. Це прискорює процес обрахунку, що надзвичайно важливо при обміні. Однак для кращого розуміння процесу розрахунку і для можливості його використання, наприклад, в лабораторних дослідах, можна скористатися алгоритмом і програмою, наведеною нижче.

CRC16 використовує характеристичний поліном вигляду:

x16+x15+x2+1 тобто 1010000000000001 (А00116)

На початку розрахунку виділяють слово (два байти) під поле  CRC і заповнюють всі біти логічними одиницями. Перший байт повідомлення(кадру) складують по виключному АБО з даним полем. Перевіряють нульовий біт на наявність одиниці. При негативному результаті проводять побітовий зсув CRC на один біт вправо, заповнюючи старший біт нулем. При позитивному зсув також проводять, а після цього добавляють по виключному АБО характеристичний поліном, тобто А00116. Операцію зсуву з перевіркою нульового біту проводять 8 раз.

Далі, цю саму процедуру проводять для інших байтів повідомлення. Результат передають в такій послідовності: спочатку молодший байт, а потім старший.

Алгоритм, як бачимо, доволі простий. Але для реалізації на мові Basic є певні труднощі, пов’язані з відсутністю вбудованих функцій для реалізації побітового зсуву та беззнакового цілого (16 бітного слова). Першу проблему подолали заміною необхідної функції діленням націло, другу – конвертацією типів змінних з слідкуванням за знаком.

Таким чином, вийшла програма, лістинг якої показаний нижче.        Вона складається з двох функцій:

CRCCHeck – функція, для генерації CRC16 по вказаному повідомленню в 16-ковому форматі;

sh_r – функція, яка реалізовує побітове зміщення вправо на 1 біт з заповненням старшого біту нулем.

Треба відмітити, що функція CRCCHeck видає код CRC в форматі: молодший_байт_старший_байт в 16-ковому форматі тексту. Для перевірки програми вказана процедура proba.

----------------------------------------------------------

Sub proba()

 MsgBox CRCCheck("0100030002")

End Sub

Function CRCCheck(MesageStr As String) As String

 Dim LenMes As Integer ‘довжина кадру

 Dim Polinom As Integer ‘характерист. поліном

 Dim CRC As Integer ‘контр.сума

 Dim ByteMesStr As String, ByteMesBt As Byte 'байт в символьному і числовому форматі

 Polinom = &HA001

 LenMes = Len(MesageStr)

 кількість символів повинна бути парна

 If LenMes \ 2 <> LenMes / 2 Then MesageStr = "0" & MesageStr

 LenMes = Len(MesageStr)

 

 CRC = &HFFFF ’початкове значення

 Dim i As Integer, bit As Integer

 For i = 1 To LenMes - 1 Step 2 ‘перебираєм кожний байт кадру

  ByteMesStr = Mid(MesageStr, i, 2) ‘байт - це 2 16-кові  символи

  ByteMesBt = CByte(val("&h" & ByteMesStr)) ‘перетворюємо в 10-ковий формат

  CRC = CRC Xor ByteMesBt

  For bit = 1 To 8 ‘зміщення проводимо 8 разів

   If (CRC / 2&) <> (CRC \ 2&) Then

    CRC = sh_r(CRC) ‘зміщуємо на 1 біт вправо

    CRC = CRC Xor Polinom ‘якщо 0-вий біт =1 - виключне OR з поліномом

   Else

    CRC = sh_r(CRC)

   End If

  Next

 Next

 CRCCheck = Hex(CRC) ‘переводимо в 16-ковий вигляд при необхідності добавляємо вперед нулі

 While Len(CRCCheck) <> 4 '             -

 CRCCheck = "0" & CRCCheck '            -

 Wend '                                 -

 '---------------------------------------

 CRCCheck = Mid(CRCCheck, 3, 2) & Mid(CRCCheck, 1, 2) ‘молодший байт передається першим

 End Function

 

‘реалізація зміщення на один біт в право

--------------------------------------------------------------

Function sh_r(val As Integer) As Integer

 Dim val1 As Long

 Const Two As Long = 2 ‘в Бейсіку немає беззнакового 16-бітного цілого, тому приходиться хитрити

If val < 0 Then val1 = CLng(val) + 65536 Else val1 = CLng(val)

 sh_r = CInt(val1 \ Two) ‘ділення націло приводить до необхідного зміщення

End Function

--------------------------------------------------------

 

 

 

 

 

 
 
 
 
 
 
 
Comments