Ассоциативное оперативное запоминающее устройство

 

Изобретение относится к вычислительной технике, в частности к запог^нающим устройствам, и может быть использовано в цифровых системах параллельной обработки информации. Цель изобретения -уменьшение информационной избыточности и упрощение устройства. Устройство содер^ жйт блок пймяти, выходной регистр, адрес-^ ный комм'утатор» промежуточный коммутатор, коммутатор записи, входной коммутатор, регистр числа, регистр началь-.ного адреса, регистр промежуточного хранения, регистр текущего адреса, реверсивный счетчик, регистр признака опроса, первый злемент неравнозначности, мультиплексор, второй и третий элементы неравнозначности, элемент И, элемент ИЛИ, инвертор, блок управления. Цель изобретения достигается тем. что информация в блоке памяти хранится в виде п-ярусного графа (п-разрядн^сть), причем каждая вершина I- яруса (I = ITiT) соответствует подмножеству записанных слов, совпадающих в i старших разрядах. Соответственно весь обьем блока памяти разделен по числу ярусов на п зон. каждая из которых содержит m ячебк разрядностью (Iog2m + 3). Три младщих разряда каждой ячейки содержат маркерные биты Д.у.а, указывающие соответственно на соответствие ячейки вершине гра^а (/9=1), на наличие ветвления в вершине графа (у = ~1), на значение i-ro бита пoдм)^oжecтвa слов, соответствующих ячейке в

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

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

РЕСПУБЛИК (51)з G 11 С 15/00

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

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

ПРИ ГКНТ СССР

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

i г

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4719907/24 (22) 18.07.89 (46) 23 .02.92..Бюл. N 7 (71) Киевский политехнический институт им.

50-летия Великой Октябрьской социалистической революции (72) B.È.Êoðìåé÷óê, А;ПкМарковский (SU), Сиала.Халед (TN) и Бардис Евгениос (GR) (53) 681.327.6(088.8) (56) Авторское свидетельство СССР

N 1324071, кл. G 11 С 15/00, 1987.

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

N. 11336633330077, кл. G 11 С 15/00, 1987. (54) АССОЦИАТИ В НОЕ ОПЕ РАТИ В НОЕ 3А ПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано 8 цифровых системах параллельной обработки информации. Цель изобретения — уменьшение информационной избыточности и упрощение устройства. Устройство содержит блок памяти, выходной регистр, адресный коммутатор, промежуточный коммутатор, коммутатор записи, входной коммутатор, регистр числа, .регистр начальИзобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в цифровых системах параллельной обработ-. ки информации.

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

На фиг.1 представлена структурная схема ассоциативного оперативного запоминающего устройства; на фиг.2 — пример: реализации блока управления; на фиг.3-8алгоритмы выполнения.соответствеййо orie„„SU „„1714682A1 ного адреса, регистр промежуточного хранения, регистр текущего адреса, реверсивный счетчик, регистр признака опроса, первый элемент неравнозначности, мультиплексор, второй и третий элементы неравнозначности, элемент И, элемент ИЛИ, инвертор, блок управления. Цель изобретения достигается тем, что информация:в блоке памяти хранится в виде и-ярусного графа (п-разрядность), причем каждая вершина lяруса (l = 1,n) -соответствует подмножеству записанных слов, совпадающих в i старших разрядах. Соответственно весь объем блока памяти разделен по числу ярусов íà и зон, каждая из которых содержит m ячеек разрядностью (1оцггп+ 3). Три младших разряда каждой ячейки содержат маркерные биты:;ф

j3, у, а, указывающие соответственно на соответствие ячейки вершине графа (P = 1), на наличие ветвления в вершине графа (у=1), на значение i-го бита подмножества слов, соответствующих ячейке в (1+1) зоне, ад- 2 рес которой совпадает с адресом в зоне

l ячейки, порождающей ветвление. 9 ил., 1 табл. 3

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

Ассоциативное оперативное запоминающее устройство (фиг.1) содержит блок 1 памяти, выходы которого подключены к входам (г+3)-разрядного выходного регистра 2(r»

- logjam, m — емкость в словах ассоциативного оперативного запоминающего. устройст1714682 поиска, выходами блока 24 управления являются выход 57 "Положительный результат операции" и выход 58 "Отрицательный результат операции", Блок 24 управления может быть выполнен в виде микропрограммного устройств управления (фиг.2) и содержит блок 59.по= стоянной памяти начальных адресов микропрограмм, блок 60 элементов ИЛИ, счетчик ва), три младших разряда которого являются маркерными, а г старших — информационными, адресный коммутатор 3, промежуточный коммутатор 4, коммутатор

5 записи; входной коммутатор 6, адресные входы 7 устройства, регистр 8 числа, информационные выходы первой группы 9устройства, регистр 49 начального адреса, регистр

11 промежуточного хранения, k-разрядный регистр 12 текущего адреса (k и logan, n— разрядность слов, хранимых в ассоциативном запоминающем устройстве), реверсивный счетчик 13, информационные входы 14 устройства, регистр 15 признака опроса, информационные выходы второй группы 16 устройства, первый элемент 17 неравнозначности; мультиплексор 18, второй элемент 19 неравнозначности, третий элемент

20 неравнозначности, элемент И 21, элемент ИЛИ 22, инвертор 23.

Кроме того, ассоциативное оперативное запоминающее устройство содержит блок 24 управления, входами которого являются выход 25 переполнения реверсивного счетчика 13, выход 26 второго разряда выходного регистра 2, выход 27 третьего разряда указанного регистра, выход 28 первого элемента 17 неравнозначности, выход 29 элемента И 21, выход 30 элемента ИЛИ 22, а выходами блока 24 управления являются соответственно вход 31 управления приемом кода регистра 8 числа, вход 32 управления приемом кода регистра 10 начального адреса, вход 33 управления приемом кода регистра текущего адреса 12, объединенные входы 34 управления считыванием блока непамяти и приема кода выходного регистра

2; вход 35 управления приемом кода регистра 11 промежуточного хранения, вход 36 управления приемом кода регистра 15 признака опроса,:управляющие входы: 37— входного коммутатора 6; 38 — коммутатора

