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

 

ОПИСАНИЕ 187

Союз Советскив

Социалистические

Республик

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (6I ) Дополммтельмое к авт. сеид-ву (22) Заювлено 03. 10, 79 (21) 2824421/ I 8-24 с присоединением заявки J% (5l)N. Кл.

"ill С 17/00 еввуАвретееввые квинтет

СССР (23 ) П р и ори тет.

Опублмковамо 1g . .I p. 81. бюллетень М 38

Дата опубликования описания l5, I0.8I ав делен взевретеккк в втерытвй (S3) УДК68I 327, .6(088.8) ОФ.3ф„игр;",, + «С «, 9,а 7 в..g „, „„

3ю

ТЕфтРц.:-. -,,, (72) Авторы изобретения

В. А. Дудков, Н. А.. Дудкова, В.И. Корнейч !

В. П. Тарасенко и Я. И. Торошанко с

cl уФ) 1 ° .

Г.

Ф

Киевский ордена Ленина политехнический институт им, 50-летн

Великой Октябрьской социалистической революции (7l ) Заявитель (4) ПОСТОЯННОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО

ДЛЯ МНОГОМЕСТНЫХ СИММЕТРИЧНЫХ ФУНКЦИЙ

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

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

10 входного слова, коммутатор и сумматор, одни входы которого подключены к первой группне выходов регистра выходного слова, другие — к выходу коммутатора, входы которого йодклю"

15 чены ко второй группе выходов регистра выходного слова, причем управляемые входы коммутатора подключены к соответствующим выходам регистра младших разрядов входного слова(1

Недостатком известного ПЗУ является необходимость в больших аппаратурных затратах. 2

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

ПЗУ, содержащее входной регистр, числовую матрицу {накопитель), ключи выборки групп, дешифраторы, выходные регистры и сумматор. В таком

ПЗУ старшим разрядам входного регистра соответствует в накопителе опорное значение функции. Младшим разрядам в накопителе соответствует рс омогательное значение функции (приращение). Результат получается сум- мированием опорного и вспомогатель= ного значения функции(2).

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

Цель изобретения — повышение информационной емкости устройства.

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

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

На фиг. 1 изображена структурная схема, ПЗУ дпя многоместных симметричных функций;на фиг. 2- пример построения коммутатора.

Предлагаемое ПЗУ содержит входной регистр I выполйенный в,виде подрегистров 1, (i I,К), где К- количество аргументов функции, К -входовой блок сравнения 2, коммутатор 3 и накопитель 4. Информационные выходы каждой i-ой группы разрядов входного регистра 1 соединены с i"ым входом блока сравнения 2, К! выходов которого подключены к управляющим входам коммутатора 3, информационные входы которого соединены с выходами подрегистров 1. i.Âûõîды коммутатора 3 соединены со входами накопителя 4. Схема представленного на фиг. 2 коммутатора содержит К1 групп блоков элементов И 5.1>

5.2, ... 5.К1 . Каждая группа содержит К элементов И 6.1., 6.2

6.К. Первые входы каждого блока эле.-.ментов И )-ой группы 6 j подключены к j-му выходу блока сравнения 2.

Каждая !-я группа (j = 1, K!) содержит К блоков элементов И б.j 1,6.j

2,... 6j К. Вторые входы каждого блока элементов И всех групп подключены к выходам соответственных подрегистров 1 i. Выходы i-x блоков элементов И 6ji (! 1, К) всех групп соединены с К!-входовыми элементами ИЛИ 7 i.

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

Многоместными симметричными функциями являются функции от К аргументов Х1, инвариантные к их перестановкам

f(X,, Х,..., Х, ) f(X, X,...,X)

" °" = " (X„Хк-» " Х.1) (! m 19 к) .

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

3277

4 аргументов, функции от такого произведения и т.п.

Y X X X)...Х„, У = з < и: (Х„Х Х ...Х 1< ) .

Входной регистр представляет собой кп-разрядный регистр ПЗУ и

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

Б накопителе 4, представляющем собой постоянную память, по пк-разрядным адресам А к А н А, ... А и...Ак хранятся значения воспроизводимой функции f (A „, А.... Ак), где

А и Ая ..aA " последовательная запись п-разрядных чисел. Числа Ag

n-i могут изменяться в диапазоне О- 2 и связаны между собой следующим соотношением

А <А>«< A <..iА> А<... Аy, (I) Входные аргументы Х; поступают на соответствующие подрегистры I.I входного регистра 1. Блоком сравнения

50 2 осуществляется сравнение записанных на подрегистрах I.i аргументов Х

