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

 

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и предназначено для электронных цифровых вычис лительных систем. Цель изобретения - повьшение быстродействия устройства. Устройство содержит накопители 2,- 2|, регистр 3 опроса, группы элементов НЕРАВНОЗНАЧНОСТЬ 4,- 4,, блоки 5,- 5д постоянной памяти, накапливающие сумматоры 6д, счетчики 7,- 7, сортирующую матрицу 8, регистр 9 результата поиска. Повышение быстродействия устройства при выполнении операции поиска слов, имеющих минимальное кодовое расстояние по отношению к признаку опроса (поиск ближайшего по Хэмманчу), достигается за счет разделения слов массива аргумента на равные части и параллельной их обработки. 2 ил. i (Л с pirjmjnr jnr I I г г-- - J I I I Lfau L---J -J. оэ NU СО 00 С5 фиг.1

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

СО1.1ИАЛИСТИЧЕСНИХ

РЕСПУБЛИН (5D4 G 11 С 15 00

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

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

ОПИСДНИЕ ИЗОБРЕТЕНИЯ /

Н А BTOPCHOMV СВИДЕТЕЛЬСТВУ (21) 3984435/24-24 (22) 29 .11 .85 (46) 30.05.87. Бюл. К - 20 (72) Л.В.Вариченко, В.И.Корнейчук, А.П.Марковский, К.Н.Новиков, М.А.Раков, В.A.Ñìèðíoâ, Ю.А.Томин и Ю.M.Тучин (53) 681.327(088.8) (56) Патент США 16 4084260,кл.364-900, 1978.

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

У 978196, кл. G 11 С 15/00, !981. (54) АССОЦИАТИВНОЕ ЗАПОМИНА10ЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и предназна„„SU, 1314386 А1 чено для электронных цифровых вычис лительных систем. Цель изобретения— повышение быстродействия устройства.

Устройство содержит накопители 2 —

2к, регистр 3 опроса, группы элементов НЕРАВНОЗНАЧНОСТЬ 4 — 4» блоки

5„ — 5М постоянной памяти, накапливающие сумматоры 6, — 6, счетчики 7<—

7» сортирующую матрицу 8, регистр

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

1314386

Изобретение относится к вычислительной технике, в частности к запоминающим устройства (ЗУ)р и предназначено для электронных цифровых вычислительных систем.

Цель изобретения — повьш ение быстродействия устройства.

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

Ассоциативное запоминающее устройство содержит блок 1 управления, основной 2 и дополнительные 2 - 2 накопители, где к — целое число, регистр 3 опроса, основную 4„ и дополнительные 4 — 4 группы элементов

НЕРАВНОЗНАЧЙОСТЬ, блоки 5„ — 5 постоянной памяти, где м — число sanoмннающих ячеек в каждом накопителе 2, накапливающие сумматоры 6, — 6, счетчики 7 — 7M сортирующую матрицу 8, регистр 9 результата поиска. Матрица

8 содержит м (L+P) разрядных ячеек 10. где L=jlog K); P.=)lopez(N/К-1)(; N— разрядность регистра 3 опроса; L и Р— соответственно младшие и старшие раз( ряды ячеек матрицы 8.

Блок 1 управления имеет выходы 1115 и содержит (фиг.2) регистр 16 кода операции, генератор 17 тактовых импульсов, дешифратор 18, микропрограммную матрицу 19 и регистр 20 микрокоманд. Сортирующая матрица 8 может быть построена на триггерах и логических элементах. Каждый из счетчиков 7 служит для подсчета поступающих на его вход единичных импульсов.

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

Слова массива-аргумента хранятся в запоминающих ячейках накопителей

2, а признак опроса — в регистре 3 опроса, причем N-разрядные слова массива-аргумента и признак опроса разбиваются на k, равных частей.

Запоминающие ячейки накопителей

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

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

Коды количества несовпадений, поступающие на входы сумматоров 6, суммируются и накапливаются в сумматорах 6, перенос из которых подается на вход соответствующих счетчиков 7, тем самым увеличивая их содержимое

50 на единицу.

Длительность тактового импульса определяется максимальной задержкой сигнала в блоке 5 постоянной памяти, сумматоре 6 и счетчике 7. Тогда сигналы, поступающие на управляющие вхоредной Разряд содержимого данной ячейки. Аналогично при поступлении управляющего импульса на управляющий вход регистра 3 опроса с выходов этого регистра поразрядно считываются очередные разряды каждой из 1 частей признака опроса.

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

15 9 результата поиска. После этого с выходов 11, 13, 14, 15 подается се-:. рия сигналов единичного уровня на управляющие входы соответственно регистра 3 опроса, накопителей 2, блоков 5 постоянной памяти, сумматоров 6.

В результате происходит последовательная выборка из накопителей 2 и регистра 3 опроса всех разрядных сре25 зов k частей слов массива-аргумента и признака опроса соответственно.Разрядные срезЫ частей всех слов поступают из накопителя 2 на первые входы соответствующих элементов НЕРАВНО-

ЗНАЧНОСТЬ 4, на вторые входы которых

30 поступают с выходов. регистра 3 опроса потенциалы соответствующих разря- . дов каждой из k частей признака onроса.

Сигналы несовпадения значений раз3 13 ды блока 5 постоянной памяти, сумматора.б и счетчика 7 соответственно с выходов 13 и 14 блока 1 управления, обеспечивают совмещение во времени работы блоков постоянной памяти, сумматора 6 и счетчика 7 единиц, т.е. в то время, когда сумматор 6 и счетчик 7 обрабатывают сигнал S-ro (S

=1, — -1) такта,на выходе блока 5 по\ стоянной памяти дублируется код количества несовпадений (S+1)-го такта.

После того, как сумматор 6 и счетчик

7 обработают сигнал N/К-ro такта, сортирующая матрица 8 определяет слово массива-аргумента, ближайшего по

Хэммингу к признаку опроса, т.е. единица на выходе сортирующей матрицы 8 соответствует слову, имеющему минимальное количество совпадений с признаком опроса.

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

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

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

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

131438б ц аа ь ю

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

Техред В.Кадар Корректор.С.Лыжова

Редактор И.Касарда

Заказ 2215/52 Тираж 590 Подписное

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

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

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