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

Изобретение относится к автоматике и вычислительной технике, в частности к устройствам сортировки, и может быть использовано в качестве со 5ставной части блока нормализации порядка чисел с плавающей запятой в ЗБМ,комплексах и системах на модулях сбольшой степенью интеграции.Цель изобретения - упрощение устройства,На фиг, изображена блок-схемапредлагаемого устройства; на фиг.2блок управления,Устройство содержит регистр-счетчик 1, счетчик 2, ассоциативный накопитель 3, регистр 4 адреса, информационный регистр 5, дешифратор 6, коммутатор 7, дешифратор 8, блок 9 управления, триггер 1 О, входы 11-15 20блока управления, выходы 16-24 блока управления,Блок 9 управления содержит генератор 25, элементы И 26-28, триггер29, элемент ИЛИ 30, триггеры 31 и 32, 25элементы 33 задержки, элемент ИЛИ 34и элементы 35-40 задержки,Устройство работает следующим образом,Если перед проведением операции 30сортировки необходимо изМенить диапазон, то на вход устройства поступает управляющий сигнал Задание диапазона , который вызывает появлениеуправляющего сигнала на выходе 19блока 9 управления, а через элементИЛИ 30 вызьгвает появление управляющего сигнала на выходе 16 блока 9 управления, Одновременно на информационные входы устройства поступает двоичное число, представляющее собойграницу (нижнюю или верхнюю в зависимости от критерия сортировки ) диапазона. Сигнал на выходе 6 блока 9 управления разрешает прием кода этогочисла на реверсивный регистр-счетчик1, Сигнал на выходе 19 блока 9 уп -равления устанавливает в "1" триггерО, в результате чего комбинация сигналов на его выходах, а значит, и напервом и втором управляющих входахассоциативного накопителя и коммутатора 7 определяют операцию записи поадресу в ассоциативный накопитель икоммутацию информационных выходоввторого дешифратора 8, Счетчик 2 висходном состоянии находится в состоянии "000", Сигнал. "Задание11диапазона поступает также на вход элемента 40 задержки, который вноси 1 задержку на время, необходимое на вышеописанные действия, связанные с установкой отдельных элементов устройства и др, Затем на выходе элемента 40 задержки появляется единичный сигнал, который через элемент ИЛИ 34 передается на выход 22 блока 9 управления, На третий управляющий вход ассоциативного накопителя поступает тактирующий сигнал. Таким образом, по адресу, определяемому счетчиком 2 (в данном случае это "00..О"), комбинация сигналов (как и любые другие комбинации), возникающая на выходах счетчика 2, поступает через регистр 4 адреса, второй дешифратор 8 и коммутатор 7 на адресные входы ас;оциативного накопителя, в результате чего ассоциативный накопитель 3 записывается нижняяили верхняя граница задаваемого диапазона, Сигнал "Задание диапазона" устанавливает в 1 находящийся в исходном состоянии триггер 29, а затем сигнал с выходя генератора 25 через элемент И 26 поступает на вход элемента 33 задержки. Далее сигнал появляется на выходе элемента 33 задержки, а следовательно, и на выходе 17 блока 9 управления. 3 гот сигнал, поступая соответственно на второй управляющий вход регистра-счетчика 1 и на управляющий вход счетчика 2 является соответственно сигналом "+1" (в зависимости от критерия сортировки) и сигналом "+1" на управляющем входе счетчика. Далее сигнал появляетсн на выходе элемента 38 задержки, а следовательно, и на выходе 3 блока 9 управления, в результате чего на управляющих входах регистра 4 адреса и дешифратора 8 появляются разрешающие сигналы, Хаким образом, следующий адрес, больший предьдущего, на единицу, поступает на адресные входы ассоциативного накопителя, а на его информационные входы поступает двоичное число, на единицу большее или меньшее границы диапа.она, Далее сигнал появляется на выходе элемента 37 задержки, а через элемент ИЛИ 34 на выходе 22 блока 9 управления. Таким образом, по следующему адресу в ассс циативный накопитель записывается следующее число диапазона. Затем с генератора 25 поступает следующий сигнал и прсцесс повторястся, Такд(сс)пи 1 икный ц 1 к)цит ел 1 заполняЕтся чиелдми, состдвляншими требуемый зддднный,идпазн. Коэффициент пересчет д ( ч е т ч и к д 2 О и р с ц е.я с. т с я к 0.1 ич е с т5 вом ячеек дссоциативцо о накопителя, т,е. величиной диапазона, По заполнени дссоциативцого накопителя счетчик 2 сбрасывается"0" и сигнал с ураезлянццего вых дд счетчика 2 посту пдег нд вход 14 блокд 9 уцрдвлеция, устацаливдя в "0" триг гер 29, отключая тем сдльм генератор 25 от цепочки ЭЛСМе НТОВ, Об ЕСПЕЧ ИГ 1 Юццх ЗдПИСЬ Кд 5 ичн),11 ГнаГ п)яллд триггера 31 пос гуп,)ет нд тр)ц ход )лементд И "2, п 1 и . Том Гигцдп Г35 ,нсрдторд 25рс.) элеми 1,1 30 по т упдет нд кХОД 16 блока 9 управ- .и( ния, д чере з )е(мс и35 )ддержки. ц )лелнт ИЛИ 34 - нд кх;1 "2 бл(- кд 9 ;Грд 11 сния(:,1 Г нс)л и; ецХс)Д( 16,1 блока 9 уцрдл ция рд.)р нН т запись чисз;з и з и .(,Од тельГТН сортируемьх чзсе ргистр Гчетик) а сиг - цдл нд выходе 22 блока 9 чрдвления зт Рс)Ре 1)н 1111 гдк гиРУн)ЦН Г игнат),55 поступдюнцй нд тр ий управляющий ьхоц дссцидтин го цдь чителя, Таким Обрдзом, цд Гцформ,Нцоннье входы дссоцидтино1 дк(те.ч поступает НГ)О ) с(е)внс ниОро рс)иходит асс)истицм 11 к)питс 1 с 3, Т 1 к кдк п.ту 1 ц с 1 ,.ри д;1 лежит закц м дкс)пителег )езультдт срдвГ С Д Ц НМ К 1 Г ГДИД 11 )ОН 1 И , и 1 Д Г)ТКСТСТВУЮ)Х:е дГ О 11 тив -ения плж и Гч ц 1 е: уп рд 1,нГ,ц ) к1 т ( Г) ГГ 1)Г тч с 1 и н и ч ы 1 Ги.ГГ 1 т у 1)Ки 4 н динич Гья вхд (О) гт в л 1) рд з(яда ин чисел здддвдемого диапазона, 15;1 длее можно поддндть ц . Инсе)ормдц 5- Оне 1 ходы последодтс льнОсть дноичнгх чц ел, подлежащих .ртировке,ПО сигцлу "1 дчдло Ог(рации", по тупднщему цд вхсд 12 бенокд 9 управ ления возникает сигнал нд выходе 20 блока 9 упрдвлсния, в результдте чсго триггер 31 устдндвлидется в ,Сигнд 1 нд вьходе 20 блока 9 упрдн - ления устандвлидет в триггер 75 1 О,рс зультдте че О комбинация сигндлок Г его выхода опредгяет опера,ин 3 д 1 и Г и ц О и р Р 3 н л к у дл я д с Г с) цид ткого ндк;пит ля и ком утдцию децефрдт ;, Г) цд д;ч Гные хды асс Оцид тен 1 О ц,к)Етеля чере ) кммутатор дормдпиоеного регистрд 5, представляюп г О Гобой гп - рд э рядный регис тр, где гг - длицд диапазона чисел. Пдновремсцно цд выходе элемента 35 задер)(- ки появляет я единичный сигнал, что означает появление сигнала на выходе 23 блока 9 упрдвлеция, В результате управлянщий сигнал Принять код поступает на первый управляющий вход информационного регистра 5, Таким обрдэом, в разряд информационного регистра 5, соответствующий записанному в ассоциативный накопитель числу, равному поступившему на информационные входы устройстд коду иэ подлежащей сортировке последовательности, )с писыва ется елаеени 1, свидетельствующаяя О том, чт( дднцое число на информационные входы ус гройства поступиПдлее Г генерд горд 25 поступает Г:едупий си нал и вышеописанный процесс повторяется до поступления на нхоц 15 блока 9 управления управляющего сигнала )Конец сортируемой посл дователНости, Триггер 31 устанавзпкдется в Г),результате чего ц,НьеинНя:)д:1 с в информационный рГтр 5 ивнздццые Г ней действия нс прои(.хцят.) дссоцидт)ицом дкопителе 3 всеч 11(лд 3 ддд нноО ц идп д зонд находятся рядке возрастания или убывания, т. , НО(:едкдтсльцость их Отсортир днд. В ИОрмдци нном регистре 5 кдждый рдзря) Гоот( ТГту т определс иной ячс йке дс.цц;тивцого накопитсля, причем млдцпй разряд соответГтуст ячейкем.;1 ц)м д;Гесом, ПриЗНДКИ В ДСГОЦЦДИКНМ НДКО. ГЕЛЕ ЭКикдлецтны чи 1)л, которые могут пос гудт Нд инфорл,1 Г;и( нные входы устроиствд. Тдким Обрдзсм, единицами в разрядах ин 1 О 1)л)ццоцного регистра 5 отмечецы т яч Еьи ассоциативного нак 1 ит еля 3,гризцдкц эдписацные в которых равны постуиншим на информационные вх)1 для сртировки двоичным числдм. Ирмдт рикдя информационцыи регистр 5 с млддших разрядов и вьДдвдя нд выход устройства двоичные числа из ячеек ассоциативного накопителя 3, лот р( соответствун)т (диеичньл рд )рядам 1 И 1 орлационного регГтрд 5, тем Г;лью ьдается на выхц устройстд ступившдя на ицформдионные вхць у т)ниства последователность Екоичных чисел уже в отсорт и(в н д н н ом в ;,(1 - и) 0 0 0 0 0 0 100 010 001 1 Х ХХ Х 0 1 ХХ Х 0 0 1Х Х0 О 01 Х 0 0 00 1 О О ОО О000000000 100 010 001 Прспес с просмотра иирма пионого регистра 5 и выдачи отсортировдцной последовательости осуществляется следующим образом. Сигнал "Конец сор -5 тнруемой последовательности поступает на единичньй вход триггера 32, а сигнал нд его единичном выходе Формирует единичный сигнал ца выходе 21 блока 9 управления, определяя на чет О вертом упрдвлямщем входе ассоциативного накопителя 3 операцию Чтение по адресу . Сигнал с единичного выхода Исходя из принеденцого в таблице соответствия Вгдно что код с выходов первого дешифрдтора Ь, поступая через коммутатор 7 нд адресные входы ассоцидтивцго накопителя 3, приводит к возбуждению адресной шины чтения, соответствумшей той ячейке ассоцидтинного накопителя, которая соответствует выделенной пзрвьм дешифрдтором35 6 младшей единице кода, зафиксированного нд инФормационном регистре 5Так как выходы первого дешифратора 6.соединены с инверсными входами ин- формационного регистра 5, то Форми руемый дешифрдтором 6 код одновременно с поступлением ца адресные входы ассоциативного накопителя 3 гасит младшую единицу кода, зафиксированного на информационном регистре, в результате чего в следующем такте младшей вьделенно единицей будет уже следующая по отношению к выделенной в данном такте, Сигнал с эпемецтд И 28 помимо выхода 21 блока Ф9 управления пос тупдет на вход элемента 36 задержки и по истечении времени, необходимого для дешифрации кода с информационного регистра 5 и коммутации кодд с выходов первого де 55 рдтср 6, поступает на адресные нходл сс цидтивного накопителя 3, д здтсм ч ре элемслт ИП 34 - цд выход 22 б:.к 9 управления, в резупь -Ю триггера 32 поступает на второй входэлемента И 28, д сигнал с генератора25 поступает на выхоц 23 блока управления и соответственно, на второйуправляющий вход информационного 1 е-,гистрд 5, что эквивалентно подачесигндлаВыдать код с информацио.ого регистра, Код с информационногорегистра 5 поступает на входы первогодешифратора 6, Дешифратор 6 реализует следующую систему функций: тате чего на третий разрешающий входассоциативного накопителя поступаеттактирующий сигнал и на инф рмдпионцых выходах ассогцативного накопителя появляется соответствующее такту выдачи отсортирсванной последовательности двоичное число (в описываемом первом такте - первое - наибольшее или наименьшее), В дальнейшемс генератора 25 поступает следующийимпульс и процессы, описанные выше,понгрямтся до тех пор, пока на информационном рсгистре 5 не будет заФиксирован код 000, что свидетельствует о том, что на выход устройства выдана упорядоченная и следовательность двоичных чисел. Тогда первый дешифр тор 6 Формирует на своемвыходе единичный сигнал, то соответствует появленик уп;двляющего сигнала "Конец операции а упдв:яющемвьгходе устройства. Сигнал с (ш+1)-говыхода первого дешифратора 6 постудет также на инверсный в:од триггера 32, устанавливая его в "0", вре ультате чего устройство переходитв исходное состояние и готово к приему следующей последовательности чиселподлежащей сортировке, о р м у л а и з о б р е т е н и 1, Устройство для сортировки чи ел зд;днцог диапазона, содержащее де 1494000шифратор и блок управления, о т л ич а ю щ е е с я тем, что, с целью упрощения устройства, но содержит ассоциативный накопитель, информаци 5 онный регистр, регистр-счетчик, счетчик, регистр адреса, второй дешифратор, коммутатор и триггер, причем информационные входы устройства соединены с информационными входами регистра-счетчика, выходы разрядов которого соединены с первой группой информационных входов ассоциативного накопителя, информационные выходы первой группы которого являются информационными выходами устройства, а информационные выходы второй группы подключены к соответствующим прямым входам информационного регистра, выходы разрядов которого соединены с входами первого дешифратора, ш выходов которого соединены с первой группой информационных входов коммутатора (ш - емкость ассоциативного накопителя) и с соответствующими инверсными входами информационного регистра, (ш+1)-й выход дешифратора является выходом конца работы устройства и соединен с первым входом блока управления, второй и третий входы которого являются соответственно входами начала операции и задания диапазона устройства, четвертый вход блоблока управления подключен к выходу переполнения счетчика, выходы разря - дов которого соединены с информационными входами регистра адреса, выходы разрядов которого соединены с входами второго дешифратора, выходы которого соединены с второй группой информационных входов коммутатора, первый и второй входы которого соединены соответственно с прямым и инверсным выходами триггера, с первым и вторым управляющими входами ассоциативного накопителя, адресные входы которого соединены с выходами разрядов коммутатора, первый выход блока управления соединен с входом разрешения записи регистра-счетчика, второй выход - со счетными входами регистра-счетчика и счс гчика, третий выход - с входом разрешения записи регистра адреса и сз робирующим входом второго деширатора, четвертый и пятый выходы - соответственно с входа. ми установки в "1" и "0" триггера, шестой и седьмой выходы - соответственно с третьим и ч 1 в ртым управляющими входами ассоциативного накопителя, восьмой и девятый выходы - соответственно с входами записи и считывания информационного регистра, пятый вход блока управления являетсявходом конца сортируемой последовательности устройства,2. устройство по п. 1, о т л и - ч а ю щ е е с я тем, что блок управления содержит генератор импульсов, три триггера, три элемента И, два элемента ИЛИ, семь элементов задержки, причем выход генератора импульсов соединен с первыми входами первого, второго и третьего элементов И, первый, второй и четвертый входы блока управления соединены соответственно с входами установки в "0" первого, в "1 п второго и в пОн третьего триггеров, прямые выходы которых соединены с вторыми входами соответственно первого, второго и третьего элементов И, выход второго элемента Р соединен с первым входом первого элемента ИЛИ, выход которого является первым выходом блока управления, выход третьего элемента И соединен через первый элемент задержки с входом второго элемента задержки и является вторым выходом блока управления, выход второго элемента задержки является третьим выходом блока управления и соединен через третий элемент задержки с первым входом второго элемента ИЛИ, третий вход блока управления соединен с входом установки в "1" третьего " тиггера, с вторым входом первого элемента ИЛИ, является четвертым выходом блока управления и через четвертый элемент задержки соединен с вторым входом второго элемента ИЛИ, вход установки в н 1 п второго триггера соединен с пятым выходом блока управления шестой выход которого соединен с пряйым выходом первого триггера, выход второго элемента И через пятый элемент задержки соединен с входом шестого элемента задержки и с третьим входом второго элемента ИЛИ, выход которого является седьмым внходом блока управления, восьмой выход которого подключен к выходу шестого элемента задержки, выход первого цемента И является девятым выходом блока управления и соединен через седьмой элемент задержки с четвертым входом второго1494000 12 в "1" первого ив "0" второго триггеров,элемента ИЛИ, пятый вход блока управлЕния соединен с входами установки го 17 2 г.2 Составитель В.Коэло ктор Л,Ревин Техред Л,Сердюковаектор Н,Король Подписно по иэобретениям и открытиям при ГКНТ ССС