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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (19) (И) А1 (51)g С 06 F 7/00

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

Н A ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

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

ПРИ ГКНТ СССР (21) 4465062/24-24 (22) 27 07.88 (46) 23.03.90.„Бюл. . 11 (711 Минский радиотехнический институт (72) И.Н.Бондарь, В.М.пащенков, Д.В.Кузьмицкий и В.П.Имерко (53) 681.325(088.8) (56) Авторское свидетельство СССР

)1 959064, кл, G 06 F 7/00, 1979.

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

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

НА ЛИНЕЙНОСТЬ БУJlEBhiX ФУНКЦИЙ (57) Изобре ение относится к цифровой

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

1552169

+ р(х) = р„+ р4х„+ р х„!,х,...х„=

I I

44 4б 44 144 рх х ... х„,х„! г

+ ° ° ° +Р 44 гк —:Е.

;=о где р,

0,2" - 1), множество целых чисел таких, что значение

P(X) E(0,1} мэ любом наборе переменных, xi «X (, 44=- 1, t г! г ° ° °

t4- 4 tl — и-разрядный двоичный код представления пара- метра i.

Арифметическая полиномиальная Форма P(X) булевой функции f(x) опредеИзобретение относится к цифровой вычислительной технике и может быть использовано для аппаратной поддержке Bbl числений в комплексах автоматизирован нс4го проектирования дискретных устройств, обработки изображений, сжатия данных, в системах синтеза топологии БИ С и СБИС.

Целью изобретения является расши- 10 рейие Функциональных врзможностей:. эа! счет распознавания на линейность булевых функций, заданных в обобщенной арифметической полиномиальной форме. 15

На Фиг. 1 представлена схема устро 4ства; на Фиг. ?. — схема коммутатс ра; на Фиг. 3 - Функциональная схема узла мультиплексоров; на Фиг. 4( схема блока регистров; на Фиг. 5 - 20 схема вычислительного блока; на фи!г. 6 - схема блока управления.

Устройство содержит коммутатор 1, блок 2 регистров, вычислительный блок 3 и блок 4 управления. Коммута- 25 тор 1 содержит 2" -,1 узлов 5 мультиплексоров, где п - число переменных булевых Функций. Блок 2 регистров содержит 2" регистров 6. Вычислительный

6 1ок 3 содержит 2 " вычитателей ЗО

74, 2 " - 1 элементов 0 сравнения и элемент И 9. Блок 4 управления соде}ржит генератор 10 тактовых импульcda, элемент И ll. элемент И-НЕ 12, счетчик 13, дешифратор 14 и триггер

15.

Арифметическая полиномиальная формд булевой функции f(х) имеет следующий вид: ляется вектором коэффициентов p =

-1 т ре 4 р 4 4 ° ° ° 4 Рл44-! 1 4 которыи

=L является результатом выполнения конъюнктивного преобразования над вектором значений Х = $ х 1 х4 1 (ten 1 х() булевой функции f(x), (2) р = к, х, где К 4 - матрица конъюнктивного преобразования размерности

44

? х 2 . формируемая по правилу

K = K, Î K h-!

1 ОЧ

К (3), (x)+ () ° ° ° + >-,().

Если -ю Функцию кортежа (j =

= О,m-l) представить в виде арифметической полиномиальной Формы P (х), J затем умножить на весовой множитель

2 и полученные с весами полиномы сложить, то результатом является обобщенная арифметическая полиномиальная форма D(x), где

2 Р (х)

D(x) Д -1

;, с1 =о

Обобщенная арифметическая полиномиальная форма системы булевых Функций D(x) однозначно представляется вектором коэффициентов D = (Д, д „

-1 т

° ° э 4 С1

Линейная обобщенная арифметическая полиномиальная Форма системы булевых Функций f (х) (j = О „m-1) имеет следующий вид:

LD(x) = 1„+ 1„х„+ 1 x„, +

44 ! 1 где Q — символ кронекеровского произведения.

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

169 6 нейной обобщенной арифметической и полиномиальной Формы содержит 2 элементов. Это свойство определяет целесообразность использования линейной обобщенной арифметической полиномиальной Формы, позволяющей сократить объем вычислений при обработке и объем памяти при хранении векторов коэффициентов. Таким образом, возникает необходимость распознава- ния на линейность обобщенных арифметических полиномиальных форм, заданных своими векторами значений Хд>.

Для обобщенной арифметической полиномиальной Формы системы булевых функций между вектором значений Х> и вектором коэффициентов 9 существует взаимно однозначное соответствие,,определяемое выражением

S 1552

Из (5) видно, что обобщенная арифметическая полиномиальная форма является линейной, если в ее состав входят только слагаемые, определяемые лишь одной булевой переменной х; (i = 1,n).

Таким образом, если коэффициенты обобщенной арифметической полиномиальной формы D(x) удовлетворяют ус- 10 ловию

Ю

d =0 для i P2, 63=0 n l, =0 2". — 1 (6)

Э

15 (7) 2"

Из (7) следует, что в общем случае условие линейности обобщенной арифметической полиномиальной формы имеет вид (о1 (1 (1 (1 х(

- х (2и 2п-Ч (8) .

35 ратора 10 тактовых импульсов, а также йа первый вход счетчика 13, в который записывается число 2" - n, код этого числа с выходов счетчика

40 13 поступает на входы дешифратора

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

В момент времени t на выходе ге-.

45 нератора 10 Формируется тактовый импульс, поступающий через элемент

И 11 на второй вход счетчика 1,Счетчик 13 переходит е состояние 2 — п +

+ 1, код с выходов счетчика 13 посту50 пает на входы дешифратора 14, на выходах которого формируются сигналы в соответствии с 1таблицей.

В моменты времени 4 и

g5 работа блока 4 управления происходит аналогично работе в момент времени

t,,только счетчик 13 переходит в состояния 2 - n + 2 и. 2" - и + 3

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

Ф

Линейная обобщенная арифметическая полином((альная Форма системы булевых функций однозначно определяет-. ся вектором коэффициентов LB = r 1, 1(f ° ..9 1 j, Характерным свойством является то, что этот вектор коэффициентов содержит всего n + l элемент,. тогда как вектор коэффициентов нели° ° ° е ° ° з ° ° ° ° ° (о1 (2 ) (а- < ) Вычислительный .блок 3 работает следующим образом. Элементы вектора значений Хр (x""1, х, ..., х з поступают на входы вычитателей 7. в которых формируются значения, разнос — 1) тей поступивших элементов x( х (1. С выходов вычнтателей 7 значения разностей х(1 - х

1 передаются на входы элементов 8 (и

8 j сравнения, с выхода которых сигнал равенства операндов на входах (высокий логический уровень) поступает на вход элемента И 9, на выходе которого формируется высокий логический уровень в случае высоких логических уровней на всех его входах.

Дешифратор 14 предназначен для

Формирования сигналов на своих выходах в соответствии с таблицей.

Блок 4 управления работает следующим образом. В момент времени t( высокий логический уровень напряжения поступает на вход запуска гене(Я."-2 ) (2 -2 )

= х - х (2и2ха)

Р

155?

В момент времени t счетчик 13 при поступлении на его второй вход тактового импульса переходит из состояния

2 - 1 в состояние О, и с его выхода

k сигнал переполнения поступает на 5 входы элемента И-НЕ 12 и триггера l5., который переходит из нулевого в единичное состояние. С выхода элемента

И-НЕ 12 сигнал фронта напряжения с

Низкого логического уровня на высокий

1 поступает на вход останова генератоа 10 тактовых импульсов.

Рассмотрим работу устройства для случая n = =4 . Элементы вектора значений = Гх() х () ... х (")) поступают на информационные входы первой группы устройства. После поступления

9а вход режима блока 4 управления высок(>го логического уровня (момент времени t ) s счетчик 13 записывает1

К ся число, равное 2 — п = 8 - 4 = 4, ему соотствуествует код 100. следова тельно, на первом выходе блока 4 управления формируются нулевые сигна- 5 лы, которые передаются на управляющий вход коммутатора 1.

Выработанный генератором 10 тактовый импульс (момент времени t ) поступает на вход записи регистров

ЗО

6 и синхронизирует запись в регистры

6 элементов вектора значений Х >, поступающих с выхода коммутатора 1.

Под действием этого тактового импульса счетчик 13 переходит из состояния

100 в состояние 101. Если выполнях(о) - х() = y,() х (> х(4> хк) х (6l — х(т1 x(8) — x(e> х (О) х() x() — х (1 = х(«) — х(")

> то на выходе вычислительного блока

3 остается высокий логический уровень, В момент времени t< тактовый импульс с второго выхода блока 4 управления передается на вход записи регистров 6 и синхронизирует запись в них элементов вектора значений Xä х() х(+) х() () х " > х(> х(" )

1 t 9 I Э У °

Эти значения записываются в регистры

6 (р = ?,8), в остальные регистры блока 2 регистров записывается та же информация, которая была в них записа-50 на в момент времени t . На выходе вычислительного блока 3 остается высокий логический уровень напряжения в случае выполнения x() - х (>

= y((> — х(<1 >> — х по> = х " )—

x(1. Под действием этого же тактового импульса счетчик 13 переходит из состояния 101 в состояние 110.

16Э 8

В момент времени.t тактовый им5 пульс с второго выхода блока 4 управления поступает на вход записи блока 2 регистров и синхронизирует запись в его регистры 6 - 6,> значений элементов х (4), x(), х («) вектора х

Содержимое остальных регистров блока

2 регистров остается без изменения.

Если выполняется х() - х (4) = х() (ю )

-.х, то на выходе вычислительного блока 3 сохраняется высокий логический уровень напряжения„ Счетчик переходит из состояния 110 s состояние 111 °

В момент времени t6 тактовый импульс поступает на счетный вход счетчика 13, который при этом переходит из состояния 111 в состояние

000 и формирует сигнал переполнения.

Сигнал переполнения поступает на вход триггера l5 и переводит его в единичное состояние, а также поступает на вход элемента И-НЕ 12 и далее на вход останова генератора 10 тактовых импульсов.

Таким образом, наличие единичного состояния триггера 15 при остановленном генераторе 10 тактовых импульсов свидетельствует о линейности распознаваемой обобщенной арифметической полиномиальной Формы.

Если обобщенная арифметическая полиномиальная форма не является линейной, то на этапе распознавания (например, в момент времени tp) не выполняется одно из равенств (7).

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

И-НЕ 12, с выхода которого высокий логический уровень напряжения передается на вход останова генератора

1О, Таким образом, наличие нулево" го состояния триггера 15 при остановленном генераторе 10 тактовых импульсов свидетельствует о непринад" лежности распознаваемой обобщенной арифметической полиномиальной формы к классу линейных.

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

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

Выходы

Код на Входы входе

1 2 . . . n-2 и 1

1 2 3 4 5 6 7 3 . . . 2 -1 2 . . . 2 -1

0 О ... О О Х X Х Х Х Х Х Х ... Х . Х ... Х

О О ... О 1 Х Х Х Х Х Х Х Х ... Х Х . .. Х

2 -и

2 -и+!

2 -и+2

О

О О 0 О О

1 1 1 1

1 1 1 1 1

О

О

О О ... О

1 ... 1

1 1 ... 1

О

О

2 -3

2 -2

2 -1

О.

О

О

О

О 1 1 1 1 1 I

1 О 1 1 1 О О О

I 1 О О О О О О

1 О ... О

О 0 ... О

О 0 ... О

1 1

1 1

1 1

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

Форме, оно содержит 2 регистров (где и - число переменных булевых

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

-1)"й подклочены соответственно к информационным входам второй группы

552169 10 коммутатора и соответственно к инФормационным входам первой группы вычислительного блока, выходы регист" и-1 п ров с 2 -го по 2 -й подключены соответственно к информационным входам второй группы вычислительного блока, выход которого подключен к входу режима блока управления, первый, второй и третий выходы которого подключены соответственно к управляющему входу коммутатора, к входам записи всех регистров и к выходу признака линейности распознаваемой обоб"

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

1552169

Фиг. б

Составитель В. Смирнов

Texpeä JI. Олийньпс Корректор Э.Лончакова

Редактор В.Петраш

Тираж 561

Подписное

Заказ 330

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

113В35, Москва, Ж-35, Раушская наб., д. 4/5

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