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

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

Иллюстрации

Показать все

Реферат

 

(72) Автор изобретения

В, И. Шилинговский (71) Заявитель (54 ) 3 АПОК 01А10КГЕ УСТРОЙСТВО коде I1) и (2).

Изобретение относится к вычислительной технике и может быть использовано в запоминающих устройствах

1JBM с последовательной обработкой информации.

Известны запоминающие устроистна с выдачей информации в последовательном

Одно из известных запоминающих устройств (ЗУ) содержит регистр сдвига, fO шины управления, элементы И по количеству разрядов регистра и элемент

ИЛИ, причем выходы разрядов регистра сдвига соединены с информационными

l5 входами элементов И, управляющие входы которых подключены к соответствующим адресным шинам, а выходы соедине— ны со входами элемента ИЛИ, информационные входы регистра сдвига подключены к соответствуюшим шинам логических нуля и единицы, вход разрешения записи регистра сдвига соединен с шиной

"Обращение", а выход последнего разряда регистра сдвига подключен ко вхоцу его первого разряда.

Недостатком этого ЗУ является его сложность при хранении больших массивов чисел, так как количество запоминающих ячеек регистра сдвига равняется количеству хранимых чисел в ЗУ.

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

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

868835 с соответствующими управляющими входами основных элементов И, а выходы эле" ментов ИЛИ другой группы соединены с соответствующими управляющими входами онные входы которых соединены с выходами разрядов регистра, сдвига, а выходы подключены к соответствующим входам элемента ИЛИ, входы двоичного счетчика подключены к шинам управле10 ния "Обращение", тактовой и к шине установки в исходное состояние, которая подключена к нулевому входу триггера, нулевой выход которого подключен к первому управляющему входу основных элементов И, а единичный выход — к первому управляющему входу дополнительных элементов И, единичный вход триггера соединен с выходом двоичного счетчика, В данном устройстве накопитель выполнен на сдвиговых регистрах.

Недостатком известного ЗУ является его сложность при хранении массивов чисел большой разрядности, т. к. с увеличением разрядности значительно увеличивается количество ячеек памяти, так как в каждой ячейке памяти хранится два и-разрядных числа с взаимно обратными кодами.

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

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

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

ИЛИ дополнительных групп, входы которых соединены с выходами элементов И соответствующих групп, первйе входы

50 которых подключены к выходам элементов 55

ИЛИ соответствукщих групп, а вторые входы — к сортветствующим выходам дополнительногд накопителя, информациондополнительных элементов И, информаци- 5 ные входы которого соединены с соо1= ветствующими шинами логического нуля и единицы, а другие входы — соответ;— ственно с шинами установки в исходное состояние, обращения и дополнительной тактовой.

На фиг. l представлена блок-схема устройства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, обращения lб, тактовую 17, дополнительную тактовую 18, установки 19 в исходное состояние, шины 20 и 21 логической единицы и нуля, соответственно. Изменяя подсоединение информационных параллельных входов накопителей l и !О, изменяют записываемые начальные коды чисел, тем самым изменяют массив хранимых в устройстве чисел. Разрядность записанных в предлагаемое устройство чисел равна пг,где и и r разрядность чисел, записанных в накопители 1 и 10, причем в накопителе 1 количество ячеек 2 памяти равняется разрядности чисел, записанных в него, а в накопителе 1О количество ячеек 11 памяти не зависит от разрядно сти чисел, з аписанных в него.

Группы элементов ИЛИ 12, ИЛИ 13, ИЛИ 14 служат для организации произся первыми разрядами r-разрядных чисел. С выхода элементов И 7, И 8 и

И 9 первой, второй и третьей группы через элементы ИЛИ 6 дополнительных групп на входы дешифратора 5 поступают сигналы, в результате действия которых возбуждается один из его вьг ходов, с которого разрешающий сигнал поступает на второй вход соответствующего элемента И 3, на первом входе которого устанавливается соответствующий разряд записанного в накопителе

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

I, подключая к выходу устройства второй разряд того же и-разрядного числа.

После проведения и-1 сдвигов посредстВоМ подачи и-1 тактовых сигналов, все n-разрядов записанного в накопителе 1 числа оказываются считаннъ|ми на выход

ЗО ус ройс ва

Затем формируется и-тактовый сигнал на тактовой шине 17, который, сдвинув начальный код числа на один разряд по кольцу в накопителе I устанавливает начальный код числа в исходное состо35 яние. Одновременно с тактовым импульсом на тактовой шине 17. формируется первый тактовый сигнал на дополнительной тактовой шине 18, который сдвигает начальный код числа в дополнитель40 ном накопителе 10 по кольцу на один разряд, подключая ко вторым входам элементов И 7, И 8 и И 9 первой, второй и третьей групп втОрые разряды

