Проверка истинности данных циклическимизбыточным кодом в устройствах с однопроводным интерфейсом

January 12, 2013 by admin Комментировать »

Общие положения

Семейство устройств с однопроводным интерфейсом фирмы Dallas Semiconductor отличает та особенность, что связь с ними осуществляется через единственный провод посредством специальной системы команд, называемой однопроводным протоколом. Отличительной чертой каждого из этих устройств является встроенное 8-байтное ПЗУ, содержащее уникальный идентификационный код устройства. Содержимое этого 8-байтного кода показано на рис. 2.6.

Рис. 2.6. Содержание 8-байтного ПЗУ. (СЗР старший значащий разряд; МЗР младший значащий разряд).

Младший байт содержит код, свидетельствующий о принадлежности к семейству устройств с однопроводным интерфейсом, определяя одновременно функциональное назначение прибора. Например, DS1820 имеет код 10h, DS1990A код 01h, DS1991 код 02h и т.д.. Поскольку к одному коммуникационному проводу может быть подключено сразу несколько устройств различного функционального назначения, процессор должен иметь возможность безошибочно разобраться, какие именно устройства подключены. Код принадлежности помогает решить эту задачу. Следующие 6 байт ПЗУ содержат уникальный серийный номер конкретного экземпляра, позволяющий отличить его от других устройств данного семейства. Этот 48-битовый код можно рассматривать как индивидуальный адрес устройства. Старший байт ПЗУ содержит результат проверки истинности данных циклическим избыточным кодом ЦИК (cyclic redundancy check CRC). Этот код вычисляется на основе содержимого предыдущих

семи байтов. Когда процессор начинает сеанс связи с устройством, он первым делом читает 8 байт ПЗУ этого устройства, причем младший значащий бит читается первым. Если ЦИК, рассчитанный процессором на основе принятых данных (семи младших байтов), совпадает с содержимым 8-го байта ПЗУ, то считается, что данные приняты верно. Если эти значения не совпадают, то процесс чтения ПЗУ повторяется.

Некоторые из устройств, в дополнение к восьми байтам ПЗУ, имеют до 64кбайт оперативного запоминающего устройства (ОЗУ), доступ к которому осуществляется посредством специальных команд. Данные в эту память записываются процессором обычным образом, затем к ним добавляется рассчитанный процессором ЦИК и также записывается в ПЗУ устройства. При получении (чтении) данных из устройства процесс обратный. Процессор, приняв данные от устройства, рассчитывает на их основе ЦИК и сравнивает его со значением, хранимым в памяти устройства как ЦИК данных. Если значения ЦИК одинаковы, то данные приняты верно. Чтобы в полной мере воспользоваться преимуществами, даваемыми данной системой проверки истинности, нужно понять, что она собой представляет и как работает. Кроме того, необходимо освоить практический метод расчета значений ЦИК процессором как в программной, так и в аппаратной реализации.

Проверка на истинность последовательных данных может осуществляться различными способами. Распространенным способом является включение в каждый проверяемый пакет данных дополнительного бита, указывающего на наличие или отсутствие ошибки. Например, при передаче 8-битовых пакетов ASCII символов к каждому 8-битовому пакету добавляется один бит (бит паритета), указывающий, есть или нет ошибки при передаче этого пакета. Предположим, что пакет данных состоит из битовой строки 11010001. Девятый бит добавляется с таким расчетом, чтобы суммарное количество битов, содержащих единицу, было нечетным. Таким образом, в приведенный выше битовый пакет должна быть добавлена единица. Теперь он будет выглядеть как 111010001. Подчеркнутый символ представляет собой дополнительный бит, так называемый бит паритета, вводимый для того, чтобы сделать суммарное количество единичных битов в 9-битовом пакете нечетным. Если приемник принял пакет 111010001, то данные переданы и приняты верно. Если же приемник принял, например, 111010101, где седьмой слева бит принят неверно, то общее количество единиц в пакете уже не будет нечетным, что свидетельствует о наличии ошибки. Обнаружив ошибку, приемник предпримет соответствующие действия. Такая схема называется проверкой на нечетность. Можно договориться о том, чтобы общее число единиц в пакете было четным. Эта схема называется проверкой на четность. Обе схемы, к сожалению, могут обнаружить только нечетное количество битовых ошибок. Если в рассмотренном только что примере пакет будет поврежден сразу в 6-м и 7-м битах, т.е. будет принята последовательность 111011101, то контроль паритета по нечетности не обнаружит ошибки, так как общее количество единичных битов будет нечетным. Указанная ошибка не будет обнаружена и в случае контроля на четность.

