Ассоциативное запоминающее устройство Советский патент 1980 года по МПК G11C15/00 

1

Изобретение относится к запоминающим устройствам.

Известно ассоциативное запоминающее устройство, содержащее запоминающие регистры,регистр опроса,детек-5 торы икомпараторы 1.

Недостаток этого устпойства - отсутствие возможности поиска по экстремальным условиям без применения алгоритмов, требую1г1их многократногоО обращения к устройству.

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

Недостатком этого устройства является повышенная сложность и понижение быстродействия вследствие последовательной организации межразрядной обратной связи.25

Цель изобретения - упрощение устройство и повышение его быстродействия.

Эта цель достигается тем, что устройство содержит блоки обратной свя- 30

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

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

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

N-Nv 2-Nr-- im

а также имеется регистр, содержащий т-разрядный признак опроса:

--,

Примем, что старшие разряды первые и номера разрядов.возрастают в порядке убывания их веса.

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

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

Обозначим z,j - сигнал на первом логическом выходе J -того /на перво логическом входе ) плока сранения слова; Z,-; - сигнал на втором логическом выходе j -того (на втором логическом входе -j+l-oro блока сравнения i-того слова, и буде называть совпадением выполнение в некотором блоке сравнения логической функции

-. - X . v X .. Sf

. -11 1 1 . 15 Ч(1)

При поиске по условиям ближайIlee болыиее и наименьшее будем наЗ.1вать положительным несовпадениеМ выполнение в некотором блоке сравнения Функции

(2)

П11иоритетои - )ункции

(3)

. - X - Y ) X -. V - X . ij 13 3 ij 1J

При поиске по условиям ближайшее меньшее и наибольшее соответст вующие фу н кции: . равен 1 словах, где но всех з предыдущих ра рядах зафиксировано совпадение, так как задггча состоит в распростра НИИ исходного сигнала 1 для любого i): --ir Q-O ij Значение сигнала Z,-j определяю два процесса: образование единичног сигнала и его распространение, Единица на втором логическом выходе К-того блок-а сравнения (КСЛ, . in ) i-Toro слова образуется в том слуЧае, если 1)2,.., 1, т.е. во всех поедыд 1ЦНХ разрядах зафиксировано совпадение ; 2)в данном разряде и.меет место ложительное несовпад;ение ; 3)среди остальных (п-1) слов не таких, в которых указанные в пп. и 2 ограничения (оба) выполнялись бы в последующих (младших) (т-к) оазрядах, Таким образом, единица на втором логическом выходе соответствующих

блоков сравнения образуется в тех словах, где первое (cTapiuee) в данном слове положительное несовпадение, при условии совпадения во всех предыду11их разрядах, наступило не ранее,- чем в любом другом слове:

2;.n.-o4J/|/.,H.) 5

Единица z,v 1 че образуется ни в одном слове,если все слова либо равны признаку опроса, либо меньше (при поиске ближайшего большего) или больше признака опроса (при поиске ближайшего меньшего),

Единица может образоваться в одноименных К-тых разрядах нескольких слов (это означает, что старшие К разрядов храниг.Их ассоциативных

признаков равны) . Однако последуюпие разряды признаков могут быть различными .

(-7к) равен i

Сигнал Z.jg

тех словах, где 1) г/(,, 1;

2) в данном разряде имеет-место приоритет.

Если пп. 1 и 2 (оба) не выполняются ни в одном слове, то 1 во всех словах, где выполняется условие п. 1 :