В зависимости от выполнения условий

Х„< Х < ° . °

35 (2) (2) X c X <... <Х.! <... < Х

Х < Х P ..<Х ° <. ° .<Ху (к.) 40 на соответствующем выходе блока сравнения 2 появляется единичный сигнал.

Будем считать, что при равенстве всех аргументов единичный сигнал появляется только:на одном выходе, нап45 ример на выходе 1. В зависимости . .т возбуждений шины блока сравнения 2 и коммутатора 3 подают на входы накопителя 4 аргументы Х„ таким образом, что на первом входе п младших раз5О рядов адресной шины накопителя всегда самое .. меньшее из чисел Х на втором накопителе — большее и т.й. в порядке возрастания, а на к-ом входе— п старших разрядов адресной шины на55 копителя — самое большое (см. неравенства (2) . Для каждой комбинации входных аргументов на выходе -коммутатора 3 в соответствии с выражени0,7 2 . 2

1,4

2 л (2 Ò6 + ) ) 35

0,7-. 2 ° К и К!

5 8732 ем (1) формируется в исполнительный адрес, по.которому выбирается искомое значение функции.

Таким образом, К! возможнъ1м комбинациям входных аргументов ПЗУ в 5 накопителе соответствует одна ячейка памяти, в которой хранятся значения Функции.

В качестве примера рассмотрим рабо- 10 ту ПЗУ для двухместной симметричной функции. f (X«X ) = f (11,Х ) . Операнды Х„и Х1 поступают на входы блока сравнения 2. На одном выходе блока сравнения 2 появляется единичный 15 сигнал, если Х,, Х . При Х,)Хъ единичный сигнал осуществляется на . другом выходе блока сравнения 2. Коммутация входных операндов осуществляется сигналами с блока сравнения 2 таким образом, что на младшие разряды адресного входа. накопителя 4 подается всегда меньшее из чисел Х,1и

Х, на старшие — большее число. Так, при Х„сХ единичный сигнал поступа- 25 ет на младшие разряды адресного входа накопителя 4, число Х вЂ” на старшие разряды накопителя 4. При Х 1Х .! единичный сигнал поступает на старшие разряды адресного входа накопи" теля, меньшее число Х1 — на старшие разряды. По сформированному таким образом адресу из накопителя 4 выбира ется значение функции f (Х X ) или

s (х, XÄ).

77 6 . равно значению !+ 1-ro разряда, и равна,tI

119У

Оценим аппаратурные затраты обоих вариантов построения ПЗУ при п 16 и К 2. фппаратурные эат" раты известногоб.,и предлагаемого!, ПЗУ определяются как „- 2 n L>+ L„L+Ю;

L ale + L „+ Qg, где. Lg, L< - затраты на один pas" ряд сумматора и схемы сравнения; ! и Lg затраты на построение

Ц известного и предлагае- мого коммутаторов.

Затраты на логическое обрамление обоих устройств примерно равны.

Емкость накопителя известного

ПЗУ больше по сравнению с йредложен» ным в

В общем случае емкость известного ПЗУ больше по сравнению с предлагаемым в к-1

П (2 + е) е=0

45

50 ! =0,7 ° 2 п3М

Проведем сравнительную характеристику аппаратурных затрат известного и предлагаемого устройств. Структура известното НЗУ позволяет сократить емкость накопителя на 10-307 по сравнению с ПЗУ, в котором квждому .. значению аргумента соответствует одна ячейка памяти. При этом состав

ПЗУ дополнительно имеет коммутатор приращений и кп-разрядный сумматор.

Емкость накопителя такого ПЗУ (число ячеек памяти) при хранении К-мест-. ных .симметричных функций равна

Емкость накопителя предлагаемого ПЗУ определяется по формуле, определяющей количество К разрядных чисел в 2 - ичной системе счисления, у которых значение каждого I-го разряда (I 1, К ) меньше илн равно значению 1-1-го разряда и больше или

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

К растут примерно одинаково.

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

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

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

873277 8 ( сравнения, а выходы — ко входам накопителя.

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

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

У 453739, кл.6 11 С 17/00, 1975.

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

 342193, кл. G, Об 6 7/26, 1970 (прототип), 873277

Дм &юи 8

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

Текред А.Савка Корректор У. Пономаренко

Редактор Л. Тюрина

Филиал ППП "Патент", r. Увгород, ул. Проектная, 4

Заказ 9055/77 Тираа 648 Подписное

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

1!3035, Иосква., Ж-35, Раутская наб., д. 4/5