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

 

Изобретение относится к вычислительной технике и может быть использовано 0 различных технических системах обработки данных в качестве аппаратной поддержки вычислений. Цель изобретения - расширение класса решаемых задач за счет возможности распознавания принадлежности булевой функции классу линейных арифметических полиномин альных форм. Цель изобретения достигается тем, что в устройство, Содержащее блок 3 синхронизации и блок 1 предварительной обработки, введены блок 2 булевого дифференцирования, блок 5 сравнения и блок 4 хранения эталонных значений . 2 з.п. ф-лы. 6 ил.

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

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

РЕСПУБЛИК (я)5 G 06 F 7/00

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

»

«» ь «, ! " " 1 Т"

Мрарма оиный Ох

Ь хФлюзж7га аююр ия,оа & ты

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4883277/24 (22) 16.11.90 (46) 23.08.92. Бюл. N 31 (71) Минский радиотехнический институт (72) И,Н.Бондарь, Д.В,Кузьмицкий, В,П.Шмерко и С.H,ßíóøêåâè÷ (56) Авторское свидетельство СССР

hL 1277089, кл. G 06 F 7/04, 1987.

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

N- 960795, кл. G 06 F 7/00, 1982, (54) УСТРОЙСТВО ДЛЯ РАСПОЗНАВАНИЯ

НА ЛИНЕЙНОСТЬ БУЛЕВЫХ ФУНКЦИЙ (57) Изобретение относится к вычислитель- ной технике и может быть использовано в

„„5U„„ i756879 А1 различных технических системах обработки данных в качестве аппаратной поддержки вычислений, Цель изобретения — расширение класса решаемых задач за счет возможности распознавания принадлежности булевой функции классу линейных арифметических полиноминальных форм. Цель изобретения достигается тем, что в устройство, Содержащее блок 3 синхронизации и блок 1 предварительной обработки, введены блок

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

1756879

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

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

Однако эффективность его использования.является низкой по ряду критериев, что

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

25 арифметических полиноминальных форм

Наиболее близким к предлагаемому по функциям и технической сущности является устройство, содержащее блоки onðåäåëåния свойств несохранения константы нуля, 30 единицы, немонотонности, нелинейности и блок несамодвойственности (в заявляемом объекте — блок предварительной обработки), дешифратор наборов свойств йолноты, регистр запоминания наборов свойств полноты, дешифратор базисных групп, блок сборки (в заявляемом объекте — блок синхронизации) и соответствующие связи, причем блок определения свойств нелинейности содержит группу. сумматоров по модулю два, группу элементов И и эле- 40 мент ИЛИ, а блЬк определения свойств не-, самодвойственности содержит два сумматора по модулЮ два, элемент ИЛИ и элемент HE.

Это устройство позволяет определить функциональную полноту системы булевых функций. Однако оно не пригодно для решения поставленной задачи по следующим и р ичинам. блок определения свойства нелинейно- 50 сти устройства позволяет распознать функции на принадлежность клаСсу линеййих, но линейных в смысле представимости линейными полиномами Жегалкина, т;е логическими полиномами. Заявляемый обьект

55 решает иную задачу — распознает принадлежность классу линейных арифметических полиномов, .

Частично удается решить поставлейную задачу с помощью блока определения для вычисления булевых производных и со- 10 свойств несамодвойственности. Но к линейHblM арифметическим полиномам соотносятся не все самодвойственные функции, а только определенный их класс.

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

Цель изобретения — расширение класса решаемых задач за счет возмо>кности распознавания принадлежности булевой функции классу:лйнейных арифметических полиноминальных форм, Поставленная цель достигается тем, что в устройство, содер>кащее блок синхронизации и блок предварительной обработки, причем управляющий вход устройства соединен с входом запуска блока синхройизации, информационный вход устройства соединен с входом блока предварительной обработки; первый выход блока синхронизаций соединен с выходом признака окончания работы устройства, введены блок булевого дифференцирования, блок сравнения и блок хранения эталонных значений, выход которого подключен к второму входу . блока сравнения; первый вход которого подключен к выходу блока булевого дифференцирования, информационный вход которого подключен к выходу блока предварительной обработки, а управляющие входы с первого по четвертый блока булевого дифференцирования подключены соответственно с второго по пятый выхода- . . ми блока синхронизации, второй вход которого подключен к.выходу блока сравнения, кроме того, блок булевого дифферен цировайия содержит коммутатор, узел сумматоров по модулю два-и два регистра, при этом информационный вход блока соединен с первым, информационным входом коммутатора, второй информационный вход которого соедине н с:. вы хо дами блока и узла сумматоров по модулю два, первый и второй информационные входы которого соединены с выходами первого и второго регистров соответственно; входы разрешения записи -. которых соединены С первым и вторым.управляющими входами блока соответственно, третий управляющий вход которого соединен с входом управления сдвигом вто1756879

