Запоминающее устройство

(54) ЗАПОКП 1 А 10 КГЕ УСТРОЙ тся к вычислиет быть исполь зоб ние отно рядцу о пе ехнике и тельно зовано тройствах бработкой запоминающихледовательной Недостатожность и с посмации вов чисел,нающих ячеек регистра сдвига равняется количеству хранимых чисел в ЗУ.Наиболее близким к предлагаемому изобретению является запоминающее уст ройство, содержащее реГистр сдвиГа, информационные входы которого соедине ны соответствующими шинами логических нуля и единицы, а выходы - с информационными входами основных элементов И, выходы которых соединены с одними входами элемента ИЛИ, и шины управления "Обращение", тактовая шина устано ки в исходное состояние, к которым е 1 3 и 2 подключены соответствующие входы гистра сдвига, дополнительные эле ты И, триггер, двоичный счетчик и группы элементов ИЛИ, входы которых подключены к адресным гщнам, выход элементов ИЛИ одной группы соедине н Известны запоминающие устроиства свыдачей информации в последовательном Одно из известных запоминающих устройств (ЗУ) содержит регистр сдвига,30 шины управления, элементы И по количеству разрядов регистра и элемент ИЛИ, причем выходы разрядов регистра сдвига соединены с информационными5 входами элементов И, управляющие входы которых подключены к соответствующим адресным шинам, а выходы соединены со входами элемента ИЛИ, информационные входы регистра сдвига подключены к соответствуюшим шинам логических нуля и единицы, вход разрешения записи регистра сдвига соединен с шиной "Обращение", а выход последнего раза сдвига подключен ко вхого разряда.ом этого ЗУ является егои хранении больших массиак как количество запомиЯб 8835 Заказ 8340/75 Тираж бч 8 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 13035, Москва, Ж, Раушская наб., д, 4/5868835 О 25 30 35 4045 50 с соответствующими управляющими входами основных элементов И, а выходы эле"ментов ИЛИ другой группы соединены ссоответствующими управляющими входами дополнительных элементов И, информаци онные входы которых соединены с выходами разрядов регистра, сдвига, а выходы подключены к соответствующим входам элемента ИЛИ, входы двоичногосчетчика подключены к шинам управления "Обращение", тактовой и к шине ус тановки в исходное состояние, которая подключена к нулевому входу триггера, нулевой выход которого подключен к первому управляющему входу основных элементов И, а единичный выход - к первому управляющему входу дополнительных элементов И, единичный вход триггера соединен с выходом двоичного счетчика, В данном устройстве накопитель выполнен на сдвиговых регистрах,Недостатком известного ЗУ является его сложность при хранении массивов чисел большой разрядности, т. к. с увеличением разрядности значительно увеличивается количество ячеек памяти, так как в каждой ячейке памяти хранится два п-разрядных числа с взаимно обратными кодами.Цель изобретения - повышение быстродействия устройства.Указанная цель достигается тем, что в запоминающее устройство, содержащее накопитель на сдвиговых регистрах, информационные входы которого соединены с соответствующими шинами логических нуля и единицы, другие входы " с соответствующими шинами установки в исходное состояние, обращение и тактовой, а вьпсоды - с первыми входами элементов И, выходы которых соединены с соответствующими входами элемента ИЛИ, группы элементов ИЛИ, вхо". ды которых. соединены с соответствующими адресными шинами, введены дополнительный накопитель на сдвиговых регистрах, дешифратор, дополнительную тактовую шину, группы элементов И и дополнительные группы элементов ИЛИ, выходы дешифратора соединены со вторыми входами соответствующих элементов И, а входы - с выходами элементов ИЛИ дополнительных групп, входы которых соединены с выходами элементов И соответствующих групп, первйе входы которых подключены к выходам элементов 55ИЛИ соответствукщих групп, а вторыевходы - к сортветствующим выходам дополнительногд накопителя, информационные входы которого соединены с соотг= ветствующими шинами логического нуля и единицы, а другие входы - соответ - ственно с шинами установки в исходное состояние, обращения и дополнительной тактовой.На фиг. 1 представлена блок-схема устройства 1 хранящего 216 двадцатиразрядных двоичных чисел; на Фиг. 2 и фиг. 3 представлены ориентированные Зйлеровы графы для четырехразрядных и пятиразрядных двоичных чисел; на фиг, 4 представлена временная диаграмма работы устройства; на фиг. 4 а показан сигна, "Обращение" на шине управления "Обращения"; на Фиг, 4 б показан сигнал на выбранной адресной шине; на фиг. 4 в показаны тактовые импульсы, поступающие на накопитель; на фиг, 4 г показаны тактовые импульсы, поступающие на дополнительньй накопитель; на Фиг. 4 д показан сигнал на шине установки в исходное состояние; на фиг, 4 е показаны сигналы на выходах дешифратора; на фиг, 4 ж показаны сигналы на выходе устройства.Предлагаемое ЗУ (Фиг. 1) содержит накопитель 1 на сдвиговых регистрах, состоящий из ячеек 2 памяти, элементы И З,элемент ИЛИ 4, дешифратор 5, до - полнительные группы элементов ИЛИ 6, первую группу элементов И 7, вторую группу элементов И 8, третью группу элементов И 9, дополнительный накопитель 10 на .сдвиговых регистрах состоя) щий из ячеек 11 памяти, первую группу элементов ИЛИ 12, вторую группу элементов ИЛИ 13, третью группу элементов ИЛИ 14, шины адресные 15, обращения 16, тактовую 17, дополнительную тактовую 18, установки 19 в исходное состояние, шины 20 и 21 логической единицы и нуля, соответственно. Изменяя подсоединение информационных параллельных входов накопителей 1 и 10, изменяют записываемые начальные коды чисел, тем.самым изменяют массив хранимых в устройстве чисел. Разрядность записанных в предлагаемое устройство чисел равна пг,где и и г разрядность чисел, записанных в накопители 1 и 10, причем в накопителе 1 количество ячеек 2 памяти равняется разрядности чисел, записанных в него, а в накопителе О количество ячеек 11 памяти не зависит от разрядности чисел, записанных в него.Группы элементов ИЛИ 12, ИЛИ 13, ИЛИ 14 служат для организации произся первыми разрядами г-разрядных чисел. С выхода элементов И 7, И 8 иИ 9 первой, второй и третьей группычерез элементы ИЛИ 6 дополнительныхгрупп на входы дешифратора 5 поступают сигналы, в результате действиякоторых возбуждается один из его вьгходов, с которого разрешающий сигналпоступает на второй вход соответствую щего элемента И 3, на первом входекоторого устанавливается соответствующий разряд записанного в накопителе1 начального кода числа, который является первым разрядом и-разрядного числа, которому соответствует этот разряд начального кода числа и которыйчерез элемент ИЛИ 4 поступает на выход устройства. После формированияна выходе уотройства первого разрядавыбранного числа, на тактовую шину 17подается первый тактовый сигнал, который сдвигает по кольцу на один разряд начальный код числа в накопителеподключая к выходу устройства второй разряд того же и-разрядного числа.После проведения исдвигов посредством подачи итактовых сигналов, всеи-разрядов записанного в накопителе 1числа оказываются считаннъми на выходустройства.Затем формируется и-тактовый сигнална тактовой шине 17, который, сдвинувначальный код числа на один разряд покольцу в накопителе 1, устанавливаетначальный код числа в исходное состояние, Одновременно с тактовым импульсом на тактовой шине 7. формируетсяпервый тактовый сигнал на дополнительной тактовой шине 18, который сдвигает начальный код числа в дополнительном накопителе 1 О по кольцу на одинразряд, подключая ко вторым входамэлементов И 7, И 8 и И 9 первой, второй и третьей групп втОрые разрядыг-разрядных чисел, записанных в, накопителеО, которые через элементыИЛИ 6 дополнительных групп поступаютна вход дешифратора 5 и возбуждают еговыход, с которого разрешающий сигналпоступает на первый вход соответствующего элемента И 3, тем самым подключая к выходу устройства соответствующий выход накопителя 1, т. е, первыйразряд второго и-разрядного числа, записанного в накопитель 1, После фор мирования на выходе устройства первого разряда второго и-разрядного числа(и + 1)разряда числавыбираемого изустройства), на тактовую шину 17 пода 5 86вольной выборки чисел иэ устройствапо данному адресу путем подсоединениявходов этих элементов к соответствующим адресным шинам 15, причем для выборки одного числа к выбранной адресной шине надо подключить по одномувходу одного из элементов ИЛИ 2,ИЛИ 13, ИЛИ 14, например, по одномувходу элементов ИЛИ 12.1, ИЛИ 13,1,ИЛИ 14.1 или элементов ИЛИ 12.6,ИЛИ 13.4 и ИЛИ 14.3.Прямые и обратные выходы ячеек 2памяти подсоединены к первым входамэлементов И 3, выходы которых подключены к соответствующим входам элемента ИЛИ 4, а вторые входы элементовИ 3 подкпючены к выходам дешифратора5, входы которого соединены с выходами элементов ИЛИ 6 дополнительныхгрупп, входы которьх подключены к выходам первой, второй и третьей группэлементов И 7, И 8 и И 9 соответственно вторые входы которых подключены кпрямым и обратным информационным выходам дополнительного накопителя 10, которыми являются выходы его ячеек 11памяти. Первые входы первой группыэлементов И 7 подключены к выходамэлементов ИЛИ 12 первой группы, первые входы второй группы элементов И 8подключены к выходам элементов ИЛИ 13второй группы, а первые входы третьейгруппы элементов И 9 - к выходам элементов ИЛИ 14 третьей группы. Входыэлементов ИЛИ 2, ИЛИ 13 и ИЛИ 14 первой, второй и третьей группы соответственно соединены с адресными шинами 15.Предлагаемое ПЗУ работает следующимобразом,В исходном состоянии накопители 1и 10 находятся в нулевом состоянии.При поступлении импульса "Обращение" с шины 16 обращения на входы накопителей 1 и 10 приходит разрешающийсигнал, и в накопители 1 и 10 записываются начальные коды чисел. Одновременно с поступлением импульса пОбращение" возбуждается одна выбраннаяадресная шина 15, с которой разрешающий сигнал через соответствующие элементы ИЛИ 12, ИЛИ 3 и ИЛИ 14 первой,второй и третьей групп поступает напервые входы соответствующих элементов И 7, И 8 и И 9, первой, второй итретьей групп на вторых входах которых устанавливаются соответствующиеразряды записанного в накопителе 10начального кода числа, которые являют 8835 6ются следующие (и 1) тактовых импульсов, в результате действия которых считываются остальные (и) разрядов второго числа, а на выходе устройства формируются следующие (и - 1) разрядов числа, выбираемого из устройства, После формирования на выходе устройства 2.п разрядного числа, выбираемого из устройства, формируются 2 и тактовый сигнал на тактовой шине 17, который О сдвинув начальный код числа на один разряд по кольцу в накопителе 1, уста" навливают начальный код числа в исходное состояние, Одновременно с 2 п тактовым сигналом на тактовой шине 17 формируется второй тактовый сигнал на дополнительный тактовой шине 18, который сдвигает начальный код числа в накопителе 10 по кольцу на один разряд, подключая ко вторым входам элементов И 7, 0 И 8 и И 9, первой, второй и третьей группы третьи разряды г-раэрядных чисел, записанных в накопителе 10, которые через элементы ИЛИ 6 дополнительных групп поступают на вход дешифрато ра 5 и возбуждают соответствующий его выход, с которого разрешающий сигнал поступает на первый вход соответствующего элемента И 3, тем самым подключая к выходу устройства соответствующий выход накопителя 1, т. е, первый разряд третьего и-разрядного числа, записанного в накопителе 1.После того, как из накопителя 10 считается г-разрядное число при подаче по дополнительной тактовой шине 1835 (и - 1) тактовых импульсов, а из нако-. пителя 1 считается 1 и-разрядных чисел при поступлении по тактовой шине 17 (пг - 1) тактовых импульсов, на40 выходе устройства формируется последний пг разряд числа, выбираемого из устройства,Затем на шине,19 установки в исходное состояние формируется сигнал, который устанавливает накопители 1 и 1045 в нулевое состояние. Устройство гото-во к следующему обращению.В показанном на фиг. 1 устройстве хранится 216 двадцатиразрядных двоичных чисел (6216, количество пере 3становок с повторениями из 6 элементов по 3) .В качестве начальных кодов чисел в накопителях 1 и 10 записаны коды 111 Р " и 110 соответственно, которые являют ся .кодами ориентированных циклов, образованными ориентированными Эйлеровыми графами для четырехразрядных и пятиразрядных чисел соответственно (фиг. 2 и фиг. 3). Каждому ребру графа поставлено в соответствие одно двоичное число. Замкнутая последовательность неповторякщихся ребер при их последовательном обходе в направлении стрелок образуют цикл, Для получения кода ориентированного цикла надо взять старшие разряды чисел, которым соответствуют ребра цикла при последовательном обходе цикла в направлении стрелок. Начинать обход цикла можно с любого ребра, принадлежащего данному циклу.Коду ориен.ированного цикла 1110 принадлежат числа 1110, 1101, 1011, 011. Из кода ориентированного цикла путем исдвига (где и - разрядность чисел графа) в направлении от младших разрядов к старшим (влево) получаются коды чисел, которым соответствует этоэ код ориентированного цикла11 О1011011011В результате сдвигов в столбцах получились четыре числа, которым соответствуют ребро, принадлежащее данному циклу (см, фиг. 2).Так как ячейки 2 памяти накопителя 1 имеют и обратные выходы, то фактически в накопителе 1 записаны два начальных кода: 110 и 0001. Коду 0001 также соответствует цикл в эйлеровом графе, с ребрами, которьи соответствуют числа 0001, 0010, 0100, 1000.0001001001001000Аналогично коду ориентированного цикла 110 принадлежат числа 11011, 101 О, 01101, а обратному коду ориентированного цикла 001 принадлежат числа 00100, 01001 и 100 О.ГО ОО10 010011 100110 00101 010Согласно подключению информационных параллельных входов накопителейи 10 к шинам 20 и 21 логических единицы и нуля, в ячейки памяти 2.1, 2.2, 2.3.11,1, 11,2 записывается "1", а в ячейки памяти 2.4, 1.3 записывается "0". Поэтому иа прямом и обратном выходах ячейки памяти 2.1 формируютсячисла.110 и 0001 соответственно, на выходах ячейки памяти 2.2 - числа 101 и 0010, на выходах ячейки памяти 2.3 - числа О и 0100, а на выходах ячейки памяти 2.4 памяти - числа О 11 и 3000.Аналогично формируются числа на выходах ячеек памяти 11. На прямом и обратном выходах ячейки памяти 11.1 формируются числа 31011 и 00100, на выходах ячейки памяти 11.2 - числа 10110 и 01001, и на выходах ячейки памяти 11.3 - числа 01101 и 10010.В приведенном (фнг. 1) устройстве хранятся только такие днадцатиразрядные числа, которые состоят из четы.рехразрядных чисел, записанных в накопителеЕсли к возбужденной адресной шине 15 подключить по одному входу элементов ИЛИ 12.1, ИЛИ 13.1 и ИЛИ 14.1,то на вход дешифратора 5 поступят в последовательном коде три одинаковых пятиразрядных числа, так как вторые входы соответствующих элементов И 7.1, И 8. и И 9, подключены к прямому выходу ячейки памяти 11 Таким образом, на нходы,дешифратора 5 поступят следующие трехразрядные числа в такой последовательности.1 1111000111111Если считать, что при поступлении на вход дешифратора 5 кода 000 разрешающий сигнал с его выхода поступит на первый вход элемента И 3,1 кода 001 - на первый вход элемента И 3.2 кода 010 - на первый вход элемента И 3.3 и т. д., то на выходе устройства считанное число будет 1000 1000 1110 1000 1000.Если к возбужденной адресной шине 15 подключить по одному входу элементов ИЛИ 12;6, ИЛИ 13.4 и ИЛИ 14.3, то на вход дешифратора 5 поступят в последовательном коде три разных пятиразрядных числа 30010, 01001, 101 О и в параллельном коде трехразрядные числа н такой последовательности1 О 1О 1 О0 О 1101010 Ва ныходе устройства считанное чис.ло будетО 00 3103 0001 0100 1301В предлагаемом устройстве информацию, записываемую в накопитель 1, надо представлять в виде кода одногоили нескольких ориентированных циклов,содержащих количество ребер, равноеразрядности и эйлерова графа или любому положительному делителю д числаи (д Ф 3),поэтому накопитель 1 обычносостоит из нескольких независимых регистров сдвига, причем возможно с различным количеством ячеек памяти 2. Таккак количество выходов дешифратора 5сравно 2 (с - положительное целое чис"ло), то количество ячеек памяти 2обычно равно 2Для записи чисел вида 000 и111 не требуется регистр сдвига.Для чисел вида 000 достаточно соответствующий выход дешифратора 5 ос"тавить неподключенным, а для чиселнида 11 соответствующий. выход дешифратора 5 соединить непосредственно с входом элемента ИЛИ 4.На код ориентированного цикла, записанного н дополннтельныи накопитель10 не накладывается никаких ограничений, и он определяется только массивом информации, записанным в ЗУ, поэтому количество ячеек 11 памяти накопитель 10 может быть любым, Информацию можно представить в виде нескольких кодов ориентированных циклов, тогда накопитель 10 будет состоять из нескольких независимых регистров сдвига.Объем хранимой информации в устЕог +х Г 40 ройстве равен (2 щ бит (гдещи е - количество ячеек памяти инакопителяхи 10 соответственно, ии г-разрядность чисел, записанных в накопителях 1 и О соответственно), так 41 как количество различных чисел, записанных в ЗУ равно (2 щ) (количестноперестановок с повторениями из шэлементов по С), где С - количествовходон дешифратора 5, Но так как 50 2 ш,2 р то ш,2 и С ОД 3, + 1Записанную в ЗУ информацию можноизменить путем изменения подсоединенияинформационных параллельных входовнакопителей 1 и 10 к шинам 20 и 21логических "1" и "О", тем самым записывая в накопители 1 и 1 О другие начальные коды чисел. Запись ноного начального кода числа в накопитель 1 озвно и различчеек. т устмеетия е чтоенцой начает изменение множества п-разрядных чисел, иэ которых состоят пг-разрядные числазаписанные в ЗУ. Запись нового начального кода числа в накопитель 10 означает изменение порядка размещения и-разрядных .чисел в пг-разрядных числах.В предлагаемом устройстве в сравнении с известным устройством для хранения одинакового количества разных чисел требуется меньшее количество оборудования.Пусть еч и щ- количество ячеек памяти в накопителях 1 и 10 соответственно, тогда в предлагаемое устройство можно записать(2 щ) 1Е г+ч разных слов, Для такого ЗУ требуется элементов 0 4 щ++ 2(2 щ + 1) (1 о 9 р+) .Получено это выражение следующим образом.Из фиг. 1 следует, что количество элементов И 3 щ 2 щ ИЛИ 12-Или 14 ИЛИ 4 ю 2 щ(1 о 9 щ + ) ИЛИ Ь109 щ +И 7 И 9 =1 о 9 р, + 1)Количество элементов в дешифраторезависит от типа дешифратора, Есливзять линейный дешифратор, тогда ко 30 личество элементов, требуемое для егопостроения, равно 2 + С, где С - косличество однофазных входов дешифратора, или равно2 вч+ 1 о 9 щ + 1Я чНайдем общее количество элементовЯ 2 щ+ 1 + Ь 9 щ, + 1 + 2 щ(1 оцщ++ )(1 о 9 гщ + )Таким образом, в предлагаемом ЗУколичество элементов на одно хранимоеслово равно Сравним значения Ч и цпном количестве запоминающих щ 4,щ З,щ 71 е 2 (2.3 + 1) 1 ору 4 Ф 1)4+ 1 16 + 1 + 2,7,3 17 + 42 59 63 216 216 8.7 + 1 57н" - = 0,290 (2.7) 196 4,4 + 1 + 2(2,5 + 1) (Гоц 4 + 1) 16 + 1 + 2,11,3 17 + 66 831000 1000 0,083 Как видно из приведенных ньпце расчетов, предлагаемое устройство дает выигрыш в количестве элементов на одно хранимое слово уже при щ = 7. При равном количестве ячеек памяти н предлагаемом устройстве можно хранить больше слов, так при щ = 7 ) = 216, а й 2) = 196, при щ = 9 Ч = 1000, а 22 =324.Недостатком устройства-прототипа является и то, что при хранении чисел большой разрядности приходится строить начальный код числа по графу с большим количеством ребер, так как хранимые числа разбиваются только на две части. Например, при хранении 20-ти разрядных чисел начальный код надо2 О строить.по графу, состоящему из 2 ребер, что очень трудно. Если числа разбивать на большее количестьо частей, то это вызовет увеличение количества элементов, так как количество групп элементов И и ИЛИ пропорционально количеству групп, на которое разбивается записанное число в устройствеустройстве количестрое разбивается заределяется раэрядсанных в дополнительи не вызывает увеличения количества элементов,Таким образом, из сравненияройства-прототипа с предлагаемыройством видно, что последнее ивыигрыш в количестве оборудовани доказывает достижение поставлцели, так как приводит к увеличениюбыстродействия.формула изобретенияЗапоминающее устройство, содержащее накопитель на сдвиговых регистрах, информационные входы которого соединены с соответствующими шинами логи- . 1 О ческого нуля и единицы, другие входыс соответствующими шинами установки в исходное состояние, обращение. и тактовой, а выходы - с первыми входами элементов И, выходы которых соединены 15 с соответствукзцийи входами элемента ИЛИ, группы элементов ИЛИ, входы которых соединены с соответствующими адресными шинами, о т л и ч а ю щ ее с я тем, что, с целью псвышения быстродействия устройства, оно содержит дополнительный накопитель на сдвиговых регистрах, дешифратордополнительную тактовую шину, группы элементов И и дополнительные группы элементов ИЛИ, выходы дешнфратора соединенысо вторыми входами соответствующихэлементов И, а входы - с выходамиэлементов ИЛИ дополнительных групп,входы которых соединены с выходамнэлементов И соответствующих групп,первые входы которых подключены к выходам элементов ИЛИ соответствующихгрупп, а вторые входы - к соответствующим выходам дополнительного накопителя, информационные входы которогосоединены с соответствующими шинамилогического нуля.и единицы, а другиевходы - соответственно с шинами уста-.новки в исходное состояниеобращенияи дополнительной тактовой.Источники информациипринятые во внимание при экспертизе1. Авторское свидетельство СССРУ 565326, кл. С 11 С 17/00, 1977.2. Авторское свидетельство СССРпо заявке У 2752838/18-24,кл, С 11 С 17/00, 1979 (прототип, 868835