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

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

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

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

Ассоциативное запоминающее уст- ройство содержит (фиг, 1) блок 1 памяти размерностью (где п - количество разрядов признака информации, am- Количество признаков ин- . формации)S п разрядньй регистр 2 опроса, вьшолнеиньш в виде регистра сдвигаJ блок 3 управления группу элементов ИЛИ 4, группу счетчиков 5, первьй элемент ИЛИ 6, буферньй регист 7, выполненный на В-триггерах, регист 8 результата поиска, вьшолненньй на Т-триггерах, генератор 9 тактовых импульсов, элемент 10 задержки, счетчик 115 первьш 12, второй 13 и третий 14 элементы И, первый 15, второй 16 и третий 17 элементы , второй элемент ИЛИ 18 и коммутатор 19.

s 0

0

Блок 3 управления имеет выходы 20-30 и входы 31-33. Устройство имеет вход 34.

Блок 3 управления содержит (фиг.2) коммутатор 35, регистр 36 адреса микрокоманды, дешифратор 37, генератор 38 тактовых импульсов, микропрограммную матрицу 39, регистр 40 микрокоманд,

Запоминаюгрге ячейки блока 1 памяти могут иметь различную конструкцию (сдвиговые регистрь} дорожки вращающихся магнитных дисков и т.п). Однако они должны обеспечивать последовательное поразрядное обращение, а именно: при поступлении очередного управляющего импульса на управляющий вход блока 1 с выхода каждой запоминающей ячейки считывается очередной разряд содержимого данной ячейки.

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

Перед началом работы устройства счетчики 5з 11 и регистры 7, 8 обнулены. В блоке 1 хранятся признаки информации, а в регистре 2 - признаки опроса. При этом на выходах блока 3 управления поддерживаются следующие сигналы:

Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и предназначено для электронных цифровых вычислительных систем. Цель изобреi-C2Z тения - расширение области применения устройства за счет введения дополнительных критериев поиска в метрике Хэмминга. Ассоциативное запоминакяцее устройство содержит блок 1 памяти размерностью n«m (где п - количество разрядов признака опроса, am- количество признаков информации), п - разрядньй регистр 2 опроса, выполнен- ньй в виде регистра сдвига, блок 3 управления, группу элементов ИЛИ, 4, группу счетчиков 5, первый элемент ИЛИ 6, буферньй регистр 7, выполнен- ньй на D-триггерах, регистр 8 результата поиска, выполненный на Т-триггерах, генератор 9 тактовых импульсов, элемент 10 задержки, счетчик 11, пер- вый 12, второй 13 и третий 14 элементы И, первый 15, второй 16 и третий 17 элементы И-НЕ, второй элемент ИЛИ 18, коммутатор 19. 2 ил.

выхода 20 21 22 23 24 25 26 27 28 29 30

Сигнал

0001 1 100000

При поступлении на вход 32 блока 3 управляющего импульса в регистр 36 адреса микрокоманд по входу 33 запишется код команды Подготовка к поиску. В результате блоком 3 управ- ления на выходах 20-22 выдаются единичные сигналы, обеспечивающие считывание из блока 1 старшего или младшего разряда всех призн.аков информации с синхронной выборкой из регистра 2 опроса соответствукяцего разряда признака опроса. Если из регистра 2 считан единичньй сигнал, то сигналы на выходах коммутатора 19 аналогичны сигналам, считанным с прямых выходов блока 1 (единицами на выходах коммутатора 19 отмечаются совпавшие разряды соответствующих признаков информации и признака опроса) ,,.

иначе считываются сигналы с инертных gj выходах 26 и 27 блока 3 формируютйя

выходов блока 1, Далее единичные сигналы, проходя через элементы ИЛИ 4, записываются в соответствукщие счетчики 5.

единичные сигналы. Если среди признаков информации нет признака, равно го признаку опроса, то единичным сиг налом с выхода первого элемента И 12

