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

со

4

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

Цель изобретения - упрощение устройства.

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

Устройство содержит регистр-счетчик 1, счетчик 2, ассоциативный накопитель 3, регистр 4 адреса, информа- ционный регистр 5, дешифратор 6, коммутатор 7, дешифратор 8, блок 9 управления, триггер 10, входы 11-15 блока управления, выходы 16-24 блока управления.

Блок 9 управления содержит генератор 25, элементы И 26-28, триггер

10

15

20

элемента 40 задержки, которьш вно сив задержку на время, необходимо на вьпчеописанные действия, связан с установкой отдельных элементов ройства и др. Затем на выходе эле мента 40 задержки появляется единичный сигнал, который через элем ИЛИ 34 передается на выход 22 бло 9 управления. На третий управляющ вход ассоциативного накопителя по ступает тактирующий сигнал. Таким образом, по адресу, определ мому счетчиком 2 (в даннс.м случае это 00...О), комбинация сигнало (как и любые другие комбинации), никающая на выходах счетчика 2, п ступает через регистр 4 адреса, в рой дeшифpatop 8 и коммутатор 7 н адресные входы ассоциативного нак теля, в результате чего ассоциати ный накопитель 3 записывается ниж или верхняя граница задаваемого д пазона . Сигнал Задание диапазона

29, элемент ШТИ 30, триггеры 31 и 32, 25 устанавливает в Г находящийся в

35

элементы 33 задержки, элемент ИЛИ 34 и элементы 35-40 задержки.

Устройство работает следующим образом.

Если перед проведением операции сортировки необходимо изменить диапазон, то на вход устройства поступает управляющий сигнал Задание диапазона, который вызьшает появление управляющего сигнала на выходе 19 блока 9 управления, а через элемент ИЛИ 30 вызьшает появление управляющего сигнала на выходе 16 блока 9 управления. Одновременно на информационные входы устройства поступает дво- до ичное число, представляющее собой границу (нижнюю или верхнюю в зависимости от критерия сортировки )диаца- зона. Сигнал на выходе 16 блока 9 управления разрешает прием кода этого 45 числа на реверсивный регистр-счетчик 1. Сигнал на выходе 19 блока 9 управления устанавливает в 1 триггер 10, в результате чего комбинация сигналов на его выходах, а значит, и на первом и втором управляющих входах ассоциативного накопителя и коммутатора 7 определяют операцию записи по адресу в ассоциативный накопитель и коммутацию информационных выходов второго дешифратора 8. Счетчик 2 в исходном состсчямии находится в со- сто янии 00...О. Сигнал. Задание дилпазо)1а шк-тупает также т вхс Д

исходном состоянии триггер 29, а тем сигнал с выхода генератора 25 рез элемент И 26 поступает на ьхо элемента 33 задержки. Далее сигна 30 появляется на выходе элемента 33 держки, а следовательно, и на вых 17 блока 9 управления. Этот сигнал поступая соответственно на второй равляющий вход регистра-счетчика и на управляющий вход счетчика 2, ляется соответственно сигналом t (в зависимости от критерия сортир ки) и сигналом il на управляющем входе счетчика. Далее сигнал появл ется на выходе элемента 38 задержк а следовательно, и на выходе 13.бл ка 9 управления, в результате чег о на управляющих входах регистра 4 а реса и дешифратора 8 появляются ра решаюп1ие сигналы. Таким образом, с дующий адрес, больший предь1дущего на единицу, поступает на адресные входы ассоциативного накопителя, а его информационные входы поступает двоичное число, на единицу большее или меньшее границы диапазона. Дал сигнал появляется на выходе элемен 37 задержки, а через элемент ИЛИ З на выходе 22 блока 9 управления. Т ким образом, по следующему адресу в ассоциативн ый накопитель записыв ется следующее число диапазона. За тем с генератора 25 поступает след щий сигнал и процесс повторяется.

50

55

0

5

0

