Элемент ассоциативной памяти Советский патент 1981 года по МПК G11C15/00 

Изобретение относится к запоминаю щим устройствам и может быть использ вано при построении матричных ассоци ативных устройств хранения информаци Известен элемент ассоциативной па мяти, содержащий триггер, элементы управления записью, считыванием, а также схему сравнения, входы которой соединены с выходами триггера и d шиной опроса til. Недостатком этого элемента являет ся ограниченное количество логических операций, выполняемых в нем за одну микрокоманду, и как следствие этого, низкое быстродействие при выполнении в ассоциативной матрице памяти поиска информации по сложному критерию. Наиболее близким техническим решением к изобретению является элемен содержащий триггер со схемами управления записью-считыванием, элемент ИЛИ, элемент И, два передающих вентиля, причем входщ элемента ИЛИ подключены к прямому выходу триггера и к разрядной шине нуля, а выход - к однок из входов элемента И, второй вход которого подключен к логическом входу элемента. Передающие вентили соединены последовательно и включены между разрядной шиной нуля и числовой шиной. На базе данного элемента реализуется ассоциативная матрица памяти, в которой за одну микрокоманду выполняется поиск чисел, равных, больших или меньших заданного С2. Недостатком этого элемента является то, что ассоциативная матрица памяти, реализованная на таких элементах, не может выполнять за одну микрокоманду операцию поиска чисел, ближайших (по кодовому расстоянию) заданном/г что снижает быстродействие и ограничивает область применения элемента. Цель изобретения - повышение быстродействия и расширение области применения элемента за счет обеспечения возможности поиска чисел, ближайших по кодовому расстоянию к заданному. Поставленная цель достигается тем, что в элемент ассоциативной памяти, содержащий первый триггер, входы которого подключены к разрядным и числовой шинам, элемент ИЛИ и перйый элемент Иг введено второй триггер, элемент НЕРАВНОЗНАЧНОСТЬ, второй, третий, четвертый-и пятый элементы И, причем входа элемента НЕРАВНОЗНАЧНОСТЬ подключены к выходам первогр триггера и к разрядным шинам, а выход - к одном из входов первого элемента И, другой вход которого является первым управлякхцим входом элемента, а выход подключен к входу установки в 1 второго триггера, вход установки в О которого подключен к выходу второго элемента И, один из входов которого являются первым логическим входом и вторым управляющим входом элемента а другой вход соединен с выходом элемента ИЛИ, прямой выход второго триггера подключен к одному из входов третьего элемента И, другой вход которого подключен к первому логическому входу элемента, а выход - к одному из входов элемента ИЛИ, другой вход, которого подключен к выходу четвертого элемента И, один из входов которого соединен с инверсным выходом второго триггера, а другой является вторым логическим входом элемента, входы пятого элемента И подключены к первому логическому входу элемента и инверсному выходу второго триггера а выходы пятого элемента И и элемент ИЛИ являются соответственно первым и вторым логическими выходги«1И элемента. На фиг. 1 приведена функциональная схема элемента ассоциативной памяти; на фиг. 2 - структурная схем ассоциативной матрицы памяти. Элемент ассоциативной памяти (фиг. 1) содержит первый триггер 1, включающий cxeMJ управления записьюсчитыванием (не показано), разрядные шины 2 и 3, числовую шину 4, элемент НЕРАВНОЗНАЧНОСТЬ 5, второй триггер 6 первый 7, второй 8, третий 9, четвертньА10 и пятый 11 элементы И, элемент ИЛИ 12, з лемент имеет первый управляющий вход 13. Триггер 6 имеет входы 14 и 15 установки 1 и в О. Элемент имеет также первый логический вход 16, второй управляющий вход 17, первый логический выход 18. Триггер 6 имеет прямой и инверсны выходы 19 и 20, соответственно. Кроме того, элемент имеет второй логический вход 21 и второй логический выход 22. Входы элемента НЕРАВНОЗНАЧНОСТЬ 5 подключены к прямому и инверсному выходам:триггера 1 и разрядным шинам 2 и 3, а выход -к одному из входов элемента И 7, другой вход которого первым управляющим входом 13, а выход подключен к входу 14 установки в 1 триггера б, вход 15 установки в О триггера б подключен к выходу элемента И 8, одни из входов которого являются первым логичес ким входом и вторым управляющим входом 17, а другой вход соединен с выходом 22, прямой выход 19 триггера 6 подключен к одному из входов элемент И 9, второй вход которого подключен к входу 16 элемента, а выход - к одному из входов элемента ИЛЦ 12, другой вход которого подключен к выходу элемента И 10, входы которого соединены с инверсным выходом 20 триггера б и вторым логическим входом 21 элемента, первый логический выход 18 элемента соединен с выходом элемента И 11, входы которого подключены к входу 16 элемента и выходу 20 триггера 6, а выход 22 элемента соединен с выходом элемента ИЛИ 12. При соединении элементов в матрицу ассоциативной памяти выходы 18 и . 22 каждого элемента соединены с входами 16 и 21, соответственно, соседнего справа элемента, разрядные шины2 и 3 объединяют элементы одного столбца матрицы, а числовая шина 4 является общей для элементов одной строки матрищл (фиг. 2}. Предлагаемый элемент может работать, в составе ассоциативной матрицы памяти в режиме поиска чисел, ближайших по кодовому расстоянию заданному. В режиме поиска числовая шина 4 находится в состоянии логического О, а на разрядные шины 2 и 3 подается парофазный код признака опроса. Поиск осуществляется за одну микрокоманду, состоящую из нескольких тактов. В первом такте поданный на разрядные шины 2 и 3 каждого столбца матрицы код признака одновременно сравнивается в каждом элементе с хранящейся в нем информацией. Сравнение осуществляется элементом НЕРАВНОЗНАЧНОСТЬ 5, выход которого соединен с выходом логического элемента И 7, стробируемого по второму входу сигналом управления с первого управляющего входа 13. В случае несовпадения данного разряда признака с хранящейся в ячейке информацией в этом такте происходит при подаче уровня логической 1 на первый управляющий вход 13занесение сигнала несовпадения во второй триггер б ячейки по входу 14установки в 1, после чего сигнал на первом управляющем входе в каждой ячейке памяти устанавливается в состояние логического О. Во втором такте начинается параллельный опрос всех строк матрицы памяти на наличие единиц в триггерах б элементов. С этой целью на первый логический вход 16 левого (для определенности) элемента каждой строки матришл подается сигнал логической 1. Этот сигнал распространяется по строке до тех пор, пока не встретится элемент, в котором второй триггер 6 находится в состоянии единицы (несовпадение разряда признака и хранящейся в ячейке информации). На первом логическим выходе этой ячейки появится сигнал логического О, а на втором логическом выходе впервые появится сигнал логической 1 (второй логческий вход крайней левой ячейки каждой строки матрицы находится в состоянии логического О). Сигнал логи1ческой 1, появившийся в ячейке с (первой единицей неэквивалентности, распространяется вдоль строки матрицы и появится на втором логическом выходе крайней правой ячейки, если в данной строке больше .не было ни одного несовпаЩения. Если же в строк,е имеется еще хотя бы одно несовпадение в ячейке, сигнал логической 1, поступивший на ее второй логический вход не пройдет на второй логический выход, соединенный со вторым,. логическим входом соседней справа ячейки, на втором логическом выходе которой установится состояние логического О и т.д.до крайней правой ячейки строки матрицы. В результате опроса матрицы в данном такте будут выделены числа (строки), имеющие кодовое расстояние 1, . несовпадающие в одном разряде с кодом призг нака. Если в данном такте опрос не дал результата, т.е. все логические выходы ячеек крайнего правого столбца матрицы находятся в состоянии логического О, производится повторный опроса матрицы, в каждой строке которой предварительно устанавливается в нулевое состояние второй триггер 6 ячейки, хранящий самую левую единицу несовпадения. Элемент И 8 выдает сигнал установки в О на вход 15 триггера 6 только в том случае, если иа ее гходы поступают сигналы логической 1 с первого яогического входа 16 элемента, второго логического выхода 18 и второго управляющего входа 17. Причем сигнгш на втором управляющем входе 17 каж дого элемент.а является стробирумпот и подается перед окончанием сигнала, подаваемого на первый логический вход 16 элемента, после того, как внешними схемами был зафиксирован результат опроса матрицы в данном такте. -..-..

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

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

такте будут обнаружены числа, равные заданному, во втором - числа с кодовым расстоянием 1 и т.д.

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

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

s

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

0 из входов первого элемента И, другой вход которого является первым управлякнцим входом элемента, а выход подключен к входу установки в I второго триггера, вход установки в О

5 которого подключен к выходу второго элемента И, одни из входов которого являются первым логическим входом и вторым управляющим входом элемента, la другой -вход соединен с выходом

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

5 вход которого подключен к выходу четвертого элемента И, один из входов которого соединен с инверсным выходом второго триггера, а другой является вторым логическим входом

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

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

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

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

5

te с ем

«vjЧ

frvj

л 1 Ч|