Устройство для упорядочивания чисел Советский патент 1982 года по МПК G06F7/06 

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

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

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

устройство для упорядочивания чисел, содержащее память для хранения подлежащих сортировке кодов чисел, несколько буферных регистров, каждый из которых обеспечивает запоминание одного кода, несколько с.хем сравнения, каждая из которых служит для сравнения кода, считанного из буферного регистра с кодом, считанным из памяти, и для формирова10ния в каждой схеме сравнения выходных сигналов Больше чем, Меньше чем. В устройстве предусмотрено несколько узлов адресации для хранения адресов кодов в адресной поISследовательности, в которой адреса кодов соответствуют кодам, хранящимся в буферных регистрах. Для подключения буферных регистров к схемам сравнения предусмотрено несколь30ко селекторов, каждый-из которых управляется адресом кода, хранимым в соответствующем узле адресации. Узел передачи состоит из нескольких 39 схем передачи, каждая из которых включается между соответствующим одним узлом адресации с целью селектив ной передачи адресов кодов между узлами адресации при формировании соответствующей схемой сравнения выходного сигнала Больше чем.Узел передачи содержит блок для передачи адреса каждого кода из памяти в любой из узлов адресации, которому соответствует выходной сигнал Больше чем на одном плече, связанной с ним схемой сравнения и сигнал Меньше чем - на другом плече. Указанный узел передачи упорядочивает адресную последовательность адресов кодов. Выходной узел служит для считывания кодов информации из буферных регистров, выбранных селекторами, в установленном порядке адре сов кодов С2 J. Недостатком известного устройстве является низкая производительность, обуславливаемая нерациональными затратами времени на последовательное сравнение кодов упорядочиваемой информации и затратами времени на выполнение операций над адресами кодов. Цель изобретения - повышение быстродействия. Поставленная цель достигается те что в устройство для упорядочивания чисел, содержащее И групп входных элементов И, п входных регистров,п групп элементов И перезаписи, (n-l) Труппу по К в каждой группе схем сравнения, (п-1) группу по k в каждой группе триггеров, блок синхронизации, группу элементов ИЛИ, информационные входы устройства сое динены с информационными входами входных элементов групп, выходы эле ментов И каждой i-ой группы, где 1 1,2,,.., п , подключены к информационным входам -го входного ре гистра, выходы каждого i-ro входно го регистра соединены с информационными входами элементов И перезаписи 1-ой группы, выходы элементов И перезаписи каждой (i + 1 )-ой группы подключены к первым информационным входам схем сравнения i-ой группы, выходы Больше и Равно, меньше каждой J-ой схемы сравнения i-ой группы, где ,2,.,., (n-l) .соединены с входами установки в единичное и ну4левое состояния соответственно j-ro j-ой схемы сравнения ой группы, гдеj 1,2,.,.,( п-i),соединены с входами установки в единичное и нулевое состояния соответственно j-ro триггера i-ой группы, вторые информационные входы каждой j-ой схемы сравнения k-ой группы, где k 1,2,.,., (п-1).подключены к выходам элементов И перезаписи (1-1)-ой группы, введены реверсивные счетчики, элементы задержки, блок памяти, причем прямой выход каждого j-ro триггера первой группы соединен с первым входом j-элемента ИЛИ, инверсный выход первого триггера первой группы подключен к первому входу п-го элемента ИЛИ, инверсные выходы второго, третьего,..., (n-l)-ro триггеров первой группы соединены через первый, второй,..., (п-2)-ой элементы задержки первой группы с вторым, третьим,..., (п-1)-ым входами соотчетствекно п-го элемента ИЛИ, прямой выход каждого j-ro триггера каждой }-ой группы, кроме первой, через j-ый элемент задержки i-ой группы подключен к j-My входу i-ro элемента ИЛИ, инверсный выход каждого j-ro триггера каждой i-ой группы . соединен через (n-i j)-ый элемент задержки с (n-i + j)-biM входом (i-l)-ro элемента ИЛИ, выход каждого f-ro элемента ИЛИ подключен к информационному входу i-ro реверсивного счетчика, выходы каждого i-ro реверсивного счетчика соединены с входами 1-го элемента И-НЕ, выходы каждого 1-го входного регистра подключены к информационным входам выходных элементов -И 1-ой группы, выход каждого i-ro элемента И-НЕ соединен с первым управляющим входом выходных элементов И (1 + 1)-ой группы, а выход п-элемента И-НЕ подключен к первому управляющему входу выходных элементов И первой группы, выходы выходных элементов И групп соединены с входами элементов ИЛИ группы, выходы которых подключены к входам блока памяти, управляющий вход устройства соединен с входом блока синхронизации, первый выход которого подключен к управляющим входам входных элементов И групп, второй выход блока синхронизации соединен сГ управляющими входами элементов И перезаписи групп, третий, четвертый и пятый выходы блока синхронизации подключены к входам управления выходных элементов И групп, реверсивных счетчиков и входных регистров соответственно. 5

