Логическая ячейка для ассоциативного запоминающего устройства

 

Союз Советских

Социалистических

Республик рв980162 (6 l ) Дополнительное к эвт. Саид-ву (22) Заявлено 150б.81 (2l) 3299787/18-24 gq З с присоединением заявки Nо

{23) Приоритет .

6 11 С 15/00

Государственный комитет

СССР но делам изобретений и открытий (Щ УДК 681, 327 (088.8) Опубликовано 071282; Бюллетень Йо 45

Дата опубликования описания 071282 (72) Авторы изобретения

В.М. Трусфус и Р. P Бикмухаметов

Казанский ардена Трудового Красного Знамени авиационный институт им. A.Н. Туполева (71) Заявитель (54) ЛОГИЧЕСКАЯ ЯЧЕЙКА ДХИ АССОЦИАТИВНОГО

ЗАПОМИНАЮЩЕГО УСТРОЙСТВА

Изобретение относится к запоминающим устройствам и может быть использовано при ассоциативной обработке информации в ряде задач физики и радиолокации, например,при цифровой обработке радиолокацйонной информации„ в качестве ячейки для обработки разрядных слоев ассоциативного запоьп нающего устройства (АЗУ).

Известна логическая ячейка,содержащая элементы И, ИЛИ триггерй Щ .

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

Наиболее близкой по технической сущности к предлагаемой является логическая ячейка для АЗУ, содержащая группу элементов И, блок местного управления, регистр результата поиска, содержащий пять триггеров, и блок вывода результата поиска f2) .

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

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

Поставленная цель достигается тем,.

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

НЕ, элементы И и элементы ИЛИ, причем первые входы первого, второго и третьего элементов И, первого элемента ИЛИ.и первого элемента И-НЕ объединены и являются первым входом ячей-. ки, первые входы четвертого, пятого и шестого элементов И, второго элемента ИЛИ и второго элемента И-НЕ объединены и являются вторым входом ячейки, первые входы седьмого и восьмого элементов И и третьего элемента

И-НЕ объединены и .являются третьим входом ячейки, первая числовая шина соединена с выходами первого и второго -элементов И-НЕ, с вторыми входами третьего и шестого элементов И и входом первого элемента НЕ, выход которого подключен к вторым входам первого и второго элементов ИЛИ и первым входам девятого, десятого и одиннадцатого элементов И, вторая числовая шина соединена с выходом третьего элемента И-НЕ, с третьими еаО1е2 входами третьего и шестого элементов

И и входом второго элемента НЕ, выход которого подключен к второму входу седьмого и первому входу двенадцатоГо элементов И, первый выход первого триггера подключен к второму

Ъходу первого элемента И-НЕ, первому входу третьего элемента ИЛИ и второму входу пятого элемента И, выход которого соединен с первыми входами четвертого и. пятого элементов MJIH и вто- 10 рым входом десятого элемента И, второй выход первого триггера подключен к второму входу второго и четвертому входу шестого элементов .И, первый выход второго триггера подключен к 35 второму входу второго элемента И-HH к вторым входам первого элемента И и третьего элемента ИЛИ, второй выход второго триггера соединен с четвертым входом третьего и вторым вхо- р() дом четвертого элементов И, первый выход третьего триггера подключен к первым входам тринадцатого и четырнадцатого элементов И, а второй выход является выходом ячейки и сое- р динен с третьими входами первого и второго и вторым входом третьего элементов H-HE, выход первого элемента И соединен с вторыми входами четвертого и пятого элементов ИЛИ и девятого элемента И„ вйход второго элемента И подключен к третьему входу четвертого и первому входу шестого элементов ИЛИ, выход четвертого элемента И соединен с четвертым входом четвертого и первым входом восьмого элементов ИЛИ, выход седьмого элемента И соединен с третьими .входами первого и второго элементов ИЛИ; выходы третьего, шестого, восьмого, девятого, десятого, одиннадцатого, двенадцатого, тринадцатого и четырнадцатого элементов И соединены соот-. ветственно с первым и вторым входами девятого, третьим входом пятого, с вторыми входами восьмого и шестого, 45 первым и вторым входами седьмого, и. третьими входами восьмого и шестого элементов ИЛИ, выходы элементов

