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

(23) Приоритет дарстаива 4 канктат СССР диан взавратеккк и втарнткйта опубликования описания 1 5, О. ОФ.ф тгр;а О п,е 7 рь ТГХ 1 рця-., сВ. А. Дудков, Н. А Дудкова, В.И. Корней В. П. Тарасенко и Я. И. Торошанко сс 1 фЯ 11Г."нститут им, 50-летневолюции 71) Заявнтел Киевский ордена Ленина политехническии Великой Октябрьской социалистической 4) ПОСТОЯННОЕ 3 ДЛЯ МНОГОМЕСТН МИНАЮЩЕЕ УСТРОЙСТ СИММЕТРИЧНЫХ ФУНК Предлагаемое изобретение относится к вычислительной технике, в частно сти к постоянным запоминающим устройствам (ПЗУ). Известно ПЗУ, содержащее регистр входного слова, соединенный через дешифратор и накопитель с соответствующими входами регистра выходного слова, регистр младших разрядов входного слова, коммутатор и сумматор, одни входы которого подключены к первой группне выходов регистра выходного слова, другие - к выходу коммутатора, входы которого йодклю" чены ко второй группе выходов регистра выходного слова, причем управляемые входы коммутатора подключены к соответствующим выходам регистра младших разрядов входного слова ИНедостатком известного ПЗУ является необходимость в больших аппаратурных затратах. Наиболее близким техническим решением к предлагаемому являетсяПЗУ, содержащее входной регистр,числовую матрицу (накопитель), ключи выборки групп, дешифраторы, выходные регистры и сумматор. В такомПЗУ старшим разрядам входного регистра соответствует в накопителе опорное значение функции. Младшим разрядам в накопителе соответствует 1 всно 1 Омогательное значение функции приращение), Результат получается сум-мированием опорного и вспомогатель=ного значения функции 21.Недостатком такого ПЗУ является 1большая емкость при хранении много"местных симметричных функций.Цель изобретения - повьвюение ин"формационной емкости устройства.20Указанная цель достигается тем,Ъчто постоянное запоминающею устройство для многоместных симметричных функций, содержащее накопи.тель ивходной регистр, содержит(кф) блок сравнения и коммутатор, при этом информационные выходы входного регистра соединены с соответствующи:ми входами блока сравнения и коммутатора, другие входы которого подключены к соответствующим выходам блока сравнения, а выходы - ко входам накопителя.На фиг. 1 изображена структурная схем, ПЗУ для многоместных симметричных функций;на фиг, 2- пример построения коммутатора.Предлагаемое ПЗУ содержит входной регистр 1, выполйенный в,виде подрегистров 1,(1,К), где К- количество аргументов функции, К -входовой блок сравнения 2, коммутатор 3 и накопитель 4. Информационные выходы каждой 1-ой группы разрядов входного регистра 1 соединены с "ым входом блока сравнения 2, К 1 выходов которого подключены к управляющим входам коммутатора 3, информационные входы которого соединены с выходами подрегистров 1. 1.Выходы коммутатора 3 соединены со входами накопителя 4. Схема представленного на фиг. 2 коммутатора содержит К групп блоков элементов И 5.1 5,2,5.К 1 . Каждая группа содержит К элементов И 6.1., 6,2 6.К. Первые входы каждого блока эле.- .ментов И 1-ой группы 6подключены к 1-му выходу блока сравнения 2. Каждая 1-я группа ( = 1, К 1) содержит К блоков элементов И 6. 1,6. 2, 6 К. Вторые входы каждого блока элементов И всех групп подключены к выходам соответственных подрегистров 1 1. Выходы 1-х блоков элементов И 6 (1, К) всех групп соединены с К 1-входовыми элементами ИЛИ 7 1. Предлагаемое устройство работает следующим образом.Многоместными симметричными функциями являются функции от К аргументов Х, инвариантные к их перестанов- кам к)с, х, х,)- к(х ххД. - Е (Х, Х ., Х.) Примером многоместных симметричных функций являются произведение К 4аргументов, функции от такого произведения и т,п. У =Х Х Х(Х Х . Хк). Входной регистр 1 представляетсобой кп-разрядный регистр ПЗУ и О состоит из к и-разрядных подрегистров 1. ( = 1, к), каждый из которыхпредназначен для приема 1-го входного аргумента (п-разрядность 1-го аргумента).Б накопителе 4, представляющемсобой постоянную память, по пк-разрядным адресам А к А н А,А иАкхранятся значения воспроизводимойфункции г(А , А Ак), где 20 А Аи Ая А " последовательнаЯзапись п-разрядных чисел. Числа А 7"я могут изменяться в диапазоне Ои связаны между собой следующим соот- ношением А сА( А ,.сА А, ( А(1) Входные аргументы Х; поступаютна соответствующие подрегистры . входного регистра 1. Блоком сравнения 30 2 осуществляется сравнение записанныхна подрегистрах 1. аргументов ХВ зависимости от выполнения усло- вий ХХ Х,(Х(1)35 ХХ СХссХ, Х 1Хе( Х св СХ у 40на соответствующем выходе блока сравнения 2 появляется единичный сигнал.Будем считать, что при равенствевсех аргументов единичный сигнал появляется только:на одном выходе, например на выходе 1. В зависимости твозбуждений шины блока сравнения 2 икоммутатора 3 подают на входы накопителя 4 аргументы Х таким образом,что на первом входе п младших раз рядов адресной шины накопителя всегдасамое меньшее из чисел Х на второмнакопителе - большее и т.й, в порядке возрастания, а на к-ом входе -п старших разрядов адресной шины на копителя - самое большое (см. неравенства (2) . Для каждой комбинациивходных аргументов на выходе коммутатора 3 в соответствии с выражени0,72.2ф 1,42 ль(2 лЬ +) 35 0,72Кй К 5 8732 ем (1) формируется в исполнительный адрес, по,которому выбирается искомое значение функции.Таким образом, К возможным комбинациям входных аргументов ПЗУв 5 накопителе соответствует одна ячейка памяти, в которой хранятся значения Функции. В качестве примера рассмотрим рабо. 10 ту ПЗУ для двухместной симметричной функции.(Х 1,Х) = Г (Х,Х ). Операнды Хи Х поступают на входы блока сравнения 2. На одном выходе блока сравнения 2 появляется единичный 15 сигнал, если ХХ. При Х,)Х единичный сигнал осуществляется на.другом выходе блока сравнения 2, Коммутация входных операндов осуществляется сигналами с блока сравнения 2 таким образом, что на младшие разряды адресного входа. накопителя 4 подается всегда меньшее из чисел Х 4 и Х , на старшие - большее число. Так, при Х сХ единичный сигнал поступа ет на младшие разряды адресного входа накопителя 4, число Х 2 - на старшие разряды накопителя 4. При Х 1 Х.1единичный сигнал поступает на старшие разряды адресного входа накопи" теля, меньшее число Х- на старшие разряды. По сформированному таким образом адресу из накопителя 4 выбира ется значение функции 1. (Х Х ) или(Х, Х). 77 6 . равно значению + 1"го разряда, и равна 119 УОценим аппаратурные затраты обоих вариантов построения ПЗУ при п6 и К2. лпаратурные эат" раты известногоб.,и предлагаемого,ПЗУ определяются как 1,- 2 п .+ЩЦ1 псс+ к+ Ьафгде. .,с- затраты на один раз"ряд сумматора и схемысравнения;.и- затраты иа построениеЦизвестного и предлагае-мого коммутаторов.Затраты на логическое обрамление обоих устройств примерно равны.Емкость накопителя известного ПЗУ больше по сравнению с йредложен". ным в В общем случае емкость известного ПЗУ больше по сравнению с пред" лагаемым в. = 0,72 пЗМ ф Проведем сравнительную характеристику аппаратурных затрат известного и предлагаемого устройств. Структура известното НЗУ позволяет сократить емкость накопителя на 1 О-ЗОХ по сравнению с ПЗУ, в котором квждомузначению аргумента соответствует од. на ячейка памяти. При этом состав ПЗУ дополнительно имеет коммутатор приращений и кп-разрядный сумматор. Емкость накопителя такого ПЗУ (число ячеек памяти) при хранении К-местных .симметричных функций равна Емкость накопителя предлагаемого ПЗУ определяется по формуле, определяющей количество К разрядных чисел в 2- ичной системе счисления, у которых значение каждого 1-го разряда (" 1, К) меньше илн равно зна" чению 1-1-го разряда и больше или В предлагаемом устройстве с умень- шением емкости накопителя уменьшается затрата ла построение адресных це пей накопителя. Затраты иа логическое обрамление обоих устройств с ростом К растут примерно одинаково,Таким образом, в предлагаемом ПЗУ по сравнению с известный объем памя" ти при хранении к-местных симметричных функций снижается примнрно в К 1 раз. Формула изобретения Постоянное запоминающее устройство для миогпместных симметричных функций, содержащее накопитель и входной регистр, о т л и ч а ю щ е е,с:ятем, что, с целью повышения информационной. емкости устройства, оно содер 1 аит блок сравнения и коммутатор, при ; этом информационные выходы входного регистра соединены с соответствующими входами блока сравнения и инфор мационными входами коммутатора, управлянзцие входы которого подключе-. ны к соответствующим выходам блока 873277 8сравнения, а выходы - ко входам на.копителя.Источники информации,принятые во внимание при экспеотизе1. Авторское свидетельство СССРУ 453739, кл.б 11 С 17/00, 1975.2, Авторское свидетельство СССРВ 342193, кл. 6, Об 6 7/26, 1970 (прототип),873277 Составитель В. Вакарктор Л. Тюрина Текред А.Савка Корректор У. Пономаренк аказ н Уагород, ул. Проектная, 4 ППП "Патент 55/77ВНИИПИ Госудапо делам13035, Иоскв ирак 643 Подптнейиого комитета СССРобретений и открытийЖ, Раущская наб д