5 записи: 39 — адресного коммутатора 3; 40 — промежуточного коммутатора 4; 41 — мультиплексора 18, вход 42 установки "0" и вход

43 установки в "1" всех разрядов реверсивного счетчика 13, суммирующий счетный вход 44, вычитающий счетный вход 45; вход

46 управления реверсивного счетчика 13, вход 47 управления записью блока 1 памяти, второй 48 и третий 49 младшие разряды информационных входов блока 1 памяти, вход 50 управления сдвигом, вход 51 установки в "1" и вход 52 установки в "0" всех разрядов регистра 15 признака опроса, второй вход 53 третьего элемента 20 неравнойначности, третий вход 54 мультиплексора

18. Внешними входами блока 24 управления являются входы 55 задания кода команды, внешний вход 56 задания направления

10 6t адреса микрокоманд, мультиплексор 62 (i+1)-й зоне, адрес которой совладает с адресом в зоне l ячейки, .порождающей ветвление. При этом в ячейке I-й зоны, адрес условий ветвления микропрограмм, элемент И 63, элемент ИЛИ 64, вход 65 тактовых импульсов, блок 66 постоянной памяти микропрограмм, регистр 67 микропрог15 рамм, выходы 31-54, 57и 58 являются выхоt дами блока 24 управления, а выходы 68 и 69 подключены соответственно к входам установки в "1" и "0" триггера 70, выход 71 которого является, как и входы 25-30 блока

20 24 управления, входом мультиплексора.62, вход 72 является входом начальной установки.

Информация в блоке 2 памяти в виде и-ярусного графа (и — разрядность), причем

25 каждая вершина I-го яруса (i - 1,n) соответствует подмножеству хранящихся слов. совпадающих между собой в i старших разрядах. Соответственно число вершин на

i-м уровне графа равно количеству слов, от30 личающихся в 1 старших разрядах. Каждая из вершин содержит информацию о ветвлении на I-м ярусе. Вершины нижнего и-го уровня соответствуют словам. хранящимся в блоке 1 памяти.

35 Соответственно объем блока 1 памяти разбит по числу ярусов графа на п эон, адресуемых кодом с выходом счетчика 13.

Каждая из зон содержит m ячеек разрядностью (logjam + 3). В пределах зоны ячейки

40 адресуются кодом с выходом адресного коммутатора 3. Три младших разряда каждой ячейки содержат маркерные биты соответственно а, Р, у. а остальные разряды указывают на адрес ветвления. Единичное

45 значение битаР указывает на соответствие ячейки вершине графа. Единичное значение бита у указывает на наличие ветвления в вершине, соответствующей данной ячейке.

В с учае наличия ветвления ячейке в Рзоне

50 сответствуют две ячейки в (!+1)й зоне, причем адрес в зоне одной из них совпадает с адресом в зоне рассматриваемой ячейки из

i-й зоны. а адрес другой указывается в информационных разрядах ячейки из 1-й зоны.

55 Бита соответствует значению i-ro бита под-. множества слов, соответствующих ячейке в

1714682 которой указывается порождающей ветвление ячейки, указывае ся адрес последней. бит. а равен нулю.

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

Пусть в блок 1 памяти последовательно 10 записываются 8-разрядные слова по соответствующим адресам: 2,3,1,0 (и = 8, m = 4)

10101100 -2

01111111- -3

10111101 -1 15

10101101 -0

Соответствующий граф представлен на фиг.9.

Информация в АЗУ разместится согласно таблице. 20

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

В устройстве реализуются следующие команды, код которых поступает на входы

55: "Запись информации по адресу"; "Счи- 25 тывание информации по адресу"; "Исключение информации по адресу"; "Поиск адреса ячейки, содержимое которой совпадает с заданным признаком опроса"; "Поиск адреса ячейки, содержащей экстремальный (ми- 30 нимальный или максимальный) код"; "Поиск адреса, содержащего код, являющийся ближайшим (большим или меньший) к заданному признаку опроса".

При записи слова в блоке 1 памяти кода 35 команда "Запись информации по адресу" подается на входы 55, одновременно адрес подается на адресные входы 7 устройства, а само слово — на информационные входы

14 устройства. Алгоритм выполнения ко- 40 манды записи представлен на фиг.3. В частности, блок 24 управления с получением команды записи по входам 55 формирует единичные сигналы на своих выходах 31, 36 и 42, а на выходах 37 — код 00, который 45 ..управляет работой коммутатора 6 таким образом, что адресные входы 7 оказываются скоммутированными на входы регистра 8 числа (соответственно, под действием сигнала с выхода 31 код адреса фиксируется на 50 регистре 8 числа), Одновременно. под управлением сигнала на выходе 36 на регистре 15.фиксируется код слова, подлежащего записи, по сигналу на выходе 42 счетчик 13 устанавливается в "0", 55

В следующем такте (блок 2 на фиг.3) блоком 24 управления формируется код 10 на выходах 39 и единичные сигналы на выходах 34,40,35, по которым соответственно коммутируется код, хранящийся на регистре 10 начального адреса, коммутатором 3 на адресные входы младших разрядов блока 1 памяти, производится считывание соответствующей ячейки блока 1 памяти на выходной регистр 2, коммутация через коммутатор 4 и прием на регистр 11 промежуточного хранения кода с регистра 10 начального адреса. В содержательном. плане приведенные микрооперации соответствуют опросу ячейки, соответствующей "корню" графа. адрес которой хранится на регистре 10 начального адреса (в приведен- . ном примере — ячейка с адресом 10 в зоне

000), Если значение бита р в считанном слове равно нулю (сигнал на входе 26 блока 24 управления равен нулю), то "корень" дерева отсутствует, т.е. в блоке 1 памяти не

