Устройство для сортировки двоичных чисел
п) 526888 ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ
СоЮа Советских
Социалистических
Республик (б1) Дополнительное к авт, свид-ву (22) Заявлено 03.06,74 (21) 2029015, 24 (51) М. Кл.2 С 06F 7, 00 с присоединением заявки ¹
Государственный комитет
Совета MNHHGTpOB СССР по делам изобретений и открытий (23) Приоритет
Опубликовано 30.08.76. Бюллетень № 32
Дата опубликования описания 20.10.7б (53) УДК 681.322(088.8) (72) Лв тор ы изобретения
И. М. Благовещенский, H. П. Куровский, В. В. Крючков и
С. А. Соколов (71) Заявитель (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ
Изобретение от носится к области вычислительной техники и пред назначено для сорти ровки массива двоичных чи|сел в порядке убывания или возрастания их величины.
Известно устройство сортировки двоичных чисел, которое может быть использо ва но для решения у каза иной задачи. Устройство работает по п ри нципу упорядоченной выборки использованием, свойств ассоциативной па мяти. Для поиока и выделения очередного сортируемого признака необходимо выполнить большое число элементарных логических OIIeраций.
В другом устройстве, каждое число из заданного множества увеличивается до тех пор, пока од но из них не достигнет заранее зада и.ной BåëH iHIHbI Логика обнаружения, связанная с этим числом, включается и указывает ка к íà apipec числа во множестве, так и на само экс времаль ное число. Это устройство содержит и каналов IcBeTчиков, соединенных IIo входу с,источником чисел, а по выходу с детекторами фикси рова нного числа и через логическую схему — со счетчиком адреса экстремаль ного числа и счетчиком кодов.
Прототипом изобретения является "cTpoHCTво для сортировки и нформации. Это устройство содержит мапр ицу ячеек, каждая из которых соде ржит элементы «И» и «ИЛИ», причем первый вход элемента «И» соединен с первым входом ячейки, а выход — с первым входом элемента «ИЛИ», выход которого соединен с первым выходом ячейки и со вторым входом последующей ячейки данной строки, третьи входы ячеек соединены с шиной съема соответствующего разряда, которая под ключена к первым входам элементов «И» съема чисел, ко вторым входам KQTophlx подключена тактовая шина.
10 Недостатком данного устройства является значительное время задержки вывода э кстремального числа, особенно при наличии в массиве нескольких одинаковых максимальных чисел.
15 Целью изобретения является увеличение быстродействия устройства.
Для достижения, этой цели каждая ячейка содержит элемент запрета, сигнальный вход которого соединен с четвертым входом ячейки, 2О а выход — со вторым выходом ячейки, второй вход элемента «И» соединен с третьим входом ячейки, а второй вход элемента «ИЛИ» — c управляющим входом элемента запрета и с вторым входом ячейки,,кроме того, устройство
25 дополнительно содержит элемент задержки и в каждой строке — элемент «НЕ», элемент запрета, элемент «ИЛИ» и триггер, в каждом столбце —.мпоговхоло вой элемент «ИЛИ», причем второй выход каждой ячейки каждого
ЗО столбца соединен с соответствующим входом
526888
3 многовходового элемента «ИЛИ», выход которого соединен с ш;ьной съема соответствующего разряда, второй вход первой ячейки каждой строки соединен с единичным выходом триггера той же строки, а первый выход по,следней ячейки каждой строки через элемент
«НЕ» соединен с первым сигнальным в одом элемента запрета и первым входом элемента
«ИЛИ» той же строки, выход элемента
«ИЛИ» каждой строки соединен со вторым входом элемента «ИЛИ» и управляющим входом элемента запрета по следующей cTipoки, вторые сигнальные входы элементов запрета каждой строки соединены с выходом элемента з Ядерщик ки, ко B Yoga KQTopoI о подкл1очена тактовая шина, а выход элемента запрета каждой строки подключен к единичному входу триггера той же строки.
На чертеже нродставлена схема устройства.
Она содержит ячейки, образующие матрицу
1, элементы «НЕ» 2, элементы запрета 3, элементы «ИЛИ» 4, триггеры 5, элементы задержки б, многовходовые элементы «ИЛИ» 7, элементы «И» съема чисел 8. Кроме того, каждая ячейка содержит элемент «И» 9, элемент запрета 10, элемент «ИЛИ» 11.
С блока внешней памяти на устройство coipтировки поступаюг и,nz разрядных двоич ных чисел а„, а„., 1...аьв,„в„„....в,...,n»,n, 1nI со старшим разрядом слева, представленных в п рямом и инверсном коде. Шины прямых кодов всех чисел поразрядно через элементы запрета 10 соединены со входами и-входовых элемечтов «ИЛИ» 4, выходы которых поразрядно соединены с первыми входами элементов «И»
9, вторые входы которых подключены к шинам тех же разрядов инверсных кодов. Для каждого числа выходы элементов «И» 9 поразрядно соединяются с одним из входо в элементов «ИЛИ» 11, выxoIäû которых подключаются к управляющим входам элементов запрета 10 и вторым входом элементов «ИЛИ»
11 следующего младшего разряда. Выход элемента «ИЛИ» 11 ста ршего разряда подключается также к уп ра вля|ощему входу схемы запрета О того же разряда.
Выход схемы «ИЛИ» 11 младшего разряда каждого числа кроме первого а и последнего и через элемент «НЕ» 2 подключен к первому сигнальному входу элемента запрета 3 и к первому в оду элемента «ИЛИ» 4, выход кото рого подключен к управляющему входу элемента запрета 3 и второму входу элемента «ИЛИ» 4 числа с большим номером. Выход элемента «ИЛИ» 11 первого числа подключен через элемент «НЕ» 2 к первому сигнальному входу элемента запрета 3 первого числа и к уп равляющему входу элемонта запрета 3 и второму входу «ИЛИ» 4 второго числа, а выход элемента «ИЛИ» 11 последнего числа че.pP3 э. IPXIcHT «НЕ» 2 coBIH HiIBTcB c си г HB 75Hbtl вхо ом элемента з" ïðåòà 3 этого же числа.
Выходы элементов запрета 3 соединены с единичными входами триггеров 5, единичные выходы которых соеди Ipíû со вторыми входа10
2о
3О
PO ми элементов «ИЛИ» 11 старшего разряда соответствующих чисел, а вторые сигнальные входы элементов запрета 3 через элемент задержки 6 соединены с тактовой шиной с которой соединяются также паровые входы эле,ментов «И» 8 съема чисел, вто рые входы которых соединены с выходами многовходовых элементов «ИЛИ» 7.
Работает устройство следующим образом.
В каждом такте из массива и двоичных числе выделяется экстремальное, например максимальное, число, которое поступает на элементы «И» 8 сьема чисел через них передается во внешнюю буферную память. После съема максимального числа указа пуным способом оно искл|очается из,рассматриваемого массива и, а с реди оставшихся (и — 1) чисел производится выбор очередного максимального числа и передача его в следующий такт в буферную память. Таким образом производится передача всех чисел во внешнее устройство
B порядке убывания или возраста|ния их значений. рассмотрим,раздельно процесс выделения максимального числа из массива и чисел и процесс формирования убывающей последовательности этих чисел.
При появлении на шинах, кодов исследуемых чисел выполняется, начиная со старшего разряда, их последовательный поразрядный анализ. В случае неравенства в анализи руемых разрядах, т. е. если в данном разряде всех чисел имеется как «О», так и «1», происходит исключение из п роцесса анализа всех более младших разрядов тех чисел, у,которых в данном разряде имеется «0». Это исключение производится путем подачи «1» на управляющие входы элементов запрета 10, соответствующих разрядов.
Пусть значение старших разрядов всех чисел равны «О». В этом случае на выходе элемента «ИЛИ» 11 первого разряда и соответственно на втором входе элементов «И» 9 и их выводах будет поприсутствовать «О», что обеспечивает п рохождение прямых кодов во втором разряде, всех чисел на входы соответствующего многовходового элемента «ИЛИ» 7.
В случае, если значения старших разрядов всех чисел равны «1», то состояние уст|ройства а налогично вышеописанному, та к как на первом входе элементов «И» 9, подключенных к шинам инверсного .кода, будет «О».
Если в ста ршем разряде чисел имеется неравенство, то произойдет совпадение «1» на входах элементов «И» 9; подключенных,к шинам инверсного кода чисел, у которых в ста ршем разряде имеется «О», и на выходе этих схем появится «1». Это п риведет к появлению
«1»,на вы одах элементов «ИЛИ» 11 и на управляющих входах элементов запрета 10 относящихся к числам, имеющим в старшем разряде «0». В результате эти числа исключаются из дальнейшего анализа, так как запрещается прохождение значении прямых кодов на элемент «ИЛИ» 7 всех последующих млад
Э
52
O ших разрядов. Оставшиеся числа анализируются во втором разряд и т. д. После окончания соавнения в младшем (первом) разряде, на выходе элементов «И:1И» 11 этого раBp;iда будет присутствовать «0» только в том случае, если на выходах всех элементов «И» 9 того же числа, к которому относится данный элемент «ИЛИ» 11, будет та кже «0». Это возможно толь ко в том случае, если ни в одно м разряде этого числа не был сформирован сигнал запрета в более младшие разряды, т. е. если это число максимально.
Таким образом, по окончании поразрядного а нализа на выхо|да lìíîãoBõîäoBûõ элементов «ИЛИ» 7 форми руется код максимального числа, а IH2 выходах элементов «ИЛИ» 11 младшего .разряда всех чисел — инверсный,позиционный код номера числа значение которого максимально.
С выходов многовходовых элементов
«ИЛИ» 7 код максимального числа поступает на первые входы элементов «И» 8, съема чисел,,на другие объединеыные входы которых поступает тактовый импульс, в момент появления которого производится съем кода и передача его на выход устройства.
Тактовый импульс, задержанный на время своей длительности на элементе задержки б поступает на все элементы запрета 3, соединен|ные;по первым сигнальным входам с инверти рова н ными на, элементах «НЕ» 2 выходами позициOtHIHQIO кода номера числа. При совпадении задержанного та ктового импульса с сигналом тех шин позицио|нного кода, которые соответствуют максимальным для рассматриваемого момента числам, на выхо де первого по порядку элемента запрета 3 возникает импульс. Последний перебрасывает соответству1сщий триггер 5, выходной сигнал которого через элементы «ИЛИ» 11 исключает из дальнейшего анализа да нное число, запрещая сго прохождение через элементы запрета 10.
Для возмож нссти считывания всех одинаковых чисел сигнал с шины позиционного кода первого максимального числа поступает на управля!Ощие в оды элементов за прета 3 всех последующих чисел (для второго непосредствен|но, а для остальных через элементы
«ИЛИ» 4), запрещая прохождения сигналов че рез элементы запрета 3 на входы триггеров
Э.
Таким образом при наличии нескольких одинаковых чисел с ни последовательно опрашиваются и,передаются во внешнюю буферную память. После съема всех чисел одного значения прои сходит выбор описанным выше способом следующего наибольшего числа и последующей его съем очередным тактовым импульсом. После съема всех чисел триггеры
5 восста навливаются в исход ное .состояние подачей на них импульса сброса.
Если требуется передать в буферную память возрастающую последовательность чисел, то устройство должно обеспечить выделение минимального числа из имеющегося массива 0
2 3
4:1
ЭЭ
6 чи ел. Д, 151 этого необ5ходимо для каждого чис ill псъ!сн51ть псрязр51днс од на с друГОЙ точК:l ПСДК, !!0×ÑÏ !51 111! .Н ПР51МСГО П 1! I!BC РСНОГО
То. I2 В к 1н . !ыЙ 410310НТ BPB5IPIIII ня
Выходах многовходозых элсмснтсз «ИЛИ» 7 будет присутствовать мини!2.7ьное ч 1сло из име10щсГося 312cci!32, чисе, i, представленное В инверсном коде.
Предг1ягясмое х стройстВО харякт6риз етс51 большим быстродействием по сравнению с известными, которое определяется только задержках!и на элементах схемы. Кроме того, устройство позволяет без потерь информации сортировать т!роизвольные массивы, включающие, например, ряд оди наковых чисел.
Формула изобре Тония
УСТРО!!СТВО + 751 coPTI!PQBI ВХОДОМ Псе.7ЕД1 IOЩЕЙ ЯЧРИК11 Д2ННОЙ СТРОКИ, третьи вход.ы ячсск соединены с шиной съема соответствующего разряда, которая подклю;ена к первы 2 входам элементов «И» съема чисел, .ко вторым входам которы;. подключена тактовая шина, o T.71!ч а ю щ се с я тем, что, с цсль!о увеличения быстродействия, каждая ячей кя содержит элемент запрета, сигнальный вход которого сосдинеп с четвертым входом я1ейки, а выход — со вторым выходом ячейки, BToðîé вход элемента «И» соединен с третьим Входом ячейки, а второй вход элемента «ИЛИ» — с упр",âëÿþùèì входом элемента запрета и с вторым Входом ячейки, кроме того, устройство дополнительно содержит элемент задepжl.и и В каждси строкe — э.7смегlт «ÍÅ», элеменT запрета, элемеHт «ИЛИ» и триггер. в каждом сто Iolic — многовходовой элемснт «ИЛИ», причем второй Выход каждой ячейки ка<ждого столбца соединен с соответствующим входом многовходового элемента «ИЛИ», выход которого соединен с шиной съема соответствующего разряда, второй вход пс рвой ячейки каждой строки соединен с единичным выходом триггера той же строки, а первый выход последней ячейки каждой стро,ки через элемент «НЕ» соединен с первым ,сигнальным входом элемента запрета и первым входом элемента «ИЛИ» той жс строки,,выход элемента «ИЛИ» каждой строки соединен со вторым входом элемента «ИЛИ» и упрявля1ащим входом элемента запрета последую!цей строки, вторыс сигнальные входы эле,ментов запрета каждой строки соеди|нены с выходом элемента задержки, ко входу которого подключена тактовая шина, а выход элемента запрета кажчой строки подключен к единичному входу триггера той же строки. 526888 Составитель В. Березкин Техред 3. Тараненко Редактор H ..Коляда Корректор Е. Хмелева Подписное Типография, пр. Сапунова, 2 Заказ 2180/5 Изд. М 1655 Тираж 864 ЦНИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий 113035, Москва, )К-35, Раушская наб., д. 4/5
