SU1561074A1 - Устройство дл определени отношени множеств - Google Patents

Abstract

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

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

Description

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

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

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

Устройство содержит блоки 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

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

Claims (1)

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

   Устройство дл  определени  отношени  множеств, содержащее первый и второй коммутаторы, первый и второй регистры признаков, п блоков сравнени , выходной элемент ИЛИ, элемент НЕ, группу п элементов ИЛИ, дешифратор, причем информационные входы первого и второго регистров признаков  вл ютс  входами первого и второго признаков устройства, а выходы соединены с управл ющими входами первого и второго коммутаторов соответственно , 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

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

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

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

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

   Заказ 977

   Тираж 568

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

   Подписное