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

 

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

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

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

РЕСПУБЛИК

„Л0„„1277211 А1 (51)4 С 11 С 15 00

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

Н АBTOPCHOMY СВИДЕТЕЛЬСТВУ

:В»

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

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

Р 1095238, кл. С 11 С 15/00, 1983.

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

Р 978196, кл. С 11 С 15/00, 1982. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам. Целью изобретения является повышение быстродействия устройства при поиске слов, ближайших по Хеммингу к признаку опроса.

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

1277211

Изобретение относится к вычислительной технике, в частности к sanoминающим устройствам.

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

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

Предлагаемое устройство содержит (фиг. 1) блок 1 управления, накопитель 2, регистр 3 опроса, первую 4 и вторую 5 группы элементов НЕРАВНОЗНАЧНОСТЬ, формирователи 6 сигналов сдвига, сдвигающую матрицу 7, регистр

8 результата поиска с входом 9. На фиг. 1 обозначены ячейки 10 сдвигающей матрицы 7. Устройство содержит также элементы ИЛИ 11, элементы ИЛИНЕ 12, выходные шины 13 строк, выходные шины 14 столбцов сдвигающей матрицы 7.

Сдвигающая матрица 7 содержит первую 15 и вторую 16 группы нагрузочных элементов. На фиг. 1 обозначены шина 17 питания, выходы l8-23 блока 1 управления. Каждая ячейка

10 сдвигающей матрицы 7 содержит (фиг. 2) триггер 24 и элемент НЕ 25.

Блок 1 управления содержит (фиг.3) дешиФратор 26, микропрограммную матрицу 27, регистр 28 микрокоманд, регистр 29 кода операции и генератор

30 тактовых сигналов.

Формирователь 6 сигналов сдвига содержит (фиг. 4) элементы И-HE 31—

34, триггер 35 и элемент ИЛИ-HE 36.

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

2, а признак опроса — в регистре 3, причем М вЂ” разрядное слово-аргумент и признак опроса разбиваются на две равные части и в одной части (например, левой) записаны старшие раз Ряды слова-аргумента и признака опроса, а в другой — младшие их разряды. Дальшейшее разбиение Г1 — разрядного слова-аргумента и признака опроса приводит к значительному усложнению конструкции формирователей 6, что затрудняет выполнение изложенных ниже требований к ним. Запоминающие ячейки накопителя 2 и регистр 3 мо5

10 !

5 гут иметь различную конструкцию (статическое или динамическое ЗУ, сдвиговые регистры, 3У на ЦИД, дорожки вращающихся магнитных ЗУ и т.д.).

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

Число ячеек 10 в строке матрицы 7

M равно — ——

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

При поступлении на входы блока 1 (фиг. 1) команды поиска блок 1 вырабатывает следующую последовательность операций. В первой микрокоманде на выходах 20, 22 и 23 формируются: на выходе 20 — сигнал (логи25 ческая единица), не препятствующий нормальной работе формирователей 6; на выходе 22 — сигнал (логическая единица), который осуществляет установку в "1" всех разрядов регистра

30 8, формирователей 6 и ячеек 10 матрицы 7; на выходе 23 — сигнал (логическая единица), запрещающий поиск строки матрицы 7, имеющей максимальное число единиц.

Затем в ряде последовательных микрокоманд выдается серия сигналов на вьгходах 18,19 и 21. В результате происходит последовательная выборка из накопителя 2 всех разрядных срезов

А0 (отдельно группы младших и старших разрядов) массива слов-аргументов с синхронной выборкой соответствующих разрядов регистра 3. Разряды всех P слов (для каждого слова выбирается ,г два разряда: один иэ группы младших, а другой из группы старших) поступают из накопителя 2 на первые входы соответствующих элементов НЕРАВНОЗНАЧНОСТЬ 4, 5, причем младшие разрядьг поступают на входы элементов НЕРАВНОЗНАЧНОСТЬ, а старшие разряды поступают на входы элементов НЕРАВНО-

ЗНАЧНОСТЬ 5. Одновременно из регистра 3 поступают соответствующие младшие разряды на входы всех элементов

НЕРАВНОЗНАЧНОСТЬ 4, а старшие pasряды — на входы элементов НЕРАВНОЗНАЧНОСТЬ 5. Для тех слов, где значение какого-либо разряда совпадает

12772

Выходной. сигнал формирователя 6 в К вЂ” ом такте

Содержимое триггера 35

Сигналы на выходах элементов НЕРАВНОЗНАЧНОСТЬ 4 и 5 в К-ом такте в К-ом В К+1— такте ом такте

О 0

01 (10) 0 О

О 35

01 (10) 40 со значением соответствующего разряда признака опроса, на выходах соответствующих элементов НЕРАВНОЗНАЧНОСТЬ 4 или 5 формируются сигналы нулевого уровня, которые поступают на входы соответствующих формирователей 6, каждый из которых работает в соответствии с таблицей. Задержка сигнала в формирователе 6 должна быть равна ;задержке сигнала при

