Устройство для распознавания на линейность булевых функций Советский патент 1992 года по МПК G06F7/00 

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

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

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

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

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

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

Частично удается решить поставленную задачу с помощью блока определения

свойств несамодвойственности. Но к линейным арифметическим полиномам относятся не все самодвойственные функции, а только определенный их класс.

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

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

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

0 обработки, первый выход блока синхронизации соединен с выходом признака окончания работы устройства, введены блок булевого дифференцирования, блок сравнения и блок хранения эталонных значений,

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

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

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

рого регистра, информационный вход которого соединен с выходом первого регистра, информационный вход которого соединен с выходом коммутатора, управляющий вход которого соединен с четвертым управляю- щим входом блока. Блок синхронизации содержит генератор импульсов, три триггера, n-разрядный счетчик, мультиплексор, три элемента задержки, три элемента И, элемент ИЛИ и элемент НЕ, вход которого со- единен с входом установки в единицу первого триггера, первым входом первого элемента И и выходом мультиплексора, ЁХО- ды которого соединены с выходами п разрядов счетчика, счетный вход которого соединен с входами первого и второго элементов задержки, первым входом второго элемента И и выходом генератора импульсов, вход пуска которого соединен с входом запуска блока, вход признака останова которого соединен с первым входом третьего элемента И, второй вход которого соединен с выходом элемента ИЛИ, выход третьего элемента И соединен с входом второго триггера и с первым входом элемента ИЛИ, вто- рой вход которого соединен с выходом переполнения счетчика, выход второго триггера соединен с первым выходом блока, выход элемента ИЛИ соединен с входом останова генератора импульсов, выход пер- вого элемента задержки соединен с входом синхронизации первого триггера, выход которого соединен с вторым входом второго элемента И, выход которого соединен с входом третьего элемента задержки и вторым выходом блока, третий выход которого соединен с входом третьего триггера и выходом третьего элемента задержки, выход второго элемента задержки соединен с вторым входом первого элемента И, выход которого соединен с четвертым выходом блока, выход третьего триггера соединен с пятым выходом блока.

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

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

Любая булевая функция f(x)n переменных xi,x2хп может быть представлена в

так называемой арифметической полиноминальной форме, которая имеет аналитическое представление вида

p(x)P(0)+P(1)xn+p(2)xn-i+p(3)xn-ixn+ . .. +

, (2П О

4-рХ1... хп

2п-1

2 p(DxV...,

I 0

(1)

,0),

где pv/ б z, 2 - множество целых чисел, таких, что р(х)с (0,1) на любом наборе переменных и при этом можно однозначно получить на упорядоченных наборах переменных функции f(x) вектор х (столбец значений обычно таблицы истинности); lj-J-й разряд двоичного представления параметра 1 (нумерация со старших);

XI1 XI,1

х,.

Например, функция, заданная в совершенной дизъюнктивной номинальной форме

f(x) Х1Х2 V )1Х2,

имеет арифметическую полиноминальную форму вида

р(х) Х1 + Х2 - 2X1X2.

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

Действительно

11:0:

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

РМ

+ p, + ...+P(n)xi.

прави(2)

10

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

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

В матричном виде оператор параметрического дифференцирования по координате X вектора значений х булевой функции f(x) имеет вид

fer Л/ф ST (mod 2), (3)

Лтх)

где х (0...0, 0...01 1...1) - координата

дифференцирования с отсчетами, соответствующими упорядоченным наборам переменных xiх„; те. 2Р, ( р 0,0.1,2,...п-1) параметр дифференцирования; М-,// - матрица размерности 2 х 2П (п - количество переменных), формируемая по рекуррентному правилу

.Mji-- (d2),

I 1

м

О)

1 1

(4)

1 1

Пусть, например, требуется найти производную вектора значений

- О 0 0 1 0 1 1 1 ,

где т - символ транспортирования булевой функции трех переменных с параметром т

15

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

эт

.W35

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

...ir. €2P, р 0,0,1 ...п-1,

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

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

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

х 0 0 1 10 0 1 1 f.

Первый шаг вычислений заключается в анализе элемента х™ вектора хТ Если он равен нулю (а в данном случае х 0 0), то выполняется следующий шаг вычислений. В противном случае, т.е. если х 1, осуществляется инвертирование всех элементов хТ

На втором шаге вычислений выполняется дифференцирование вектора значений 3 по координате X с параметром г- 1 согласно выражению (3)

О 1 О 1 О

1 о 1

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

На третьем шаге реализуется операция дифференцирования вектора д х/ д х, полученного на предыдущем шаге вычислений

Э/9 м

а№гм

д

(1)

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

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

10 L

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

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

001 1 .

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

Повторим эту процедуру при г 1 еще

А Ш) - М У

j9 дх

