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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР (21) 4327423/24-24 (22) 10.11.87 . (46) 07.11.89. Бюл. ¹ 41 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) В.И.Корнейчук, А.П.Марковский, А.Ю.Михайлюк, Е.А,Осадчий и Ф.Ф.Галилейский (53) 681.307.6(088.8) (56) Авторское свидетельство СССР № 1179429, кл. G 11 С 11/00, 1985.

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

¹ 1177856, кл. G 11 С ll/00, 1985. (54) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике и может быть использовано при построении устройств

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

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

На фиг.1 приведена структурная схема запоминающего устройства;. на фиг.2 — структурная схема одного из вариантов блока управления; на фиг.3блок-схема алгоритма работы блока управления в режиме считывания; на фиг.4 — 6 — блок-схема алгоритма работы блока, управления в режиме записи.

Запоминающее устройство имеет (фиг.1) первый регистр 1 адреса, адресные входы 2, первый выход 3 блока

„„SU„„1520592 (51)4 G 11 С 11/00

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

1 табл. 6 ил.

4 управления, блок 5 архивной памяти, второй 6 и третий 7 выходы блока управления, первый блок 8 сравнения, первый 9 и второй 10 входы блока управления, информационные выходы 11, регистр !2 слов, четвертый 13 и пятый 14 выходы блока управления, информационные входы 15 блока 16 памяти кодов, регистр 17 кодов, шестой

18 и седьмой 19 выходы блока управления, второй регистр -20 адреса, . восьмой 21, девятый 22, десятый 23 и одиннадцатый 24 выходы блока управления, входной регистр 25, информационные входы 26, первый 27 коммутатор, двенадцатый выход 28 блока управления, выход 29 блока памяти кодов, второй 30 и третий 3! коммута152059? торы, вспомогательный регистр 32, четвертый коммутатор 33, регистр 34 свободной ячейки, тринадцатый 35 и четырнадцатый 36 выходы блока

5 управления, счетчик 37, пятнадцатый

38, шестнадцатый 39, семнадцатый 40 и восемнадцатый 41 выходы блока управления, второй блок 42 сравнения, блок элементов И 43, сумматор 44, сдвигающий регистр 45, девятнадцатый 46, двадцатый 47, двадцать первый 48, двадцать второй 49 и двадцать третий 50 выходы блока управления, третий вход 51 блока управления, входы записи 52, чтения 53 и установки 54 в исходное состояние, сигнальный вход 55, выход 56 переполнения блока управления и двадцать четвертый выход 57 блока управления. 20

Блок управления (фиг.2) имеет вход синхронизации 58 устройства, блок 59 постоянной памяти микропрограмм, регистр 60 микрокоманды,счетчик 61 адреса и блок 62 мультиплексоров.

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

Все запоминаемые слова и их коды хранятся в блоке 16 памяти кодов, ячейка которого в первой группе разрядов хранит одно запоминаемое слово, а во второй группе разрядов — 40 соответствующий ему код. При загрузке системы слова (и их коды) размещаются в блоке 16 памяти кодов в порядке возрастания, что позволяет вес" . ти бинарный поиск. Адрес первой не- 45 занятой ячейки блока 16 памяти кодов заносится в регистр 34 свободной ячейки. Если некоторое слово запоминается впервые, то оно заносится в блок 16 памяти кодов и снабжается кодом, равным среднему арифметическому кодов в соседних ячейках.

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

Для подготовки устройства к работе на вход 54 блока 4 управления по55 дается импульс, устанавливающий его в начальное состояние. После этого на вход 53 (52) блока 4 управления поступает сигнал, переводящий его в режим считывания записи информации, а на адресный вход 2 устройства подается код адреса, по которому информация должна быть считана (записана).