Однопроводный ЦИК фирмы Dallas Semiconductor

Схема проверки истинности потока данных, основанная на вычислении циклического избыточного кода, является наиболее эффективной при локализации ошибок и требует минимальных аппаратных затрат. Опишем применяемую Dallas Semiconductor схему определения ошибок, не приводя сложных математических обоснований метода. Работу схемы проще всего пояснить на примере ее аппаратной реализации. Аппаратно схема представляет собой сдвиговый регистр с обратной связью (рис. 2.7).

Рис. 2.7. Аппаратная реализация 8-битового алгоритма проверки истинности данных циклическим избыточным                                                                              кодом,

соответствующая полиномиальной функции X + X + X +1.

Процедуру выделения ошибки часто описывают в виде полиномиальной функции формальной переменной X. Показатели степени ненулевых членов этого полинома показывают, на какие разряды сдвигового регистра замыкаются петли обратной связи. Число разрядов сдвигового регистра (в аппаратной реализации) или степень полинома (при математическом описании) определяют разрядность вычисляемого ЦИК. Обычно при цифровом обмене данными используют 16разрядные ЦИК. Dallas Semiconductor при чтении 64-битовых ПЗУ своих устройств использует 8-разрядные ЦИК. 64-битовый код ПЗУ состоит из 8-битового кода принадлежности к семейству устройств, поддерживающих однопроводный интерфейс, 48-битового серийного номера устройства и 8битового ЦИК, рассчитанного на основе первых 56 битов содержимого ПЗУ. ЦИК содержится в старшем байте ПЗУ. Расположение точек входа петель обратной связи, обозначенных на рис. 2.7 логическими элементами “исключающее ИЛИ” (или, что то же самое, степени ненулевых членов полинома), определяет свойства ЦИК и способность алгоритма выявить определенные классы ошибок при передаче данных. Алгоритм, приведенный на рис. 2.7, способен распознать следующие классы ошибок:

•     Любое нечетное число ошибок в любом месте 64-битовой посл едовател ьности.

•     Все двойные ошибки (ошибки в двух смежных битах) в любом месте 64-битовой последовательности.

•     Любые кластеры ошибок в пределах 8-битового “окна”, т.е. кластеры, содержащие от 1 до 8 неправильных битов.

•     Большинство кластерных ошибок с размерами кластера, превышающими 8 бит.

Входные данные подаются на один из входов двухвходового логического элемента “исключающее ИЛИ” (XOR). Ко второму входу этого элемента подключается выход старшего разряда 8-разрядного сдвигового регистра (рис. 2.7). Математически сдвиговый регистр может рассматриваться как схема деления. Входные данные это делимое, а сдвиговый регистр с цепями обратной связи служит делителем. Целая часть полученного частного отбрасывается, а остаток представляет собой искомый ЦИК, который окажется в сдвиговом регистре, как только последний бит данных пройдет на вход. Из такого аппаратного описания алгоритма видно, что результат (значение ЦИК) очень сложным образом зависит от предыстории контролируемой последовательности битов. Поэтому комбинации ошибок, способные пройти незамеченными через такой контроль, очень редки.

