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

(9) ( 6 Р 7/06 4( ТЕЛЬСТВУ триггевыход О выходнен с с а сининича ГОСУДАРСТ 8 ЕННЫЙ НОМИТЕТ. СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ПИСАНИЕ ИЗОБ(56) 1. Патент США У 3931612,кл. С 06 Г 7/02, 1976,2, Авторское свидетельство СССУ 932487, кл. С 06 Г 7/06, 1980(прототип),(54) (57) УСТРОЙСТВО ДЛЯ УНОРЯДОЧИВА- .НИЯ ЧИСЕЛ, содержащее блок памяти,первый и второй счетчики, триггер,первый, второй и третий элементы ИЛИ,элемент И и блок синхронизации, включающий первый и второй триггеры, генератор тактовых импульсов и первыйэлемент И, первый вход которого подключен к выходу генератора тактовыхимпульсов, вход запуска устройстваподключен к входу установки в"1" первого триггера, о т л и ч а юц е е с я тем, что, с целью его упрощения, оно содержит коммутатор ибуферный запоминающий блок, информационные входы которого соединены синформационной ниной устройства, подключенной также к входам первого элемента ИЛИ и первой группе входов коммутатора, вторая группа входов которого подключена к выходам разрядовпервого счетчика, а выходы - к адресным входам буферного запоминающегоблока, выходы которого соединены свходами второго элемента ИЛИ и инфор.мационными входами блока памяти, адресные входы которого соединены свыходами р зрядов второго счетчика,счетный вход которого соединен с выходом третьего. элемента ИЛИ, первый вход которого соединен с прямым выходом триггера и первым входом элемента И, выход которого. подключен к входу синхронизации триггера, информаци-. онный вход которого соединен с выходом первого элемента ИЛИ, блок синхронизации дапблнительно содержит второй и третий элементы И, причем вход конда записи устройства соединен с входом установки в "0 первогора блока синхронизации, прямой Ькоторого соединен с управляющим входом коммутатора, входом разрешения записи буферного запоминающего блока и первым входом второго элемента И блока синхронизации, второй вход которогоподключен к выходу генератора тактовых импульсов, а выход соединен с входом записи буферного запоминающего блока, вторым входом элемента И, инверсный выход первого тригге,ра блока синхронизации подключен к второму входу первого элемента И.выход которого соединен с первым входом третьего элемента. И и счетным входом первого счетчикапереполнения которого соеди ин хровходом второго триггера блок хронизации, вход установки в ед ное состояние которого подключен кг входу запуска устройства, информационный вход второго триггера блока синхронизации соединен с шиной логического нуля, а выход - с управляющим входом генератора тактовых импульсов, второй вход третьего элемен та И блока синхронизации подключен к вы хлду второго элемента ИЛИ, а выход соединен с входом записи блока памяти и вто рым входом третьего элемента ИЛИ.1144Изобретение относится к автоматике и вычислительной технике и можетиспользоваться в устройствах обработки цифровой информации,Известно устройство для упорядочивания чисел, содержащее память дляхранения подлежащих сортировке кодовчисел; буферные регистры, схемы сравнения узлы адресаций, селекторы,узел передачи 111,Недостатком такого устройства является низкая производительность, обусловленная нерациональными затра.тами времени на последовательное сравнение коцов упорядочиваемой информации и затратами времени на выполнение операций над адресами кодов,Наиболее близким по техническойсущности к предлагаемому устройствуявляется устройство для упорядочивания чисел, содержащее и групп входных элементов И, и входных регистров,и групп элементов И перезаписи,(и) группу по и в каждой группесхем сравнения, и) группу по к Вкаждой группе триггеров, блок синхронизации, группу элементов ИЛИ,реверсивные счетчики, элементы И-НЕ,элементы задержки, блок памяти, при 3 Очем информационные входы устройствасоединены через группы входных элементов И с входами регистров, выходыкаждого 1.-го входного регистра через элементы перезаписи подключены ЗБк первым информационным входамсхем сравнения .-й группы, выходыкаждой 1-й схемы сравнения -группы,где х=1,2,и. 1=1,2,= ,(и),соединены с входами установки в еди- бг"иничное и нулевое состояния соответственно 1-го триггера-й группы,вторые информационные входы каждой1-й схемы сравнения поцключены квыходам элементов И перезаписи(х+1)-й группы выходы триггеровчерез элементы задержки и элементыИЛИ подключены к входам реверсивного счетчика, выходы которых черезэлементы И-НЕ и группы элементов ИЛИ бподключены к входам блока памятиблок синхронизации содержит формирователи импульсов, элементы задержки,триггеры, элементы ИЗИ,. И И-НЕ,счетчик, генератор тактовых импульсов с соответствующими связями 21.Недостатком известного устройстваявляется сложность технической реали 1 ОЗ 2зации при упорядочивании больших массивов информации,Цель изобретения - упрощение устройства. 11 оставленная цель достигается тем, что устройство для упорядочивания чисел, содержащее блок памяти, первый и второй счетчики, триггер, первый, второй и третий элементы ИЛИ, элемент И и блок синхронизации, вклю. чающий первый и второй триггеры, генератор тактовых импульсов и первый элемент И, первый вход которого подключен к выходу генератора тактовых импульсов, вход запуска устройства подключен к входу установки в "1" первого триггера, содержит коммутатор и буферный запоминающий блок,информационные входы которого соедииены с информационной шиной устройства, подключенной также к входам первого элемента И 11 И и первой группевходов коммутатора, вторая группавходов которого подключена к выходам разрядов первого счетчика, а выходы - к адресным входам буферного запоминающего блока, выходы которого соединены с входами второго элементаИЛИ и информационными входами блока памяти, адресные входы которого соединены с выходами разрядов второго счетчика, счетный вход которого соединен с выходом третьего элемента ИЛИ, первый вход которого соединен с прямым выходом триггера и первым входом элемента И, выход которого подключен к входу синхронизации триггера, информационный вход ко- - торого соединен с выходом первого элемента ИЛИ, блок синхронизации дополнительно содержит второй и третий элементы И, причем вход конца записи устройства соединен с входом установ. ки в "О" первого триггера блока синхронизации, прямой выход которого соединен с управляющим входом коммутатора, входом разрешения записи буферного запоминающего блока и первьпч входом второго элемента И блока синхронизации, второй вход которого подключен к выходу генератора тактовых импульсов, а выход соединен с входом записи буферного запоминающего блока, вторым входом элемента И,инверсный выход первого триггера блока синхронизации подключен к вто. рому входу первого элемента И, выход которого соединен с первым вхо3дом третьего элемента И и счетнымвходом первого счетчика, выход переполнения которого соединен с синхровходом второго триггера блока синхро.низации, вход установки в единичноесостояние которого подключен к входу запуска устройства, информационный вход второго триггера блока синхронизации соединен с шиной логического нуля, а выход - с управляющимвходом генератора тактовых импульсов, второй вход третьего элемента Иблока синхронизации подключен к выходу второго элемента ИЛИ, а выходсоединен с входом записи блока памяти и вторым входом третьего элемента ИЛИ,На фиг. 1 схематически представлен алгоритм упорядочивания чисел;на фиг, 2 - блок-схема устройства;на фиг, 3 - блок-схема блока синхронизации; на фиг. 4 - временная диаграмма, поясняющая работу устройства.Устройсфво содержит буферный запоминающий блок 1, блок 2 памяти,коммутатор 3, первый элемент ИЛИ 4,второй элемент ИЛИ 5, первый 6 ивторой 7 счетчики, блок 8 синхронизации, третий элемент ИЛИ 9, элементИ 10, триггер 11, информационную шину 12, вход 13 запуска, вход 14 конца записи,1Блок 8 синхронизации содержитпервый триггер 15, второй триггер 16,первый, второй и третий элементы . 35И 17 - 19, генератор 20 импульсов,входы 21-24, выходы 25-28Счетчики 6 и 7 представляют собойдвоичные счетчики, срабатывающие позаднему фронту синхросигиала. 40Коммутатор 3 - устройство, передающее на свой выход в зависимости отсостояния управляющего входа логический ноль или логическую единицу,соответственно информацию с вторых 45или первых входов.Триггеры 11 и 16 представляют собой синхронные триггерыР -типа, срабатывающие по заднему фронту синхросигнала. Триггер 15 - триггер 8-5-типа,50Сущность работы устройства заключается в следующем (фиг, 1),Число К=а,а 1а 11 иэ входного числового массива И записывается в буферный запоминающий блок 1 55(фиг. 2), предварительно обнуленный,ло адресу К; = аа 1., а 1, Приотсутствии числа К, из входного мас 103сива Х соответствующего блока 1 ло данному адресу сохраняется нулевая информация.При перезаписи иэ буферного запоминающего блока 1 в блок 2 памяти информация в виде упорядочиваемых чисел записывается в блок 2 памяти в соответствии с адресом, который одногременно является признаком приоритета, начиная с нулевого адреса, при построении возрастающего ряда чисел, или с максимального адреса при построении убывающего ряда чисел.Устройство работает следующим образом.В исходном состоянии буферный.запоминающий блок 1, блок 2 памяти, первый 6 и второй 7 счетчики, первый 15 и второй 16 триггеры блока 8 синхронизации обнулены, триггер 11 установлен в единичное состояние,Работа устройства начинается по сигналу "Пуск", поступающему ло входу 13 на первый вход 21 блока 8 синхронизации (фиг.40) . По этому сигналу первый триггер 15 по 8-входу устанавливается в единичное состояние(фиг. 40), Уровень логической единицы с прямого выхода первого триггера 15 через четвертый выход 28 блока 8 синхронизации поступает на управляющий вход буферного запоминающегоблока 1, переводя его в режим записи, и на управляющий вход коммутатора 3, переключая его на передачу информации из кодовой шины 12,числа на адресные входы буферного запоминающего блока 1. Одновременно с этим сигнал .1 Пуск" устанавливает в единичное состояние по 3-входу триггер 16 (фиг. 46), с выхода которого сигналуровнем логической единицы поступает на управляющий вход генератора 20импульсов и запускает его (фиг. 4 Ф).Импульсы с выхода генератора 20 импульсов через открытый по первому входу элемент И 17 уровнем логической единицы с прямого выхода триггера 15 в виде синхроимпульсов СИ 1 поступают на первый выход 25 блока 8Осинхронизации и далее на вход записи буферного запоминающего блока 1, на счетный вход триггера 11 черезоткрытый элемент И 10 и на выходнуюшину синхронизации устройства(фиг. 4 е),Информация из числового массиваИ поступает по шине 12 устройства наинформационные входы буферного запо-, минающего блока 1 и записывается в него по заднему фронту импульсов СИ 1, поступающих на вход записи в соответствии с адресом, формируемым 5 коммутатором 3. При этом, так как коммутатор 3 подклйчает на адресные входы буферного запоминающего блока 1 информацию с первых входов, подклю ченных к шине 12 устройства, число 10 К из входного массива И записывает- Ься по адресу К, число К- по адресу К и т.д.Одновременно с этим число К из входного массива чисел поступает на 15 входы первого элемента ИЛИ 4, с выхода которого при К О, сигнал уровня логической единицы поступает на информационный вход триггера 11 (Фиг, 4) и по заднему фронту импуль 20 сов,. поступающих на его синхровход, подтверждает его состояние. При наличии во входном массиве М хотя бы одного "нулевого" числа (К = 0) на выходе первого элемента ИЛИ образует ся сигнал уровня логического нуля (Фиг. 4 Ф), и триггер 11 переводится в нулевое состояние, Отрицательный перепад уровня, образованный на выходе триггера 11 (фиг, 4) поступает З 0 через третий элемент ИЛИ 9 (фиг. 4 а) на счетный вход второго счетчика 7, и увеличивает его состояние на единицу, Фиксируя тем самым в блоке 2 памяти "нулевое" число с "нулевым" приоритетом, Кроме того, сигнал уровня логического нуля с выхода триггера 11 поступает на второй вход элемента И и блокирует его, таким образом триггер 11 Фиксирует только одно ".нулевое число" при его наличии во входном числовом массиве И.Для окончания цикла записи входного массива чисел И в буферный запоминающий блок 1 по входу 14 подается сигнал КЗП (Фиг. 4), который поступает через второй вход 22 блока 8 синхронизации на К-вход первого триггера 15.и устанавливает его в ну. левое состояние (Фиг. 4), при этом уровень логического нуля с прямого выхода триггера 15 через четвертый выход 28 блока 8 синхронизации поступает на управляющий вход буферного запоминающего блока 1, переводя его в режим чтения, и на управляющий вход коммутатора 3, переключая его на передачу информации на адресные входы буферного запоминающего блока1 с вторых выходов, подключенных кинформационным выходам первого счетчика 6. Одновременно с этим сигналуровня логического нуля поступаетна первый вход первого элемента И 17 блока 8 синхронизации и блокирует его, а сигнал уровня логической единицы с инверсного выхода триггера 15 открывает по первому входу второй элемент И 18, на выходе которогопоявляются синхроимпульсы СИ 2(фиг, 4 и), поступающие на второйвыход 26 блока 8 синхронизации и напервый вход третьего элемента И 19, второй вход которого через четвертый вход 24 блока 8 синхронизацииподключен к выходу второго элемента ИЛИ 5. Таким образом, устройствопереводится в режим перезаписи информации из буферного запоминающегоблока 1 в блок 2 памяти.Первый и второй счетчики 6 и 7являются счетчиками адреса соответ,ственно буферного запоминающегоблока 1 и блока 2 памяти, Первыйсчетчик 6 находится в обнуленномсостоянии и указывает нулевой адрес буферного запоминающего блока 1,состояние второго счетчика 7 определяется наличием "нулевого" числа вовходном массиве чисел И и указываетлибо нулевой адрес блока 2 памяти,либо первый,Информация, считываемая из буферного запоминающего блока 1, поступает на информационные входы блока 2 памяти и на входы второго элемента ИЛИ 5, на выходе которого образуетсялсигнал с задержкой(- время выборки информации из буферного запоминающего блока 1), который через четвертый вход 24 блока 8 синхронизации стробирует по второму входу третий элемент И 19, на выходе которого Формируются синхроимпульсы СИЗ, поступающие на вход записи блока 2 памяти и синхровод второго счет чика 7.По нулевому адресу буферного запоминающего блока 1, а также по адресам, по которым не происходила запись, находится "нулевая" информация, которая, будучи считанная из буферного запоминающего блока 1, поступает на входы второго, элемента ИЛИ 5 (фиг. 4 л) и вызывает появление на его выходе уровня логического нуля,1144 10 Адрес Н Иуле Раяан Фееаи дрес Ь, Фрес 31 дрес 3 е Адрес Н Адресно Адрес НаУаеазаФармерАдрес н А дресЬн-Адрес Ь который блокирует по,второму входу третий элемент И 19 блока 8 синхронизации и, таким образом, в данном случае синхроимпульсы СИЗ не формируются (фиг. 4 н), запись в блок 2 памяти не происходит, второй счетчиксвоего состояния не изменяет.По заднему фронту СИ 2 первый счетчик 6 изменяет свое состояние, т,е. переключает буферный запоминающий блок 1 на следующий адрес К 1. При наличии по заданному адресу числа К1 оно считывается из буферного запоминающего блока 1, причем на выходе второго элемента ИЛИ 5 появляется уровень логической единицы (фиг. 4 ь), который открывает элемент И 19 блока 8 синхронизации, и на его выходе формируется импульс СИЗ (фиг. 4 щ), который через третий выход 27 блока 8 синхронизации поступает на вход записи блока 2.памяти и записывает в него по заднему фронту число К 1 по адресу В 1. Одновременно по заднему фронту СИЗ через третий элемент д ИЛИ 9 (фиг. 4 н) переключается второй счетчик 7 на следующий адрес В, а по заднему фронту СИ 2 первый счетчик переключается на адрес К и т.д.После опроса последнего адреса буферного запоминаюшего блока на выходе переноса первого счетчика 6 формируется импульс переноса(фиг.40),который поступает через третий вход 23 блока 8 синхронизации на синхровход второго триггера 16 и по заднему35 фронту устанавливает его в нулевое состояние (фигл 6), блокируя тем самым генератор 20 импульсов, На этом 1 ОЗ 8,режим перезаписи информации из буферного запоминающего блока 1 я блок 2 памяти прекращаетсяТаким образом, после перебора всех адресов буферного запоминающего блока 1 в блоке 2 памяти будут записаны в порядке возрастания адреса (приоритета) К 1, упорядочиваемых чисел из входного массива.Объем буферного запоминающего блока 1 определяется по формуле= и2иВЗЧгде и - разрядность числа.9Объем блока 2 памяти определяется по формуле= п 1 оя п.бпПреимуществом предлагаемого устройства является упрощение устройства высокое быстродействие, таккак отсутствует последовательный перебор чисел с целью определения максимального (минимального) числа из оставшихся. Кроме того, практически нет ограничения на качество упорядочиваемых чисел (ограничивается емкостью буферного запоминающего устройства), можно получить однородную наращиваемую структуру, устройство позволяет легко вводить ранжирование чисел или дополнительные признаки для решения конкретной задачи.Применение предлагаемого устройства по сравнению с известным устройством упорядочивания чисел в составе базового устройства А 8 позволило сократить оборудование на ЗОХ, 11441031144 103 е и Составитель Е Техред А.Кикем Иваноей едактор Р. Цицика орректор В. кая аказ 931 илиал ППП "Патент", г. Ужгород, ул. Проектная,Тираж 7 ВНИИПИ Государ по делам изоб 035, Москва, Ж твенногоетений и5, Раушск Подписноеомитета СССРткрытийя наб., д. 4/5