( Н

45

50

1

1 1 1 1 1 1 1 1 1 1 1 1 1

55

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

Л/э /ам /Эл

(a7/; (V

(L(

0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 0 1 1 О

1

На этом вычисления заканчиваются, так как количество операций п 3. Результат не равен 1... , поэтому исходный вектор не принадлежит классу линейных арифметических полиноминальных форм. В этом легко убедиться, выполнив над ним преобразование Фурье в конъюнктивном базисе ten (п 3)

Р К2ЗХ:

00000 00000 00000

10000 01000

0-1 100

0-1010

1 1-1-1 1

о 1 о

-1

1

-1

-1

0.

т.е. р(х) хз - Х2хз + xi - Х1хз - xiX2 не есть линейный арифметический полином.

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

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

устройства.

Блок 1 предварительной обработки обеспечивает передачу вектора значений ЗГ х ... с входа на выход без изменений в случае, если элемент О,

или в инвертированном виде, если х 1.

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

математической моделью.

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

Блок 4 хранения эталонных значений

предназначен для хранения кода размерности 2П вида 1.... Конструктивно он выполнен в виде жесткого соединения разрядных шин выхода блока с второй по 2п-ю с шиной высокого логического уровня напряжения

(логической единицы).

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

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

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

Блок 1 предварительной обработки ра0 ботает следующим образом. При поступле- мм на его ВХОд элементов вектора значений Г Do°V1 ...x(2n Y булевой функции п переменных осуществляется анализ значений первого элемента При этом возможны

5 два случая.

В первом случае, когда х 0, на сумматорах по модулю два с 1 по 12П выполняется сложение по модулю два логического нуля со значениями элементов вектора 3 В

результате на выход блока 1 предварительной обработки передаются все элементы вектора х без изменений.

Во втором случае, когда х™ 1, на сумматорах по модулю два с 1j по 12П выполняется суммирование по модулю два логической единицы со значениями элементов вектора Ј В результате на выход блока 1 предварительной обработки передаются инверсные значения элементов вектора х 4х(0)Д..х 2п-15 т.

Таким образом, блок 1 предварительной обработки осуществляет передачу вектора х с входа на выход в прямом или в инверсном коде в зависимости оттого нулевое или единичное значение соответственно имеет первый элемент вектора х Блок 2 булевого дифференцирования (фиг. 3) содержит коммутатор 6, узел 7 сумматоров по модулю два, первый 8 и второй 9 регистры, при этом пятый (информационный) вход блока соединен с первым информационным входом коммутатора В, второй информационный вход которого соединен с выходами блока и узла 7 сумматоров по модулю два, первый и второй информационные входы которого соединены с выходами первого 8 и второго 9 регистров соответственно, вторые входы (входы разрешения записи) которых соединены с первым и вторым управляющими входами блока соответственно, третий управляющий вход которого соединен с третьим входом (входом управления сдвигом) второго регистра, первый (информационный) вход которого соединен с выходом первого регистра 8, первый (информационный) вход которого соединен с выходом коммутатора б, третий (управляющий) вход которого соединен с четвертым управляющим входом блока.

Коммутатор 6 предназначен для передачи информации с первого или второго ин- формационных входов на выход соответственно при низком или высоком Логическом уровне сигнала на его третьем управляющем входе.

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

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

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

работает следующим образом. Предварительно во все разряды первого 8 и второго 9 регистров записываются нули. С четвертого информационного входа блока по тракту 10 первый вход - выход коммутатора 6 (на третьем - управляющем - входе коммутатора 6 - низкий логический уровень сигнала) в первый регистр 8 осуществляется запись кода анализируемого вектораЗГили х, момент 15 времени ti (фиг. 5).

В момент времени ti Ata по сигналу на втором управляющем входе блока 2 булевого дифференцирования осуществляется перезапись кода вектора Гиз первого реги- 0 стра 8 во второй регистр 9. В момент времени ti + At2 по сигналу на третьем управляющем входе блока 2 выполняется сдвиг на один разряд в сторону младших содержимого второго регистра 9. На выходе 5 узла 7 сумматоров по модулю два формируется результат д )7 дх.

Далее функционирование блока 2 булевого дифференцирования заключается в записи полученного результата в первый 0 регистр 8 (момент времени ta), перезаписи его из первого регистра 8 (ta + Ata) во второй регистр 9, сдвиге на один разряд в сторону младших содержимого второго регистра 9 (момент времени ta + Ata) и поразрядном 5 суммировании по модулю два содержимых первого 8 и второго 9 регистров и узле 7 сумматоров по модулю два. Тем самым формируется результат вида д( Эх/йх)/Эх. Управляющие сигналы записи в первый 0 регистр 8, записи во второй регистр 9, сдвиг содержимого второго регистра 9 на один или несколько разрядов соответственно на первом, втором и третьем входах блока 2 булевого дифференцирования повторяются 5 циклически.

Блок 3 синхронизации (фиг. 5) содержит генератор 10 импульсов, первый 11, второй 12 и третий 13 триггеры, счетчик 14, мультиплексор 15, первый 16, второй 17, третий 18 0 элементы задержки, первый 19, второй 20 и третий 21 элементы И, элемент ИЛИ 22 и элемент НЕ 23, вход которого соединен с входом установки в единицу первого триггера 11, первым входом первого элемента И 5 19 и выходом мультиплексора 15, входы которого соединены с выходами п разрядов счетчика 14, счетный вход которого соединен с входами первого 16 и второго 17 элементов задержки, первым входом второго

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). Конструктивно это синхронный D-триггер С установкой и сбросом ( мер, К155ТМ2), причем на входы D и R постоянно подаются уровни логического нуля и единицы соответственно. Первым входом (входом установки в единицу) первого триггера 11 является вход установки S, а вторым входом - вход синхронизации С. Начальное состояние первого триггера 11 -единичное. Второй 12 и третий 13 триггеры предназначены для формирования сигналов на четвертом и пятом выходах блока 3 синхро- низациии соответственно. Конструктивно это D-триггеры, которые по фронту на их входе устанавливаются в единичное состояние. Исходное состояние их - нулевое,

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

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

0п-1

2, 44 + 2, (2Р + 1). Во всех остальных

р 1

случаях на выходе мультиплексора 15 - сигнал логической единицы (таблица ).

5 Режим работы мультиплексора 15, имеющего п адресных и 2П информационных входов, обеспечивается тем, что адресные входы с первого по n-й подключаются к соответствующим выходам (с первого по п-й)

0 счетчика 14. На информационные входы мультиплексора 15 подключаются потенциалы логических уровней в соответствии с таблицей.

Конструктивно разрядность мульти5 плексора 15 (2П - 1) может быть достигнута использованием каскадного соединения мультиплексоров.

Первый 16, второй 17 и третий 18 элементы задержки обеспечивают задержку

о входного сигнала на время Ati, At2nAts соответственно.

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

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

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

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

5 2 булевого дифференцирования, на четвертом выходе 3 синхронизации формируется сигнал сдвига во втором регистре 9, на пятом выходе формируется сигнал, регламентирующий функционирование коммутатора 6. Количество сигналов сдвига т, формируемых на четвертом выходе блока 3 синхронизации, определяется по значению кода на выходах счетчика 14. Таким образом, сигналы записи и сдвига, формируемые на втором, третьем и четвертом выходах блока 3 синхронизации,образуют группууправляющих сигналов, регламентирующих функцио- нирование блока 2 булевого дифференцирования в течение выполнения операции булевого дифференцирования с параметром г.

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

В момент времени to (фиг. 5) осуществляется запуск устройства. В результате импульсный сигнал, формируемый на выходе генератора 10, поступает на входы счетчика 14, первого 16. второго 17 элементов задержки и второго элемента И 20, с выхода которого импульсный сигнал передается на второй выход блока 3 синхронизации (на втором входе второго элемента И 20 - высокий логический уровень сигнала, поступающий с выхода первого триггера 11 (от находится в состоянии логической единицы). Кроме того, импульсный сигнал с выхода второго элемента И 20 поступает на вход третьего элемента 18 задержки. В момент времени Ati + Ata(A т,з- время задержки на третьем элементе 18 задержки) импульсный сигнал с выхода третьего элемента 18 задержки передается на третий выход блока 3 синхронизации, а также на вход третьего триггера 13. который устанавливается в состояние логической единицы, и на пятый выход блока 3 синхронизации поступает высокий логический уровень сигнала (он сохраняется на пятом выходе блока 5 синхронизации до окончания выполнения булевого дифференцирования). На первом выходе блока 3 синхронизации сохраняется низкий логический уровень сигнала. Рассмотрим формирование сигнала на четвертом выходе блока 3 синхронизации. По импульсному сигналу, формируемому на выходе генератора 10 импульсов в момент времени ti (фиг. 5), счетчик 14 переходит из состояния 0...0 в состояние 0...01, Код 0...01 с выхода счетчика 14 передается на входы с первого по n-й мультиплексора 15, на выходе которого формируется высокий логический уровень сигнала (таблица), который передается на первый вход первого элемента И 19, На второй вход первого элемента И 19 в момент времени ti + A t2 с выхода второго элемента 17 задержки (фиг. 5) поступает импульсный сигнал, который передается 5 с выхода первого элемента И 19 на четвертый выход блока 3 синхронизации.

Кроме того, высокий логический уровень сигнала с выхода мультиплексора 15 передается на вход установки в единицу 10 первого триггера 11, при этом сигнал на выходе первого триггера 11 не изменяется. В момент времени ti + Ati на вход синхронизации первого триггера 11 поступает импульсный сигнал с выхода первого элемента

15 16 задержки, и триггер 11 переключается в состояние логического нуля. В результате в момент времени t2 на второй выход блока 3 синхронизации импульсный сигнал не поступает.

0 Таким образом, в моменты времени ti - t2 на выходах блока синхронизации формируется первая группа управляющих сигналов: в момент времени ti - на втором выходе; ti + At3 - на третьем выходе, в

5 момент времени ti + A t3 сигнал сдвига на четвертом выходе (импульсные сигналы) и на пятом выходе формируется высокий логический уровень потенциала.

В момент времени t2 счетчик 14 перехо0 дит из состояния 0...01 в состояние 0,..010, и на выходе мультиплексора 15 формируется низкий логический уровень сигнала, который вызывает следующие изменения в схеме: первый триггер 11 устанавливается в

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

- логический уровень сигнала, который блокирует формирование импульсов на четвер гом выходе блока 3 синхронизации (фиг. 5). На

0 выходе элемента НЕ 23 формируется высокий логический уровень сигнала, который передается на второй вход третьего элемента И 21. В результате на выход третьего элемента И 21 передается сигнал, поступа5 ющий на первый вход третьего элемента И 21 с входа признака останова блока 3 синхронизации (это сигнал-признак результата распознавания с выхода блока 5 сравнения). При этом возможны два случая, когда при0 знак сравнения равен нулю, и когда признак сравнения равен единице. Рассмотрим первый случай, т.е. случай, когда на первый вход третьего элемента И 21 поступает низкий логический уровень сигнала. Тогда на выхо5 де третьего элемента И 21 сохраняется низкий логический уровень сигнала. В результате блок 3 синхронизации подготовлен к формированию следующей первой группы управляющих сигналов.

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

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

Рассмотрим также случай, когда на первом входе третьего элемента И 21 все время сохраняется низкий уровень сигнала, т.е. признак результата распознавания за 2П тактов не сформирован (функция не линейна). В этом случае в момент времени т.б счетчик 14 переходит в состояние 1...1 (211 -1). В момент времени те на (п+1)-м выходе счетчика 14 формируется сигнал переполнения (высокий логический уровень напряжения). Этот сигнал поступает на второй вход элемента ИЛИ 22 и далее с его выхода - на вход останова генератора 10 импульсов. При этом на первом выходе блока синхрониза- ции формируется низкий логический уровень сигнала (признак отрицательного результата распознавания).

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

На первом этапе работы блок 1 предварительной обработки выполняет анализ элемента х(0} вектора - х{0)х(1).,.х(2п 1)т. Ее- , тона выход блока 1 предварительной обработки передается вектор х без изменений. В противном случае (х 1) на

его выход передается инверсное значение вектора т.е. х «..

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

На третьем этапе вычислений блок 5 сравнения осуществляет анализ на совпадение вектора dlt/ д х на первом входе с эталонным вектором хэ 1..., передаваемым на второй вход с выхода блока 4 хранения эталонных значений. В случае несовпадения векторов д х/dx выходе блока 5 сравнения сохраняется низкий логический уровень сигнала (признак продолжения логической обработки). В случае совпадения векторов д х/dx и & на выходе блока 5 сравнения формируется сигнал логической единицы - признак принадлежности распознаваемого вектора 5t классу линейных арифметических форм.

Количество этапов функционирования устройства определяется структурой анализируемого вектора х

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

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

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

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

23

Вмё

Iff fa

Xwtfywmqp

2

Mf

ы/

2-uj№tuyqP

SxptfZ

SxtfJ

1756879

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

BwffJ

Фаг. 2.

J-U/№ff/%9

7

&/w#

&РЯ МЈЩ№#

n

WAK

Фиг.З

8wj за/уду

Лг flt//WffM№y

l//i(Jf i

faVWfffWWM/ {.

йхеЯяризта к/ядм/а

ч

23

dxptf 3Styf№

Sx0e Wt/Mt- M PfWtwefa

Sbtrffrf/

(т/игге/ttf

Гтфаш/, utfffyjlfffe

Cwmvuxti

tywWMMfrqp/J

№ MFtffffff.A MttyWfltM

7/иггфМ

Jkaett

8b/xet J 2-й ,

IBfffJKXt/fi

fa/w/4

to, Ь b

Лг flt//WffM№yy#J

l//i(Jf i

{.

2-iZMfffttwy //}-

Siffffj

/-UJ/&% V/f4/ ,.

0№8S// #

ff

Me/

Шаг 2

Шаг

f/a тхт маге (вщ / &(% ц а///ждя5

У

Ч

f

|г-,