r-разрядных чисел, записанных в, нако45 пителе IO которые через элементы

ИЛИ 6 дополнительных групп поступают на вход дешифратора 5 и возбуждают его выход, с которого разрешающий сигнал поступает на первый вход соответствующего элемента И 3, тем самым подключая к выходу устройства соответствующий выход накопителя 1, т. е. первый разряд второго и-разрядного числа, записанного в накопитель I, После фор55 .мирования на выходе устройства первого разряда второго и-разрядного числа (и + 1)разряда числа выбираемого из устройства), на тактовую шину 17 пода5 86 вольной выборки чисел иэ устройства по данному адресу путем подсоединения входов этих элементов к соответствующим адресным шинам 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 соответственно вторые входы которых подключены к прямым и обратным информационным выходам дополнительного накопителя I О,,которыми являются выходы его ячеек 11 памяти. Первые входы первой группы элементов И 7 подключены к выходам элементов ИЛИ 12 первой группы, первые входы второй группы элементов И 8 подключены к выходам элементов ИЛИ 13 второй группы, а первые входы третьей группы элементов И 9 — к выходам элементов ИЛИ 14 третьей группы. Входы элементов ИЛИ 12, ИЛИ 13 и ИЛИ 14 первой, второй и третьей группы соответственно соединены с адресными шинами 15.

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

В исходном состоянии накопители 1 и 10 находятся в нулевом состоянии.

При поступлении импульса "Обращение" с шины 16 обращения на входы накопителей 1 и 10 приходит разрешакиций сигнал, и в накопители 1 и 10 записываются начальные коды чисел. Одновременно с поступлением импульса "06paщение" возбуждается одна выбранная адресная шина 15, с которой разрешающий сигнал через соответствующие элементы ИЛИ 12, ИЛИ 13 и ИЛИ 14 первой, второй и третьей групп поступает на первые входы соответствующих элементов И 7, И 8 и И 9, первой, второй и третьей групп на вторых входах кото1 рых устанавливаются соответствуиицие разряды записанного в накопителе 10 начального кода числа, которые являют8835 6

868835 ются следующие (n 1) тактовых импульсов, s результате действия которых считываются остальные (n- 1) разрядов второго числа, а на выходе устройства

Формируются следующие (и — 1) разрядов числа, выбираемого из устройства, После формирования на выходе устройства

2. п разрядного числа, выбираемого из устройства, формируются 2 и тактовый сигнал на тактовой шине 17, который )0 сдвинув начальный код числа на один разряд по кольцу в накопителе 1, уста" навливают начальный код числа в исходное состояние, Одновременно с 2 и тактовым сигналом на тактовой шине 17 фор-)5 мируется второй тактовый сигнал на дополнительный тактовой шине )8, который сдвигает начальный код числа в накопителе IO по кольцу на один разряд, подключая ко вторым входам элементов И 7, 0

И 8 и И 9, первой, второй и третьей группы третьи разряды r-разрядных чисел, записанных в накопителе 10, которые через элементы ИЛИ 6 дополнительных групп поступают на вход дешифрато- 5 ра 5 и возбуждают соответствующий его выход, с которого разрешающий сигнал поступает на первый вход соответствующего элемента И 3, тем самым подключая к выходу устройства соответствующий выход накопителя 1, т. е. первый разряд третьего и-разрядного числа, записанного в накопителе 1.

После того, как из накопителя 10 считается г-разрядное число при подаче по дополнительной тактовой шине 18

35 (n 1) тактовых импульсов, а из нако-. пителя I считается 1 п-разрядных чисел при поступлении по тактовой шине

17 (пг — 1) тактовых импульсов, на

40 выходе устройства формируется последний nr разряд числа, выбираемого из устройства.

Затем на шине,19 установки в исходное состояние формируется сигнал, который устанавливает накопители 1 и 10

45 в нулевое состояние. Устройство гото- во к следующему обращению.

В показанном на фиг. ) устройстве хранится 216 двадцатиразрядных двоичных чисел (6 216 количество пере3 становок с повторениями из 6 элементов по 3) .

