Устройство для определения отношения множеств

 

Изобретение относится к вычислительной технике и может быть использовано при построении систем управления банками данных. Цель изобретения - расширение области применения устройства за счет реализации сравнения всех соответствующих элементов двух множеств. Устройство содержит два коммутатора 3 и 4, два регистра 5 и 6 признаков, блок 10 сравнения, элемент НЕ 14, элементы ИЛИ 9 и дешифратор 8

в него введены два блока 1 и 2 памяти, шифратор 7, два счетчика 11 и 12, три элемента И 16,17 и 20, второй элемент НЕ 15, элемент 19 задержки и элемент ИЛИ 18 начальной установки. После подачи на вход устройства кода операции сравнения на информационные входы блоков сравнения поступают поочередно элементы множеств и, если критерии сравнения выполняются, на выходе устройства появляются код отношения множеств. 1 ил.

СОЮЗ СОЯЕТСНИХ

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

РЕСПУБЛИН щ) G 06 F 15/38, 7/02

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

Г10 ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

ПРИ ГКНТ СССР

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

И АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4063098/24-24 (22) 25.04.86 (46) 30.04.90. Бюл. № 16 (72) Б,С. Богумирский, С,В, Глазков и В.я. Яцук (53) 681 . 325 (088. 8) (56) Авторское свидетельство СССР

И- 1543419, кл. G 06 Г 15/38, 1985.

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

У 121 1759, кл. G 06 F 15/38, G 06 F 7/02, 1985.

„„Я0„» 1561074 А1

