Элемент ассоциативной памяти

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОИ:КОМУ СВИ ИТВЛЬСТВУ

Союз Советсмия

Сециапнстичесинк

Республик

< «875460 (61) Дополнительное к ввт. свид-ву (51)М. Кл.з (22) Заявлено 280280 (21) 2889915/18-24 с присоединением заявки Нов

G 11 С 15/00

Государственный комитет

СССР но делам изобретений и открытий (23) Приоритет

Опубликовано 23.10.81. Б«оллетень Ж 39 (53) У4К 881. 327, . (088 ° 8) Дата опубликования описания 2310.81 (72) Авторы

- изобретения

»

»:.

Н.A. Зосимов а и Я. И. Фет

- @Ж -.

«« ., ф т„ .

I $p;» ф «

--... ®ау@ (71) Заявитель (54 ) ЭЛЕИЕНТ АССОЦИАТИВНОЙ IIAMHTH

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

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

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

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

ИЛИ, элемент И, два передающих вентиля, причем входы элемента ИЛИ подключены к прямому выходу триггера и 25 к разрядной шине нуля, а выход - к одно««у из входов элемента И, второй вход которого подключен к логическому входу элемента. Передающие вентили соединены последовательно и включены 30 между разрядной шиной нуля и числовой шиной.

На базе данного элемента реализуется ассоциативная матрица памяти, в которой за одну микрокоманду выполняется поиск чисел, равных, больших или меньших заданного (2) .

Недостатком этого элемента является то, что ассоциативная матрица памяти, реализованная на таких элементах, не может выполнять за одну

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

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

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

ИЛИ являются соответственно первым и вторым логическими выходами элемента.

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

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

НЕРАВНОЗНАЧНОСТЬ 5, второй триггер б, первый 7, второй 8, третий 9, четвертный 10 и пятый 11 элементы И, элемент ИЛИ 12, элемент имеет первый управляющий вход 13.

Триггер б имеет входы 14 и 15 установки "1" и в "0".

Элемент имеет также первый логический вход 16, второй управляющий вход 17, первый логический выход 18.

Триггер б имеет прямой и инверсный выходы 19 и 20, соответственно.

Кроме того, элемент имеет второй логический вход 21 и второй логический выход 22.

Входы элемента НЕРАВНОЗНАЧНОСТЬ

5 подключены к прямому и инверсному выходам:триггера 1 и разрядным шинам

2 и 3, а выход †к одному из входов элемента И 7, другой вход которого явлются первым управляющим входом

13, а выход подключен к входу 14 установки в "1" триггера 6, вход 15 установки в "0" триггера б подключен к выходу элемента И. 8, одни из входов которого являются первым логическим входом и вторым управляннцим входом 17, а другой вход соединен с выходом 22, прямой выход 19 триггера 6, подключен к одному из входов элемента

65 ся элемент, в котором второй триггер

6 находится в состоянии единицы (несовпадение разряда признака и хранящейся в ячейке информации). На первом логическим выходе этой ячейки появится сигнал логического "0", а на втоИ 9, второй вход которого подключен к входу 16 элемента, а выход — к одному нз входов элемента ИЛИ 12, другой вход которого подключен к выходу элемента И 10, входная которого соеди5 иены с инверсным выходом 20 триггера б и вторым логическим входом 21 элемента, первый логический выход 18 элемента соединен с выходом элемента

И 11, входы которого подключены к входу 16 элемента и выходу 20 триггера б, а выход 22 элемента соединен с выходом элемента ИЛИ 12.

При соединении элементов в матрицу ассоциативной памяти выходы 18 и

22 каждого элемента соединены с входами 16 и 21, соответственно, соседнего справа элемента, разрядные шины2 и 3 объединяют элементы одного столбца матрицы, а числовая шина 4 является общей для элементов одной строки

2Q матрицы .(фиг. 2).

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

25 В режиме поиска числовая шина 4 находится в состоянии логического "0", а на разрядные шины 2 и 3 подается парофазный код признака опроса.

Поиск осуществляется за одну Микрокоманду, состоящую из нескольких тактов.

