Устройство для сравнительного анализа п чисел

Устройство для сравнительного анализа п чисел

Иллюстрации

Показать все

Реферат

 

Союз Советских

Социалистическкх

Республик

ОПИ иЗОБР н11736ООО (61) Дополнитель (22) Заявлено 2

G F 7/00 с присоединением заявки №

Государственный комитет

СС С Р но делам изобретений и открыти и (23) Приоритет

1 (53) УДК б 81 . 32 5 . 5 (088. 8) Опубликовано 250580. Бюллетень ¹ 19

Дата опублйкования описания 2505.80

В.И. Рабинович и А.A Чайка (72) Авторы изобретения

Новосибирский электротехнический институт (71) Заявитель (54) УСТРОЙСТВО ДЛЯ СРАВНИТЕЛЬНОГО АНАЛИЗА и ЧИСЕЛ

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

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

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

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

i-ro числа, где i = 1,2,...,n, выход элемента равнозначности каждого канала подключен к информационным входам первого и второ го триггеров того

5 же канала, элементы И, ИЛИ, НЕ, запрета, регистры сдвига (2) .

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

15 части по одной или двум границам.

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

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

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

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

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

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

Устройство содержит и кан алов ан ализа 14,1,...-,1п, каждый из которых состойт из элемента 2 равнозначности, триггеров 3 и 4, элемент И 5, элемент 6 запрета, элемент ИЛИ 7, входные шины 8, 8,..., 8, шины

9-16 управления.

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

nm-разрядных двоичных чисел Х

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

Вспомогательные операции включают маскирование разрядов, раздельную установку в исходное состояние триггеров, перезапись информации триггеров 3 в триггеры 4, дизъюнктинное выполнение операций.

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

При выделении максимального числа в исходное состояние триггеры 3 устанавливают ся сигналом по входу 10, а триггеры 4 — по входу 11. Прк этом на управляющих входах элементов 2

5 ,равнозначности устанавливаются разрешаюшие сигналы. В этом режиме на ши— ны 9, 14 к 16 управления подается сигнал логкческой 1, а на шину 13 управления сигнал логического 0 .

Далее одновременно с первым тактирующим импульсом, поступающим на шину

l5 управления, старшие разряды всех: чисел подаются на первые входы сост нет ствующи х элементов 2 равно зн ачности, сигнал на выходе которых появит ся и случае, если (1 X )Q R- = 1, К к к

