Устройство для вычисления контрольного кода

 

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОНТРОЛЬНОГО КОДА, содержащее регистр и сумматор, причем выходы сумматора соединены с информационными входами регистра, отличающееся тем, что, с целью его упрощения, устройство содержит группу сумматоров по модулю два, счетчик количества информационных подблоков, счетчик количества элементов и группу элементов И, причем информационные входы устройства соединены с первыми информационными входами соответствующих сумматоров группы по модулю два, выходы которых соединены с соответствующими входами сумматора, тактовый вход устройства соединен со счетным входом счетчика количества элементов , выход переполнения которого соединен со счетным входом счетчика количества информационных подблоков, выход каждого разряда которого соединен с вторым входом соответствующего сумматора группы по модулю два, каждый i-й разряд регистра (где i .1...П, а п - количество разрядов в элементе информации) соединен с вторым входом (i+1)-ro разряда суммаI тора, выход переноса сумматора соединен с входом переноса сумматора, ел информационные выходы регистра соединены с первыми входами соответствующих элементов И группы выход переполнения счетчика количества информационных подблоков соединен с вторыми входами элементов И группы, выходы которых являются выходом контрольного кодустройства.

09) (11) СОЮЗ СОВЕТСКИХ

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

РЕСГ1УВЛИК

