Ассоциативное запоминающее устройство Советский патент 1986 года по МПК G11C15/00 

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

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

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

Предлагаемое устройство содержит (фиг. 1) блок 1 управления, накопитель 2, регистр 3 опроса, первую 4 и вторую 5 группы элементов НЕРАВНОЗНАЧНОСТЬ, формирователи 6 сигналов сдвига, сдвигающую матрицу 7, регист 8 результата поиска с входом 9. На фиг. 1 обозначены ячейки 10 сдвигающей матри1ц 1 1. Устройство содержит также элементы ШТИ 11, элементы ИЛИ- НЕ 12, выходные шины 13 строк, выходные шины 14 столбцов сдвигающей матрицы 7.

Сдвигающая матрица 7 содержит первую 15 и вторую 16 группы нагрузочных элементов. На фиг. 1 обозначены шина 17 питания, выходы 18-23 блока 1 управления. Каждая ячейка 10 сдвигающей матрицы 7 содержит (фиг. 2) триггер 24 и элемент НЕ 25.

Блок 1 управления содержит (фиг.З дешифратор 26, микропрограммную матрицу 27, регистр 28 микрокоманд, регистр 29 кода операции и генератор 30 тактовых сигналов.

Формирователь 6 сигналов сдвига содержит (фиг. 4) элементы И-НЕ 31- 34, триггер 35 и элемент 1-ШИ-НЕ 36.

Слова массива-аргумента хранятся в запоминающих ячейках накопи .геля 2, а признак опроса - в регистре 3, причем М - разрядное слово-аргумент и признак опроса разбиваются на две равные части и в одной части (например, левой) записаны старшие раз- ряды слова-аргумента и признака опроса, а в другой - младхиие их разряды. Дальшейтлее разбиение Ы - разрядного слова-аргумента и признака опроса приводит к значительному усложнению конструкции формирователей 6, что затрудняет выполнение изложенных ниже требований к ним. Запоминающие ячейки накопителя 2 и регистр 3 мо

гут иметь различную конструкцию (статическое или динамическое ЗУ, сдвиговые регистры, ЗУ на ЦМД, дорожки вращающихся магнитных ЗУ и т.д.). Однако они должны обеспечивать последовательное поразрядное обращение, а именно: при поступлении очередного управляющего импульса на входы регистра 3 и накопителя 2 с выходов каждой запоминающей ячейки одновременно считываются очередные разряды левой и правой частей данной.ячейки. Число ячеек 10 в строке матрицы 7

М равно ,

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

8,

При поступлении на входы блока 1 (фиг. 1) команды поиска блок 1 выабатывает следуюд(ую последователь- ность операций. В первой микрокоманде на выходах 20, 22 и 23 формируются: на вькоде 20 - сигнал (логи- ческая единица), не препятствующий нормальной работе формирователей 6; на выходе 22 - сигнал (логическая единица), который осуществляет установку в 1 всех разрядов регистра

формирователей 6 и ячеек 10 матрицы 7; на выходе 23 - сигнал (логическая единица), запрещающий поиск строки матрицы 7, имеющей максимальное число единиц.

Затем в ряде последовательных микрокоманд вьщается серия сигналов на выходах 18,19 и 21. В результате происходит последовательная выборка из накопителя 2 всех разрядных срезов (отдельно группы младших и старших разрядов) массива слов-аргументов с синхронной выборкой соответствующих разрядов регистра 3. Разряды всех Р слов (для каждого слова выбирается два разряда: один из группы младших, а другой из rpynm.i старших) поступают из накопителя 2 на первые входы соответствующих элементов НЕРАВНОЗНАЧНОСТЬ 4, 5, причем младшие разряды поступают на входы элементов НЕРАВНОЗНАЧНОСТЬ, а старшие разряды поступают на входы элементов НЕРАВНО- ЗНАЧНОСТЬ 5. ОдноЕфеменно из регистра 3 поступают соответствующие млад--. шие разряды на входы всех элементов НЕРАВНОЗНАЧНОСТЬ 4, а старшие разряды - на входы элементов НЕРАВНОЗНАЧНОСТЬ 5. Для тех слов, где значение какого-либо разряда совпадает

со значением соответствующего разряда признака опроса, на выходах соответствующих элементов НЕРАВНОЗНАЧНОСТЬ 4 или 5 формируются сигналы нулевого уровня, которые поступают на входы соответствующих формирователей 6, каждый из которых работает в соответствии с таблицей. Задержка сигнала в формирователе 6 должна быть равна:задержке сигнала при сдвиге в строке матрицы 7. Сигнал, поступающий на входы формирователей 6 с выхода 21, обеспечивает совмещение во времени работы формирователей 6 и матрицы 7, т.е. в то время, когда матрица 7 отрабатьюает сигнал одного такта, формирователи 6 отраба- тьшают сигнал последующего такта.

Если на выходе К-ого (К 1, Р) формирователя 6 формируется сигнал разрешения сдвига (логическая единица) , поступающий на входы синхронизации всех ячеек 10 К-ой строки матрицы 7, то в этой строке произойдет сдвиг содержимого ячеек 10 на один разряд вправо, а в освободившуюся, например, крайнюю левую ячейку 10

этой строки запишется 1 , в противном случае содержимое строки ячеек 10 матрицы 7 не изменится. По оконча/ М .X

НИИ серии из у +1;-го сигналов,

формируемых на выходах 18 и 19,на выходе 20 формируется сигнал (О), который, поступая на первые входы

5

0

0

5

формирователей 6, формирует на их выходах сигнал разрешения сдвига (1), если в триггере 35 (фиг. 4) этого формирователя 6 хранилась 1, и сигнал запрещения сдвига - в противоположном случае.

На (-J- +2)-ом такте с выхода 21

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

, М „,

(,- + такте и сводится к установке (сигналами, поступающими с выходов соответствующих элементов ИЛИ 11) в О всех ячеек 10, кроме ячеек 10 столбца матрицы 7, в котором содержится самая правая 1, причем строка, в которой содержится указанная 1, соответствует слову, ближайшему к признаку опроса по критерию Хемминга. После установки в О указанных Bbmie ячеек 10, сигнал нулевого уровня на одной из шин 13 укажет на слово-аргумент, имеющее минимальное кодовое расстояние к признаку : опроса,, т.е. слово, ближайшее по Хем- мингу к признаку опроса.

Необходимо отметить, что is общем случае массив-аргумент может содер- жать несколько слов, имеющих одинаковые минимальные кодовые расстояния по отношению к признаку опроса, причем эти слова могут быть одинаковыми (тогда несовпадение имеет место в одних и тех же разрядах) либо различными (несовпадение в разных разрядах). Всем этим словам соответствует одинаковое количество 1 в соответствующих строках матрицы 7, где они параллельно выделяются. В случае необходимости в предлагаемое устройство известными средствами может быть введено маскирование про- извольньЕХ разрядов накопителя 2, при этом обеспечивается возможность выполнения всех описанных выше операций только над незамаскированными разрядными срезами.

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

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

1, Ассоциативное запоминающее устройство, содержащее регистр опроса, накопитель, первую группу элементов НЕРАВНОЗНАЧНОСТЬ, регистр результата поиска и блок управления, одни из выходов которого подключены к управляющим входам регистра опроса, регистра результата поиска и накопителя, одни из выходов которого соединены с первыми входами элементов НЕРАВНОЗНАЧНОСТЬ первой группы, вторые входы которых подключены к первому выходу регистра опроса, отличающееся тем, что, с целью повыше- ния быстродействия устройства при поиске слов, ближайших по Хеммингу к признаку опроса, в него введены элементы ИЛИ, элементы ИЛИ-НЕ, вторая группа элементов НЕРАВНОЗНАЧНОСТЬ, формирователи сигналов сдвиг.; и сдвигающая матрица, входные шины столбцов которой соединены с выходами элементов ИЛИ, первые входы которых подключены к выходам элементов ИЛИ-НЕ, первый вход каждого из которьк подключен к выходной шине соответствующего столбца сдвигающей матрицы, а второй вход каждого элемента ИЛИ-НЕ,

кроме последнего,- к выходным шинам

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

сигналов сдвига,первые и вторые входы которых подключены соответственно к выходам элементов НЕРАВНОЗНАЧНОСТЬ первой и второй групп, причем первые входы элементов НЕРАВНОЗНАЧНОСТЬ второй группы соединены с вторыми выходами накопителя, а вторые входы - с вторым выходом регистра опроса, выходные шины строк сдвигающей матрицы подключены к входам регистра результата опроса, управляющий вход которого соединен с вторыми входами элементов ИЛИ.и третьими входами формирователей сигналов сдвига, четвертые и пятые входы которых и третьи входы элементов ИЛИ- НЕ подключены соответственно к другим выходам блока управления ,второй вход последнего элемента.ИЛИ-НЕ подключен к щине питания.

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

«о

1

г,

«5

, ргЭгЕЭг 1„

|1-q L-rji j.-P-L

fil

- оiCj

Я

1 « .

-рЦ...

1

.-4f

ti

tt

j

L ,J

«

Hfr

1±J

«-I

F

Ту;1

lf

fn

4J1

Tin

i:b

/

cb

. M

:h

Ebl

li

«N

NJ

ky

КЗ ii

55 op

|::r

Tl

«

J

lf

c

Ф 11 I

ffl

J

1

/

irh

Й

т

J

То

OmW (От 6 J m/fO-j- 2/

От 6

Редактор М. Товтин

Составитель Т. Зайцева

Техред А.Кравчук Корректор М. Самборская

Заказ 6687/48 Тираж 543Подписное

ВНИИПИ Государственного ко1 штета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная,

91

an

25 I oKW

I

.J

.2

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам. Целью изобретения является повьппение быстродействия устройства при поиске слов, ближайших по Хеммингу к признаку опроса. Устройство содержит накопитель, регистр опроса, блок управления, первую группу элементов НЕРАВНОЗНАЧНОСТЬ, регистр результата поиска, а также вновь введенные формирователи сигналов сдвига, элементы PfflH, элементы ИЛИ-НЕ, вторую группу элементов НЕРАВНОЗНАЧНОСТЬ, и сдвигающую матрицу, каждая ячейка которой содержит триггер и элемент НЕ. Увеличение быстродействия достигается за счет того, что слова, хранящиеся в накопителе, и разряды признака опроса разбиваются на две о сновные части, обработка которых ведется параллельно . Последовательно-поразрядно из накопителя выбираются разрядные срезы, значения которых сравниваются в элементах НЕРАВНОЗНАЧНОСТЬ с признаком опроса. При несовпадении в соответствующей строке сдвигающей матрицы производится сдвиг, например, вправо, установленных ранее нулевых значений и запись в освободивпгуюсн крайнюю левую ячейку единичного значения. Искомым словам соответствуют единичные значения в ячейках крайнего правого столбца сдвигающей матри- цы. Увеличение быстродействия достигается также за счет сокращения времени, необходимого для сдвига значений в матрице и за счет выделения искомого числа за один такт. 1 з.п. ф-лы, 4 ил, 1 табл. (Л ю