Блок синхронизации содержит формирователи импульсов, элементы задержки, триггеры, элементы ИЛИ, И, И-НЕ, счетчик, генератор тактовых импульсов, причем вход блока син- 0 хронизации соединен с входом установки в единичное состояние первого триггера и через первые элемент задержки и формирователь импульсов с входом установки в нулевое состоя- 5 ние первого триггера и входом установки в единичное состояние второго триггера, а через вторые элемент задержки и формирователь им пульсов с входом установки в нулевое состоя- 20 ние второго триггера и через третий элемент задержки и третий формирователь импульсов - с первым входом элемента ИЛИ и с входом четвертого элемента задержки, выход которого 25 через четвертый формирователь импульсов соединен с входом установки в нулевое состояние третьего триггера и с входом запуска генератора тактовых импульсов, выход которого 30 соединен с первым входом элемента И, с входом счетчика и с вторым вхоом элемента ИЛИ, выход которого одключен к входу установки в единичное состояние третьего триггера, jj нверсный выход которого соединен вторым входом элемента И, выходы метчика подключены к входам элеента И-НЕ, выход которого соединен входом останова генератора тактовых 4о импульсов, прямые выходы первого, второго и третьего триггеров, выход элемента И подключены к первому, второму, третьему и четвертому выходам блока, вход блока через пятый формировтель соединен с пятым выходом блока.

На фиг,1 представлена блок-схема устройства; на фиг.2 - блок-схема узла синхронизации.

Устройство содержит группы входных элементов И 1., l.... t IH входные регистры 2, 2,..., 2ц ,

группы элементов И Зт. 3

перезаписи.группы схем Ц, Ц,,,. 4у, сравнения, группу триггеров 5. 5a.f..., , элементы Ц, ..,, 6vvi задержки, группы элементов ИЛИ 7/|i7i I... 7п, реверсивные счетчики г

8,8, ... ,8,, элементы И-НЕ 9 , 9, группы элементов И 10., 10, ...10, группу элементов ИЛИ 11, бло 12 памяти, блок13 синхронизации.

Блок 13 синхронизации содержит элементы задержки,формирователи 18-22, триггеры , генерато 2б тактовых импульсов, счетчик 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.1-7.4 выдают импульсы с единичных и нулевы выходов на входы реверсивных счетчиков 8.1-8.4. Для обеспечания го срабатывания триггеров реверсивного счетчика к входам эт ементов ИЛИ 7..4, начиная со второго подключаются элементы 6ч1-6.В дедержки.

