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

 

изобретеняя.В.Сави Ф

-г;

41:. !, с..

1 (7!) Заявятель (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧИВАНИЯ ЧИСЕЛ

l 0

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

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

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

Наиболее близким техническим решением к предлагаемому явЛяетСя устройство для упорядочивания чисел,содержащее память для хранения подлежащих сортировке кодов чисел, несколько буферных регистров, каждый из которых обеспечивает запоми5 нание одного кода, несколько схем сравнения, каждая иэ которых служит для сравнения кода, считанного из буферного регистра с кодом, счи1О таиным иэ памяти, и для формирования в каждой схеме сравнения выходных сигналов "Больше чем", "Иеньше чем". В устройстве предусмотрено несколько узлов адресации для храlS нения адресов кодов в адресной последовательности, в которой адреса кодов соответствуют кодам, хранящимся в буферных регистрах. Для подключения буферных регистров к схемам сравнения предусмотрено несколько селекторов, каждый из которых управляется адресом кода, хранимым в соответствующем узле адресации.

Узел передачи состоит иэ нескольких

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

"Больше чем" на одном плече, связанной с ним схемой сравнения и сигнал "Меньше чем" - на другом плече.

Указанный узел передачи упорядочивает адресную последовательность адресов кодов. Выходной узел служит для считывания кодов информации из буферных регистров, выбранных селекторами, в установленном порядке адресов кодов (.2 ).

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

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

Поставленная цель достигается тем, что в устройство для упорядочивания чисел, содержащее И групп входных элементов И, и входных регистров,п групп элементов И перезаписи, (n"1) группу no g a каждой rpynne схем сравнения, (п-1) группу по k в каждой группе триггеров, блок синхронизации, группу элементов ИЛИ, информационные входы устройства соединены с информационными входами входных элементов групп, выходы элементов И каждой i"îé группы, где i,2...,, n, подключены к инфор-, мационным входам 1-ro входного регистра, выходы каждого i-ro входного регистра соединены с информационными входами элементов И перезаписи 1-ой группы, выходы элементов И перезаписи каждой (1+1)-ой группы подключены к первым информационным входам схем сравнения i-ой группы, выходы "Больше" и "Равно", меньше "каждой J-ой схемы сравнения i-ой группы, где j=1,2,..., (n-i),ñîåäèíåíû с входами установки в единичное и ну5 о

25 зо

4S

55 левое состояния соответственно j-го

lj""ой схемы сравнения i-ой группы, где j =1,2,...,(n-i),ñoåäèíåíû с входами установки в единичное и нулевое состояния соответственно j-ro триггера i-ой группы, вторые информационные входы каждой j-ой схемы сравнения k-ой группы, где — 1,2,..., (n-l),ïîäêëþ÷åíû к выходам элементов И перезаписи (i-1)-ой группы, введены реверсивные счетчики, элементы задержки, блок памяти, причем прямой выход каждого j--го триггера первой группы соединен с первым входом j-элемента ИЛИ, инверсный выход первого триггера первой группы подключен к первому входу

n"""ro элемента ИЛИ, инверсные выходы второго, третьего,..., (и-1)-ro триггеров первой группы соединены через первый, второй,..., (n-2) -ой элементы задержки первой группы с вторым, третьим,..., (и-1)-ым входами соответственно п ãо элемента ИЛИ, прямой выход каждого j --ro триггера каждой 1-ой группы, кроме первой, через j -ый элемент задержки i-ой группы подключен к j-му входу i ãî элемента ИЛИ, инверсный выход каждого

j-ro триггера каждой i-ой группы соединен через (и-1 + j)-ый элемент задержки с (n-i + J)-ым входом (i-1)-го элемента ИЛИ, выход каждого

i-го элемента ИЛИ подключен к информационному входу I-ro реверсивного счетчика, выходы каждого i-ro реверсивного счетчика соединены с входами 1-го элемента И-НЕ, выходы каждого i-го входного регистра подключены к информационным входам выходных элементов И i-Ой группы, выход каждого i-го элемента И-НЕ соединен с первым управляющим входом выходных элементов И (i + 1)-ой группы, а выход и-элемента И-НЕ подключен к первому управляющему входу выходных элементов И первой группы, выходы выходных элементов И групп соединены с входами элементов ИЛИ группы, выходы которых подключены к входам блока памяти, управляющий вход устройства соединен с входом блока синхронизации, первый выход которого подключен к управляющим входам входных элементов И групп, второй выход блока синхронизации соединен с управляющими входами элементов И перезаписи групп, тре9324 тий, четвертый и пятый выходы блока синхронизации подключены к входам управления выходных элементов И групп, реверсивных счетчиков и входных регистров соответственно. S

Блок синхронизации содержит формирователи импульсов, элементы задержки, триггеры, элементы ИЛИ, И, И-НЕ,.счетчик, генератор тактовых импульсов., причем вход блока синхронизации соединен с входом установки в единичное состояние первого триггера и через первые элемент задержки и формирователь импульсовс входом установки в нулевое состояние первого триггера и входом установки в единичное состояние второго триггера, а через вторые элемент задержки и формирователь импульсов " с входом установки в нулевое состоя- Зе ние второго триггера и через третий элемент задержки и третий формирователь импульсов - с первым входом элемента ИЛИ и с входом четвертого элемента задержки, выход которого 25 через четвертый формирователь импульсов соединен с входом установки в нулевое состояние третьего триг" гера и с входом запуска генератора тактовых импульсов, выход которого щ соединен с первым входом элемента

И, с входом счетчика и с вторым входом элемента ИЛИ, выход которого подключен к входу установки в единичное состояние третьего триггера, инверсный выход которого соединен с вторым входом элемента И, выходы счетчика подключены к входам элемента И-НЕ, выход которого соединен с входом останова генератора тактовых импульсов, прямые выходы первого второго и третьего триггеров, выход элемента И подключены к первому, второму, третьему и четвертому выходам блока, вход блока через пятый формировтель соединен с пятым выходом блока, На фиг,1 представлена блок-схема устройства; на фиг.2 - блок-схема узла синхронизации.

Устроиство содержит группы вход$0 ных элементов И 1, 1,..., входные регистры 2, 2 ...,, 2и, группы элементов И 3.1, 3,..., 3и перезаписи, группы схем 4, 4,..., 4 « сравнения, группу триггеров 5,, И

51 »1, элементы 6, 6,..., 6и задержки, группы элементов ИЛИ

7,1,7,...,7и, реверсивные счетчики

87 6

8,8,...,8и, элементы И-НЕ 91, 9, ...,9и, группы элементов И 10Ä, 1О, ...10„, группу элементов ИЛИ 11, блоь

12 памяти, блок 13 синхронизации.

Блок 13 синхронизации содержит элементы 14-17 задержки, формирователи 18-22, триггеры 23-25, генератор

26 тактовых импульсов, счетчик 27, элемент И 28, элемент ИЛИ 29, элемент И-НЕ 30.

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

Работа начинается по сигналу

"Пуск", поступающему по кодовой шине управления на вход блока 13 синхронизации. По этому сигналу усилителем-формирователем 19 формируется сигнал "УстО", который поступает на нулевые входы регистров 2,1-2.4 и обнуляет их. По окончании сигнала

"УстО" в блоке 13 синхронизации формируется синхроимпульс "СИ1", посту .пающий на первые входы элементов И первой группы 1.1"1.4, разрешает запись кодов информации во входные регистры 2.1-2..4.

По окончании записи кодов чисел упорядочиваемого массива из блока 13 синхронизации на первые входы узлов элементов И второй группы 3,1-3.4 поступает синхроимпульс тСИ2", разрешающий одновременную выдачу кодов чисел.упорядочиваемого массива на входы соответствующих схем 4; 1-4.6 сравнения. Схемы сравнения представляют собой узлы сравнения по старшему разряду последовательного типа, поэтому длительность синхроимпульса

"СИ2" должна обеспечить прохождение сигнала через элемент И, вхему сраяне ия и триггер знака. Триггеры 5.15.6 знака обеспечивают запоминание и хранение знака результата сравне- . ния и через элементы ИЛИ 7. -7.4 выдают импульсы с единичных и нулевых выходов на входы реверсивных счетчиков 8.1-8,4. Для обеспечения ч тЪо- го срабатывания триггеров реверсивного счетчика к входам элементов

ИЛИ 7.1-7.4, начиная со второго, под. ключгются элементы 6..1-6.8 задерж-. ки.

Число импульсов, записанное в ре- версивном счетчике, явгяется кодом приоритета Н исла массива А.

Таким образом, после сравнения кодов чисел упорядочивания массива в реверсивных счетчиках 8,1-8.4 записа.с ны коды приоритетов упорядочиваемых ком 27, По окончании считывания ко" дов содержимое счетчика 27 становится равным нулю, разрешая формирование сигнала, по которому останавливается генератор тактовых импульсов. При наличии в массиве информации двух равных чисел на выходе соответствующей схемы сравнения сигнал отсутс1 вует, поэтому триггер знака находится в том состоянии, в котором он находился после окончания переходных процессов. В этом случае очередность выдачи кодов чисел определяется текущим состоянием данного триггера знака.

Оценка технико-экономической эффективности изобретения проводилась методом математического моделирования с последующей программной реализацией модели на ЭВИ БЭСМ-б.

Анализ показывает, что эффективность предлагаемого устройства упорядочивания .зависит от объема упорядочиваемого массива и может составлять от 5 до 3,74 10 . Применение предлагаемого изобретения наиболее эффективно для 20<и <100.

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

1. Устройство для упорядочивания чисел, содержащее И групп входных элементов И, И входных регистров, групп элементов И перезаписи, (И -1) группу по К в каждой группе схем сравнения, (И -1) группу по k в каждой группе триггера, блок синхронизации, группу элементов ИЛИ, информационные входы устройства соединены с информационными входами входных элементов групп, выходы элементов И каждой 4-й группы,где 1,2,..., Ь, подключены к информационным вхо дам -го .входного регистра, выходы каждого 4-го входного регистра соединены с и формационными входами элементов И перезаписи 4 -й группы, выходы элементов И перезаписи каждой (i"1)"é группы подключены к первым информационным входам схем сравнения

4 «й группы, выходы "Больше" и Равно, меньше" каждой $-ои схемы сравнения

1-ой группы, где 1 = 1,2,...,(p -1 ), соединены с входами установки в единичное и нулевое состояния соответственно )-ro триггера -ой группы вторые информационные входы каждой

$-o схемы сравнения, K-ой группы, 7 932487 8 чисел, причем код приоритета наибольшего числа равен нулю. В связи с этим на единичных выходах тригге" ров реверсивного счетчика, хранящего код приоритета наибольшего 5 числа, будут нулевые потенциалы,а на выходе соответствующего элемента И"НЕ единичный потенциал, разрешающий по второму входу узла элементов И третьей группы 10.1-10.4 14 выдачу кода наибольшего числа.

Для обеспечения устойчивого последовательного срабатывания триггеров реверсивных счетчиков и формирования кодов приоритетов между концом синхроимпульса "СИ2" и началом первого синхроимпульса "СИ3" необ" ходима задержка, длительность кото" рой может быть определена по следующей формуле: 20 = „,„+(и-йИ:, где С " время срабатывания триггера реверсивного счетчика; Г„ я- время распространения сигнала И в элементе ИЛИ; и - число упорядочиваемых кодов массива.

Выдача кодов наибольшего числа осуществляется с выхода ооответ", 3O ствующего входного регистра через узел элементов И третьей группы, на втором входе которого есть разрешающий потенциал и на. первый вход которого с блока 13 синхронизации поступает синхроимпульс "СИ3". Код наибольшего числа через узел элементов ИЛИ 11 записывается в первый регистр 12 стековой памяти.

По окончании синхроимпульса "СИ3" в блоке 13 синхронизации формируется синхроимпульс "СИ4", который с пятого выхода блока синхронизации поступает на оеверсивные входы счетчиков 8.1"8.4, уменьшая содержимое счетчиков на единицу.

Таким образом, для числа, следующего за наибольшим, код приоритета становится равным нулю и с выхода соответствующего элемента И-НЕ на вход элемента И третьей группы подается разрешающий потенциал. При поступлении синхроимпульса "СИ3" следующий код числа записывается в первый регистр блока 12 памяти, сЬдер5$ жимое которого переписывается во второй регистр и т.д.

Число тактов выдачи подсчитывается в блоке 13 синхронизации счетчи32487 10 ключены к входам управления выходных эгементов И rpynn, реверсивных счетчиков и входных регистров соответственно, 2. Устройство по п.1, о т л ич а ю щ е е с я тем, что блок синхронизации содержит формирователи импульсов, элементы задержки, триггеры, элементы ИЛИ, И, И-НЕ, счет10 чик, генератор тактовых импульсов, причем вход блока синхронизации соединен с входом установки s единичное состояние первого триггера и через первые элемент и формирователь им"

1S пульсов - с входом установки в нулевое состояние первого триггера и входом установки в единичное состояние второго триггера, а через вторые элемент задержки и формирователь им" в .пульсов - с входом установки в ну" левое состояние второго триггера и через третий элемент задержки и третий формирователь импульсов - с первым входом элемента ИЛИ и с входом ру четвертого элемента задержки, выход которого через четвертый формирователь импульсов соединен с входом установки в нулевое состояние третьего триггера и с входом запуска геуЕ нератора тактовых импульсов, выход которого соединен с первым входом элемента И, с входом счетчика и с вторым входом элемента ИЛИ, выход которого подключен к входу установки в единичное состояние тРетьего триггера, инверсный выход которого соединен с вторым входом элемента И, выходы счетчика подключены к входам элемента И-НЕ, выход которого соединен с входом останова генератора тактовых импульсов, прямые выходы первого, второго и третьего триггеЬ ров, выход элемента И подключены к первому, второму, третьему и четв"ртому выходам блока, вход блока чер -з пятый формирователь соеди з.. с пятым выходом блока.

I. где 1 = 1,2..., (И-1), подключены к выходам элементов И перезаписи (1+ 1)-ой группы, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия,в него введены реверсивные счетчики, элементы И-НЕ, элементы задержки, блок памяти, причем прямой выход каждого у -ro триггера первой группы соединен с первым вхо" дом g -га элемента ИЛИ, инверсный . выход первого триггера первой группы подключен к первому входу И-го элемента ИЛИ, инверсные выходы второго, третьего,..., (И -1)-го триггеров первой группы соединены через первый, второй,..., (И-2 f-ой элементы задержки первой группы с вторым, третьим,..., (И -1)-ым входами соответственно М-го элемента ИЛИ, прямой выход каждого g -ro триггера каждой 1-ой группы, кроме первой через 1 -ый элемент задержки 1-ой группы подключен к 1-му входу 1--ro элемента ИЛИ, инверсный выход каждого $-го триггера каждой 1-ой группы соединен через (и - 1 + 1 ) -ый элемент задержки с (И - 1 + g f -ым входом И-1)-го элемента ИЛИ, выход каждого 4-ro элемента ИЛИ подключен к информационному входу 1 "го реверсивного счетчика, выходы каждого

3-го реверсивного счетчика соединеI ны с входами л-ro элЪмента И"МЕ, выходы каждого 1-ro входного регистра подключены к информационным входам выходных элементов И 1-ой группы, выход каждого 1 -ro элемента

И-НЕ соединен с первым управляющим входом выходных элементов И (i + 1у-ой группы, а выход p"го элемента И-НЕ подключен к первому управляющему входу выходных элемен" тов И первой группы, выходы выходных . элементов И групп соединены с вхо" дами элементов ИЛИ группы, выходы которых подключены к входам блока памяти, управляющий вход устройства соединен,с входом Ьлока синхронизации, первый выход которого подключен к управляющим входам входных элементов И групп, второй выход блока синхронизации соединен с управ.ляющими входами элементов И перезаписи групп, третий, четвертый и пя-ый выходы блока синхронизации подИсточники информации, принятые во внимание при экспертизе

l. Авторское свидетельство CRAP

И 691847, кл. G 06 l. 7/02, )977, 2. Патент СВЙ 3931612, кл. 6 06 F 7/02, опублик. 1976 (opo"

1 тотип>, 932487

Составитель В.белкин

Редактор E,Ïàïï Техред И. РейвесКорректор С.бекмар

Заказ 3785/69 Тираж 732 Подписное

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

133035 Москва, N"35, Рауаскав наб., д, 4/5 филиал ППП "Патент", r. Ужгород, ул. Проектная,- 4