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

,80,4 107 3 1 8 6 Р 7/06. ГОСУДАРСТВЕННЫЙ КОМ ПО ДЕЛАМ ИЗОБРЕТЕНИ ОТНРЬ ПИСАНИЕ ИЗОБРЕТЕН ТВУ саидетвъс АВТ(56) 1. Авторское свУ 637810, кл . С 06 Р2. Авторское свидВ 911513,кл. С 06 Р ния выдачи числа устройства и управляющим входам выходных элементов И второй группы, выходы которых являются выходами адреса блока памяти устрбйства, а информационные входы соединены с соответствующими выходами сумматора, входы первой группы которого соединены с входами задания ад реса области памяти устройства, а входы второй группы - с выходами разрядов счетчика, каждый 1-й выход рас пределителя импульсов подключен к управляющим входам элементов И -й группы, о т л и ч а ю щ е е с я тем, что, с целью повышения достоверности записи массива путем исключе- Е ния потерь информации при записи одинаковых чисел, в устройство введены и триггеров, и элементов И и п элементов ИЛИ, причем каждый 1-й выход распределителя импульсов соеди- Я нен с входом установки в единичное .состояние -го триггера, выход которого подключен к первому входу д-го ффф элемента И, выход которого соединен с первым входом -го элемента ИЛИ, а второй вход - с выходом "Равно" блока сравнения, выход меньше" которого подключен к второму входу д-гоэлемента КПИ, выход которого.соедиНен с соответствующим входом счетчика. детельство СССР7/08, 1976.тельство СССР7/06, 1980 (про тип(54)(57) УСТРОЙСТВО ЧИСЕЛ, содержащее ра пульсов, й регистров нения, группы элемен сумматоррегистр рез выходы разрядов кажд ра, где =1, 2, с соответствующими и входами первой группь кения и 1-й группы э которых подключены к группы регистра резу разрядов которого по мационным входам вто блоков сравнения и к Р ТИРОВ спределитель .ими блоков срав тов И, счетчик,ультата, причем ого 1-го регист и, соединеныформационными-го блока сравлементов И,выходывходам д-й льтата, выходы дключены к инборрой группы всехинформационным ентов И первойявляются инфорустройства, а упвходам выходных эле руппы,выходы которых ационными выходами авляющие входы перв ентов И подключены х выход элешине разреше 1Изобретение относится к автоматике и вычислительной технике и можетбыть использовано в специализированйых машинах и устройствах обработкиданных,5,.Известно устройство для сортировки присел, содержащее ш регистров,выходы которых соединены с входамисхем сравнения, другие вьжоды которых подключены к выходам регистра ре Озультата, выходы схем сравнения соединены через переключатель с входамиэлемента ИЛИ, элементы И, триггер,узлы запрета и временной распределитель 13.15Недостатком этого устройства является низкое быстродействие.Наиболее близким по техническойсущности к предлагаемому являетсяустройство для сортировки ш и-разряд 20ных чисел, содержащее распределительимпульсов, и регистров, и схем сравнения,. группы элементов И, счетчик,сумматор, регистр результата, причемвьжоды разрядов каждого -го регистра где 1=1,2, , и, соединены ссоответствующими информационными входами первой группы -й схемы сравнения и -й группы элементов И, выходыкоторых подключены к входам -группы30регистра результата, а каждый х-йвыход распределителя импульсов соединен с управляющим входом элементов И-й группы, выходы регистра результата подключены к информационным входам второй группы всех схем сравнения 5и к информационным входам первых выходных элементов И группы, выход каждой -й схемы сравнения соединен сз-м входом счетчика, выходы которогоподключены к входам первой группысумматора, входы второй группы которого соединены с входными шинами уст"ройства, а выходы - с информационнымй входами выходных элементов И второй группы элементов, управляющиевходы выходных элементов И первой ивторой групп подключены к управляющейшине устройства 21.Однако, если среди сортируемогомассива имеются одинаковые числа, то 50на выходе устройства они формируютсяс одним и тем же адресом. Таким образом, в .запоминающем устройстве будетзаписан отсортированный массив чиселс недостающими членами. Например,если имеется пять равных чисел, тоих значение будет записано толькопо одному первому адресу, а четыре 118гпропущено с сохранением предыдущих значений ячеек, что приведет к невозможности дальнейшей обработки .месива,Цель изобретения - безошибочное формирование упорядоченного массива чисел.Указанная цель достигается тем, что в устройство для сортировки чисел, содержащее распределитель импульсов, и регистров, и блоков сравнения, группы элементов И, счетчик, сумматор регистр результата, причем выходы разрядов каждого д-го регистра, где =1, 2, , и, соединены соответствующими информационными входами первой группы х-го блока сравнения и -й группы элементов И, выходы которых подключены к входам -й группы регистра результата, выходы разрядов которого подключены к информационным входам второй группы1всех блоков сравнения и к информационным входам выходных элементов И первой группы, выходы которых являются информационными выходами устройства, а управляющие входы первых выходных элементов И подключены к шине разрешения выдачи числа устройства и управляющим входам выходных элементов И второй группы, выходы которых являются выходами адреса блока памяти устройства, а информационные входы соединены с соответствующими выходами сумматора, входы первой группы которого соединены с входамн задания адреса области памяти устройства, а входы второй группы - с выходами разрядов счетчика, каждый д-й выход распределителя импульсов подключен к управляющим входам элементов И 1-й группы. введены и триггеров, и элементов И и и элементов ИЛИ, причем каждый -й выход распределителя импульсов соедийен с входом установки в единичное состояние -го триггера, выход которого подключен к первому входу -го элемента И, выход которого соединен с первым входом х-го элемента ИЛИ, а второй вход - с выходом "Равно" блока сравнения, выход "Меньше" которого подключен к второму входу -го элемента ИЛИ, выход которого соединен с соответствующим входом счетчика.На чертеже представлена схема предлагаемого устройства.Устройство содержит распределитель 1 импульсов, и регистров 2, и схем 3 сравнения, регистр 4 результата, группы 5-6 элементовИ, сумматор 8, счетчик 9, входы 10 и 11 устройства, вход 12 управления устройства, выходы 13 и 14 устройства, птриггеров 15, и элементов И 16, пэлементов ИЛИ 17. 5Устройство работает следующим образом.В регистры 2 заносятся сортируемыечисла, регистр 4 результата и триггеры 15 устанавливаются в нуль, а распределитель 1 импульсов - в исходноесостояние (не показано). После этогоустройство готово к сортировке чиселв порядке возрастания.Затем на вход 10 устройства подается первый тактовых сигнал, по которому появляется сигнал на первом(верхнем) выходе распределителяимпульсов. При этом верхний триггер15 установится в единичное состояние, фсигнал с которого разрешает прохождение сигнала с выхода."Равно 1 схемы 3 сравнения через элемент И 16.Также открывается группа 6 элементов И и число из верхнего регистра 2перезаписывается в верхний регистр 4результата. Это число сравниваетсясо всеми сортируемыми числами всхемах 3 сравнения. Если число вкаком-либо регистре 2 меньше чиспа, Збнаходящегося в регистре 4 результата, то на выходе Меньше соответствующей схемы 3 сравнения появляетсясигнал, если числа равны, то сигналпоявляется на выходе Равно . Сигнал 351 1с выхода Равно поступит через элементы И 16 и ИЛИ 17 на счетчик 9только при наличии разрешающего сигнала с триггера 15, т.е. для чиселранее сравниваемых со всеми (включая 40число сравниваемое в текущем такте),Счетчик 9 подсчитывает количествосхем 3 сравнения, имеющих сигнал насвоем выходе,Таким образом, с выхода счетчика 49 на один иэ входов сумматора 8 подается код количества сортируемых чисел, меньших или равных (но ранеесравниваемых со всеми) числу, записанному в регистре 4 результата. На второй вход сумматора 8 подается уменьшенный на единицу код адреса области памяти, начиная с которого необхо". димо разместить отсортированную информацию, Тогда адрес области памяти, по которому следует записать число, находящееся в регистре 4 результата, определяется соотношением А (А ярч 1) +где А - адрес области памяти, начиная с которого необходимо разместить отсортированные чиспа;Й - число чисел,-меньших илиравных, но ранее сравниваемых со всеми, числу,записанному в регистререзультата.Сумматор 8 вычисляет сумму(Анрч -1) + О. По сигналу на входе12 устройства число, находящееся врегистре 4 результата, записываетсяв запоминающее устройство по адресу,выдаваемому сумматором 8.Второй такт работы устройства начинается с подачи второго тактовогосигнала на вход 10 устройства. Приэтом появляется сигнал на втором выходе распределителя 1 импульсов, который устанавливает в единичное состояние соответствующий триггер 15.иоткрывает соответствующую группу элементов И, вследствие чего в регистр4 результата дерезаписывается числоиз регистра 2. Дальнейшая работаустройства аналогична рассмотренному.После того как устройство отрабо-тает гактов, в запоминающем устройстве будет записан отсортированный массив чисел по адресу, заданному навходе 11 устройства, Для сортировкичисел в порядке убывания необходимов регистры 2 записать инверсные зна-чения кодов сортируемых чисел,Предлагаемое устройство обладает расширенными возможностями по сортировке чисел, т.е. позволяет безоши-бочно формировать отсортированный массив из любого произвольного массива чисел,Тираа 699 ПодписиГосударственного комитета СССРелам изобретений и открытийосква, 3-35, Раущская наб д, 4/5 Филиал ППП "Патент", г. Уагород, ул. Проектна Составитель Е. ИвановаРедактор С. Патруаева Техред Ж. Кастелевич Коррек