Запоминающее устройство Советский патент 1981 года по МПК G11C19/00 

(54) ЗАПОМРШЛЩПЕ УСТРОЙСТВО

Изобретение относится к вычислительной технике и может быть использовано в запоминающих устройствах ЦВМ с последовательной обработкой информации. Известны запоминающие устройства с вьщачей информации в последовательном коде l и 2. Одно из известных запоминающих уст ройств (ЗУ) содержит регистр сдвига, шины управления, элементы И по количеству разрядов регистра и элемент ИЛИ, причем выходы разрядов регистра сдвига соединены с информационными входами элементов И, управляющие входы которых подключены к соответствующим адресным шинам, а выходы соединены со входами элемента ИЛИ, информаци онные входы регистра сдвига подключены к соответствующим шинам логических нуля и единицы, вход разрешения записи регистра сдвига соединен с шиной Обращение, а выход последнего разряда регистра сдвига подключен ко входу его первого разряда. Недостатком этого ЗУ является его сложность при хранении больвтх массивов чисел, так как количество запоминающих ячеек регистра сдвига равняется количеству хранимых чисел в ЗУ. Наиболее близким к предлагаемому изобретению является запоминающее устройство, содержащее регистр сдвига, информационные входы которого соединены соответствующими шинами логических нуля и единицы, а выходы - с информационными входами основных элементов И, выходы которых соединены с одними входами элемента ИЛИj и шины управления Обращение, тактовая шина установки в исходное состояние, к которым подключены соответствукнцие входы регистра сдвига, дополнительные элементы И, триггер, двоичный счетчик и группы элементов ИЛИ, входы которых подключены к адресным пинам, выходы элементов ИЛИ одной группы соединены С соответствующими управляющими входа ми основных элементов И, а выходы эле ментов ИЛИ другой группы соединены с соответствующими управляющими входами дополнительных элементов И, информаци онные входы которых соединены с выходами разрядов регистра одвига, а выходы подключены к соответствукяцим вхо дам элементаИЛИ, входы двоичного счетчика подключены к шинам управления Обращение , тактовой и к шине ус тановки в исходное состояние, которая подключена к нулевому входу триггера, нулевой вькод которого подключен к первому управляющему входу основных элементов И, а единичный выход - к первому управляющему входу дополнительных элементов И, единичный вход триггера соединен с выходом двоичного счетчика. В данном устройстве накопитель выполнен на сдвиговых регистрах. Недостатком известного ЗУ является его сложность при хранении массивов чисел большой разрядности, т. к, с увеличением разрядности значительно увеличивается количество ячеек памяти, так как в каждой ячейке памяти хранится два п-разрядных числа с взаимно обратш 1ми кодами. Цель изобретения - повьшение быстродействия устройства. Указанная цель достигается тем, что в запоминающее устройство, содержащее накопитель на сдвиговых регистрах, информационные входы которого соединены с соответствующими шинами логических нуля и единицы, другие вхо ды - с соответствующими шинами устано . ки в исходное состояние, обращение и тактовой, а выходы - с первыми входами элементов И, выходы которых соединены с соответствующими входами элемента ИЛИ, группы элементов ИЛИ, входы которых соединены с соответствующими адресными шинами, введены дополнительный накопитель на сдвиговых регистрах, дешифратор, дополнительную тактовую ЩИНУ, группы элементов И и дополнительные группы элементов ИЛИ, выходы дешифратора соединены со вторыми входа а1 соответствующих элементов И, а входы с выходами элементов ИЛИ дополнительных групп, входы которых соединены с выходами элементов И соответствующих групп, первью входь которых подключены к выходам элементо ИЛИ соответствующих групп, а вторые входы - к соответствующим дополнительногё накоп1ртеля, информацион ные входы которого соединены с соот ветствующими тинами логического нуля и единицы, а другие -входы - соответственно с шинами установки в исходное состояние, обращения и дополнительной тактовой. На фиг. 1 представлена блок-схема устройства хранящего 216 двадцатиразрядных двоичных чисел; на фиг. 2 и фиг. 3 представлены ориентированные Эйлеровы графы для четырехразрядных и пятиразрядных двоичных чисел; на фиг. 4 представлена временная диаграмма работы устройства; на фиг. 4а показан сигнал Обращение на шине управления Обращения ; на фиг, 46 показан сигнал на выбранной адресной шине; на фиг. 4в показаны тактовые импульсы, поступающие на накопитель; на фиг. 4г показаиы тактовые импульсы, поступаюище на дополнительн; 1й накопитель; на фиг. 4д показан сигнал на шине установки в исходное состояние; на фиг. 4е показаны сигналы на выходах дешифратора; на фиг. 4ж показаны сигналы на выходе устройства. Предлагаемое ЗУ (фиг. 1) содержит накопитель 1 на сдвиговых регистрах, состоящий из ячеек 2 памяти элементы И 3,элемент ИЛИ 4, дешифратор 5, дополнительные группы элементов ИЛИ 6, первую группу элементов И 7, вторую группу элементов И 8, третью группу элеме.нтов И 9, дополнительный накопитель 10 на .сдвиговых регистрах состоящий из ячеек И памяти, первую группу элементов ИЛИ 12, вторую группу элементов ИЛИ 13, третью группу элементов ИЛИ 14, шины адресные 15, обращения 16, тактовую 17, дополнительную тактовую 18, установки 19 в исходное состояние, шины 20 и 2 логической единицы и нуля, соответственно. Изменяя подсоединение информационных параллельных входов накопителей 1 и 10, изменяют записываемые начальные коды чисел, тем-самым изменяют массив храни ялx в устройстве чисел. Разрядность записанных в предлагаемое устройство чисел равна пг, где п и г разрядность чиселJ записанных в накопители 1 и 10, причем в накопителе 1 количество ячеек 2 памяти равняется разрядности чисел, записанных в него, а в накопителе 10 количество ячеек 11 памяти не зависит от разрядности чисел, записанных в него. Группы элементов ИЛИ 12, ИЛИ 13, ИЛИ 14 служат для организации произВОЛЬНОЙ выборки чисел из устройства по данному адресу путем подсоединения входов этих элементов к соответствующим адресным шинам 15, причем для выборки одного числа к выбранной адресной шине надо подключить по одному входу одного из элементов ИЛИ 12, ИЛИ 13, ИЛИ 14, например, по одному входу элементов ИЛИ 12.1, ИЛИ 13.1, ИЛИ 14.1 или элементов ИЛИ 12.6, ИЛИ 13.4 и ИЛИ 14.3. Прямые и обратные выходы ячеек 2 памяти подсоединены к первым входам элементов И 3, выходы которых подключены к соответствующим входам элемента ИЛИ 4, а вторые входы элементов И 3 подключены к выходам дешифратора 5, входы которого соединены с выходами элементов ИЛИ 6 дополнительных групп, входы которых подключены к выходам первой, второй и третьей групп элементов И 7, И 8 и И 9 соответстве1 но вторые входы которых подключены к прямым и обратным информационным выхо дам дополнительного накопителя 10, ко торыми являются выходы его ячеек 11 памяти. Первые входы первой группы элементов И 7 подключены к выходам элементов ИЛИ 12 первой группы, первые входы второй группы элементов И 8 подключены к выходам элементов ИЛИ 13 второй группы, а первые входы третьей группы элементов И 9 - к выходам элементов ИЛИ 14 третьей группы. Входы элементов ИЛИ 12, ИЛИ 13 и ИЛИ 14 пер вой, второй и третьей группы соответственно соединены с адресными шинами 1 5 ., Предлагаемое ПЗУ работает следунлци образом. В исходном состоянии накопители 1 и 10 находятся в нулевом состоянии. При поступлении импульса Обращение с шины 16 обращения на входы накопителей 1 и 10 приходит разрешающий сигнал, и в накопители 1 и 10 записываются начальные коды чисел. Одновременно с поступлением импульса Обращение возбуждается одна выбранная адресная шина 15, с которой разрешающий сигнал через соответствующие элементы ИЛИ 12, ИЛИ 13 и ИЛИ 14 первой, второй и третьей групп поступает на первые входы соответствукщих элементов И7,И8иИ9, первой, второй и третьей групп,на вторых входах которых устанавливаются соответствунхцие разряды записанного в накопителе 10 начального кода числа, которые являют ся первыми разрядами г-разрядных чисел. С вьрсода элементов И 7, И 8 и И 9 первой, второй и третьей группы через элементы ИЛИ 6 дополнительных групп на входы дешифратора 5 поступают сигналы, в результате действия которых возбуждается один из его выходов, с которого разрешающий сигнал поступает на второй вход соответствующего элемента И 3, на первом входе которого устанавливается соответствующий разряд записанного в накопителе 1 начального кода числа, который является первым разрядом п-разрядного числа, которому соответствует этот разряд начального кода числа и который через элемент ИЛИ 4 поступает на выход устройства. После формирования на выходе устройства первого разряда выбранного числа, на тактовую шину 17 подается первый тактовый сигнал, который сдвигает по кольцу на один разряд начальный код числа в накопителе 1, подключая к выходу устройства второй разряд того же п-разрядного числа. После проведения п-1 сдвигов посредством подачи п-1 тактовых сигналов, все п-разрядов записанного в накопителе 1 числа оказываются считанными на выход устройства. Затем формируется п-тактовый сигнал на тактовой шине 17, который, сдвинув начальный код числа на один разряд по кольцу в накопителе 1, устанавливает начальный код числа в исходное состояние. Одновременно с тактовым импульсом на тактовой шине I7, формируется первый тактовый сигнал на дополнительной тактовой шине 18, который сдвигает начальный код числа в дополнительном накопителе 10 по кольцу на один разряд, подключая ко вторым входам элементов И7, И8иИ9 первой, второй и третьей групп вторые разряды I-разрядных чисел, записанных в, накопителе 10, которые через элементы ИЛИ 6 дополнительных групп поступают на вход дешифратора 5 и возбуждают его выход, с которого разрешающий сигнал поступает на первый вход соответствующего элемента ИЗ, тем самым подключая к выходу устройства соответствующий выход накопителя 1, т. е, первый разряд второго п-разрядного числа, записанного в накопитель 1, После форирования на выходе устройства первого разряда второго п-разрядного числа (п - 1)разряда числа,выбираемого из стройства), на тактовую шину 17 пода- ются следукщие (п - 1) тактовых импульсов, в результате действия которых счйтьюаются остальные (п- 1) разрядов второго числа, а н,а выходе устройства формируются следующие (п - 1) разрядов числа, выбираемого из устройства. После форьшрования на выходе устройства 2 П разрядного числа, выбираемого из устройства, формируются 2 п тактовый сигнал на тактовой шине 17, который сдвинув начальный код числа на один разряд по кольцу в накопителе , устанавливают начальный код числа в исходное состояние. Одновременно с 2 п тактовым сигналом на тактовой шине 17 фор мируется второй тактовый сигнал на дополнительньй тактовой шине 18, который сдвигает начальный код числа в накопителе 10 по кольцу на один разряд, подключая ко вторым входам элементов И 7 И 8 и И 9, первой, второй и третьей группы третьи разряды г-разрядных чисел, записанных в накопителе 10, которые через элементы ИЛИ 6 дополнительных групп поступают на вход дешифратора 5 и возбуждают соответствующий его выход, с которого разрешающий сигнал поступает на первый вход соответствую щего элемента И 3, тем самым подключа к выходу устройства соответствующий выход накопителя 1, т. е. первый разряд третьего п-разрядного числа, записаннэго в накопителе 1. После того, как из накопителя 10 считается i-разрядное число при подаче по дополнительной тактовой шине 18 (п - 1) тактовых импульсов, а из нако пителя 1 считается I п-разрядных чисел при поступлении по тактовой шине 17 (пг - 1) тактовых импульсов, на выходе устройства формируется последний пг разряд числа, выбираемого из устройства. Затем на шине,19 установки в исход ное состояние формируется сигнал, который устанавливает накопители 1 и 10 в нулевое состояние. Устройство готово к следующему обращению. В показанном-на фиг. 1 устройстве хранится 216 двадцатиразрядных двоичных чисел (6 216, количество перестановок с повторениями из 6 злементов по 3) . В качестве начальных кодов чисел в накопителях 1 и 10 записаны коды 1110 И 110 соответственно, которые являются кодами ориентированных циклов, образованными ориентированными Эйлеровы ми графами для четырехразрядньк и пятиразрядных чисел соответственно (фиг. 2 и фиг. З), Каждому ребру графа поставлено в соответствие одно двоичное число. Замкнутая последовательность неповторяюоощхся ребер при их последовательном обходе в направлении стрелок образуют цикл. Для получения кода ориентированного цикла надо взять старшие разряды чисел, которым соответствуют ребра цикла при последовательном обходе цикла в направлении стрелок. Начинать обход цикла можно с любого ребра, принадлежащего данному циклу. Коду ориен.-ированного цикла 1110 принадлежат числа 1110, 1101, 1011, 0111. Из кода ориентированного цикла путем п-1 сдвига (где п - разрядность чисел графа) в направлении от м. разрядов к старшим (влево) получаются коды чисел, которым соответствует этот код ориентированного цикла В результате сдвигов в столбцах получились четыре числа, которым соответствуют ребро, принадлежащее данному циклу (см. фиг. 2). Так как ячейки 2 памяти накопителя. 1 имеют и обратные выходы, то фактически в накопителе I записаны два начальных кода: 1110 и 0001. Коду 0001 также соответствует цикл в эйлеровом графе, с ребрами, которым соответствуют числа 0001,0010, 0100, 1000. Аналогично коду ориентированного цикла ПО принадлежат числа ПОИ, 10110, 01101, а обратному коду ориентированного цикла 001 принадлежат числа 00100, 01001 и 10010. TW бо 101 010 011 100 ПО 001 . 101 010 Согласно подключению информационных параллельш,1х входов накопителей I и 10 к шинам 20 и 2I логических единицы и нуля, в ячейки памяти 2.1, 2.2, 2.3.П.1, 11.2 записывается 1, а в ячейки памяти 2.4, П.З записывается О, Поэтому на прямом и обратном выходах ячейки памяти 2.1 формируются числа.1110 и 000Г соответственно, на выходах ячейки памяти 2.2 - числа N01 и 0010, на выходах ячейки памяти 2.3 - числа lull и 0100, а на выходах ячейки памяти 2.А памяти - чис ла 0111 и 1000. Аналогично формируются числа на выходах ячеек памяти П. На прямом и обратном выходах ячейки памяти 11.1 формируются числа ПОП и 00100, на выходах ячейки памяти 11.2- числа 10110 и 01001, и на выходах ячейки памяти 11.3 - числа 01101 и 10010. В приведенном (фиг. 1) устройстве хранятся только такие двадцатиразряд ные числа, которые состоят из четы-рехразрядных чисел, записанных в нак пителе I . Если к возбужденной адресной шине 15 подключить по одному входу элемен тов ИЛИ 12.1, ИЛИ 13.1 и ИЛИ 14.1,то на вход дешифратора 5 поступят в последовательном коде три одинаковых пятиразрядных числа, так как вторые входы соответствующих элементов И 7-. И 8.1 и И 9.1 подключены к прямому выходу ячейки памяти 11.1. Таким образом, на входы.дешифратора 5 постучисла в пят следугацие трехразрядные такой последовательности. Ill 1 I Если считать, что при поступлении на вход дешифратора 5 кода 000 разре шаюишй сигнал с его выхода поступит на первый вход элемента И 3,I кода 001 - на первый вход элемента И 3.2 кода 010 - на первый вход элемента И 3.3 и т. д., то на выходе устройства считанное число будет 1000 1000 1I10 1000 1000. Если к возбужденной адресной шине 15 подключить по одному входу элементов ИЛИ 12.6, ИЛИ 13.4 и ИЛИ 14.3, то на вход дешифратора 5 поступят в последовательном коде три разных пятиразрядных числа J0010, 01001, 10110 и в параллельном коде трехразрядные числа в такой последовательности 101 О I О ha выходе устройства считанное число будет 0100 1101 0001 0100 1101 В предлагаемом устройстве информацию, записываемую в накопитель 1, надо представлять в виде кода одного или нескольких ориентированных циклов, содержащих количество ребер, равное разрядности п эйлерова графа или любому положительному делителю d числа п (d f 1), поэтому накопитель 1 обычно состоит из нескольких независимых регистров сдвига, причем возможно с различным количеством ячеек памяти 2. Так как количество выходов дешифратора 5 равно 2 (с - положительное целое число) , то количество ячеек памяти 2 обычно равно 2. Дпя записи чисел вида 00...О и 11...I не требуется регистр сдвига. Дпя чисел вида 00...О достаточно соответствующий выход дешифратора 5 оставнть неподключенным, а для чисел вида 1 1... I соответствующий выход дешифратора 5 соединить непосредственно с входом- элемента ИЛИ 4. На код ориентированного цикла, записанного в дополнительный накопитель 10,не накладывается никаких ограни-чений, и он определяется только массивом информации, записанным в ЗУ, поэтому количестпо ячеек 1I памяти накопитель 10 может быть любым. Информацию можно представить в виде нескольких кодов ориентированных циклов, тогда накопитель 10 будет состоять из нескольких независимых регистров сдвига. Объем хранимой информации в устtocfrrt , -- X nV . ройстве равен (2mnJ бнт (где m , и т количество ячеек памяти и накопителях 1 и 10 соответственно, п и г-разрядность чисел,записанных в накопителях 1 и 10 соответственно), так как количество различных чисел, записанных в ЗУ, равно (2т) (количество перестановок с повторениями из тл элементов по С) , где С - количество входов дешифратора 5. Но так как 2т 2, то т - и С log,n + I. Записанную в ЗУ информацию можно изменить путем изменения подсоединения информационных параллельных входов накопителей 1 и 10 к шинам 20 и 21 логических 1 и О, тем самым записывая в накопители 1 и 10 другие начальные коды чисел. Запись нового начального кода числа в накопитрль I оз18начает изменение множества п-разрядных чисел, из которых состоят пг-разрядные числа.записанные в ЗУ. Запись нового начального кода числа в накопитель 10 означает изменение порядка размещения п-разрядных чисел в пг-раз рядных числах. В предлагаемом устройстве в сравнении с известным устройством для хранения одинакового количества разны чисел требуется меньшее количество оборудования. Пусть га и количе.ство ячеек памяти в накопителях 1 и 10 соответст венно, тогда в предлагаемое устройство можно записать N (2т) разных слов. Для такого ЗУ требуется элементов Q 4т + I + 2(2 + ) ( О. Получено это выражение следующим образом. I следует, что количество Из фиг. элементов ИЛИ 1 2-Или 14 г И 3 « 2 т 2m( ИЛИ 4 - 1 + 1 И 7 И 9 ИЛИ 6 Jog m 2т( + l Количество элементов в дешифратор зависит от типа дешифратора. Если взять линейный дешифратор, тогда количество элементов, требуемое для ег построения, равно 2 + С, где С - ко личество однофазных входов дешифрато или равно 2т + + Найдем общее количество элементов Q 2т + 1 + tog,m + 1 + 1) + 2m,j( - 1) + 2m + f log-m + I « 1 + 2( ) + I) 4m + 1 + 2(2m2 + fmo I 1). Таким образом, в предлагаемом ЗУ количество элементов на одно хранимое слово равно Q .Я. /. J. Л,Я..1. А1.Ц.°. В устройстве-прототипе q, равно 8т + 1 Сравним значения q и q при разли ном количестве запоминающих ячеек. mА 4, m . 4. 1 2 (2.3 + l)(1oga4 l) ., 17 + Д2 216 0,290 5, m 9 4.4 + 1 + 2(2.5 и- ){1одг + Jl Я (2.5) 17-1-66 83 0,225 Как видно из приведенных вьпие расчетов, предлагаемое устройство дает выигрыш в количестве элементов на одно хранимое слово уже при m 7. При равном количестве ячеек памяти в предлагаемом устройстве можно хранить больше слов, так при , а N „ 196, при m 9 N 1000, а М„ 324. Недостатком устройства-прототипа является и то, что при хранении чисел большой разрядности приходится строить начальный код числа по графу с большим количеством ребер, так как хранимые числа разбиваются только на две части. Например, при хранении 20-ти разрядных чисел начальный код надо строить по графу, состоящему из 2 ребер, что очень трудно. Если числа разбивать на большее количество частей, то это вызовет увеличение количества элементов, так как количество групп элементов И и ИЛИ пропорциональ О количеству групп, на которое разбивается записанное число в устройствепрототипе. В предлагаемом устройстве количество частей, на которое разбивается записанное число, определяется разрядностью чисел, записанных в дополнительный накопитель 10 и не вызывает увеличения количества элементов. Таким образом, из сравнения устройства-прототипа с предлагаемым устройством видно, что последнее имеет выигрыш в количестве оборудования, что и доказывает достижение поставленной

цели,-так как приводит к увеличению быстродействия.

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

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

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

кл. G 11 С 17/00, 1979 (про -отип).

то

piios

0011

ww

Фи1.1

QOOOO

i-J

LJT JTJlJlJljnJlJlJl 1ЛП

LJi

1

L.

-J

L. rijnjlJ-LrL ™ П TL