элемента 40 задержки, которьш вносив задержку на время, необходимое на вьпчеописанные действия, связанные с установкой отдельных элементов устройства и др. Затем на выходе элемента 40 задержки появляется единичный сигнал, который через элемент ИЛИ 34 передается на выход 22 блока 9 управления. На третий управляющий вход ассоциативного накопителя поступает тактирующий сигнал. Таким образом, по адресу, определяемому счетчиком 2 (в даннс.м случае это 00...О), комбинация сигналов (как и любые другие комбинации), возникающая на выходах счетчика 2, поступает через регистр 4 адреса, второй дeшифpatop 8 и коммутатор 7 на адресные входы ассоциативного накопителя, в результате чего ассоциативный накопитель 3 записывается нижняя или верхняя граница задаваемого диапазона . Сигнал Задание диапазона

5 устанавливает в Г находящийся в

5

о 5

исходном состоянии триггер 29, а затем сигнал с выхода генератора 25 через элемент И 26 поступает на ьход элемента 33 задержки. Далее сигнал 0 появляется на выходе элемента 33 задержки, а следовательно, и на выходе 17 блока 9 управления. Этот сигнал, поступая соответственно на второй управляющий вход регистра-счетчика I и на управляющий вход счетчика 2, является соответственно сигналом tl (в зависимости от критерия сортировки) и сигналом il на управляющем входе счетчика. Далее сигнал появляется на выходе элемента 38 задержки, а следовательно, и на выходе 13.блока 9 управления, в результате чег о на управляющих входах регистра 4 адреса и дешифратора 8 появляются раз- решаюп1ие сигналы. Таким образом, следующий адрес, больший предь1дущего, на единицу, поступает на адресные входы ассоциативного накопителя, а на его информационные входы поступает двоичное число, на единицу большее или меньшее границы диапазона. Далее сигнал появляется на выходе элемента 37 задержки, а через элемент ИЛИ ЗА - на выходе 22 блока 9 управления. Таким образом, по следующему адресу в ассоциативн ый накопитель записывается следующее число диапазона. Затем с генератора 25 поступает следующий сигнал и процесс повторяется. Так

0

5

accfMinarnBHL.nl накопит елъ заполняется чи; Л 1ми, составляющими треебуемый заданный диапа-лч). Козф(} ицнент пересчета счетчика 2 определяется количеством ячеек ассоциативно о накопителя, т.е. величиной диапазона. По заполнении ассоциативного накопителя счет чик 2 сбрасывается н О и сигнал с

формапяонного рег истра 5, представляющего собой т-разряднмй регистр, где m - длила диапазона чисел. Одновременно на выходе элемента 35 задержки появляется единичне-гй сиг нал, что означает появление сигнала на выходе 23 блока 9 управления, В результате управляющий сит нал Принять код по

Изобретение относится к автоматике и вычислительной технике ,в частности, к устройствам сортировки, и может быть использовано в качестве составной части блока нормализации порядка чисел с плавающей запятой в ЭВМ, комплексах и системах с большой степенью интеграции. Целью изобретения является упрощение устройства. Устройство содержит регистр - счетчик 1, счетчик 2, ассоциативный накопитель 3, регистр адреса 4, информационный регистр 5, дешифратор 6, коммутатор 7, дешифратор 8, блок управления 9, триггер 10. Основной принцип работы предложенной структуры состоит в регистрации поступления определенного двоичного числа, входящего в заданный диапазон чисел, на выходы устройства при помощи маркерной единицы в информационном накопителе с помощью ассоциативного накопителя и в дальнейшем при помощи ассоциативного накопителя формирования кодов двоичных чисел, поступающих для сортировки, в отсортированном виде на выходах устройства. 1 з.п. ф-лы, 2 ил.

упраиляницего выхода счетчика 2 посту- ю ступает на первый управляющий вход

пает на вход 14 блока 9 управления, устанавливая в О триггер 29, отключая тем самым г енератор 25 от цепочки элементов, обеспечивающих запись чисел задаваемого диапазона.

Лалее можно подавать н. информационные ВХОД1.1 послед1 ватель.;ость дво- ИЧН1.ГХ чисел, подлежащих сортировке.

