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

(56) АвторскоУ 928342, кл.АвторскоеУ 1092494, кл ССС 80. СР свидетельство 6 06 Р 7/06, 1 видетельство С С, 06 Р 7/06,(54) (57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИЧИСЕЛ, содержащее и регистров, И элементов И, где И число сортируемихчисел, И схем сравнения, (и) элементов запрета, регистр результата,две группы выходных элементов И,сумматор, первая группа входов которого соединена с входами задания начального адреса устройства, а выходысоединены с информационными входамивыходных элементов И первой группы,выходы которых являются выходами адреса устройства, выходы регистра результата соединены с информационными входами выходных элементов И второй группы, выходы которых являютсявыходами отсортированного числа устройства, управляющие входы выходныхэлементов И первой и второй группподключены к тактовому входу устройства, входы сортируемых чисел. устройства соединены с информационнымивходами соответствующих регистров,выходы которых соединены с первымигруппами входов соответствующих схемсравнения, 1 .-е инверсные входы элементов запрета с 3 -го по (и)-йобъединены ( 0 =1,2п), о т -л и ч а ю щ е е с я тем, что, сцелью повьппения быстродействия, внего введены (ш- и) элементов запрета, И дешифраторов, о элементовИЛИ, где И =2 , (щ) элементовзапрета, элемент задержки, шифратори элемент И-НЕ, выход которого является выходом конца сортировки устройства, а входы подключены к выходамшифратора, входам регистра результата и вторым группам входов всех схемсравнения, выходы схем сравнения соединены с первыми входами соответствующих элементов И, выходы которых подключены к входам установки внулевое состояние соответствующихрегистров, выходы которых дополнительно подключены к входам соответствующих дешифраторов,-й выход .-го дешифратора, где=1,2,ю=1,2 и, соединены с 1 -мвходом-го элемента ИЛИ, выход первого элемента ИЛИ соединен с первымвходом шифратора и первыми инверсными входами элементов запрета,выход-го элемента ИЛИ, где1 =2,3. в, подключен к прямомувходу (1-1)-го элемента запрета ик 1 -му инверсному входу 1 -го элемента запрета, выход р -го элемента запрета,где р =1,2(ю),соединен с (р+1)-м входом шифратора,тактовый вход устройства через элемент задержки подключен к вторымвходам всех элементов И.Изобретение относится к автоматике и вычислительной технике и может найти применение в специализированных вычислительных машинах иустройствах обработки данных.Цель изобретения - повышение бы"стродействия.На чертеже приведена Аункциональная схема устройства.Устройство содержит и регистров1, и дешиФраторов 2, й элементовИЛИ 3, (ш) элементов запрета 4,шиАратор 5,схем 6 сравнения,элементов И 7, регистр 8 результата; сумматор 9, элемент 10 задержки, элемент И-НЕ 11, группы выходных элементов И 12 и 13, входы14 сортируемых чисел устройства,входы 15 задания начального адресаустройства, выход 16 конца сортировки, выходы 17 отсортированногочисла, тактовый вход 18 и выход 19адреса устройства,Рассмотрим принципы построениян работу устройства,Исходное состояние устройствахарактеризуется тем, что в .регист"ры 1 по входам 14 принимается массив исходных чисел, а в сумматор 9 код адреса памяти, начиная с которого необходимо разместить отсортированный массив чисел.Исходные числа преобразуютсяде.;чйраторами 2, выходные сигналыс одноименных выходов которых объединяются соответствующими элементами ИЛИ 3.Пусть массив чисел имеет следующий вид: а, =4, ц =5, а=3, а =4,При этих чсходных данных работадешиФраторов 2 и элементов ИЛИ 3поясняется таблицей 1. Из таблицы видно, что номер выходов дешийраторов, а следовательно и номер элемента ИЛИ 3 однозначно соответствуют значению числа, а выходные единичные сигналы элементов ИЛИ 3 размещены в порядке возраста ния значения чисел. Кроме того, при равных двоичных кодах в массиве чисел (а= а=100" а, = а 6=101) единичные сигналы Аормируются,соответствующими элементами ИЛИ 34 и 3, Таким образом, упорядоченный "массив должен иметь вид: Ъ, =1, 1 =3, 1 4, Ь =5, причем эти числа необходимо разместить в выделенной12 40 45 50 55 После установки в "0" регистра 1 на выходах элементов ИЛИ 3 Аормируется очередной позиционный код 00111, а на входе шиАратора 5 - код 00100. При этом в регистр 8 результата принимается двоичный код 011, а в схеме б сравнения Формируется единичный сигнал. По очередному тактовому импульсу с входа 18 значения числа 011 и код адреса А поступают в ЭВМ, а в устройстве регистр 1 устанавливается в "0" и в сумматоре 9 Аормируется очередной адрес А =А +1, При этом на выходах элементов ИЛИ 3 Аормируется позиционный код 00010, а на выходе шиАратора 5 - двоичный код 100. В схемах 6, и 6 сравнения происходит совпадение кодов,11718 2области памятч, код начального адреса которого Ащ принят в сумматор 9.Позиционный код выходных сигналов элементов ИЛИ 3 10111 подаетсяна элементы запрета 4, включенныепо приоритетной схеме. Так, единичный сигнал с выхода элементаИЛИ З,закрывает по инверсным входам,все последующие элементы 4,-4 запрета. При этом на входе шифратора 5 Формируется позиционный код10000. ШиФратором 5 этот код преобразуется в двоичный 001, принимаемый в регистр 8 результата. Крометого, в схеме 6 сравнения происходит совпадение кодов, единичныйсигнал с выхода которой поступаетна первый вход элемента И 7 Навыходе элемента И-НЕ 11 единичныйсигнал отсутствует, поэтому из ЭВМпо входу 18 поступает тактовый импульс. По этому импульсу адресА,=Аиз сумматора 9 через группуэлементов И 13 поступает на выходы 19, а двоичный код первого числа из регистра 8 результата черезгруппу элементов И 12 выдается 30на выходы 17. Через некоторое время, определяемое задержкой в элементе 10. задержки, в сумматоре 9Формируется очередной адрес А А +1и устанавливается в "0" регистр 1,чем исключается из анализа число й,Бремя задержки выбирается исходяиз необходимого времени приема вЭВМ адрес.а и значения чисел с выходов 17 и 19.По очередному импульсу по входу18 значение числа 100 и код адресаАз поступают в ЭВМр регистры 11 и 1устанавливаются в "0", а в сумматоре 9 Формируется адрес очередногочисла А=А+1. По следующему тактовому импульсу происходит записьчисла 101 по адресу А, а в устройстве - установка в "0" регистров Номер выходов дееввррееоре 2,2 р Двоичныйкод числа 2 3 4 0 0 О 0 О 0 0 00 0 0 0 0 0 0 0 0 0 0 Позиционныйкод элемента ИЛИ 3 0 6,-100 а,=101 а 011 а, 100а =001.о =101 1211718 41 и 1. При этом все регистры 1оказываются в нулевом состоянии, и 1на выходе элемента И-НЕ 11 Формируется единичный сигнал, поступающийв ЭВМ в качестве сигнала концасортировки.Таким образом, массив из жестичисел отсортирован на четыре тактовых сигнала."Патент" город, ул. Проектная аказ 640/52 . Тираж 673 . ВНИИПИ Государственного по делам изобретений 113035, Москва, Ж, Рауш