Устройство для сравнения информационных массивов

 

Изобретение может быть использовано в системах управления банками данных. Цель изобретения - повышение быстродействия. Устройство содержит два блока 1 и 2 памяти, два коммутатора 3 и 4, элемент 5 задержки, блоки 6 сравнения, элементы ИЛИ, дешифратор 8, два счетчика 9 и 11, регистр 12 и генератор 13 импульсов. Оно осуществляет покомпонентное сравнение выделенных столбцов двух таблиц на предмет принадлежности всех пар компонент одному из отношений =, ≠, *98, *98, ≤, ≥. 1 ил.

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

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

РЕСПУБЛИК

Ai щ)5 6 06 F 15/38, 7/02

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

Н А BTOPCHOINV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ пО изОБРетениям и ОткРытиям

;ПРИ ГКНТ СССР (2 l ) 4343975/24-24

:(22) 03.10.87 ,,(46) 07.08.90,Бюл. 11» 29 (72) Б.С.Бегумирский и В.М,Цыганков ,: (53) 681.325 (088.8)

: (56) Авторское свидетельство СССР

i0» l211759, кл.С 06 Р .15/38, 1985.

Авторское свидетельство СССР ,11» l561074, кл. G Об F 7/15/38,7/02, 1986. (54) УСТРОИСТВО ДЛЯ СРАВНЕНИЯ ИНФОР,МАЦИОННЫХ МАССИВОВ

l(57) Изобретение может быть исполь„.SU„„1 83941 .

2 зовано в системах управления банками данных. Цель изобретения - повышение быстродействия. Устройство содержит два блока 1 и 2 памяти, два коммутатора 3 и 4, элемент 5 задержки, блоки 6 сравнения, элементы ИПИ» дешифратор 8, два счетчика 9 и ll регистр 12 и генератор 13 импульсов, Оно осуществляет покомпонентное сравнение выделенных столбцов двух таблиц на предмет принадлежности всех пар компонент одному из отношений

=» » (» ) ° « » 3 ° 1 ил °

1583941

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

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

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

Устройство содержит блоки 1 и 2 памяти, коммутатора 3 и 4, элемент 5 задержки, блоки 6> — 6„ сравнения, элементы ИЛИ 7, — 7„ t первой группы, дешифратора 8, счетчик 9, элементы

ИЛИ IO< - 10; второй группы, счетчик

11, регистр 12, генератор 13 импульсов, группы 14 и 15 входов признаков, группы lá и 17 адресных входов, вход

18 запуска и выходы 19>- 19 . В качестве коммутаторов 3 и 4 может быть 20 использовано многоканальное устройство для редактирования, которое выделяет по заданным признакам компоненты входного кода и выдает их на выход, сдвигая избранные компоненты к место- 25 положению первой компоненты, исключая тем самым образовавшиеся промежутки., блок 6. сравнения осуществляет

1 проверку кодов, поданных на его информационные входы, на принадлежность 30 к следующим отношениям сравнения:

Ф, (, ), <, ). Он выдает сигнал на своем Е-.м (21,...,6). выходе в том случае, когда поданные на его входы коды не.принадлежат 2-му отношению сравнения и присутствует сигнал на, его управляющем входе. Перенумеровать перечисленные отношения можно в любом . порядке.

Дешифратор 8 выдает сигнал на 40

i-м выходе, если в коде на его и входах присутствует i единиц. Он может быть получен на базе стандарт" ного дешифратора путем объединения по