В табл. 2.1 показан пошаговый расчет ЦИК исходной 64битовой последовательности. Каждая строка левого столбца отражает содержимое сдвигового регистра после подачи на вход очередного бита из 64-битовой последовательности пересылаемых данных. Первым на вход подается младший бит младшего байта. В начале процедуры все биты сдвигового регистра сброшены (т.е. представляют собой нули). Расчет начинается подачей младшего бита 64-битовой последовательности. В этом примере младший байт равен 02h и представляет собой код принадлежности к семейству устройств с однопроводным интерфейсом. После того как последний, 56-й бит (код принадлежности + серийный номер) будет введен в сдвиговый регистр, в нем окажется число 10100010 (или A2h в 16-ричном выражении). Это и будет ЦИК для введенной последовательности из 56 битов. Если это число использовать в качестве входной последовательности для следующих восьми шагов, то в результате в сдвиговом регистре останутся одни нули. Иными словами, если вы проверяете полное 64-битовое ПЗУ, хранящее в своем старшем байте ЦИК первых 56 бит, то, не ограничиваясь при вводе 56-ю битами, а вводя все 64, получите очищенный сдвиговый регистр (все нули). Отмеченный факт является свойством описываемого алгоритма. Его можно сформулировать и в более общей форме. Если любое 8-битовое число, находящееся в данный момент в сдвиговом регистре, использовать в качестве входной последовательности для последующих 8 шагов сдвига, то результатом будет очищенный регистр, все разряды которого содержат нуль. Это можно объяснить следующим образом. При описанном выше условии (равенстве содержимого регистра и входной последовательности) выход старшего разряда регистра (8-й шаг) всегда будет равен входному биту данных, а на выходе логического элемента “исключающее ИЛИ” всегда будет нуль. Этот нуль по цепи обратной связи поступает в младший разряд сдвигового регистра (1-й шаг). При поступлении на вход следующего бита нулевой бит младшего разряда регистра сдвинется в следующий разряд, а на его место поступит нулевой же бит с выхода элемента “исключающее ИЛИ”. После восьми таких шагов во всех разрядах сдвигового регистра окажутся нули. Структура 64-битового ПЗУ в однопроводных устройствах Dallas Semiconductor использует указанное свойство для упрощения аппаратного обеспечения устройств, применяемые для чтения ПЗУ. Сдвиговым регистр читающего устройства очищается, а затем читаются 64 бита данны1х из ПЗУ контролируемого устройства, включая и байт ЦИК. Если данные прочитаны верно, то   регистр читающего

устройства будет          снова содержать                    нули, что легко

фиксируется. Если       же в сдвиговом                 регистре окажется

ненулевое значение, операцию чтения нужно повторить.

Таблица 2.1. Пример расчета ЦИК 64-битовой последовательности.

Содержание 64-битового ПЗУ: А200000001В81С02 Hex Код семейства:

О                                           2                          Шестнадцитиричный (Hex)

0000                                    0010                                         Двоичный (Bin)

Серийный номер:

00000001В81С Hex

0            0000 0000 0000 0000 0000 0000 0001 1011 1000 0001 1100 Bin

ЗНАЧЕНИЕ ЦИК

ВХОДНОЕ

ЗНАЧЕНИЕ

00000000

0

00000000

1

10001100

0

2

01000110

0

00100011

0

10011101

0

11000010

0

0

01100001

0

10111100

0

01011110

0

00101111

1

с

00010111

1

00001011

1

00000101

0

10001110

0

1

01000111

0

10101111

0

11011011

0

11100001

0

8

11111100

1

11110010

1

11110101

1

01111010

0

в

00111101

1

00011110

1

10000011

0

11001101

0

1

11101010

0

01110101

0

10110110

0

01011011

0

0

10100001

0

11011100

0

01101110

0

00110111

0

0

10010111

0

11000111

0

11101111

0

11111011

0

0

11110001

0

11110100

0

01111010

0

00111101

0

0

10010010

0

01001001

0

10101000

0

01010100

0

0

00101010

0

00010101

0

10000110

0

01000111

0

0

10101101

0

11011010

0

01101101

0

10111010

0

0

01011101

0

10100010 = А2Н = ЦИК для [00000001 В81С(Серийный номер) + 02(Код семейства)]

10100010

0

01010001

1

00101000

0

2

00010100

0

00001010

0

00000101

1

00000010

0

А

00000001

1

00000000 = ООН = ЦИК для [А2(ЦИК) + 00000001 В81С(Серийный номер) + 02(Код семейства)].

До сих пор мы обсуждали аппаратную реализацию процесса вычисления ЦИК. Но можно вычислить ЦИК и программным способом. В табл. 2.2 приведен ассемблерный код такой процедуры. Операция XRL над содержимым регистра А и константой 18h соответствует в аппаратной реализации наличию логических элементов “исключающее ИЛИ” на входах четвертого и пятого разрядов сдвигового регистра (см. рис. 2.7).

DOCRC:

PUSH

ACC

;сохраняем аккумулятор