В качестве начальных кодов чисел в накопителях 1 и 10 записаны коды I I IP " и 110 соответственно, которые являются .кодами ориентированных циклов, образованными ориентированными Эйлеровы1 ми графами для четырехразрядных и пятиразрядных чисел соответственно (фиг. 2 и фиг. 3). Каждому ребру графа поставлено в соответствие одно двоичное число. Замкнутая последовательность неповторякщихся ребер при их последовательном обходе в направлении стрелок образуют цикл. Для получения кода ориентированного цикла надо взять старшие разряды чисел, которым соответствуют ребра цикла при последовательном обходе цикла в направлении стрелок. Начинать обход цикла можно с любого ребра, принадлежащего данному циклу.

Коду ориен.ированного цикла l))0 принадлежат числа 1110, 1101, 10)I, OlI1. Из кода ориентированного цикла путем и-1 сдвига (где n — разрядность чисел графа) в направлении от младших разрядов к старшим (влево) получаются коды чисел, которым соответствует этоэ код ориентированногo цикла

1!10

1IOl

1011

01)

В результате сдвигов в столбцах получились четыре числа, которым соответствуют ребро, принадлежащее данному циклу (см. фиг. 2).

Так как ячейки 2 памяти накопителя

1 имеют и обратные выходы, то фактически в накопителе I записаны два начальных кода: 1110 и 0001. Коду 000) также соответствует цикл в эйлеровом графе, с ребрами, которьи соответствуют числа OOOI, 0010, 0100, )000.

000)

Аналогично коду ориентированного цикла 110 принадлежат числа 11011, 101!0 01101, а обратному коду ориентированного цикла 001 принадлежат числа 00100, 01001 и IOO!0.

Г!О 001

l0I 010

011 100

110 00!

101 010

Согласно подключению информационных параллельных входов накопителей ! и 10 к шинам 20 и 21 логических единицы и нуля, в ячейки памяти 2.1, 2.2, 2.3.11,1 11.2 записывается "1", а в ячейки памяти 2.4, I!.3 записывается

"0". Поэтому иа прямом и обратном выходах ячейки памяти 2.1 формируются

868835

lO числа.!110 и 0001 соответственно, на выходах ячейки памяти 2.2 — числа

1101 и 0010, на выходах ячейки памяти 2.3 - числа 101! и 0100, а на выходах ячейки памяти 2.4 памяти — числа 031! и 1000.

Аналогично формируются числа на выходах ячеек памяти 1!. На прямом и обратном выходах ячейки памяти 11.1 формируются числа 110)l и 00100, на выходах ячейки памяти )3.2 — числа

10110 и 01001, и на выходах ячейки памяти 11.3 — числа 0110) и 10010.

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

Если к возбужденной адресной шине

15 подключить по одному входу элементов ИЛИ 12.1 ИЛИ 13.1 .и ИЛИ 14.1 то на вход дешифратора 5 поступят в последовательном коде три одинаковых пятиразрядных числа, так как вторые входы соответствующих элементов И 7.3>

И 8.1 и И 9.1 подключены к прямому выходу ячейки памяти Il.!. Таким образом, на нходы,дешифратора 5 поступят следующие трехразрядные числа в такой последовательности.

1 1

1 1 I

1 1 1

1 1 I

Если считать, что при поступлении на вход дешифратора 5 кода 000 разрешающий сигнал с его выхода поступит на первый вход элемента И 3,1 кода

0OI — на первый вход элемента И 3.2 кода OIO — на первый вход элемента

И 3.3 и т. д., то на выходе устройства считанное число будет 1000

IOOO lllO 1000 1000.

Если к возбужденной адресной шине

l5 подключить по одному входу элементов ИЛИ 12;6, ИЛИ 13.4 и ИЛИ 14.3, то на вход дешифратора 5 поступят в последовательном коде три разных пятиразрядных числа )0010, 01001, )0)10 и в параллельном коде трехразрядные числа в такой последовательности

1 О 1

О 1 О

О 0 l

101

О 1 О

ha ныходе устройства считанное число будет

О!00 3101 0001 0100 !)О!

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