После окончания серии из п аналогичных микрокоманд в счетчиках 5 хранятся СУМ1-1Ы количества совпадений разрядов всех признаков информации и признака опроса, а на выходе 22 блока 3 устанавливается нулевой сигнал блокировки коммутатора 19 (на его выходах формируется нулевой код), который поддерживается до окончания любого вида поискаi При этом на вход 32 блока 3 поступает управлянлций импульс, разрещающий запись в регистр 36 кода заданного вида поиска (адрес первой микрокоманды поиска).

Рассмотрим тепер ь поиск по различным критериям.

единичные сигналы. Если среди признаков информации нет признака, равного признаку опроса, то единичным сигналом с выхода первого элемента И 12

запускаются на счет счетчики 5 и сччик 11, иначе данньй признак отмечается единицей в регистре 8 результата. При переполнении какого-либо из счетчиков 5 единичный сигнал с выхо да первого элемента ИЛИ 6 устанавливает на выходах третьего элемента И-НЕ 16 и первого элемента И 12 сигнал нулевого уровня, т.е. останавли вает все счетчики. Кроме того, этот же сигнал, инвертируясь первым элементом И-НЕ 15, на втором входе этого элемента поддерживает единичньй сигнал, т.е. сигнал переполнения счетчика 11 нулевого уровня, но счечик 11 не переполнен, разрешает запись в регистры 7, 8 кода, поступа- гацего с выходов переполнения счетчиков 5. Таким образом, в регистре 8 единицей отмечается признак, ближайший по Хэммингу к признаку опроса, а в счетчике 11 фиксируется его расстояние Хэмминга к признаку опроса.

В первой микрокоманде поиска.на выходе 30 блока 3 формируется сигнал разрешения записи в счетчик, куда по входам 34 поступает значение R (граничное расстояние Хэмминга). В следующей микрокоманде на выходах 28 и 26 блока 3 установится единичный сигнал, а на выходе 27 - сигнал нулевого уровня, т.е. блокируется запись в регистр 36, запускаются все счетчики на счет. При переполнении какого-либо из счетчиков 5 единичный сигнал с соответствующего выхода переполнения записывается в регистр 7 (в нем хранится только последний единичный сигнал переполнения), после чего он перезаписьшается в регистр 8 причем те триггеры, на информационны входы которых поступает единичный сигнал, меняют свое состояние на противоположное, при поступлении нулевого сигнала их состояние не изменя ется..

После переполнения счетчика 11 работа всех счетчиков прекращается (это обеспечивается подачей на вход первого элемента И 12 нулевого сигнала), а в регистре 8 единицами фиксируется результат поиска.

Данный вид поиска является базовым для всех последующих видов поиска.

15

0

Q

25

g

0

5

0

0

5

После выполнения базового поиска в очередной микрокоманде на выходе 23 блока 3 управления формируется сигнал установки в единицу всех разрядов регистра 7, а на выходе 24 - сигнал разрешения записи в регистр 8. Таким образом, содержимое регистра 8 проин- вертируется, т.е. единицами в нем отмечаются все признаки, меньшие границы Хэмминга.

После вьтолнения базового поиска в очередной микрокоманде на выходе 25 блока 3 управления формируется сигнал обнуления регистра 8, а на выходе 24 - сигнал разрешения записи в регистр 8. Таким образом, в нем фиксируется результат данного вида поиска.

на выходе 25 блока 3 формируется сигнал разрешения обнуления регистра 8, а на выходе 29 - сигнал разрешения счета счетчика 11. Таким образом, на выходе переполнения счетчика 11 устанавливается единичный сигнал и происходит запись в регистры 7, 8 результата поиска (если существует признак информации, расстояние Хэмминга которого равно границе Хэмминга).

После вьтолнения базового поиска на выходе 29 блока 3 формируется единичный сигнал разрешения счета счетчиком 11 (его обнуление). На выходах 26 и 27 блока 3 устанавливается соответственно сигнал единичного и нулевого уровней (при этом запускаются ; на счет все счетчики), а на выходе 25 - сигнал обнуления регистра 8, Затем на выходах 26 и 27 блока 3 устанавливается единичный сигнал, т.е. разрешается остановка всех счетчиков при появлении первого сигнала переполнения счетчиков 5. После появления этого сигнала в регистре 8 зафиксируется результат поиска, а в счетчике 11 - его расстояние ЗСэмминга по.отношению к границе R.

