Устройство для сортировки чисел заданного диапазона
Изобретение относится к автоматике и вычислительной технике ,в частности, к устройствам сортировки, и может быть использовано в качестве составной части блока нормализации порядка чисел с плавающей запятой в ЭВМ, комплексах и системах с большой степенью интеграции. Целью изобретения является упрощение устройства. Устройство содержит регистр - счетчик 1, счетчик 2, ассоциативный накопитель 3, регистр адреса 4, информационный регистр 5, дешифратор 6, коммутатор 7, дешифратор 8, блок управления 9, триггер 10. Основной принцип работы предложенной структуры состоит в регистрации поступления определенного двоичного числа, входящего в заданный диапазон чисел, на выходы устройства при помощи маркерной единицы в информационном накопителе с помощью ассоциативного накопителя и в дальнейшем при помощи ассоциативного накопителя формирования кодов двоичных чисел, поступающих для сортировки, в отсортированном виде на выходах устройства. 1 з.п. ф-лы, 2 ил.
союз советских социАлистических
РЕСПУБЛИК (51)4 G 06 F 7/04
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ а
1
ГОСУДАРСТВЕННЫЙ КОМИТЕТ
ПО ИЭОБРЕТЕНИЯМ И ОТКРЫТИЯМ
ПРИ ГКНТ СССР (2)) 4354980/24-24 (22) 20.11.87 (46) 15.07.89. Бюл. М 26 (71) Киевский политехнический институт им, 50-летия Великой Октябрьской социалистической революции (72) В.И.Корнейчук, О.В.Журавлев, В.Н.Сороко и А.Г.Езикян (53) 681.325(088.8) (56) Авторское свидетельство СССР
828450, кл. G 06 F 7/04, 1980, Авторское свидетельство СССР
М 1291961, кл. G 06 F 7/02, 1985. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ
ЗАДАННОГО ДИА11АЗОНА (57) Изобретение относится к автоматике и вычислительной технике, в частности к устройствам сортировки, и может быть использовано в качестве составной части блока нормализации порядка чисел с плавающей запятой в
„„SU„„1494000 А 1
ЭВМ, комплексах и системах с большой степенью интеграции. Целью изобретения является упрощение устройства.
Устройство содержит регистр — счетчик 1, счетчик 2, ассоциативный накопитель 3, регистр 4 адреса, информационный регистр 5, дешифратор 6, коммутатор 7, дешифратор 8, блок 9 управления, триггер 10. Основной принцип работы предложенной структуры состоит в регистрации поступления определенного двоичного числа, входящего в заданный диапазон чисел, на выходы устройства при помощи маркерной единицы в информационном накопителе с помощью ассоциативного накопителя и в дальнейшем при помощи ассоциативного накопителя формирования кодов двоичных чисел, поступающих для сортировки в отсортированном виде на выходах устройства. 1 s.n. ф лы, 2 ил.
1494000
Изобретение относится к автоматике и вычислительнс и технике, н частности к устройствам сортировки, и может быть использовано в качестве со5 станной части блока нормализации порядка чисел с плавающей запятой н Б!1, комплексах и системах на модулях с большой степенью интеграции.
Цель изобретения — упрощение устройства.
IIa фиг,! изображена блок-схема предлагаемого устройства; на фиг.2 блок управления, Устройство содержит регистр-счетчик 1, счетчик 2, ассоциативный накопитель 3, регистр 4 адреса, информационный регистр 5, дешифратор 6, коммутатор 7, дешифратор 8, блок 9 управления, триггер 10, входы 11 — 15 2р блока управления, ныходы 16-24 блока управления, Блок 9 управления содержит генератор 25, элементы И 26-28, триггер
29, элемент HJIH 30, триггеры 31 и 32, 25 элементы 33 задержки, элемент ИЛИ 34 и элементы 35-40 задержки, Устройство работает следующим образом.
Если перед проведением операции 3р сортировки необходимо изМенить диапазон, то на вход устройства поступает управляющий сигнал "Задание диапазона, который вызывает поянление управляющего сигнала на выходе 19 блока 9 управления, а через элемент
ИЛИ 30 вызивает появление управляющего сигнала на выходе 16 блока 9 управления, Одновременно на информационные входы устройства поступает дво- 4р ичное число, представляющее собой границу (нижнюю или верхнюю н зависимости от критерия сортировки ) диапазона. Сигнал на выходе !6 блока 9 управления разрешает прием кода этого 45 числа на реверсивный регистр-счетчик
I. Сигнал на выходе 19 блока 9 уи— равления устананлинает в "1" триггер
10, в результате чего комбинация сигналов на его выходах, а значит, и на первом и втором управляющих входах ассоциативного накопителя и коммутатора 7 определяют операцию записи по адресу в ассоциатинный накопитель и коммутацию информационных ныходон второго дешифратора 8. Счетчик 2 в исходном сc>ãòîÿíèè находится в состоянии "00...0". Сигнал ° "Задание
II диапазона и ступает также иа вход элемента 40 задержки, который нносиТ задержку на время, необходимое на вышеописанные действия, связанные с установкой отдельных элементов устройстна и др. Затем на выходе элемента 40 задержки появляется единичный сигнал, который через элемент
HJIVi 34 передается на ныход 22 блока
9 управления. На третий управляющий вход ассоциативного накопителя поступает тактирующий сигнал. Таким образом, по адресу, определяемому счетчиком 2 (в данном случае это "00. ° .0"), комбинация сигналов (как и любые другие комбинации), возникающая на выходах счетчика 2, поступает через регистр 4 адреса, второй дешифратор 8 и коммутатор 7 на адресные входы ас:-оциативного накопителя, н результате чего ассоциативный накопитель 3 записывается нижняя или верхняя граница задаваемого диапазона, Сигнал Задание диапазона" устанавливает в "1" находящийся в исходном состоянии триггер 29, а затем сигнал с выхода генератора 25 через э: емент И 26 поступает на вход элемента 33 задержки. Далее сигнал появляется на выходе элемента 33 задержки, а следовательно, и на выходе
17 блока 9 управления. 3 гот сигнал, поступая соответственно на второй управляющий вход регистра-счетчика 1 и иа управляющий вход счетчика 2„ является соответственно сигналом +I (в зависимости от критерия сортировки) и сигналом "+1" на управляющем входе счетчика. Далее сигнал появляетсн на выходе элемента 38 задержки, а следовательно, и на выходе !3 блока 9 управления, в результате чего на управляющих входах регистра 4 адреса и дешиа,ратора 8 появляются разрешающие сигналы, Хаким образом, следующий адрес, больший предьдущего, на единицу, поступает иа адресные входы ассоциативного накопителя, а на его информационные входы поступает двоичное число, на единицу большее или Mpньшее границы диапа.*она. Далее сигнал появляется на выходе элемента
37 задержки, а через элемент ИЛИ 34 на выходе 22 блока 9 управления. Таким образом, по слеиующему адресу в ассс циативный накопитель записывается следующее число диапазона. Затем с генератора 25 поступает следуюший сигнал и ирсцесс повторястся, Так! 4 94 ()(() аС СС>НИВ < ИБН«tf» ft(IK()IIJ»1 (ЕЛЬ ЗсlПОЛНЯ(TCB чf! Jldìè, составлян>шими требуемый эа даННЫй,!Ис»Пав< Н. I(<)a+>HJJ«eflux ПЕрЕГЧЕта с четчина 2 определяется количест5
ВоМ ячеек dcc Оциативно! о накопителя, т.е. величиной диапазона. I!o запол— нен»и ассоциативного нако»ителя счетчик 2 сбрасывается « "0" и сигнал с у««равпянццего вых(да счетчика 2 пог T$ — 10 паег на вход !4 блока 9 управления, устанавливая в "0" три! гРр 29, отключая тем самым генератор 25 от цепочки зпс м(- JJTC)B > ОбРспс чHB lюкlих запис1
Единичш!и <»гнк 1 г tt;,)B r гo BF, ла триггера 31 пос Гуп.)ет на «т< р;>й
Вход .)лгмента I! 2), п) 13 -.т» c игнап с
35, (1»с ра тор(3 25 1< pr- -3 э JeM(«3! 1 .«1И 30 по 3 упает на выход 16 c>stc>KFI 9 управления, 1 лере.3 1лсм(-и l 35 (адержки. и 1»!ел!РНТ И.(1И 34 — нс) к> tx l "2 бпс>9 vJ! p» J(ti (kf f»st ° (:.1»l H 3 Jl I l > 13 ых с>дс 1 с),1()
Г) 1()KB 9 у»раf(JI< ««ия ра.»р< !««,)(т запись
wftcJt;3 и 3 и< (tt»i>B;) TeJif гти сортируемь«х чисел 13 р. гис тр-счетчик 1, а сигнал на выходе 2 . б>пока 9 ч1!равле«»ия
ЗTC Pñl 3 P f f>I;3«<>f » lit Т<3 K 1 1»РУН)ЩИИ Г ИГH;1 JI > с по<.ту»аюнц!й fl;3 т!.,(«ий управляющий с. .о B< r<>llf»da l»i»«! ГO JIB«< of»T(.JIH. ТаКИМ Обра 3C,M, t!f! l: igrnpM,»»»ОННЫР ВХОДЫ ассопиати«но« < нанон«»те)«ч поступает 1 3»Г»«О > с P;1 « H (ll и(l ОРО« (> <1, 1ои xojlf1 T
13 аг С « tlf»<3 Tftf»J»r>M Jt;3 K<)IJ ИТС . BI!<. М «>ВКОПИтЕЛЕ Г< )>езультат сравИеа»Н(>М": lr;3< Or>.JИа1!с1 3ОН" IИ(t, I! > и llc3 Гr)(>Т«С ТСТВУЮ «3! !х< .Ip аг « I!J»FI Tèâ— tfe I!HB llr)ilr, И tf ц! f "J у п р а ..: I н (ц (н< > !» H !K< >ri l»1 f. Jisr !!< >3«3 !>! Гт< Я f lèíè÷ ><Ы<1 ГИ« !r;!Ji > tl(>r 1 у» «НШ!ИН1 fl;r (сдИНИЧ >!Ь!1! <3 X (д (<)r) 1 «("! r 13 V)r ц!Р I <1 рс» 3 (>Яда ИН чисел зад »ваемо! диапазона, )Г ;1але Р можно подавать k! . 1»н(3>)орма циОнные «ходы по<.ледо«3TC пьf:oñò«дноичш lx чи(с л, по))лежащих <-ортировк Р . По Риги;»лу "1!ачало ОГ!с р«»ц«»и", по<. тупан>щему на вхс>д 1 2 блока 9 управ- 2() пения Возникает сигнал на Bf txc)jfe 20 блока 9 управл ния, B ре»ультате чсгo триггер 31 уст »навли«3(»етг«1 В "1И. Сиги(»п на вь«ходе 20 блока 9 управ— пения устанавли«ае T В "<) триггер 7!> 1(), В рс зультате vf i о комбинация с»гнало«. г его выхода опред(.!Яет опера— 1 .ИН 3сз!1ИГИ 11О CIPf» 3HНКУ ДЛЯ ВС(Опием т»«когс> н;»к<;пит< ля и ком.!утацию IF øk»(I)па 3 <>;-,3 Г) на ()др< Гные Ilxr)jll аг< оциа- 30 Telf3ll<)I r) Jl к< п>»тепя чере ) коммутатор («>ормап«»о«»ног<) регистра 5, представляK)ttff !.о гобой m — p(3çðÿjfíf Jé регистр, где щ — длина диапазона чисел. Пдновремснно на выходе элемента 35 задер)3<ки появляет< я единичный сигнал, что означает появление сигнала на выходе 23 блока 9 управ!»ения, с) результате управлян щий гигнал Принять код погтупает на первый управляющий вход информационногo регистра 5. Таким образом, в разряд информационного регистра 5, соответствующий записанному в ассоциативный накопитель числу, РаВНОМУ JJOC Tytl»I»! jl,r !1 «!Р«»!
I) f3ccofif»c) Tf;Irffot! 1!акоп»теле 3 все Ч»С Пс» Э сЭДсэ ННО 1 (! ll It i!It l 3 ОН В Нсэ ХОДЯТСЯ «ш р>!дке 13(1 »раста!3«!я или убывания, Т . (. !JOB:!Ед 1«а ТC Ji f,«tr) Cт Ь ИХ ОТСОртнр >«ВHH. !1 шl(с рмл lf» нном регистре 5 каждый ра 3psljl гo(13«(тгтву т опредеJtf f«i<)fi ячс ике аг«-)ill!;ITI»B«ln!.n накопитсля, Itpf»÷åM младцп!й разряд соответГт«УЕ T ЯЧС.ЙКС < »J»3>II>ll»M 3jf 1FOOM HPH 3»аки B ассоц»а t икн(и нако<. Геле эк«икапентны чи(:i;3;», кс торь!е могут пос ту»ат« на инфорн«,31:ис нные входы устpoJt< TBа. Таким образсм, единицами в p;3Bps3jff3x»H<1<)pM>3ifff<>I3H<)ro регистра 5 Отыс ЧРНЫ т(Я le»1 И аССОцИатИВНОГО Нак(»иц еля 3«С)р«»(3«1(3!Си записанные в которых равны посту»иншим на информаЦИОННЫЕ ВХОДЫ Д t«3 СОРТИ))ОВКИ ДВОИЧ ным числам. 1!р(<ма»р»кая информационныи регистр 5 с младших разрядов и выдавая на выход устройства двоичные числа из ячеек ассоциативного накопителя 3, лот(р!с соответствуют РДИНИЧНЫМ Ра »РЯД lti Инф»РМаЦИОННОГО ppl »стра 5, тем Г;)мын! «ыдается на вых )д устройc I f»ct II< (тупш»шая на информа!!ионные входь! у< троигтва последова3 ельk«)< T«jff«»«3««>x ««cc JJ y)t e B отсор1 lrp(В (3HHOM ВИ;!(. 1494000 Входы дешифратора 6 Выходы дешифратора 6 (I — m+ I ) (1 — m) О О О О О О 1 0 О О 1 О 001 1 Х Х ... Х Х О 1 Х ... Х Х О О 1 ... Х Х ° ° ° 0 0 0 ... I X О О О ... О 1 000...ОО ° ° ° О О О 1 О О 0 1 О О О 1!!р«це< с просм<>тра и>«<3>ормацион««ого регистра 5 и выдачи отс<>pòltðoâattíol> последовател3 ности осуществляется следующим < бразом, Сигнал "Конец сор5 тнруемой последовательности поступавT на единичнь«й вход триггера 32, а сигнал н» его единичном выходе формирует единичный сигнал на выходе 21 блока 9 управления, определяя на чет- 1О вертом управлям>щем входе ассоциативного накопителя 3 операцию Чтение по адресу< . Сигнал с единичного выхода Исходя из принедеьп«ого в таблице COOTI3tЕTCТВИЯ В3«ДНС> ЧТО КОД С ВЬ«ХОДОВ первого дешифратора Ь, поступая через коммутатор 7 на адресные входы ассоциативн< го накопителя 3, приводит к возбуждению адресной шины чтения, соответствующей той ячейке ассоциатинного накопителя, которая соответствует выделенной первым дешифратором 6 младшей единице кода, зафиксированного на информационном регистре 5 ° Так как выходы первого дешифратора 6. соединены с инверсными нходзми ин- формационнОГО регистра 51 тО фОрми 40 руемый дешифрато ром 6 код одновременно с поступлением на адресные входы ассоциатив««ого накопителя 3 гасит младшую единицу кода, зафиксированного на информационном регистре, в 45 результате чего в следующем такте младшей вь«деленно: единицей будет уже следующая по отношению к выделенной н данном такте. Сигнал с элемента И 28 помимо выхода 21 блока 9 управления 3«ос тупзет на вход э «емента 36 задержки и ttn истечении времени, необходимого для дешифрации кода с информационного регистра 5 и коммутации код1 с выходов первого де55 «>«3«<1>р<«тор<«6, поступает на адресные нходл«<<сс >циативного накопителя 3, а:«a t ått ч< ре.> эле>«е1«т ШИ> 34 — H<1 Bbtход 2? б:. >ка 9 управления, в резуль— Ю триггера 32 поступает на второй вход элемента И 28, а сигнал с генератора 25 «н>ступает на выхоц 23 блока управл HH>3 и < оответственно, на второй управляющий вход информационног<> !>е-. гистра 5, что эквивалентно подаче сигнала Выдать код с информацио».ог<> регистра, Код с информационного регистра 5 поступает на входы первого дешифратора 6. Дешифратор 6 реализует следующую систему функций: тате чего на третий разрешающий вход ассоциативного накопителя поступает тактирующий сигнал и на HH о р м у л а и з î б р е т е н и 1. Устройство для сортировки чи< ел зад;3НН «Г > laàÏàÇÎÍà, СОцЕржащЕЕ дЕ1494000 шифратор и блс к управления, о т л ич а ю ш е е с я тем, что, с целью упрощения устройства, оно содержит ассоциативный накопитель, информаци5 онный регистр, регистр-счетчик, счетчик, регистр адреса, второй дешифратор, коммутатор и триггер, причем информационные входы устройства соединены с информационными входами регистра-счетчика, выходы разрядов которого соединены с первой группой информационных входон ассоциативного накопителя, информационные выходы первой группы которого являются информационными ныходами устройства, а информационные выходы второй группы подключены к соответствующим прямым входам информационного регистра, выходы разрядов которого соединены с входами первого дешифратора, m выходов которого соединены с первой группой информационных входон коммутатора (m — емкость ассоциативного накопителя) и с соответстнующими инверсными входами информационного регистра, (m+I) — é выход дешифратора является выходом конца работы устройства и соединен с первым входом блока управления, второй и третий входы которого являются соответственно входами начала операции и задания диапазона устройства, четвертый вход блоблока управления подключен к выходу переполнения счетчика, выходы разря— дов которого соединены с информационными входами регистра адреса, выходы разрядов которого соединены с входами второго дешифратора, выходы которого соединены с второй группой информационных входон коммутатора, первый и второй входы которого соединены соответственно с прямым и инверсным выходами триггера, с первым и нторым управляющими входами ассоциативного накопителя, адресные входы которого соединены с выходами разрядов коммутатора, первый вьгход блока управления соединен с входом разрешения записи регистра-счетчика, второй выход — со счетными входами регистра-счетчика и счс гчика, третий выход — с входом разреkklk. kkèÿ записи регистра адреса и сз рлбирующим входом нторого дешифратора, четвертый и пятый выходы — соответственно с входами установки н "1" и "0" триггера, шестой и седьмой ных цы — соответственно с третьим и ч авертым управляющими входами ассоциативного накопителя, восьмой и девятый выходы — со ответственно с входами записи и считывания информационного регистра, пятый вход блока управленйя является входом конца сортируемой последовательности устройства, 2. Устройстно по п. I, о т л и ч а ю щ е е с я тем, что блок y ïравления содержит генератор импульсов, три триггера, три элемента И, два элемента ИЛИ, семь элементов задержки, причем выход генератора импульсов соединен с первыми нходами первого, второго и третьего элементов И, первый, второй и четвертый входы блока управления соединены соответственно с входами установки в "0" первого, в "1 второго и н "0" третьего триггеров, прямые выходы которых соединены с вторыми входами соотнетственно первого, второго и третьего элементов И, выход второго элемента Р соединен с первым входом первого элемента ИЛИ, выход которого является первым выходом блока управления, выход третьего элемента И соединен через перный элемент задержки с входом второго элемента задержки и является вторым выходом блока управления, выход второго элемента saдержки является третьим выходом блока управления и соединен через третий элемент задержки с первым входом второго элемента ИЛИ, третий вход блока управления соединен с входом установки н "I" третьего " иггера, с вторым входом первого элемента ИЛИ, является четвертым выходом блока упранлення и через четнертый элемент задержки соединен с нторым входом второго элемента ИЛИ, вход установки в "I" второго триггера соединен с пятым выходом блока управления, шестой вьгход которого соединен с пряйым вы ходом первого триггера, выход второго элемента И через пятый элемент задержки соединен с входом шестого элемента задержки и с третьим входом второго элемента ИЛИ, выход которого является седьмым выходом блока управления, восьмой выход которого подключен к выходу шестого элемента задержки, выход первого цемента И является девятым выходом блока управления и соединен через седьмой элемент задержки с четвеpTklkl входом второго 149400() 12 в "1" первого и в "0" второго триггеров. элемента ИЛИ, пятый вход блока управлЕния соединен с входами установки го 22 Аа.2 Заказ 4111/45 Тираж 668 Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР 113035, 11осква, Ж-35, Раушская наб., д. 4/5 Проиэводстненно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101 13 19 f2 Составитель В.Козлов Редактор Л.Ревин Техред Л.Сердюкова Корр ор Н.Король 23 29 
