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

СОЮЗ СОВЕТСНИХСО 1.1 ИАЛИСТИЧЕСНРЕСПУБЛИН 19) (1 11 С 15 ИЗОБ САНИ НИ СНОМ НА У строде нии оп икза дназна 1 1 ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ 21) 3984435/24-2422) 29.11,851,46) 30.05,87. Бюл. 9 20(57) Изобретение относится к вычлительной технике, в частностпоминающим устройствам, и пре чено для электронных цифровых вычис лительных систем. Цель изобретения - повышение быстродействия устройства. Устройство содержит накопители 2 - 2 к, регистр 3 опроса, группы элементов НЕРАВНОЗНАЧНОСТЬ 41 в 4, блоки 5 - 5 М постоянной памяти, накапливающие сумматоры 6, - 6, счетчики 7 - 7 ц, сортирующую матрицу 8, регистр 9 результата поиска, Повышение быйствия устройства при выполнеерации поиска слов, имеющих минимальное кодовое расстояние по отношению к признаку опроса (поиск ближайшего по Хэмманчу), достигается за счет разделения слов массива аргумента на равные части и параллельной их обработки, 2 ил.Изобретение относится к вычислительной технике, в частности к запоминающим устройства (ЗУ),и предназначено для электронных цифровых вычислительных систем,Цель изобретения - повьшение быстродействия устройства.На фиг.1 приведена функциональнаясхема ассоциативного запоминающегоустройства; на Фиг.2 - структурнаясхема блока управления.Ассоциативное запоминающее устройство содержит блок 1 управления,основной 2 и дополнительные 2- 2накопители, где к - целое число, регистр 3 опроса, основную 4 идополнительные 4 - 4группы элементовНЕРАВНОЗНАЧЙОСТЬ, блоки 5 - 5 постоянной памяти, где м - число запоминающих ячеек в каждом накопителе 2,накапливающие сумматоры 6, - 6 , счетчики 7 - 7 ц, сортирующую матрицу 8,регистр 9 результата поиска, Матрица8 содержит м (Ь+Р)-разрядных ячеек 10,где Ь=1 од К; Р=11 од (Б/К); И -разрядность регистра 3 опроса; Ь и Р -соответственно младшие и старшие разряды ячеек матрицы 8.Блок 1 управления имеет выходы 1115 и содержит (Фиг,2) регистр 16 кода операции, генератор 17 тактовыхимпульсов, дешифратор 18, микропрограммную матрицу 19 и регистр 20 микрокоманд. Сортирующая матрица 8 можетбыть построена на триггерах и логических элементах. Каждый из счетчиков 7 служит для подсчета поступающих на его вход единичных импульсов.Устройство работает следующим образом.Слова массива-аргумента хранятсяв запоминающих ячейках накопителей2, а признак опроса - в регистре 3опроса, причем Б-разрядные словамассива-аргумента и признак опросаразбиваются на к равных частей,Запоминающие ячейки накопителей2 и регистр 3 опроса могут иметьразличную конструкцию (статическиеили динамические ЗУ, сдвиговые регистры, ЗУ на ЦМД, дорожки вращающихся магнитных ЗУ и т,д,), Однакоони должны обеспечивать последовательное поразрядное обращение, аименно, при поступлении очередногоуправляющего импульса на управляющиевходы накопителя 2 с выхода каждойзапоминающей ячейки считывается очередной Разряд содержимого даннойячейки. Аналогично при поступленииуправляющего импульса на управляющий вход регистра 3 опроса с выходовэтого регистра поразрядно считываются очередные разряды каждой из к частей признака опроса.При поступлении на входы блока 1управления команды поиска, ближайшего по Хэммингу, блок 1 вырабатываетследующую последовательность сигналов, На выходе 12 блока 1 формируется единичный сигнал, которым устанав-..ливаются в нуль все разряды регистра 15 9 результата поиска. После этого свыходов 11, 13, 14, 15 подается се-рия сигналов единичного уровня науправляющие входы соответственно регистра 3 опроса, накопителей 2, блоков 5 постоянной памяти, сумматоров 6.В результате происходит последовательная выборка из накопителей 2 и регистра 3 опроса всех разрядных срезов К частей слов массива-аргументаи признака опроса соответственно,Разрядные срезЫчастей всех слов поступают из накопителя 2 на первые входы соответствующих элементов НЕРАВНО-ЗНАЧНОСТЬ 4, на вторые входы которых 30поступают с выходов, регистра 3 опроса потенциалы соответствующих разрядов каждой из 1 частей признака опроса.Сигналы несовпадения значений разрядов д-тых частей (1=1,к) чисел с соответствующими разрядами признака опроса на выходах 1.-тых элементов НЕРАВНОЗНАЧНОСТЬ 4 соответствующих групп поступают . на -тые адресные входы соответствующих блоков 5 постоянной памяти, соответствующих каждому слову массива-аргумента, на выходах которых формируется код количества несовпадений значений 1 разрядов слов с соответствующими разрядами признака опроса.Коды количества несовпадений, поступающие на входы сумматоров 6, суммируются и накапливаются в сумматорах 6, перенос из которых подается на вход соответствующих счетчиков 7, тем самым увеличивая их содержимоена елиницу,Длительность тактового импульса определяется максимальной задержкой сигнала в блоке 5 постоянной памяти, сумматоре 6 и счетчике 7. Тогда сигналы, поступающие на управляющие вхо 3 13 ды блока 5 постоянной памяти, сумматора 6 и счетчика 7 соответственно с выходов 13 и 14 блока 1 управления, обеспечивают совмещение во времени работы блоков постоянной памяти, сумматора 6 и счетчика 7 единиц, т.е. в то время, когда сумматор 6 и счетчикобрабатывают сигнал Б-го (ББ=1, - -1) такта,на выходе блока 5 по стоянной памяти дублируется код количества несовпадений (8+1)-го такта. После того, как сумматор 6 и счетчик 7 обработают сигнал И/К-го такта, сортирующая матрица 8 определяет слово массива-аргумента, ближайшего по Хэммингу к признаку опроса, т.е. единица на выходе сортирующей матрицы 8 соответствует слову, имеющему минимальное количество совпадений с признаком опроса.Формула изобретенияАссоциативное запоминающее устройство, содержащее. регистр опроса, основные и дополнительные накопители, основную группу элементов НЕРАВНОЗНАЧНОСТЬ, счетчики, сортирующую матрицу, регистр результата поиска и блок управления, первый, второй и третий выходы которого подключены соответственно к управляющим входам накопителя, регистра результата поиска и регистра опроса, основной выход которого соединен с первыми входами элементов НЕРАВНОЗНАЧНОСТЬ основной 14386группы, вторые входы которых соединены с выходами основного накопителя,выходы разрядов счетчиков подключенык входам старших разрядов соответствующих ячеек сортирующей матрицы,выходы которой соединены с входами регистра результата поиска,о т л и ч а ющ е е ся тем,что, с целью повышениябыстродействия устройства, в него 10 введены накапливающие сумматоры, бло-.ки постоянной памяти и дополнительные группы элементов НЕРАВНОЗНАЧНОСТЬ, причем выходы блоков постоянной памяти соединены с информационными входами соответствующих накапливающих сумматоров, выходы переполнения накапливающих сумматоров подключены к счетным входам соответствующих счетчиков, разрядные выходы 20 накапливающих сумматоров соединены свходами младших разрядов соответствующих ячеек сортирующей матрицы,первые входы элементов НЕРАВНОЗНАЧНОСТЬ дополнительных групп подключены к соответствующим дополнительнымвыходам регистра опроса, вторые входы элементов НЕРАВНОЗНАЧНОСТЬ дополнительных групп, соединены с выходамисоответствующих дополнительных накопителей, выходы элементов НЕРАВНОЗНАЧНОСТЬ основной и дополнительныхгрупп подключены к адресный входамсоответствующих блоков постояннойпамяти четвертый и пятый выходы бло ка управления соединены с управляющими входами блоков постоянной памяти и накапливающих сумматоров,.Касарда ар Заказ 2215 2 Тираж 590 ПодписноВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д,4 5