Число импульсов, записанное в реверсивном счетчике, является кодом приоритета К; числа / массива А. Таким образом, после сравнений кодов чисел упорядочивания массива в реверсивных счетчиках 8.1-8.4 записаны коды приоритетов упорядочиваемых , причем код приоритета наибольшего числа равен нулю. В связи с этим на единичных выходах триггеров реверсивного сметчика, хранящего код приоритета наибольшего числа,будут нулевые потенциалы,а на выходе соответствующего элемента И-НЕ единичный потенциал, раз решающий по второму входу узла элементов И третьей группы 10.1-10. выдачу кода наибольшего числа. Для обеспечения устойчивого последовательного срабатывания тригге ров реверсивных счетчиков и формиро вания кодов приоритетов между концом синхроимпульса СИ2 и началом первого синхроимпульса СИЗ необходима задержка, длительность которой может быть определена по следую щей формуле: , зЛлм - тр. где tX - время срабатывания триггера реверсивного счетчика; время распространения сигна в элементе ИЛИ; число упорядочиваемых кодов массива. . Выдача кодов наибольшего числа осуществляется с выхода «хютветствующего входного регистра через узел элементов И третьей группы, на втором входе которого есть разрешающий потенциал и на. первый вход которого с блока 13 синхронизации поступает синхроимпульс СИЗ. Код наибольшего числа через узел элемен тов ИЛИ 11 записывается в первый регистр 12 стековой памяти. По окончании синхроимпульса СИЗ . в блоке 13 синхронизации формируется синхроимпульс СИ, который с пятого выхода блока синхронизации поступает, на реверсивные входы счет чиков B-I-B., уменьшая содержимое счетчиков на единицу. Таким образом, для числа, следую щего за наибольшим, код приоритета становится равным нулю и с выхода соответствующего элемента И-НЕ на вход элемента И третьей группы пода ется разрешающий потенциал. При поступлении синхроимпульса СИЗ сле дующий код числа записывается в пер вый регистр блока 12 памяти, сЬдержимое которого переписывается во второй регистр и т.д. Число тактов выдачи подсчитывает ся в блоке 13 синхронизации счетчи78ком 27. По окончании считывания кодов содержимое счетчика 27 становится равным нулю, разрешая формирование сигнала, по которому останавливается генератор тактовых импульсов. При наличии в массиве информации двух равных чисел на выходе соответствующей схемы сравнения си|- нал отсутствует, поэтому триггер знака находится в том состоянии, в котором он находился после окончания переходных процессов. В этом случае очередность выдачи кодов чисел определяется текущим состоянием данного триггера знака. Оценка технико-экономической эффективности изобретения проводилась методом математического моделирования с последующей программной реалиэацией модели на ЗВМ БЭСМ-6. Анализ показывает, что эффективность предлагаемого устройства упорядочивания зависит от объема упорядочиваемого массива и может составлять от 5 до З. 10 . Применение предлагаемого изобретения наиболее эффективно для 100. Формула изобретения 1. Устройство для упорядочивания чисел, содержащее и групп входных элементов И, И входных регистров, групп элементов И перезаписи, (и -1) группу по К в каждой группе схем срайнения, См О группу по К а каждой группе триггера, блок синхронизации, группу элементов ИЛИ, информационные входы устройства соединены с информационными входами входных элементов групп, выходы элементов И каждой группы,где 1,2 Ь, подключены к информационным дам -I-го входного регистра, выходы каждого 4-го входного регистра соединены с и формзционными входами элементов И перезаписи группы, выходы элементов И перезаписи каждой (1-1)-й группы подклйчень к первым информационным входам схем сравнения i-й группы, выходы Болбше и Равно, меньше каждой j-Ьй схемы сравнения t-ой группы, где j 1,2,,.., (и -i), соединены с входами установки в единичное и нулевое состояния соответственно j-ro триггера -i-ой группы вторые информационные входы каждой j-ой схемы сравнения , К-ой группы. где К 1,2,..., (И-1, подключены к выходам элементов И перезаписи (1 + 1 )-ой группы, отличающе еся тем, что, с целью повышения быстродействия,в него введены реверсивные счетчики, элементы И-НЕ, эле менты задержки, блок памяти, причем прямой выход каждого У-го триггера первой группы соединен с первым вхо дом j -го элемента ИЛИ, инверсный выход первого триггера первой группы подключен к первому входу И-го элемента ИЛИ, инверсные выходы второго, третьего,..., (и -1)-го триггеров первой группы соединены через первый, второй,..., (и-2j-ой элемен ты задержки первой группы с вторым, третьим,..., ( И -1)-ым входами соответственно И-го элемента ИЛИ, прямой выход каждого J-ro триггера каждой 1-ой группы, кроме первой, через j-ый элемент задержки 1-ой группы подключен к j-му входу -i-rc элемента ИЛИ, инверсный выход каждого j-ro триггера каждой Н-рй группы соединен через (и - 1 +J ) -ый элемент задержки с (и - i + f -ым входом Ci-O-ro элемента ИЛИ, выход каждого 4-го элемента ИЛИ подключе к информационному входу i -го ревер сивного счетчика,выходы каждого го реверсивного счетчика соединены с входами -V-ro элемента И-НЕ, выходы каждого 1-го входного регистра подключены к информационным входам выходных элементов И } -ой группы, выход каждого -i -го элемент И-ИЕ соединен с первым управляющим входом выходных элементов И ., (i -f 1)-ой группы, а выход и-го элемента И-НЕ подключен к первому управляющему входу выходных элементов И первой группы, выходы выходны элементов И групп соединены с входами элементов ИЛИ группы,выходы которых подключены к входам блока памяти, управляющий вход устройства соединен,с входом «элока синхронизации, первый выход которого подключен к управляющим входам входных элемент9в И групп, второй выход бло ка синхронизации соединен с управляющими входами элементов И перезаписи групп, третий, четвертый и пяый выходы блока синхронизации по ключены к входам управления выходных элементов И групп; реверсивных счетчиков и входных регистров соответственно. 2. Устройство по п.1, о т л и чающееся тем, что блок синхронизации содержит формирователи импульсов, элементы задержки, три1- геры, элементы ИЛИ, И, И-НЕ, счетчик, генератор тактовых импульсов, причем вход блока синхронизации соединен с входом установки в единичное состояние первого триггера и через первые элемент и формирователь импульсов - с входом установки в нулевое состояние первого триггера и входом установки в единичное состояние второго триггера , а через вторые элемент задержки и формирователь импульсов - с входом установки а нулевое состояние второго триггера и через третий элемент задержки и третий формирователь импульсов - с первым входом элемента ИЛИ и с входом четвертого элемента задержки, выход которого через четвертый формирователь импульсов соединен с входом установки в нулевое состояние третьего триггера и с входом запуска гв нератора тактовых импульсов, выход которого соединен с первым входом элемента И, с входом счетчика и с вторым входом элемента ИЛИ, выхо/:; которого подключен к входу установки в единичное состояние третьего триггера, инверсный выход которого соединен с вторым входом элемента И, 9ЫХОДЫ счетчика подключены к входам элемента И-НЕ, выход которого соединен с входом останова генератора тактовых импульсов, прямые выходы первого, второго и третьего триггеров, выход элемента И подключены к первому, второму, третьему и четвертому выходам блока, вход блока через пятый формирователь coeдикo с пятым выходом блока. Источники информации, принятые во внимание при экспертизе 1.Авторское свидетельство СССР f 6918А7. кл. G Об F 7/02, 1977, 2.Патент ClilA К 3931612, кл. G Об F 7/02, опублих. 1976 (прототип) .

МУ