Р(Х)=Р(п1+Р 1 Хп+РГ21кп-1+Р Хп-1Хп+... +

2 — 1 и р(1} Д ...,1, 1=О

xi =x ;

ОО

5 6 рого регистра, информационный вход кото- так называемой арифметической полиномирого соединен с выходом первого регистра, нальной форме, которая имеет аналитичеинформационный вход которого соединен с ское представление вида выходом коммутатора, управляющий вход которого соединен с четвертым управляю- 5 щим входом блока. Блок синхронизации содержит генератор импульсов, три триггера, и-разрядный счетчик, мультиплексор, три г ll (2 — 1} элемента задержки, три элемента И, эле- +р мент ИЛИ и элемент НЕ, вход которого со- 10 единен с входом установки в единицу первого триггера, первым входом первого элемента И и выходом мультиплексора, вхо(1) ды которого соединены с выходами и разрядов счетчика, счетный вход которого 15 „е 0) z z-мн ж где р я г, г — множество целых чисел, таких, соединен с входами первого и втоРого эле- что р(х) < (0,1) на любом наборе переменных го "У " УпоРЯдоченных набоРах пеРеменных фУнкзапуска лока, вход признака останова Ко- 20 таблицы истинности); t-J-й разряддвоичноторого соединен с первым входом третьего: го и ти); 1-1-и разряд двоичноэлемента И вто ой го представления параметра i (нумерация со элемента, второй вход которого соединен старши ). с выходом элемента ИЛИ, выход третьего элемента И соединен с входом второго триго гера и с первым входом элемента ИЛИ, вто- 25 ..xi = 1. рой вход которого соединен с выходом переполнения счетчика, выход второго шен

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

1(х) = х1х2 v х!х2, синхронизации первого триггера, выход которого соединен с вторым входом второго имеет арифметическую полиноминальн ю элемента И, выход которого соединен с вхот ог форму вида дом третьего элемента задержки и вторым 35 р(х) = x1+ х2 - 2х1х2. выходом блока, третий выход которого соединен с входом третьего триггера и выходом . третьего элемента задержки, выход второго ных „„и х этo вы ж

На любом наборе ОО, 01, 10. 11 пе еменных х1 и х2 это выра ение имеет значени О дом первого элемента И, выход которого 40 н н вто ым вхо или 1 и они в упорядоченном виде есть не соединен с четвертым выходом блока, ничто иное, как векто знач и функции f(x), Действительно ход третьего триггера соединен с пятым выf

Суть данного изобретения заключается в том, что исследуемая. булевая функция, 45 х1х2: ИХ1

f(): р(х) заданная вектором своих значений на упорядоченных наборах переменных, поДвергается специальной обработке, называемой 01 параметрическим дифференцированием по

1 координате. В результате этой обработки, 50 10 если функция принадлежит классу линейных арифметических форм, получается определенныи вектор и для распознавания

11: О принадлежности достаточно сравнить его с эталонным значением. иноминальная форма отличается от известВ основу данного изобретения положеных логических представлений, нап им р д влений, например ны следующие математические модели ком- - ем а и м полинома Жегалкина, и еж е всего н ем арифметических операций. Эта форма

Любая булевая функция 1(х)п перемендля инженернои практики является возмож1756879 (4)

И

p(Ä) р(о) + p()ÄÄ + p()хя, + р()х1 (2) Таким образом, решение поставленной задачи в принципе сводится к построению (вычислению) для задайной булевой функ ции полинома (1) и проверке его условию(2).

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

В матричном виде оператор йараметрического дифференцирования по координате

Х вектора значений х булевой функции f(x) 2 имеет вид

1 0001

0001

10001

000

1 0 0

30

35 „=(1...1), <Е2 р =0,0, 1 ... и — 1, дх.1

1 1 (4) Первый шаг вычиЧлений заключается в анализе элемента х вектора х, Если он равен нулю (а в данном случае х () = О), то вйполняется следующий шаг вычислений. В противном случае, т.е; если х = 1, осущест- . вляется инвертирование всех элементов х.

На втором шаге вычислений выполняет55 ся дифференцирование вектора значений х по координате Х с параметром t= 1 согласно выражению (3) Ф

