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

(51) 4 С 06 Р 7/06 ОПИСАНИЕ ИЗОБРЕТЕНИ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО.ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ(56) Авторское свидетельство СССР Яф 1168927, кл, С 06 Р 7/06, 1984.Авторское свидетельство СССР Ф 12117 18, кл. С 06 Р 7/06, 1984, (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ . (57) Изобретение относится к автоматике и вычислительной технике и может найти применение в специализированных вычислительных машинах и устройствах обработки данных. Целью изобретения является расширение области применения устройства за счетвозможности сортировки нулевых и равных чисел, Устройство содержит и регистров 1, и триггеров 2, группы элементов И 4, 10, 15, .16, дешифраторы3 элементы ИЛИ 5, группы элементов 6,9 запрета, шифратор 7, и схем 8 сравнения, регистр 12 результата, элемент ИЛИ-НЕ 11, сумматор 13.Устройство сортирует массив чисел по возрастанию и выдает его для занесенияв ЭВМ, начиная с заданного адресабез потери нулевых и равных чисел.1 табл., 1 ил.14447Изобретение относится к автоматике и вычислительной технике и может найти применение в специализированных вычислительных машинах и устройствах обработки данных.Цель изобретения - расширение области применения устройства за счет возможности сортировки равных и нулевых чисел. 10На чертеже изображено предлагаемое устройство.Устройство содержит п регистров 1, и триггеров 2, и дешифраторов 3, п элементов И 4 первой группы, (ш+1) 15 элементов ИЛИ 5, ш элементов 6 запрета первой группы, шифратор 7, и схем 8 сравнения,(п) элементов 9 запрета второй группы, и элементов И 10 второй группы, элемент ИЛИ-НЕ 20 11, регистр 1.2 результата, сумматор 13, элемент 14 задержки, группы выходных элементов И 15 и 16, входы 17 сортируемых чисел устройства, входа 18 сопровождения числа, входы 19 на чального адреса устройства, выход 20 конца сортировки, выходы 21 отсортированного числа, тактовый вход 22 и выхрд 23 адреса устройства.Устройство работает следующим образом.Исходное состояние устройства характеризуется тем, что в регистры 1 по входам 17 принимается массив исходных чисел, а в сумматор 13 - код адреса памяти, начиная с которого необходимо разместить отсортированный массив. По входам 18, соответствующим входам 17, по которым поступили исходные числа, подаются сигналы, переводящие соответствующие триггеры 2 в единичное состояние, которое является признаком наличия числа в регистре 1.,Исходные числа, в том числе и равные О, преобразуются дешифраторами 3, выходные сигналы с одноименных выходов45 которых, кроме нулевогообъединяются соответствующими элементами ИЛИ 5, сигналы с нулевых выходов дешифратора 3 выделяются элементами И 4 и на вход элемента ИЛИ 5 поступают сигналы толь.50 ко с тех элементов И 4, которые соответствуют регистрам 1, принявшим нулевые числа. Сигналы с триггеров 2 позволяют отличить исходное состояние регистров 1 от наличия вних нулевых чисел.11 усть массив исходных чисел имеет следующий вид: 49 24а 3 а 0 а 1 а 4 аа =5,При этих исходных данных работадешифраторов 3 и элементов ИЛИ 5 по-,ясняется таблицей.Из таблицы видно, что номер выходов дешифраторов 3 и номер элементаИЛИ 5 однозначно соответствуют значению числа,. а выходные единичные сигналы элементов ИЛИ 5 размещены вПорядке возрастания значения чисел.При равных двоичных кодах в массивечисел (а=а =001) единичный сигналформируется соответствующим элементом ИЛИ 5 (ИЛИ 5,),Упорядоченный массив должен иметьвид;Ь =От Ь . 1 ф Ьь=1 Ъ =3 Ь=4 Ь =5 эпричем эти числа необходимо разместить в выделенной области памяти, код начального адреса А=Анач которой принят в сумматор 13. Позиционный код 11011 выходных сигналов элементов ИЛИ 5 подается на элементы 6 запрета, включенные по приоритетной схеме. Единичный сигнал с выхода элемента ИЛИ 5 закрывает по инверсным входам все последующие элементы 6,-6 запрета. При этом на входе шифратора 7 формируется позиционныйкод 100000 и в регистр 12 результата принимается двоичный код 000. Помимо этого, в схеме 8 сравнения происходит совпадение кодов, единичный сигнал с выхода схемы 8 сравнения поступает на первый вход элемента И 10, минуя элементы 9 запрета. На выходе элемента ИЛИ-НЕ 11 отсутствует единичный сигнал, поэтому из ЭВМ по входу 22 поступает тактовый импульс, По этому импульсу адрес А=Анач из сумматора 13 через группуэлементов И 16 поступает на выходы 23, а двоичный код первого числа из регистра 12 результата через группу элементов И 15 выдается на выходы 21. Через некоторое время, определяемое задержкой в элементе 14 задержки, в сумматоре 13 формируется очередной адрес А=А +1 и устанавливается в "0" регистр 1 и триггер 2 , чем исключается из рассмотрения число а. Время задержки выби - рается исходя из необходимого вре- мени приема в ЭВМ адреса и значения. числа с выходов 21 и 23.14447494ответствовать последовательность равных чисел,Двоичный код числ а,=011 а,=000 а =001 а,=100 а =ОО а =101 50 После установки в "0" регистра1 и триггера 2на выходах элементов. ИЛИ 5 формируется очередной позиционный код 010111, а на входешифратора- код 010000. При этом5в регистр 12 результата принимается двоичный код 001, а в схемах 8 зи 8сравнения формируется единичный сигнал,10Элемент 9 запрета пропускаетсигнал с выхода схемы 8 з сравненияна вход элемента И 1 Оз, этот же сигнал закрывает по инверсным входамвсе последующие элементы 9 Ззапрета, тем самым не пропуская с выхода схемы 8 сравнения.По очередному тактовому импульсу с входа 22 значение числа 00 икод адреса А поступают в ЭВМ, в результате чего в устройстве регистр1 и триггер 2 з устанавливаются в"0", а сумматоре 13 формируется очередной адрес А=А +1. При этом навыходах элементов ИЛИ 5 формируется 25код 010111, а на входе шифратора 7 -код 010000.По очередному тактовому импульсу,по,входу 22 значение числа 001 и кодадреса Аз поступают в ЭВМ, в результате чего в регистр 1 и триггер 25устанавливаются в состояние "0", при. этом в сумматоре 13 формируется адрес очередного числа А=Аз+1. Последующему тактовому импульсу происходит запись числа 011 по адресу А 4,в результате чего, в устройстве регистр 18 и триггер 2устанавливаются в "0".По очередным тактовым импульсам 40происходит последовательная записьчисел 100 и 101 по адресам А =А+и А=А +1 соответственно и регистры51 и 1 и триггеры 2и 2 устанавливаются в "О". При этом после устаковки триггера 2в "0" все триггерыоказываются в состоянии "0", в результате чего на выходе элементаИЛИ-НЕ 11 формируется единичный сиг-нал, поступающий в ЭВМ в качествесигнала конца сортировки.Таким образом, в результате работы устройства массив исходных чисел будет отсортирован по возрастанию и отсортированная последовательность будет занесена в память ЭВМ,55начиная с заданного начальногоадре"са, причем, если в массиве есть рав-.ные числа, то на выходенм будет соНомер выхода дешифраторов3,3 (номер элементаИЛИ 5) 0 1 2 3 4 5 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 00 1 0 0 1 0 0 0 0 0 0 0 0 0 1 Формула изобретения Устройство для сортировки чисел, содержащее п регистров, где и - число сортируемых чисел, и дешифраторов, и элементов И первой группы, ш элементов ИЛИ, где ш = 2 , (ш) элементов запрета, шифратор, и схем сравнения, регистр результата, сумматор, две группы выходных элементов И, эле мент задержки, элемент ИЛИ-НЕ, причем входы сортируемых чисел устрой ства соединены с информационными . входами соответствующих регистров, выходы которых соединены с входамисоответствующих регистров и входами первых групп соответствующих схем сравнения, -й выход 3-го дешифратора, где= 1, 2,, ш, 3 = 1 2п, соединен с 1-ым входом 1-го элемента ИЛИ, -е инверсные входы элементов запрета с д-го по (ш"1)-й объединены, выходы шифратора соединены с входами вторых групп всех схем сравнения и информационными входами регистра результата, выходы разрядов которого подключены к пер". вым входам соответствующих выходных элементов И первой группы, выходы которых являются выходами отсортиро- ванного числа устройства, входы начального адреса устройства подключеЗаказ 650 б/47 Тираж 704 Подписное ВНИИПИ Государственного комитета СССР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб., д, 4/5Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 5 1444 ны к входам первой группы сумматора, выходы которого соединены с первыми входами соответствующих выходных элементов и второй группы, выходы которых являются выходами адреса устроиства,ю5 тактовый вход устройства подключен к вторым входам выходных элементов И первой и второй групп и через элемент задержки к входу второй группы10 сумматора и первым входам, всех элементов И первой группы, второй вход первого элемента И первой группы соединен с выходом первой схемы сравнения выход элемента ИЛИ-НЕ явФ15 ляется выходом конца сортировки устройства, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения устройства за счет возможности сортировки равных и нулевых чисел, в него введены дополнительный элемент ИНИ, дополнительный элемент запрета первой группы, (и) элементов запрета второй группы, и элементов И второй группы и и триггеров, входы установки в единичное состояние которых подключены к соответствующим входам сопровождения чисел устройства, а выходы соединены . с входами элемента ИНИ-НЕ и с пер 749 6выми входами соответствующих элементов И второй группы, вторые входы которых соединены с выходами обнаружения нуля соответствующих дешифраторов, а выходы подключены к входам дополнительного элемента ИНИ, выход которого соединен с дополнительным входом шифратора и первыми инверсными входами элементов запрета, первой группы, выход -го элемента ИЛИ (1=1,2ш) соединен,с прямым входом -го элемента запрета первой группы и (+1)-ым инверсным входом элементов запрета с (д+2) - го по ш-й первой группы, выходы элементов запрета первой группы подключены к соответствующим входам шифратора, выход первой схемы сравнения подключены к первым инверсным входам элементов запрета второй группы, выход 1 с-й схемы сравнения В=2,3п) соединен с прямым входом Ь)-го элемента запрета второй группы и с 1 с-ым инверсным входом элементов запрета второй группы с к-го по (п)-й, выход Ь)-го элемента запрета второй группы подключен к второму входу Е-го элемента И первой группы.