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

 

Изобретение относится к вычислительной технике и может быть использовано в системах контроля и автоматического управления при анализе статистики различных параметров. Целью изобретения является повышение быстродействия устройства . Поставленная цель достигается тем, что оно содержит группы блоков 3 сортировки и блоки 4 вычитания с соответствующими связями, Эги признаки позволяют решать различные задачи разбиения по множеству признаков: определение минимума и максимума, разбиение на классы и т.д. Связи между блоками устройства обеспечивают параллельное выполнение всех этих задач. 1 з.п. ф-лы, 3 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (sl)s G 11 С 15/00

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 S

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 479144G/24 (22) 13.02.90 (46) 07.11.92. Бюл. N. 41 (71) Московский институт инженеров гражданской авиации (72) С. Ж. Кишенский, А. Я. Крекер, А. Л,Кузьмин и О, lO, Христенко (56) Авторское свидетельство СССР

Мт 277857, кл, G 11 С 15/00, 1970.

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

1 1. 1052792, кл. G 11 С t5/00, 1983 /прототип/.. (54) АССОЦИАТИР НОЕ ЗАПОМИНА1ОЩЕЕ

УСТРОЙСТВО

Изобретение относится к автоматике и вычислительной технике и может быть использовано в системах контроля и авто латического управления при анализе статистики различных параметров.

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

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

Наиболее близким по технической сущности к заявляемому является ассоциативное запоминающее устройство, содержащее регистр опроса, информационные регистры, аналого-цифровые преобразователи, блоки сравнения и индикаторы, цифроаналоговый преобразователь, ключи, .БЫ 1774377 А1 (57) Изобретение относится к вычислительной технике и может быть использовано в системах контроля и автоматического управления при анализе статистики различных параметров. Целью изобретения является повышение быстродействия устройства. Поставленная цель достигается тем, что оно содержит группы блоков 3 сортировки и блоки 4 вычитания с соответствующими связями, Эти признаки позволяют решать различные задачи разбиения по множеству признаков: определение минимума и максимума, разбиение на классы и т.д. Связи между блоками устройства обеспечивают параллельное выполнение всех этих задач. 1 з.п, ф-лы, 3 ил. пороговый элемент, сумматор, блок сравнения и элементы И. Недостатком известного устройства является узость функциональных возможностей за счет ограниченного числа критериев поиска, и низкое быстродействие зг счет последовательного анализа по различным критериям поиска.

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

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

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

Кроме того, ка>кдый блог сортировки содержит элемент сравнения, четыре ключевых элемента и инвертор, причем вход инвертора соединен с управляющими входами первого и второго ключевых элементов и выходом элемента сравнения, первый и второй входы которого являются первым и вторым входами блока сортировки соответственно, и соединены с информационными входами первого и второго ключевых элементов сответственно, и третьего и четвертого ключевых элементов соответствен5

50 но, управляющие входы которых соединены с выходами инвертора, выходы первого и четвертого ключевых элементов соединены и являются первым выходом блока сортировки, выходы второго и третьего ключевых элементов соединены и являются вторым выходом блока сортировки, На фиг. 1 приведена структурная схема ассоциативного запоминающего устройства; на фиг, 2 — структурная схема последовательного соединения нечетной и четной групп блоков сортировки; на фиг, 3 — структурная схема блока сортировки.

Ассоциативное запоминающее устройство содер>кит группу 1 информационных регистров, группу2 -2к цифро-аналоговых преобразователей, последовательно соединенные группы 31-Зк блоков сортировки, группу 41-4к-1 блоков вычитания, группу 5,5к- блоков сравнения, регистр б опроса, цифроаналоговый преобразователь 7, вход

Oрегистра опроса,,выходы 911-9к аналогоцифровых преобразователей группы, выходы 91, +1 — 9к, + блоков сравнения i-й группы, l --1,V.

Нечетная группа блоков сравнения (фиг, 2) содержит (32i+l) К/2 блоков сортировки, четная (3>;) — (К/2) — 1 блоков сортировки 10.

Блок сортировки (фиг. 3) содержит элемент 11 сравнсния, ключевые элементы 121124 с первого по четвертый, инвертор 13.

Устройство позволяет разбить все мно>кество приз IBKQB на классы, то есть, произвести классификацию признаков, Различными признаками /классами/ считаем те их совокупности, которые внутри каждого класса отличаются по значению на некоторую величину, не превышающую заданное заранее значение, задаваемое признаком опроса, К различным классам принадле>кат те совокупности признаков, ближайшие из которых отличаются по значению на величину, большую заданной. Так, если имеются признаки, значения Ko. opbfx равны, например, 5, 11, 8, 7, 14, 13, - признак опроса равен 3, то общая совокупность признаков разбивается на два класса: а/ 5, 7 и 8 и б/ 11, 13 и 14, Внутри каждого класса соседние признаки отличаются на величину, меньше признака опроса, а между классами — на величину, большую чем признак опроса, Устройство работает следующим образом.

Начальное состояние устройства — регистры 1 и 6 в нулевом состоянии, сигналов с блоков сравнения нет. Цепи установки в начальное состояние не показаны.

