Устройство для сравнения информационных массивов Советский патент 1990 года по МПК G06F17/27 G06F7/02 

3158

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

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

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

Устройство содержит блоки 1 и 2 памяти, коммутатора 3 и 4, элемент 5 задержки, блоки 6,- 6П сравнения, элементы ИЛИ 7, - 7h-i первой группы, дешифратора 8, счетчик 9, элементы ИЛИ 10, - 10t- второй группы, счетчик 11, регистр 12, генератор 13 импульсов, группы 14 и 15 входов признаков, группы 16 и 17 адресных входов, вход 18 запуска и выходы 19),- 19. В качестве коммутаторов 3 и 4 может быть использовано многоканальное устройство для редактирования, которое выделяет по заданным признакам компоненты входного кода и выдает их на выход, сдвигая избранные компоненты к место- положению первой компоненты, исключая тем самым образовавшиеся промежутки., блок 6. сравнения осуществляет проверку кодов, поданных на его информационные входы, на принадлежность к следующим отношениям сравнения: j, 7s, f, , 4, . Он выдает сигнал на своем 1-м (,...,6) выходе в том случае, когда поданные на его входы коды не принадлежат Ј-му отношению сравнения и присутствует сигнал на , его управляющем входе. Перенумеровать перечисленные отношения можно в любом порядке.

Дешифратор 8 выдает сигнал на i-м выходе, если в коде на его п входах присутствует i единиц. Он может быть получен на базе стандартного дешифратора путем объединения по ИЛИ выходов, соответствующих вход- ным комбинациям, содержащим одинакового число единиц. Блоки 1 и 2 памяти хранят элементы сравниваемых множеств. Элемент множества представляет СОбОЙ СТРОКУ ТабЛИЦЫ,

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

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

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

Л ( А (ар еь, ))

г Ь( Е Ч

Q 5 0 5 0

о 5 Q

е

5

где a pt - Pt -я компонента r-й строки первого множества;

bo - компонента r-й строки второго множества;

0g - Eg отношение сравнения из множества ,,,,

}

т.е. устройство сравнивает соответствующие избранные компоненты одноименных строк по шести отношениям, объединяя результаты в строках и столбцах по И. Каждый из п компонент соответствует по одному входу из групп 14 и 15.

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

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

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

it

и b

If

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

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

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

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

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

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

ды которого, кроме выхода дополни1

тельного разряда, соединены с инфор-

5 мациониыми выходами первого коммута8

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

сравнения n-го блока сравнения, выход j-ro элемента ИЛИ группы соединен с входом разрешения сравнения j-ro блока сравнения, первый выход j-ro блока сравнения соединен с j-м входом

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

являются адресными входами первой и второй групп устройства, выходы разрядов которого соединены с адресными входами второго блока памяти, выход дополнительного разряда,которого соединен с входом останова генератора импульсов, вход запуска которого соединен с входом запуска устройства, k-й выход (, 6) i-rp блока сравнения соединен с i-м вхо

715839418

дон k-го элемента И второй группы, вы- торого являются выходами устрой- ходы элементов ИЛИ второй группы сое- ства.

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

динены с входами регистра выходы ко