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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ СоЮа Советских Социалистических Республик151) М. Кл.2 С 06 Г 7 00 веннын комит пиетров ССС ГосударСоветапо дел риорите бликовано 30.08.76, Бюллетень32а опубликования описания 20.10.7 б 3) УДК 681,322(088.8) изобретений открытн 2) Лвторы изобрете. Благовещенский, Н. П, Куровский, В. В, Крючков и С, А. Соколов 1) Заявител УСТРОЙСТВО ОРТИРОВКИ ДВОИЧНЫХ ЧИСЕ Изобретение относится к области вычислительной техники и передназначено для сортировки массива двоичных чисел в порядке убывания или возрастания их величины.Известно устройство сортировки двоичных чисел, которое может быть использовано для решения указаиной задачи, Устройство работает по принципу упорядоченной выборки использованием, свойств ассоциативной памяти. Для поиока и выделения очередного сортирувмого признака необходимо выполнить большое число элементарных логических операций.В другом устройстве, каждое число из заданного множества увеличивается до тех пор, пока одно из них не достигнет зауавее задаиной величины, Логика обнаружения, связанная с этим числом, включается и указывает как на аднес числа во множестве, так и на само эисвремальное число. Это устройство со. держит и каналов счетчиков, соединенных по входу с,источником чисел, а по выходу с де. текторами фиксированного числа и через логическую схему - со счетчиком адреса экстремального числа и очетчикосм кодов.Прототипом изобретения является у 1 стройство для сортировки информации. Это устройство содержит маприцу ячеек, каждая из которых содержит элементы И и ИЛИ, причем первый вход элемента И соединен с первым входом ячейки, а выход - с первым входом элемента ИЛИ, выход которого соединен с первым выходом ячейки н со вторым входом последующей ячейки данной строки, 5 третьи входы ячеек соединены с шиной съемасоответствующего разряда, которая подключена к первым входам элементов И съема чисел, ко вторым входам которых подключена тактовая шина.10 Недостатком данного устройства являетсязначительное время задержки вывода экстремального числа, особенно при наличии в массиве нескольких одинаковых максимальных чисел.15 Целью изобретения является увеличение быстродействия устройства.Для достижения, этой цели каждая ячейкасодержит элемент запрета, сигнальный вход которого соединен с четвертым входом ячейки, 20 а выход - со вторым выходом ячейки, второйвход элемента И соединен с третьим входом ячейки, а второй вход элемента ИЛИ - с управляющим входом элемента запрета и с вторым входом ячейкикроме того, устройство 25 дополнительно содержит элемент задержки ив каждой строке - элемент НЕ, элемент запрета, элемент ИЛИ и трпггер, в каждом столбце - мпоговходовой элемент ИЛИ, причем второй выход каждой ячейки каждого Зо столбца соединен с соответствующим входом3многовходового элемента ИЛИ, выход которого соединен с ш;ьной съема соответствующего разряда, второй вход первой ячейки каждой строки соединен с единичным выходом триггера той же строки, а первый выход по,следней ячейки каждой строки через элемент НЕ соединен с первым сигнальным водом элемента запрета и первым входом элемента ИЛИ тойже строки, выход элемента ИЛИ каждой строки соединен со вторым входом элемента ИЛИ и управляющим входом элемента запрета последующей строки, вторые сигнальные входы элементов запрета каждой строки соединены с выходом элемента задер 2 кки, ко входу котояр ого подкл 1 очена тактовая шина, а выход элемента запрета каждой строки подключен к единичному входу триггера той же строки.На чертеже нродставлена схема устройства.Она содержит ячейки, образу 1 ощие матрицу 1, элементы НЕ 2, элементы запрета 3, элементы ИЛИ 4, триггеры 5, элементы задержки б, многовходовые элементы ИЛИ 7, элементы И съема чисел 8, Кроме того, какдая ячейка содержит элемент И 9, элемент запрета 10, элемент ИЛИ 11.С блока внешней памяти на устройство сортировки поступаюг и,т разрядных двоичных 1 ИСЕЛ Г 1 д Г 1 1ГУ 1 В В 1 , В 1 И Ид 1 И 1 СО СТЯР шим разрядом слева, представленных в прямом и инверсном коде. Шины прямых кодов всех чисел поразрядно через элементы запрета 10 соединены со входами и-входовых элемечтов ИЛИ 4, выходы которых поразрядно соединены с первыми входами элементов И 9, вторые входы которых подключены к шинам тех же разрядов инверсных кодов. Для каждого числа выходы элементов И 9 поразрядно соединяются с одним из входов элементов ИЛИ 11, выходы которык подключа 1 отся к управляющим входам элементов запрета 10 и вторым входом элементов ИЛИ 11 следующего младшего разряда. Выход элемента ИЛИ 11 старшего разряда подключается также к управля 1 ощему входу схемы запрета О того же разряда.Выход схемы ИЛИ 11 младшего разряда каждого числа кроме первого а и последнего и через элемент НЕ 2 подключен к первому сигнальному входу элемента запрета 3 и к первому входу элемента ИЛИ 4, выход которого подключен к управляющему входу элемента запрета 3 и второму входу элемента ИЛИ 4 числа с большим номером. Выход элемента ИЛИ 11 первого числа подключен че 1 рез элемент НЕ 2 к первому сигнальному входу элемента запрета 3 первого числа и к управля 1 ощему входу элемонта запрета 3 и второму входу ИЛИ 4 второго числа, а выход элемента ИЛИ 11 последнего числа через э,1 емспт НЕ 2 соединяется с сигналы 1 ым входом элемента запорота 3 этого же числа.Выходы элементов запрета 3 соединены с единичными входами триггеров 5, единичные выходы которых соединены со вторыми входа 1 О 15 2 О 26 зо 35 40 45 50 5 э о ми элементов ИЛИ 11 старшего разряда соответствующих чисел, а вторые сигнальные входы элементов запрета 3 через элемент задержки 6 соединены с тактовой щиной с которой соединяются также паровые входы эле,ментов И 8 съема чисел, вторые входы которых соединены с выходами многовходовых элементов ИЛИ 7.Работает ус 11 ройство следу 1 ощим образом.В каждом такте из массива и двоичных числе выделяется экстремальное, например максимальное, число, которое поступает на элементы И 8 сьема чисел через них передается во внешнюю буферную память, После съема максимального числа указапуным способом оно искл 1 очается из,рассматриваемого массива и, а среди оставшихся (и - 1) чисел производится выбор очередного максимального числа и передача его в следующий такт в буферную память. Танским образом производится передача всех чисел во внешнее устройство в порядке убывания или возрастания их значений.Рассмотрим,раздельно процесс выделения максимального числа из массива и чисел и процесс формирования убывающей последовательности этих чисел.При появлении на шинах, кодов исследуемых чисел выполняется, начиная со старшего разряда, их последовательный поразрядный анализ. В случае неравенства в анализируемых разрядах, т, е. если в данноьм разряде всех чисел имеется как О, так и 1, происходит исключение из процесса анализа всех более младших разрядов тех чисел, у,которых в данном разряде имеется О. Это исключение производится путем подачи 1 на управляющие входы элементов запрета 10, соответствующих разрядов.Пусть значение старших разрядов всех чисел равны О, В этом случае на выходе элемента ИЛИ 11 первого разряда и соответственно на втором входе элементов И 9 и их выводах будет поприсутствовать О, что обеспечивает прохождение прямых кодов во втором разряде, всех чисел на входы соответствующего многовходового элемента ИЛИ 7.В случае, если значения старших разрядов всех чисел равны 1, то состояние устройства аналогично вышеописанному, так как на первом входе элеме 1 нтов И 9, подключенных к шинам инверсного кода, будет О.Если в ста 1 ршем разряде чисел имеется неравенство, то произойдет совпадение 1 на входах элементов И 9; подключенных,к шинам инверсного кода чисел, у которых в старшем разряде имеется О, и на выходе этих схем появится 1, Это п 1 риведет к появлению 1,на выодах элементов ИЛИ 11 и на управляющих входах элементов запрета 10 относящихся к числам, имеющим в старшем разряде О, В результате эти числа исключаются из дальнейшего анализа, так как запре- н щается прохождение значении прямых кодов на элемент ИЛИ 7 всех последующих млад10 15 52ших разрядов. Оставшиеся числа анализируются во втором разряд и т. д. После окончания соавнени 5 в младшем (первом) разряде,на выходе элементов И:1 И 11 этого разряда будет присутствовать О только в том случае, если на выходах всех элементов И 9 того же числа, к которому относися данныйэлемент ИЛИ 11, будет также О. Этовозможно только в том случае, если ни в одном разряде этого числа не был сформировансигнал запрета в более младшие разряды,т. е. если это число максимально.Таким образом, по окончании поразрядногоанализа на выходах многовходовых элементов ИЛИ 7 формируется код максимальногочисла, а на выходах элементов ИЛИ 11младшего .разряда всех чисел - инверсный,позиционный код номера числа значение которого максимально.С выходов многовходовых элементовИЛИ 7 код максимального числа поступает на первые входы элементов И 8, съемачиселна другие объединенные входы которыхпоступает тактовый импульс, в момент появления которого производится съем кода и передача его на выход устройства,Тактовый импульс, задержанный на времясвоей длительности на элементе задержки бпоступает на все элементы запрета 3, соединенНые,по первым сигнальным входам с инвертированными на, элементах НЕ 2 выходами позицисИного кода номера числа. При совпадении задержанного тактового импульса ссигналом тех шин позиционного кода, которыесоответствуют максимальным для рассматриваемого момента числам, на выходе первогопо порядку элемента запрета 3 возникает импульс. Последний перебрасывает соответствуСщий триггер 5, выходной сигнал которогочерез элементы ИЛИ 11 исключает из дальнейшего анализа данное число, запрещая сгопрохождение через элементы запрета 10.Для возможнссти считывания всех одинакоВых чисел сигнал с шины позиционного кодапервого максимального числа поступает на управляющие входы элементов заПрета 3 всехпоследующих чисел (для второго непосредственно, а для остальных через элементыИЛИ 4), запрещая прохождеНия сигналовчерез элементы запрета 3 на входы триггеровТаким образом при наличии несколькиходинаковых чисел сни последовательно опрашиваются и,передаются во внешнюю буферную память. После съема всех чисел одногозначения происходит выбор описанным вышеспособом следующего наибольшего числа ипоследующей его съем очередным тактовымимпульсом. После съема всех чисел триггеры5 восстаНавливаются в исходное состояние подачей на них импульса сброса.Если требуется передать в буферную память возрастающую последовательность чисел,то устройство должно обеспечить выделениеминимального числа из имеющегося массива 20 2 д 30 35 4:1 45 50 ЭЭ 60 05 6чиел. Для этого неооходимо для каждого чис 1 псмсн 5 ть псразр 51 дцс Одна с друГОЙ тсч. и: ЦСД 1051 О Ч ЕЦ: 51 Ц 11 Ц ПР 51 МОГО И ИИВСЯЭ СИОГО кодоВ. ТО. дя В к 11 н, 1 ый 1 Омснт Времени ня Выходах многовходозых элсмсцтсз ИЛИ 7 будет присутствовать минимальное ч 1 сло цз име 10 гцсгсс 51 5 ассиза, чисе,1, предстаВленное В инверсном коде.Предлагаемое устройстВО хяряктбризетс 51 большим быстроде 1 ствием пс спдвнсни 10 с изВестными, которое определяется только задержками на элементах схемы. Кроме того, устройство позволяет без потерь информации сортировать тронзвольные массивы, включающие, например, ряд Одинаковых чисел. Формула изобретения УсроЙстВО для сортцрсв 1 и двоичных чисел, содержащее хатриц яСоккаждаярых содержит элемснты И и ИЛИ причем первый вход элемента И соедцнсн с первым Входом ячейк 11, а Выход - с,первым Входом элемента ИЛИ, выход которого соединен с псрвым выходом ячейки и со вторьв входом послед 1 сщеЙ яче 11 ки даной строки, третьи входы ячсск соединены с шиной съема соответствующего разряда, которая подключена к первым входам элементов И съема чисел, ко вторым входам которы.; подключена тактовая шина, отличающееся тем, что, с цельо увеличения быстродействия, каждая ячейкя содержит элемент запрета, сигнальный вход которого сосдцнеп с четвертым входом ячейни, а Выход - со вторым выходом ячецкп, Ворой вход элемента И соединен с третьим Входом ячейки, а второй вход элемента ИЛИ - с управляющим Входом элемента запрета ц с вторым Входом ячейки, кроме того, устройство дополнительно содержит элемент задержки и В каждои строке - элсме 11 т НЕ, элемент запрета, элемент ИЛИ и триггер, в каждом столбцс - многовходовой элемснт ИЛИ, причем второй Выход каждой ячейки каждого столбца соединен с соответствующим входом многовходового элемента ИЛИ, выход которого соединен с шиной съема соответствующего разряда, второй вход псрвой ячейки каждой строки соединен с единичным выходом трцггера той же строки, а первый выход послеДней ячейки каждой стро,ки через элемент НЕ соединен с первым ,сигняльцым входом элемента запрета и псрвым входом элемента ИЛИ той жс строки, ,выход элемента ИЛИ каждой строки соединен со вторым входом элсмента ИЛИ и упрязляОщим входом элемента запрета последую 1 цей строки, вторыс сигнальные входы эле,ментов запрета каждой строки соедцнены с выходом элемента задержки, ко входу которого подключена тактовая шина, а выход элемента запрета каждой строки подключен к единичному входу триггера той же строки,526888 Составитель В, Берез Техред 3. Тараненко дакто ляд Тираж 864митета Совета Министров СССРтений и открытийРаушская наб., д, 4/5 одписное ипограсЬия, пр. Сапунова, 2 каз 2180/5 Изд, Мо 1655 ЦНИИПИ Государственного к по делам изобр 113035, Москва, )К.З