I( где Х; — i-ый разряд к-го числа;

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

3 к-го чк сла, образован— ный после окон чани я (i-1) — го такта анализ а;

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

1 -

4 к-го гк сла, о бр аз о ван—

25 ный после окончанкя (i-1 ) -го такта анализа.

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

Х„ = 1. Элемент ИЛИ 7 выявляет, имеет ся ли среди по ступи вши х си гн алон хотя бы один единичный. Очевидно, некоторое число не может быть мак— симальным к подлежит исключению из дальнейшего анализа, е сли среди по ступивших значений старшего разряда всех чисел хотя бы одна единица, а в старшем разряде данного числа нуль, т.е. если сигнал на выходе

40 элемента ИЛИ 7 то число Х подлежит исключению.

Если Р.- = 1, то тот же тактовый импульс через элемент И 5 поступает на входы синхронизации всех триггеров 3, из которых устанавливаются в нулевое состояние только те, на информационных входах которых прк— сутствует сигнал логического 0 .

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

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

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

На следующем такте на первые входы всех элементов раннозначностк поступают значения следующе го по ст ар65 шеству разряда обрабатываемых чи ел

736090 и процесс сравнения продолжает ся ан алогичным образом.

В итоге за и тактов сравнения выявляются максимальные числа, местонахождение которых фиксируется триггером 3, не изменившим исходного состояния. Сравнение может закон5 читься и на первом такте, если среди значений старшего разряда чисел только одно единичное.

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

i-го канала соединен с входной шиной i-го числа, где 1 = 1,2,...,n, выход элемента равнозначности каждого канала подключе. к информационным входам первого и второго триггеров того же канала, элементы И, ИЛИ, запрета, о т л и ч а ю щ ее с я тем, что, с целью расширения функциональных возможностей путем определения экстремальных и отличающихся заданным признаком чисел, разбиением совокупности данных по заданным границам и упорядочения массива, в нем вторые входы элементов равнозначности всех каналов подключены к первой шине управления, входы установки в единичное состояние первых триггеров всех каналов соединены со второй шиной управления, выход первого триггера каждого канала подключен к первому входу установки в нулевое состояние второго триггера и к третьему входу элемента равнозначности того же канала, выход второго триггера соединен с прямым информационным входом втоПоиск минимального числа произво10 дится аналогично, при этом на шину 9 управления подается логический О .

Поиск числа по признаку, частным случаем которого является поиск заданного числа, производится следующим образом.

Допустим производится поиск числа, в 1-ом разряде которого единичное значение, à B g-oM — нулевое и безразлично каково значение остальных 20 разрядов.

В исходное со тояние триггеры

4 и 3 устанавливаются по шинам 10 и 11 управления, На шинах 13 и 16 управления устанавливается сигнал логической 1 . Ha шину 9 управления подается единичный сигнал при поиске чисел больших и равных заданного.

На шину 16 управления поступает синхронно-поразрядно с числами код заданного числа A при поиске чисел

Х À или инверсный код заданного. числа А при поиске чисел Х > А. Таким образом при поиске чисел X P A

К тактирующие импульсы на вход синхронизации триггеров 3 постулают при анализе тех разрядов, где А 1" — Î, а на входы синхронизации триггеров ,.4 — где А.) = 1. Триггеры 3 осуществляют запоминание чисел X >< А, а

3 триггеры 4 — исключение чисел Х < А 40 из дальнейшего анализ а. Три ггер 4 блокируется по прямому информационному входу и подает запрещающий сигнал на соответствующий элемент 2 равнозначности. 45

При поиске чисел Х А, тактирующие импульсы на входы синхронизации триггеров 3 поступают при анализе тех разрядов, где A; = 1, а на входы синхронизации триггеров 4 — где

А = О. Триггеры 3 осуществляют за1 К поминание чисел Х <А, а триггеры 4— исключение чисел Х 7A из дальнейшего анализа.

B итоге триггеры 4, не изменившие своего состояния, определяют местоположение чисел Х А (Х <А) .

Двухкратным повторением операции с подачей соответствующих сигналов на шины управления устройства осуществляется поиск чисел A X B, где A 40 и  — заданные границы части массива, причем В ) A.

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

После проведения соответствующего цикла поиска информация с триггеров 3 переписывается в триггеры

4 по входам установки в единичное состояние, для чего на шину 12 управления подается импульс перезаписи. Затем триггеры 3 устанавливают- ся по шине 10 управления в исходное состояние и цикл сравнения повторяетсяя.

Следовательно, можно производить упорядочение чисел всего массива или подмассива данных по заданному закону (возрастания, убывания, четных, нечетных и другого программного упорядочения) .

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

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

Ф ,В"

f36090

/,г . Р;

7 /

)

1 (1

ЦПИИПИ Заказ 2266/á Тираж 751 Подписное

Филиал ППП Патент, г. Ужгород, ул. Проектная, 4 рого триггера и с четвертым входом элемента равнозначности, выход элемента равнозначности i-го канала подключен к i-ому входу элемента ИЛИ, (i+1) -ый вход которого соединен с третьей шиной управления, а выход— с первым входом элемента И, второй, третий, четвертый входы которого подключены к четвертой, .пятой и шестой шинам управления, выход элемента

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

Источники информации, принятые во внимание при экспертизе, 1. Авторское свидетельство СССР

9478303, кл. G 06 F 7/04, 12,05.72.

2. Авторское свидетельство СССР

Р 521566 кл, G 06 F 7/04, 17.05 74 (прототип).