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

(7) Заявятель тФ ЛЯ УПОРЯДОЧИВАНИЯ Ч 54) УСТРОЙС авления ход каж.с сонтов И ел. Наиболее близкиением к предлагае ехницеск т м Йзобретение относится к автоматике и вычислительной технике, можетиспользоваться в устройствах обработки цифровой информации и дискрет.ной автоматики.Известно устройство для сравнения. чисел, содержащее набор узлов сравнения,элементы ИЛИ, элемент И, элементы И блокировки признаков "Иеньше"и "Большем причем первый выходкаждого узла сравнения соединен ссоответствующим входом элемента И,входы узлов сравнения подключенык входным шинам, а входы упрк шине управления, первый выдого узла сравнения соединенответствующими входами элемеблокировки признаков 1,Недостатком данного устройстваявляется возможность решения задачи упорядочивания произвольных ци устроиство для упорядочивания чисел,содержащее память для храненияподлежащих сортировке кодов чисел,несколько буферных регистров каждый из которых обеспечивает запоминание одного кода, несколько схемсравнения, каждая иэ которых служитдля сравнения кода, считанного избуферного регистра с кодом, считанным иэ памяти, и для Формирования в каждой схеме сравнения выходных сигналов "Больше чем", Иеньше цем". В устройстве предусмотренонесколько узлов адресации для хранения адресов кодов в адресной последовательности, в которой адресакодов соответствуют кодам, хранящимся в буферных регистрах. Дляподключения буферных регистров к схемам сравнения предусмотрено несколько селекторов, каждый из которыхуправляется адресом кода, хранимымв соответствующем узле адресации.Узел передачи состоит иэ несколькихсхем передачи, каждая из которых включается между соответствующим одним узлом адресации с целью селективной передачи адресов кодов между узлами адресации при формировании соответствующей схемой сравнения выходного сигнала "Больше чем".Узел передачи содержит блок для передачи адреса каждого кода из памяти в любой из узлов адресации, которому соответствует выходной сигнал "Больше чем" на одном плече, связанной с ним схемой сравнения и сигнал "Меньше чем" - на другом плече, Указанный узел передачи упорядочивает адресную последовательность адресов кодов. Выходной узел служит для считывания кодов информации из буферных регистров, выбранных селекторами, в установленном порядке адресов кодов 2 3.Недостатком известного устройства является низкая производительность обуславливаемая нерациональными затратами времени на последовательное сравнение кодов упорядочиваемой информации и затратами времени на выполнение операций над адресами кодов. Цель изобретения - повышение быстродействия.Поставленная цель достигается тем,что в устройство для упорядочивания чисел, содержащее И групп входныхэлементов И, и входных регистров,пгрупп элементов И перезаписи, (и) группу по К в каждой группе схемсравнения, (и) группу по к в каждой группе триггеров, блок синхронизации, группу элементов ИЛИ, информационные входы устройства соединены с информационными входамивходных элементов групп, выходы элементов И каждой 1-ой группы, где 1= 1,2 и , подключены к инфор", мационным входам 1-го входного регистра, выходы каждого 1-го входного регистра соединены с информационными входами элементов И перезаписи 1"ой группы, выходы элементов И перезаписи каждой (1+1)-ой группы подключены к первым информационным входам схем срав" нения 1-ой группы, выходы "Боль. ше" и "Равно", меньше "каждой )-ой схемы сравнения 1-ой группы, где 1=1,2.(п),соединены с входами установки в единичное и ну левое состояния соответственно )-гоД"ой схемы сравнения 1-ой группы,5 0 15 20 25 30 35 40 45 50 55 где 3 =1,2( п-),соединены с входами установки в единичное и нулевое состояния соответственно )"го триггера -ой группы, вторые информационные входы каждой )-ой схемы сравнения -ой группы, где - 1,2,(п),подключены к выходам элементов И перезаписи (1-1)-ой группы, введены реверсивные счетчики, элементы задержки, блок памяти, причем прямой выход каждого 1-го триггера первой группы соединен с первым входом )-элемента ИЛИ, инверсный выход первого триггера первой группы подключен к первому входу и"го элемента ИЛИ, инверсные выходы второго, третьего (и)-го триггеров первой группы соединены через первый, второй (и) -ой элементы задержки первой группы с вторым, третьим ., (и)-ым входами соответственно и-го элемента ИЛИ, прямой выход каждого )-го триггера каж- . дой 1-ой группы, кроме первой, через-ый элемент задержки 1-ой группы подключен к -му входу 1-го элемента ИЛИ, инверсный выход каждого 1-го триггера каждой 1-ой группы соединен через (и+ )-ый элемент задержки с (и+ -ым входом (1-1)-го элемента ИЛИ, выход каждого 1-го элемента ИЛИ подключен к информационному входу 1-го реверсивно. го счетчика, выходы каждого 1-го реверсивного счетчика соединены с входами 1-го элемента И-НЕ, выходыкаждого 1-го входного регистра подключены к информационным входам выходных элементов И 1-ой группы, выход каждого 1-го элемента И-НЕ соединен с евым управляющим входом выходных элементов И (1 + 1)-ой группы, а выход и-элемента И-НЕ подключен к первому управляющему входу выходных элементов И первой группы, выходы выходных элементов И групп соединены с входами элементов ИЛИ группы, выходы которых подключены к входам блока памяти, управляющий вход устройства соединен с входом блока синхронизации, первый выход которого подключен к управляющим входам входных элементов И групп, второй выход блока синхронизации соединен с управляющими входами элементов И перезаписи групп, тре9324тий, четвертый и пятый выходы блока синхронизации подключены к входамуправления выходных элементов Игрупп, реверсивных счетчиков ивходных регистров соответственно. %Блок синхронизации содержит формирователи импульсов, элементы задержки, триггеры, элементы ИЛИ, И,И-НЕ, счетчик, генератор тактовыхимпульсов., причем вход блока синхронизации соединен с входом установки в единичное состояние первоготриггера и через первые элемент задержки и формирователь импульсов "с входом установки в нулевое состояние первого триггера и входом установки в единичное состояние второготриггера, а через вторые элементзадержки и формирователь импульсов "с входом установки в нулевое состояние второго триггера и через третийэлемент задержки и третий формирователь импульсов - с первым входомэлемента ИЛИ и с входом четвертогоэлемента задержки, выход которого 25через четвертый формирователь импульсов соединен с входом установки в нулевое состояние третьего триг"гера и с входом запуска генераторатактовых импульсов, выход которого Звсоединен с первым входом элементаИ, с входом счетчика и с вторым входом элемента ИЛИ, выход которогоподключен к входу установки в единичное состояние третьего триггера,инверсный выход которого соединенс вторым входом элемента И, выходысчетчика подключены к входам элемента И-НЕ, выход которого соединенс входом останова генератора тактовых оимпульсов, прямые выходы первого,второго и третьего триггеров, выход элемента И подключены к первому, второму, третьему и четвертомувыходам блока, вход блока через пятыйформировтель соединен с пятым выходом блока,На фиг,1 представлена блок-схемаустройства; на фиг.2 - блок-схемаузла синхронизации,Устроиство содержит группы вход36ных элементов И 1,входные регистры 2 с 22,2 игруппы элементов И 3.1, 3 с 3 иперезаписигруппы схем 4, 441,сравнения, группу триггеров 5И5.51 1, элементы 6, 66 задержки, группы элементов ИЛИ7 с 71 с с 7 и, реверсивные счетчики 87 68 ,8, ,8 элементы И-НЕ 91, 9,с 9 и, группы элементов И 10, 10,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-24.По окончании записи кодов чиселупорядочиваемого массива из блока 13синхронизации на первые входы узловэлементов И второй группы 3,1-3,4поступает синхроимпульс ссСИ 2 сс, разрешающий одновременную выДачу кодовчисел,упорядоциеаемого массива навходы соответствующих схем 4; 1-4.6сравнения. Схемы сравнения представляют собой узлы сравнения по старшему разряду последовательного типа,поэтому длительность синхроимпульса"СИ 2 сс должна обеспечить прохождениесигнала через элемент И, вхему сраяне; ия и триггер знака, Триггеры 5.1.6 знака обеспечивают запоминаниеи хранение знака результата сравне- .ния и церез элементы ИЛИ 7,1-7.4выдают импульсы с единицньсх и нулевыхвыходов на входы реверсиеных счетчиков 8.1-8,4. Для обеспечения цтЪо-го срабатывания триггеров реверсивного счетчика к входам элементовИЛИ 7.1-7.4, начиная со второго, подклюцгются элементы 6.,1-6.8 задерж-.ки,Число импульсов, записанное в ре-версивном счетчике, явгсяется кодомприоритета Н цисламассива А,Таким образом, после сравнения кодовчисел упорядочивания массива в реверсивных сцетчиках 8,1-8.4 записа 6ком 27. По окончании считывания ко" дов содержимое счетчика 27 становится равным нулю, разрешая формирование сигнала, по которому останавливается генератор тактовых импульсов, При наличии в массиве информации двух равных чисел на выходе соответствующей схемы сравнения сигнал отсутс 1 вует, поэтому триггер знака находится в том состоянии, в котором он находился после окончания переходных процессов. В этом случае очередность выдачи кодов чисел определяется текущим состоянием данного триггера знака.Оценка технико-экономической эффективности изобретения проводилась методом математического моделирования с последующей программной реализацией модели на ЭВИ БЭСМ-б.Анализ показывает, что эффективность предлагаемого устройства упорядочивания .зависит от объема упорядочиваемого массива и может составлять от 5 до 3,74 10 . Применение предлагаемого изобретения наиболее эффективно для 20и 100. формула изобретения 1. Устройство для упорядочивания чисел, содержащее й групп входных элементов И, И входных регистров, групп элементов И перезаписи, И -1) группу по К в каждой группе схем сравнения, И -1) группу по К в каждой группе триггера, блок синхронизации, группу элементов ИЛИ, информационные входы устройства соединены с информационными входами входных элементов групп, выходы элементов И каждой 1-й группы,где - 1,2 Ь, подключены к информационным вхоф дам 1-го входного регистра, выходы каждого 4-го входного регистра соединены с и формационными входами элементов И перезаписи 4 -й группы, выходы элементов И перезаписи каждой (1"1)"й группы подключены к первым информационным входам схем сравнения 4 -й группы, выходы "Больше" и Равно, меньше" каждой -ои схемы сравнения-ой группы, где= 1,2(И -1), соединены с входами установки в единичное и нулевое состояния соответственно 3-го триггера 1 -ой группы вторые информационные входы каждой -ой схемы сравнения , К-ой группы,7 932487 8чисел, причем код приоритета наибольшего числа равен нулю. В связис этим на едицицных выходах тригге"ров реверсивного счетчика, хранящего код приоритета наибольшего 5числа, будут нулевые потенциалы,ана выходе соответствующего элемента И"НЕ единичный потенциал, разрешающий по второму входу узлаэлементов И третьей группы 10.1-10.4 1 фвыдачу кода наибольшего числа.Для обеспечения устойчивого последовательного срабатывания триггеров реверсивных счетчиков и формирования кодов приоритетов между концом синхроимпульса "СИ 2" и началомпервого синхроимпульса "СИ 3" необходима задержка, длительность кото"рой может быть определена по следующей формуле: 20:+и-йИ:где С " время срабатывания триггерареверсивного счетчика;Гя- время распространения сигнала Ив элементе ИЛИ;и - число упорядочиваемых кодовмассива.Выдача кодов наибольшего числаосуществляется с выхода боответ" , Звствующего входного регистра черезузел элементов И третьей группы,на втором входе которого есть разрешающий потенциал и на. первый входкоторого с блока 13 синхронизации 55поступает синхроимпульс "СИ 3". Коднаибольшего числа через узел элементов ИЛИ 11 записывается впервый регистр 12 стековой памяти,По окончании синхроимпульса "СИ 3"в блоке 13 синхронизации формируется синхроимпульс "СИ 4", который спятого выхода блока синхронизациипоступает на оеверсивные входы счетчиков 8.1"8.4, уменьшая содержимоесчетчиков на единицу.Таким образом, для числа, следующего за наибольшим, код приоритетастановится равным нулю и с выходасоответствующего элемента И-НЕ навход элемента И третьей группы подается разрешающий потенциал. При поступлении синхроимпульса "СИ 3" следующий код числа записывается в пер"еый регистр блока 12 памяти, сЬдер 55жимое которого переписывается вовторой регистр и т.д.Число тактов выдачи подсчитывается в блоке 13 синхронизации счетчи32187 10ключены к входам управления выходных эгементов И групп; реверсивныхсчетчиков и входных регистров соответственно,2, Устройство по п.1, о т л ич а ю щ е е с я тем, что блок синхронизации содержит формирователиимпульсов, элементы задержки, триггеры, элементы ИЛИ, И, И-НЕ, счет 1 О чик, генератор тактовых импульсов,причем вход блока синхронизации соединен с входом установки в единичноесостояние первого триггера и черезпервые элемент и формирователь им"пульсов - с входом установки в нулевое состояние первого триггера ивходом установки в единичное состояние второго триггера, а через вторыеэлемент задержки и формирователь им"щ .пульсов - с входом установки в ну"левое состояние второго триггера ичерез третий элемент задержки и третий формирователь импульсов - с первым входом элемента ИЛИ и с входомИ четвертого элемента задержки, выходкоторого через четвертый формирователь импульсов соединен с входомустановки в нулевое состояние третьего триггера и с входом запуска генератора тактовых импульсов, выходкоторого соединен с первым входомэлемента И, с входом счетчика и свторым входом элемента ИЛИ, выходкоторого подключен к входу установкив единичное состояние третьего триггера, инверсный выход которого соединен с вторым входом элемента И,выходы счетчика подключены к входамэлемента И-НЕ, выход которого соединен с входом останова генераторатактовых импульсов, прямые выходыпервого, второго и третьего триггеЬров, выход элемента И подключены кпервому, второму, третьему и четвсртому выходам блока, вход блока черазпятый формирователь соеди он с пятымвыходом блока. где М= 1,2 И), подключены к выходам элементов И перезаписи 0 + 1)-ой группы, о т л и ч а ю щ ее с я тем, что, с целью повышения быстродействия,в него введены реверсивные счетчики, элементы И-НЕ, элементы задержки, блок памяти, причем прямой выход каждого у -го триггера первой группы соединен с первым вхо" дом ) -га элемента ИЛИ, инверсный . выход первого триггера первой группы подключен к первому входу И-гоэлемента ИЛИ, инверсные выходы второго, третьего ( И -1)-го триггеров первой группы соединены черезпервый, второй 1 и)-ой элементы задержки первой группы с вторым,третьим (И -1)-ым входами соответственно М-го элемента ИЛИ, прямой выход каждого-го триггеракаждой 1-ой группы, кроме первой, через л -ый элемент задержки 1-ойгруппы подключен к ) -му входу 1-го элемента ИЛИ, инверсный выход каждого -го триггера каждой 1-ойгруппы соединен через (и - 1 + 1 ) -ыйэлемент задержки с И - 1 + Д ) -ымвходом О)-го элемента ИЛИ, выходкаждого 1-го элемента ИЛИ подключенк информационному входу 1 "го реверсивного счетчика, выходы каждого3-го реверсивного счетчика соедине 1ны с входами л-го элемента И"МГ,выходы каждого 1 -го входного регистра подключены к информационнымвходам выходных элементов И 1-ойгруппы, выход каждого 1 -го элементаИ-НЕ соединен с первым управляющим входом выходных элементов И 1, 1 + 1)-ой группы, а выход 11-го элемента И-НЕ подключен к первому управляющему входу выходных элемен" тов И первой группы, выходы выходных . элементов И групп соединены с вхо" дами элементов ИЛИ группы, выходикоторых подключены к входам блокапамяти, управляющий вход устройства соединен,с входом Ьлока синхронизации, первый выход которого подключен к управляющим входам входных элементов И групп, второй выход блока синхронизации соединен с управ.ляющими входами элементов И перезаписи групп, третий, четвертый и пя-ый выходы блока синхронизации подИсточники информации,принятые во внимание при экспертизе 1. Авторское свидетельство ИСР И 918 М кл.06 : 02, 1977,2, Патент СЮ Вф 3931612,кл. Я Щ702 у Опублике 1976 (про" тотип;.932187 аказ 3785/69 Тираж 732 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 133035, Москва, В, Рауаскаю наб., дПП "Патент", г. Ужгород, ул. Орое фи Составитель В.белкин тор Е,Папп Техред И. РейвесКорректор С.Юекмар