ИЛИ с первого по пятый соединены соответственно с вторыми входами три- Я} надцатого, четырнадцатого, восьмого двенадцатого и одиннадцатого элементов И, первые входы первого, второго и третьего триггеров соединены соответственно с выходами восьмого,шес- g5 того и седьмого элементов ИЛИ, а вторые входы объединены и являются четвертым входом ячейки, третьи входы первого и второго триггеров объедине ны и являются пятым входом ячейки, который соединен с третьим входом девя- того элемента ИЛИ,выход которого подклю. чен к третьему входу третьего триггера.

На фиг; 1 изображена функциональная схема логической ячейки для АЗУ; на фиг ° 2. — графа состояний этой ячейки.

В логической ячейке для ассоциативного запоминающего устройства,со.держащего регистр входного признака у, и запоминающих регистров для записи чисел х (! } -;и) и и логических ячеек, осуществляется сравнение х с у с целью определения числа с мйнимальным значением модуля разности этих чисел; Сравнение производится поразрядно-последовательно, начи .ная со старших разрядов. Результатй сравнения каждого разряда (текущее соотношение чисел с точностью до рас сматриваемого разряда) фиксируются в логической ячейке. При сравнении учи° тываются соотношение цифр в текущем разряде и результат сравнения в старших разрядах.

Примем, что х; и у — правоустановленные целые положительные числа: х х, р ° ° ° gxj< р ° ° ° ух|и1у j Г(у ° ° у,...,у,„, где х „, у — двоичные разряды; } — номер разряда, (j .3-е).

Совокупности старших разрядов х" и у до j --го разряда включительно обозначим через }х„), (у1, рассматривая их как целые положительные числа.

В процессе поразрядного сравнения в логических ячейках определяются по характеру первого (старшего) неравенства цифр х; и у, числа, большие меньшие или равные у с точностью до рассматриваемого разряда. на каждом шаге сравнения для всех х„ определяются значения модуля разности х „ — у с точностью до рассматриваемого разряда })1 =!(х„.) "("I / "С, которые кор ректируются путем сдвига начала шкалы отсчета таким образом, чтобы наименьшее из них равнялось нулю. Здесь

С вЂ” величина сдвига качала шкалы отсчета за счет коррекции у в старших разрядах. После выполнения m шагов сравнения искомые числа определяются по нулевому значению скорректированной разности.

