Постоянное запоминающее устройство для многоместных симметричных функций Советский патент 1992 года по МПК G11C17/00 

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

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

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

Известно также постоянное запоминающее устройство для получения значений симметричных булевых функций четырех и менее аргументов, содержащее элемент РАВНОЗНАЧНОСТЬ, элемент НЕРАВНОЗНАЧНОСТЬ, элемент И, элемент ИЛИ-НЕ, сумматор по модулю два, шесть входов и выход устройства.

VJ ел ел GJ

hO

ел

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

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

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

Целью изобретения является снижение аппаратурных затрат.

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

На чертеже представлена структурная схема ПЗУ для многоместных симметричных функций.

Предлагаемое ПЗУ для многоместных симметричных функций содержит регистр Т ыполненный в виде подрегистров 1,1 (,k), где к - количество аргументов функции, k - входовой блок 2 сравнения, коммутатор 3 и (k-1) блоков памяти 4, j (, k-1), включенных каскадно. Информационные

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

При конкретной реализации устройства регистр 1 может быть реализован, например, с использованием микросхем 155ИР1, блок 2 сравнения может быть построен на основе схем специализированных модулей, например устройства для выделения максимального числа. Коммутатор 3 может быть реализован с использованием элементов И (микросхем 155/1И5). Блоки памяти 4, j ( k-1) могут быть реализованы на постоянных запоминающих устройствах - микросхемах 568РЕЗ.

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

Функция от k аргументов, инвариантная к перестановкам ее аргументов, т.е. F (Xi,

Х2XkJ Fk-i(Xi, Fk-2(X2Fi(Xk-i,Xk))...)Fk1(X2, Fk-2(Xi Fi(Xk-i, Xk))...)...Fk-i(Xk, Fk2(Хм,..., Fi(X2, Xi))...j называется многоместной симметричной функцией. Примерами многоместных симметричных функций являются функции суммы и произведения к аргументов, элементарные функции от суммы и произведения к аргументов и т.п., которые можно представить в виде суперпозиции симметричных функций двух переменных:

...+xK (..-((Ах1 Ах) Ахз) .... Ахк)

(Xi X2 ... Хк) (..Jog cXi log c X2)+ log сХз)+..,од СХК).

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

Входные аргументы Xi поступают на соответствующие подрегистры 1, i регистра 1. Блоком 2 сравнения осуществляется сравнение записанных на подрегистрах 1, i аргументов X. В зависимости от выполнения условий

Xi Х2 .... Xi .... Xk; (1) Xa Xi .... Xi .. . Xk ; (2)

Xk Xn ... .... X, на соответствующем выходе блока 2 сравнения появляется единичный сигнал. Будем считать, что при равенстве всех аргументов единичный сигнал появляется только на одном выходе, например на выходе 1. В зависимости от состояния выходов блока 2 сравнения коммутатор 3 подает на адресный вход первой группы первого блока па- мяти с номером 4.1 самое меньшее из чисел Xi, а остальные аргументы Xi(, k) в порядке возрастания (см. неравенства (1D) подаются на адресные входы вторых групп блоков памяти с номерами 4, Ы. Это при- водит к тому, что на выходе блока памяти с номером 4.1 будет получено значение FI, на выходе блока памяти с номером 4,2 - значение F2 и т.д. На выходе же последнего блока памяти с номером 4, k-1 будет получено значение (Xi, Х2Хк).

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

n2n(2n+1)(2n+2)...(2n+k-1) /k биг.

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

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

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

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

n2n(2n+1)(2n+2).,,(2n+k-1)/k /n22n(k-1)- (2n+ 1) (2n+ 2)...( k-1) /k 2n(k-1).

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

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

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