При осуществлении данного вида поиска базовый поиск вьшолняется два

раза: в первом случае на счетчик 11 записьтается R,, а после окончания первого базового поиска сигналом с выхода 25 блока 3 осуществляется обнуление регистра 8 В счетчик 11 записьшается (R, - R, ) и происходит

второй базовый поиск, ,после чего на выходе 29 блока 3 формируется единичный сигнал, т,е, счетчик 11 устанав- ливается в исходное состояние, а в регистре 8 фиксируется результат поиска.

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

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

Работа устройства в данном режиме начинается подачей запускающего им- аульса на вход 32 блока 3, при этом S регистр 36 по входам 33 запишется код команды Подготовка к поиску.

В первой микрокоманде этой команды сигналом с выхода 30 блока 3 разрешается запись веса разряда в счетчик 11, а также формируется единичный сигнал на выходе 28 этого блока, т.е. запрещается запись в регистр 36 Помимо этого единичными сигналами с выходов 20-22 блока 3 разрешается выборка старшего или младшего разряд из регистра 2 и- блока 1 и разблокируется коммутатор 19„ Сигналом с выхода 29 блока 3 запускается на счет счетчик 11 и храняпгнйся в нем код перезаписывается в счетчики 5, на входы которых поступает еданичный сигнал. После переполнения счетчика 11 блокируется коммутатор 19 и разрешается запись в регистр 36, После окончания п аналогичных тактов работы устройства выполняется один из описанных видов поиска.

Если веса разрядов признака опроса равны степени двойки (2 , 2 , ,,, ), а в регистре 2 записан единич- ньй код, то после выполнения описан- Q

5

379206

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

0

5

Ассоциативное запоминающее устройство, содержащее блок памяти,, регистр опроса, информационные входы которого являются признаковьпчи входами устройства, группу элементов .ШШ, первый элемент ИЛИ, буферньй регистр, блок управления и группу счетчиков, выходы переполнения которых подключены к информационным входам буферного регистра и к входам первого элемента ИЛИ, причем входы счетчиков группы подключены к выходам элементов ИЛИ группы, вход Запуск и вход Тип поиска блока управления являются соот0 ветственно входом обращения и входом задания типа поиска устройства, о т- личающееся тем, что, с целью расширения области применения устройства за счет введения дополниf. тельных критериев поиска в метрике Хэмминга, в него введены коммутатор, генератор тактовых импульсов, счетчик, второй элемент ИЛИ, первый, второй и третий элементы И, элемент за0 держки, первый, второй и третий элементы И-НЕ и регистр результата поис-- ка, информационные входы которого соединены с выходами буферного регистра, вход синхронизации регистра

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

g и к выходу первого элемента И-НЕ, первый вход которого соединен с выходом первого элемента ИЛИ и с первым входом второго элемента И-НЕ, выход которого соединен с первым

g входом первого элемента И, второй вход которого подключен к выходу генератора тактовых импульсов и к первому входу второго элемента И, выход которого соединен с входом разрешения блокировки коммутатора, информационные входы первой и второй групп которого подключены к прямым и инверсным выходам блока памяти, управляющий вход коммутатора соединен с выходом регистра опроса, выходы коммутатора подключены к первым входам элементов ШШ группы, вторые входы подключены к выходу первого эле-ю третьего элемента И, с входом установ- мента И и к первому входу второго эле- ки в О регистра результата поиска, мента И.ПИ, выход которого соединен с входом разрешения счета счетчика, выход переполнения которого соединен с третьим входом первого и вторым входом второго элементов И, с вторым входом первого элемента И-ВЕ и с первым входом третьего элемента И-НЕ, выход которого подключен к входу Пес четвертым входом первого элемента И, с вторым входом второго элемента И-НЕ, с вторым входом третьего эле- 15 мента И-НЕ, с вторым входом второго элемента ИЛИ и счетным входом счетчика, входы разрядов которого являются входами установки границы Хэмминга.

Фив. 2

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

третьего элемента И, с входом установ- ки в О регистра результата поиска,

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