Устройство сортировки чисел

СОЮЗ СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 06 Р 7/ ОПИСАНИЕ ИЗОБРЕТЕНИЯ л. Целье ие быстит ш- ига начиная имально максима льности м а о исла до упорядоч ности чисел СУДАРСТВЕННЫЙ НОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ ВТОРСНОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССРУ 478303, кл, С 06 Р 7/04, 1973.Авторское свидетельство СССРВ 826339, кл. С 06 Р 7/06, 1979,(54) УСТРОЙСТВО СОРТИРОВКИ ЧИСЕЛ(57) Изобретение относится к вычительной технике и может быть испозовано для построения устройств с ЯО 1441384 А 1 орядочивания чисе является повышенУстройство содерж льцевые регистры сдв И 2, элементы ИЛИ 3, элетриггеры 5, 6, 7, элемент И-ИЛИ 8, блокУстройство выполняет дов сортируежх чисел, тарших разрядов, выбор о из них, затем исключвльного числа из последочисел, выбор максимально оставшихся чисел и т,д. ивания всей последовательз.п. ф-хы, 2 ил. тировки и у изобретения родействия. разрядные к 1, элементы ; менты 2 И-ИЛИ управ ляюппв управления анализ разрИзобретение относится к вычислительной технике и может быть использовано для построения устройств сортировки, ранжировки и упорядочиваниячисел.Целью изобретения является повышение быстродействия.На фиг. 1 изображено устройствосортировки чисел, на фиг. 2 - блокуправления,Устройство (фиг. 1) содержит шразрядные кольцевые регистры 1 сдвига, элементы И 2, элементы ИЛИ 3,элементы 2 И-ИЛИ 4, триггеры 5-7, управляющий элемент И-ИЛИ 8, блок 9 .управления, вход 10 запуска, выходы11-17 блока управления, адресныйвыход 18, выход 19 отсортированногочисла, информационные входы.Блок управления содержит двойнойтриггер 20, генератор 21 импульсов,счетчик 22, дешифратор 23, элементыИ 24 и 25, элемент НЕ 26, элементИ 27, элемент НЕ 28,В кольцевые регистры 1,- 1 п каждого модуля устройства массив сортируемых чисел записывается любымизвестным способом. По сигналу,поступающему на вход 10 блока 9 управления с помощью синхроимпульсовс, и, поступающих из генератора2 1 импульсов, двойной триггер 20,триггеры 5-7 всех модулей устанавливаются в состояние " 1", этими жесигналами управления и синхроимпульсами счетчик 22 устанавливается всостояние "0". После этого установившееся состояние " 1" двойноготриггера 20 с помощью очередной серии синхроимпульсов , иустанавливает счетчик 23 в состояние00001 (младшие разряды справа).Это же единичное состояние триггера20 разрешает прохождение синхроимпульсов . , и Г через элемент И 24на кольцевые регистры 1,-1 каждогомодуля. С помощью этих синхроимпульсов начинает сдвигаться на одиндвоичный разряд информация в кольцевых регистрах 1, -1. Допустим, чтов старшем разряде одного из кольцевых регистров 1, - 1 цифра равна 1,тогда на выходе управляющего элемента И-ИЛИ 8 сигнал будет равен единич.ному состоянию, т.е . состоянию, разрешающему прохождение сигналов через схемы И элементов 2 И-ИЛИ 4, Другими словами, нулевое состояние, например, в старшем разряде кольцевого регистра 1 одного из модулей поступает через первый вход элемента2 И-ИЛИ 4 на его выход. С приходомсинхроимпульса б, с выхода 16блока 9 управления поступает сигнал,который устанавливает триггер 5 всостояние "0". Второй синхроимпульспоступающий с выхода 17 блока уп.равления, устанавливает триггер 7в состояние "0". Состояние старшегоразряда всех кольцевых регистров переписывается в самый младший их разряд, На место старшего разряда посту"пает значение цифры разряда с весомна единицу меньше . Аналогично выходстаршего разряда всех кольцевых регистров 1, -1 в случае единичногосостояния на выходе управляющегоэлемента И-ИЛИ действует на соответствующие триггеры 5 и 7.Если выход управляющего элементаИ-ИЛИ 8 соответствует нулевому сос тоянню, а этой случай, когда всецифры кольцевых регистров 1 -1 рассматриваемого разряда равны нулю, всфэлементы И-ИЛИ, одним из входов которых являются инверсные выходы коль цевых регистров 1,-1, закрыты, исброс триггеров 5 и 7 устройства всостояние "0" с приходом синхроимпульсов , ине осуществляется.В этом случае иифорФмщия в кольцевых 35 Регистрах 1-1сдвинется на одинразряд. Сброс триггеров 5 и 7 в состояние "0" свидетельствует о том,что число (содержимое данного кольцевого регистра) является меньшим пЬвеличине, чем числа (других кольцевых регистров 1 других модулей), соответствующие триггеры 5 и 7 которых находятся в состоянии " 1" . Управляющий элемент И"ИЛИ 8 исключаетих операции сортировки с помощью сигнала, поступакщего из прямого выхода данного триггера 7. Нулевое состояние этого выхода блокирует,информацию, поступаюшую из кольцевого регистра 1; на соойетствующий входуправляющего элемента И-ИЛИ 8. Этаблокировка действувт в течение очередных сдвигов в кольцевых регистрах 1-1 до окончания полного цикла сдвига, который . измеряется коли.чеством сдвигов, равных ш, где шразрядность чисел. В течение ш-госдвига, а именно иа этапе действиясинхроимпульса с помощью сигнала,41384 второй группы и входу запуска блока40 управления, первый и второй выходы 50 з 14 поступающего с блока 9 управления с выхода 15, д-й триггер 6 сбрасываетйя в состояние "О", если соответствующий триггер 5 в это время находится в состоянии "О". С наступлением состояния счетчика 22 блока 9 управления, равного числу ш, подача сннхроимпульсов с выходов 16 и 17 на входы кольцевых регистров 1,-1 прекращаетсяЭто осуществляется подачей запрещающего сигнала из дешифратора 23 на элемент И 28. В это же время (состояние сче;"чика 23, равное числу ш) происходят перезапись состояния д-го триггера 6 в триггер 5 . Прямые выходы триггеров 7 являются адресными выходами 18 устройств, с них считывается адрес наибольшего числа иэ чисел, сортируемых в течение предьдущих ш сдвигов . Само же это число считьвается в течение этих ш сдвигов поразрядно на выход 19. После ш сдвигов в течение действия очередной посылки пары синхроим-. пульсов Я, и с, состояния триггеров 5 и 7 приобретают состояние триггера 6 предлагаемого устройства, 1-е, триггеры 5 и 7 каждого модуля будут в состоянии "О", если в соответствующем .-м кольцевом регистре 1 находится число, ранее отсортированное в ранг большйх чисел. Состояние "О" прямого выхода триггера 7 исключает из дальнейшей сортировки соответствующий кольцевой регистр 1 с помощью управляющего элемента ИИЛИ 8Состояние " 1" триггеров 5 и 7 говорит о том, что содержимое соответствующего д-го регистра, исключенное в течение предыдущей сортировки (ш сдвигов) теперь участвует в сортировке . Процедура очередного этапа сортировки соответствует ранее описанной процедуре, т.е. в течение очередных сдвигов на выход 19 устройства последовательно поступает разряд за разрядом следующее по величине число из сортируемого массива, а по окончании ш-го сдвига на выход 18 поступает адрес этого числа. Формула из обретения 1, Устройство сортировки чисел, содержащее и ш-разрядных кольцевых регистров сдвига, где и - чис 5 10 15 20 25 30 ло сортируемых чисел, информационныевходы которых являются информационными входами устройства, управляющий элемент И-ИЛИ, п элементов 2 И-ИЛИдва элемента И, элемент ИЛИ, блокуправления, причем прямой выход старшего разряда .-го ш-разрядного кольцевого регистра сдвига (1,п) соединен с управляющим входом.-го элемента И управляющего элемента И-ИЛИ, о т л и ч а ю щ е е с ятем, что, с целью повышения быСтродействия, в устройство введены тригруппы триггеров пэлементов И,иэлементов ИЛИ, причем инверсныйвыход старшего разряда .-го ш-разрядного кольцевого регистра сдвига соединен с первым входом первого элемен"та И .-го элемента 2 И-ИЛИ,. выход которого соединен с входом установкив О -го триггера первой группы,прямой выход которого подключен квходу установки в "О" -го триггеравторой группы и входу установки вединичное состояние .-го триггератретьей группы, прямой выход которого является .-и адресным выходомустройства и соединен с информациой-ным входом -го элемента И управляют щего элемента И-ИЛИ, выход которого является выходом отсортированногочисла устройства и соединен с вторымвходом второго элемента И -го элемента 2 И-ИЛИ, вход запуска устройства подключен к первым входам всехэлементов ИЛИ входам установки в единичное состояние всех триггеров которого подключены к входам управ" ления сдвигом всех ш-разрядных регистров сдвига, а третий выход соединен с первыми входами всех элементов И, всех вторых элементов И, всех элементов 2 И-ИЛИ, выход 1-го элемента И подключен к второму входу з-го элемента ИЛИ, выход которого соединен с входом установки в единичное состояние .-го триггера первой группы, инверсный выход которого нодклячен к входу установки в "О" д-готриггера третьей группы, прямой иинверсный выходы .-го триггера второйгруппы соединены с вторыми входамисоответственно -го элемента И и второго элемента И .-го элемента 2 И-ИЛИ,четвертый, пятый и шестой выходыблока управления соединены с синхроСоставитель Е.ИвановаТехред М,Дидык Корректор, С.Шекмар Редактор Е. Копча Заказ 6289/52 Тираж 704 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4,5 1 входами триггеров соответственно первой, второй и третьей групп,2. Устройство по и. 1, о т л и - ч а ю щ е е с я тем, что блок управления содержит генератор импуль сов, двойной триггер, счетчик, де" шифратор, три элемента И и два элемента НЕ, причем выходы генератора импульсов подключены к синхровходам двойного триггера, первым входам соответственно первого и второго элементов И и счетным входам счетчика, выходы разрядов которого соединены с входами дешифратора, выходы которого соединены соответственно с третьим выходом блока управления и вторыми входами первого и второго 441384 6элементов И, выходы которых являютсясоответственно четвертым и пятым выходами блока управления, а выход5второго элемента И через первый элемент НЕ - с шестым выходом блока управления, вход запуска блока управле"ния подключен к входу установки в0" счетчика и инФормационному входу 10 двойного триггера, выход которогосоединен с управляющим входом счетчика и первым входом третьего элемента И, второй выход которого соединен с первым выходом генератЬра 15 импульсов, а выход является первымвыходом блока управления и через,второй элемент НЕ соединен с вторымвыходом блока управления.