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

 

Изобретение относится к вычислитель- , ной технике, в частности к постоянным запоминающим устройствам (ПЗУ), используемым в цифровых вычислительных устройствах. Целью изобретения является сокращение аппаратурных затрат. Цель достигается тем, что в ПЗУ для многоместных, симметричных функций, содержащем блок памяти, блок сравнения, коммутатор и регистр , информационные входы которого являются информационными входами устройства, информационные выходы регистра соединены с информационными входами блока сравнения и коммутатора, управляющие входы которого соединены с соответствующими выходами блока сравнения , введены дополнительные блоки памяти , адресный вход первой и второй групп первого блока памяти соединен с выходами соответственно первой и второй групп коммутатора , выходы третьей и последующей групп коммутатора соединены с адресными входами второй группы второго и последующих дополнительных блоков памяти соответственно , адресные входы первой группы второго и последующих дополнительных блоков памяти соединены с информационными выходами первого и последующих дополнительных блоков памяти соответственно, выход последнего дополнительного блока памяти является выходом устройства. 1 табл., 1 ил. (/ С

СОЮЗ СОВЕТСКИХ сОциАлистических

РЕСПУБЛИК (Я)5 G 11 С 17/00

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4718247/24 (22) 11.07.89 (46) 15.08.92, Бюл. М 30 (71) Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции (72) Яхья Наджар (SY), А.Г,Накалюжный и

В.П.Тарасенко (SU) (56) Авторское свидетельство СССР, М

873277, кл. G 11 С 17/00, 1981.

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

М 1396137, кл. G 06 F 7/00, 1988. (54) ПОСТОЯННОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО ДЛЯ МНОГОМЕСТНЫХ СИММЕТРИЧНЫХ ФУНКЦИЙ (57) Изобретение относится к вычислитель-,. ной технике, в частности к постоянным запоминающим устройствам (ПЗУ), используемым в цифровых вычислительных устройствах. Целью изобретения является сокращени аппаратурных затрат. Цель достигается тем. что в ПЗУ для многоместных симметричных функций, содержащем блок

Изобретение относится к вычислительной технике, в частности к постоянным запоминающим устройствам (ПЗУ), используемым в цифровых вычислительных устройствах.

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

« Ы«1755325A1

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

Недостатком этого устройства является сравнительно большая требуемая емкость памяти.

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

РАВНОЗНАЧНОСТЬ, элемент НЕРАВНОЗНАЧНОСТЬ, элемент И, элемент ИЛИ-HE. сумматор по модулю два, шесть входов и выход устройства.

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

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

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

Предлагаемое ПЗУ для многоместных

Недостатком такого устройства являет- выходы каждой группы разрядов регистра 1 ся ограниченная область применения уст- соединены с >-м входом блока 2 сравнения, ройства, так как оно не позволяет получать k âûõoäîâ которого подключены к управляющим входам коммутатора 3, информацифункций. 5 онные входы которого соединены с

Наиболее близким к изобретению явля- выходами подрегистров 1, i. Адресный вход ется постоянноезапомина1ощееустройство первой группы первого блока памяти с нодля многоместных симметричных функций, мером 4.1 подключен к выходу первой групсодержащее входной регистр, информаци- пы коммутатора 3, выходы остальных групп онные выходы котОрого соединены с соот- 10 которого с номерами l(1=2, k) соответственно ветствующими входами блока сравнения и соединены с адресными входами вторых групп блоков памяти, имеющих номера 4, i-1. Информационный выход каждого блока памяти с н оме ром 4, m (m-1, !;.-2) подключен

15 к адресному входу первой группы блока памяти с номером 4, а+1, а выход последнего блока памяти с номером 4, k-1 является вы- ходом устройства. хранения значений многоместных симмет- При конкретной реализации устройства ричных функций, что приводит к значитель- 20 регистр 1 может быть реализован, напри. ному росту аппаратурных затрат. мер, с использованием микросхем 155ИР1, Целью изобретения является снижение блок 2 сравнения может быть построен на основе схем специализированных модулей, например устройства для выделения максипостоянномзапоминающемустройстведля 25 мального числа. Коммутатор 3 может быть многоместных симметричных функций, со- реализован с использованием элементов И держащем блок памяти, блок сравнения, (микросхем 155ЛИ5). Блоки памяти4,J(j=-1, коммутатор и регистр, информационные k-1) могут быть реализованы на постоянных запоминающих устройствах — микросхемах

30 568РЕЗ.

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

Функция от k аргументов, инвариантная соединены с соответствующими выходами 35 к перестановкам ее аргументов, т.е. F (Х1, блока сравнения, введены дополнительные Х2,.„iXk)=Fk-1(X1, Fk-2(Х2...., F1(Xk-1,Xk)) )=Fk1(X2 Рк-2(Х1„... F1(Xk-1 Xk))»)=" Fk-1(Xk Fk

2(Xk-1,..., F1(X2, Х1))...) на э ы в а ется выходами соответственно первой и второй .многоместной симметричной функцией.

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

