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

 

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

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

СОЦИАЛИСТИЧЕСКИХ

PECflYB JlHH

А1 (5И 4 G 1! С 15/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

H A 9TOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИИ (21) 4236710/24-24 (22) 29.04.87 (46) 15.11.88. Бюл. Р 42 (71) Киевский политехнический институт им. 50-летия Великой Октябрьской социалистической революции (72) В.И.Корнейчук, А.П.Марковский и Ю.В.Яблуновский (53) 681.327(088.8) (56) Авторское свидетельство СССР

У 978196, кл. С 11 С 15/00, 1980.

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

У 332502, кл. G 11 С 15/00, 1970. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и предназначено для электронных цифровых вычислительных систем. Цель иэобре„„ЯО„„ЯЯЯ20 тения — расширение области применения устройства за счет введения дополнительных критериев поиска в метрике

Хэмминга. Ассоциативное запоминающее устройство содержит блок 1 памяти размерностью и ш (где и — количество разрядов признака опроса, а m — количество признаков информации), п —разрядный регистр 2 опроса, выполненный в виде регистра сдвига, блок 3 управления, группу элементов ИЛИ, 4, группу счетчиков 5, первый элемент

ИЛИ 6, буФерный регистр 7, выполненный íà D-триггерах, регистр 8 результата поиска, выполненный на Т-триггерах, генератор 9 тактовых импульсов, щ 2 элемент 1О задержки, счетчик 11, первый 12, второй 13 и третий 14 элементы И, первый 15, второй 16 и третий 17 элементы И-НЕ, второй элемент

ИЛИ 18, коммутатор 19, 2 ил.

1437920

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

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

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

Ассоциативное запоминающее устройство содержит (фиг. 1) блок 1 памяти размерностью n- m (где п — количество разрядов признака информации, а m — количество признаков информации), и-разрядный регистр 2 20 опроса, выполненный в вице регистра сдвига, блок 3 управления, группу элементов ИЛИ 4, группу счетчиков 5, I первый элемент ИЛИ 6, буферный регистр

7, выполненный на D-триггерах, регистр

8 результата поиска, выполненный на

Т-триггерах, генератор 9 тактовых импульсов, элемент 10 задержки, счетчик 11, первый 12, ьторой 13 и третий 14 элементы И, первый 15, второй ЗО

16 и третий 17 элементы И-НЕ, второй элемент ИЛИ 18 и коммутатор 19.

Р .выхода 20 21 22 23 24

Сигнал 0 0 0 1

При поступлении на вход 32 блока

3 управляющего импульса в регистр 36 адреса микрокоманд по входу 33 запишется код команды "Подготовка к поII иску . В результате блоком 3 управ- 40 ления на выходах 20-22 выдаются единичные сигналы, обеспечивающие считывание из блока 1 старшего или младшего разряда всех признаков информации с синхронной выборкой чз 45 регистра 2 опроса соответствующего разряда признака опроса. Если из регистра 2 считан единичный. сигнал, то сигналы на выходах коммутатора 19 аналогичны сигналам, считанным с пря--50 мых выходов блока 1 (единицами на выходах коммутатора l9 отмечаются совпавшие разряды соответствующих признаков информации и признака опроса), иначе считываются сигналы с инертных выходов блока 1. Далее единичные сигналы, проходя через элементы ИЛИ 4, записываются в соответствующие счетчики 5.

Блок 3 управления имеет выходы

20-30 и входы 31-33. Устройство имеет вход 34.

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

38 тактовых импульсов, микропрограммную матрицу 39, регистр 40 микрокоманд.

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

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

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

3 управления поддерживаются следующие сигналы:

25 26 27 28 29 30

1 0 0 0 0 0

После окончания серии иэ п аналогичных микрокоманд в счетчиках 5 хранятся суммы количества совпадений разрядов всех признаков информации и признака опроса, а на выходе 22 блока 3 устанавливается нулевой сигнал блокировки коммутатора 19 (на его выходах формируется нулевой код), который поддерживается до окончания любого вида поиска. При этом на вход

32 блока 3 поступает управляющий импульс, разрешающий запись в регистр

36 кода заданного вида поиска (адрес первой мнкрокоманды поиска).

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

1. Поиск ближайшего по Хэммингу.

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

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

55 з

14379 запускаются на счет счетчики 5 и счетчик 11, иначе данный признак отмечается единицей в регистре 8 результата. При переполнении какого-либо из счетчиков 5 единичный сигнал с выхода первого элемента ИЛИ 6 устанавливает на выходах третьего элемента

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

2. Поиск всех больших границы Хэм- 25 минга.

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

3. Поиск всех меньших границы Хэмминга.

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

4. Поиск ближайшего большего границы Хэмминга.

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

5. Поиск равного границе Хэмминга.

После выполнения базового поиска на выходе 25 блока 3 формируется сигнал разрешения обнуления регистра

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

6 ° Поиск ближайшего меньшего границы Хэмминга.

После выполнения базового поиска на выходе 29 блока 3 формируется единичный сигнал разрешения счета счетчиком 11 (его обнуление). На выходах

26 и 27 блока 3 устанавливается соответственно сигнал единичного и нулевого уровней (при этом запускаются на счет все счетчики), а на выходе

25 — сигнал обнуления регистра 8.

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

7. Поиск в интервале границ Хэмминга.

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

5 14 раза: в первом случае на счетчик 11 записывается В,, а после окончания первого базового поиска сигналом с выхода 25 блока 3 осуществляется обнуление регистра 8. В счетчик 11 .записывается (R — К,) и происходит второй базовый поиск,,после чего на выходе 29 блока 3 формируется единичный сигнал, т.е. счетчик 11 устанавливается н исходное состояние, а н регистре 8 фиксируется результат поиска.

8. Поиск нне интервала границ Хэмминга .

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

Хэмминга, т..е, проинвертируется содержимое регистра 8.

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

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

В первой микрокоманде этой команды сигналом с выхода 30 блока 3 разрешается запись веса разряда в счетчик 1 1, а также формируется единичный сигнал на выходе 28 этого блока, т.е. запрещается запись в регистр 36.

Помимо этого единичными сигналами с выходов 20-22 блока 3 разрешается ныборка старшего или младшего разряда из регистра 2 и блока i и разблокируется коммутатор 19. Сигналом с выхода 29 блока 3 запускается на счет счетчик 11 и хранящийся в нем код перезаписынается в счетчики 5, на входы которых поступает единичный сигнал. После переполнения счетчика

11 блокируется коммутатор 19 и разрешается запись в регистр 36. После окончания и аналогичных тактов работы устройства выполняется один из описанных видов поиска.

Если веса разрядов признака опроо са равны степени двойки (2, 2

2 ), a в регистре 2 записан единичный код, то после выполнения описан37920 6 ной команды Подготовка. к поиску" данное устройство может выполнять следующие виды поиска; поиск максимального числа; поиск всех больших заданного числа; поиск ближайшего большего к заданному числу; поиск всех меньших заданного числа; поиск ближайшего меньшего заданного числа; простой ассоциативный поиск; поиск чисел, входящих в заданный интервал; поиск чисел, не нходящих н заданный интервал.

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

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

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

Хэмминга, в него введены коммутатор, генератор тактовых импульсов, счетчик, второй элемент ИЛИ, первый, второй и третий элементы И, элемент задержки, первый, второй и третий элементы И-НЕ и регистр результата поис ка, информационные входы которого соединены с выходами буферного регистра, вход синхронизации регистра результата поиска соединен с выходом элемента задержки, вход которого соединен с выходом третьего элемента И, первый вход которого подключен к входу синхронизации буферного регистра и к выходу первого элемента И-НЕ, первый вход которого соединен с ныходом первого элемента ИЛИ и с первым входом второго элемента И-НЕ, выход которого соединен с первым входом первого элемента И, второй вход которого подключен к выходу генератора тактовых импульсов и к первому входу второго элемента И, выход которого соединен с входом раэрешеЦ)иг. 2

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

Техред М.Ходанич

Корректор З.Лончакова

Редактор М.Бандура

Заказ 5900/52 Тираж 590

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

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

Подписное

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

1437 ния блокировки коммутатора, информационные входы первой и второй групп которого подключены к прямым и инверсным выходам блока памяти, управляющий вход коммутатора соединен с выходом регистра опроса, выходы коммутатора подключены к первым входам элементов ИЛИ группы, вторые входы которых подключены к выходу первого эле-10 мента И и к первому входу второго элемента ИЛИ, выход которого соединен с входом разрешения счета счетчика, выход переполнения которого соединен с третьим входом первого и вторым входом второго элементов И, с вторым входом первого элемента И-НЕ и с первым входом третьего элемента И-НЕ, 11 выход которого подключен к входу Пе920 8 реход к следующей микрокоманде" блока управления, выходы которого с первого по одиннадцатый соответственно соединены с управляющим входом регистра опроса, с управляющим входом блока памяти, с третьим входом второго элемента И, с входом установки в "i" буферного регистра, с вторым входом третьего элемента И, с входом установки в "0" регистра результата поиска, с четвертым входом первого элемента

И, с вторым входом второго элемента

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