Устройство для распознавания на линейность булевых функций

(19 5)5 О 06 Е 7/ ОБР ЕТЕЛЬСТВУ АВТОРСКОМУ С ЗхФлюзюэа рюерюоя,оаЬлы ГОСУДАРСТВЕННЫИКОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР(71) Минский радиотехнический институт(56) Авторское свидетельство СССРЬЬ 1277089, кл. О 06 Р 7/04, 1987,Авторское свидетельство СССРМ 960795, кл. 6 06 Р 7(00, 1982,(54) УСТРОЙСТВО ДЛЯ РАСПОЗНАВАНИЯНА ЛИНЕЙНОСТЬ БУЛЕВЫХ ФУНКЦИЙ(57) Изобретение относится к вычислитель-ной технике и может быть использовано в 2различных технических системах обработки данных в качестве аппаратной поддержки вычислений, Цель изобретения - расширение класса решаемых задач за счет возможности распознавания принадлежности булевой функции классулинейных арифметических полиноминальных форм. Цель изобретения достигается тем, что в устройство, Содержащее блок 3 синхронизации и блок 1 предварительной обработки, введены блок 2 булевого дифференцирования, блок 5 сравнения и блок 4 хранения эталонных значений. 2 з.п, ф-лы. 6 ил.В моменты времени тз, тз+ Лтз, сз+ Лт 2на выходах блока 3 синхронизации, втором, третьем и четвертом выходах соответственно формируются сигналы из второй группы управляющих сигналов (эта группа сигналов обеспечивает управление функционированием блока 2 булевого дифференцирования при дифференцировании с параметром т = 1). Формирование второй, группы управляющих сигналов аналогично 10 формированию первой группы управляющих сигналов, однако третий триггер 13 в этом случае не изменяет своего состояния (состояние логической единицы).Рассмотрим второй случай, когда на 15 первый вход третьего элемента И 21 поступает высокий логический уровень сигнала (признак распознавания (момент времени 14, фиг. 5). Этот сигнал поступает с первого входа на выход третьего элемента И 21 (на 20 втором входе элемента И 21 - высокий логический уровень сигнала, который поступает с выхода элемента НЕ 23, на входе которого - низкий логический уровень сигнала с выхода мультиплексора 15). С выхода третьего 25 элемента И 21 высокий логический уровень сигнала передается на первый вход элемента ИЛИ 22 и далее - на вход останова генератора 10 импульсов. Таким образом, функционирование блока 3 синхронизации 30 завершается.Рассмотрим также случай, когда на первом входе третьего элемента И 21 все время сохраняется низкий уровень сигнала, т.е. признак результата распознавания за 2" 35 тактов не сформирован (функция не линейна). В этом случае в момент времени 16 счетчик 14 переходит в состояние 11 (2" - 1). В момент времени т 6 на (и+1)-м выходе счетчи-: ка 14 формируется сигнал переполнения 40 (высокий логический уровень напряжения). Этот сигнал поступает на второй вход элемента ИЛИ 22 и далее с его выхода - на вход останова генератора 10 импульсов. При этом на первом выходе блока синхрониза ции формируется низкий логический уровень сигнала (признак отрицательного результата распознавания).Рассмотрим работу устройства в совокупности составляющих его компонентов, 50 выделив. в его функционировании ряд эта-пов.На первом этапе работы блок 1 предварительной обработки выполняет анализ элемента хвектора х = (х х ;х " ), Ес ли х =О, то на выход блока 1 предваритель(оной обработки передается вектору х без изменений. В противном случае(х -1) на его выход передается инверсное значение е У ( (ОУф ) У и 1 тНа втором этапе выполняется однократное дифференцирование вектора х или х блоком 2 дифференцирования в соответствии с математической моделью (3) при т = 1. Это обеспечивается группой управляющих сигналов, формируемых блоком 3 синхронизации, результат в виде вектора д х/ дх передается на первый вход блока 5 сравнения.На третьем этапе вычислений блок 5 сравнения осуществляет анализ на совпадение вектора дй д х на первом входе с эталонным вектором х = (1.1), передаваемым на второй вход с выхода блока 4 хранения эталонных значений. В случае несовпадения векторов д х/д х и х на выходе блока 5 сравнения сохраняется низкий логический .уровень сигнала (признак продолжения логической обработки). В случае совпадения векторов д х/д х и 4 на выходе блока 5 сравнения формируется сигнал логической единицы - признак принадлежности распознаваемого вектора х классу линейных арифметических форм.Количество этапов функционирования устройства определяется структурой анализируемого вектора х,На фиг. 6 представлена схема вычислительного процесса распознавания на линейность вектора х = 00001111) и показано изменение на каждом шаге вычислейий содержимого первого 8 и второго 9 регистров блока.2 булевого дифференцирования 2. Результат суммирования по модулю два содержимого первого 8 и второго 9 регистров на каждом шаге поступает на первый вход блока 5 сравнения и на второй вход первогорегистра 8, затем содержимое первого регистра 8 перезаписывается во второй регистр 9, Содержимое последнего сдвигается на т разрядов, а именно на 1, 1 и 2 разряда в соответствии с математической моделью (3), Процесс вычисления заканчивается на третьем шаге, когда результат вида д( д ( дх/ дх)/ дх)/ д (2 х) оказывается равным эталон ному вектору ээ = (111111113.Таким образом; предлагаемое изобретение характеризуетея расширением класса решаемых задач по сравнению с аналогами й прототипом, что обеспечивает оперативный анализ принадлежности заданной булевой функции классу линейных арифметических полиноминальных форм; простотой технических решений и технологичностью изготовления; повышением быстродействия анализа,1756879 21 но, третий управляющий вход которого соединен с входом управления сдвигом второго регистра, информационный вход которого соединен с выходом первого регистра, инФормула изобретения1. Устройство для распознаванйя на лиформационный вход которого соединен с нейность булевых функций, содержащее 5 выходом коммутатора; управляющий вход которого соединен с четвертым управляющим входом блока,3, Устройство по п.,1, о т л и ч а ю щ е еблок синхронизации и блок предваритель- ной обработки, причем управляющий вход устройства соединен с входом запуска блока синхронизации, информационнйй вход с я тем, что блок синхронизации содержит устройства соединен с входом блока,преА мента задержки, три элемента И, элемент признака окончания работы устройства, отИЛИ и элемент НЕ, вход которого соединен л и ч а ю щ е е с я тем, что. с целью расшис входом установки в "1" первого триггера рениякласса решаемых задач за счет воз можности распознавания принадлежности первым входом первого элемента И и выхобулевой функции классу линейныхарифме- дом мультиплекСора, входы которого соедитическихполиноминальныхформ,устройст- нены с выходами и разрядов счетчика, во . содержит блок булевого . счетный вход которого соединен с входами дифференцирования, блок хранения эта первогоивторогоэлементовзадержки,перлонных значений и блок сравнения, при вым входом второго элемента И и выходом этом выход блока предварительной обра- генератора импульсов, вход пуска которого ботки соединен с информационным входом соединен с входом запуска блока, вход приблока булевого дифференцирования, выход знака останова которого соединен с первым которого соедийен с первым входом блока 25 входом третьего элемента И, второй вход сравнения, второй вход которого Соедйненкоторого соединей с выходом элемента НЕ, с вь 1 ходом блока храйения эталонных значе- выход третьего элемента И соединен с входом второготриггера и первым входом элений, выход блока сравнения соединен с.вхомента ИЛИ, второй вход которого соединен домпризнака останова блока синхронизации. с второго по пятый выходы 30 с выходом переполнения счетчика, выход которого соединены с первого почетвертый второго триггера соединен с первым выходом блока, выход элемента ИЛИ соединен с управляющие входы соответственно блока булевого дифференцирования. 2. Устройство по и. 1, отл и ч а ю ще евходом останова генератора импульсов, выход первого элемента задержки соединен с с я тем, что блок булевого дифференцирования содержит коммутатор, узел суммирования по модулю два и два регистра, приэтом информационный вход блока соединен входом синхронизации первого триггера, выход которого соединен с вторым входом второго элемента И, выход которого соединен С входом третьего элемента задержки и с первым информационным входом комму- вторым выходом блока, третий выход кототатора, второй информационный вход кото рого соединен с входом третьего триггера и рого соединен с выходами блока и узлавыходом третьего элемента задержки, выход второго"элементазадержки Соединен с сумматоров по модулю два, первый и второй Информационные входы которого соедине- вторым входом первого элемента И. выход ны с выходами первого и второго. регистров которого соединен"с четвертым выходом соответственно, входы разрешения записи 45блока, выход третьего триггерасоединен с которых соединены с первым и вторым уп- пятым выходом блока.равляющими входами блока соответствен варительной обработки, первый выход бло- генератор импульсов, три триггера, и-разка синхронизации соединен с выходом рядный счетчик, мультиплексор, три эле1756879 Г Рхю/у иу/ Арлат ывщуГ ЮлоюЮфтей Жоlяу 3 хадукиюджин Ахи (гуаггу Онрю акулы Др дуррцуцрд,у1756879 оставитель Д,Кузьмицкийехред М,Моргентал ктор Е.Папп дактор Л,Гратил экаэ 3088 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб 4/5 Производственно-издательский комбинат "Патент", г, Ужгород, ул,ГагаринаИзобретение относится к области цифровой вычислительной техники и может быть использовано для аппаратной поддержки вычислений в системах сжатия данных, синтеза топологии БИС, синтеза и анализа дискретных автоматов, обработки изображений, принятия решений, управления роботами-манипуляторами.Известно устройство, предназначенное держащее блок формирования наборов, группу элементов -неравнозначности, два мультиплексора, элементы ИЛИ и триггеры.Однако эффективность его использования является низкой по ряду критериев, что 15 не позволяет воспользоваться им на практике, Причина заключается в том, что результирующий вектор, полученный в результате обработки вектора значений бу 20 левой функции по математической модели,положенной в основу данйогоустройства,приходится сравнивать с ряДом эталонов,количество которых близко к числу булевых функций, относящихся к классу линейных 25 арифметических полиноминальныхформ Наиболее близким к предлагаемому по функциям и технической сущности является устройство, содержащее блоки определения свойств несохранения константы нуля,30 единицы, немонотонности, нелинейности и блок несамодвойственности (а заявляемом объекте - блок предварительной обработки), дешифратор наборов свойств йолноты, регистр запоминания наборов свойств полноты, дешифратор базисных групп, блок сборки (в заявляемом объекте - блок синхронизации) и соответствующие связи, причем блок определения свойств нелинейности содержит группу. сумматоровпо модулю два, группу элементов И и элемент ИЛИ, а блЬк определения свойств не-,самодвойственности содержит два сумматора по модулЮ два, элемент ИЛИ иэлемент НЕ,Это устройство позволяет определить функциональную полноту системы булевых функций, Однако ононе пригодно для решения поставленной задачи по следующим причинам, блок определения свойства нелинейно сти устройства позволяет распознать функции на принадлежность клаСсу линеййых,но линейных в смысле представимости линейными полиномами Жегалкина, т;е логическими полиномами. Заявляемый обьект 55 решает иную задачу - распознает принадлежность классу линейных арифметических полиномов,.Частично удается решить поставлейную задачу с помощью блока определения для вычисления булевых производных и со свойств несамодвойственности. Но к линейным арифметическим полиномам соотносятсяне все самодвойственные функции, а толькоопределенный их класс.Таким образом, с помощью известныхтехнических устройств не удается решитьважную задачу - оперативно определитьпринадлежность заданной булевой функции классу линейных арифметических полиноминальных форм. Это затрудняетрешение связанных с данной прикладныхзадач сжатия логических данных или бинарных изображений (как системы булевыхфункций), хранения и обработки топологических изображений, обработки логическихданных на структурах, не имеющих логических операций, и т,д.Цель изобретения - расширение классарешаемых задач за счет возможности распознавания принадлежности булевой функции классу лйнейных арифметическихполиноминальных форм,Поставленная цель достигается тем, чтов устройство, содержащее блок синхронизации и блокпредварительной обработки,причем управляющий вход устройства соединен с входом запуска блока синхройизации, ийформационный вход устройствасоединен с входом блока предварительнойобработки; первый выход блока синхронизаций соединен с выходом признака окончания работы устройства, введены блокбулевого дифференцирования, блок сравнения и блок хранения эталонных значений,выход которого подключен к второму входу. блока сравнения; первый вход которогоподключен к выходу блока булевого дифференцирования, информационный вход которого подключен к выходу блокапредварительной обработки, а управляющие входы с первогопо четвертый блокабулевого дифференцирования подключенысоответственнос второго попятый выхода. ми блока синхронизации, второй вход которого подключен к выходу блока сравнения,кроме того, блок булевого дифференцировайия содержит коммутатор,узел сумматОровпо модулю два-и два регистра, при этоминформационный вход блока соединен спервым, информационным входомкоммутатора, второй информационныйвход которогосоединен с "выходами блока и узласумматоров помодулю два, первый и второйинформационные входы которого соединеныс выходами первогои второго регистровсоответственно; входы разрешениязаписи .которыхсоединены С первым и вторым.управляющими входами блока соответственно, третий управляющий вход которогосоединен с входом управления сдвигом вто1756879 ность полиноминального описания системы функций и решение задач минимизации (сжатия) системы булевых функций на основе данной формы, В связи с этим возникает необходимость оперативного распознава ния булевой функции на принадлежность классу линейных арифметических полиноминальных форм. Класс линейных форм определяется соотношением(2) р(х) р+ р )х + р х+,+рфх 1 Выполним операцию дифференцирования согласно выражению (3) Таким образом, решение поставленной задачи в принципе сводится к построению (вычислению) для задайной булевой функции полинома (1) и проверке его условию(2). Однако такой путь не является эффективным по вычислительной сложности. В основу реализуемого заявляемым устройством подхода положены математические модели 20 на основе аппарата логического дифференцирования.В матричном виде оператор йараметрического дифференцирования по координате Х вектора значений х булевой функции 1(х) 25 имеет вид 1 -ъахДРх) 2 1 0001 0001 10001 000 100 0 1т-) = м п х (аос 3 2), (3)3 (0.0, 001;, 11) - координата ейцирования с отсчетами, соответими упорядоченным наборам перех 1 х, те 2 г, ( р = 0,0,1,2,;,.и) - тр дифференцирования; М ) размерности 2 ф х 2" (и - количество нных), формируемая по рекуррентавилут и 1) . ю ГЧи Игт"Мг)= М п Гюоо 2) ю казать, что удаетсяа-3то вектор х относитсяарифметических полинРассмотрим в рамкганизацию вычислитеконкретйом примереПусть задан векто4 функйии тРех пеРемен.к классу линейных оминальных форм. ах этого условия орльного процесса на р значений булевой ных х=0011 Первый шаг вычис анализе элемента хф равен нулю (а в данно вйполняется следующ противном случае, т.е; вляется инвертирован На втором шаге вы 55 ся дифференцировани по координате Х с пара но выражению (3)001 17 ебуется наййий Пусть, например, т водную вектора знач х (00010110),евой мтгде т функ где х диффер ствующ меннйх параме матрица переме ному пр1) И г=М символ транспортированияи трех переменных с парамет лении заключается в вектора х, Если он м случае хго 1 = О), той шаг вычислений. В если хф =1, осущесте всех элементов х. числений выполняете вектора значений хметром т= 1 соглас1756879 10 дх и) - =,М зх= дяР 10 что соответствует линейному полиному ви. да Р(Х) = хг.Рассмотрим другой прймер, поясняющий суть математической модели устройства, когда исходный вектор значений хне принадлежит классу линейных арифметических полиноминальнйх форм, Пусть он определен в виде Поскольку дифференцирование с г= 1 не привело к искомому результату, а количество шагов не исчерпано (всего можно выполнять 2" 1 шагов), а в данном случае и;-3, 20 то выполняется переход к следующему шагу.На третьем шаге реализуется операция дифференцирования вектора д х/ д х, полученного на предыдущем шаге вычислений 25 х=0100110 Ц. Поскольку хи = О, вектор х не инвертируется, и его первая частная производная при т=.1 равнадх )- :М зХ=-- =Идр дх г дк 30 Повторим зту процедуру при т, = 1 ещераз 40 На этом вычисления заканчиваются, так как исходный вектор значений хфприведен к виду 1 1 1 1 1 11 Ц, что является признаком принадлежности его классу линейных арифметических полиноминальных форм. Это 45 легко проверить, используя аппарат преоб- . разований.Так называемое преобразование Фурье в коньюнктивном базисе Кгп вектора значе. ний х позволяет получить вектор козффици ентов Р арифметической полиноминальной формы Р:К,дх: При значении т=2 получим 1 11 11 11 11 11 111 1 11 11 11 111 О 1 0 0 О 1 0 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 0000000 - 11000000 - 1 01 00000 1 - 1 - 1 1 0000 - 10001000 1 - 100-1100 1 01 01 010 - 1 1 1-1 1-1-1 1 1 11 11 11 11 11 11 1 11 11 11 11 11 11 11 0 1 0 0 1 0 1 0 с 1 1 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1о 0 1 о о О 0 ,0 0 1 1 1 1 0 0 11011011 011011011011 01 0 1 1 1 1 О 0 1 10 Р=к зх= О 1 0 -11 -1 -1 О 0 1 0 0 1.1 0 1 10000000 - 11000000 -101 00000 1-1 - 110000 - 10001 0001-1 0 0-1 1 0 0 1 0-1 0-1 0 1 0 -1 1 1-1 1-1 - 1 1 30 35 т.е, р(х) = хз - хгхз + х 1 - х 1 хз - х 1 хг не естьлинейный арифметический полином,На фиг. 1 представлена структурная 40схема устройства; на фиг. 2 - блок предварительной обработки; на фиг. 3 - блок булевого дифференцирования; на фиг. 4 -структурная схема блока синхронизации; нафиг. 5 - временная диаграмма функционирования блока синхронизации; на фиг. б -работа устройства.Устройство (фиг. 1) содержит блок 1предварительной обработки, блок 2 булевого дифференцирования, блок 3 синхронизации, блок 4 хранения эталонных значений иблок 5 сравнения, выход которого соединенс вторым входом блока 3 синхронизации,вход запуска которого соединен с управляющим входом устройства, а первый выход 55блока 3 синхронизации является выходомпризнака окончания работы устройства,причем с второго по пятый выходы блока 3синхронизаций соединены соответственнос первого по четвертый управляющими вхоНа этом вычисления заканчиваются, так как количество операций и = 3. Результат не равен(11, поэтомуисходный вектор х не 15 принадлежит классу линейных арифметических полиноминальных форм. В этом легко убедиться, выполнив над ним преобразование Фурье в коньюнктивном базисе Кгп (и.= =3) 20 дами блока 2 булевого дифференцирования,выход которого соединен с первцм входомблока 3 сравнения, второй вход которогосоединен с выходом блока 4 хранения эталонных значений, а пятый (информационный) вход блока 2 булевогодифференцирования подключен к выходублока предварительной обработки, вход которого является информационным входомустройства.Блок 1 предварительной обработкиобес(печ(ивает пере)дачу вектора значений х== .(х ) х )х(с входа на выхоод безо) 1) (гптизменений в случае, если элемент х(,) = О,или в инвертированном виде, если х = 1.(о,Блок булевого дифференцирования 2обеспечивает логическую обработку векто - э =Гра х или х, поступающего на его пятый (информационный) вход в соответствии сматематической моделью.Блок 3 синхронизации предназначендля формирования сигналов, управляющихработой устройства.Блок 4 хранения эталонных значенийпредназначен для хранения кода размерности 2" вида (11. Конструктивно он выполнен в виде жесткого соединения разрядныхшин выхода блока с второй по 2"-ю с шинойвысокого логического уровня напряжения(логической единицы),Блок 5 сравнения предназначен дляанализа на совпадение кодов, поступающихна его первый и второй входы. При совпадении кодов на его выходе формируется сигнал логической единицы.Блок 1 предварительной обработки,блок 2 булевого дифференцирования и блок3 синхронизации имеют особенностисхемотехнических решений и функционирования.Блок 1 предварительной обработки(фиг. 2) содержит 2 ф сумматоров 11(1 = 1, 2 д)по модулю два, вторые входы которого соединены между собой и подключены к первому входу первого сумматора 11 по модулюдва; первый вход 1-го сумматора по модулюдва является первым входом блока 1 предварительной обработки.Блок 1 предварительной обработки работает следующим образом. При поступлении на его вход элементов вектора значений(О) (1) (гп) тх = ххх( ) булевой функции и пере-,менных осуществл 1 е)тся анализ значенийпервого элемента х . При этом возможны,одва случая.В первом случае, когда х = О, на сум(о)маторах по модулю два с 11 по 1 г" выполняется сложение по модулю два логическогонуля со значениями элементов вектора х. Врезультате на выход блока 1 предваритель- налу на втором входе (входе разрешенияной обработки передаются все элементы записи). Сдвиг содержимого в сторону младвекторах без изменений., ших разрядов выполняется по сигналу наВо втором случае, когда х = 1, на сум- третьем входе (входе управления сдвигом),маторах по модулю два с 11 по 12 л выпол Блок 2 булевого дифференцированияняется суммирование по модулю два работает следующим. образом. Предварилогической единицы со значениями элемен- тельно во все разряды первого 8 и второготов вектора э В результате на выход блока 9 Регистров записываютСя нули. С четверто 1 предварительной обработки передаются го информационного входа блока по трактуинверсные значения элементов вектора х 10 первый вход - выход коммутатора 6 (на:х х( ,х третьем - управляющем - входе коммутатоТаким образом, блок 1 предваритель- Ра 6 - низкий логический УРовень сигнала) вной обработки осуществляет передачу век- первый регистр 8 осуществляется запись котора х с входа на выход в прямом или в да анализируемого вектора х или х, моментинверсном коде в зависимости оттого нуле времени 11.(фиг. 5).вое или единичное значение соответствен- В момент времени 11+ Лз по сигналуно имеет первый элемент вектора х. на втором управляющем входе блока 2 булеБлок 2 булевого дифференцирования (фиг, вого дифференцирования осуществляется3) содержит коммутатор 6, узел 7 суммато- перезапись кода вектбрах из первого региров по модулю два, первый 8 и второй 9 20 стра 8 но второй регистр 9, В момент времерегистры, при этом пятый (информацион- ни т 1 + Лтг по сигналу на третьемный) вход блока соединен с первьм инфор- управляющем входе блока 2 выполняетсямационным входом коммутатора 6,.второй сдвиг на один разряд в сторону младшихинформационный вход которого соединен с содержимого второго регистра 9, На вьходевыходами блока и узла 7 сумматоров по мо 25 узла 7 сумматоров по модулю два формирудулю два, первый и второй информацион- . ется результат д х/дх.ные входы которого соединены с выходами Далее функционирование блока 2 булепервого 8 и второго 9 регистров соответст- вого диФференцирования заключается в завенно, вторые входы(входы разрешения за- писи полученного результата в первыйписи) которых соединены с первым и 30 регистр 8 (момент времени з), перезаписивторь 1 м управляющими входами блока соот- его из первого регистра 8(тз+ йз) во второйветственно, третий управляющий вход кото регистр 9, сдвиге на один разряд в сторонурого соединен с третьим входом (входом младших содержимого второГо регйСтра 9управления сдвигом) второго регистра, пер- (момент времени тз + Ь 12) и поразрядномвый (информационный) вход которого сое суммировании по модулю два содержимыхдинен с выходом первого регистра 8, первого 8 и второго 9 регистров и узле 7первый (информационный) вход которого сумматоров по модулю два; Тем самым форсоединен с выходом коммутатора 6, третий мируется результат вида д( д х/ дх)/дх. Уп(управляющий) вход которого соединен с равляющие сигналы записи в первыйчетвертым управляющим входом блока; 40 регистр 8, записи во второй регистр 9, сдвигКоммутатор 6 предназначен для пере- содержимого второго регйстра 9 на одиндачи информации с первого или второго ин- или несколько разрядов соответственно наформационных входов на выход первом, втором и третьей входах блока 2соответственно при низком или высоком ло- булевого дифференцирования повторяютсягическом уровне сигнала на его третьем уп циклически,равляющем входе, Блок 3 синхронизации (фиг. 5) содержитУзел 7 сумматоров по модулю два обес- гейератор 10 импульсов, первый 11, второйпечивает поразрядное сложение по модуйю 12 и третий 13 триггеры, счетчик 14, мультидва кодов, поступающих на его первый и . плексор 15, первый 16, второй 17, третий 18второй входы. 50 элементы задержки, первый 19, второй 20 иПервый регистр 8 предназначен длятретий 21 элементы И, элемент ИЛИ 22 иприема и кратковременного хранения кода элемент НЕ 23, вход которого соединен сх, поступающего с первого (информацион- входом установки в единицу первого триггеного)входа по сигналу на втором входе(вхо- ра 11, первым входом первого элемента Иде разрешения записи). 55 19 и выходом мультиплексора 15, входы коВторой регистр 9 предназначен для торого соединены с выходами и разрядовприема, кратковременного хранения и пре- счетчика 14, счетный вход которого соедиобразования (сдвига) кода, поступающего нен с входами первого 16 и второго 17 элена первый (информационный) вход по сиг- ментов задержки; первым входом второго10 15 20 30 40 45 50 55 20 элемента И и выходом генератора 10 импульсов, вход пуска которого соединен с входом запуска блока, вход признака оста- нова которого соединен с первым входом третьего элемента И 21, второй вход которого соединен с выходом элемента НЕ 23, выход третьего элемента И 21 соединен с входом второго триггера 12 и с первым входом элемента ИЛИ 22, второй вход которого соединен с выходом переполнейия счетчика 14, выход второго триггерз 12 соединен с первым выходом блока, выход элемента ИЛИ 22 соединен с входом останова генератора импульсов, выход первого элемента задержки 16 соединен с входом синхронизации первого триггера 11, выход которого соединен с вторым входом второго элемента И 20, выход которого соединен с входом третьего элемента 18 задеркки и вторым выходом блока, третий выход которого соединен с входом третьего триггера 13 и выходом третьего элемента 18 задержки, выход второго злелента 17 задеркки соединен с вторым входом первого элемента И 19, выход которого соединен с четвертым выходом блока, выход третьего триггера 13 соединен с пятым выходом блока.Генератор 10 импульсов предназначен для формирования регулярной последоватетьности импульсов и имеет первый вход пуска и второй вход останова.Первый триггер 11 предназначен для управления работой второго элемента И 20 с целью формирования импульсов на первом и втором выходах блока 5 синхронизации. В нулевом состоянии триггер 11 блокирует формирование импульсов на первом и втором выходах блока 5 синхронизации (фиг. 5). Конструктивно это синхронный О-триггер с установкой и сбросом (например, К 155 ТМ 2), причем йа входы О и В постоянно подаются уровни логического нуля и единицы соответственно, Первым входом (входом установки в единицу) пеовога триггера 11 является вход установки 5, а вторым входом - вход синхронизации С. Начальное состояние первого триггера 11-единичное.Второй 12 и третий 13 триггеры предназначены для формирования сигналов на четвертом и пятом выходах блока 3 синхронизациии соответственно. Конструктивно это О-триггеры, которые по Фронту на их входе устанавливаются в едийичное состоя- ние. Исходное состояние их - нулевое,Счетчик 14 предназначен для регламентирования работы устройства. Конструктивно он представляет собой и-разрядный счетчик суммирующего типа со счетным входом, (и+1)-й выход счетчика 14 - выход переполнения. Начальное состояние его - нулевое.Мультиплексор 15 предназначен для формирования на своем выходе сигнала, управляющего работой первого триггера 11,третьего элемента И 21 и элемента НЕ 23. Мультиплексор 15 формирует на своем выходе сигнал логического нуля при следующих значениях на своих адресных входах: О, п - 1 2, 44+ " (2 р+ 1). Во всех остальных р - 1случаях на выходе мультиплексора 15 - сигнал логической единицы (таблица ),Режим работы мультиплексора 15, имеющего и адресных и 2" информационных входов, обеспечивается тем, что адресные входы с первого по и-й подключаются к соответствующим выходам (с первого по и-й) счетчика 14. На информационные входымультиплексора 15 подключаются потенциалы логических уровней в соответствии стаблицей,Конструктивно разрядность мультиплексора 15 (2" -ф 1) может быть достигнута использованием каскадного соединения мультиплексоров,Первый 16, второй 17 и третий 18 элементы задержки обеспечивают задеркку ВхаднОгО Сигнала на врвмя Лт 1, Л 12 и ЛтЗ соответственно.Первый 19, второй 20 и третий 21 элементц И предназначены для логического анализа поступающих на входы сигналов 35 путем выполнения операции коньюнкции.Элемент ИЛИ 22 предназначен для логического анализа входных сигналов посредством выполнения над ними операции дизъюн кции,Функции блока 3 синхронизации заключаются в формировании сигналов управления работой блока2 булевого дифференцирования. Предварительно триггер 11 устанавливаются в состояние логической единицы, второй 12 и третий 13 триггеры - в состояние логического нуля, а счетчик 14 - в нулевое состояние. Запуск блока 3 синхронизации осуществляется по сигналу на входе пуска генератора 10 импульсов. На первом выходе блока 2 синхронизации формируется признак результата распознавания, на втором и третьем выходах формируются соответственно сигналы записи в первый 8 и второй 9 регистры блока 2 булевого дифференцирования, на четвертом выходе 3 синхронизации формируется сигнал сдвига во втором регистре 9, на пятом выходе формируется сигнал, регламентирующий функционировайие коммутатора 6, Количество сигналов сдвига х, Формируемых на четвертом выходе блока 3 синхро- та И 19, На второй вход первого элемента И низации, определяется по значению кода на 19 в момент времени т + Ь т 2 с выхода втовыходах счетчика 14. Таким образом, сигна- рого элемента 17 задержки (фиг. 5) поступдлы записи и сдвига, формируемые на вто- ет импульсный сигнал, который передается ром, третьем и четвертом выходах блока 3 5 с выхода первого элемента И 19 на четвер- синхронизации, образуют группу управляю- тый выход блока 3 синхронизации.щих сигналов, регламентирующих функцио- Кроме того, высокий логический уронирование блока 2 булевого вень сигнала с выхода мультиплексора 15 дифференцирования втечение выполнения передается на вход установки в единицу операции булевого дифференцирования с 10 первого триггера 11, при этом сигнал на: параметром х. выходе первого триггера 11 не изменяется,Рассмотрим формирование первой В момент времени И + Лц на вход синхрогруппы управляющих сигналов на выходах низации первого триггера 11 поступает имблока 3 синхронизации. Эти сигналы обес- пульсный сигнал с выходапервого элемента печивают управление функционированием 15 16 задержки, и триггер 11 переключается в блока 2 булевого дифференцирования в те- состояние логического нуля. В результате в чение выполнения операции булевого диф- момент времени 12 на второй выход блока 3 ференцирования с параметром т = 1, Это синхронизации импульсный сигнал не по- обусловлено следующей работой элементов . ступает.блока 3 синхронизации 20 . Таким образом, в моменты времени свВ момент времени то (фиг, 5) осуществ- с 2 на выходах блока синхронизации формиляется запуск устройства. В результате им- руется первая группа управляющих сигнапульсный сигнал, формируемый на выходе лов; в момент времени О - на втором генератора 10, поступает на входы счетчика выходе; ц + Лтз - на третьем выходе, в 14, первого 16, второго 17 элементов задер момент времени 11+ Ьйз - сигнал сдвига на жкии второго элемента И 20, с выхода кото- четвертом выходе (импульсные сигналы) и рого импульсный сигнал передается на на пятом выходе формируется высокий ловторой выход блока 3 синхронизации (на гический уровень потенциала.втором входе второго элемента И 20 - высо- В момент времени т 2 счетчик 14 перехокий логический уровень сигнала, поступаю дит из состояния 001 в состояние 0010, щий с выхода первого триггера 11 (от и на выходемультиплексора 15 формируетнаходится в состоянии логической едини-. ся низкий логический уровень сигнала, котоцы). Кроме того, импульсный сигнал с выхо- рый вызывает следующие измЕнения в да второго элемента И 20 поступает на вход схеме: первый триггер 11 устанавливается в третьего элемента 18 задержки. В момент 35 состояние логической единицы, на выходе времени ЛО+ Лтз(Л тз - время задержки первого элемента И 19 формируется низкий на третьем элементе 18 задержки) импульс-, логический уровень сигнала, который блокиный сигнал с выхода третьего элемента 18 рует формирование импульсов на четвертом задержки передается натретий выходблока выходе блока 3 синхронизации (фиг, 5), На 3 синхронизации, а также на вход третьего 40 выходе элемента НЕ 23 формируется высо- триггера 13, который устанавливается в со- кий логический уровень сигнала, который стояние логической единицы, и на пятый передаетсянавторойвходтретьегоэлеменвыходблока 3 синхронизациипоступаетвы- та И 21, В результате на выход третьего сокий логический уровень сигнала (он со- элемента И 21 передается сигнал, поступахраняется на пятом выходе блока 5 45 ющий на первый вход третьего элемента И синхронизации до окончания выполнения 21 с входа признака останова блока 3 синхбулевого дифференцирования). На первом ронизации (это сигнал-признак результата выходе блока 3 синхронизации сохраняется распознавания с выхода блока 5 сравнения), низкий логический уровень сигнала. Рас- При этом возможны два случая, когда присмотрим формирование сигнала на четвер знак сравнения равен нулю, и когда признак том выходе блока 3 синхронизации. По сравненияравенединице. Рассмотримперимпульсному сигналу, формируемому на вы- вый случай, т.е, случай, когда на первый вход ходегенератора 10 импульсоввмоментвре- третьего элемента И 21 поступает низкий мени с 1 (фиг. 5), счетчик 14 переходит. из. логическийуровеньсигнала. Тогда на выхосостояния 00 всостояние 001, Код О.,;01 55 детретьего элемента И 21 сохраняется низс выхода счетчика 14 передается на входы с кий логический уровень сигнала. В первого по и-й мультиплексора 15, на выхо- результате блок 3 синхронизации подготовде которого формируется высокий логиче- лен к формированию следующей первой ский уровень сигнала (таблица), который группы управляющих сигналов,передается на первый вход первого элемен