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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК127 С 11 С 150 ПИСАНИЕ ИЗОБРЕТЕН ЛЬСТИ У 885162/24-246,04.855.12.86. Бюл.невский орденаий институт имтябрьской соци(21) 3 (22) 1 (46) 1 (71) К ническ кой Ок волюци 6 тех енина по 50-летия елиистическои П. МарковскийГ оэовский ОСУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ ИОТКРЫТИЙ К АВТОРСКОМУ СВИ(56) Авторское свидетельство СССР Р 1095238, кл. С 11 С 15/00, 1983,Авторское свидетельство СССР Р 978196, кл. С 11 С 15/00, 1982. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО(57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, Целью изобретения является повышение быстродействия устройства при поиске слов, ближайших по Хеммингу к признаку опроса. Устройство содержит накопитель, регистр опроса, блок управления, первую группу элементов НЕРАВНОЗНАЧНОСТЬ, регистр результата поиска, а также вновь введенные формирователи сигналов сдвига, элементы ИЛИ, элементы ИЛИ-НЕ, вторую группу элементов НЕРАВНОЗНАЧНОСТЬ.и сдвигающую матрицу, каждая ячейка которой содержит триггер и элемент НЕ. Увеличение быстродействия достигается за счет того, что слова, хранящиеся в накопителе, и разряды признака опроса разбиваются на две основные части, обработка которых ведется параллельно. Последовательно-поразрядно из накопителя выбираются разрядные срезы, значения которых сравниваются в элементах НЕРАВНОЗНАЧНОСТЬ с признаком опроса. При несовпадении в соответствующей строке сдвигающей матрицы производится сдвиг, например, вправо, установленных ранее нулевых значений и запись в освободившуюся крайнюю левую ячейку единичного значения. Искомым словам соответствуют единичные значения в ячейках крайнего правого столбца сдвигающей матрицы. Увеличение быстродействия достигается также за счет сокращения времени, необходимого для сдвига значений в матрице и за счет выделения искомого числа за один такт. 1 з.п. ф-лы, 4 ил, 1 табл.Изобретение относится к вычислительной технике, в частности к запоминающим устройствам.Цель изобретения - повышение быстродействия устройства при поиске слов, ближайших по Хеммингу к признаку опроса.На фиг. 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 питания, выходы 18-23 блока 1 управления. Каждая ячейка 10 сдвигающей матрицы 7 содержит(фиг. 2) триггер 24 и элемент НЕ 25,Блок 1 управления содержит (фиг.3) дешифратор 26, микропрограммную матрицу 27, регистр 28 микрокоманд, регистр 29 кода операции и генератор 30 тактовых сигналов.Формирователь 6 сигналов сдвига содержит (фиг. 4) элементы И-НЕ 31 - 34, триггер 35 и элемент ИЛИ-НЕ 36.Слова массива-аргумента хранятся в запоминающих ячейках накопиеля 2, а признак опроса - в регистре 3, причем М - разрядное слово-аргумент и признак опроса разбиваются на две равные части и в одной части (например, левой) записаны старшие разряды слова-аргумента и признака опроса, а в другой - младшие их разряды. Дальшейшее разбиение Г 1 - разрядного слова-аргумента и признака опроса приводит к значительному усложнению конструкции формирователей 6, что затрудняет выполнение изложенных ниже требований к ним. Запоминающие ячейки накопителя 2 и регистр 3 мо 5 10 5 гут иметь различную конструкцию (статическое или динамическое ЗУ, сдвиговые регистры, 3 У на ЦМД, дорожки вращающихся магнитных ЗУ и т.д.), Однако они должны обеспечивать последовательное поразрядное обращение, а именно: при поступлении очередного управляющего импульса на входы регистра 3 и накопителя 2 с выходов каждой запоминаюшей ячейки одновременно считываются очередные разряды левой и правой частей данной ячейки, Число ячеек 10 в строке матрицы 7Мравно ---2Предложенное устройство работает следующим образом. При поступлении на входы блока 1 (фиг. 1) команды поиска блок 1 вырабатывает следующую последовательность операций. В первой микрокоманде на выходах 20, 22 и 23 формируются: на выходе 20 - сигнал (логи ческая единица), не препятствующийнормальной работе формирователей 6;на выходе 22 - сигнал (логическаяединица), который осуществляет установку в "1" всех разрядов регистра 30 8, формирователей 6 и ячеек 10 матрицы 7; на выходе 23 - сигнал (логическая единица), запрещающий поискстроки матрицы 7, имеющей максимальное число единиц.Затем в ряде последовательных микрокоманд выдается серия сигналов навьгходах 18,19 и 21. В результате происходит последовательная выборка изнакопителя 2 всех разрядных срезов А 0 (отдельно группы младших и старшихразрядов) массива слов-аргументов ссинхронной выборкой соответствующихразрядов регистра 3, Разряды всех Рслов (для каждого слова выбираетсядва разряда: один иэ группы младших,а другой из группы старших) поступают из накопителя 2 на первые входысоответствующих элементов НЕРАВНОЗНАЧНОСТЬ 4, 5, причем младшие разряды поступают на входы элементов НЕРАВНОЗНАЧНОСТЬ, а старшие разрядыпоступают на входы элементов НЕРАВНО-ЗНАЧНОСТЬ 5. Одновременно из регистра 3 поступают соответствующие младшие разряды на входы всех элементовНЕРАВНОЗНАЧНОСТЬ 4, а старшие разряды - на входы элементов НЕРАВНОЗНАЧНОСТЬ 5. Для тех слов, где значение какого-либо разряда совпадает12772 Выходной. сигналформирователя 6 в К - ом такте Содержимоетриггера 35 Сигналы на выходах элементов НЕРАВНОЗНАЧНОСТЬ 4и 5 в К-омтакте В К+1 -омтакте в К-омтакте 0 0 0300 01 (10) 0 0 0 35 01(10) 40 со значением соответствующего разряда признака опроса, на выходах соответствующих элементов НЕРАВНОЗНАЧНОСТЬ 4 или 5 формируются сигналы нулевого уровня, которые поступают 5 на входы соответствующих формирователей 6, каждый из которых работает в соответствии с таблицей. Задержка сигнала в формирователе 6 должна быть равна;задержке сигнала при1 О сдвиге в строке матрицы 7, Сигнал, поступающий на входы формирователей 6 с выхода 21, обеспечивает совмещение во времени работы формирователей 6 и матрицы 7, т.е. в то время, когда матрица 7 отрабатьвает сигнал одного такта, формирователи 6 отрабатьвают сигнал последующего такта. Если на выходе К-ого (К1, Р) формирователя 6 формируется сигнал разрешения сдвига (логическая единица), поступающий на входы синхрониза 45 ции всех ячеек 10 К-ой строки матрицы 7, то в этой строке произойдет сдвиг содержимого ячеек 10 на один разряд вправо, а в освободившуюся, например, крайнюю левую ячейку 10 этой строки запишется "1", в противном случае содержимое строки ячеек 10 матрицы 7 не изменится. По окончаМнии серии из (-2- +1) -го сигналов, 55 формируемых на выходах 18 и 19,на выходе 20 формируется сигнал ("0"), который, поступая на первые входы 11формирователей 6, формирует на их выходах сигнал разрешения сдвига ("1"), если в триггере 35 (фиг. 4) этого формирователя 6 хранилась "1", и сигнал запрещения сдвига - в противоположном случае.МНа ( +2)-ом такте с выхода 212поступает сигнал ( О ), запрещающий формирование на выходах формирователей 6 сигналов разрешения сдвига, а с выхода 23 поступает сигнал, разрешающий выделение строки матрицы 7, содержащей максимальное количество единиц, т.е. вьщеления слова, в наибольшей степени совпадающего с признаком опроса. Выделение происходит вМ( + 3)-ом такте и сводится к уста 2новке (сигналами, поступающими с выходов соответствующих элементов ИЛИ 11) в "0" всех ячеек 10, кроме ячеек 10 столбца матрицы 7, в котором содержится самая правая "1", причем строка, в которой содержится указанная "1", соответствует слову, ближайшему к признаку опроса по критерию Хемминга. После установки в "0" укаванных выше ячеек 10, сигнал нулевого уровня на одной из шин 13 укажет на слово-аргумент, имеющее минимальное кодовое расстояние к признаку опроса,. т.е. слово, ближайшее по Хеммингу к признаку опроса.Необходимо отметить, что в общем случае массив-аргумент может содержать несколько слов, имеющих одинаковые минимальные кодовые расстояния по отношению к признаку опроса, причем,эти слова могут быть одинаковыми (тогда несовпадение имеет место в одних и тех же разрядах) либо различными (несовпадение в разных разрядах). Всем этим словам соответствует одинаковое количество "1" в соответствующих строках матрицы 7, где они параллельно выделяются. В случае необходимости в предлагаемое устройство известными средствами может быть введено маскирование произвольных разрядов накопителя 2, при этом обеспечивается возможность выполнения всех описанных вьппе операций только над незамаскированными разрядными срезами. Увеличение быстродействия достигается за счет разделения слов-аргументов и признака опроса на две рав 3 12772 ные части и их параллельной обработки при выполнении операции поиска слов ближайших по Хеммингу к признаку опроса, а также за счет сокращения времени, необходимого для сдвига информации в строке матрицы 7 и за счет того, что выделение искомого числа в матрице 7 занимает один такт.формула изобретения 101. Ассоциативное запоминающее устройство, содержащее регистр опроса, накопитель, первую группу элементов НЕРАВНОЗНАЧНОСТЬ, регистр результата поиска и блок управления, одни из выходов которого подключеиы к управляющим входам регистра опроса, регистра результата поиска и накопителя, одни из выходов которого соединены 2 О с первыми входами элементов НЕРАВНОЗНАЧНОСТЬ первой группы, вторые входы которых подключены к первому выходу регистра опроса, о т л и ч а ющ е е с я тем, что, с целью повыше ния быстродействия устройства при поиске слов, ближайших по Хеммингу к признаку опроса, в него введены элементы ИЛИ, элементы ИЛИ-НЕ, вторая группа элементов НЕРАВНОЗНАЧНОСТЬ 30 формирователи сигналов сдвиг,; и сдвигающая матрица, входные шины столбцов которой соединены с выходами элементов ИЛИ, первые входы которых подключены к выходам элементов ИЛИ-НЕ, первый вход каждого из которых подключен к выходной шине соответствующего столбца сдвигающей матрицы, а второй вход каждого элемента ИЛИ-НЕ, кроме последнего, - к выходным шинам последующих столбцов сдвигающейматрицы, входные шины строк которой соединены с выходами формирователей сигналов сдвига, первые и вторые входы которых подключены соответственно к выходам элементов НЕРАВНОЗНАЧНОСТЬ первой и второй групп, причем первые входы элементов НЕРАВНОЗНАЧНОСТЬ второй группы соединены с вторыми выходами накопителя, а вторые входы - с. вторым выходом регистра опроса, выходные шины строк сдвигающей матрицы подключены к входам регистра результата опроса, управля" ющий вход которого соединен с вторыми входами элементов ИЛИ .и третьими входами формирователей сигналов сдвига, четвертые и пятые входы которых и третьи входы элементов ИЛИНЕ подключены соответственно к другим выходам блока управления, второй вход последнего элемента ИЛИ-НЕ подключен к шине питания.2. Устройство по п. 1, о т л ич а ю щ е е с я тем, что сдвигающвя матрица содержит триггеры, элементы НЕ и нагрузочные элементы, первые выводы которых подключены к шине питания, причем входы синхронизации триггеров строки и информационные входы триггеров первого столбца матрицы соединены с входной шиной строки матрицы, установочные входы триггеров столбца подключены к входной шине столбца матрицы, первый выход каждого триггера в строке соединен с информационным входом последующего в строке триггера и входом элемента НЕ, выход которого подключен к выходной шине строки, вгорые выходы триггеров в столбце соединены с выходной шиной столбца, вторые выводы одних из нагрузочных элементов подключены к выходным шинам строк, а вторые выводы других нагрузочных элементов - к выходным шинам столбцов.1277211 29 г.Ф Составитель Т. ЗайцеТехред Л.Кравчук Тираж 5 ч 3Государственного коми елам изобретений и от осква, Ж, Раушская Подписноетета СССРрытий ВНИИПИ по 113035, наб., д. роизводст