Устройство для сравнительного анализа п чисел Советский патент 1980 года по МПК G06F7/00 

1

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

Известно устройство для сравнения п двоичных чисел,содержащее п кольцевых регистров сдвига, п схем равнозначности, две п входовые схемы ИЛИ, схему И. Устройство служит для одновременного поразрядного сравнения п чисел 1.

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

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

i-ro числа, где i 1,2;...,п,выход элемента равнозначности каждого ка нала подключен к информационным входам первого и второго триггеров того 5 же канала, элементы И, ИЛИ, НЕ, запрета, регистры сдвига 2 .

Однако количество информадионнопоисковых операций данном устройстве ограничено. Устройство поэволя10 .ет опред.злять только экстремальные числа и числа, отличающи.еся заданным признаком. Множество же поисковых операций определяется, кроме тОго, разбиением массива данных на

15 части по одной или двум границам. Данное устройство не позволяет производить указанные операции.

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

25Поставленная цель достигается

тем, что в устройстве вторые входы элементов равнозначности всех каналов подключены к первой шине управ- . ления, входы установки в е:диничное

30 состояние первых триггеров всех

каналов соединены со второй шиной управления, выход первого триггера каждого канала подключен к пepвo y входу установки в нулевое состояние второго триггера и к третьему входу элемента равнозначности того же канала, выход второго триггера сое;зилён с прямым информационным входом Bjroporo триггера и с четвертым входо элемента равнозначности , выход эле1 ента равнозначности i-ro канала подкраючен к i-ому входу элемента ИЛИ, (1+1)-ый вход которого соединен с третьейшиной управления, а выход - о первым входом элемента И, второй, третий и четвертый входы которого подключены к четвертой, пятой и шест;ой шинам управления, выход элемента И соединен со входами синхронизации г(ервых триггеров всех каналов, информационный вход элемента запрета подключен к-пятой шине управления,а его управляющий вход - к шестой шине управления, выход элемента запрета соединен со входами синхронизации дторых триггеров всех каналов, входы установки в единичное состояние втор1ых триггеров всех каналов анализа . 11одключены к седьмой шине управления вторые входы установки в нулевое сос1 ояние вторых триггеров всех канатов соединены с восьмой шиной управления,

На чертеже представлена функциональная схема,

Устройство содержит п каналов анаЛиза 1, , 12, , . ,, If, каждый из котоЕ ых состоит из элемента 2 равнознач Ности, триггеров 3 и 4, элемент И 5, элемент 6 запрета, элемент ИЛИ 7, входные шины 8 ,8„, , . . ,Вц шины 9-16 управления.

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

„ nm-разрядных двоичных чисел X , X ,,,,,х подаются на входы элементов 2 равнозначности соответствующих каналов одновременно,поразрядно, начиная со старших разрядов. На шины 9-10 и 13-16 управления сигналы подаются в соответствии с видом производимой операции. Множество , функций, реализуемых предлагаемым устройством определяется выбором; и. последовательным выполнением базисных и вспомогательных операций. Байисные операции включают выделение экстремальных из совокупности чисел, поиск чисел по признаку, определение чисел больших (меньших) заданного. Вспомогательные операции включают маскирование разрядов, раздельную Установку в исходное состояние триггеров, перезапись информации триггеров 3 в триггеры 4, дизъюнктивное выполнение операций,

Работа устройства при выполнении ;в отдельности каждой из базисных Операций заключается в следующем.

При выделении максимального числа в исходное состояние триггеры 3 устанавливаются сигналом по входу 10, а триггеры 4 - по входу 11, При этом на управляющих входах элементов 2 .равнозначности устанавливаются разрешающие сигналы. В этом режиме на шины 9, 14 и 16 управления подается

а на шину 13

1

сигнал логической управления сигнал логического О.

Далее одновременно с первым .тактирующим импульсом, поступающим на шину 15 управления, старшие разряды всех; чисел подаются на первые входы соответствующих элементов 2 равнозначности, сигнал на выходе которых появится в случае, если

()QL кД/ ь

где. X,- i-ый разряд к-го числа;

Q - выходной сигнал триггера

3к-го числа, образованный после окончания

(i-l)-ro такта анализа;

R. - выходной сигнал триггера

4к-го числа, образованный после окончания

(i-I)-ro такта анализа. Следовательно, при поиске максимального числа сигнал логической образуется на выходах только тех элементов 2 равнозначности, где 1, Элемент ИЛИ 7 выявляет, имеется ли среди поступивших сигналов хотя бы один единичный. Очевидно, некоторое число не может быть максимальным и подлежит исключению из дальнейшего анализа, если среди поступивших значений старшего разряда всех чисел хотя бы одна единица, а в старшем разряде данного числа нуль, т,е, если сигнал на выходе 0 элемента ИЛИ 7

.1.. ..:(,,l. ..Я-;..-, , . то число X подлежит исключению.

5Если Р 1, то тот же тактовый

импульс через элемент И 5 поступает на входы синхронизации всех триггеров 3, из которых устанавливаются в нулевое состояние только те, на

Q информационных входах которых присутствует сигнал логического О , Следовательно, на управляющие входы элементов равнозначности, соответствующих триггерам 3, изменившим

. свое состояние, поступает сигнал исключения из дальнейшего анализа соответствующих чисел.

Если Р - О, т.е, значение данного разряда всех чисел не равны 1, то тактовый импульс не поступает

0 на входы синхронизации триггеров 3 и состояние, их не изменяется.

На следующем такте на первые входы всех элементов равнозначности поступают значения следующего по стар5 шесгву разряда обрабатываемь-лх чисел и процесс сравнения продолжается ан логичным образом. В итоге за п тактов сравнения вы являются максимальные числа, местонахождение которых фиксируется триггером 3, не изменившим исходног состояния. Сравнение гложет закончиться и на первом такте, если среди значений старшего разряда чисел только одно единичное. Поиск минимального числа произво дится аналогично, при этом на шину Управления подается логический О Поиск числа по признаку, частным случаем которого является поиск заданного числа, производится следующим образом. Допустим производится поиск числ в i-oM разряде которого единичное значение, а в j-ом - нулевое и безразлично каково значение остальных разрядов. В исходное состояние триггеры 4 и 3 устанавливаются по шинам 10 и 11 управления. На шинах 13 и 16 у ,равления устанавливается сигнал лог ческой Ч. На шину 9 управления подается единичный сигнал при поиск чисел больших и равных заданного. На шину 16 управления поступает син хронно-поразрядно с числами код заданного числа А при поиске чисел или инверсный код заданного, числа А при поиске чисел . Таким образом при поиске чисел X тактирующие импульсы на вход синхро низации триггеров 3 поступают при анализе тех разрядов, где Af 0, а на входы синхронизации триггеров ;4 - где А Триггеры 3 осуществляют запоминание чисел , а триггеры 4 - исключение чисел из дальнейшего анализа. Триггер 4 блокируется по прямому информационному входу и подает запрещающий сиг нал на соответствующий элемент 2 ра нозначности. При поиске чисел X $ А, тактирующие импульсы на входы синхронизации триггеров 3 поступают при анали зе тех разрядов, где А; 1, а на входы синхронизации триггеров 4 - г А - 0. Триггеры 3 осуществляют запоминание чисел X А, а триггеры 4 исключение чисел из дальнейшег анализа. В итоге триггеры 4, не Изменивши своего состояния, определяют местоп ложение чисел () . Двухкратным повторением операции подачей соответствующих сигналов на шины управления устройства осуществляется поиск чисел А : Xi В, где А и В - заданные границы части массива, причем , Дизъюнктивное выполнение операций поиска экстремальных чисел,чисел с заданным признаком, с сохранением результатов предыдущих анализов,осуществляется следующим образом. После проведения соответствующего цикла поиска информация с триггеров 3 переписывается в триггеры 4 по входам установки в единичное состояние, для чего на шину 12 управления подается импульс перезаписи. Затем триггеры 3 устанавливаются по шине 10 управления в исходное состояние и цикл сравнения повторяется. Следовательно, можно производить упорядочение чисел всего массива или подмассива данных по заданному sajKOну (возрастания, убывания, четных, нечетных и другого программного упорядочения). Таким образом, устройство на основе совокупности проведения базисных и дополнительных операций позволяет решать множество информа ционно-поисковых задач, например, таких как: определение экстремальных и отличающихся заданным признаком чисел из всего массива или его части, разбиение массива данных на части по одной или двум (верхней |И нижней) заданным границам,определение чисел ближайших больших (меньших) заданного, упорядочение данных массива или его части по заданному закону и др. Формула изобретения Устройство для сравнительного анализа п чисел, содержащее п каналов анализа,каждай из которых состоит из элемента равнозначности и двух триггеров, причем первый вход элементов равнозначности каждоххэ i-ro канала соединен с входной шиной i-ro числа, где i 1,2,,,,,п, выход элемента равнозначности каждого канала подключе.. к информационным входам первого и второго триггеров того же канала, элементы И, ИЛИ, запрета, отличающееся тем, что, с целью расширения функциональных возможностей путем определения экстремальных и отличающихся заданным признаком чисел, разбиением совокупности данных по заданным границам и упорядочения массива, в нем вторые входы элементов равнозначности всех каналов подключены к первой шине управления, входы установки в единичное состояние первых триггеров всех каналов соединены со второй шиной управления, выход первого триггера каждого канала подключен к первому входу установки в нулевое состояние второго триггера и к третьему входу элемента равнозначности того же канала, выход второго триггера соединен с прямым информационным входом второго трихгера и с четвертым входом, элемента равнозначности, выход элемента равнозначности i-ro канала подключен к i-ому входу элемента ИЛИ, С1+1)-ый вход которого соединен с третьей шиной управления, а выход с первым входом элемента И, второй, третий, четвертый входы которого подключены к четвертой, -пятой и шестой шинам управления, выход элемента И соединен со входами синхронизации первых триггеров всехканалов,информационный вход элемента запрета подключен к пятой шине управления, а его управляющий вход - к шестой шине управления, выход элемента запрета соединен со входами синхронизации вторых триггеров всех .лов, входы установки в е,диничное состояние вторых триггеров всех каналов анализа подключены к седьмой шине управлег НИН, вторые входы установки в нулевое состояние вторых триггеров всех каналов соединены с восьмой шиной управления.

Источники информации, Q принятые во внимание при экспертизе ,

1.Авторское свидетельство СССР №478303, кл. G 06 F 7/04, 12.05.72,

2.Авторское свидетельство СССР№ 521566, кл. G 06 F 7/04, 17.05.74 (прототип).

и

/

1/