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

Предлагаемое изобретение относит ся к вычислительной технике, в част сти к постоянным запоминающим yctpo ствам (ПЗУ). Известно ПЗУ, содержащее регистр входного слова, соединенный через дешифратор и накопитель с соответствующими входами регистра выходного слова, регистр младших разрядов входного слова, коммутатор и сумматор, одни входы которого подключены к первой групппе выходов регистра выходного слова, другие - к выходу коммутатора, входы которого подключены ко второй группе выходов регистра выходного слова, причем управляемые втсоды коммутатора подключены к соответствующим выходам регистра младших разрядов входного слова Гц Недостатком известного ПЗУ является необходимость в больших аппаратурных затратах. Наиболее близким техническим решением к предлагаемому является ПЗУ, содержащее входной регистр, числовую матрицу (накопитель), ключи выборки групп, дешифраторы, выходные регистры и сумматор. В таком ПЗУ старшим разрядам входного регистра соответствует в накопителе опорное значение функции. Мпадшим разрядам в накопителе соответствует рспомогательиое значение функции приращение). Результат получается суммированием опорного и вспомогатель-ного значения функцииГ23. Недостатком такого ПЗУ является большая емкость при хране1ши многоместных симметричных функций. Цель изобретения - повышение информационной емкости устройства. Указанная цель достигается тем, что постоялное запоминакицев устройство дпя многоместных симметричных функций, содержащее иакошг тель ивходной регистр, содержит 3 блок сравнения и коммутатор, при этом информационные выходы входного регистра соединены с соответствующими входами блока сравнения и коммутатора, другие входы которого подключены к соответствующим выходам блока сравнения, а выходы - ко входам накопителя. На фиг. I изображена структурная схем, ПЗУ для многоместных симметрич ных функций;на фиг. 2- пример постро ния коммутатора. Предлагаемое ПЗУ содержит входной регистр 1, вынолйенный в .виде подрегистров 1, 1 (I 1,к), где К- количество аргументов функции, К -входовой блок сравнения 2, коммутатор 3 И накопитель 4. Информационные выходы каждой I-ой группы разрядов входного регистра 1 соединены с f-ым входом блока сравнения 2, К выходов которого подключены к управляющим входам коммутатора 3, информационные входе.1 которого соединены с выходами подрегистров . I.Выходы коммутатора 3 соединены со вводами накопителя 4. Схема представленного на фиг. 2 коммутатора содерзкит KI групп блоков элементов И 5.1, 5.2, ... 5.К . Каждая группа содержит К элементов И 6.1., 6.2 ..., 6.К. Первые входы каждого блока эле.ментов И ,}-ой группы 6 j подключены к j-му выходу блока сравнения 2. Каждая J-я группа (j 1, К) содержит К блоков элементов И 6.J l,6.j 2,... 6j К. Вторые входы каждого блока элементов И всех групп подключены к выходам соответственных подрегистров Г i. Выходы i-x блоков элементов И 6j i (i 1, К) всех груп соединены с К -входовыми элементами ИЛИ 7 I. Предлагаемое устройство работает следукяцим образом. Многоместныни симметричными функциями являются функции от К аргуменинвариантные к их перестанов ...xj (Ху, Хц.1, (I - I, К). Примером многоместных симметричных функций являются произведение К 7 аргументов, функции от такого произведения и т.п. Y X.VX... Y sin.. (,j.Xj ...Хц). Входной регистр I представляет собой кп-разрядный регистр ПЗУ и состоит из к п-разрядных подрегистров 1.i (i I, к), каждый из которых предназначен для приема i-го входного аргумента (п-разрядность i-ro аргумента) . В накопителе 4, представляющем собой постоянную память, по пк-разрядным адресам Ах А,, к А,,.. . А н. . .А хранятся значения воспроизводимой функции f (А «, А . . . Aj) , где А,..АК последовательнаязапись п-разрядных чисел. Числа А могут изменяться в диапазоне О- 2 и связаны между собой следующим соотношениемAjiAji , ,iAj А.....;ЛК Входные аргументы X , поступают на соответствующие подрегистры 1 . i входного регистра 1. Блоком сравнения 2 осуществляется сравнение записанных на I на соответствующем выходе блока сравнения 2 появляется единичный сигнал. Будем считать, что при равенстве всех арг ментов единичный сигнал появляется только :на одном выходе, например на выходе 1. В зависимости от возбуждений шины блока сравнения 2 и 1соммутатора 3 подают на входы накопителя 4 аргументы таким образом, что на первом входе п младших разрядов адресной шины накопителя всегда самое: меньшее из чисел X. на втором накопителе - большее и т.п. в порядке возрастания, а на к-ом входе п старших разрядов адресной шины накопителя - самое большое (см. неравенства (2) . Для каждой комбинации входных аргументов на выходе коммутатора 3 в соответствии с выражением (1) формируется в исполнительный адрес, по.которому выбирается искомо значение функции. Таким образом. К возможным комбинациям входных аргументов ПЗУ в накопителе соответствует одна ячейка памяти, в которой хранятся значения функции, В качестве примера рассмотрим раб ту ПЗУ для двухместной симметричной функции.f(X,X2) f .(XjX). Операнда X(j поступают на входы блока сравнения 2. На одном выходе блока сравнения 2 появляется единичш)1й сигнал, если . При (j единичный сигнал осуществляется на: другом выходе блока яравнения 2. Ком мутация входных операндов осуществляется сигналами с блока ;равнения 2 таким образом, что на младшие разряды адресного входа накопителя 4 подаётся всегда меньшее из чисел Хл, на старшие -большее число. Так при единичный сигнал поступает на младшие разряды адресного входа накопителя 4, число Х на старшие разряды накопителя 4. При , единичный сигнал поступает на старшие разряды адресного входа накопителя, меньшее число на старшие разряды. По сформированному таким об разом адресу из накопителя 4 выбира ется значение функции f (Х Х) или f (XQ, Х). Проведем сравнительную характерис тику аппаратурных затрат известного и предлагаемого устройств. Структура известного ПЗУ позволяет сократить емкость накопителя на 10-30% по сравнению с ПЗУ, в котором каждому . значению аргумента соответствует од на ячейка памяти. При этом состав ПЗУ дополнительно имеет коммутатор приращений и кп-разрядньй сумматор. Емкость накопителя такого ПЗУ (число ячеек памяти) при хранении К-мест ных симметричных функций равна :,.-°- Емкость накопителя предлагаемого ПЗУ определяется по формуле, опре делякмцей количество К разрядных чисел в 2 - ичной системе счисления, у которых значение каждого I-го разряда (i- 1, К) меньше или равно зна чению -)-го разряда и больше или равно значению 1+ 1-го разряда, и равна .Г К Оценим аппаратурные затраты обоих вариантов построения ПЗУ при п 16 и К 2, паратуршае затраты известного 1|.,и предлагаемогоLK ПЗУ определяются как 1ц 2 п Ljj + L, L +nSV; Ц .+ Ifl3y, где. Ljj, -( затраты на один разряд сумматора и схемы сравнения; Lj,H Lj - затраты на построение известного и предлагаемого коммутаторов. Затраты на логическое обрамление обоих устройств примерно равны, Емкость накопителя известного ПЗУ больше по сравнению с предложен ным в 0,. 2 T Wb-rrr В общем случае емкость известного ПЗУ больше по сравнению с предлагаемым в О, 7. . К .. К 1 . П ( е) В предлагаемом устройстве с умен шением емкости накопителя уменьшается затрата па построение адресных цеп пей накопителя. Затраты на логическое обрамление обоих устройств с ростом К растут примерно одинаково. Таким образом, в предлагаемом ПЗУ по сравнению с известный объем памяти при хранении к-местных симметричных функций снижается примерно в К раз. Формула изобретения Постоянное запоминающее уЬтройство для многоместных симметричных ункций, содержащее накопитель и входной регистр, отличающее сгя

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

сравнения, а выходы - ко входам накопителя.

Источники информации, принятые во внимание при экспертизе

1.Авторское свидетельство СССР 453739, КЛ.6 и С 17/00, 1975.

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

342193,-кл. G 06 G 7/26, 1970 (прототип) .

2

1А.г