Устройство для вычисления контрольного элемента и обнаружения ошибок Советский патент 1987 года по МПК G06F11/08 

устройства за счет обнаружения ошибок в информационном блоке. Устройство для вычисления контрольного элемента содержит группу 1 элементов ИЛИ, сумматор 2, регистры 3,4, группы 5,6,7 элементов И, одновибратор 8, элемент .НЕ 9, счетчик 10, узел 11 синхрониза- ции, элементы задержки 12-17, триггер 18, элементы И 19-22, элементы ИЛИ 23-25, информационные входы 26, тактовый вход 27, вход 28 режима кодирования устройства, вход 29 режима Декодирования устройства. Устройство

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

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

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

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

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

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

Ь, (N-Da, «(N-2)...

+2ац. + N, где N г - 1.

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

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

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

Ь,, а (ttioj N),

b (aj -ь а ) f«cicl N,

bj, (a, + a) + mod N,

b, - (a + a,+.. .+a,) ni)(J N.

JfiЯ

Ha первом регистре формируются числа

bj b,, a, mod N,

bj (b, + b2,) (2a,+ a)-tioclN,

bj (b2+ b-j,)(3a + N,

Ьц i(:N-1) (N-2)...+a h,.

В режиме декодирования таким же образом вычисляется контрольный элемент b , которьй далее сравнивается с поступившим элементом Ьк , т.е. определяется определитель S( b +b )mod2.

Если , то принимается решение об отсутствии ошибок в информационном блоке, длины К. Если , то принимается решение о наличии ошибок в информационном блоке длины К. Для обеспечения высокой обнаруживающей способ

ностн желательно, чтобы N (2 ri-l) было простым числом. По-Разрядный регистр 3 предназначен для хранения пре- дьщущих сумм информационных элементов в режиме кодирования и декодирования и вьшолняет вспомогательную роль, п,- разрядный регистр 4 - для хранения предыдущих сумм произведения информационных элементов на соответствующие последовательные целочисленные коэффициенты, для выдачи контрольного элемента Ь в канал через группу 7 элементов И после завершения кодирования, для хранения и выдачи результата сравнения контрольных сумм (определителя S) в режиме декодирования в элемент ИЛИ 23 с целью анализа определителя S и принятия решения о достоверности информационного блока длины К.

Сумматор 2 состоит из одноразрядных сумматоров на три входа в коли

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

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

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

ре 3, с очгередным информационным эле- 45 элемента 20 поступает разрешающий ментом а- по mod (2 -De последующим суммированием результата этой суммы, переведенной в регистр 3, с предыдущей суммой произведения информационных элементов на последовательные целочисленные коэффициенты, хранившихся в регистре 4 по lool (), а также для поразрядного суммирова50

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

Один Такт кодирования одного ин формационного элемента а , делится н g два полутакта. За первый полутакт дирования осуществляется суммирова ние поступившего информационного э мента с предьдущей суммой информац онных элементов по moj (2 -1)

ния (сравнения) вычисленного контрольного элемента bк с поступившим контрольным элементом Ь по mod 2.

Узел 11 синхронизации на линиях 12-17 задержки предназначен для фор

мирования из тактового сигнала, пос-, тупающего с входа 27 устройства, разрешающих сигналов для элементов И 5 и 6 первой и второй групп, сигнала счета для счетчика 10 и управляюпшх сигналов записи для регистров 3 и 4, По сигналу счета счетчик 10 считает количество поступивших информационных элементов. Причем счетчик 10 имеет два выхода. Первый выход соответствует счету К, которьй в режиме кодирования используется узлом 11 в качестве завершающего сигнала после выдачи контрольного элемента, приводящего устройство в исходное состояние. Второй выход счетчика 10 используется только в режиме декодирования. При счете К + 1 по сигналу второго выхода счетчика 10 осуществляется анализ определителя S и формирование узлом 11 завершающего сигнала, приводящего устройство в исходное состояние в режиме декодирования.

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

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

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

элемента 20 поступает разрешающий

45 элемента 20 поступает разрешающий

50

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

45 элемента 20 поступает разрешающий

Один Такт кодирования одного информационного элемента а , делится на g два полутакта. За первый полутакт кодирования осуществляется суммирование поступившего информационного элемента с предьдущей суммой информационных элементов по moj (2 -1) и

запись результата в регистр 3. За второй полутакт осуществляется суммирование результатов сумм регистров 3 и 4 по mod() и запись результата этой суммы в регистр 4.

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

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

13254836

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

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

Ш

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

И 19 и 21 блокированы, а первый вход Ь.. и сигнал с первого выхода счет- элемента 20 разблокирован. Информаци- чика 10, соответствующий счету К, онные элементы поступают поочередно на, информационные входы 26.устройства. По поступлении сигнала на такто20

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

Затем по сигналам узла 11 синхро- . низации (по сигналам выходов линий 14 и 15 задержки) на входы первого слагаемого сумматора 2 поступает че- , рез элементы И 6 второй группы содержимое второго регистра 4, и сумма по tnca (2 - 1) содержимого первого и второго регистров 3 и 4 записьшается во второй регистр 4. После этого к содержимому счетчика 10 добавляется единица.

По окончании суммирования всех элементов информационного блока длины К во втором регистре 4 образуется контрольный элемент Ь и сигнал с первого выхода счетчика 10, соответст- вующийг счету К, проходя через элемент И 20, пропускает кон1грольньй элемент через элементы И 7 третьей группы на информационные выходы устройства. Этот же сигнал переполнения, проходя через элемент ИЛИ 24 и элемент 17 задержки, устанавливает в нулевое состояние счетчик 10, регистр 4 и, проходя через элемент ИЛИ 25, регистр 3.

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

25

30

35

40

45

50

55

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

По поступлению элемента Ь на вход 26 устройства и сигнала на тактовый вход 27 устройства сигналы с выходов элементов задержки узла 11 синхронизации разрешают прохождение элемента Ьц через элементы И 5 первой группы и элементы ИЛИ 1 на входы первого слагаемого сумматора 2 и записывают результат сложения Ь с нулевым содержимым регистра 3 в регистр 3. Затем по сигналам узла 11 синхронизации во втором полутакте на входы первого слагаемого сумматора 2 через элементы И 6 второй группы поступает содержимое второго регистра 4 и сумма по moj 2 содержимого первого и второго регистров 3 и 4 записывается во второй регистр 4. После этого к содержимому счетчика 10 добавляется единица и на втором выходе счетчика 10 появляется сигнал, соответствующий счету (К+1).

По окончании приема и суммирования всех (К+1) элементов кодового вектора во втором регистре 4 формируется определитель S, т.е. (Ь + ) oj 2, и сигнал с второго выЬ.. и сигнал с первого выхода счет- чика 10, соответствующий счету К,

0

5

0

5

0

5

0

5

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

По поступлению элемента Ь на вход 26 устройства и сигнала на тактовый вход 27 устройства сигналы с выходов элементов задержки узла 11 синхронизации разрешают прохождение элемента Ьц через элементы И 5 первой группы и элементы ИЛИ 1 на входы первого слагаемого сумматора 2 и записывают результат сложения Ь с нулевым содержимым регистра 3 в регистр 3. Затем по сигналам узла 11 синхронизации во втором полутакте на входы первого слагаемого сумматора 2 через элементы И 6 второй группы поступает содержимое второго регистра 4 и сумма по moj 2 содержимого первого и второго регистров 3 и 4 записывается во второй регистр 4. После этого к содержимому счетчика 10 добавляется единица и на втором выходе счетчика 10 появляется сигнал, соответствующий счету (К+1).

По окончании приема и суммирования всех (К+1) элементов кодового вектора во втором регистре 4 формируется определитель S, т.е. (Ь + ) oj 2, и сигнал с второго выхода счетчика 10, соответствующий счету (К+1), проходя через элемент И 21, пропускает результат анализа определителя S с выхода анализируемо го элемента ИЛИ 23 через элемент И 22 на выход ошибки устройства. Этот же сигнал, проходя через элемент ИЛИ 24 и линию 17 задержки, устанавливае в нулевое состояние счетчик 10, ре- гистр 4 и, проходя через элемент ИЛИ 25, регистр 3.

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

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

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

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

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