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

о тк:,с а.н к е ИЗОБРЕТЕН ИЯ Союз СоветскихСоциалистическихРеспублик(11) 525161 АВТОРСКОМУ СВИДЕТЕЛЬСТЬУ Дополнительное к авт. свид-ву 1,03,74 (21) 2004001/2 Зая 1) М. Кл,е З 11 С 15 ением заявки-с при осударственныи комитетСовета Министров СССРоо делам иэооретенийи открытий Прнорит 53) УДК 681.327ллетень 3 публикования описания 07.04,7 2) Авторы изобретения С. И. Хмельник и В. П люции всесоюзный гос и научно-исследовате арственный кий инстит 1) Заявитель м и электрических сетсетьпроект(54) АССОБИАТ ЗАПОМИНАЮШЕЕ УСТРОЙСТ фиг. 3 изображен чческого хода; на фвания и поиска накодов,зоб к области запослучай геометан пример кодир ние отн тройств тн Изв. 4 дере оминвющееминвющий блок, ку и реги тно ассоциативное запо, содержащее запонный к адресному бл геометрических Устройство содержит (минвющий блок 1, пять рересный блок 7, арифметичблок декодирования 9. Вхключены соответственно х1, 7, 9 и первых четыреха выходы - ко входам бло2 и второго 3 регистров,блока 9 соединен с ввыход - со входом п оходы регистров 2 и 3 подклюветствующим входам блока подключстры. естно боты ыход ятог е запоминающегоое запоминающеее схемой, позвоаавыделить один разрможно обратитьсябайта и адрес битаустройства мы будйшем. В качеств зуется обычн дополненно ного байта устройству та (адрес свойством ся в дальн ка испольройство вщей из выбраняд. К такому с адресом бив байте), этимем пользовать(43) Опубликовано 15.08 Ордена Октябрьской Рев проектно-изыскательски энергетических систУ изв го устройства невысокая скорость ра и дорогостоящая аппаратура.С целью повьппения быстродействия и эффективной емкости предложенное устрой ство содержит блок декодирования и арифметический беток, входы которого подключены соответственно к выходам запоминающего блока, адресного блока, блока декодирования и первых четырех регистров, а вы ходы - ко входам адресного блока, блока декодирования первого и второго регистров, один из входов блока декодирования соединен с выходом первого регистра, а выход - со входом пятого регистра, выходы первого 20 и второго регистров подключены к соответствующим входам адресного блока.Нв фиг. 1 показана блок-схема предложенного устройства; на фиг. 2 представлено дерево" геометрических кодов, на 25 см. фиг, 1) запогистров 2-6, вдеский блок 8 и ды блока 8 подвыходам блоков регистров 2-5 ков 7, 8 первого один из входов ом регистра 2, а регистра 6, вычены к соотУстройство в целом решает две задачи: 1) кодирование массива двоичных кодов в линейный геометрический код (ГКЛ), хранящийся в блоке 1 в виде последовательности двоичных разрядов, каждый из которых определяется своим номером в этой последовательности, т.е. адресом в блоке 1;2) ассоциативный поиск кодов, удовлетворяющих некоторому условию поиска, которое определяется двумя двоичными кодами,ключевым и базисным, при этом предполагается что массив кодов, в котором производится поиск, уже закодирован в виде ГКЛ и хранится в блоке 1.Арифметический блок 8 реализует некоторую рекурентную формулу, связывающую ключевой и базисный коды с предыдущим и последующим значениями чисели к.Кроме того, он считает количество циклов поиска и тем самым определяет момент ф окончания поиска,Адресный блок 7 вычисляет адрес разряда ГКЛ в блоке 1 по известным значениям чисел К и, а затем обращается по этому адресу в блок 1.25Блок декодирования результата 9 по известному значению числа определяет искомый код.Рассмотрим функционирование устройства в целом,Адресный блок 7 на основе анализа содержимого регистров 2 (число) и 3 (число 1 ) определяет адрес одного бита Зб и посылает этот адрес в запоминающий блок 1 по адресному выходу. Дальнейшие действия различаются в зависимости от решаемой задачи (поиск или кодирование),40При поиске значение бита по вычисленному в блоке 7 адресу выдается в блок 8, который по этому значению и содержимому регистров 2,4,5, (в последних двух регистрах хранятся коды, определяющие условия поиска) 45 определяет новые значения регистров 2 и 3.Кроме того, блок 8 проверяет, завершен ли поиск очередного кода, и передает управление блоку 7, если поиск не завершен, или блоку 9, если поиск завершен. Последний по Зф содержимому регистра 2 определяет искомый код и записывает его в регистр 6.Затем управление вновь передается блоку 7 для поиска следующих кодов, удовлетворяющих условиям поиска, определяемым кодами, находящимися в регистрах 4 и 5.При кодировании адресный блок 7 по вычисленному адресу бита записывает 1" в блок 1 (для этого блок 7 связан с запоминающим блоком 1 адресной и информа 4ционной шинами) . Затем арифметическийблок 8 по значениям регистров 2, 4 вычисляет новые значения регистров 2 и 3 и передает управление блоку 7. Цикл повторяется до завершения кодирования.Рассмотрим теперь процессы кодирования и поиска подробнее.1. Кодирование,Предварительно рассмотрим дерево,изображенное на фиг. 2, и присвоим враждойего вершине двузначный номер ( С К ), гдеК - номер яруса, а- номер вершинь-.в 1 -м ярусе. При этом будем считать,что нумерация ярусов идет справа налево,а нумерации вершин - сверху вниз. Пусть0 и Ю - номера крайнего правого и левого ярусов соответственно.Тогда=и;П -12,1 0; Ь = 1,2,К,2Число ярусов Г = П+1; число узлов дерева ц, = 2 - 1.иЧисло вершин в ярусе Р Й = 2Обозначим через1 вершину с чеьным номером 6 и через Я- вершину7с нечетным номером 1,ю иПуть в дереве, соединяющий вершиныф и )о , назовем Р-путем. Очевидно,каждый Р-путь можно изобразить последовательностью символов оС и 3 . Например, на фиг. 2 выделен путь, которому соответствует последовательность 5 аРл" 34,7( О(4 Л 2,2 ф 1 70 Каждый символк (или ):7 ) последовательности, изображающей некоторый Р-путь на "дереве , назовем К -разрядом Р-пути. Если каждому разряду Р-пути поставить в соответствие "1 (для) и "0" (для р ), то Р-путь может быть изображен двоичным кодом Кр . В частности, для рассмотренного случая Кр =0001100. Номер пути-Р, очевидно, равен номеру того разряда в д -м ярусе, на котором заканчивается этот путь.Условимся теперь, что С идвоичные величины ( сС =0,1 и 7= 0,1). Назс вем Р-пучь открытым, если величина всех его разрядов равна 1, и закрытым, если величина хотя бы одного его разряда равна О.На фиг. 3 для иллюстрации изображено "дерево" двоичных разрядов, в котором открыты пути: В 4 , 40 , Ь; аС.3,4444Вершина7 находится за разрядной сеткой и не участвует в вычислениях, приведенных ниже.Каждому из этих путей соответствует двоичный код; К= 0110, "40= 1001, 525161тественно, невозможно выбрать из ГКЛ одновременно.В связи с этим предлагается следующая схема поиска; 1) перенос распространяется справа налево по наивысшим разрядам" каждогояруса, т.е. из возможных путей распространения переноса выбирается тот, который проходит через разряд с наименьшимномером в ярусе;2) при прекращении распространения переноса на каком-либо промежуточном илипоследнем ярусе, перенос "отражается" ираспространяется в противоположную сторону до ближайшего разряда, в который"отраженный" сигнал приходит из разрядас четным номером , т.е. из ; еслиключевой код этого разряда равен 1", топеренос продолжает распространяться вмладшие ярусы (в нулевом ярусе процесспоиска прекращается);3) выбирается разряд с номером+1,т.е, разряд (, данной пары;4) перенос из выбранного разряда распространяется справа налево, как в п.1и т.д,Время выполнения ассоциативного поиска по этому алгоритму пропорциональноразрядности искомых кодов и количествукодов, удовлетворяющих условию поиска,но нв зависит от общего объема массивакодов,ф орм ула из о бр ет енияАссоциативное запоминающее устройф ство, содержащее запоминающий блок, подключенный к адресному блоку, и регистры, отличающееся тем,что,сцелью повышения быстродействия и эффективной емкости устройства, оно содержит блок ф декодирования и арифметический блок,входы которого подключены соответственно к выходам запоминающего блока, адресного блока, блока декодирования и первых четырех регистров, а выходы - ко входам адресного блока, блока декодирования, первого и второго регистров, один из входов блока декодирования соединен с выходом первого регистра, а выход - со входом пятого регистра, выходы первого и второго Я 5регистров подключены к соответствующим входам адресного блока.Составитель В. Рудаков Редактор Москаленко Техред М. Ликович Корректор Н. ЗолотовскаяЗаказ 5088/581 Тираж 723 Подписное ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д, 4/5 филиал ППП " Патент", г. Ужгород, ул. Проектная, 4