PUSH

В

;сохраняем регистр В

PUSH

ACC

;сохраняем биты, ;подлежащие сдвигу

MOV

В,#8

устанавливаем сдвиг = 8 бит

CRCLOOP:

XRL

RRC

A,CRC

A

подсчитываем ЦИК

MOV

A,CRC

;получаем последнее ;значение ЦИК

JNC

ZERO

;пропускаем, если данные = 0

XRL

A,#18H

;обновляем значение ЦИК

ZERO:

RRC

A

;позиционируем новыйЦИК

MOV

CRC,A

;запоминаем новый ЦИК

POP

ACC

;получаем оставшиеся биты

RR

A

;позиционируем следующий ;бит

PUSH

ACC

;сохраняем оставшиеся биты

DJNZ

B,CRC LOOP

;повторяем для 8-ми битов

POP

ACC

;очищаем стек

POP

В

восстанавливаем регистр В

POP

RET

ACC

;восстанавливаем

;аккумулятор

Другим программным решением является создание таблицы преобразования, определяющей связь между любым текущим 8-битовым значением регистра ЦИК и любым 8битовым отрезком входных данных. В простейшем случае, когда текущее значение регистра ЦИК равно 00h, можно рассчитать 256 возможных битовых комбинаций входного байта и разместить их в матрице, где индекс матрицы будет равен значению входного байта (т.е. индекс будет пробегать значения от 0 до 255, и число, размещенное в i-й позиции, будет равно i). Можно показать, что если текущее значение регистра ЦИК отлично от нуля, то для любого заданного значения ЦИК и любого входного байта таблица преобразования будет состоять из тех же 255 значений, но расставленных в таблице в соответствии с формулой:

Новое значение ЦИК = Таблица (i),

где i = (Текущее значение ЦИК) XOR (Входной байт).

Когда текущее значение ЦИК равно 00h, данная формула приводит к описанному выше простейшему случаю. Второе программное решение сокращает время расчета, так как операции производятся не над битами, как в первом варианте, а над байтами. Однако в этом случае требуется 256 байт дополнительной памяти для размещения таблицы преобразования. Для первого варианта программного решения память требуется только для размещения программного кода. Пример программного кода для второго варианта приведен в табл. 2.3. Табл. 2.4 иллюстрирует использование метода таблицы преобразования на уже приводившемся ранее примере. Два свойства алгоритма вычисления ЦИК могут помочь в отладке программного кода. Первое из них уже упоминалось при описании аппаратной реализации алгоритма, а именно: если текущее значение регистра ЦИК использовать в качестве следующего входного байта, то в результате в регистре ЦИК окажутся одни нули. Второе свойство заключается в том, что если в качестве входной последовательности использовать байт, инверсный байту, содержащемуся в данный момент в регистре ЦИК, то через восемь шагов в регистре ЦИК окажется число 35h (53 в десятичном выражении). Эта процедура показана в табл. 2.5.

Var

CRC : Byte Procedure Do^CRC(X: Byte);

{

Эта процедура вычисляет ЦИК для всех байтов, проходящих через однопроводную шину. Результат накапливается в глобальной переменной CRC.

}

Const

Table : Array[0…255] of Byte = (

0,                              94,       188,       226,       97,       63,       221,       131,      194,      156,      126,       32,       163,      253,                                31,       65,

157,                         195,      33,        127,      252,      162,       64,        30,       95,         1,       227,       189,       62,       96,                                130,      220,

35,                           125,      159,       193,       66,       28,       254,       160,      225,      191,      93,         3,        128,      222,                                60,       98,

190,                         224,       2,         92,       223,      129,       99.        61,       124,       34,       192,       158,       29,       67,                                161,      255,

70,                            24,       250,       164,       39,       121,      155,       197,      132,      218,      56,        102,      229,      187,                                89,        7,

219,                         133,      103,       57,       186,      228,        6,         88,       25,        71,       165,       251,      120,      38,                                196,      154,

101,                          59,       217,       135,        4,        90,       184,       230,      167,      249,      27,        69,       198,      152,                                122,      36,

248,                         166,      68,        26,       153,      199,       37,        123,      58,       100,      134,       216,       91,        5,                                231,      185,

140,                         210,      48,        110,      237,      179,       81,        15,       78,        16,       242,       172,       47,       113,                                147,      205,

17,                            79,       173,       243,      112,      46,       204,       146,      211,      141,      111,       49,       178,      236,                                14,       80,

175,                         241,      19,        77,       206,      144,      114,       44,       109,       51,       209,       143,       12,       82,                                176,      238,

50,                           108,      142,       208,       83,       13,       239,       177,      240,      174,      76,        18,       145,      207,                                45,       115,

202,                         148,      118,       40,       171,      245,       23,        73,        8,        86,       180,       234,      105,      55,                                213,      139,

87,                             9,       235,       181,       54,       104,      138,       212,      149,      203,      41,        119,      244,      170,                                72,       22,

233,                         183,      85,        11,       136,      214,       52,        106,      43,       117,      151,       201,       74,       20,                                246,      168,

116,                          42,       200,       150,       21,       75,       169,       247,      182,      232,      10,        84,       215,      137,                                107,      53);

