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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСНРЕСПУБЛИК 14 5 19) 06 Р 7 САНИЕ ИЗОБРЕТЕН ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ТОРСНОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССР Р 876339, кл. С 06 Г 7/06, 1979.Авторское свидетельство СССР В 1001083, кл. С 06 Р 7/06, 1981, (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации технических средств ЭВМ и создании устройств обработки статистической информации. Цель изобретения - повышение быстродействия, Устройство содержит ш-разрядные регистры 1, группы элементов И 3-5, 7,8, группу элементов ИЛИ 6, группы элементов запрета 9, 10, группу триггеров 11,элемент 12, сдвигающий регистр 13,группы элементов задержки 15, 16,группу дифференцирующих элементов 17.Устройство реализует принцип упорядочивания чисел по возрастанию сразбиением исходного ряда на 2 подгруппы с каждым циклом сравнения (1 номер цикла) и последующим одновременным упорядочиванием чисел в каждой подгруппе, что обеспечивает полное упорядочивание чисел за однократный просмотр их разрядов. 1 ил.Изобретение относится к автоматике и вычислительной технике и может быть использовано при реализации технических средств ЭВИ и создании устройств обработки статистической информации.Цель изобретения в .повышение быстродействия устройства.На чертеже представлена блок-схе"- 10 ма устройства.Устройство содержит ш-разрядные регистры 1, -1, группу входных зле;ментов ИЛИ 2, группу элементов И 3 ,записи, группу элементов И 4 перезаписи, группу элементов И 5 анализа, группу элементов ИЛИ б, первую и вторую группы элементов И 7 и 8, первуюю и вторую группы, элементов 9 и 10 ,запрета, группу триггеров 11 элемент ИЛИ 12, сдвигающий регистр 13,элемент 14 задержки, первую и вторуюгруппы элементов 5 и 16 задержки, , группу дифференцирующих элементов 17,третью группу элементов 18 задержки, 25 вход 19 запуска устройства и выход , 20 окончания сортировки устройства.Устройство работает следующимобразом.30В исходном состоянии триггеры 11 11 ц находятся в единичном состоянии, открывая по одному из входов все элементы И 8, -8 н, . В регистры , 1 -1 н записываются упорядочиваемые ;числа (входы записи не показаны), после чего на вход 19 устройства поступает сигнал запуска. Этот сигнал через элемент ИЛИ 12 поступает на элемент 14 задержки, одновременно устанавливая первый разряд сдвигаю- щего регистра 13.в единичное состояние, Сигнал с выхода первого разряда регистра 13 открывает по одному из входов элементы И 5 ц -5,н, подключенные к первым (старшим) разрядам каждого регистра 1 -1 МНачинается сравнение выделенныхразрядов. Их значения через открывающиеся элементы И 5 н -5,нпоступают на входы элементов ИЛИ б -6 . С выхода элемента ИЛИ 61 непосредственно, а с выходов элементов ИЛИ 6 -бн- через элементы 18, -. 18задержки сигналы поступают на входы элементов И 7, -7 , и запрещающие входы эле ментов 9, -9 нзапрета соответствующих им регистров. Одновременно сигналы с выходов элементов 18-18 нзадержки поступают на информационные и запрещающие входы соответственно элементов 9 -9 н, и 10, -10, запрета которые относятся к регистрам, предназначенным для записи больших по значению чисел - старшим регистрам (в регистр 1, записывается наибольшее из упорядочиваемых чисел, а в регистр 1 н - наименьшее, Сравнение выделенных разрядов двух соседних регистров 1 -1 н происходит на элементе 9-9 н, запрета старшего регистра. В случае, если значения сравниваемых разрядов равнозначны, т.е. в двух соседних регистрах выделенные разряды равны, то на выходе элемента 9, -9 нзапрета сигнал отсутствует, так как на его входах одинаковые либо единичные, лйбо нулевые сигналы. Это будет и в случае, если в старшем регистре значение выделенного разряда равно 1, а в младшем - О, так как элемент 9-9запрета относящийся к старшему разряду, закрыт.В случае, если значение сравниваемого разряда старшего регистра равно О, а значение этого же разряда младшего регистра равно 1, т.е. в мяадшем регистре записано большее по значению число, то единичный сигнал с выхода элемента ИЛИ 6 в б н младшего разряда через открытый элемент 9, -9 нзапрета старшего разряда поступает на вход соответствующего ему элемента И 8 -Ян 1, открытого по второму входу триггером 11 -11 н-Сигнал с выхода открывающего элемента И 8 -8 нстаршего регистра поступает на входы элемен- тов И 3, -3 , и элементов И 4, 4старшего и младшего регистров соответственно, разрешая перезапись значений находящихся в них чисел. Значения разрядов регистров через открытые элементы И 3, -3 и 4 п -4поступают на элементы 15-15и 16., -16 задержки соответственно и запоминаются на них на время, необходимое для обнуления регистров 1, -1 н . Обнуление регистров 1, -1 , участвующих в перезапи-ф си чисел, осуществляется по входам сброса импульсом сброса, Формирующимся дифференцирующим элементом 17- 17 н, по переднему Фронту сигнала, поступающего с элемента И 8, -8 н,; После обнуления регистров большеепо значению число, хранящееся в младшем регистре, через элементы ИЛИ 2, -2 записывается в старший регистр, а меньшее - наоборот. Процесс перезаписи чисел продолжится . до тех пор, пока в двух соседних регистрах встречается комбинация значений сравниваемых разрядов 01 т.е, все числа, значащее значение сравниваемого разряда которых равно 1, сдвигаются в старшие регистры устройства (начиная с регистра 1, ), а со значением сравниваемого разряда, равным 0; - в младшие регистры. Для исключения сбоев устройства при ,обнулении регистров 1, -111 служат элементы 18, -18 , задержкиобеспечивающие задержку сигналов на время, достаточное для перезаписи чи- . сел из регистра в регистр, По окончании перезаписи чисел в регистрах 1, -1записаны числа с 1 в сравниваемом разряде, а в регистрах 1 - 1 я - с нулевым значением сравниваемого разряда.Единичный сигнал с выхода К-го элемента ИЛИ 6 поступает на один из входов К-го элемента И 7 , на другой вход которого поступает.сигнал с выхода элемента 14 задержки. Время задержки сигнала элементом 14 . выбрано таким, что успевают закончиться все процессы перезаписи чисел в регистрах 11 -1 н . Счгнал с выхода элемента 14 задержки через элемент ИЛИ 12 сдвигает 1 в сдвигающем регистре 13 в следующий разряд, одновременно устанавливая триггеры 11 в нулевое состояние через открывшййся элемент И 7 и открытый нулевым сигналом с выхода элемента ИЛИ 6 , элемента 10 запрета. Тем самым блокируется элемент И 8 , запрещая до конца работы устройства перезапись чисел между регистрами 1 к и 1 к+, независимо от значений сравниваемых разрядов записываемых В них чиселоСигнал с выхода второго разряда сдвигающего регистра 13 открывает элементы И 5 , -5 я всех регистров, после чего начинается цикл сравнения вторых разрядов упорядочиваемыхчисел.Цикл сравнения и перезаписи чисел между регистрами повторяется, только теперь упорядочивание чисел по значению второго разряда происходит вУстройство для сортировки чисел,содержащее распределитель управляющих сигналов, элемент задержки, элемент ИЛИ, Н регистров, где К - количество сортнруемых чисел, первую ивторую группы элементов И, К групп ЗБэлементов И анализа по ш элементовИ анализа в каждой группе, где ш -количество разрядов сортируемых чисел, Игрупп элементов И записи 40 ш элементов И записи В каждой группефЯгрупп элементов И перезаписи шэлементов И перезаписи в каждой группе, группу элементов ИЛИ, Югруппвходных элементов ИЛИ, первую и вто рую группу элементов задержки, группу триггеров, причем выход каждоготриггера группы соединен соответст-венно с первым входом элемента И первой группы, выход К-го входного элемента ИЛИ Р-й группы, где К 1ш,Р=1,И, соединен соответственнос К-м информационным входом (Р+1)-горегистра, выход К-го регистра д-горегистра, где =1Я, соединенсоответственно с первым входом К-го элемента И анализа д-й группы, выходК-го элемента И анализа -й группысоединен с К-м входом -го элементаИЛИ группы, о т л к ч а ю щ е е с я 5 10 15 20 двух группах регистров 1 -1н 1" 1 н, так как перезапись чисел между К-м и (К+1)-м регистрами запрещена. Следующим сигналом с выхода элемента 14 задержки в нулевое состояние сбрасываются по крайней мере еще два триггера 11 1 -11 н, (по одному в каждой подгруппе регистров 11и 1. -1 , и так далее. После сравнения последнего разряда чисел на выходе 20 сдвигающего регистра 13 появляется сигнал об окончании процесса упорядочивания чисел. Прн этом наибольшее число записано в регистре 1, , а наименьшее - в регистре 1 я .Таким образом, устройство реализует принцип упорядочивания чисел по возрастанию с разбиением исходного ряда на 2 подгруппы с каждым циклом сравнения ( - номер цикла) и последующим одновременным упорядочиванием чисел в каждой подгруппе, что обеспечивает полное упорядочиванне чисел за однократный просмотрих разрядов. Формула изобретенияСоставитель В.КозловТехред А.Кравчук Корректор М.Максимишинец Редактор О.Юрковецкая Заказ 6077/47 . Тираж 04 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, 3-35, Раушская наб.; д. 4/5 Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4 5 14 тем, что, с целью повышения быстродействия, распределитель управляющих сигналов выполнен на сдвигающем регистре и в устройство введены первая и вторая группы элементов запрета, группа дифференцирующнх элементов, третья группа элементов задержки, причем вход запуска устройства сое динен с первым входом элемента ИЛИ выход которого соединен с входом сдвига,сдвигающего регистра и через элемент задержки с вторым входом элемента ИЛИ и первым входом 1-го элемента И второй группы, где =1., , Н, выход которого соединен с информационным входом 3-го элемента запрета первой группы, выход которого соединен с входом установки. в "О" х-го триггера, выход первого элемента ИЛИ группы соединен с. вторым входом первого элемента И второй груп" пы и с запрещающим входом первого элемента запрета второй группы, выход Ц+1)-го элемента ИЛИ группы соединен через соответствующий элемент задержки первой группы с запрещающим входом (+1)-го элемента запрета первой группы и с информационным входом 1-го элемента запрета второй группы, выход Р-го элемента задержки первой группы соединен с вторым входом (Р+1)-го элемента И второй группы и с запрещающим входом (Р+1)-го элемента запрета второй группы, выход 1-го элемента запрета второй группы соединен с вторым входом 3-го эле 39576 6мента И первой группы, выход которого соединен с управляющими входами К элементов И записи и перезаписи51-х групп и через 1-й дифференцирующнй элемент с входами установки в"О" (1 го и (1+1)-го регистров, К-йвыход 1-го регистра соединен с информационным входом (К-го элементаИ записи 1-й группы, К-й выход (+1)- го регистра соединен с информационным входом К-го элемента И перезаписи 1-й группы, выход К-го элементаИ Р-й группы соединен через соответствующий элемент задержки второйгруппы с первым входом К-го входного элемента ИЛИ Р-й группы, вьиодК-го элемента И записи (Я)-й группы соединен через соответствующийро элемент задержки второй группы с(К-м информационным входом Я-го регистра, выход К-го элемента перезаписи (Р+2)-й группы соединен черезсоответствующий элемент задержки25 третьей группы с вторым входом К"говходного элемента ИЛИ Р-й группы,выход К-го элемента И перезаписивторой группы соединен через соответствующий элемент задержки третьейЗО группы с К-и информационным входомпервого регистра, К-й выход сдвигающего регистра соединен с вторыми входами К-х элементов И анализа х-хгрупп, выход старшего разряда сдвигающего регистра является выходом окончания сортировки устройства,