При работе блока 4 управления в режиме считывания (фиг.3) каждый блок (кроме проверки условия) описывает состояние выходов блока 4 управления в течение одного тактового периода., С(...) — сигнал на соответствующем входе-выходе. На блок-схемах фиг.3 — 6 показаны сигналы, имеющие значения логической "1". Не приведенные в блоках сигналы на протяжении соответствующего тактового периода полагаются равными нулю..

В первом тактовом периоде (блок 1, фиг.3) адрес считываемой информации записывается в регистр 1 (С(3)=!) и подается на адресный вход блока 5 памяти, который переведен в режим считывания сигналом с выхода 6 блока 4 управления. Вследствие этого с информационного выхода блока 5 памяти на первый вход блока 8 сравнения поступает код считываемого слова. Выход регистра 12 переведен в высокоомное состояние сигналом С(14)=1. Одновременно с этим происходит обнуление регистра 32 (С(40)=1). Кроме того, с выхода регистра 34 через второй вход коммутатора 33 (так как С(36)=0, в счетчик 37 переписывается (С(38) 1) число, являющееся адресом первой свободной ячейки блока 16 памяти, поступающее на второй вход сумматора 44, на первый вход которого подан код числа 9. Код числа N с выхода сумматора 44 подается на информационный вход регистра 45 и записывается в него вследствие С(47) =1.

В следующем такте (блок 2,фиг.3) в регистре 45 по сигналу C(48)=l данный код сдвигается вправо с потерей младшего разряда H заполнением старшего разряда нулем. Таким образом, на информационный вход регистра 20 поступает код числа (—, где квадратные скобки означают целую часть заключенного в них выражения. По .сигналу С(19) 1 данный код заносится в регистр 20 и подается на адресный . вход блока 16 памяти, переведенного в режим считывания сигналом C(21) I. Из

Э 15 блока 16 памяти считмнается содержи1И мое ячейки с адресом 1 —, причем записанный в ней код,со второй группы 291 разрядов выходной шины 29 через второй вход коммутатора,27 (так как С(28)=9) проходит на второй вход блока 8 сравнения. Если данный код больше кода, поданного на первый вход блока 8 сравнения, то на первом выходе последнего формируется единица, подаваемая на вход 9 блока 4 управления, Это влечет за собой то, что

s следующем тактовом периоде (блок 4, фиг.3) иэ регистра 45 через второй вход коммутатора 31 (C(5=)=9) и первый вход коммутатора 33 (С(36) l) в счетчик 37 записывается (так как н1

С(38) 1) код числа 1 — 1 . В резуль 2 . тате на выходе сумматора 44 формиру я 1 ется код —, 1, который записывается в регистр 45 (С(47)"1).

Если имеет место обратное соотношение кодов на входах блока 8 сравнения, то сигнал высокого уровня появляется на втором его выходе и поступает на вход 10 блока 4 управления. В этом случае в следующем тактовом периоде (блок 6, фиг.3) код чи" сла — 1 с выхода коммутатора 31 эа 2 писывается в регистр 32 (С(41)1) °

В результате с выхода сумматора 44 на информационный вход регистра 45 по3N дается код числа—

После этого устройство работает аналогично описанному..В последующем (блок 2, фиг.3) такте код, занесенный в регистр 45, сдвигается вправо и записывается в регистр 20, что вызывает считывание содержимого ячейки блока 16 памяти, имеющей адГN1 3

pec () (или N ).и т.д. Таким образом осуществляется бинарный поиск в блоке 16 памяти ячейки, содержащей во второй rpyIIIIe своих разрядов код, идентичный считанному из блока

5 памяти. В момент ее нахождения на обоих выходах блока 8 сравнения присутствующее извлеченному из блока 5 памяти коду. После этого (блок 8, фиг.3) с выхода регистра 12 слово проходит на информационный выход 11

20592 6 запоминающего устройства (C(14) =9) .

Блок 4 упранления формирует логи— и и ческую I на выходе 55; которая по5 ступает на сигнальный выход 55 устройства, сигнализируя об отработке заданной операции.

Если устройству задан режим записи информации, оно работает следующим образом. По сигналу C(52)=l работа блока 4 управления организуется в соответствии с блоком-схемой (фиг.4).

В первом тактовом периоде (блок 1, фиг.4) с информационного входа 26 устройства в регистр 25 заносится (С(23)=1) записываемое слово, которое переписывается также в регистр 12 (С(13)=1). Одновременно с адресного входа 2 в регистр 1 заносится адрес, по которому данное слово должно быть записано. В то же время аналогичным режиму считывания образом в регистр 45 записывается код числа. В следующем тактовом периоде (блок 2, фиг.4) занесенный в регистр 45 код сдвигается вправо на один разряд (С(48) 1) и переписывается в регистр

20 (С(19)=1), в результате чего из блока 16 памяти считывается (С(21)

1) содержимое ячейки с адресом с

N1 — )..Кроме того, выход регистра 25 переводится в высокоомное состояние (С(24)=1), блок 16 памяти переходит в режим считывания (C(21) 1), в результате чего. через первый вход коммутатора 27 (так как C{28) 1) на второй вход блока 8 сравнения подает40 ся содержимое первой группы разрядов считываемой из блока 16 памяти ячейки. На первый вход блока 8 сравнения с выхода регистра 12 подается записываемое слово информационный выход

45 блока 5 памяти находится в высокоомном состоянии, так как С 6ф. Далее (блоки 3 — 7, фиг.4) осуществляется бинарный поиск в блоке 16 памяти ячейки, содержащей в первой группе своих

50 разрядов слово, идентичное записываемому. Работа устройства в данном режиме аналогична работе блоков 3—

6 режима считывания. Момент нахождения данной ячейки идентифицируется по присутствию логических нулей на выходах блока 8 сравнения. Это влечет в следующем тактовом периоде (блок 20, фиг.4) перевод блока 5 памяти в режим записи (С(7)=1). В результате с вто1520592 рой группы разрядов 29> шины 29 в соответствующую ячейку блока 5 памяти з а писыв ае тс я код э апо мин аемо го слова.. Далее (блок 21 фиг.4) блок 4 упф °

5 равления формирует логическую "1" на выходе 55, поступающую на сигнальный выход 55 устройства, после чего работа устройства заканчивается.

Однако возможен случай, когда в блоке 16 памяти не будет найдена ячейка с запоминаемым словом, что свидетельствует о том. что данное слово запоминается впервые. Тогда на неко1 тором и-шаге бинарного поиска, где п((log N+1 j достигается ситуация, когда в регистре 32 и счетчике 37 оказываются коды чисел, отличающихся на единицу (обозначим их соответственно М и М+1), тогда на выходе сум" матора 44 имеют 2М+1, а на выходе

1 2М+1 1 сдвигающего регистра 45 — — 1

1"

=(и + —, 1-(м1+ (- - м+ - и. в результате блок 42 сравнения формирует на своем выходе единицу, посту" лающую на вход 51 блока 4 управления. Поступление данного сигнала свидетельствует о необходимости сдвига содержимого ячеек блока 16 памяти, имеющих адреса от М+1 до N-1, на одну ячейку вперед и записи нового sanoминаемого слова в ячейку с адресом

М+1 совместно со сформированным для него кодом. Вследствие этого в следующем тактовом периоде-(блок 8,, фиг,4) из регистра 34 через второй вход коммутатора 33 (C(36}Q) в счетчик 37 записывается (так как С(38)1) 40 код числа N поступающий на второй вход сумматора 44, на первый вход которого подается ноль,. так как C(57)

9..С выхода 46 блока 4 управления на вход переноса сумматора 44 подает- 45 ся единица. В результате в регистр

45 записывается (С(47) I)Я+1. В следующем тактовом периоде (блок 9, фиг.4) это число записывается (C(35)

1) в регистр 34. Далее (блок 10, фиг.4) содержимое счетчика 37 уменьшается на единицу (C(39) l) и без изменений (С(39) 1} и (С(46,48)"9) записывается в регистр 45 (С(47)1), а затем в регистр 20 (С()9) 1 в бло55 ке 12 (фиг.4). Данный адрес подается на адресный вход блока 16 памяти, переведенного в режим считывания сигналом С(21)"1. Из блока 16 памяти считывается содержимое ячейки с данным адресом. С второй группы разрядов 29 щины 29 записанный в данную ячейку код через первый вход коммутатора 30 С(49)=1 поступает в регистр 17 и заносится в него по сигналу С(18) 1. Хранящееся в извлекае" мой ячейке слово с первой группы разрядов 29 шины 29 переписывается в регистр 12 (С(13) 1, а выход регистра 25 находится в высокоомном состоянии из-за С(24) 1. Далее (блок 13, фиг.4) на вход переноса сумматора 44 подается единица (С(46)1), благодаря чему в регистр 45 записывается (С(47) 1) адрес ячейки блока 16 памяти, следующей за той, содержимое ко" торой находится в регистрах 12 и 17.Далее (блок 14, фиг.4) этот адрес записывается в регистр 20 (C(19)"-1), а затем подается на адресный вход блока 16 памяти, переведенного в режим записи сигналом С(22) 1. В результате в соответствующую ячейку записывается содержимое регистров 12 и 17.

Циклическая работа блока 4 управления по отработке блоков 10 — 14 (фиг.4} позволяет передвигать содержимое ячеек блока 16 памяти на одну ячейку вперед. Этот процесс повторяется до тех пор, пока после очередного уменьшения содержимого счетчика 37 в последнем не окажется число М. В результате коды на входах блока 42 сравнения становятся равными и он подает логическую "1" на вход 51 блока

4 управления. После получения данного сигнала (блок 15, фиг.4) из блока

16 памяти извлечено (С(21) 1) сорержимое ячейки с адресом М. С второй группы разрядов 29 шины 29 записанный в данной ячейке код через второй вход коммутатора 27 (блок 17,фиг.4)

С(28)=9 и первый вход коммутатора

31 (C(50) 1) записывается (С(41) 1) в регистр 32. Далее (блок 16,фиг.4) наличие С(46) 1 обеспечивает формирование на выходе сумматора 44 кода числа М+1, который запоминается (С(19)1) в регистре 20 (блок 17, фиг.4). В результате из блока 16 памяти считывается содержимое ячейки с данным адресом. Записанный в ней код через второй вход коммутатора .27 (С(28)ф), первый вход коммутатора

31(C(50) 1) и первый вход коммутатора 33 (С(36), 1) переписывается (С(38)

1) в счетчик 37 и подается на вто!

20

30

I l52 рой вход сумматора 44, на первый вход которого поступает содержимое регистра 32 (так как C(57) 1). В результате в регистр 45 записывается (С(47)=1) сумма кодов, хранящихся в ячейках блока 16 памяти с адресами М и М+1. Далее (блок 18, фиг.4) сигнал (С(48)=1) обеспечивает сдвиг этой суммы на один разряд вправо. Полученное среднее арифметическое кодов через второй вход коммутатора 30

С(49)=9. записывается в регистр 17 (С(18) 1) и с его выхода поступает на вторую группу разрядов 15 информационного входа 15 блока 16 памяти, находящегося в режиме записи С(22)=1

s блоке 21 (фиг.4). На первую группу 15! разрядов информационного входа 15 блока 16 памяти через регистр

12 C(13) 1, С(14)=!I! с выхода регистра 25 подается запоминаемое слово. В результате в ячейку блока 16 памяти с адресом М+1 записывается запоминаег мое слово с ego кодом. После этого (блок 20, фиг.4) блок 16 памяти переводится в режим чтения C(21)=l и устройство работает аналогично описанному ° .

Возможен вариант, когда коды, хранящиеся в ячейках блока 16 памяти с адресами М и М+1, различаются всего на единицу. Тогда после вычисления среднего арифметического данных кодов (блок 19, фиг.4 ) вследствие потери дробной части при сдвиге имеет место равенство кодов на входах блока 42 сравнения ° По формируемому на его выходе сигналу С(51)=1 блок 4 управления формирует (блок 25, фиг.4) на своем выходе 56 единицу, поступа" ющую на выход 56 переполнения устройства. Этот сигнал вызывает переэа-. грузку системы с перераспределением кодов для обеспечения необходимых интервалов между соседними в блоке

16 памяти кодов кодами.

Работа запоминающего устройства в режиме записи. Пусть в запоми-. нающем устройстве записываются двоичные 20-разрядные слова из набора, приведенные в таблице.

Каждое слово снабжено 6-разрядным кодом. Данная таблица при загрузке заносится в первые 10 ячеек блока 16 памяти кодов. При записи слова

00000000000!10011111 в процессе би-нарного поиска выясняется, что дан0592 !О ное слово записано в первой группе разрядов второй ячейки блока 16 памяти кодов. Тогда из второй группы разрядов данной ячейки считывается соответствующий код 00!000 и записывается в блок 5 архивной памяти по заданному адресу.

Рассмотрим случай, когда слово запоминается впервые. Пусть идет запись слова 00000000010000000001. После окончания поиска выясняется, что такого слова в блоке 16 памяти кодов нет. Поскольку значение данного слова больше значения слова, записанного в четвертой ячейке, и меньше,расположенного в пятой, данное слово должно быть записано в блок 16 памяти кодов между этими словами. Для этого содержимое 5-1 — 10-й ячеек блока

16 передвигается на одну ячейку вперед, а записываемое слово заносится в 5-ю ячейку. В соответствие ему становится код, равный среднему арифметическому кодов соседних слов, а именно 010010. Данный код з апоминается во второй группе разрядов четвертой ячейки, а также в блоке 5 архивной памяти по заданному адресу.

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

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

40 целью повышения информационной ем" кости устройства, в него введены сум матор, первый — четвертый коммутато-: ры, блок управления, блок памяти кодов, блок архивной памяти, второй регистр адреса, регистр свободной ячейки, вспомогательный регистр, сдвигающий регистр, регистр кодов, регистр слов и блок элементов И, адресные входы блока ар>0 хивной памяти соединены с выходами первого регистра адреса, информационные входы которого являются адресными входами устройства; первый и второй выходы первого блока сравнения соединены с первым и вторым входами задания режима блока управления, выходы блока архивной памяти соединены с входами первой группы первого блока сравнения, выходами регистра слов, 0592 J2

15

ll 152 информационными входами первой груп1 пы блока памяти кодов и являются информационными выходами устройства, выходы регистра кодов соединены с информационными входами второй группы блока памяти кодов, адресные входы которого соединены с выходами второго регистра адреса, информационные входы которого соединены с выходами сдвигающего регистра, входами первой группы второго блока сравнения, информационными входами первой группы второго и третьего коммутаторов, информационные входы второй группы которого соединены с выходами перво»

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

1520592

1З

Слова

Коды

МР

1 000000000

2 000000000

3 000000000

4 000000000

5 000000000

6 000000001

7 00000001 0

8 000010010

9 00001 1 000

10 01 1 100000

001 1001 1 01 0

001 l 00 1 I I I I

0011 0100000

1 0000000000

l 000001 0000

0 l 1010 l 100 1

00100011111

0001 00

01 0000

01 О! 00

01? 000

011 1 00 ! 00000

1 001 00

1 01 000

1520592

1 з, (). i >

rpuz. 5

Составитель Ю.Сычев

Техред M.Коданич Корректор И.Пожо

Редактор О.Головач

Заказ 6764/53 Тираж 558 Подписное

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

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

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101