Begin

CRC : = Table[CRC xor X];

End;

Таблица 2.4. Использование метода таблицы преобразования для вычисления ЦИК (в примере приведены те же исходные данные, что и в табл. 2.1).

Текущее значение ЦИК ( = текущему табличному индексу)

Входные

данные

Новый индекс ( = результату операции "Текущий ЦИК" XOR "Входные данные")

Новая позиция (индекс) в таблице ( = новому значению ЦИК)

00000000 = ООН

00000010 = 02Н

(ООН XOR 02Н) = 02Н = 2Dec

ТаЫе[2] = 10111100 = ВСН = 188Dec

10111100 = вен

00011100 = 1СН

(BCHXOR 1СН) = A0H = 160Dec

Table[160] = 10101111 = AFH = 175Dec

10101111 = AFH

10111000 = В8Н

(AFH XOR В8Н) = 17Н = 23Dec

Table[23] = 00011110 = 1 ЕН = 30Dec

00011110 = 1 ЕН

00000001 = 01Н

(1 EH XOR 01H) = 1FH = 31 Dec

Table[31] = 11011100 = DCH = 220Dec

11011100 = DCH

00000000 = ООН

(DCH XOR 00H) = DCH = 220Dec

Table[220] = 11110100 = F4H = 244Dec

11110100 = F4H

00000000 = ООН

(F4H XOR 00H) = F4H = 244Dec

Table[244] = 00010101 = 15Н = 21 Dec

00010101 = 15Н

00000000 = ООН

(15H XOR ООН) = 15H = 21 Dec

Table[21] = 10100010 = А2Н = 162Dec

10100010 = А2Н

10100010 = А2Н

(A2H XOR A2H) = 00H = ODec

Table[0] = 00000000 = ООН = 0 Dec

В таблице: Н шестнадцатиричное число: Dec десятичное число.

Таблица 2.5. Изменение содержимого сдвигового регистра генератора ЦИК при подаче на его вход байта, комплементарного байту, содержащемуся в нем в данный момент.

Значение

регистра ЦИК

Вход

Х0

х

Х2

Х

Х

Х

Х

Х

*■

Х

1

Х0

х

Х

Х

Х

Х

Х

Х

1

1

Х0

Х

Х

Х

Х

Х

Х

1

1

1

Х

Х

Х

Х

Х

Х

О

1

1

1

Х

Х

Х

Х

Х

1

О

1

1

О

Х

Х

Х

Х

1

1

О

1

О

1

Х

Х

Х

О

1

1

О

1

О

1

Х

Х

О

О

1

1

О

1

О

1

Z

Значение регистра ЦИК                                                            Вход

Z = 35Н = 53Dec (конечное значение ЦИК) ; значение, комплементарное

Источник: Карначёв А.С., Белошенко В.А., Титиевский В.И., Микролокальные сети: интеллектуальные датчики, однопроводный интерфейс, системы сбора информации. Донецк: ДонФТИ НАНУ Украины, 2000. 199с. с ил.

Оставить комментарий

микросхемы мощности Устройство импульсов питания пример приемника провода витков генератора выходе напряжение напряжения нагрузки радоэлектроника работы сигнал сигнала сигналов управления сопротивление усилитель усилителя усиления устройства схема теория транзистора транзисторов частоты