(б;

t

V(e.)«V;i.He-.H. Объединяя процессы образования и распространения единицы 7 -I получим: ), (f.. Z. M(()ii Появление сигнала Z,-, -} означает, что соответствующий ассоциативный признак равен признаку опроса, а сигнал Z/J,, --1, что он является ближайшим большим (меньшим), но не равным. Для аппаратной реализации экстремального поиска необходимо построить комбинационную логическую сеть,реализуюшую для каждс го разряда функции (4) и (7) . В данном устройстве, в отличие от известного, реализован сквозной перенос сигнала Т (8) с,. - ( 2 i J ,;/р-5 Р НР На фиг,1 изображена структурная схема ассоциативного запоминающего ус-1рг ис.-тв,) ( записи, считывания), на Лиг,2 - Лункциональная схема блоков сравнения. Устройство (фиг.1) содержит п х элементов 1 памяти, выходы 2 которы присоединены к признаковым входам соответствующих, блоков 3 сравнения, межразрядные шины 4, соединяющие логические выходы и входы предыдущих и, соответственно/ последующих блоков сравнения (т-1) первых 5, m вторых 6; m третих 1, m четвертых 8 разрядных шин и (т - 1) блоков обратной связи, например, элементов И 9, одни входы которых подключены к одноименным первым разрядным шинам 5,а выходы присоединены к пре дыдущим вторым разрядным шинам б и другим входам предыдущих блоков 9 обратной связи. Межразрядные 4 и четвертые разря ные шины 8-двухфазные.Каждый блок 3 сравнения (фиг.2) представляет собо комбинационную логическую схему,сод жащую элементы И 10-14,элементы ИЛИ и 16 и элементы НЕ 17 и 18 и имеет первый 19 и второй 20 входы опроса, первый 21 и второй 22 логические входы, первый 23 и второй 24 логические выходы, выходы разрядной 25 межразрядной 26 обратной связи, входы разрядной 27 и межразрядной 2 обратной связи и первый 29 и второй 30 входы опроса. Устройство работает следующим образом. Запись и считывание в устройстве могут быть организованы любым из известных способов. При поиске ближайшего большего (наименьшего) в исходном состоянии на первый 19 и второй 20 признако-вые входы } -того блока 3 сравнения i-Toro слова поданы и инверсное значения X,-j и соответствующего ассоциативного признака, а на первый 29 и второй 30 входы опроса поданы прямое и инверс ное значения У,- и 5j j-того разряда признака опроса. Предположим, что на первый 21 и второй 22 ло,гические входы поданы сигналы () и Zj(;j.i) , определенные согласно формула (4) и (6),на вход разрядной обратно связи 27 Подан сигнал -: (9) -(j-i) ij а на вхо.д межразрядной обратной свя зи - сигнал S. , определенный согласно (В) . - Тогда на первом 23 и втором 24 логических выходах реализуются функ ции, соответственно: « 1(1-1)13 И I- а. i4i-l-)i3 3 34 i(j-i-)) Учитывая (1)- (4) , (7)- (9) получим - I /) На выходе разрядной обратной связи 25 реализована функция 7 . . X Hj-iHij, третья разрядная шина 7 выполняет функцию монтажного И, поэтому сигнал на ней .е.предположение о сигнале на входе разрядной обратной связи 27 справедливо. На выходе межразрядной обратной связи 26 реализована функция iO-1Иii j З первая разрядная шина 5 выполняет функцию монтажного И, поэтому сигнал на ней -5j- ;i,4jM NМожно показать, что сигнал на выходе соответствуюгчего блока обратной связи 9 ы.и является сигналом на входах межразрядной обратной связи 28 (-1)-ых блоков S равнения, что также подтверждает сделанное выше предположение . Для полного соответствия математической модели (4) и (7) и аппаратной реализации экстремального поиска необходимо определить начальные условия. Так как признаки имеют m известных разрядов, следует считать, что незаданные разряды, старшие первого и младшие т-того, равны у всех признаков, откуда следует, что z;, 1, Z 0 для любого i. т.е. при поиске на второй вход последнего блока 9 обратной связи (на последнюю третью разрядную шину 7) и на первые логические входы 21 первых блоков 3 сравнения должны быть поданы логические ,а на вторые логические входы 22 первых блоков 3 сравнения - логические О . Описанное устройство, кроме общего с известным устройством оборудования, содержит (т-1) элементов И, которые в аппаратном отношении заменяют п (т-1) элементов ИЛИ и п (т-1) элементов НЕ, т.е.оно проще известного, Т&кже оно является и более быстродействующим.

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

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

разпядным шинам, а выходы - к предыдущ гм вторым разрядным шинам и к другим, входам предыдущих блоков обратной связи.

2, Устройство по п,1, о т л и чающееся тем, что блоки обратной связи- выполнены в виде злементов И, входы и выходы которых подключены к соответствующим входам и выходам блоков обратной связи. Источники информации,

принятые во внимание при экспертизе

1.Авторское свидетельство СССР № 277837, кл.С 11 С 15/00, 1970.

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

(4 564656, кл.С 11 С 15/00, 1975 (прототип) .