Если (хД >(у)„,. в ячейке обработки разрядных слоев определяется значение О}; = } х„} -PyJ> -C, если хД (у1 ., то 0;i = (у). - х.Д -С.

Учйтывая,. что (Z) = 2 (Zj > + получаем для х„" > у э„" =2 .хД1 „ -(Ы -1 3 } С=

2((х g> „-() .,-q(2)«<,-q,,=23; „Я где ц м „-у, d„ „- скорректированное значение D„ > 1 .

Аналогично для х < у получаем

О, "- 24.} -С(.

Окончательно получаем

23„" „ О,если(хд „ Я „;

4 есл (xil j-1 Ы .

О+ } И/, если (х „), =(qj !

980162 где (О, если

1, если (, гели

Х1%%У У1{31 Р1„ =1)

1{Ч1 1{ >

К „ = (! ; =1 5

Как следует из (1), для наименьшего значения скорректированной вели. чины в предыдущем разряде, т.е. для д { 1 = О, 0 1 меняется в пределах — 1, О, 1. По этим значениям корректируются все значения DÄ 1, т.е. d;

0„„ -D

Если А = О н В = О, то это означает, что для всех 0{{1 1 О, 0{1 Ф f, Из сказанного следует, что

a = y(o„; =-<) =y((a„;„=o)(((;q; „

{ {

4!.ф1 1)ЩЧ((ХД „() J „)бД е =÷(î„",=î = (é;; „=o}v;„.

В логической ячейке достаточно фиксировать лишь три значения d„ ,*a именно: d{i - О, di1 - 1 и d{i > 2, так как, в соответствии с (1), если де > 2, то и при рассмотрении всех более младших разрядов.х, начиная с ()+1)-го разряда, будет де > 2, ()+1) "m.

Таким образом, после выполнения в шагов сравнения, число, ближайшее или равное входному признаку, определяется по условию d;{„ = О.

Ячейка содержит триггеры 1-3,образующие регистр 4 результата поиска, элементы И-НЕ 5-7, числовые шины 8 и 9, первый элемент НЕ 10, имеющий 4О выход 11, второй элемент HE 12, элементы И 13-26, элементы ИЛИ 27-35, первый 36, второй 37 и третий 38 входы ячейки, выход 39 ячейки, первые выходы 40-42 триггеров, 1-3 соответ- 45 ственно, вторые выходы 43 и 44 триггеров 1 и 2 соответственно,. первые входы 45-47, вторые входы 48-50 и третьи входы 51-53 триггеров 1-3 соответственно, четвертый 54 и пятый 50

55 входы ячейки.

Ячейка работает следующим образом.

Производится установка в нулевое состояние триггеров 1-3 (фиг. 1) подачей сигнала на вход 55 ячейки. В процессе поиска на каждом шаге сравнения на входы 36-38 ячейки поступают соответственно сигналы01 „,8;;и Р „ .

При этом ячейка может находйться в одном из 6 возможных состояний а фа{-, 60 где ао — начальное состояние, указанных на графе состояний ячейки (фиг 2)

Здесь С„-.C{< ссинггннааллы ы ппееррееххооддаа, на" чальное состояние а© соответствует значениям d„ „ = 0 и (х;j 1 = 65 (у11 .{, 01 соответствует значениям д{ 1 { О и (х > у(1 „ а -{ д„у< = 1 и (хД ° (у!

ag d1>q = 0 н Гх;1, „. (У1;», а4 д{ 1 { = 1 и х 1 q а(у) { а5-,Ц{1„{ 2.

Выход из состояния аа осуществляется при появлении сигнала первого поразрядного неравенства !ц „или 31;, В обоих случаях 0;> = 1. Отметим, что пока среди чисел x имеется хотя бы один, равный у с точностью до 1-rо разрядаг для Всех (ха 1Ф (у11 „д,)>.1 э

Поэтому при появлении сигнала первого поразрядного неравенства не может быть 0; { — 1 (А О), и ячейка переходит в состояние а или а>, если при этом В = 0, или а или а, если

В = 1. Отсюда С --81; В, С> =p) В;

С =-В,, В; С =(О;,.В".

В состоянии а

-1 ecJEH Я 1 = 1

D = О, еслиР1; =1, 1, если 31„. = 1.

При этом если А = О и В ; — О, то

0 { — 4 = О. Если A = О и В = 1, то dq -" 011 0111.,Если 1, то независимо от значения В d „

О.; (0919 2.

В результате С АВ о { АР1„, Сь = AS;„, В состоянии а2

1, если (И1, = 1, 0 ° 2, если Р, =1 5

3, если 1; = 1, При этом, если A -= -О и В = О, то d<> = 0„; - 1 = ÎY1Y2. Ecsm A 0 и В =. 1, то d{1 = 0{1 = 1М2У3. Если

A = 1, то независимо от значения В

de)> 2

Таким образом, Со =- AB (U1„, С{{{{ =

А Ва УАВ(Р1 чье„ ) А =Ь1 У AV В х х Р-;.

Аналогично можно показать, что

СЦ = ГВ8.{{, С12=, ({{1{УАУ ВР (Каждой из шести состояний ячейки кодируется определенным набором состояний триггеров 1-3, состояние а кодируется набором.(0, О, О), а{ набором (1, О, Î), а{ — набором (1, О, 1), а9 вЂ,набором (О, 1, О), а4 - набором (О; 1, 1), ас -. набором (1, 1, 1). Отсюда следует, в частности, что выполнение условия 4{1 1 О кодируется нулевым состоянием третьего триггера 3. После выполнения m шагов сравнения сигнал на этом выходе 39 ячейки означает, что d {» = О, т.е. рассМатриваемое число х.. является ближайшим по значению или равным.у.

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

980162

8 сравнению с прототипом. Вместо восьми межчи«словых шин используются две шины, количество триггеров и входов логических элементов сокращено в

1," раза. Поиск числа, ближайшего по значению или равного у, выполняет- S ся путем ОднОкратнОгО ОпрОса регист-: ра р зультата поиска в прототипе за два;такта опроса.

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

Логическая ячейка для ассоциативного запоминающего устройства, содержащая триггеры, элементы И-HE u

".«ис«1овь«е шины О T л и H и K щ а я с я тем, что, с целью упрощения и повышения быстродействия ячейки, -в нее ввецены элементы НЕ, элементы И и элементы ИЛИ, причем первые входы первого,. второго и третьего элементов И, первого элемента ИЛИ и перво" го элемента И-.НЕ объединены и являются и рным входом ячейки, первые входы четвертогО у пятого и шестох О 25 элементов И, второго элемента ИЛИ и второго элемента И-HE объединены и являются вторым входом ячейки, перВЫЕ ВХОДЫ СЕДЬМОГО И ВОСЬМОГО ЭЛЕментов И и третьего элемента И-HE объединены и являются третьим входоМ .ячейки, первая числовая шина соединена с выходами первого и второго .элементов И-НЕ, с вторыми входами третьего и шестого элементов И и входом первого элемента HE выход которого 35 подключен к вторым входам первого и второгО элементов ИЛИ и первым входам девятого, десятого и одиннадцатого. элементов И, вторая числовая шина соединена с выходом третьего элемента И-Н5, с третьими входами третьего и шестого элементов И и входом второI"o элемен",.à HE выход которого подКЛЮЧЕН К В ОРОМУ ВХОДУ СЕДЬМОГО И ПЕРвому входу двенадцатого элементов N, 45 первый вьход первого триггера подключен к второму входу первого элемента

И-НГ, первому входу третьего элемента ИЛИ и второму входу пятого элемента И, выход которого соединен с пер- 5О ными входами четвертого и пятого элементов ИЛИ и вторым входом десято"о элемента И, второй выход первого ,триггера подключен к второму входу второго и четвертному входу шестого элементов И, первый вь«ход второго триггера подключен к второму входу второго элемента И-НЕ, к вторым вхо- дам первого элемента И и третьего элемента ИЛИ, второй выход второго триггера соединен с четьертым входом третьего и вторым входом четвертого элементов И, первый выход третьего триггера подключен к первым входам тринадцатого и четырнадцатого элементов И, а второй выход является выходом ячейки и соединены с третьими входами первого и второго и вторым входом третьего элементов И-НЕ, выход первого элемента И соединен с вторыми входами четвертого и пятого элементов ИЛИ и девятого элемента И, выход второго элемента И подключен к третьему входу четвертого и первому входу шестого элементов ИЛИ, выход четвертого элемента И соединен с четвертым входом четвертого и первыМ входом восьмого элементов ИЛИ, выход седьмого элемента И соединен с третьими входами первого и второго элементов ИЛИ, выходы третьего, шестого, восьмого, девятого, десятого, одиннадцатого, двенадцатого, тринадцатого и четырнадцатого элементов И соединены соответственно с первым и вторым входами девятого, третьим входом пятого, с вторыми входами восьмого и шестого, первым и вторым входами седьмого, и третьими входами восьмого и шестого элементов ИЛИ, выходы элементов ИЛИ с первого по пятый соединены соответственно с вторыми входами тринадцатого, четырнад- цатого, восьмого, двенадцатого и одиннадцатого элементов И, первые входы первого, второго и третьего триггеров соединены соответственно с выходами восьмого,.шестого и седьмого элементов ЙЛИ, а вторые входы объединены и являются четвертым входом ячейки, третий вход первого и второго триггеров объединены и являются пятым входом ячейки, который

-соединен с третьим входом девятого элемента ИЛИ, выход которого подклю-: чен к третьему входу третьего тригге.ра.

Источники информации, принятые во внимание при экспертизе

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

Р 332502, кл. 6 11 С 15/00, 1970.

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

Р 780043, кл, G 11 С 15/00, 1980 (прототип).

980162

Составитель В.Рудаков

Редактор С.Лушникова Техред Т.Маточка Корректор A.Äýÿòêo

Заказ 9368/42 Тираж 622 Подписное

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

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

Филиал ППП "Патент", r. Ужгород, ул. Проектная,. 4