n (d Ф 1),поэтому накопитель I обычно состоит из нескольких независимых регистров сдвига, причем возможно с различным количеством ячеек памяти 2. Так как количество выходов дешифратора 5 с равно 2 (с — положительное целое чис" ло), то количество ячеек памяти 2 обычно равно 2

Для записи чисел вида 00...0 и

ll...1 не требуется регистр сдвига.

Для чисел вида 00...0 достаточно соответствующий выход дешифратора 5 ас" тавить неподключенным, а для чисел нида !1...1 соответствующий. выход дешифратора 5 соединить непосредственно с входом элемента ИЛИ 4.

На код ориентированного цикла, записанного н дополннтельныи накопитель

10 не накладывается никаких ограни-. чений, и он определяется только массивом информации. записанным в ЗУ, поэтому количество ячеек ll памяти накопитель 10 может быть любым. Информацию можно представить в виде нескольких кодов ориентированных циклов, тогда накопитель 10 будет состоять из нескольких независимых регистров сдвига.

Объем хранимой информации в устI

Еог ;.

Х him

40 ройстве равен (2m J бит (где

m „ и m — количество ячеек памяти и накопителях и 10 соответственно, и и r-разрядность чисел, записанных в накопителях 1 и IO соответственно), так

41 как количество различных чисел, записанных в ЗУ равно (2m„) (количестно перестановок с повторениями из m элементов по С), где С вЂ” количество входон дешифратора 5. Но так как у3 2а„2, то m„ 2 " и с = !одр,, + 1.

Записанную в ЗУ информацию можно изменить путем изменения подсоединения информационных параллельных входов накопителей 1 и 10 к шинам 20 и 21 логических "I" и "0", тем самым записывая в накопители 1 и 10 другие начальные коды чисел. Запись ноного начального кода числа в накопит>.ль I оз868835 начает изменение множества и-разрядных чисел, иэ которых состоят nr-разрядные числа записанные в ЗУ. Запись нового начального кода числа в накопитель 10 означает изменение порядка размещения и-разрядных .чисел в nr-разрядных числах.

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

Пусть еч и m ч — количество ячеек памяти в накопителях 1 и 10 соответственно, тогда в предлагаемое устройстso можно записать !{! (2m ) е разных слов, Для такого ЗУ требуется элементов Q 4mÄ + + 2(2m< + I) (1Ярч + 1) °

Получено это выражение следующим образом.

Из фиг. I следует, что количество элементов

И32щ„ ИЛИ 12-Или 14

ИЛИ 4 2m (1og m„+ 2

ИПИЬ** logm + И7 И9=

2щ (1о92m „+ 1)

Количество элементов в дешифраторе зависит от типа дешифратора. Если взять линейный дешифратор, тогда ко30 личество элементов, требуемое для его построения, равно 2 + С, где С вЂ” кос личество однофазных входов дешифратора, или равно

2m„+ logm + l

Я ч

Найдем общее количество элементов

Я 2щ„+ l + Eog

+ 1) + 2m<(log2m< + 1) + 2m„+

+ log щч + 4m„+ l + 2((ogham„+ 1)+

+ 4m2! Iog4m< + !) 4m + 1 + 2{2 2 t

+ 1)(loog2mm„" 1).

Таким образом, в предлагаемом ЗУ количество элементов на одно хранимое слово равно

В устройстве"прототипе q> равно !

} 8m+ 1

)ч

Ц. mmm» ВВ 50 (2m ), СРавним значениЯ q и 1п пРи Различном количестве запоминающих ячеек. щ 4, щ З,щ 7 .1

4.4+ 1+ 2 (2.3 + 1) (1оуу 4 + 1)

0 4 + 1

l6 + l + 2 7 3 17 + 42 59

63 216 216

= 0,273

8.7 + 1 57

Ч вЂ” = 0,290 (2. 7) 196

4.4 + 1 + 2(2.5 + 1) (fog 2 4 + i) 2,5

16 + 1 + 2.11 3 17 + 66 83

1000 1000

0,083

8.9 + 73

g (2.9) 324

0,225 чения количества элементов.

Таким образом, из сравнения устройства-прототипа с предлагаемым устройством видно, что последнее имеет выигрыш в количестве оборудования, что и доказывает достижение поставленной

Как видно из приведенных эь()((е расчетов, предлагаемое устройство дает выигрыш в количестве элементов на одно хранимое слово уже при m = 7. При равном количестве ячеек памяти н предлагаемом устройстве можно хранить больше слов, так при m = 7 !)! = 216, а !

{!2) = 1962 при m = 9 Ч = 1000, à Nn =

324.

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

В предлагаемом устройстве количество частей, на которое разбивается записанное число, определяется разрядностью чисел, записанных в дополнительный накопитель 10 и не вызывает увели13

868835

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

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

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

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

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

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

У 565326, кл. С !1 С 17/00, 1977.

2. Авторское свидетельство СССР по эаявке М 2752838/18-24, кл. G 11 С 17/00, 1979 (про"отип).

868835

Заказ 8340/75

Тираж 648 Подписное

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

ll3035, Москва, Ж-35, Раушская наб., д. 4/5

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

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

Редактор Е. Спиридонова Техред C.Èèãóíoàà Корректор С. Шекмар