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

(71) Московский инсданской авиации(56) Авторское сеидеМт 277857, кл, О 11 САвторское свиде2792, кл. 6 11 итут инженеров граж Иг 106 тип/ втоматике и сет быть исля и автоглди анализе запоминаюегистр опроединенные фровые блое преобразоовые блоки устройст итериев п хническои сущся ассоциативустройство, информационовые преобрди индикаторы, ватель, ключи,ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМИПРИ ГКНТ СССР НИЕ ИЗОБ(46) 07.11.92.Бюл, ГФ 4 А, Я, Крекер, А. Л,Кузькотельство СССР15/00, 1970.тельство СССРС 15/00, 1983 /прото(54) АССОЦИАТИР.НОЕ ЗАПОМИНАЮЩЕУСТРОЙСТВО Изобретение относится к а вычислительной технике и глох польэовано в системах контро тического управления пр статистики различных параметр Известно ассоциативное щее устройство, содержащее р са, последовательно со информационные регистры, ци ки сравнения,цифроаналоговы ватели, селекторы, аналог соавнения и индикагоры. Недостатками известного являются ограниченное число к иска.Наиболее близким по те ности к заявляемому являе ное запоминающее содержащее регистр опроса ные регистры, аналого-циф зовдтели, блоки сравнения цифроаналоговый преобраз(57) Изобретение относится к вычислительной технике и может быть использовано в системах контроля и автоматического управления при анализе статистики различных параметров, Целью изобретения является повышение быстродействия устройства. Поставленная цель достигается тем, что оно содержит группы блоков 3 сортировки и блоки 4 вычитания с соответствующими связями, Эти признаки позволяют решать различные задачи разбиения по множеству признаков: определение минимума и максимума, разбиение на классы и т.д. Связи между блоками устройства обеспечивают параллельное выполнение всех этих задач. 1 з.п, ф-лы, 3 ил. пороговый элеглент, сумматор, блок сравнения и элементы И,Недостатком известного устройства является узость функциональных возможностей за счет ограниченного числа критериев поиска, и низкое быстродействие зг счет последовательного анализа по различным критериям поиска.Целью изобретения является повышение быстродействия устройства,Поставленная цель достигается тем, что в ассоциативное запоминающее устоойство, содержащее информационные регистры, группу цифроаналоговых преобразователей, регистр опроса, цисрроа.налоговый преобразователь, блоки сравнения, выходы которых являются выходами устройства, первые входы блоков сравнения соединены с выходом цифроаналогового преобразователя, входы которого соединены с выходами регистра опроса, входы которого являются входами опроса устройства, входы цифроаналоговых преоб 177437755 разователей группы соединены с соответствующими выходами информационных регистров, входы которых являются информационными входами устройства, введены группы блоков сортировки и блоки вычитания, выходы которых соединены с вторыми входами соответствуюших блоков сравнения, первый вход первого блока вычитания соединен с первым выходом первого блока сортировки предпоследней группы, первые входы блоков нычитания, кроме первого, соединены с соответствующими первыми и вторыми выходами блоков сортировки последней группы, вторые входы каждого блока вычитания, кроме последнего, соединены с первыми входами последующих блоков вычитания, а второй вход последнего блока вычитания соединен с вторым выходом последнего блока сортировки предпоследней группы, первые и вторые входы блоков сортировки первой группы соединены с выходами соответствующих цифроаналоговых преобразователей, первые выходы блоков сортировки, кроме первых, нечетных групп соединены с вторыми входами соответствующих блоков сортировки последующих четных групп, а первые выходы первых блоков сортировки нечетных групп, кроме предпоследней, соединены с первыми входами пердых блоков сортировки последующих нечетных групп, вторые выходы блоков сортировки, кроме последнего, нечетных групп, соединены с первыми входами соответстнующих блоков сортировки последующих четных групп, а вторые выходы последних блоков сортировки нечетных групп, кроме предпоследней, соединены с вторыми входами последующих блоков сортировки последующих нечстных групп, первые входы блоков сортировки, кроме первых, нечетных групп, кроме первой, соединены с вторыми выходами соответствующих блоков сортировки предыдущих четных групп, а вторые входы блоков сортировки, кроме последних, нечетных групп, кроме первой, соединены с первыми выходами соответствующих блоков сортировки предыдущих четных групп,Кроме того, какдый блог сортировки содержит элемент сравнения, четыре ключеных элемента и инвертор, причем вход иннертора соединен с управляющими входами первого и второго ключевых элементов и выходом элемента сравнения, первый и второй входы которого являются первым и вторым входами блока сортировки соответственно, и соединены с информационными входами первого и второго ключевых элементов сотнетстненно, и третьего и четвертого ключевых элементов соответствен 5 10 15 20 25 30 35 40 45 50 но, управляющие входы которых соединеныс выходами иннертора, выходы первого ичетвертого ключевых элементов соединеныи являются первым выходом блока сортировки, выходы второго и третьего ключевыхэлементов соединены и являются вторымвыходом блока сортировки,На фиг, 1 приведена структурная схемаассоциативного запоминающего устройства; на фиг, 2 - структурная схема последовательного соединения нечетной и четнойгрупп блоков сортировки; на фиг, 3 - структурная схема блока сортировки,Ассоциативное запоминающее устройство содеркит группу 1 информационныхрегистров, группу 21-2 к цифро-аналоговыхпреобразователей, последовательно соединенные группы 31-Зк блоков сортировки,группу 41-4 кблоков вычитания, группу 515 кблоков сравнения, регистр б опроса,цифроаналоговый преобразователь 7, вход8 регистра опроса, выходы 91-9 к 1 аналогоцифровых преобразователей группы, выходы Яц+1 - 9 к,+1 блоков сравнения -й группы,:-1,К,Нечетная группа блоков сравнения (фиг,2) содержит (32+1) К/2 блоков сортировки,четная (32;) - (К/2) - 1 блоков сортировки 10.Блок сортировки (фиг, 3) содержит элемент 11 сравнсния, ключевые элементы 121124 с первого по четвертый, инвертор 13.Устройства позволяет разбить нсе мнокество признаков на классы, то есть, произвести классификацию признаков,Различными признаками /классами/ считаем те их совокупности, которые внутрикаждого класса отличаются по значению нанекоторую величину, не превышающую зэданное заранее значение, задаваемое признаком опроса, К различным классампринадлежат те совокупности признаков,ближайшие из которых отличаются по значению на величину, большую заданной. Так,если имеются признаки, значения которыхравны, например, 5, 11, 8, 7, 14, 13, а признак опроса ранен 3, то общая совокупностьпризнаков разбивается на дна класса: а/ 5,7 и 8 и б/ 11, 13 и 14, Внутри каждого классасоссдние признаки отличаются на величину,меньше признака опроса, а между классами - на величину, большую чем признакопроса,Устройство работает следующим образом,Начальное состояние устройства - регистры 1 и б в нулевом состоянии, сигналов сблоков сравнения нет. Цепи установки в начальное состояние не показаны.Работа устройства начинается с записив регистры 1 значений признаков и значе 1774377ния признака опроса е регистр б. В цифроаналоговых преобразователях эти значения преобразуются е соответствующие аналоговые величины. Аналоговые значения признаков поступают а последовательно соедиценные группы блоков сортировки 3, состоящие из блоков сортировки 10. Блок сортировки 10 работает следующим образом: на его входы поступают деэ зачения признаков. Схема сравнения 11 формирует ца выходе сигнал в случае, когда значение признака на входе 91 больше значения признака на входе 9 г, Этот сигнал является разрешающим для ключевых элементов 12 и 122, он открывает их, и значения признаков с первого и второго выходов блока 10 поступают 6 оотеетственно на его первый и второй выходы, Если же зцачеия признаков равны, либо значение признака ца втором входе больше, схема 11 не выдает единичного сигнала; в этом случае он формируется на выходе элеменга НЕ /ицвертора/ и открывает ключевые элементы 12 з и 134,зачение признака с первого входа коммутируется ца второй выход и наоборот. Таким образом, в блоке сортировки больший по эачению сигнал коммутируется а первый выход, а меньший - цэ второй.За счет К ступеней упорядочения /Кгрупп блоков сравнения/ при лабом расположении значений признаков на выходе К-й группы блоков сортировки 3 к значения признаков будут упорядочены: э первом выходе 91,к+ - максимальное значение признака, нэ выходе Як,к+ - минимальное значение признака, Соединение четных и нечетных групп блоков сортировки /фиг. 2/ обеспечивает участие всех признаков е процессе упорядочеия,Упорядоченнье значения признаков поступэот а блоки 4 вычитания, причем на вход "уменьшаемого" каждого блока 4 поступает большее значение признака, э э вход "вычитаемого" - меньшее значениепризнака. С блоков 4 формируются значения разностей смежных /после упорядочения/ признаков. Эти разности поступают вустройства 5 - блоки сравнения, которые осуществляют сравнение этих разностей со значением призака опроса, Блоки 5 выдают сигналы цэ выходах е случае, когда признак опроса меньше соответствующей разности, Таким образом, сигналы с блоковсравнения 5 являются "рэзделяощими" дляразличных классов признаков,Пусть имеется К=8 значений признаков,которые на выходе последнего, восьмого блока 3 упорядоченьпо значениям; пустьэти значения равны, например, 8, 5, 4, 4, 3, 2, 1 и 1, Соответствующие значения разно 5 10 15 20 25 30 35 40 50 стей, например, при пороге - опросе признака, равном 1,5, равны; 3, 1, О, 1, 1, 1, О, Таким образом, зцачения признаков распадаются на два класса - первый признак и еторой-еосьмол признаки; при этом сработает первый блок сравнения 5, фиксирующий этот факт.Исходное расположение каждого признака в регистрах 1 определяется однозначно при анализе сигналов, например, с ицверторов 13 блоков 10 сортировки. Анализируя последовательность сработавших /или нет/ инверторов, начиная от некоторого выбранного по желанио выходного сигнала, используя знание принципа сортировки пар признаков блоками сортировки, однозначно для любого случая можно достичь соответствующего выбранному признаку информационного регистра 1, и,таким образом, определить, расположениезаданного признака в совокупности классов и упорядоченных значений.Таким образом, устройство позволяетрешать различные задачи разбиения множества признаков: определение максимума и минимума среди значений признаков, определение признаков, имеющих минимальное и максимальное значение, разбиение множества признаков на классы, определение наличия максимального и минимального среди значений признаков, отличающихся от остальных на величину, превышающую заданное значение опроса, Причем решение этих задач проивоздится устройством одновременно, что повышает его быстродействие в сравнении с известными устройствамл.Формула изобретения 1. Ассоциативное запоминающее устройство, содержащее информационные регистры, группу цифроаналоговых преобразователей, регистр опроса, цифроаналоговый преобразователь, блоки сравнения, -,ыходы которых являются выходами 5 устройства, первые входы блоков сравнения соединены с выходом цифроаналогового преобразователя, входы которого соединеньс выходами регистра опроса, входы которого являются входами опроса устройства, входы цифроаналоговых преобразователей группы соединены с соотеетст.вующими выходами информационных регистров, входы которых являотся информэционныл 1 и входэлял устройства, о т л и ч а ю щ е е с я тем, что, с целью повышениябыстродействия устройства, оцо содержит группы блоков сортировки и блоки вычитания, выходы которых соединены с вторыми входами соответствующих блоков сравнения, переыл вход первого блока вычитания1774377 гз соединен с первым выходом первого блока сортировки предпоследней группы, первые входы блоков вычитания, кроме первдго, соединены с соответствующими первыми и вторыми ьыходами блоков сортировки последней группы, вторые входы каждого блока вычитания, кроме последнего, соединены с первыми входами последующих блоков вычитания, а второй вход последнего блока вычитания соединен с вторым выходом последнего блока сортировки предпоследней группы, первые и вторые входы блоов сортировки первой группы соединены с выходами соответствующих цифроаналоговых преобразователей группы, первые выходы блоков сортировки, кроме первых, нечетных групп соединены с вторыми входами соответствующих блоков сортировки последующих четных групп, а первые выходы. первых блоков сортировки нечетных групп, кроме предпоследней, соединены с первыми входами первых блоков сортировки последующих нечетных групп, вторые выходы блоков сортировки, кроме последнего, нечетных групп, соединены с первыми входами соответствующих блоков сортировки последующих четных групп, а вгорые выходы последних блоков сортировки нечетных. групп, кроме предпоследней, соединены с вторыми входами последних блоков сортировки последующих нечетных групп, первые входы блоков сортировки, кроме первых, нечетных групп, кроме первой, соединены с вторыми выходами соот ветствующих блоков сортировкипредыдущих четных групп, а вторые входы блоков сортировки, кроме последних, нечетных групп, кроме первой, соединены с первыми выходами соответствующих блоков 10 сортировки предыдущих четных групп,2, Устройство по п. 1, о т л и ч а ю щ е ес я тем, что каждый блок сортировки содержит элемент сравнения, четыре ключевых элемента, инвертор, вход которого соеди нен с управляющими входами первого и второго ключевых элементов и выходами элемента сравнения, первый и второй входы которого являются первым и вторым входами блока сортировки соответственно и сое динены с информационными входамипервого и второго ключевых элементов соответственно и третьего и четвертого ключевых элементов соответственно, управляющие входы которых соединены с 25 выходом инвертора, выходы первого и четвертого ключевых элементов соединены и являются первым выходом блока сортировки, выходы зторого и третьего ключевых элементов соединены и являются вторым 30 выходом блока сортировки,1774377 Г МЖЮг;р Составитель С, Кишенскийехред М.Моргентал Корректор О. Кравцова еда кто ственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101. Прои аказ 3929 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5