Устройство для формирования контрольного признака

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в цифровых системах повышенной информационной надежности. Цель изобретения - сокращение аппаратурных затрат устройства. Устройство содержит регистры 2, 5, блок 3 памяти, сумматор 4, элементы И 6-9, элементы ИЛИ 10, 11, 18, счетчики 12, 15, дешифраторы 13, 16, элемент НЕ 14, элемент задержки 17. Информация поступает на информационный вход 1 устройства, сопровождаемая сигналами на тактовом входе 21 устройства. Передается информация вместе с контрольным признаком с выхода 19 устройства. 1 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (зов G 06F 11/08

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (21) 4807810/24 (22) 29.03.90 (46) 23.11.92. Бюл. hb 43 (72) В.С.Василенко и В.B.Âàñèëåíêî (56) Авторское свидетельство СССР

М 660054, кл. G 06 F 11/08, 1977.

Авторское свидетельство СССР

N. 1695305, кл. G 06 F 11/08, 1989. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

КОНТРОЛЬНОГО ПРИЗНАКА (57) Изобретение относится к автоматике и вычислительной технике и может быть ис;„, Ы„„1777141 А1 пользовано в цифровых системах повышенной информационной надежности. Цель изобретения — сокращение аппаратурных затрат устройства. Устройство содержит регистры 2, 5, блок 3 памяти, сумматор 4, элементы И 6 — 9, элементы ИЛИ 10, 11, 18, . счетчики 12, 15, дешифраторы 13, 16, элемент НЕ 14, элементзадержки 17. Информация поступает на информационный вход 1 устройства, сопровождаемая сигналами на тактовом входе 21 устройства. Передается информация вместе с контрольным признаком с выхода 19 устройства. 1 ил.

1777141

Изобретение относится к автоматике и вычислительной технике и может быть использовано в цифровых системах повышенной информационной надежности.

Целью изобретения является сокращение аппаратурных затрат устройства.

Функциональная схема устройства приведена на чертеже, где приняты следующие обозначения: информационный вход 1 устройства, первый регистр 2, блок 3 памяти, сумматор 4, второй регистр 5, элементы И

6-9, третий элемент ИЛИ 10, второй элемент ИЛИ 11, второй счетчик 12, второй дешифратор 13. элемент НЕ 14, первый счетчик 15, первый дешифратор 16, элемент задержки 17, первый элемент ИЛИ.18, выход 19 устройства, установочный и тактовый входы 20, 21 устройства GQQTBGTcTBGHHo, формирователь 22 импульсов.

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

BY-кода. Код i-й группы, рассматриваемый как некоторое число Q, умножается на соответствующий весовой коэффициент С . От суммы полученных произведений вычисляется остаток по контрольному модулю в соответствии с выражением г(А) = a c)д (1)

1=1 где знак {Х}я означает вычисление остатка от деления величины Х на контрольный модуль q. Полученная величина r(A) при кодировании и после него сопровождает исходный код А в качестве его контрольного признака и используется при декодировании для определения факта искажения исходного кода, а при правильном выборе величин Ci u q — и для определения места (номера групп) и величины ошибки (Ла ).

Это следует из того, что неискаженное число для целей контроля может быть представлено в виде и

А Qi Cl ° (2)

l = 1

Если допустить возникновение ошибки величиной Аа в одной из групп (а)), то искаженное число, аналогично (2), будет иметь представление, j+1

A -y. дс +(+ла m,,ci+ а ci.

i=1 I =j+1 (3)

Представление искаженных ошибкой данных J-й группы в выражении Ptja аиде

Я =(О) 4-ЛО))г) й) обусловлено тем, что появление ошибки лю-.

- бой кратности в любой из фиксированных групп не приводит к появлению переносов в смежные группы. При этом в выражениях (3, 4) величина mj - 2, где Sj — разрядность

J-й группы.

Из условия (4) следует, что

10 Ч =(4 -Ч3в 1 и в силу этого величины возможных ошибок заключены в интервале. определяемом в соответствии с неравенством

0 Ьа) S mj — 1.

Применив процедуру (1) к числам, представленным в соответствии с выражениями (2, 3), и вычтя полученные контрольные признаки, получают синдром ошибки

М = { МА)}ч - ИА ) — Ф )}q { jCj}q

20 "" (5)

Если величина Л r оoтTл и ч нHа оOт T нHуYл я, то число А . по сравнению с числом А имеет искажение величиной ha), и, следовательно, процесс обнаружения ошибок эавер25 шен.