Работа устройства начинается с записи в регистры 1 значений признаков и значе1774377 ния признака опроса в регистр б. В цифроаналоговых преобразователях эти значения преобразуются в соответствующие аналоговые величины. Аналоговые значения признаков поступают ««а последовательно соединенные группы блоков сортировки 3, состоящие из блоков сортировки 10. Блок сортировки 10 работает следу«ощил«oGpaзом: на его входы поступают два з««ачения признаков. Схема сравнения 11 формирует на выходе сигнал в случае, когда значение признака на входе 91 больше значения признака на входе 9z. Этот сигнал является разрешающим для ключевых элементов 121 и

12, он открывает их, и значе«.ия признаков с первого и второго выходов блока 10 поступают 6оответственно на его первый и второй выходы, Если же значе««ия признаков равны, либо значение признака на втором входе больше, схема 11 не выдает единичного сигнала; в этом случае он формируется на выходе эле«лента НЕ /инвертора/ и открывает ключевые элементы 12з и 134,з««ачение признака с первого входа коммутируется на второй выход и наоборот.

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

За с, ет К ступеней упорядочения /К групп блоков сравнения/ при л«обом ðàñïoложении значений признаков на выходе К-й группы блоков сортировки 3к значения признаков будут упорядочены: ««а первом D«,lxoде 91,<+> — максимальное значение признака, на выходе Як,к+« — минимальное значение признака. Соединение четных и нечетных групп блоков сортировки /фиг. 2/ обеспечивает участие всех при" íàêîâ в процессе упорядоче««ия.

Упорядоченнь«е значения признаков поступа«от ««а блоки 4 вычитания, причем на вход "уменьшаемого" каждого блока 4 поступает большее значение признака, а ««а вход "вычитаемого" — меньшее значение признака. С блоков 4 формируются значения разностей смежных /после упорядочения/ признаков. Эти разности поступают D устройства 5 — блоки сравнения, которые осуществляют сравнение этих разностей со значением приз««ака опроса, Блоки 5 выдают сигналы на выходах в случае, когда признак опроса меньше соответствующей разности, Таким образом, сигналы с блоков сравнения 5 являются "разделя«ощими" для различных классов признаков, Пусть имеется K=8 значений признаков, которые на выходе последнего, восьмого блока 3 угорядочены по значениям; пусть эти значения равны, например. 8, 5, 4, 4, 3, 2, 1 и 1. Соответствую«цие значения разно5

50 стей, например, при пороге — опросе признака, равном 1,5,; 3, 1, О, 1, 1, 1, О, Таким образом, значения признаков распадаются на два класса — первый признак и второй-восьмой признаки; при этом сработает первый блок сравнения 5, фиксирующий этот факт.

Исходное расположение каждого признака в регистрах 1 определяется однозначно пр!1 анализе сигналов, например, с инверторов 13 блоков 10 сортировки. Анализируя последовательность сработавших

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

Таким образом, устройство позволяет

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

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

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

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

1774377 гз

3 соединен с первым выходом первого блока сортировки предпоследней группы, первые входы блоков вычитания, кроме первдго, соединены с соответствующими первыми и вторыми ьыходами блоков сортировки последней группы, вторые входы каждого блока вычитания, кроме последнего, соединены с первыми входами последующих блоков вычитания, а второй вход последнего блока вычитания соединен с вторым выходом последнего блока сортировки предпоследней группы, первые и вторые входы бло.;ов сортировки первой группы соединены с выходами соответствующих цифроаналоговых г1реобраэователей группы, первые выходы блоков сортировки, кроме первых, нечетных групп соединены с вторыми входами соответствующих блоков сортировки последующих четных групп, а первые выходы. первых блоков сортировки нечетных групп, кроме предпоследней, соединены с первыми входами первых блоков сортировки последующих нечетных групп, вторые выходы блоков сортировки, кроме последнего, нечетных групп, соединены с первыMH ВхорВМН соответству loLUI1x блоков сортировки последующих четных групп, а вгорые выходы последних блоков сортировки нечетных. групп, кроме предпоследней, соединены с вторыми входами последних блоков сортировки последующих нечетных групп, первые входы блоков сортировки, кроме первых, нечетных групп, кроме первой, соединены с вторыми выходами соот5 ветствующих блоков сортировки предыдущих четных групп, а вторые входы блоков сортировки, кроме последних, нечетных групп, кроме первой, соединены с первыми выходами соответствующих блоков

10 сортировки предыдущих четных групп, 2, Устройство по п. 1, о т л и ч а ю щ е ес я тем, что каждый блок сортировки содержит элемент сравнения, четыре ключевых элемента, инвертор, вход которого соедиl5 нен с управляющими входами первого и второго ключевых элементов и выходами элемента сравнения, первый и второй входы которого являются первым и вторым входами блока сортировки соответственно и сое20 динены с информационными входами первого и второго ключевых элементов соответственно и третьего и четвертого ключевых элементов соответстненно, управляющие входы которых соединены с

25 выходом инвертора, выходы первого и четвертого ключевых элементов соединены и являются первым выходом блока сортировки, выходы зторого и третьего ключевых элементов соединены и являются вторым

30 выходом блока сортировки, l774377

Составитель С. Кишенский

Техред M.Моргентал Корректор O Кравцова

Редактор

Производственно-издательский комбинат "Патент", r. Ужгород, ул.Гагарина, 101.

Заказ 3929 Тираж Подписное

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

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