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

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

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

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

Ассоциативное запоминающее устройство содержит блок 1 управления, основной 2 и дополнительные 2 накопители, где к - целое число, регистр 3 опроса, основную 4, и дополнительные 4,- 4 ц группы элементов НЕРАВНОЗНАЧНОСТЬ, блоки 5д постоянной памяти, где м - число запоминающих ячеек в каждом накопителе 2, накапливающие сумматоры 6, счетчики 7д,, сортирующую матрицу 8, регистр 9 результата поиска. Матрица 8 содержит м (L+P)-разрядных ячеек 10 где ,, (N/K-) ; N - разрядность регистра 3 опроса; L и Р соответственно младшие и старшие разряды ячеек матрицы 8.

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

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

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

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

редной разряд содержимого данной ячейки. Аналогично при поступлении управляющего импульса на управляющий вход регистра 3 опроса с выходов

этого регистра поразрядно считываются очередные разряды каждой из k частей признака опроса.

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

9 результата поиска. После этого с выходов 11, 13, 14, 15 подается се-., рия сигналов единичного уровня на управляющие входы соответственно регистра 3 опроса, накопителей 2, блоков 5 постоянной памяти, сумматоров 6. В результате происходит последовательная выборка из накоцителей 2 и регистра 3 опроса всех разрядных срезов k частей слов массива-аргумента и признака опроса соответственно.Разрядные срезы k частей всех слов поступают из накопителя 2 на первые входы соответствующих элементов НЕРАВНОЗНАЧНОСТЬ 4.; на вторые входы которых поступают с выходов.регистра 3 опроса потенциалы соответствующих разря- дов каждой из k частей признака опроса.

Сигналы несовпадения значений разрядов i-тых частей ( ,к) чисел с cooтвeтcтвyющи ш разрядами признака опроса на выходах i-тых элементов НЕРАВНОЗНАЧНОСТЬ 4 соответствующих групп поступают : на i-тые адресные

входы соответствующих блоков 5 постоянной памяти, соответствующих каждому слову массива-аргумента, на выходах которых формируется код количества несовпадений значений k разрядов слов с соответствующими разрядами признака опроса.

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

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

313

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

N

1, 1) такта,на выходе блока 5 постоянной памяти дублируется код количества несовпадений (S+l)-ro такта. После того, как сумматор 6 и счетчик 7 обработают сигнал N/K-ro такта, сортирующая матрица 8определяет слово массива-аргумента, ближайшего по Хэммингу к признаку опроса, т.е. единица на выходе сортирующей матрицы 8 соответствует слову, имеющему минимальное количество совпадений с признаком опроса.

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

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

64

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

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

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

фиг. 2

if 15

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и предназначено для электронных цифровых вычис лительных систем. Цель изобретения - повьшение быстродействия устройства. Устройство содержит накопители 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