3(. Ю G 06 F 11/08

ОПИСАНИЕ ИЗОБРЕТЕНИЯ!

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР по делАм изОБРетений и ОтнРытий (21) 3463848/18-24 (22) 05.07.82 (46) 07.07.84. Бюл . N - 25 (72) Л.М. Паронян (53) 681.3(088.8) (56) 1. Контроль функционирования больших систем. Под ред. Г.П. Шибанова. M., "Иашиностроение", 1977, с. 115-131.

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

Р 503243, кл. G 06 F 11/08,1974 (прототип}. (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

КОНТРОЛЬНОГО КОДА, содержащее регистр и сумматор, причем выходы сумматора соединены с информационными входами регистра, о т л и ч а ю щ е е с я тем, что, с целью его упрощения, устройство содержит группу сумматоров по модулю два, счетчик количества информационных подблоков, счетчик количества элементов и группу элементов И, причем информационные входы устройства соединены с первыми информационными входами соответствующих сумматоров группы по модулю два, выходы которых соединены с соответствующими входами сумматора, тактовый вход устройства соединен со счетным входом счетчика количества элементов, выход переполнения которого соединен со счетным входом счетчика количества информационных подблоков, выход каждого разряда которого соединен с вторым входом соответствующего сумматора группы по модулю два, каждый i-й разряд регистра (где i

1...n, а п — количество разрядов в элементе информации) соединен с вторым входом (i+1)-го разряда сумматора, выход переноса сумматора соединен с входом переноса сумматора, информационные выходы регистра соединены с первыми входами соответствующих элементов И группы выход переполнения счетчика количества информационных подблоков соединен с вторыми входами элементов И группы, выходы которых являются выходом контрольного код устройства.

1101826

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

Известны устройства для вычисления контрольного знака, в частности устройства, служащие для вычисления контрольной суммы по модулю 2,2; (2 -1) и (2 а +1) ь где по — длина информационного элемента в двоичном 10 коде (для байта и = 8 бит). Вычисление контрольной суммы по mod 2 позволяет определять искажение одного бита в кодом слове, а вычисление контрольной суммы по модулям 2 а, (2 — 1) 15

"о Па и (2"0+1) позволяет определять произ— вольные ошибки в пределах одного информационного элемента длины пр (1).

Устройства характеризуются простотой реализации, однако они не позволяют определять ошибки„ возникающие из-за перестановки элементов сообщения, так как при перестановке слагаемых (информационных элементов) сумма по модулю не меняется. .15

Наиболее близким по технической сущности к изобретению является устройство для вычисления контрольного кода, содержащее блок хранения весовых коэффициентов, блок поправок, в который входят регистр накопления суммы и сумматор, блок определения дополнения до модуля, блок управления и вывода, тактовый генератор (2).

Недостатком известного устройства

35 является то, что для вычисления контрольного знака требуется производить большое количество арифметических действий, а это не позволяет кодировать один информационный элемент за один-два такта. Кроме того, длина информационного слова ограничена, так как 1 с К с И вЂ” 1, где К вЂ” длина информационного слова, М вЂ” модуль. !

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

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

И, причем информационные входы устройства соединены с первыми информационными входами соответствующих сумматоров группы по модулю два, выходы которых соединены с соответствующими входами сумматора, тактовый вход устройства соединен со счетным входом счетчика количества элементов, выход переполнения которого соединен со счетным входом счетчика количества информационных подблоков, выход каждого разряда которого соединен с вторым входом соответствующего сумматора группы по модулю два, каждый 1-й разряд регистра (где i = 1...n, а п количество разрядов в элементе информации) соединен с вторым входом (i+1)-ro разряда сумматора, выход переноса сумматора соединен с входом переноса сумматора, информационные выходы регистра соединены с первыми входами соответствующих элементов И группы, выходы переполнения счетчика количества информационных подблоков соединен с вторыми входами элементов И группы, выходы .которых являются выходом контрольного кода устройства.

В устройстве используется следующий алгоритм вычисления контрольного кода.

Пусть для защиты информационного слова ot = (а „а,,...ак)необходимо вычислить контрольный знак Ь, где

rr0

2, a; = a 1. a 2 . a;„o

1,K a E 5 Е(?) и ъ = Тйо.

Если 1 с К и, то Ь„: — (2 а, +

+ 2 о а + ...+ 2 a„) mod(2 0 1)

Эту сумму за К тактов суммирования можно получить следующим образом такт II такт III такт и т .д

Ь, = а, b, =2@, а2 Ь,=2(2a, ñ ) a>

Ь,=2(...2(2(2g„«1+о Й ао " ак- ) q

Нетрудно показать, что

2j„2(2(2о,+а, а ) а „. a „,) а = аа

У 1 г

Если по п с 1 . с 2 rrо го

Ь ЛЪ 112"О 1.2 "rlo 2 0 — 1л °" no

2 al > )mall, ° <), 1 0 где а означает, что информационИа+Г ные элементы второго подблока суммируются с инверсией всех разрядов, т.е. на вход сумматоров они поступают предварительно с инверсией всех разрядов.

1101826 з

Если 2п cК Зп, то

4 (g 1о -1 2З.- nî Qoо- 2 з и а2 с

no+ < 2Aot 2

° 2 a "" ) „„о J(g " ..<1 о О 7

-2З, э "о где а означает, что на вход сумматора информационные элементы третьего подблока поступают с инверсией всех разрядов кроме первого и т.д. при (2 -1)n с К c n 2

b 2„=- 5b q + bã,+ ° . ° +(2 а(г" Ф о+ +

2 о21 0-1

Q(Yl() ) z $. .1 2 с дюкло)моо ф -$) где а у,,1„ „ означает, что информа-1 пo ã о ционные элементы 2 подблока суммируются с инверсией первых разрядов.

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

На чертеже приведена схема предлагаемого устройства.

Устройство содержит регистр 1, сумматор 2, группу сумматоров 3 по Зо модулю 2, счетчик 4 количества информационных подблоков, счетчик 5 количества элементов, группу элементов И 6 для блокировки выходов регистра и выдачи контрольного знака, информационный вход 7 устройства, тактовый вход 8 устройства. по-разрядный регистр 1 предназначен для хранения предыдущих сумм произведения информационных элемен- 40 е тов на степенные коэффициенты 2 (где f = О, по -1) в процессе кодирования, а также выдачи контролируемого кода Ь через группу элемен-! тов 6 после завершения кодирования.

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

2по входа по mod (2 о -1).

Сумматор предназначен для суммиро-55 вания предыдущей суммы произведения информационных элементов на степенные коэффициенты 2, хранившихся в регистре 1, с очередным информационным элементом а; по mod (2 -1) .

С входов, устройства.п -разрядо ные информационные элементы параллельно поступают на входы сумматора 3 помодулю два, а с входа 8 приема тактовых сигналов устройства тактовая частота поступает на вход счетчика 5.

Выходы счетчика 4 соединены с соответствующими входами сумматора 3 для осуществления процедуры инвертирования

1 разрядов информационных элементов в момент прохождения через сумматор

3 по рассмотренному алгоритму.

Для осуществления операции умнопо жения на 2 no mod (2 -1) выходы регистра 1 соединены с входами блока 2 со сдвигом влево на одну позицию, а старший п -разряд регистра 1 соединен с входом одноразрядного сумматора первого разряда блока 2. Такое соединение позволяет преобразовать результат умножения на 2 больше чем (2 î-1) по mod (2 о-1) Перед началом работы устройство устанавливается в исходное положение. В таком положении счетчики 4 и 5 и регистр 1 обнулены, а входь| элементов И группы 6 блокированы сиг— налом, поступающим со счетчика 4.

Пусть первый информационный элемент а1 и соответствующий тактовый сигнал поступает соответственно на входы 7 и 8 устройства. Так как счетчик 4 обнулен, то все разряды элемента а,, без изменения пройдя через сумматоры 3 и 2, записываются в регистр 1, а в счетчике 5 счет устанавливается на 1. Второй информационный элемент а без изменения разря2 дов, пройдя через блок 3, поступает на входы сумматора 2 и суммируются со сдвинутым на один разряд влево значением регистра 1, т.е. с 2а .

Результат суммы (2a> + а ), преобразованный по mod (2 о-1)(если 2а + по

+ а, ) 2 о — 1), записывается в регистре 1.После ввода второго элемента в счетчике 5 счет устанавливается на 2. Таким образом, суммируются и все остальные элементы первого подблока и после суммирования последнего а„ элемента в регистре 1 формируется результат

b =-:(2 ;.а„+ 2,а +...+

+ 2 а „) mod (2 -1) °

1101826

После ввода элемента а в счетно чике 4 счет устанавливается на п0 (2 -1) (все и разряды единицы), и со всех разрядов счетчика 4 сигналы поступают на входы сумматора 3 и оста- ются до завершения кодирования всех и элементов второго подблока. Первый

Э элемент а второго подблока, постуПОФ1 пив на вход сумматора блока 3, проходит через него с инверсией всех 10 разрядов и в сумматоре 2 суммируется со сдвинутым на один разряд значе-4 нием регистра 1, т.е. с 2 (2 о а, +

+ 2 а + ...+ 2 а„, ) тпой(2 -11.

Результат суммы 2 (2 ь а„+ 2 а + 15

+ 2 а ) + а" "" записывается в региПь стре 1. Таким же образом, с инверсией всех разрядов, кодируются все остальные элементы второго подблока. В результате после кодирования а „

1о элемента (последний элемент второго подблока) в регистре 1 формируется значение пь --1 а в счетчике 4 счет устанавливается на (2 ь -2), т.е. на единицу уменьшает"ь ся. Так как первый разряд счетчика 4 30 равен нулю, то все элементы третьего подблока поступают на вход блока

2 без инверсии первых разрядов. После кодирования всех элементов третьего подблока в счетчике 4 счет устанавливается на (2 -3) . В этом случае

"ь все элементы четвертого подблока через сумматор 3 поступает на входы сумматоров блока 2 без инверсии вторых разрядов.

Таким же образом кодируются и элементы остальных подблоков. После кодирования последнего а„ 2 элемента о

"о "о подблока 2 ь устройство переходит в режим выдачи контрольного кода. На выходе переполнения счетчика 4 появляется сигнал, который разблокировывает входы клапанов 6, и контрольный знак через блок 6 поступает в канал вслед за информационными элементами.

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

Устройство позволяет автоматически генерировать весовые коэффициенты и реализовать процесс кодирования одного информационного элемента за один такт. !

Предла гаема е устройств о зн ачительно проще известного, так как в нем отсутствуют такие узлы, как блок хранения весовых коэффициентов, блок определения поправки и блок определения дополнения до модуля, и найдет применение в вычислительной технике для защиты хранимой и обрабатываемой информации (защита управляемых программ, пакетов программ, массивов и т.д.), в системах передачи данных (мультиплексоры, устройства защиты от ошибок, групповые устройства повышения достоверности и т.д.) и в автоматизированных системах управления.

1101826

Составитель И. Сигалав

Техред А. Бабинец Корректор В. Бутяга

Редактор В. Данко

Филиал ППП "Патент"; r. Ужгород, ул. Проектная, 4

Заказ 4769/33 Тираж 699 Подписное

BHHHIIH Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5