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

 

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

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

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

РЕСПУБЛИН (19) (11) (59 4 G 06 F 11 08

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ/.,".

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ Щд... б !

6pi

26 (21) 4045084/24-24 (22) 03.03.86 (46) 23.0?.87. Бюл. У 27 . (75) Л.М. Паронян (53) 631. 3 (088. 8) (56) Авторское свидетельство СССР

У 1101826, кл. С 06 Р 11/08, 1983.

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

У 1198524, кл. G 06 F 11/08, 1984. (54) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ КОНТРОЛЬНОГО ЭЛЕМЕНТА И ОБНАРУЖЕНИЯ ОШИБОК (57) Изобретение относится к вычислительной технике и может быть исполь зовано в системах передачи и обработки данных. Цель изобретения — расширение функциональных воэможностей

1325483 где N* ? 1. ,н, устройства за счет обнаружения ошибок в информационном блоке. Устройство для вычисления контрольного элемента содержит группу 1 элементов ИЛИ, сум-. матор 2, регистры 3,4, группы 5,6,7 элементов И, одновибратор 8, элемент

НЕ 9, счетчик 10, узел 11 синхронизации, элементы задержки 12-17, триггер 18, элементы И 19-22, элементы

ИЛИ 23-25, информационные входы 26, тактовый вход 27, вход 28 режима кодирования устройства, вход 29 режима декодирования устройства. Устройство

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

Цель изобретения — расширение 5 функциональных воэможностей устройства за счет возможности обнаружения ошибок в информационном блоке.

На чертеже изображена схема устройства для вычиСления контрольного элемента и обнаружения ошибок.

Устройство содержит группу элементов ИЛИ 1, сумматор 2, регистры 3 н

4, группы элементов И 5 — 7, одновибратор 8, элемент НЕ 9, счетчик 10 ° 15 узел 11 синхронизации, включающий элементы 12-17 задержки, триггер 18, элементы И 19-22, элементы ИЛИ 23-25, информационные входы 26 устройства. тактовый вход 27, вход 28 режима 20 кодирования устройства, вход 29 режима декодирования устройства.

Устройство работает следующим образом.

Вычисление контрольного элемента базируется на теории кодирования биноидных кодов. Контрольный элемент для информационного блока длины К информационных элементов К;(длина информационного элемента и разрядов) 3О вычисляется по правилу

Ь„=((0-1)а, +(N-2)а +...+

+2ак-< + axloo4 " 35 позволяет обнаруживать одиночные ошибки (произвольные ошибки в пределах информационного элемента длины и ), часть ошибок большей кратности и ошибки, возникающие в результате перестановки информационных элементов. Расширение функциональных возможностей устройства достигается вве. дением четырех элементов И, трех элементов ИЛИ, триггера, одновибратора .и элемента НЕ и позволяет в совокупности организовать режимы кодирования и декодирования информации. 1 ил.

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

На втором регистре при этом последовательно формируются числа

Ъ„ = а (ии4 N)

Ь" = (a,+ аг) oJ N, Ь, = ((а,+ аг) + аз J мтос1»

° ° ° ° в ° ° °

Ьк (a + aà+ +a ) cop N.

На первом регистре формируются чисЬ =b„=a, п о N, Ь =(Ь, + Ьг )=(2а,+ аг) od»

Ь = (Ьг+ Ъ3 )=(За + 2а +а ) и,о1»

31

° В ° ° ° ° ° °

Ь„=((N-1)a,+ (N-2)a,+...+a„j 03N.

В режиме декодирования таким же образом вычисляется контрольный элемент

Ь„, который далее сравнивается с поступившим элементом Ь, т.е. определяется определитель S (Ь„+Ь„) о 2 °

Если S=0, то принимается решение об отсутствии ошибок в информационном блоке длины К, Если Б О, то принимается решение о наличии ошибок в ин, формационном блоке длины К. Для обеспечения высокой обнаруживающей способ1325483 ности желательно, чтобы N = (2 ;.1) было простым числом. и, -Разрядный регистр 3 предназначен для хранения предыдущих сумм информационных элементов в режиме кодирования и декодирования и выполняет вспомогательную роль, ив разрядный регистр 4 — для хранения предыдущих сумм произведения информационных элементов на соответствующие 1О последовательные целочисленные коэффициенты, для выдачи контрольного эле мента Ь в канал через группу 7 элементов И после завершения кодирования, для хранения и выдачи результата срав-15 нения контрольных сумм (определителя

S) в режиме декодирования в элемент

ИЛИ 23 с целью анализа определителя

S и принятия решения о достоверности информационного блока длины К. 20

Сумматор 2 состоит из одноразрядных сумматоров на три входа в количестве п, которые по переносу в старший разряд через элемент И на два входа соединены последовательно, 25 а перенос одноразрядного сумматора . позиции п через элемент И на два входа соединен с входом первой позиции одноразрядного сумматора, образуя сумматор на 2п, входа по cop(2 -1) 10 при нулевом состоянии первого выхода счетчика 10, соединенного с элементом НЕ 9.

Если первый выход счетчика 10 находится в состоянии 1", то на вторые входы элементов И сумматора 2 с выхода элемента НЕ 9 поступает блокирующий переносы одноразрядных сумматоров сигнал, тем самым превращая сумматор 2 в одноразрядные сумматоры на 40 два входа rro ynoct2 в количестве и,.

Сумматор 2 предназначен для суммирования предыдущей суммы информационных элементов, хранившихся в регистре 3, с очередным информационным эле- 4> ментом а; по oJ(2 — 1) с последукщим суммированием результата этой суммы, переведенной в регистр 3, с предыдущей суммой произведения информационных элементов на последовательные целочисленные коэффициенты, хранившихся в регистре 4 по о4 (2" -1), а также для поразрядного суммирования (сравнения) вычисленного конт1 рольыого элемента Ь q с поступившим контрольным элементом b по од 2.

Узел 11 синхронизации на линиях

12-17 задержки предназначен для формирования из тактового сигнала, пос-, тупающего с входа 27 устройства, разрешающих сигналов для элементов И 5 н 6 первой и второй групп, сигнала счета для счетчика 10 и управляющих сигналов записи для регистров 3 и 4.

По сигналу счета счетчик !О считает количество поступивших информационных элементов. Причем счетчик 10 имеет два выхода. Первый выход соответствует счету К, который в режиме кодирования используется узлом 11 в качестве завершающего сигнала после выдачи контрольного элемента, приводящего устройство в исходное состояние. Второй выход счетчика 10 используется только в режиме декодирования.

При счете К + 1 по сигналу второго выхода счетчика 10 осуществляется анализ определителя S и формирование узлом 11 завершающего сигнала, приводящего устройство в исходное состояние в режиме декодирования.

Триггер 18 режима задает режим работы предлагаемого устройства и имеет два выхода (нулевой и единичный) и два входа, соединенные соответственно с входами 28 и 29 устройства.

При поступлении сигнала на вход 28 триггер устанавливается в нулевое состояние, т.е. устройство переходит в режим кодирования, а при поступлении сигнала на вход 29 триггер устанавливается в единичное состояние, т.е. устройство переходит в режим обнарушения ошибок (декодирования).

В режиме обнаружения ошибок на первые входы элементов И 19 и 21 поступает разрешающий потенциал, а на первый вход элемента И 20 — блокирующий сигнал. В режиме кодирования, наоборот, входы элементов И 19 и 21 блокированы триггером 18, а на первый вход элемента 20 поступает разрешающий сигнал. Одновибратор 8 в режиме кодирования не действует, он действует только в режиме декодирования и формирует одиночный сигнал только по сигналу первого выхода счетчика 10 соответствующего счету К.

Один такт кодирования одного информационного элемента а; делится на два полутакта. 3а первый полутакт кодирования осуществляется суммирование поступившего информационного элемента с предыдущей суммой информационных элементов по twomo (2 " -1) и 1325483 запись результата в регистр 3. 3а второй полутакт осуществляется суммирование результатов сумм регистров 3 и 4 по rwJ(2 — 1) и запись результата этой суммы в регистр 4. 5

Независимо от режима перед началом работы устройство устанавливается в исходное состояние — счетчик 10 и регистры 3 и 4 находятся в нулевом состоянии»

Допустим, устройство находится в режиме кодирования, т.е. триггер 18 режима находится в нулевом состоянии.

В этом режиме первые входы элементов

И 19 и 21 блокированы, а первый вход элемента 20 разблокирован. Информационные элементы поступают поочередно на, информационные входы 26.устройства. По поступлении сигнала на тактовый вход 27 устройства сигналы с выходов элементов задержки узла 11 сийхронизации разрешают прохождение информации через элементы И 5 первой группы и элементы ИЛИ 1 на входы первого слагаемого сумматора 2 и записывают результат сложения (по сигналу выхода ликии 13 задержки) информации с содержимым первого регистра 3 в регистр 3.

Затем по сигналам узла 11 синхро. низации (по сигналам выходов линий

14 и 15 задержки) на входы первого слагаемого сумматора 2 поступает через элементы И 6 второй группы содержимое второго регистра 4 и сумма по и, t

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

По окончании суммирования всех элементов информационного блока длины К во втором регистре 4 образуется контрольный элемент Ь и сигнал с перИ вого выхода счетчика 10, соответствующий счету К, проходя через элемент

И 20, пропускает конгрольный элемент через элементы И 7 третьей группы на информационные выходы устройства.

Этот же сигнал переполнения, проходя через элемент ИЛИ 24 и элемент 17 задержки, устанавливает в нулевое состояние счетчик 10, регистр 4 и, проходя через элемент ИЛИ 25, регистр 3.

Устройство готово к вычислению нового контрольного элемента или, если режим изменился,к работе в режиме декодирования.

Допустим, на вход 29 устройства поступает сигнал, который устанавливает триггер 18 в единичное состояние. Рассмотрим работу устройства в режиме декодирования. В этом режиме входы элементов И 19 и 21 разблокированы, а вход элемента И 20 блокирован. Работа устройства начинается с исходного состояния и продолжается так до суммирования последнего К вЂ” го элемента.

По окончании суммирования всех К элементов информационного блока на втором регистре 4 образуется сумма

b и сигнал с первого выхода счетK чика 10, соответствующий счету К, проходя через элемент И 19, создает на выходе одновибратора одиночный импульс, который, проходя через элемент ИЛИ 25, устанавливает в нулевое состояние регистр 3. Этот же сигнал с первого выхода счетчика 10, проходя через элемент НЕ 9, блокирует прохождение переноса с младших разрядов в старшие в сумматоре 2, тем самым преобразуя сумматор 2 по що8 (2 — 1) в одноразрядные сумматоры на два входа по шой 2. Устройство в таком состоянии остается до прихода последнего (К+1)-го элемента, т.е. контрольного элемента Ь„ .

По поступлению элемента Ь„ на вход 26 устройства и сигнала на тактовый вход 27 устройства сигналы с выходов элементов задержки узла 11 синхронизации разрешают прохождение элемента Ь через элементы И 5 перK вой группы и элементы ИЛИ 1 на входы первого слагаемого сумматора 2 и записывают результат сложения Ь„ с нулевым содержимым регистра 3 в регистр 3. Затем по сигналам узла 11 синхронизации во втором полутакте на входы первого слагаемого сумматора 2 через элементы И б второй группы поступает содержимое второго регистра

4 и сумма по ntod 2 содержимого первого и второго регистров 3 и 4 записывается во второй регистр 4. После этого к содержимому счетчика 10 добавляется единица и на втором выходе счетчика 10 появляется сигнал, соответствующий счету (К+1).

По окончании приема и суммирования всех (К+1) элементов кодового вектора во втором регистре 4 формируется определитель S, т.е. (Ь + !

+ Ь ) и од 2, и сигнал с второго вы1325483 хода счетчика 10, соответствующий счету (К+1), проходя через элемент

И 2 1, пропускает результат анализа определителя S с выхода анализируемого элемента ИЛИ 23 через элемент И

22 на выход ошибки устройства. Этот же сигнал, проходя через элемент ИЛИ

24 и линию 17 задержки, устанавливает в нулевое состояние счетчик 10, регистр 4 и, проходя через элемент

ИЛИ 25, регистр 3.

Устройство готово к декодированию очередного кодового вектора или, при изменении режима, к кодированию.

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

10

ЭО

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

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

45,с выходом первого элемента И, выход ,элемента НЕ соединен с входом блокировки распространения переносов сум50 матора вход переноса которого соеУ динен с выходом переноса сумматора, выход второго элемента ИЛИ соединен с входом установки в начальное состо" якие второго регистра, разрядные вы55 ходы первого регистра соединены с соответствующими входами третьего элемента ИЛИ, выход которого соединен с вторьич входом четвертого элемента И.

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

НЕ и одновибратор, причем вход задания режима кодирования устройства соединен с входом установки в "0" триггера, прямой выход которого соединен с первыми входами первого и второго элементов И, второй вход первого элемента И соединен с входом элемента

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