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

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

Цепь изобретения - повышение быстродействия и надежности устрой-ч ства :

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

рс;1/истра результата поиска, па:готтител5з соед1 нены с дру г;--ст Еходами 3jiGf ieHTOB НЕРЛВНОЗНАЧ КОСТЬ; выходы которых соединены с входами счетчиков единиц,

йа ф15г-1 приведена функциональная ассопиатизного запоминающего устройства; на. фиг „2 - структурная схема б.тюка управления; на фиг.З зремекные диаграмл5гл работы устрой::: т в а ,

Ассоциативное запоминающее устройство (фиг.1) содержит блок 1 я ра и1ания f накопитель 2, состоящий -; К-разрядны:с запоминающих ячеек, N-разрядный регистр 3 опроса, М элементов НЕРАВНОЗНАЧНОСТЬ 4, М log.T -paзpлдныx двоичных счетчиков 5 единиц, М разрядный регистр 6 результсчта поиска и сортирующую матри;ту 7 , содержащую М

строк по log 2 N в кандой строке. Инверсный HleeK

вы. ход -го запоминающего элемента

i-ro счетчика 5 (1 1 fMT., logjN) соединен с. информационным в.хо.г дом .ij -ой ячейки 8 матрицы 7, Первый логический выход (i, log/j N)-ой ячейки 8 подключен к единичному входу 1-го разряда регистра 6, Нулевые входы всех разрядов регистра. 6 объединены и подключены к выходу 9 блока .1 управления. Управляющие входы накопителя 2 и регистра 3 соеинены соответственно с выходами 10 и 11 блока 1 управления,

Блок 1 управления (фиг,2) содерит регистр 12 кода операции, генератор 13 тактовых импульсов, дешифатор 14, микропрограммную матрицу 15, регистр 16 микрокоманд.

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

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

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

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

В первой микрокоманде выдается сигнал на выходе 9 блока 1, который

О

всех

осуществляет установку в

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

По окончании этого цикла в каждом из счетчиков 5 содержится двоичное число, равное расстоянию Хэмминга между соответств ТЭщим словом массива-аргумента и признаком опроса.

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

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

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

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

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

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

При практической реализации

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

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

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

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

Источники информации,

принятые во вни мание при экспертизе

1,Заявка ФРг 2605344, кл, 42 t2 15/00, опублик, 1978,

2,Патент США 4084260,кл, 364г-900, опублик. 1978 (прототип),

/4

fS

12

Фи8.г

п

i г 5

фиг. Ъ

16

TVyy § Ю 11

/V