/ записано ни одного слова. В этом случае записываемое слово будет первым и его адрес станет адресом "корня" дерева слов, хранящихся в устройстве, Для этого блок 24 управления сигналами с выходов 32,35,40, кодом 11 с выходов 39 инициирует запись содержимого регистра 8 числа через адресный коммутатор 3 на регистр 10 начального адреса и регистр, 11 промежуточного хранения (блок 3 алгоритма на фиг.3). Если значение битаP (сигнал на входе

26) равно единице, то работой блока 24 управления управляет сигнал совпадения, формируемый на его входе 30. Указанный сигнал имеет единичное значение, если текущий разряд признака опроса равен биту а считанного слова либо бит ссылки у не равен нулю, и формируется на выходе элемента ИЛИ 22. Фактически единичное значение сигнала на входе 30 свидетельствует о том, что в блоке 1 памяти хранятся слова, совпадающие в текущем и предшествующих разрядах с записываемым. В этом случае анализируется сигнал с выхода элемента И 21 (вход 29 блока 24 управления). Указанный сигнал имеет нулевое значение, если записываемое слово совпадает текущим разрядОм со словом, лежащим в

"корне" дерева слов, В этом случае необходимо в следующей зоне обращаться к ячейке, имеющей тот же адрес, что и ячейка, считанная в текущей зоне, Указанная операция обеспечивается выполнением в следующем такте (блок 3 алгоритма на фиг.3) выдачи блоком 24 управления сигналов с выходов 44,50, по которым соответственно увеличивается на единицу содержимое реверсивного.счетчика 13 (осуществляется переход к последующей зоне и сдвигается содержимое регистра 15 признака опроса), т.е. при обращении к последующей зоне

1714682 блока 1 памяти анализируется значение последующего разряда признака опроса.

Если сигнал на входе 29 блока 24 управления равен логической единице, то это значит, что записываемое слово совпадает в текущем разряде со словом, на адрес которого указывает ссылка ветвления. В этом случае в последующей зоне. необходимо анализировать содержимое ячейки с адресом, указанным в поле ссылки ячейки, считанной в текущей зоне. Для этого в последующем такте (блок 5 алгоритма на фиг.3) блок управления формирует единичные сигналы на выходах 35,44,60, по которым соответственно содержимое поле ссылки выходного регистра 2 через коммутатор 4 (сигнал на управляющем входе 40 которого равен нулю) записывается на ре-. гистр 11 промежуточного. хранения, содержимое реверсивного счетчика 13 увеличивается на единицу и содержимое регистра 15 признака опроса сдвигается на один разряд, При отсутствии сигнала переполнения на входе 25 производится считывание содержимого ячейки в следующей зоне (фиг.3, блок 9), которое обеспечивается выдачей блоком 24 кода 01 на выходе 39 и единичного сигнала на выходе 34. Цикл анализа повторяется.

В елучае, если при опросе ячейки блока

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

Для этого блок 24 управления (блок 6 алгоритма на фиг.3) формирует код 01 на выходах.39, код 10 на выходах 38, код 00 на выходах 41, единичные сигналы на выходах

47-49., которые инициируют запись в ячейку, адрес которой содержится в регистре 11 промежуточного хранения (т.е. в ячейку, содержимое которой считывалось в предшествующем такте. считывания) маркерного бита, сР. .этой же ячейки без изменения (через элемент 20 неравнозначности, на второй вход

53 которого подается нуль, и мультиплексор

18), единицы в маркерный бит P(c выхода

48), единицы в маркерный бит у (с выхода

49), адреса. содержащегося на регистре 8 числа (через коммутатор 5 записи).

В следующем такте (блок 7 алгоритма на фиг.3) блоком 24 управления формируется

50 ся, По окончании процесса записи блок 24 управления выдает сигнал на выходе 57 устройства. . При исключении слова из блока 1 памяти код команды "Исключение информации по адресу " подается на входы 55, одновременно адрес подается на адресные входы 7 устройства. Алгоритм:- выполнения команды исключения представлен на фиг.4

Блок 24 управления в первом такте (блок 1 алгоритма на фиг.4) формирует код 00 на выходах 37,единичные сигналы на выходах

31,43,69, которые обеспечивают запись адреса исключаемого слова с входов 7 на регистр 8 числа; установку всех разрядов реверсивного счетчика 13 в единицу, установку триггера 70 в "0".

В следующем такте производится считывание содержимого ячейки с адресом исключаемого слова на выходной регистр 2. Это обеспечивается выдачей блоком 24 управления (блок 2.алгоритма на фиг.4) кода 11 на выходах 39 и единичного сигнала на выходе 34.

Если бит Р равен единице, то анализируется состояние триггера 70, индицируекод 11 на выходах 39, код 01 на выходах 38, единичные сигналы на выходах 47,44,50, ко-. торые обеспечивают запись в блок 1 памяти . по адресу, содержащемуся в регистре 8 чис5 ла, нуля в маркерные биты P, g (с выходом

48,49), адреса, содержащегося на регистре

11 промежуточного хранения через коммутатор 5 записи, а также увеличение на единицу содержимого реверсивного счетчика 13 и

10 сдвига содержимого регистра 15 признака опроса.

Если при увеличении содержимого реверсивного счетчика 13 возникает сигнал переполнения, который поступает на вход

15 25 блока 24 управления, то операция записи заканчивается. В противном случае в следующей зоне записывается по адресу вводимого слова бит р присутствия и текущий разряд признака опроса в бит а. Для этого

20 блок 24 управления формирует коД 11 на выходах 39, код 01 на выходах 41 и единичные сигналы на выходах 47,48,44,50, которые обесйечивают запись по адресу из регистра 8 числа единицы в маркерный бит P

25 (с выхода 48) и бита текущего разряда записываемого слова в регистре-16 в маркерный бит а(через элемент 17 неравнозначности, на второй выход 56 которого подается нулевой сигнал, и мультиплексор 18), произво30 дится также увеличение содержимого счетчика 13 и сдвиг. регистра 15. При отсутствии сигнала переполнения счетчика 13, подаваемого на вход 25, указанные действия (блок 8 алгоритма на фиг.3) повторяют1714682

10 мое сигналом на входе 71 блока 24 управления. Если триггер 70 установлен в "0", то анализируется бит у считанного из блока 1 памяти слова (вход 27). Если бит у равен нулю. то считанное слово не содержит ссы- лок и,.следовательно, исключение слова в текущей зоне состоит в установке маркерного бита Р в "0". Далее блок 24 управления формирует код 11 на выходах 39, единичные сигналы на выходах 47,45 (блок 3 алгоритма на фиг,4), которые обепечивают запись нуля (с выхода 48) в маркерный бит