45 суперпозиции симметричных функций двух дополнительных блоков памяти соединены переменных: с информационными выходами первого и Y=-А"1+"2+"з+...+xK =(((A"! А" ) А" )

А"к)

У=!ОЦ, (X1 Х2 ... Хк)= (...!ОС! Х1 lOg c X2)+

50 log сХз)+" log сХй). выходом устройства, Регистр 1 представляет собой kn-разНа чертеже представлена структурная рядный регистр и состоит из kn-разрядных подрегистров 1, i(-1,k), каждый иэ которых предназначен для приема l-го входного ар55 гумента (и-разряность i-ro аргумента). симметричных функций содержит регистр Входные аргументы Х1 поступают на со,1 выполненный в виде подрегистров 1,i ответствующие подрегистры 1, i регистра 1. (1= l,k), где k — количество аргументов функ- Блоком 2 сравнения осуществляется сравции, К вЂ” входовой блок 2 сравнения, комму- нение записанных на подрегистрах 1; l аргутатор 3 и (k-1) блоков памяти 4, j (l=f, М), ментов Х. включенных каскадно. Информационные В зависимости от выполнения услови

1755325 предлагаемом, рассчитанные при различных и и К где k — количество аргументов, n— разрядность аргумента.

Из таблицы видно, что требуемый объем

5 постоянной памяти предлагаемого устройства по сравнению с прототипом уменьша ется, а выигрыш в обьеме памяти оценивается согласно выражению:

10 (n2n(2л+1)(2л+2) (2n+ k-1} /k! /„2 "(k 1)-. (2"+ 1) (2"+ 2,...,(2"+ К- 1} /k 2"(k-1), Формула изобретения

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

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

40 последующих дополнительных блоков памяти соответственно," выход последнего дополнительного блока памяти является выходом устройства.

Требуемый объем постоянной памяти в предлагаемом ст ойстве бит остототи1048576

1572864

2097152

2621440

10"

1014

10 9

1023

1011

1011

1,374

2,062

1011

Х1 <Х2 < .... < Х 5 ....< Хк; (1) Х X> - ..., Х,. -. Хк, (2) Хк < Хк-1 < .„< Х;< ..„< X> на соответствующем выходе блока 2 сравнения появляется единичный сигнал. Будем считать, что при равенстве всех аргументов единичный сигнал появляется только на одном выходе, например на выходе 1. В зави-. симости от состояния выходов блока 2 сравнения коммутатор 3 подает на адресный вход первой группы первого блока памяти с номером 4.1 самое меньшее из чисел

Хь а остальные аргументы Xi(!=2, k) в порядке возрастания (см. неравенства (13) подаются на адресные входы вторых групп блоков памяти с номерами 4, 1-1. Это приводит к тому, что на выходе блока памяти с номером 4.1 будет получено значение F<, на выходе блока памяти с номером 4,2 — значение Fz и т.д. На выходе же последнего блока памяти с номером 4, k-1 будет получено значение Fk-g=F (X), Х „„, Хф

Емкость накопителя ПЗУ в прототипе, определяется количеством k-разрядных чисел в 2 "- ичной системе счисления, у которых значение каждого 1-го разряда (=1,к) меньше или равно значению (i+1)-ro разряда и больше или равно значению (i-1)-го разряда.

Это количество равно п(2П+1) (2П+2) (2п+ k -1) ф 1 би-r

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

В таблице приведены требуемые объемы памяти в устройстве по прототипу и в

Выигрыш в объеме памяти от использования и

1755325

Составитель Н,Яхья

Редактор Т.Лазоренко Техред М.Моргентал

Корректор А.Осауленко

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

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

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

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