Ассоциативная запоминающая матрица

 

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

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

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

РЕСПУБЛИК (19) (11) (51) 4 (11 С 15/00 е4

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ

К ABTOPCHOMY СВИДЕТЕЛЬСТВУ (21) 3861118/24-24 (22) 01.03.85 (46) 07.12.86. Бюл, И 45 (71) Киевский ордена Ленина политехнический институт им,50-летия Великой Октябрьской социалистической революции (72) В.И.Корнейчук, А.П.Марковский и Ю.В.Яблуновский (53) 681.327(088.8) (56) Авторское свидетельство СССР

У 920841, кл, G 11 С 15/00, i980.

Авторское свидетельство СССР й- 898504, кл. G 01 С 15/00, 1980. (54) АССОЦИАТИВНАЯ ЗАПОМИНАЮЩАЯ МАТРИЦА (57) Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано в цифровых системах обработки информации. Цель изобретения — расширение функциональных воэможностей матрицы за счет обеспечения ассоциативного поиска слова, ближайщего к признаку поиска. Она содержит ячейки памяти, подключенные по строкам к входным шинам выборки слов и выходным шинам результата поиска, а по столбцам — к маскирующим шинам, входным и выходным информационным шинам, две группы элементов

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

1 1

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

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

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

Ассоциативная запоминающая матрицы (фиг.1) содержит ячейки 1.1 памят д ти (j = 1,m; i 1,п где п — количество столбцов, * m — количество строк; матрицы).

Первые 2 и вторые 3 входы ячеек 1 памяти одноименных столбцов матрицы подключены к соответствующим маскирующим 4 и"входным информационным 5 шинам, а первые выходы 6 — к выходным информационным шинам 7, Третьи входы 8 ячеек 1 памяти одноименных строк матрицы соединены с соответствующими входными шинами 9 выборки слов, а вторые выходы 10 — с выходными шинами 11 результата поиска.Матрицы содержат первую группу элементов НЕ 12, имеющих входы 13 и вторую группу элементов НЕ 14. Кроме того, на фиг, 1 обозначены шина 15 синхронизации, входная управляющая шина 16, четвертые 17, пятые 18 и шестые 19 входы ячеек 1 памяти, третьи выходы 20, седьмые входы 21,четвертые 22 и пятые 23 выходы ячеек памяти, Матрица также содержит элементы развязки, выполненные в виде резисторов 24 — 27, подключенных к источнику 28 потенциала логической единицы.

Каждая ячейка 1 памяти (фиг.2) содержит элемент 29 памяти, элементы ИЛИ-НЕ 30 — 33 с первого по четвертый, первый 34 и второй 35 элементы НЕ, элемент 36 задержки, элемент И 37, элемент ИЛИ 38, элемент

И-НЕ 39 и элемент РАВНОЗНАЧНОСТЬ 40.

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

В исходном состоянии на управляющей шине 16 установлен потенциал едИничного уровня, которым на выходах 22 и 23 всех ячеек 1 памяти устанавливается потенциал логического нуля и единицы соответственно. На вы275546 2 ходах 20 каждой ячейки 1 памяти устанавливается потенциал единичного уровня, так что потенциал на входах

20 соответствует единичному уровню, Шина 15 синхронизации имеет нулевой потенциал.

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

В режиме адресного считывания на шину 9 выборки слова, определяемую задаваемым адресом слова, подается сигнал нулевого уровня, который, поступая через входы 8 ячеек 1 памяти соответствующей строки на входы элементов ИЛИ 38, формирует на выходе последних сигналы, соответствующие состоянию элементов 29 памяти, В режиме ассоциативного поиска, ближайшего по Хеммингу,признак опроса подается на информационные шины

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

На управляющую шину 16 подается нулевой потенциал, который, поступая на входы 17 каждой ячейки 1 памяти, разрешает их работу в режиме ассоциативного поиска, ближайшего по Хеммингу,B кроме того,инвертируясь элементами НЕ 12, поступает в виде сигнала поиска на входы 19 всех ячеек 1 памяти первого столбца. Его содержимое ячейки 1 памяти первого столбца совпадает с сигналом на шине 5.1 (первым разрядом признака опроса), то сигнал поиска с выхода 22 „ этой ячейки поступает на вход 19 соответствующей ячейки 1 памяти. В случае, если содержимое ячейки 1, не совпадает со значением первого разряда входного слова, то сигнал поиска на выходе 22, не формируется, а сама ячейка 1, блокируется, При маскировании ячейки 1 памяти сигнал поиска беспрепятственно проходит с ее входов

19 и 18 на выходы 22 и 23 и далее на следующую по строке ячейку 1 памяти.

Таким образом, сигнал поиска проходит через любую другую ячейку 1 памяти при совпадении ее содержимого со значением соответственно разряда входз 1275 ного слова и блокируется, в противном случае, при незамаскированном этом разряде. Таким образом, в каждой строке матрицы сигнал поиска распространяется последовательно по ячейкам строки до тех пор, пока не заблокируется ячейкой 1 памяти, содержимое которой не совпадает со значением

К-го разряда признака опроса. При этом на выходах 10 (р4 К) устанавли- 10

P вается потенциал единичного уровня,а на выходе 10„ — потенциал нулевого уровня. Если все немаскируемые разряды признака опроса совпадают с содержимым соответствующих ячеек 1 строки 15 (т,е, расстояние Хемминга равно нулю), то на выходах 10 всех ячеек 1 памяти, принадлежащих данной строке, формиру ется единичный сигнал, который, поступая на шину 11, соответствующую 20 данной строке, свидетельствует об окончании процесса поиска и указывает на стро. у, содержимое которой совпадает в незамаскированных разрядах с заданным словом

Если такой строки нет, то сигналы поиска блокируются на всех строках.

Каждая ячейка 1 памяти, блокирующая 30 прохождение сигнала поиска, формиру-, ет на своем выходе 20„ сигнал нуле-. вого уровня (в то время как на выходах 20 (р Ф К) остальных ячеек 1

Ф памяти формируются сигналы единичного уровня). Когда блокируется прохождение сигнала поиска во всех строках, то на всех выходах 20 ячеек 1 памяти устанавливается сигнал нулевого уровня, который, инвертируясь 40 элементами НЕ 14, преобразуется в сигнал единичного уровня на шийе 15 синхронизации, который, поступая на входы 21 каждой ячейки 1 памяти,разблокирует заблокированные ячейки 1 . 4

Процесс распространения сигналов поиска по строкам матрицы продолжается и проходит до тех пор, пока не заблокируется во всех строках и в этом случае устройство функционирует по 50 описанному способу, либо не формируется единичный сигнал на одной из шин 11 результата поиска. В этом последнем случае шина 11, на которой сформирован сигнал единичного уров- 55 ня, указывает на строку, ближайшую по Хеммингу к признаку опроса

546 4

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

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

2. Матрица по п.1, о т л и ч аю щ а я с я тем, что каждая ячей ка памяти содержит элемент памяти, элементы ИЛИ-НЕ с первого по четвертый, первый и второй элементы

НЕ, элемент задержки, элемент И элемент ИЛИ, элемент И-НЕ и элемент

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

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

1275546

47

/У

23

24 б /Р

Составитель В.Рудаков

Техред Л.Олейник Корректор М.Самборская

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

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

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

Редактор И.Дербак

Заказ 6569/46

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