Очевидно, что для коррекции ошибки, т,е. установления ее места (J) и величины (haj), необходимо обеспечить однозначное соответствие между любой возможной ве30 личиной искажения he(в любой из имеющихся групп разрядов и синдромом ошибки

hr, полученным в соответствии с (5). С этой целью необходимо правильно выбрать как величины весовых коэффициентов С, так и

35 величину контрольного модуля q, Рассмотрим порядок выбора весовых коэффициентов. Иэ выражения (5) следует, что

hr - Рй Cj)q - {{ МЫСА}я

Отсюда видно, что выбирать весовые коэффициенты следует так, чтобы удовлетворялось условие

Ci

Второе условие выбора также вытекает из (5) и состоит в том, чтобы весовые коэффициенты не являлись делителями конт50 рольного модуля, т,е.

С4 с, (6) или

С е

d а где d — любое из натурального ряда чисел, причем d<2 . В противном случае вычисленный в соответствии с (5) синдром ошибки для искажений Ж), кратных б, тождественно равен нулю, т.е. ошибки данной группы

1777141 вида О, d, 2d, ... по контрольному модулю оказываются неразличными и, следовательно, необнаруженными.

При определении величины контрольного модуля необходимо исходить из следующих посылок.

Во-первых, величина контрольного модуля должна обеспечивать требуемое значеwe вероятности обнаружения ошибок:

Робн 1

%.

Во-вторых, для обеспечения однозначного соответствия между величиной ошибки