2 (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ ОТНОШЕНИЯ МНОЖЕСТВ (57) Изобретение относится к вычислительной технике и может быть использовано при построении систем управления банками данных, Цель изобретения — расширение области применения устройства за счет реализации сравнения всех соответствующих элементов двух множеств. Устройство со15610 держит два коммутатора 3 и 4, два регистра 5 и 6 признаков, блоки 10 сравнения, элемент НЕ 14, элементы

ИЛИ 9 и дешифратор 8, в него введены два блока 1 и 2 памяти, шифратор 7, 5 два счетчика 11 и 12, три элемента И 16, 17 и 20, второй элемент

НЕ 15, элемент 19 задержки и эле74 4 мент ИЛИ 18 начальной установки, После подачи на вход устройства кода операции сравнения на информационные входы блоков сравнения поступают поочередно элементы множеств и, если критерии сравнения выполняются, на выходе устройства появляется код отношения множеств. 1 ил.

I!

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

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

На чертеже приведена схема уст,ройства.

Устройство содержит блоки 1 и 2 25 памяти, коммутаторы 3 и 4, регистры 5 и 6 признаков, шифратор 7, дешифратор 8, элементы ИЛИ 9, блоки срав,нения 1О, счетчики 11 и 12, выход"ной элемент ИЛИ 13, элементы ПЕ 14 ,и 15, элементы И 16, 17, элемент

ИЛИ 18 начальной установки, элемент

19 задержки, элемент И 20, входы 21 и 22, вход 23 запуска, выходы 24 и тактовый вход 25. Блок сравнения

10 осуществляет проверку следующих отношений сравнения: =, ф, <, Он выдает сигнал на своем выходе лишь в том случае, когда отношение сравнения, конкРетно oIIpepåëÿåìîå 40 подачей на соответствующий управляющий вход единичного сигнала, не удов-. летворяется между кодами на группах его информационных входов и присутствует сигнал на его разрешающем 45 входе.

Шифратор 7 выдает сигнал на своем выходе при подаче на его управляющий вход единичного сигнала.

Блоки 1 и 2 памяти хранят элементы сравниваемых множеств. Последний элемент каждого множества помечается единицей в О-ом разряде. Остальные элементы множеств отмечены нулем, Адрес элементов множеств представляет собой целое число в интервале от 1 до L где L — число элементов множеств. Сравниваемые множества имеют одинаковую размерность. Блоки

1 и 2 выдают содержимое соответствующих ячеек памяти на свои выходы и поддерживают его там при подаче соответствующего адреса на адресный вход.

Элементы множеств состоят из и компонент.Пусть заданы списки Х=р, pr

Я р и У = r,, г,...,r компонент, определяющие элементы двух множеств

А и В, подлежащих сравнению (р, r; номера (имена) компонент, i = 1,2, m, ш n). Тогда под критерием сравнения элементов множеств А и В понимают (а ЯВ,, ) А(а ЯВ„)А...А(а QB> ) где а, -р -ая компонента элемента

Р; множества А, В„ -r, -ая компонента элемента множества В,  — одно из отношений: =,,ф (с

Каждой компоненте элементов мно- жеств в регистрах 5 и 6 соответствует один разряд.

Устройство работает следующим образом, По групце 21 входов в разряды регистра 5 записываются единицы, соответствующие списку Х, Аналогично в разряды регистра 6 по группе 22 входов записываются единицы, соответствующие списку У, Коммутаторы

3 и 4 настраиваются на выдачу компонент элементов множеств А и В в соответствии со списками X u Y.

Дешифратор 8 анализирует количество единиц в регистре 5. Если в регистре 5 находится код, содержащий

m единиц, то появляется сигнал на

m-oM выходе дешифратора 8. Этот сигнал через элементы ИЛИ 9 поступает на разрешающие входы блоков сравнения 10 с первого по m-ый. Следовательно, во внимание принимаются резуль1561074 таты сравнения m компонент элементов множеств А и В.

В исходном состоянии счетчики 11 и 12 содержат информацию, относящуюся к предыдущему сравнению некоторых двух множеств (при подаче питания предыдущим будет какое-то

II I1 фиктивное сравнение). Результатом предыдущего сравнения является блокировка подачи синхроимпульсов со входа 25 устройства.

Запуск устройства осуществляется подачей сигнала на вход 23 устройства. По этому сигналу содержимое счетчиков 11 и 12 стает равным единице. Блоки 1 и 2 памяти выдают на свои выходы первые элементы множеств

А и В. С выхода счетчика 11 . сигнал поступает на первый управляющий вход включенных блоков сравнения 10. Выделенные коммутаторами 3 и 4 компоненть» элементов проверяются блоками сравнения 10 на выполнение первой операции сравнения, Если критерий сравнения выполняется, то единичный сигнал с выхода элемента НЕ 14 поступает на третий вход элемента И 17, на первый вход которого подается единичный сигнал с выхода элемента НЕ 15 (так как элементы множеств не последние). Синхроимпульс, поступивший со входа 25 устройства, увеличивает значение счетчика 12 на единицу. На выходах блоков 1 и 2 появляются следующие элементы множеств А и В, Блоки сравнения 10 производят их сравнение.

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

Сравниваются следующие элементы множеств и т.д., пока на выходах блоков 1 и 2 не появятся компоненты последних элементов множеств. Единичный сигнал с выхода блока 2 блокирует приращение значения счетчика 12.

В случае "успешного" сравнения последних элементов множества А и В на оба входа элемента И 20 поступают единичные сигналы с управляющих выходов блоков 1 и 2 (элемент задержки

19 компенсирует время переходных процессов при сравнении). Когда сиг" нал поступает на управляющий вход шифратора 7, последний выдает на выходе 24 код, соответствующий найденному отношению.

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

Устройство для определения отношения множеств, содержащее первый и

40 второй коммутаторы, первый и второй регистры признаков, и блоков сравнения, выходной элемент ИЛИ, элемент НЕ, группу и элементов ИЛИ, дешифратор, причем информационные входы первого

45 и второго регистров признаков являются входами первого и второго признаков устройства, а выходы соединены с управляющими входами первого и второго коммутаторов соответст50 венно, i-e, где i = 1,...,п, n— число отношений группы выходов первого и второго коммутаторов соединены соответственно с первой и второй груп;пами входов i-ro блока сравнения, выход которого соединен с соответствующим входом выходного элемента ИЛИ, выход которого соединен с входом элемента НЕ, выходы первого регистра признаков соединены с входами дешиф5

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

ИЛИ 13 присвоит содержимому счетчика 12 значение, равное единице. Кроме -.îãî, сигнал с выхода элемента ИЛИ 13 поступает на второй вход элемента И 16. Пришедший синхроим пульс увеличивает на единицу значение счетчика 11. Зле»»енты множеств А и В сравниваются, начиная опять с первых элементов, на выполнение следующей операции сравнения.

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

Код операции сравнения подается на вход устройства. Пусть имеются два множества, отношение между которыми необходимо определить. Решение этой задачи требует применения следующего алгоритма: выбор операции сравнения; подача на информационные входы компараторов первых элементов множеств; сравнение элементов множеств; если критерий сравнения не выполняется, то переход на п.1; если элементы мноI жеств последние, то переход на п. 8; подача на информацион ые входы компараторов следующих элементов множеств переход на п.3; выдача кода операции сравнения.

1561074

Составитель В. Козлов

Редактор Н, Горват Техред Л,0лийнык Корректор Н „Король

Заказ 977

Тираж 568 Подписное

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

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

Производственно-издательский комбинат "Патент"., r.ужгорол, ул. Гагарина, 101 ратора, j -й (j = 1, 2,..., n-1), выход, которого соединен с входами элементов ИЛИ группы с первого по j-й, а (j+1)-"é выход дешифратора соединен

5 с входом разрешения сравнения п-го блока сравнения, выход j-го элемента ИЛИ группы соединен с входом разрешения сравнения j-го блока сравнения, 1-е управляющие входы(1с = 1, 2...6) всех блоков сравнения объединены, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет возможности сравнения всех соответствующих элементов двух множеств, в него введены первый и второй блоки памяти, шифратор,первый и второй счетчики, первый, второй и третий элементы И, второй элемент НЕ, элемент ИЛИ начальной установки, элемент задержки, причем i-e группы выходов первого и второго блоков памяти соединены с i-ми группами информационных входов первого и второго коммутаторов соответственно,выход k-ro разряда первого счетчика соединен с k-ми управляющими входами блоков сравнения, и k-м входом шифратора, управляющий вход которого соединен с выходом первого элемента И, первый вход которого через элемент задержки соединен с выходом нулевого разряда первого блока памяти, а второй вход соединен с выходом нулевого разряда второго блока памяти и через второй элемент НЕ с первым входом второго элемента И, выход которого соединен со счетным входом второго счетчика, вход установки в единичное состояние которого соединен с выходом элемента

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