1 1 х (О О О 1 0 1 1 1 0), ность полиноминального описания системы функций и решение задач минимизации (сжатия) системы булевых функций на основе данной формы, В связи с этим возникает необходимость оперативного распознавания булевой функции на принадлежность классу линейных арифметических полиноминальных форм. Класс линейных форм определяется соотношением - — "„1— мсдп х (mod 2),. (3) где х - (0...0. 0...01...;. 1...1) — координата дифферейцирования с отсчетами, соответствующими упорядоченным наборам переменнйх x1,...,x„; tå 2г, (р = 0,0,1.2,;..п-1)— параметр дифференцирования; М „) матрица размерности 2" х 2" (n — количество переменных), формируемая по рекуррентному правилу

1 ) (1) П) <1) . f,r Г )

I"1 =М,п И и М n=(, nj (гт Од2)

Пусть, например, требуется найти производную вектора значейий где т — символ транспортирования булевой функции трех переменных с параметром t=4. Матрица М(„) в соответствии с правилом (4) имеет вид

1000 j

000

0001

1 000

000

0 0

1 0

Выполним операцию дифференцирования согласно выражению (3)

1 ах <> дух) 0

1

1

1

Можно показать, что удается получить результат вида

-3» то вектор х относится .к классу линейных арифметических полиноминальных форм.

Рассмотрим в рамках этого условия организацию вычислительного процесса на конкретйом примере.

Пусть задан вектор значений булевой функции трех переменных х = (О О 1 1 О О 1 1) ..

1756879

10 о

1 о о

О

О, О дх «) — =M р,=. я

10 что соответствует линейному полиному ви. да Р(Х) = хг.

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

