Устройство для определения отношения множеств Советский патент 1990 года по МПК G06F15/38 G06F7/02 

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

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

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

Устройство содержит блоки 1 и 2 памяти, коммутаторы 3 и 4 регистры 5 и 6 признаков, шифратор 7, дешифратор 8, элементы ИЛИ 9, блоки сравнения 10, счетчики 11 и 12, выходной элемент ИЛИ 13, элементы НЕ 14 и 15, элементы И 16, 17,, элемент ИЛИ 18 начальной установки, элемент 19 задержки, элемент И 20, входы 21 и 22, вход 23 запуска, выходы 24 и тактовый вход 25„ Блок сравнения 10 осуществляет проверку следующих отношений сравнения: , Ј , , , . Он выдает сигнал на своем выходе лишь в том случае, когда отношение сравнения, конкретно определяемое подачей на соответствующий управляющий вход единичного сигнала, не удовлетворяется между кодами на группах его информационных входов и присутствует сигнал на его разрешающем входе.

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

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

0

5

0

5

0

5

0

5

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

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

р VYI и компонент, определяющие элементы двух множеств А и В, подлежащих сравнению (р, f - номера (имена) компонент, i 1,2, ..., m, ). Тогда под критерием сравнения элементов множеств А и В понимают

Ц,,9ВГ, ) Л ( Ъ,2 )А . .. )

где а о. -ая компонента элемента

множества А, В. компонента элемента

множества В, 9 - одно из отношений: ,

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

Устройство работает следующим образом.

По гр.упце 21 входов в разряды регистра 5 записываются единицы, соответствующие списку X. Аналогично в разряды регистра 6 по группе 22 входов записываются единицы, соответствующие списку Y0 Коммутаторы 3 и 4 настраиваются на выдачу компонент элементов множеств А и В в соответствии со списками X и Y.

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

В исходном состоянии счетчики 11 и 12 содержат информацию, относящуюся к предыдущему сравнению некоторых двух множеств (при подаче питания предыдущим будет какое-то фиктивное сравнение). Результатом предыдущего сравнения является блокировка подачи синхроимпульсов со входа 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 код, соответствующий найденному отношению.

5610746

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

с ИЛИ 13 присвоит содержимому счетчика 12 значение, равное единице. Кроме того, сигнал с выхода элемента ИЛИ 13 поступает на второй вход элемента И 16. Пришедший синхроим10 пульс увеличивает на единицу

значение счетчика 11, Элементы множеств А и В сравниваются, начиная опять с первых элементов, на выпол- ,- нение следующей операции сравнения.

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

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

25 алгоритма: выбор операции сравнения; подача на информационные входы компараторов первых элементов множеств; сравнение элементов множеств; если критерий сравнения не выполняется,

30 то переход на п.1; если элементы множеств последние, то переход на п. 8; подача на информацион ые входы компараторов следующих элементов мно5

0

5

0

жеств переход на п.З; выдача кода операции сравнения.

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

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

5

0

5

0

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

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

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

Редактор Н. Горват

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

Техред Л.Олнйнык Корректор Н. Король

Заказ 977

Тираж 568

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, Москва, Ж-35, Раушская наб., д. 4/5

Подписное