Р ячейки, адрес которой определяется содержимым регистра 8 числа. Одновременно содержимое .реверсивного счетчика 13 уменьшается на единицу. Опять повторяется цикл считывания, если нет сигнала на входе 25, Если.исключаемая ячейка в текущей зоне содержит ссылку, а триггер 70 установлен в "0", то указанная ситуация соответствует тому, что от исключаемой ветви графа, хранящегося в блоке 1 памяти; отходит неискл ючаемая ветвь. П ризна ком наличия такой ветви, отходящей от исключаемой, является единичное состояние триггера 70. Поэтому при обнаружении ветвления в исключаемой ветви триггер 70 необходимо установить в "1 и продублировать-исключаемую ветвь по адресу отходящей. Для этого адрес отходящей ветви графа следует за.фиксировать на регистре 11 промежуточного хранения. Блок 24 управления формирует (блок 4 алгоритма на фиг.4) код 00 на выходах 39, код 00 на выходах 41 и единичные сигналы на выходах 35,47,48,68,53, которые инициируют передачу кода из выходного регистра 2 через открытый нулевым сигналом с выхода 40 блока 24 коммутатор 4 на регистре 11 промежуточного хранения и запись в ячейку с адресом, определяемым кодом ссылки на выходном регистре 3 единичного маркерного бита Р (с выхода 48) и бита а, формируемого как инверсия аналогичного бита исключаемого слова. (указанная инверсия осуществляется элементом 20 неравнозначности, на вход 53 которого подается единичный сигнал), поскольку текущий бит слова, ветвь которого отходит от исключаемого, не совпадает с текущим битом исключаемого слова. Далее выполняется описанный такт установки в "0" маркера присутствия исключаемого слова (блок 3 алгоритма на фиг.4), Если и рй анализе ячейки, соответствующей в текущей зоне исключаемому слову, триггер 70 установлен в "0", то анализируется бит у считанного слова, которыми указы. вает на наличие ветвления на более высоких

55 если все разряды счетчика 13 не обнулены.

Если при анализе считанной в текущей зоне ячейки, соответствующей исключаемому алову ячейки, обнаружится, что маркерный бит Р присутствия равен нулю, то зто означает, что исключаемая ветвь графа на текущем уровне ответвляется от другой, адрес которой зафиксирован в поле ссылки, .считанной с ячейки. Очевидно, что если не было ответвлений от исключаемой ветви, то уровнях графа, Так, если бит р равен единице (имеется сигнал единичного уровня на выходе 27 блока 24 управления), то необходимо переписать по адресу, хранящемуся в

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

10 хранения. Указанные микрооперации выполняются в два такта. В первом такте (блок

5 алгоритма на фиг,4) блок 24 управления формирует код 01 на выходах 39, код 10 на выходах 38, код 00 на выходах 41, единич15 ные сигналы на выходах 47-49, которыми обеспечивается запись маркерного разряда а из регистра 2 (через элемент 20 неравнозначности, на второй вход 53 которого подается нулевой сигнал, и мультиплексор 18) в

20 поле маркера а запись единиц в поле остальных маркерных разрядов, запись кода с регистра 2 в поле ссылки ячейки, адрес которой определяется кодом, хранящимся на регистре 11, Во втором. такте (блок 6

25 алгоритма на фиг.4) блок 24управления формирует код 00 на выходах 39, код 01 на выходах 38, единичные сигналы на выходе

47, которые обеспечивают запись в ячейку по адресу, определяемому кодом, храняЗО щимся на регистре 2 маркерного бита Р, равного нулю, кода с регистра 11 промежуточного хранения. После указанных корректировок при ненулевом коде на счетчике 13 осуществляется переход к описанному так35 ту установки в "0" маркера присутствия исключаемого слова (блок 3 алгоритма на фиг.4). Если исключаемое слово на текущем уровне графа не содержит ветвлений (V (27)=

= О), то содержимое исключаемой ячейки

40 переписывается. по адресу,. зафиксированному в регистре 11.промежуточного хранения. Соответственно, блок 24 управления формирует код 01 на выходах 39, код 10 на выходах 38, код00 на выходах 11 и единичные сигналы на выходах 47,40 (блок 7 алгоритма на фиг.4), которые обеспечивают выполнение указанной записи. Дальше следует такт установки в "0" маркера присутствия исключаемого слова (блок 3 алгоритма на фиг,4), 1714682

12 необходимо установить в "О" маркерный Процесс исключения может иллюстрибит g ветвления в слове, содержащем ссылку роваться следующим примером. ветвления на исключаемую ветвь. Указан- Пусть в условиях предыдущего примера ная микрооперация обеспечивается выда- из блока 1 памяти исключается слово, запичей блоком 24 управления кода 00 на 5 санное по адресу 10. В первом цикле на выходах 39, кода 00 на выходах 41 и единич- счетчике 13 устанавливается код 111, на реных сигналов на выходах 47,48,53 (блок 8 гистре8числа-код10.Маркерныеразряды алгоритма на фиг.4). соответствующегослова равны а= 1, P= 1,.

В случае наличия ответвлений в исклю- y - 1. Следовательно, выполняется блок 4 чаемой ветви (триггер 70 установлен в "1") 10 алгоритма, представленного на фиг.4;тригосуществлетсязаписьвполессылкиячейки, гер 70 устанавливается в "1", в ячейку.00 указывающей на исключаемую ветвь, адре- зоны 111 записывается код О „В = 1,у са ветви,ответвляющейся от исключаемой,а =1, блоком 3 алгоритма бит Р в ячейке 10 также запись адреса ячейки, содержащей устанавливается в "0". в регистр 11 записыссылку на исключаемую ветвь в поле сылки 15 вается код 00, Содержимое счетчика 13 стаячейки, соответствующей ветви, отходящей новится равным 110. Так как в ячейке с от исключаемой. Указанные действия осу- адресом 10 в этой зоне, как и в последующествляются в два такта, В первом такте щихзонах101,100; р --1у =О,то выполняблоком 24 управления (блок 9 алгоритма на ются блоки 7 и 3 алгоритма на фиг.4, которые фиг,4) выдается код 00 на выходах 39, код 00 20 реализуют запись в ячейку 00 маркеров а= на выходах 41, код 01 на выходах 38 и еди- = 0 (для зоны 110) или а = 1 (для зон ничные сигналы на выходах 47 — 49,53, кото- 101,100),р =O,у =0. В зоне 011 маркерные рые инициируют запись в ячейку биты в ячейке 10 имеют значение а =О, p= определяемую адресом, хранящимся в поле = 1, у = 1, Следовательно, выполняются ссылки выходного регистра 2. следующей 25 блоки 5,6,3 алгоритма на фиг.4. Блоком 5 в инфоРмации: в поле ссылок — код с выходов ячейку 00 заносится код 011Q1, блоком 6 в