1О сдвиге в строке матрицы 7. Сигнал, поступающий на входы формирователей

6 с выхода 21, обеспечивает совмещение во времени работы формирователей

6 и матрицы 7, т.е. в то время, когда матрица 7 отрабатывает сигнал одного такта, формирователи 6 отрабатывают сигнал последующего такта.

Если на выходе К-oro (К 1, P) формирователя 6 формируется сигнал разрешения сдвига (логическая единица), поступающий на входы синхрониза45 ции всех ячеек 10 К-ой строки матрицы 7, то в этой строке произойдет сдвиг содержимого ячеек 10 на один разряд вправо, а в освободившуюся, например, крайнюю левую ячейку 10 этой строки запишется "1", в противном случае содержимое строки ячеек

10 матрицы 7 не изменится. По окончаM нии серии из (— — +1) -го сигналов, формируемых на выходах 18 и 19, на выходе 20 формируется сигнал ("0"), который, поступая на первые входы

11 формирователей 6, формирует на их выходах сигнал разрешения сдвига ("1"), если в триггере 35 (фиг. 4) этого формирователя 6 хранилась "1", и сигнал запрещения сдвига — в противоположном случае.

М

На (+2)-ом такте с выхода 21

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

M (+ 3) -ом такте и сводится к уста2 новке (сигналами, поступающими с выходов соответствующих элементов ИЛИ

11) в "0" всех ячеек 10, кроме ячеек

10 столбца матрицы 7, в котором содержится самая правая "1", причем строка, в которой содержится указанная "1", соответствует слову, ближайшему к признаку опроса по критерию

Хемминга. После установки в "0" укаванных выше ячеек 10, сигнал нулевого уровня на одной из шин 13 укажет на слово-аргумент, имеющее минимальное кодовое расстояние к признаку опроса,. т.е. слово, ближайшее по Хеммингу к признаку опроса.

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

Увеличение быстродействия достигается за счет разделения слов-аргументов и признака опроса на две рав5 12772 ные части и их параллельной обработки при выполнении операции поиска слов„ ближайших по Хеммингу к признаку опроса, а также за счет сокращения времени, необходимого для сдвига информации в строке матрицы 7 и за счет того, что выделение искомого числа в матрице 7 занимает один такт.

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

1 ° Ассоциативное запоминающее устройство, содержащее регистр опроса, накопитель, первую группу элементов

НЕРАВНОЗНАЧНОСТЬ, регистр результата поиска и блок управления, одни из выходов которого подключеиы к управляющим входам регистра опроса, регистра результата поиска и накопителя, одни из выходов которого соединены 2р с первыми входами элементов НЕРАВНОЗНАЧНОСТЬ первой группы, вторые входы которых подключены к первому выходу регистра опроса, о т л и ч а ющ е е с я тем, что, с целью повыше- 25 ния быстродействия устройства при поиске слов, ближайших по Хеммингу к признаку опроса, в него введены элементы ИЛИ, элементы ИЛИ-НЕ, вторая группа элементов НЕРАВНОЗНАЧНОСТЬ 30 формирователи сигналов сдвиг,; и сдвигающая матрица, входные шины столбцов которой соединены с выходами элементов ИЛИ, первые входы которых подключены к выходам элементов IUIH-HI, первый вход каждого из которых подключен к выходной шине соответствующего столбца сдвигающей матрицы, а второй вход каждого элемента ИЛИ-НЕ, кроме последнего, — к выходным шинам последующих столбцов сдвигающей матрицы, входные шины строк которой соединены с выходами формирователей сигналов сдвига, первые и вторые входы которых подключены соответственно к выходам элементов НЕРАВНОЗНАЧНОСТЬ первой и второй групп, причем первые входы элементов НЕРАВНОЗНАЧНОСТЬ второй группы соединены с вторыми выходами накопителя, а вторые входы — с. вторым выходом регистра опроса, выходные шины строк сдвигающей матрицы подключены к входам регистра результата опроса, управляющий вход которого соединен с вторыми входами элементов ИЛИ .и третьими входами формирователей сигналов сдвига, четвертые и пятые входы которых и третьи входы элементов ИЛИНЕ подключены соответственно к другим выходам блока управления, второй вход последнего элемента ИЛИ-НЕ подключен к шине питания.

2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что сдвигающая матрица содержит триггеры, элементы

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

НЕ, выхбд которого подключен к выходной шине строки, вгорые выходы триггеров в столбце соединены с выходной шиной столбца, вторые выводы одних из нагрузочных элементов подключены к выходным шинам строк, а вторые выводы других нагрузочных элементов— к выходным шинам столбцов.

1277211

1277211

0m 10 (Orn6j оАп ЛО0mE

Л

I

6 9202/22 23 Ьг. 2

Фиг. Ф

Составитель Т. Зайцева

Техред A.Êðàâ÷óê Корректор M. Самборская

Редактор М. Товтин

Заказ 6687/ч8

Тираж 5ч3 Подписное

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

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

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