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

Б.С. Богумирский и Э.П. Чернако Авторызобретеиия аявятель ЛЯ СОРТИРО 8 КИ ЧИСЕЛ(5 М) УСТРОЙС та ИЛ запре ется те схем срав счетчик вых рез Изобретение относится к автоматике и вычислительной технике и может быть использовано в специализи"рованных вычислительных машинах иустройствах обработки данных.Известно устройство для сортировки цисел, содержащее и регистров,выходы которых соединены с входами.схем сравнения, другие входы которых подключены к выходам регистрарезультата, выходы схем сравнениясоединены через переключатели с входами элемента ИЛИ, элементы И, триггер и узлы запрета 1.Недостатком этого устройства является низкое быстродействие,Наиболее близкое по техническойсущности к предлагаемому устройство,содержащее щ регистров, выходы которых соединены с входами схем сравнения, другие входы которых подключены к выходам регистра результата,оды схем сравнения соединены чепергклюцатель .с входами элеменИ, элементы И, триггер, узлыта и временной распределительНедостатком этого устройства являетсятакже низкое быстродействие,так как сортировка всего исходногомассива чисел требует в(п+1) тактовработы устройства, где щ - число,а и - разность сортируемых чисел.Цель изобретения - повышение быстродействия устройства,6Указанная цель достига мчто в устройстве для сортировки чисел, содержащем распределитель импульсов, и регистров, инения, группы элементов И15сумматор, регистр результата, причем выходы каждого 1-го регистра,где 1 = 1,2п, соединены с информационными входами первой группы301-ой схемы сравнения и 1-ой группыэлементов И, выходы которых подключены к входам 1-ой группы регистра результата, а каждый 1-ый выходраспределителя импульсов соединен915- науч+ ф Таким образом, с 9 на один из входов ется код количества сел, меньших числа,гистре 4 результата,сумматора 8 подаетсявыхода счетчикасумматора 8 подасортируемых чизаписанного в реНа второй вход код адреса об 3с управляющим входом элементов Им1-ои группы, выходы регистра результата подключены к информационным входам второй группы всех схем сравнения и к информационным входам первых5выходных элементов И группы, выходкаждой 1-ой схемы сравнения соединенс 1-ым входом счетчика, выходы которых подключены к входам первой, группы сумматора, входы второй группы Н 1которого соединены с входными шинамиустройства, а выходы - с информационными входами выходных элементов И второй группы элементов, управляющиевходы выходных элементов И первой и 15второй групп подключены к управляющей шине устройства,На чертеже представлена схемапредлагаемого устройства.Устройство содержит распредели 20тель 1 импульсов, и регистров 2, исхем 3 сравнения, регистр 4 результата, группы 5-7 элементов И, сумматор 8, счетчик 9, входы устройства10 и 11, вход 12 управления устрой- у 5ства и выходы 13 и 14 устройства.Устройство работает следующимобразом.В регистры 2 заносятся сортируемые числа, регистр 4 результата уста"Мнавливается в нуль, а распределитель1 импульсов - в исходное состояние(не показано). После этого устройство готово к сортировке чисел в порядке возрастания.Затем на вход 10 устройства пода 35ется первый тактовый сигнал, по которому появляется сигнал на,первом(верхнем) выходе распределителя 1импульсов. При этом открывается40группа б элементов И и число из верхнего регистра 2 переэаписывается врегистр 4 результата. Это число сравнивается со всеми сортируемьйи числами в схемах 3 сравнения, сигнал навыходе которых появляется лишь в том45случае, когда числа, находящиеся всоответствующих регистрах 2, меньшечисла, записанного в регистре 4 результата. Счетчик 9 подсчитывает количество схем 3 сравнения, имеющихсигнал на своем выходе,13 4ласти памяти, начиная с которого необходимо разместить отсортированную информацию, Тогда адрес области памяти,по которому следует записать число, находящееся в регистре 4 результата, определяется соотношением где А 1 С 1 Ч - адрес области памяти, начиная с которого необходимо разместить отсортированные числа1М- число чисел, меньших числа, записанного в регистре результата. Сумматор 8 вычисляет суммуИицц+ Й. По сигналу на входе 12 устройства число, находящееся в регист-ре 4 результата, записывается взапоминающее устройство по адресу,выдаваемому сумматором 8.Второй такт работы устройства начинается с подачи второго тактовогосигнала на вход 10 устройства. Приэтом появляется сигнал на втором выходераспределителя 1 импульсов,который открывает соответствующуюгруппу 6 элементов И, вследствиечего в регистр 4 результата перезаписывается число из регистра 2. Дальнейшая работа устройства аналогичнарассмотренному выше.После того, как устройство отработает и тактов, в запоминающем устройстве будет записан отсортированныймассив чисел по адресу, заданномуна входе 1 устройства.Для сортировки чисел в порядке убы-.вания необходимо в регистры 2 записать инверсные значения кодов сортируемых чисел.ЪПредлагаемое устройство обладаетвысоким быстродействием, так какдля сортировки и чисел требуетсяи тактов работы,формула изобретения Устройство для сортировки чисел, содержащее распределитель импульсов, и регистров, и схем сравнения, группы элементов И, счетчик, сумматор, регистр результата причем выходы каждого -го регистра, где 1 = 1,2. . .и, соединены с информационными входами первой группы29/40 Тираж 732 Подписное И ПИ За лиал ППП "Патент", г,.Ужгород, ул.Проектная,4 5 911513 61 1-ой схемы сравнения и 1-ой группы сумматора, входы второй группы кото- элементов И, выходы которых подклю- рого соединены с входными шинами цены к входам 1-ой группы регистра устройства, а выходы - с информационрезультата, а каждый 1-ый выход рас- ными входами выходных элементов И пределителя импульсов соединен с ю второй группы элементов; управляю- управляющим входом элементов И 1-ой щие входы выходных элементов И пергруппы, о т л и ч а ю щ е е с я тем, вой и второй групп подключены к упчто, с целью повышения быстродей- равляющей шине устройства. ствия, Выходы регистра результатаподключены к информационным входам 1 О Источники информации, второй группы всех схем сравнения и принятые во внимание при экспертизе к информационным входам первых выход- , 1, Авторское свидетельство СССР ных элементов И группы, выход каж- И 263277, кл, С 06 Р 7/00, 1958. дой 1-ой схемы сравнения соединен с 2. Авторское свидетельство СССР.1-ым входом счетчика, выходы которых 15 йф 637810,кл. 6 06 Р 7/08, 1976 подключены к входам первой группы (прототип).