РегистРа 11 пРомежУточного хРанениЯ, в по- ячейку 01 заносится код XQXQQ B зонах 010 ле маРкеРных битов P,y— - единиц (с выхо- и 001 выполняются операции, аналогичные дов 48, 49), в поле маркерного бита а — выполнявшимся взонах101,100. Взоне000 инверсное значение соответствующего бита 30 маркерные биты слова, хранящегося в ячейвыходного регистра 2. Во втором такте бло- ке 10, равны а = 1,p = 1,y = 1, Соответстком 24 управления выдается (блок 10 алго- венно выполняют блоки 5,6,11,12 ритма на фиг,4) код 01 на выходах 39, код 10 алгоритма,. изображенного на фиг.4, в ячей, на выходы 38, единичные потенциалы на ку 00 загружается код 111 11, в ячейку 11 выход 48, которые инициируют запись в 35 загружается код 0000 00, маркерный бит р ячейку по адресу, совпадающему с кодом на в ячейке 10 устанавливается в "О". Код 00 регистре 11 промежуточного хранения, мар- загружается в регистр 10 начального адреса керных битов р иу, равных нулю, и кода с вместо ранее там находившегося кода 10. выходов регистра2,Поокончаниивыполне- . При поиске слова по совпадению код ния указанных микрокоманд (после выпол- 40 команды "Поиск адреса ячейки, содержинения блоков 8 или 10 алгоритмов на фиг.4) мое которой совпадает с заданным признаблок24управленияформируетнавыходе57 ком опроса", подается на входы 55 сигнал конца операции, устройства, одновременно код слова подаПосле выполнения блоков 4,6,7 алгорит- ется на информационные входы 14 устройма на фиг,4 выполняется описанный блок 3 45 ства, Алгоритм выполнения команды поиска микРоопеРаций Установки в "0 маРкеРного по совпадению представлен на фиг.5. бита р присутствия исключаемого слова и Выполнение команды -начинается (блок уменьшения на единицу, содержимого счет- 1 алгоритма на фиг.6) выдачей блоком 24 чика 13. Если в результате указанного управления единичных сигналов на выходах уменьшения счетчик 13 выдает сигнал пере- 50 46,42,31, кодов 10 на выходах 39 и 37, котополнения на вход 25 блока 24 управления, рыми инициируется прием кода признака то в следующем такте (блок 11 алгоритма на опроса на регистр 15, пересылка кода с рефиг.4) блок 24 управления формирует код 00 гистра 10 начального адреса через коммутана выходах 39 и единичный сигнал на выхо- торы 3 и 6 на регистр 8 числа, установка в де32, которые обеспечивают пересылкуад- 55 "О" разрядов реверсивного счетчика 13. В реса ветви, отходящей от исключаемой, из следующем такте (блок 2 алгоритма на регистра 11 промежуточного хранения че- фиг.5) выдачей блоком 24 управления кода рез адресный коммутатор 3 на регистр 10 11 на выходах 39 и единичного сигнала на. начального адреса. Операция исключен я выходе 47 обеспечивается считывание из заканчивается, 14

1714682

10

35

40 блока 1 памяти содержимого ячейки, соответствующей "корню" дерева слов, записанных в блоке 1. Дальнейшее функционирование устройства определяет ся значением сигналов на входах 29 и 30 блока24управления. Еслисигнал на входе

30 равен нулю, то операция поиска оканчива ется выдачей сигнала с выхода 58 устройства, свидетельствующего об отсутствии в блоке 1 памяти слова, совпадающего с признаком опроса. В случае, если единичный сигнал на входе 30 есть, анализируется сигнал на входе 29: если он равен нулю, то; следовательно, признак опрОса в текущем разряде совпадает с соответствующим разря- 15 дом слова, отражаемого в блоке 1 памяти, прямым участком ветви. 8 противном случае текущий разряд признака опроса совпадает с соответствующим разрядом слова, отражаемого ответвлением, Соответствен- 20 но в первом случае (блок 4 алгоритма на фиг.5) блок 24 управления сигналами с вы- . ходов 44,50 осуществляет увеличение содержимого счетчика 13 и сдвиг содержимого регистра 15 признака опроса. Затем цикл анализа повторяется. Во втором случае производится переход к новому адресу в последующей зоне (блок 3 алгоритма íà фиг.5), блок 24 управления формирует единичные сигналы на выходах 44,50,31 и код 01 на выходах 37, которые инициируют кроме. прибавления единицы к содержимому счет чика 13 и сдвига регистра 15 занесение через входной коммутатор кода ссь1лки с выходного регистра 2 на регистр 8 числа..

Если счетчик 13 в результате прибавления единицы не обнуляется, выдавая при этом сигнал на вход 25 блока 24 упраления, то цикл поиска повторяется, в противном случае по сигналу с входа 25 блок 24 управления формирует единичный сигнал конца операции на выходе 57; а адрес искомого слова, совпадающего с признаком поиска, фиксируется при этом на выходах 9 устройства. - 45

При поиске экстремума код команды

"Поиск ячейки, содержащей экстремальный код", подается на входы 55, а на вход,56 подается бит, определяющий направление поиска, равный нулю при поиске максимума 50 и единице при поиске минимума. Пусть для. определенности ищется максимум среди чисел, хранящихся в устройстве, В первом . такте поиска (блок 1 на алгоритме поиска экстремума, представленном на фиг.6) блоg 55

24 управления формирует коды 10 на выходах

39 и 37, единичные сигналы на выходах

31,42,51, которые обеспечивают запись кода, хранящегося на регистре 10 начального адреса;через коммутаторы 3 и 6 на регистр

8 числа, обнуление всех разрядов реверсивного счетчика 13 и установку в "1" всех разрядов регистра 15 признака опроса. 8 последующем такте (блок 2 алгоритма на фиг.6) выполняется считывание на выходной регистр 2 содержимого ячейки с адресом, зафиксированным на регистре 8 числа.

Для этого блок 24 управления формирует код 11 на своих выходах 39 и единичный сигнал на выходе 34. Выбор следующей микрокоманды, подлежащей выполнению, осу-. ществляется в зависимости от сигналов на входах 29, 30 блока 24 управления. Так, если сигнал совпадения (сигнал на входе 30 блока 24) равен нулю, то необходимо инвертировать текущий разряд признака опроса и перейти к следующей зоне. Соответственно блок 24 управления формирует единичные сигналы на своих выходах 44,50 и код 10 на выходах 41, которые инициируют увеличение содержимого счетчика 13 на единицу и сдвиг содержимого регистра 15 на один разряд с запоминанием освободившегося разряда нулем, сигнал которого поступает с выхода 54 блока 24 управления через мультиплексор 18. Если счетчик 13 не выдает сигнала переполнения на вход 25 блока 24 управления, вновь выполняется микрокоманда, соответствующая блоку.2 алторитма на фиг.6.

B случае, если сигнал совпадения на входе 30 равен единице, анализируется сигнал на выходе 29. который определяет ветвь графа (прямую или отходящую), с которой выявлено совпадение. Если, в частности, сигнал на входе 29 равен нулю (соответствует совпадению по прямой ветви), то блок

24 управления выдает единичные сигналы на выходах 44,50,54 и код 10 на выходах 41 (блок 3 алгоритма на фиг.6),которыми осуществляется увеличение содержимого реверсивного счетчика 13 на единицу, сдвиг содержимого регистра 15 с заполнением освободившегося при этом разряда единицей, поступающей с выхода 54 через мультиплексор 18. Если сигнал на входе 29 равен еди-, нице, то выполняется блок 4 алгоритма на фиг.6 — блок 24 управления в дополнение ко всем сигналам, выдаваемым в блоке 3 алгоритма; формируется код 01 на выходах 37 и сигнал на выходе 31, соответственно, в дополнение к описанным микрооперациям выполняется занесение кода с регистра 2.через входной коммутатор 37 на регистр 8 числа, Если при переходе на следующую зону содержимое счетчика 13 обнулится, то на входе 26 блока 24 управления сформируется единичный сигнал, по которому последний выдаст сигнал конца операции на входе 57.

1714682

16 код максимального слова будет зафиксирован при этом на выходах 16 устройства, а его адрес — на выходах 9 устройства.

При поиске минимума на вход 56 подается потенциал единичного уровня и результат с выходов 16 считывается в инверсном коде.

При поиске числа, ближайшего к заданному, код команды "Поиск адреса, содержащего код, являющийся ближайшим (большим или меньшим) к признаку опроса", подается на входы 55, код признака опроса подается на входы 14 устройства, а направление поиска задается сигналом на входе 56 (при поиске ближайшего большего — нулевой сигнал, при поиске меньшего — единичный). Алгоритм работы устройства при реализации указанного вида поиска представлен на фиг.7. Пусть для определенности ищется ближайшее большее заданного.

Суть процесса поиска ближайшего состоит в следующем.

В и-ярусном графе, представляющем числа, хранящиеся в блоке 1 памяти, выделяется ветвь, отходящая бт ветви заданного признака опроса в направлении, соответствующем критерию поиска на ярусе с наибольшим значением. В подграфе, порождаемом указанной отходящей ветвью, отыскивается ветвь, соответствующая минимальному числу, Если, например, ищется ближайшее большее в графе чисел, представленной на фиг.9, к числу 10100000, то ветвью заданного числа будет ветвь, расположенная по адресу 10 от зоны 000 до эоны 1000. Отходящая ветвь начинается в зоне 100 по адресу 10 и порождает подграф, в котором минимальное число соответствует адресу 10. Следовательно, искомый код равен 10101100.

Установка узлов устройства в исходное состояние реализуется микрокомандой 1 алгоритма на фиг.7, в которой блок 24управления формирует коды 10 на выходах 39 и

37, единичные сигналы на выходах

31,42,36,69, которые инициируют пересылку кода "корня" дерева с,регистра 10 начального адреса через коммутаторы 3,6 на регистр 8.числа, установку в "0" реверсивного счетчика 13, прием кода признака опроса с входов 14 на регистр 15 признака опроса, установку в "0" триггера 70.

Цикл прохода зон начинается считыванием на выходной регистр 2 содержимого ячейки блока 1 памяти, адресуемой кодом с регистра 8 числа (блок 2 алгоритма на фиг.7).

Укаэанные микрооперации реализуются выдачей блоком 24 управления кода 11 на выходах 39 и единичного сигнала на выходе 34.

Дальнейшая последовательность следования микрокоманд зависит от сигналов, поступающих на входы 28 — 30 блока 24 управления, В частности, если имеется единичный сигнал совпадения на входе 30, что „ соответствует совпадению ветви числа — признака опроса и одной из ветвей графа, хранящегося в блоке 1 памяти, то анализи- руется значение текущего разряда призна10 ка опроса, выдаваемое на вход 28 блока 24 в прямом коде, если ищется ближайшее большее, и в инверсном, если ищется ближайшее меньшее. Ели сигнал на входе 28 не равен нулю (что свидетельствует о невозможности ответвления в направлении,соответствующем критерию поиска) ° то анализируется сигнал на выходе 29 блока 24 управления: если укаэанный сигнал равен нулю, то ветвь признака опроса совпадает с

25 прямым продолжением ветви, хранящейся в блоке 1, а если единице; то ветвь признака опроса совпадает с отходящим участком ветви и, следовательно, для продолжения поиска необходимо изменить адрес при обращении в последующей зоне. В первом случае выполняется блок 4 алгоритма, представленного на фиг.7, а во втором — блок 3.

Соответственно в первом случае блоком 24 управления формируются единичные сигналы на выходах 44,50, которые управляют увеличением на единицу содержимого счетчика 13 и сдвигом регистра 15. Во втором случае дополнительно к упомянутым микрооперациям выдачей блоком 24 управления

35 кода 01 на выходах 37 и единичного сигнала на выходе 31 осуществляется загрузка регистра 8 числа кодом ссылки с выходного регистра 2.

Если сигнал на входе 28 равен нулю, то на входе 29 блока 24 управления. Если ука-,. занный сигнал равен нулю, то это соответ45 ствует тому, что от ветви с адресом, зафиксированным на регистре 9, совпадающей с ветвью признака опроса, ответвляется ветвь, адрес которой зафиксирован на выходном регистре 2, соответствующая чис50 лам большим признаку поиска, Соответственно блоком 24 управления (блок

5 алгоритма на фиг.7) формируются единичные сигналы на выходах 35,44,50,68, которые инициируют передачу кода из поля

55 ссылок выходного регистра 2 через откры. тый нулевым сигналом с выходом 40 коммутатор 4 на регистр 11 промежуточного хранения, увеличение на единицу содержимого счетчика 13, сдвиг содержимого регистра 15 признака опроса, установку в "1"

40 возможно ответвление ветви, соответствующей числам, большим заданного признака опроса, В этом случае анализируется сигнал

1714682

18 триггера 70, единичное состояние которого свидетельствует о фиксации начальной ветви подграфа чисел, больших заданного признака опроса, В последующем такте (блок:6 алгоритма на фиг.7) сигналом с выхода 33 5, блока 24 управления осуществляется фиксация содержимого счетчика 13 на фиксирующем регистре.12.

Еслй сигнал на входе 29 I блока 24 управления равен единице, то это соответст- -10 вует тому, что ветвь с адресом, зафиксированным в поле ссылок выходного регистра 2, совпадающая с ветвью признака опроса, ответвляется от ветви, адрес. которой зафиксирован на регистре & и которая 15 соответствует числам, большим заданного -. признака опроса. Соответственно блоком

24 управления (блок 7 алгоритма на фиг.7) формируются код 11 на выходах 39, код 01 на выходах 37, единичные сигналы на выхо- 20 дах 35,40,31,44,50,68, которые инициируют пересылку кода с регистра 8 через коммута- . торы3и4: на регистр 11 промежуточного .хранения, пересылку кода с поля ссылок. выходного регистра 2 через коммутатор 6 на 25 регистр 8 числа, увеличение на единицу содержимого счетчика 13, сдвиг содержимого регистра 15, установку в единичное состояние триггера 70.

В последующем такте выполняется мик- 30 рокоманда, соответствующая блоку 6 aht оритма на фиг,7, Если в результате описанных микроопераций появится сигнал на входе 25 блока 24 управления, то процесс поиска закончен и адрес искомого слова 35 может быть считан с выходов 9 устройства.

В противном случае начинается обработка информации в последующей зоне блока 1 памяти.

Если в результате считывания очеред- 40 ного фрагмента графа, осуществляемого блоком 2 алгоритма на фиг.7, окажется, что сигнал на входе 30 блока 24 управления равен нулю, то это соответствует тому, что ветвь, соответствующую признаку опроса, 45 не совпадает далее ни с одной из ветвей графа, хранящегося в блоке 1 памяти, и необходимо переходить к поиску. минимального элемента на подграфе чисел, больших заданного.. 50

Если очередной разряд признака опроса равен нулю (соответственно и равен нулю сигнал на выходе 28 блока 24 управления), то подграф множества чисел ближайших больших заданного признака .опроса по- 55 рождается продолжением ветви, адрес ко-. торой зафиксирован на регистре 8:чйсла.

Блок 24 управления формирует сигнал единичного уровня на своем выходе 52, которым: все разряды регистра 15 устанавливаются в "0" (блок 8 алгоритма) и " далее управление передается микроподп-. рограмме (блоки 11-13 алгоритма на фиг.7), которая реализует поиск минимального числа в подграфе, корень которого задан адресом в регистре 8 числа. Если значение текущего разряда признака опроса. (а значит, и сигнал на входе 28 блока 24 управления) равен единице, то минимальное число следует искать по подграфу, порождающий корень которого зафиксирован на регистре

12 текущего адреса и регистре.11 промежуточного хранения. Для этого предварительно анализируется состояние триггера 70: если последний установлен в "0", то среди записанных в блоке 1 памяти чисел нет больших заданного, соответственно блоком

24 управления выдается сигнал неуспешного поиска с выхода 58 устройства. В противном случае выполняется блок 10 алгоритма на фиг.7, в котором блок 24 управления выдает единичные сигналы на своих выходах

46, 31, 52, код 01 на выходах39 и код 11 на выходах 37; которые инициируют прием кода с регистра 12 текущего адреса на реверсивный счетчик 13, пересылку кода с регистра

11 промежутоного хранения через коммутаторы 3,6 на регистр 8 числа, установку в "0" всех разрядов регистра 15.

Процесс поиска минимума, реализуемый подпрограммой, задаваемой блоками

11- 14 алгоритма на фиг.7, аналогичен описанной процедуре поиска экстремума за тем исключением, что при переходе к следующей зоне в блоке 1 памяти сдвиг содержимого регистра 15 не производится. По выдаче счетчиком 13 сигнала переполнения на вход 25 блока 24 управления искомый адрес фиксируется на регистре 8 и выдается посредством выходов 9, блок 24 формирует единичный сигнал конца операции на выходе 57.

При считывании слова по его адресу код соответствующей команды подается на входы 55, код адреса подается,на входы 7 устройства. Алгоритм выполнения команды считывания слова по адресу представлен на фиг.8, Первая микрокоманда (блок 1 алгоритма на фиг.8) устанавливает исходное состояние устройства. Соответственно блоком 24 управлейия формируется код 00 на выходах

37 и единичные. сигналы на выходах 31,43, под управлением которых код адреса с входов 7, поступая через входной коммутатор

6, фиксируется на регистре 8 числа, все разряды счетчика 13 устанавливаются в "1".

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

1714682

Цикл поиска в зоне начинается считыванием слова, адресуемого кодом на регистре

8 иэ блока 1 памяти на выходной регистр 2 (блок 2 алгоритма на фиг.8), что обеспечивается выдачей блоком 24 управления кода 11 на выходах 39 и единичного сигнала на выходе 34. Если маркерный бит фсчитанного на регистр 2 слова (сигнал на входе 26 блока 24) равен единице, то производится сдвиг содержимого регистра 15 с заполнением освободившегося разряда маркерным битом а слова, считанного на регистр 2, при этом сигнал с младшего разряда регистра 2 поступает через элемент 20 неравнозначности, на другой вход 53 которого подается нулевой сигнал, и мультиплексор 18. Содержимое счетчика 13 уменьшается на единицу. Все эти микрооперации, объединенные в блок 3 алгоритма на фиг,8, реализуются под действием кодов 00 на выходах 41, единичных,сигналов с выходов 50, 45, формиру. емых блоком 24 управления, При отсутствии сигнала переполнения счетчика 13 вновь повторяется микрооперация считывания (блок 2 алгоритма на фиг.8).

Если маркерный бит Р считанного слова окажется. равным нулю, то выполняется блок 4 алгоритма. Указанная ситуация соответствует вхождению считываемой ветви в обобщающую, В этом случае адрес последней указан в поле ссылки кода, содержащегося на выходном регистре 2, и подлежит пересылке в регистр 8 числа. Блок 24 управления формирует код 01 на выходах 37, код

00 на выходах 39, единичные сигналы на выходах 34,31, которые инициируют пересылку кода с выходного регистра 2 через входной коммутатор.6 на регистр 8 и одновремеНное считывание из блока 1 памяти слова, адресуемое кодом, поступающим с выходного регистра 2, через адресный коммутатор 3 на адресные входы блока I памяти, Анализируется маркерный бит у считанного слова, поступающий по входу ,27: если y = О, то по заданному адресу нет записанного слова и блок 24 управления выдает единичный сигнал на выход 58, свидетельствующий о том, что поиск неуспешно завершился, В противном случае выполняется блок 5 алгоритма на фиг.8, в котором блок 24 управления выдает код 00 на выходах 41, единичные сигналы на выходах 50, 45, 53, которые обеспечивают уменьшение на единицу содержимого счетчика

13, сдвиг регистра 15 с заполнением освобождающегося разряда инверсией бита а, хранящегося на регистре 2, причем инвертирование сигнала. поступающего с младшего разряда регистра 2, осуществляется элементом 20 неравнозначности.

Если счетчик 13 выдает сигнал переполнения на вход 25 блока 24 управления, последний сформирует единичный сигнал на выходе 57 устройства, а код искомого слова может быть считан с выходов 16 устройства.

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

Ассоциативное оперативное запомина10 ющее устройство, содержащее блок памяти, 25 выходу элемента ИЛИ, первый, второй и третий выходы блока управления соединены соответственно с синхровходом регистра числа, с входами управления считыванием и защиты блока памяти, первая группа выходов блока управления под30 ключена к управляющим входам входного коммутатора, пятый и шестой выходы блока управления являются выходами положительного и отрицательного результатов по35 иска, о т л и ч а ю щ е е с я тем, что, с целью уменьшения информационной избыточности и упрощения устройства, в него введены реверсивный счетчик, регистр текущего адреса, регистр начального адреса, выход40 ной регистр, регистр промежуточного хранения, регистр признака опроса, адресный коммутатор, коммутатор записи, промежуточный коммутатор, мультиплексор, причем информационные выходы блока памяти

45 подключены к входам (г+3)-разрядного выходного регистра (r = !од2е, m — количество слов, хранящихся в устройстве), выходы старших разрядов которого соединены с информационными входами первой группы коммутатора записи, промежуточного коммутатора и адресного коммутатора, а также с информационными входами второй группы входного коммутатора, информационные входы второй группы адресного

55 коммутатора.и коммутатора записи подклю.чены к выходам регистра промежуточного хранения, информационные входы которого соединены с выходами промежуточного коммутатора, информационные входы второй группы которого подключены к инфоррегистр числа, входной коммутатор, элемент ИЛИ, элемент НЕ, элемент И, блок управления, входы группы которого являются входами кода команды устройства, а пер15 вый и второй входы являются входом тактовых импульсов и входом начальной установки устройства, информационные входы первой группы входного коммутатора являются адресными входами устройства, 20 выходы входного коммутатора соединены с информационными входами регистра числа, выходы которого являются информационными выходами первой группы устройства, третий вход блока управления подключен к

1714682

22

21 мационным входам третьей группы входного коммутатора, к информационным входам регистра начального адреса, к выходам ад- . ресного коммутатора и к младшим адрес ным входам блока памяти, старшие 5 адресные входы которого соединены с информационными входами регистра текуще.

ro адреса и с информационными выходами реверсивного счетчика, установочные входы которого подключены к выходам регист- -10 ра текущего адреса, информационные входы третьей группы адресного коммутатора соединены с выходами регистра начального адреса, информационные входы четвертой группы адресного коммутатора 15 подключены к выходам. регистра числа и к информационным входам третьей группы коммутатора записи, выходы. которого сое-: динены со старшими информационными входами блока памяти, информационные 20 входы и выходы младших разрядов регистра признака опроса являются соответственно информационными входами и информационными выходами второй группы устройства,.выход старшего разряда регистра 25 признака опроса соединен с первым входом первого элемента неравноэначности, второй вход которого является входом задания направления поиска устройства, а выход которого.подключен к первому входу второго 30 элемента неравноэначности, второй вход.

-которого соединен с первым входом третьего элемента неравноэначности и с (r+I)-м выходом выходного регистра, (г+2)-й выход которого подключен к четвертому входу бло- 35 . ка управления, пятый вход которого соединен с (r+3) м выходом выходного регистра и с первым входом элемента И. выход которо- .

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

23

1714682

Продолжение таблицы

П р и м е ч а н и е . Х-безразличное состояние бита.

1714682

1714682

1714682 "

1714682

1714682

1714682

Корректор М.Пожо

Редактор С.Пекарь

Заказ.698 Тираж Подписное

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

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

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

06 +

Составитель О.Исаев

Техред М.Моргентал