Поскольку дифференцирование с г= 1 не привело к искомому результату, а количество шагов не исчерпано (всего можно выполнять 2" 1 шагов), а в данном случае и;- 3, 20 то выполняется переход к следующему шагу.

На третьем шаге реализуется операция дифференцирования вектора д х/ д х, полученного на предыдущем шаге вычислений 25 х = (О 1 0 0 1 1 0 Ц .

Поскольку х() = О, вектор х не инвертируется, и его первая частная производная при z-=1 равна дх «>» — =М лХ=

Дк г — — =И дрдх дк

Повторим зту процедуру при т = 1 еще раз дх дх Z . дх

На этом вычисления заканчиваются, так как исходный вектор значений х приведен к виду(1 1 I 1 1 1 1 Ц, что является признаком принадлежности его классу линейных арифметических полиноминальных форм. Это 45 легко проверить, используя аппарат преоб- . разований.

Так называемое преобразование Фурье в коньюнктивном базисе К п вектора значений х позволяет получить вектор козффици- 50 ентов Р арифметической полиноминальной формы

Г1

Р=Кдх=

При значении т = 2 получим

1 1

1 1

1 1

1 1

1 1

1 1

1 1

1 1 1 1

1 1

1

1 1

О

l

0

0

О

0

0

О .1

О I

О

0

1

1

1

10000000 — 11000000 — l 01 00000

1 — 1 — 1 l 0000 — 10001000

1 — 1001100

1 01 01 01 0 — 1 1 1-1 i-1-1 1

1 1

1 1

1 1

1 1

1 1

1 1

1 1

1 1

1 1

1 1

1 1

1 1

1 1

1

О

1

О

0

1

О

1

О

О

1

0

0

1

1

1

0

1756879

1

1

0

О

1 0 1

101

1 0 1 1 01

1 0 1

1 О 1

1 0

10 р=к зх =

1

0 — 1

-1

-1

1

О

1.

О

10000000 — 1 1 000000

-1 01 00000

1 — 1-110000 — 10001 000

1-t 001 1 00

10-10-1010

-1 1 1-1 1-1 — 1 1

35 т.е. р(х) = хз - х2хз + x> - х1хз - x>x2 не есть линейный арифметический полинам.

На фиг. 1 представлена структурная 40 схема устройства; на фиг. 2 — блок предварительной обработки; на фиг. 3 — блок булевого дифференцирования; на фиг. 4— структурная схема блока синхронизации; на фиг. 5 — временная диаграмма функциони- 45 рования блока синхронизации; на фиг. 6— работа устройства.

Устройство (фиг. 1) содержит блок 1 предварительной обработки, блок 2 булевого дифференцирования, блок 3 синхрониза- 50 ции, блок 4 хранения эталонных значений и блок 5 сравнения, выход которого соединен с вторым входам блока 3 синхронизации, вход запуска которого соединен с управляющим входом устройства, а первый выход 55 блока 3 синхронизации является выходом признака окончания работы устройства, причем с второго по пятый выходы блока 3 синхронизаций соединены соответственно с первого по четвертый управляющими вхоНа этом вычисления заканчиваются, так как количество операций n = 3. Результат не равен (1 ... 1), поэтому исходный вектор х не 15 принадлежит классу линейных арифметических полиноминальных форм. В этом легка убедиться, выполнив над ним преобразование Фурье в коньюнктивном базисе K2n (n.=

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

Блок 1 предварительной обработки обеспеч(ивает передачу вектора значений x=

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

Блок 3 синхронизации предназначен для формирования сигналов, управляющих работой устройства.

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

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

Блок 1 предварительной обработки, блок 2 булевого дифференцирования и блок

3 синхронизации имеют особенности схемотехнических решений и функционирования.

Блок 1 предварительной обработки (фиг. 2) содержит 2 сумматоров 11(1 = 1, 2 ) по модулю два, вторые входы которого соединены между собой и подключены к первому входу первого сумматора 11 по модулю два; первый вход t-го сумматора по модулю два является первым входом блока 1 предварительной обработки.

Блок 1 предварительной обработки работает следующим образом. При поступлении на его вход элементов вектора значений (0) (1) (2n-1) т

x = (х()х()...х()) булевой функции и пере-. менных осуществляется анализ значений первого элемента х . При этом возможны о два случая.

В первом случае, когда x = О, на сум(о) маторах по модулю два с 11 по 12" выполняется сложение па модулю два логического нуля со значениями элементов вектора х. В

1756879 результате на выход блока 1 предваритель- налу на втором входе (входе разрешения ной обработки передаются все элементы записи). Сдвиг содержимого в сторону младвектора без изменений.... ших разрядов выполняется по сигналу на

Во втором случае, когда x ) = 1, на сум- третьем входе (входе управления сдвигом). маторах по модулю два с 1 по 12л выпол- 5 Блок 2 бУлевого ДиффеРенЦиРованиЯ няется суммирование по модулю два работает следующим. образом. Предварилогической единицы со значениями элемен- тельно во все Разряды первого 8 и второго тов вектора В результате на выход блока 9 РегистРов записываютСЯ нУли. С четверто1 предварительной обработки передаются го инфоРмационного входа блока по тРактУ инверсные значения элементов вектора х 10 первый вход — выход коммутатора 6 (на

-(0)-(1) -(2n-1) т

=(х х ...x ). третьем — уп ра вл я ющем — входе коммутато Уаким образом, блок 1 предваритель- Ра 6 — низкий логический УРовень сигнала) в ной обработки осуществляет передачу век- первый Регистр 8 осущЕствляется запись котора х с входа на выход в прямом или в да анализиРУЕмого вектора х"или х, момент инверсном коде в зависимости оттого нуле- 15 вр - (ф 5) вое или единичное значение соответствен- В момент времени tj + Лтз по сигналу но имеет первый элемент вектора х . на втором управляющем входе блока 2 булеБлок 2 булевого дифференцирования (фиг вого дифференцирования осуществляется

3) содержит коммутатор 6, узел 7 суммато- перезапись кода вектбраМ из первого региров по модулю два, первый 8 и второй 9 20 стра 8 но второй регистр 9. В момент времерегистры, при этом пятый (информацион- ни t1 + Лт2 по сигналу на третьем ный) вход блока соединен с первым инфор- управляющем входе блока 2 выполняется мационным входом коммутатора 6,.второй сдвиг на один Разряд в сторону младших информационный вход которого соединен с содержимого второго регистра 9, На выходе выходами блока и узла 7 сумматоров по мо 25 Узла 7 сУмматоРов по модУлю два фоРмиРУдулю два, первый и второй информацион- . ется результат д х/ дх. ные входы которого соединены с выходами Далее функционирование блока 2 булепервого 8 и второго 9 регистров соответст- вого д фференц рованиЯ заключаетсЯ в завенно, вторые входы (входы разрешения за- писи полученного результата в первый писи) которых соединены с первым и 30 регистр 8 (момент времени 1з), перезаписи вторым управляющими входами блока coDT- его из первого регистра 8(t3+ At3) во второй ветственно, третий управляющий вход кото» регистр 9, сдвиге на один разряд в сторону рого соединен с третьим входом (входом младших содержимого второго регистра 9 управления сдвигом) второго регистра, пер- (момент времени тз + Лт2) и поразрядном вый (информационный) вход которого сое- 35 суммировании по модулю два содержимых динен с выходом первого регистра 8, первого 8 и второго 9 регистров и узле 7 первый (информационный) вход которого сумматоров по модулю два; Тем самым форсоединен с выходом коммутатора 6, третий мируется результат вида д(д х/ дх)/дх. Уп(управляющий) вход которого соединен с равляющие сигналы записи в первый четвертым управляющим входом блока; 40 регистр 8, записи во второй регистр 9, сдвиг

Коммутатор 6 предназначен для пере- содержимого второго регйстра 9 на один дачи информации с первого или второго ин- или несколько разрядов соответственно на формационных входов на выход первом, втором и третьем входах блока 2 соответственно при низком или высоком rto- булевого дифференцирования повторяются гическом уровне сигнала на его третьем yri- 45 циклически, равляющем входе. Блок 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 элена первый (информационный) вход по сиг- - ментов задержки; первым входом второго

1756879

20 элемента И и выходом генератора 10 импульсов, вход пуска которого соединен с входом запуска блока, вход признака останова которого соединен с первым входом третьего элемента И 21, второй вход которого соединен с выходом элемента HE 23, выход третьего элемента И 21 соединен с входом второго триггера 12 и с первым входом элемента ИЛИ 22, второй вход которого соединен с выходом перепалнейия счетчика

14, выход второго триггерз 12 соединен с первым выходом блока, выход элемента

ИЛИ 22 соединен с входом останова генератора импульсов, выход первого элемента задержки 16 соединен с входом синхронизации первого триггера 11, выход которого соединен с вторым входом второго элемента И 20, выход которого соединен с входом третьего элемента 18 задер>кки и вторым выходом блока, третий выход которого соединен с входом третьего триггера

13 и выходом третьего элемента 18 задержки, выход второго элемента 17 задер>кки соединен с вторым входом первого элемента И 19, выход которого соединен с четвертым выходом блока, выход третьего триггера 13 соединен с пятым выходом блока.

Генератор 10 импульсов предназначен для формирования регулярной последовате>тьности импульсов и имеет первый вход пуска и второй вход останова.

Первый триггер 11 предназначен для управления работой второго элемента И 20 с целью формирования импульсов на первом и втором выходах блока 5 синхронизации. В нулевом состоянии триггер 11 блокирует формирование импульсов на первом и втором выходах блока 5 синхронизации (фиг. 5). Конструктивно это синхронный

D-триггер с установкой и сбросом (например, K155TM2), причем на входы 0 и 8 постоянно подаются уровни логического нуля и единицы соответственно, Первым входом (входом установки в единицу) пеавога триггера 11 является вход установки S, а вторым входом — вход синхронизации С. Начальное состояние первого триггера 11-единичное.

Второй 12 и третий 13 триггеры предназначены для формирования сигналов на четвертом и пятом выходах блока 3 синхронизациии соответственно. Конструктивна это D"Tðèããt ðû, которые по фронту на их входе устанавливаются в едийичное состоя- ние. Исходное состояние их — нулевое.

Счетчик 14 предназначен для регламентирования работы устройства. Конструктивно он представляет. собой и-разрядный счетчик суммирующего типа со счетным входом, (и+1)-й выход счетчика 14 — выход переполнения. Начальное состояние его — нулевое.

Мультиплексор 15 предназначен для формирования на своем выходе сигнала, управляющего работой первого триггера 11, третьего элемента И 21 и элемента НЕ 23.

Мультиплексор 15 формирует на своем выходе сигнал логического нуля при следую10

2, 4„...4+, (2р+ 1). Во всех остальных

20

35 путем выполнения операции коньюнкции.

Элемент ИЛИ 22 предназначен для логического анализа входных сигналов посредством выполнения над ними операции

55 щих значениях на своих адресных входах: О, п — 1 р — 1 случаях на выходе мультиплексора 15 — сигнал логической единицы (таблица ).

Режим работы мультиплексора 15, имеющего и адресных и 2" информационных входов, обеспечивается тем, что адресные входы с первого по и-й подключаются к соответствующим выходам (с первого по и-й) счетчика 14. На информационные входы мультиплексора 15 подключаются потенциалы логических уровней в соответствии с таблицей, Конструктивно разрядность мультиплексора 15 (2" - 1) может.быть достигнута использованием каскадного соединения мультиплексоров, Первый 16, второй 17 и третий 18 элементы задержки обеспечивают задер>кку входного сигнала на время Лт1, A t2 и Лтз соответственно.

Первый 19, второй 20 и третий 21 элементы И предназначены для логического анализа поступающих на входы сигналов дизъюн кции.

Функции блока 3 синхронизации заключаются в формировании сигналов управления работой блока 2 булевого дифференцирования. Предварительно тригrep 11 устанавливаются в состояние логической единицы, второй 12 и третий 13 триггеры — в состояние логического нуля, а счетчик 14 — в нулевое состояние. Запуск блока 3 синхронизации осуществляется по сигналу на входе пуска генератора 10 импульсов. На первом выходе блока 2 синхронизации формируется признак результата распознавания, на втором и третьем выходах формируются соответственно сигналы записи в первый 8 и второй 9 регистры блока

2 булевого дифференцирования, на четвертом выходе 3 синхронизации формируется сигнал сдвига ва втором регистре 9, на пятом выходе формируется сигнал, регламентирующий функционировайие коммутатора

6. Количество сигналов сдвига r, формиру1756879 емых на четвертом выходе блока 3 синхро- та И 19. На второй вход первого элемента И низации, определяется по значению кода на 19 в момент времени tq + Ь tg с выхода втовыходах счетчика 14. Таким образом, сигна- . рого элемента 17 задержки (фиг. 5} поступалы записи и сдвига, формируемые на вто- ет импульсный сигнал, который передается ром, третьем и четвертом выходах блока 3 5 с выхода первого элемента И 19 на четверсинхронизации, образуют группу управляю- тый выход блока 3 синхронизации. щих сигналов, регламентирующих функцио- Кроме того, высокий логический уронирование блока 2 булевого вень сигнала с выхода мультиплексора 15 дифференцирования втечение выполнения передается на вход установки в единицу операции булевого дифференцирования с 10 первого триггера 11, при этом сигнал на:-. параметром t. выходе первого триггера 11 не изменяется.

Рассмотрим формирование первой В момент времени t1+ Лt> на вход синхрогруппы управляющих сигналов на выходах низации первого триггера 11 поступает имблока 3 синхронизации. Эти сигналы обес- пульсный сигнал с выхода первого элемента печивают управление функционированием 15 16 задержки, и триггер 11 переключается в блока 2 булевого дифференцирования в те- состояние логического нуля. В результате в чение выполнения операции булевого диф- момент времени tg на второй выход блока 3 ференцирования с параметром т= 1. Это синхронизации импульсный сигнал не пообусловлено следующей работой элементов . ступает. блока 3 синхронизации.. 20 . Таким образом, в моменты времени t1—

В момент времени to (фиг. 5) осуществ- tz на выходах блока синхронизации формиляется запуск устройства. В результате им- руется первая группа управляющих сигнапульсный сигнал, формируемый на выходе лов: в момент времени 31 — на втором генератора 10; поступает на входы счетчика выходе; ц + Лтз — на третьем выходе, в

14, первого 16, второго 17 элементов задер- 25 момент времени 11+ Л з — сигнал сдвига на жкии второго элемента И 20, с выхода кото- четвертом выходе (импульсные сигналы) и рого импульсный сигнал передается на на пятом выходе формируется высокий ловторой выход блока 3 синхронизации (на гический уровень потенциала. втором входе второго элемента И 20 — высо- В момент времени tzсчетчик 14 перехокий логический уровень сигнала, поступаю- 30 дит из состояния 0...01 в состояние 0...010, щий с выхода первого триггера 11 (от и на выходе мультиплексора 15формируетнаходится в состоянии логической едини-. ся низкий логический уровень сигнала, котоцы). Кроме того, импульсный сигнал с выхо- рый вызывает следующие измЕнения в да второго элемента И 20 поступает на вход схеме: первый триггер 11 устанавливается в третьего элемента 18 задержки. В момент 35 состояние логической единицы, на выходе времени At>+ Лтз(Л з — время задержки первого элемента И 19 формируется низкий на третьем элементе 18 задержки) импульс-,- логический уровень сигнала, который блокиный сигнал с выхода третьего элемента 18 рует формирование импульсов на четвертом задержки передается натретий выходблока выходе блока 3 синхронизации (фиг, 5). На

3 синхронизации, а также на вход третьего 40 выходе элемента НЕ 23 формируется высотриггера 13, который устанавливается в со- кий логический уровень сигнала, который стояние логической единицы, и на пятый передаетсянавторойвходтретьегоэлеменвыходблока3синхронизациипоступаетвы- та И 21, В результате на выход третьего сокий логический уровень сигнала (он со- элемента И 21 передается сигнал, поступахраняется на пятом выходе блока 5 45 ющий на первый вход третьего элемента И синхронизации до окончания выполнения 21 с входа признака останова блока 3 синхбулевого дифференцирования). На первом ронизации (это сигнал-признак результата выходе блока 3 синхронизации сохраняется распознавания с выхода блока 5 сравнения). низкий логический уровень сигнала. Рас- При этом возможны два случая, когда присмотрим формирование сигнала на четвер- 50 знак сравнения равен нулю, и когда признак том выходе блока 3 синхронизации. По сравненияравенединице. Рассмотримперимпульсному сигналу, формируемому на вы- . вый случай, т.е, случай, когда на первый вход ходегенератора10импульсоввмоментвре- третьего элемента И 21 поступает низкий мени t> (фиг. 5), счетчик 14 переходит. из. логический уровеньсигнала. Тогда на выхосостояния 0...0 в состояние 0...01, Код О.,;01 55 де третьего элемента И 21 сохраняется низс выхода счетчика 14 передается на входы с кий логический уровень сигнала. В первого по и-й мультиплексора 15, на выхо- результате блок 3 синхронизации подготовде которого формируется высокий логиче- лен к формированию следующей первой ский уровень сигнала (таблица), который группы управляющихсигналов. передается на первый вход первого элемен1756879

В моменты времени тз, тз+ Л ta, to+ h, t2 на выходах блока 3 синхронизации, втором, третьем и четвертом выходах соответственно формируются сигналы из второй группы управляющих сигналов (эта группа сигналов обеспечивает управление функционированием блока 2 булевого дифференцирования при дифференцировании с параметром т = 1). Формирование второй, группы управляющих сигналов аналогично 10 формированию первой группы управляющих сигналов, однако третий триггер 13 в этом случае не изменяет своего состояния (состояние логической единицы).

Рассмотрим второй случай, когда на 15 первый вход третьего элемента И 21 поступает высокий логический уровень сигнала (признак распознавания (момент времени

t4, фиг. 5). Этот сигнал поступает с первого входа на выход третьего элемента И 21 (на 20 втором входе элемента И 21 — высокий логический уровень сигнала, который поступает с выхода элемента HE 23, на входе которого — низкий логический уровень сигнала с выхода мультиплексора 15). С выхода третьего 25 элемента И 21 высокий логический уровень сигнала передается на первый вход элемента ИЛИ 22 и далее — на вход останова генератора 10 импульсов. Таким образом, функционирование блока 3 синхронизации 30 завершается.

Рассмотрим также случай, когда на первом входе третьего элемента И 21 все время сохраняется низкий уровень сигнала, т.е. признак результата распознавания за 2" 35 тактов не сформирован (функция не линейна). В этом случае в момент времени t6 счетчик 14 переходит в состояние 1...1 (2" - 1). В момент времени tg на (и+1)-м выходе счетчи-: ка 14 формируется сигнал переполнения 40 (высокий логический уровень напряжения).

Этот сигнал поступает на второй вход элемента ИЛИ 22 и далее с его выхода — на вход останова генератора 10 импульсов. При этом на первом выходе блока синхрониза- 45 ции формируется низкий логический уровень сигнала (признак отрицательного результата распознавания).

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

На первом этапе работы блок 1 предварительной обработки выполняет анализ элемента х вектора х = (х х " .,;х " ), Ес- 55 ли х =О, то на выход блока 1 предвэритель(о ной обработки передается вектоо х без изменений. В противном случае (х - 1) на его выход передается инверсное значение векторами т.е х =(х х )...х " ) .

На втором этапе выполняется однократное дифференцирование вектора х или х блоком 2 дифференцирования в соответствии с математической моделью (3) при т = 1.

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

На третьем этапе вычислений блок 5 сравнения осуществляет анализ на совпадение вектора д х/ д х на первом входе с эталонным вектором х = (1...1), передаваемым на второй вход с выхода блока 4 хранения эталонных значений. В случае несовпадения векторов д х/д х и х» на выходе блока 5 сравнения сохраняется низкий логический .уровень сигнала (признак продолжения логической обработки). В случае совпадения векторов д x/ä х и4 на выходе блока 5 сравнения формируется сигнал логической единицы — признак принадлежности распознаваемого вектора х классу линейных арифметических форм.

Количество этапов функционирования устройства определяется структурой анализируемого вектора х, На фиг. 6 представлена схема вычислительного процесса распознавания на линейность вектора х = (00001111) и показано изменение на каждом шаге вычислейий содержимого первого 8 и второго 9 регистров блока.2 булевого дифференцирования 2. Результат суммирования по модулю два содержимого первого 8 и второго 9 регистров на каждом шаге поступает на первый вход блока 5 сравнения и на второй вход первого регистра 8, затем содержимое первого регистра 8 перезаписывается во второй регистр 9. Содержимое последнего сдвигается на т разрядов, а именно на 1, 1 и 2 разряда в соответствии с математической моделью (3), Процесс вычисления заканчивается на тре ;ьем шаге, когда результат вида д(д (дх/ дх)/ дх)/ д (2 х) оказывается равным эталон ному векторухз = (11111111) .

Таким образом; предлагаемое изобретение характеризуетея расширением класса решаемых задач по сравнению с аналогами и прототипом, что обеспечивает оперативный анализ принадлежности заданной булевой функции классу линейных арифметических полиноминальных форм; простотой технических решений и технологичностью изготовления; повышением быстродействия анэлиза..1 756879

21 но, третий управляющий вход которого соединен с входом управления сдвигом второго регистра, информационный вход которого соединен с выходом первого регистра, инФормула изобретения

1. Устройство для распознаванйя на лиформационный вход которого соединен с нейность булевых функций, содержащее 5 выходом коммутатора; управляющий вход которого соединен с четвертым управляющим входом блока, "

3, Устройство no n..1, о т л и ч а ю щ е еблок синхронизации и блок предваритель - ной обработки, причем управляющий вход устройства соединен с входом запуска блока синхронизации, информационнйй вход с я тем, что блок синхронизации содержит устройства соединен с входом блока, преД- 10 мента задержки, три элемента И, элемент признака окончания работы устройства, отИЛИ и элемент НЕ, вход которого соединен л и ч а ю щ е е с я тем, что. с целью расшис входом установки в "1" первого триггера рения класса решаемых задач за счет воз- 15 можности распознавания принадлежности первым входом первого элемента И и выхобулевой функции классу линейных арифме- дом мультиплекСора, входы которого соедитическихполиноминальныхформ,устройст- нены с выходами и разрядов счетчика, во . содержит блок булевого . счетный вход которого соединен с входами дифференцирования, блок хранения эта- 2() первогоивторогоэлементовзадержки, перлонных значений и блок сравнения, при вым входом второго элемента И и выходом этом выход блока предварительной обра- генератора импульсов, вход пуска которого ботки соединен с информационным входом соединен с входом запуска блока, вход приблока булевого дифференцирования, выход знака останова которого соединен с первым которого соедийен с первым входом блока 25 входом третьего элемента И, второй вход сравнения, второй вход которого Соедйнен которого соединей с выходом элемента НЕ, с выходом блока храйения эталонных значе- выход третьего элемента И соединен с входом второго триггера и первым входом элений, выход блока сравнения соединен с вхомента ИЛИ, второй вход которого соединен дом признака останова блока синхронизации. с второго по пятый выходы 3() с выходом переполнения счетчика, выход которого соединены с первого почетвертый второго триггера соединен с первым выходом блока, выход элемента ИЛИ соединен с управляющие входы соответственно блока булевого дифференцирования.

2. Устройство по и. 1, отл и ч а ю ще евходом останова генератора импульсов, выход первого элемента задержки соединен с с я тем, что блок булевого дифференциро- 35 вания содержит коммутатор, узел суммирования по модулю два и два регистра, при этом информационный вход блока соединен входом синхронизации первого триггера, выход которого соединен с вторым входом второго элемента И, выход которого соединен с входом третьего элемента задержки и с первым информационным входом комму- вторым выходом блока, третий выход кототатора, второй информационный вход кото- 4О рого соединен с входом третьего триггера и рого соединен с выходами блока и узла выходом третьего элемента задержки, выход второго"элемента задержки Соединен с сумматоров по модулю два, первый и второй информационные входы которого соедине- вторым входом первого элемента И. выход ныс выходами первого и второго. регистров -которого соединен с четвертым выходом соответственно, входы разрешения записи 45 блока, выход третьего триггера соединен с которых соединены с первым и вторым yn-" пятым выходом блока. равляющими входами блока соответствен-варительной обработки, первый выход бло- генератор импульсов, три триггера, и-разка синхронизации соединен с выходом рядный счетчик, мультиплексор, три эле1756879

24

Продолжение таблицы

1756879

Г

Ухо/pg ю дщ;/

Фиг. 4

Жиlяу.

ЬдР уай ям а .лги/

АюЬ (лунгу

lipped ююулд джюат фыр су

/йл жю

NurgAh4 уиггу

1756879

Фиг,б

Составитель Д. Кузьмицкий

Техред М,Моргентал Корректор Е.Папп

Редактор Л, Гратилло

Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101

Заказ 3088 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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