В первом такте поданный на разрядные шины 2 и 3 каждого столбца матрицы код признака одновременно сравнивается в каждом элементе с хранящейся в нем информацией. Сравнение осуществляется элементом НЕРАВНОЗНАЧНОСТЬ 5, выход которого соединен с выходом логического элемента И 7, стробируемого по второму входу сигна10 лом управления с первого управляющего входа 13. В случае несовпадения данного разряда признака с хранящейся в ячейке информацией в этом такте происходит при подаче уровня логичес45 кой "1" на первый управляющий вход

13 занесение сигнала несовпадения . во второй триггер 6 ячейки по входу

14 установки в "1", после чего сигнал на первом управляющем входе в каждой ячейке памяти устанавливается в состояние логического "0".

Во втором такте начинается параллельный опрос всех строк матрнцы памяти на наличие единиц в триггерах 6 элементов. С этой целью на первый логический вход 16 левого (для определенности) элемента каждой строки матрицы подается сигнал логической

"1" . Этот сигнал распространяется по строке до тех пор, пока не встретит875460 ром логическом выходе впервые появится сигнал логической "1" (второй логический вход крайней левой ячейки каждой строки матрицы находится в состоянии логического "0"). Сигнал логи1 ческой "1", появившийся в ячейке с .первой единицей неэквивалентности, распространяется вдоль строки матрицы и появится на втором логическом выходе крайней правой ячейки, если в данной строке больше .не было ни одного несовпадения. Если же в строке имеется еще хотя бы одно несовпадение в ячейке, сигнал логической "1", поступивший на ее второй логический вход не пройдет на второй логичес-, кий выход, соединенный со вторым 15 логическим входом соседней справа ячейки, на втором логическом выходе которой установится состояние логического "0" и т.д.до крайней правой ячейки строки матрицы. В результате 20 опроса матрицы в данном такте будут выделены числа (строки), имеющие кодовое расстояние 1, т.е. несовпадающие в одном разряде с кодом приз-. нака. Если B данном такте опрос не дал результата, т. е. все логические выходы ячеек крайнего правого столбца матрицы находятся в состоянии логического "0", производится повторный опроса матрицы, в каждой строке которой предварительно устанавливается в нулевое состояние второй триггер 6 ячейки, хранящий самую левую единицу несовпадения. Элемент И 8 выдает сигнал установки в "0" на вход 15 триггера 6 только в том случае, если на ее входы поступают сигналы логической "1" с первого логического входа 16 элемента, второго логического выхода 18 и второго управляющего входа 17. Причем сигнал 40 на втором управляющем входе 17 каждого элемента является стробируащим и подается перед окончанием сигнала, подаваемого на первый логический вход 16 элемента, после того, как 4 внешними схемами был. зафиксировав результат опроса матрицы в данном такте.

Таким образом, если в К-ом такте микрокоманды в некоторой стороке матрицы впервые появится сигнал логической единицы на втором логическом выходе 18 крайнего справа элемента, это означает, что результат содержится в данной строке и имеет ко-, довое расстояние К, т.е. хранящееся в данной строке число отличается s

К разрядах от заданного признака и является ближайшим к нему по кодовому расстоянию.

При наличии в матрице хранящихся 40 чисел, равных заданному числу, оии могут быть выявлены при опросе матрицы, если в нее ввести дополнительный столбец из таких же элементов, хранящих код "1". Тогда в первом 65 такте будут обнаружены числа, равные заданному, во втором — числа с кодовым расстоянием 1 и т.д.

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

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

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

:элемента ИЛИ, прямой выход второго триггера подключен к одному из входов третьего элемента И, другой вход которого подключен к первому логичес.кому входу элемента, а выход - к одному as входов элемента ИЛИ, другой вход которого подключен к выходу четвертого элемента И, один из входов которого соединен с инверсным выходом второго триггера, а другой является вторым логическим входом элемента, входы пятого элемента И, подключены к первому логическому входу элемента и инверсному выходу второго триггера, а выходы пятого элемента И и элемента ИЛИ являются соответственно первым и вторым логическими выходами элемента.

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

1. Прангишвили И.В. и др.. Одно;родные микроэлектронные ассоциатив ные процессоры. И., "Советское радио", 1973, с. 17.

2. Авторское свидетельство СССР Р 513392, кл. G 11 С 15/00, 1973 ,(прототип).