ИЛИ выходов, соответствующих вход- 45 ным комбинациям, содержащим одинакового число единиц. Блоки I и 2 памяти хранят элементы сравниваемых множеств. Элемент множества представляет собой строку таблицы, 50 состоящую из и компонент, а все множество — таблицу. Элементы множества хранятся в отдельных смежных ячейках памяти, Последний элемент множества помечается единицей в дополнительном разряде, остальные эле-менты отмечены нулем. Два сравниваемьи множества должны иметь одинаковую мощность (одинаковое число элеS m

h (h (ap 9 Ъ, )), Р=< Фи и где a P — Р -я компонента r-й строки первого множества;

Ъ Ч я 1с компонента r-й строки второго множества; отношение сравнения из множества (=,Ф,(,V, <, )), т.е. устройство. сравнивает соответ- . ствующие избранные компоненты одно- . именных строк по шести отношениям, объединяя результаты в строках и столбцах по И. Каждый из и компонент соответствует по одному входу из групп 14 и 15.

Устройство работает следующим образом, При включении питания все шесть разрядов регистра 12 устанавливаются в единичное состояние, а генератор 13 импульсов переводится в заторможенное состояние (цепь установки устройства в исходное состояние не показана).

По группе 14 подается код, содержащий единицы на Р -х входах. Аналогично по группе 15 подается "код, содержащий единицы на gg "x входах. Остальные входы этих групп должны поддерживать нулевой уровень. По группам 16 и 17 входов в счетчики 9 и ll заносятся адреса первых элементов первого и второго множеств соответственно.- В результате этих действий через элементы ИЛИ 7 открываются блоки 6,- 6 сравнения. Иэ блоков 1 и 2 памяти считываются первые элементы сравниваемых множеств, При этом с помощью коммутаторов 3 и 4 на компаратор б подаются компоненты а1

Р

H 5/I ° ментов)..Блоки 1 и 2 выдают содержимое ячеек памяти, адреса которых поданы на входы, и поддерживают его до снятия или изменения адресов.

Пусть ш — число выбранных для сравнения столбцов (ш < n) S - мощ" ность множества; Р„,Р ...,,P u ,Ч,...,q — номера столбцов первого и второго множеств, подлежащих сравнению. Устройство предназначено для вычисления следующих шести (в зависимости от 2) булевых формул:

1583941

1О !

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

Результаты сравнения компонент первой строки по критерию 6 объединяются на элементе ИЛИ 10<. Если хотя бы одна пара компонент первого и второго множеств не удовлетворяет критерию

8g, то на выходе элемента ИЛИ 10 появляется сигнал. В противном случае на его выходе поддерживается нулевой уровень.

Запуск устройства в работу осуществляется импульсом по входу 18.

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

С задержкой, необходимой для обновления содержимого регистра 12, в счетчиках 9 и 11 формируются адреса вторых элементов сравниваемых множеств, в результате чего их коды считываются из блокон 1 и 2 памяти. Если задержки блоков и элементов 1 (2), 3 (4), 6 и !О достаточна для обновления содержимого регистра 12, то элемент 5 задержки может .быть исключен, В дальнейшем устройство работает аналогично. По каждому тактовому импульсу н регистр 12 заносятся результаты сравнения компонент очередных элементов множеств и считываются следующие компоненты множеств. При считывании последних элементов множеств появляется сигнал на дополнительном выходе блока 2 памяти. который останавливает генератор 13 и может быть использован для сигнализации окончания работы.

Задержка его поступления на генератор

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

1.2, Результаты сравнения выдаются на выходы 19. Если на выходе 19 осталась единица, то элементы избранных столбцов удовлетвбряют критерию 8, в противном случае не удовлетворяют.

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

Устройство для сравнения информационных массивов, содержащее два блока памяти, два коммутатора,п блоков сравнения, где и — число компонентов элемента множества, первую группу из (n-1) элементов ИЛИ, дешифратор, первый счетчик, вторую группу элементов

ИЛИ, элемент задержки, причем выходы первого счетчика соецинены с адресными входами первого блока памяти, выходы которого, кроме выхода дополни- тельного разряда, соединены с инфсЕмационными выходами первого коммутМтора, i-я (i = 1, n) группа выходов которого соединена с первой группой ,входов i-го блока сравнения, вторая ( группа входов которого соединена с

i-й группой выходов второго комму-, татора, информационные входы которого соединены с выходами второго блока памяти, кроме выхода дополнительного разряда, входы перного и второго признаков устройства соединены с адресными входами первого и второго коммутаторов, входы первого признака устройства подключены дополнительно к входам дешифратора, j-й выход ко30 торого (j = 1, (n-1) соединен с j-ми входами элементов ИЛИ первой группы с первого по j-й, и-й выход дешифратора соединен с и-ми входами элементов:

ИЛИ первой группы и входом разрешения

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

1583941

Корректор С.Черни

Подписное

Tsyaa 571

Заказ 2256

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

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

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина,101 дои Ы-го элемента И второй группы .вы-; ходы элементов ИЛИ второй группы сое-, динены с входами регистра, выходы ко"

Составитель Е.Иванова

Редактор И.Шулла Техред Л.Сердюкова торого являются выходами устройства.