Ьа и ее синдромом (5) необходимо, чтобы величина модуля превышала число возможных ошибок и«, обнаружение и исправление которых возможно для данного кода, т,е. необходимо обеспечить ц п, =г g (г" — >), =1 или, при одинаковой разрядности всех групп, т.е. при $ = S (! = 1 и)

q. a 2n(2 — 1).

Множитель 2 в последних выражениях обусловлен тем, что в зависимости от величины ошибки и исходного кода искажаемой группы величина r(A), рассчитанная в соответствии с (1), может быть либо больше, либо меньше величины г(А ), т,е. одной и той же

1 ошибке может соответствовать либо синдром Ь, либо синдром (q- >h

В-третьих, для обеспечения однозначности необходимо соблюдать условие неравенства между собой контрольных признаков при возникновении искажений в любой из групп разрядов. Таким образом, должно выполняться неравенство

{ @CDÜ H(c9CJh для всех I М l. С учетом представления искаженного числа в виде (3) необходимо обеспечить справедливость неравенства ((e + Л а }лу Сф}ч 4 ((а) + b5}qCj}a, что в общем случае приводит к выражению

n n

Л Л ((+ оФЩС - (Я + Я }mjCI}4 4 0 и i фг, где знак4 Х означает вычисление конъюнкс=1 ции величины Хь Последнее выражение для заданных значений ть ml и контрольного модуля q позволяет найти весовые коэффициенты Сi или для заданного набора Ci определить значение q.

При таком выборе величин Ci u q обеСпечивается однозначное соответствие между Ь; с одной стороны, и j, а также Ьа, с другой. Это позволяет, получив, например, таблицы соответствия типа Ь-+(,Ла ), (q—

Ь)-ъ(), Aaj), после обнаружения ошибки обеспечить ее коррекцию, так как из (4) спедует

Qj = (QJ — Л hajj.„.

В описанном виде В Г-код позволяет обнаружить и исправить все однократные ошибки (ошибки в одном разряде} и все те групповые ошибки кратностью Si и менее, которые локализованы в пределах I-й груп10 nbl, Первый регистр 2 предназначен для приема, хранения и сдвигов информации, подаваемой на его входы. Емкость регистра рассчитывается на К разрядов информации, 15 где К - )og2q(, а знак )X(означает вычисление ближайшего большего целого. Парал. лельный информационный вход регистра 2 является К-разрядной шиной и предназначен для параллельного приема информации

20 с выхода второго регистра 5. По последова-, тельному информационному входу этого регистра осуществляется поразрядный прием информации, представленной в последовательном коде. Со старшего разряда выхода

25 регистра 2 выдается информация К-го разряда, которая, в зависимости от состояния вторых счетчика 12 идешифратора 13, через элементы И 7 и элемент ИЛИ 18 выдается на выход 19 устройства. С выхода регистра по

30 S-разрядной шине выдается информация в параллельном коде со всех S младших разрядов кода I-й группы разбиения аЬ.

Блок 3 памяти предназначен для табличного расчета величин (NCj}q по величине

35 кода 1-й группы Q и ее номеру I. При этом адрес каждой ячейки формируется из двух групп разрядов. Первая из них.отображает номер обрабатываемой группы I è передается t-разрядной шине с выхода второго счет чика 12. Здесь t =)logs(n+1)(, n — число групп разбиения. Вторая группа разрядов представляет собой S-разрядный код обрабатываемой группы, передаваемой по

S-разрядной шине с выхода первого регистра 2. При этом общая разрядность адреса блока 3 памядравна ($+ t), а емкость блока

3 памяти 2 . В каждой ячейке блока 3 памяти с адресом (l, e) хранится вычислен, ное заранее значение по модулю q от про-. изведения кода адреса а на соответствующий весовой коэффициент Сь т,е. величина (ai С }, имеющая разрядность

К.

Сумматор 4 предназначен для сложения по модулю q К-разрядных чисел, поступающих на его входы с выхода второго регистра 5 и блока 3 памяти.

Второй счетчик 12 предназначен для подсчета числа обрабатываемых групп раз1777141 биения. Таких групп в исходном разбиении и. Кроме того, одна, (и+1)-я, группа формируется в устройстве в качестве его контрольного признака. Таким образом, модуль счета второго счетчика 12 равен (n+1), Для этого в устройстве реализована принудительная установка в нулевое состояние данного счетчика сигналом, подаваемым на установочный вход, с выхода элемента ИЛИ

10 в случае, если на выходе второго дешифратора 13 выработан разрешающий сигнал при переходе второго счетчика 12 в (п+1 -е состояние. а на втором выходе первого дешифратора 16 — разрешающий сигнал при переходе первого счетчика 15 в К-е состояние, Формирователь 22 импульсов предназначен для формирования одиночного импульса; длительность которого меньше периода следования синхросигналов, и обеспечивает запись информации по параллельному информационному входу первого регистра 2. Этот импульс формируется при появлении на выходе второго дешифратора

13 разрешающего сигнала.

Первый счетчик 15 предназначен для подсчета числа разрядов в каждой из (и+1) групп, Поскольку первые и групп имеют разрядность 3, а последняя (и+1)-я — К, то в устройстве реализовано изменение модуля счета путем принудительной установки данного счетчика в нулевое состояние. С этой целью при модуле счета S, сигнал установки

sнулевое состояние,,подаваемый на установочный вход через элемент ИЛИ 11, формируется на выходе элемента И 8 при обработке (и+1)-й группы а приеме S-ro информационного разряда. При модуле счета

К сигнал установки в нулевое состояние формируется на выходе четвертого элемента И 9 при обработке (и+1)-й группы и приеме -ro информационного разряда путем

Обьема сигналОВ с (и+1)-ro выхода второго дешифратора 13 и второго, К-го, выхода первого дешифратора 16.

Второй дешифратор 13 Обеспечивает формирование выходного сигнала на (и+1)м выходе, а первый дешифратор 16 — на первом, Зм,и втором, К-м, Выходах.

Второй регистр 5 предназначен для приема и хранения К-разрядных чисел. При этом второй регистр 5 совместно с сумматором 4 образуют модульный накапливающий сумматор, обеспечивающий накопление информации. поступающей на входы сумматора 4, т,е, формирование величины контрольного признака после сложения и слагаемых: п(А)- f g а Сф .

1=1

Элемент задержки 17 предназначен для формирования на его выходе сигнала, задержанного относительно входного сигнала на время, равное сумме времен выборки иэ блока 3 памяти и сложения в сумматоре 4.

Этим достигается временное согласование

10 функционирования элементов устройства, Устройство работает следующим обраЗом.

В исходном состоянии счетчики 12, 15 и второй регистр 5 сигналом начальной уста15 ковки по входу 20 устройства или с выхода элемента И 9 через элемент ИЛИ 10 установлены в нулевое состояние. При этом на (и+1)-м выходе дешифратора 13, íà S-и и К-м . выходах дешифратора 16 отсутствуют раз20 решающие. сигналы, в силу чего элементы И

-7 — 9 закрыты, а элемент И 6 сигналом с вы-. хода элемента HE 14 открыт.

На входы 1 и 21 устройства поступают в исследовательном коде информационные символы и синхронизированные с ними так-. тирующие импульсы. Каждым тактирующим импульсом, поступающим на вход первого счетчика 15, изменяется его состояние на единицу. Этим же тактирующим импульсом

30 осуществляется сдвиг содержимого регистра 2 на один разряд и запись в его.младший . разряд очередного информационного символа. Так как элемент И 6 открыт, то информационные сймволы с информационного

35 входа 1 устройства через элементы И 6 и

ИЛИ 18 поступают на выход 19 устройства.

После приема 3-ro тактирующего сигнала на первом, $-м. выходе первого дешифратора появляется сигнал. которым

40 разрешается чтение информации из блока 3 памяти и через элемент И 8 и элемент ИЛИ . 11 установка первого счетчика 15 В нулевое состояние. Поскольку эа это время на первом регистре 2 накоплено 3 информационных символов (-й группы а1 и код номера этой группы свыхода второг,о счетчика 12 совместно с кодом а1 поступают на адресные входы блока 3 памяти, то на его выходе формируется код (а С1)ц, который поступает

50 на сумматор 4, где складывается с содержимым второго регистра 5, К этому моменту на вход записи второго регистра 5 с выхода элемента задержки 17 поступает сигнал, задерж Вн н ы и относительно считывающего

55 сигнала блока 3 памяти на время выборки информации иэ этого блока и время сложения в сумматоре 4. Этим сигналом разрешается запись очередной суммы Во второй регистр 5 и переход второго счетчика 12 в очередное состояние, соответствующее об1777141

10 работке очередной группы разрядов исходного числа.

За nS тактирующих сигналов на выход

19 устройства будут выданы в последовательном коде все информационные разряды обрабатываемого числа, принято первым регистром 2 в последовательном коде и выдано в параллельном коде п групп по S разрядов в каждой, сосчитано из блока 3 памяти и просуммировэно в сумматоре 4 п групп кодов (NCi)q, в результате чего во втором регистре 5 будет получен код контрольного признака и п(А) = (, а С@ .

1=1

При записи во второй регистр 5 последнего результата суммирования и переходе второго счетчика 12 в очередное. (п+1)-е, состояние на выходе второго дешифратора

13 появится сигнал, которым открываются элементы И 7, 9, запускается формирователь 22 импульсов, сигналом которого будет разрешена запись в первый регистр 2; кроме того, этим же сигналом с выхода второго дешифратора 13 после инверсии в элементе

НЕ 14 закрываются элементы И 6, 8. В результате этого в первый регистр 2 будет записан К-разрядный код контрольного признака с выхода второго регистра 5 и изменен модуль счета второго счетчика 15 с $ на К. С приходом последующих К тактирующих сигналов с выхода регистра 2 через открытый элемент И 7 и элемент ИЛИ 18 на выход 19 устройства будут выданы К символов контрольного признака, после чего на первом счетчике 15 будет установлен код, соответствующий числу К. В результате этого на втором выходе первого дешифрэтора

16 появится сигнал, который через открытый элемент И 9 и элемент ИЛИ 10 устано-. вит в нулевое состояние второй счетчик 12 и второй регистр 5, а также через элементы

ИЛИ 10, 11 — первый счетчик 15, После этого устройство готово к приему очередного слова.

Таким образом, за время, соответствующее (nS+K) периодам следования тактирующих импульсов, на вход устройства будут приняты nS разрядов исходного числа. а на выход устройства будут выданы nS информационных и К контрольных разрядов ВГкода исходного числа.

Формула изобретения

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

5 соединен с первым входом второго элемента И, выходы первого и второго элементов И соединены соответственно с первым и вторым входами первого элемента ИЛИ, выход которого является выходом устройства, вы10 ход первого регистра соединен с соответствующими разрядами адресного входа блока памяти, тактовый вход первого регистра и счетный вход первого счетчика подключены к тактовому входу устройства, информаци15 онный выход первого счетчика соединен с информационным входом первого дешифратора, первый и второй выходы которого соединены с первыми входами третьего и четвертого элементов И соответственно, вы20 ход третьего элемента И через элемент задержки соединен с входом записи второго регистра, выход которого соединен с входом первого операнда сумматора. выход результата которого соединен с

25 информационным входом второго регистра, информационный выход второго счетчика соединен с информационным входом второго дешифратора, выход которого соединен с вторым входом второго элемента И и вхо30 дом элемента НЕ, выход которого соединен с вторым входом первого элемента И, выход второго элемента ИЛИ соединен с установочным входом первого счетчика, о т л и ч аю щ е е с я тем, что, с целью сокращения

35 эппаратурных затрат устройства, оно содержит формирователь импульсов, причем выход второго регистра соединен с параллельным информационным входом первого регистра, информационный выход

40 блока памяти — с входом второго операнда сумматора, выход второго дешифратора через формирователь импульсов соединен с входом записи первого регистра и непосредственно с вторым входом четвертого

45 элемента И, выход которого соединен с первым входом третьего элемента ИЛИ, второй вход которого подключен к установочному входу устройства, выход третьего элемента

ИЛИ соединен с установочными входами

50 первого регистра и второго счетчика и с первым входом второго элемента ИЛИ, второй вход которого соединен с выходом третьего элемента И, второй вход которого соединен с выходом элемента НЕ, информационный

55 выход второго счетчика соединен с соответствующими разрядами адресного входа блока памяти, вход чтения которого соединен с первым выходом первого дешифратора, выход элемента задержки соединен со счетным входом второго счетчика.