По сигналу Начало операции, nor ступан)щему на вход 12 б.чока 9 управления возникает сигнал на выходе 20 блока 9 управления, в результате чего триггер 31 устанавливается в 1. Сигнал на выходе 20 блока 9 управления устанавливает в () триггер И), в результате чего комбинация сиг - налгч1 с его выхода определяет операцию записи по для ассоциативного нак(;пителя и коммутацию дещиф рат ор.ч на адресные входы ассоциа- тинного накопителя чере коммутатор 7.

Кдиничн(, спг нл.ч с прям Я о выхода тригтера 31 посгуп.чет на второй вход элемента И 27, njij OTi i сигнал с генератора 25 ч(рез ) И.ПИ 30 поступает на вьгход 16 блока 9 управления, а через uuiMf-in 35 задержки.

и элемент ИЛИ 34 - на пых

блока 9 упранг ения. (. иг нал нл В1.1ходе 16 блока 9 унрпнленця разрешает запись числа из нос ледова тел1 ности сортируемых чисел в рет ис тр-гчетч ПК I, а сигнал на выхг)де 22 блока 9 унравления - зтс.-. разрешаюрщн гак 1 ирую1ций сигнал, постунающиГ на третий управляющей ьход ассоциа ИЫ1(:Г(; накопители. Таким образом, на 1;иформаии пп1ые входы ассоциативно (1 накопителя поступает число, сравнение i . ropoi o происходит в ассоциатинн()м накопителе- 3. Так как постунивп ее чис Ь 1:рИ1 г,ллежит за- ;:исанному ii аг сен |ч г нвнo Р .акопителе диапазону чисе,-,. гс ))езультат сравнения поло: и г e:(Mi и на соответствующем унра. -.лянч н м и1.1Х(1ле ас:сопиатив- нако} и 1 e. i.vi ги1нв; етс ч единичный , Г10С1 унаюищй на единичный вход с:оотве | гт HVT Unei i) разряда ининформационного регистра 5. Таким образом, в разряд информационного регистра 5, соответствующий записанному в ассоциативш 1Й накопитель числу, равному пocтyrIИB lle(y на информацион- входы устро11ства коду иэ подлежащей сортировке последовательности, записывается единица, свидетельствую- П(ая о том, что данное число на инфор0

5

мационные входы устройства поступило. Далее с генератора 25 поступает следующий сигнал и вышеописанный процесс повторяется до поступления на вход 15 блока 9 управления управляющего сигнала Конец сортируемой последовательности. Триггер 31 устанав- липается в О, в результате чего далы1ей 11ая запись в информационный регистр 5 и связанные с ней действия

0 не происходят.

Б ассониа накопителе 3 все числа заданногс диацлзона находятся р порядке возрастания или убывания, т.е. псч ледовательность их отсортиg рована. В ццсЬирмшни Нном регистре 5 кажды разряд соответствует опреде- jieHHoii ячеГше ассоциативного накопителя, причем младший разряд соответствует ячейке с м. 1ад11Н1М адпесом. Признаки в асс(1циат ивном наксн. -геле эквивалентны числам, которые могут по- стунат). на информационные входы устройства. Таким образом, единицами в разрядах инф1Ормацис }шого регистра 5 отмечены те ячейки ассо1;иативного на- конителя З Признаки записанные в которых равны пост унившим на информационные д, 1н с 1ртировки двоичным числам. Иргн мат ривая информа1Ц1- онный регистр 5 с младших разрядов и выдавая на выход устройства двоичные числа из ячеек ассоциативного на- к(.)нителя 3, котсрые соответствуют единичным разрядам ин1| ормационного регистра 5, тем caNii.iM выдается на выход устройства 1ии:т-упившая на информационные входы у(:т)ойства последовательность дв(п1чных чисел уже в отсор- ти1)ованном виде.

0

Ь

0

5

Ilptniecc просмотра информационного регистра 5 и иыдачн отсортированной 11оследоватрл ности осуществляется следующим образом. Сиг-нал Конец сортируемой последовательности поступает на единичный вход триггера 32, а сигнал на его единичном выходе формирует единичный сигнал на выходе 2 блока 9 управления, определяя на чет- вертом управляющем входе ассоциативного накопителя 3 операцию Чтение по адресу. Сигнал с единично1 о выхода

;TВходы дешифратора 6 I Выходы дешифратора 6 (1 - т)(1 -т+1)

Исходя из приведенного в таблице соответствия видно, что код с выходов первого де111ифратора 6, поступая через коммутатор 7 на адресные входы ассоциативного накопителя 3, приводит к возбуждению адресной шины чтения, соответствующей Toii ячейке ассоциативного накопителя, которая соответствует выделенно первым дешифратором 6 младшей единице кода, зафиксированного на информационном регистре 5. Так как выходы первого дешифратора 6 соединены с инверсньми входами информационного регистра 5, то форми- руемый дешифратором 6 код одновременно с поступлением на адресные входы ассоциативног о накелтителя 3 гасит младшую единицу кода, зафиксированного на информационном регистре, в результате чего в следующем такте младшей выделенно,: единицей будет уже следующая по отношению к выделенной в данном такте. Сигнал с элемента И 28 помимо выхода 21 блока 9 управления гтоступает на вход элемента 36 задержки и по истечении времени, необходимого для дешифрации кода с информационного регистра 5 и коммутации кода с выходов первого шифратора 6, поступает на адресные входы ассоциативного накопителя 3, а загем через племет.т lillli 34 - на выход 22 блока 9 управления, в резуль

триггера 32 поступает на нтороГ; вход элемента И 28, а сигнал с генератора 25 поступает на выход 23 блока управления и соответственно, на второй управляю1дий вход информационного pe гистра 3, что эквивалентно подаче С пгнала Выдать код с информациоь.ю- го регистра. Код с информационного регистра 5 поступает на входы первого дешифратора 6. Дешифратор 6 реализу- ei следующую систему функций:

0

5

Q

5

0

5

тате чего на третий разрешающий вход ассоциативного накопителя поступает тактируюи1,ий сигнал и на информационных выходах ассоциативного накопителя появляется соответствующее такту выдачи отсортированной последовательности двоичное число (в описываемом первом такте - первое - наибольшее или наименьшее). В дальнейшем с 1 енератора 25 поступает следующий импульс и процессы, описанные выше, поитчрякггся до тех пор, пока на информационном рс Т истре 5 не будет зафиксирован код 00...О, что свидетельствует о том, что на выход устройства выдана упорядоченная последовательность двоичных чисел. Тогда пер- Bbii i дешифратор 6 формирует на своем выходе единичный сигнал, что соответствует появлению уп;.-1вляюще1 О сигнала Конец операции ча уп1 ав;1яющем выходе устройства. Сигнал с (ra-t-1 )-го выхода первого дешифратора п поступает также на инверо ый вход триггера 32, устанавливая его в О, в результате чего устройство переходит в исходное состояние и готово к приему следующей последовательности чисел г1ОД-чежап1ей сортировке,

3 о р м у л а и 3 о б р е т ( н и ;

1, Устройство для сортировки чисел заданного диапазона, содержащее дешифратор и блок управления, о т л и- ч а ю U1 е е с я тем, что, с целью упроп;ения устройства, оно содержит ассоциативный накопитель, информационный регистр, регистр-счетчик, счетчик, регистр адреса, второй дешифратор, коммутатор и триггер, причем информационные входы устройства соединены с информационными входами регистра-счетчика, выходы разрядов которого соединены с первой группой информационных входов ассоциативного накопителя, информационные выходы первой группы которого являются информационными выходами устройства, а информационные выходы второй группы подключены к соответствующим прямым входам информационного регистра, выходы разрядов коюрого соединены с входами первого дешифратора, m выходов которого соединены с первой группой информационных входов коммутатора (т - емкость ассоциативного накопителя) и с соответствующими инверсными входами информационного регистра, (т+1)-й выход дешифратора яв ляется выходом конца работы устройства и соединен с первым входом блока управления, второй и третий входы которого являются соответственно входами начала операции и задания диапазона устройства, четвертый вход бл блока управления подключен к выходу переполнения счетчика, выходы разрядов которого соединены с информационными входами регистра адреса, выходы разрядов которого соединены с входами второго дешифратора, выходы которого соединены с второй группой информационных входов коммутатора, первый и второй входы которого соединены соответственно с прямым и инверсным выходами тригг ера, с первым и вторым управляющими входами ассоциативного накопителя, адресные входы которого соединены с выходами разрядов коммутатора, первый выход блок управления соединен с входом разрешения записи регист)а-счетчика, второй выход - со счетными входами регистра-счетчика и счс1чика, третий выход - с входом разрешения записи регистра адреса и стробирующим входом второго дешифратора, четвертьй и пятый выходы - соответственно с входами установки в 1 и О триггера, шестой и седьмой выходы - соответственно с третьим и чстертым управляю0

5

0

5

0

5

0

5

0

5

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

элемент HJTli, пятый вход блока управ- в 1 первого и в О второго триг- лёния соединен с входами установки i-еров.