Логическая ячейка для ассоциативного запоминающего устройства Советский патент 1982 года по МПК G11C15/00 

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

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

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

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

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

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

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

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

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

25 которого подключен к вторым входам первого и второго элементов ИЛИ и первым:вход9м девятого, десятого и одиннадцатого элементов И, вторая числовая шина соединена с выходом

30 третьего элемента И-НЕ, с третьими входами третьего и шестого элементов И и входом второго элемента НЕ, выход которого подключен к второму входу седьмого и первому входу двенадцатого элементов И, первый выход первого триггера подключен к второму Ъходу первого элемента И-НЕ, первому Ьходу третьего элемента ИЛИ и втором входу пятого элемента И, выход которого соединен с первыми входами четвертого и. петого элементов ИЛИ и вто рым входом дЪсятого элемента И, второй выход первого триггера подключен к второму входу второго и четвертому входу шестого элементов И, первый выход второго триггера подключен к второму входу второго элемента И-НЕ, к вторым входам первого элемента И и третьего элемента ИЛИ,- второй выход второго триггера соединен с четвертым входом третьего и вторым входом четвертого элементов И, первый выход третьего триггера подключен к первым входам тринадцатого и четырнадцатого элементов И, а второй выход является выходом ячейки и соединен с третьими входами .первого и второго и вторым входом третьего элементов И-НЕ, выход первого элемен та И соединен с вторыми входами четвертого и пятого элементов ИЛИ и девятого элемента И, выход второго эле мента И подключён к третьему входу четвертого и первому входу шестого элементов ИЛИ, выход четвертого элемента И соединен с четвертым входом четвертого и первым входом восьмого элементов ИЛИ, выход седьмого элемен т& И соединен с третьими .входами первого и второго элементов ИЛИ/ выходы третьего, шестого, восьмого, девятого, десятого, одиннадцатого, двенадцатого, тринадцатого и четырнадцатого элементов И соединены соот ветственно с первым и BTOptJM входами девятого, третьим входом пятого, с вторыми входами восьмого и шестого, первым и вторым входами седьмого, и третьими входами восьмого и шестого элементов ИЛИ, выходы элементов ИЛИ с первого по пятый соединены соответственно с вторыми входами тринадцатого, четырнадцатого, восьмого двенадцатого и одиннадцатого элементов И, первые входы первого, второго и третьего триггеров соединены со ответственно с выходами восьмого,шес того и седьмого элементов ИЛИ, а вто рые входы объединены и являются четвертым входом ячейки, третьи входы первого и второго триггеров объедине ны и являются пятым входом ячейки, который соединен с третьим входом девя того элемента ИЛИ эыход которого подкл чен к третьему входу третьего триггера На фиг; 1 изображена функциональная схема логической ячейки для АЗУ/ на фиг. 2.- графа; состояний этой ячейки. , В логической ячейке для ассоциативного запоминающего устройства,содержащего регистр входного признака у, п запоминающих .регистров для записи чисел х {I Ип) и п логических ячеек, осуществляется сравнение Х|- с у с целью определения числа с минимальным значением модуля разности этих чисел; Сравнение производится поразрядно-последовательно, начи,ная со старших разрядов. Результата сравнения каждого разряда (текущее ,. соотношение чисел с точностью до рассматриваемого разряда) фиксируются в логической ячейке. При сравнении учитываются соотношение цифр В текущем разряде и результат сравнения в старших разрядах. Примем, что Xj и у - правоустановленные целые положительные числа: X - Х f t , , fXj ,..,, у у , . . , У ,...,Ут, где xj , yj - двоичные разряды; j - номер разряда, (j 1-m), Совокупности старших разрядов и у до j-ro разряда включительно обозначим через рассматривая их как целые положительные чи.сла. В процессе пора зрядного сравнения в логических ячейках определяются по характеру первого (старшего) неравенства цифр Xj и у, числа, большие меньшие или равные у с точностью до рассматриваемого разряда. На каждом шаге сравнения для всех определяются значения модуля разности х - у с точностью до рассматриваемого разряда Calj / С, которые корректируются путем сдвига начала шкалы отсчета таким образом, чтобы наименьшее из них равнялось нулю. Здесь С - вёЯйчина сдвига начала шкалы отсчета за счет коррекции у в старших разрядах. После выполнения m шагов сравнения искомые числа определяются по нулевому значению скорректированной разности. Если У1 г в ячейке обработки разрядных слоев определяется значение Ь U rtyJi т° teli-l ild-c. Учитывая,--что tZJj . j , получаем для у )-с- l xaKWs-rC/2)5Cii-yi 2d j.,Q где 0. к -у:, d-ij.- скорректированное значение D jАналогично для х у получаем (1л 2d..-Q. Окончательно получаем .-v Q, если хЛ i-i Mi-i-, .-Q,ecAvi x - j., 0 + |Q/,,,, О, если Xj i{VXjiij, Ql -1,если 1 , -,ейм SiTr-l i Как следует из (1), для наименьш го значения скорректированной величины в предыдущем разряде, т.е. для О, Ogj меняется в пределах - 1, О, 1. По этим значениям коррек тируются все значения ,T.e. d,7 D;.j -Dp,j. Для передачи значений Кор рекции используются две числовые ши ны А и В . При этом А 1, если имеется хртя бы одно - 1; В 1, если имеется хотя бы одно DKJ 0. Если А О и В О, то это означает что для всех . О, t. Из сказанного следует, что ft-VlD j -1)Y(.,-OK(tx, i ylj-i).,-Mi.,)6iO)j (D j 0 -NU;i-i-0) логической ячейке достаточно фиксировать лишь три значения , iu именно: d,j О, 1 и : 2, так как, в соответствии с (), если dej 2, то и при рассмотрении всех более младших разрядов.х, начиная с (j+1)-ro разряда, будет 2, у (J+1)fm. Таким образом, после выполнения шагов сравнения, число, ближайЬюе или равное входному признаку, опред ляется по условию «1 nj Ячейка содержит триггеры 1-3,обр зующие регистр 4 результата поиска, элементы И-НЕ 5-7, числовые шины 8 и 9, первый элемент НЕ 10, имеющий выход 11, второй элемент НЕ 12, эле менты И 13-26, элементы ИЛИ 27-35, первый 36, второй 37 и третий 38 вх ды ячейки, выход 39 ячейки, первые выхода 40-42 триггеров, 1-3 соответ ственно, вторые выходы 43 и 44 триг геров 1 и 2 соответственно,, первые входы 45-47, вторые входы 48-50 и третьи входы 51-53 триггеров 1-3 со ответственно, четвертый 54 и пятый .55 входы ячейки. Ячейка работает следующим образо Производится установка в нулевое состояние триггеров 1-3 (фиг. 1) по дачей сигнала на вход 55 ячейки. В процессе поиска- на каждом шаге срав нения на входы 36-38 ячейки поступа ют соответственно сигналы |UJ P-j При этом ячейка может находиться в одном из 6 возможных состояний где а - начальное состояние, указа ных на графе состояний ячейки фиг4 Здесь ,2 сигналы перехода, начальное состояние а соответствует значениям О и .,( Lvli-v.T соответствует значении ly3i-t f ям d/j. О J-l dijvv 1 и cy3j. .., 0 и txOj-, ylj.,. cd ij 1 2. Выход из состояния ag осуществляется при появлении cHrnajia первого поразрядного неравенства mj или 8;. В обоих случаях 1. Отметим, что пока среди чисел xj имеется хотя бы один, равный у с точностью до J-ro разряда, для всех . ylj Поэтому при появлении сигнала первого поразрядного неравенства не может (А 0), и ячейка перебыть О ходит в состояние а. или а при этом В О, или а или а, В 1. Отсюда С., 8:: в; С, ( В; Г л ХП П.- Я1.- -О 1, в, С состоянии если |ljj; если Pj если Sj При 3foM если А О и В О, то Ъц -{ Q, Если А О и В 1, то dij - Oii 01/1. ,Е:СЛИ l, то независимо от значения В d ОУ1У2. ABSj V В результате Cj Cj, . В состоянии ajr 1,если fUji 2,если Pj 3,если Si В О, этом, если А О Если А О (J М . Если и В 1, то А 1, то независимо от значения В dM 2. Таким образом, С ABfU;, А V AB( ) А & V AY В. X X Анало гично можно показать, что С„ SBSi , (i( ,- . Каждое из шести состояний ячейки кодируется определенным набором состояний триггеров 1-3, состояние а кодируется набором (О, О, О) , а набором Uf О, 0), а - набором U О, 1), ад -,набором (О, 1, О), а4 набором (о; 1, 1), aj - набором (1, 1, 1). Отсюда следует, в частности, что выполнение условия кодируется нулевым состоянием третьего триггера 3. После выполнения m шагов сравнения сигнал на этом выходе 39 ячейки означает, что О т .е. рассматриваемое число Х| является ближайшим по значению или равным.у. Технико-экономическое преимущество предлагаемой ячейкизаключается в меньшем количестве оборудования и более высоком быстродействии по сравнению с протётипом. Вместо восьм межчисловых шин используются две шины f количество триггеров и входов логических элементов сокращено в If раза. .Поиск числа, ближайшего по значению или равного у, выполняет ся путем однократного опроса регистра результата поиска Б прототипе за два .такта опроса. изобретення Логическая ячейка для ассоциативного запоминающего устройства, содержащая триггеры, элементы И-НЕ и «числовые шины, отличающаяс я тем, что, с целью упрощения и повБПиеиия быстродействия ячейки, -в нее введены элементы НЕ, элементы И и элементы ИЛИ, причем первые входы первого., второго и третьего элементов И, первого элемента ИЛИ и первого элемента И-НЕ обт единенн и являются первым входом ячейки, первые входы четвертого, пятого и шестого элементов И, второго элемента ИЛИ и второго элемента И-НЕ объединены и йвляются вторым входом ячейки, первые входы седьмого и восьмого эле:ментов И и третьего элемента И-НЕ .объединены и являются третьим входом .ячейкиj первая числовая шина соедин на с выходами первого и второго .элементов , с вторглми. входами треть го и шестого элементов И и входом , первого элемента НЕ, выход которого подключен к вторым входам первого и второго элементов ИЛИ и первым входа девятого, десятого и одиннадцатого, элементов И, вторая числовая шина соединена с выходом третьего элемента И-НЕ с третьими входами.третьего и шестого элементов И и входом второ го элемента НЕ, выход которого подключен к второму входу седьмого и пе воглу входу двенадцатого элементов И первый выход первого триггера подклю чен к второму входу первого элемент И-НЕ, первому вхо,ду третьего элемен та ИЛИ и второму входу пятого элеме та И, выход которого соединен с пер выми входами четвертого и пятого элементов- ИЛИ и вторым входом десят го элемента И, второй выход первого .тригугера подключен к второму входу . второго и четвертному входу шестого элементов И,, первый выход второго триггера подключен к второму входу второго элемента И-НЕ, к вторым входам первого элемента И и -третьего элемента ИЛИ, второй выход второго триггера соединен с четвертым входом третьего и вторым входом четвертого элементов И, первый выход третьего триггера подключен к первым входам ; тринадцатого и четырнадцатого элементов И, а второй выход является выходом ячейки и соединены с третьими входами первого и -второго и вторым входом третьего элементов И-НЕ, выход, первого элемента И соединен с вторыми входами четвертого и пятого элементов ИЛИ и девятого элементаИ, выход второго элемента И под слючен к третьему входу четбертого и первому входу шестого элементов ИЛИ, выход четвертого элемента И соединен с четвертым входом четвертого и первым входом-ВОСЬМОГО: элементов ИЛИ, выход седьмого элемента И соединен с третьими входами первого и второго элементов ИЛИ, выходы третьего, шестого, восьмого, девятого, десятого, одиннадцатого, двенадцатого, тринадцатого и четырнадцатого элементов И соединены соответственно с первым и вторым входами девятого, третьим входом пятого, с вторыми входами восьмого и шестого, первым и вторым входами седьмого, и.третьими входами восьмого и шестого элементов ИЛИ, выходы элементов ИЛИ с первого по пятый соединены соответственно с вторыми входами тринадцатого, четьгрнадцатого, восьмого, двенадцатого и одиннсшцатого элементов И, первые входы первого, второго и третьего триггеров соединены соответственно с выходами восьмого,.шестого и седьмого элементов ИЛИ, а вторые входы объединены и являются четвертым входом ячейки, третий вход первого и второго триггеров объединены и являются пятым входом ячейки, который соединен с третьим входом девятого элемента ИЛИ, выход которого подклю : чен к третьему входу третьего триггера. . Источники информации, при-нятые во внимание при экспертизе 1.Авторское свидетельство СССР № 332502, кл. G 11 С 15/00, 1970. 2.Авторское свидетельство СССР № 780043, кл, G 11 С 15/00, 1980 (прототип).

V