Устройство для упорядочения @ чисел Советский патент 1989 года по МПК G06F7/06 

СП

о to

Изобретение относится к вычислительной технике и может быть использовано для построения возрастаюидих (Ь. bj. ) или убывающих (Ь,, b ;,.,) иариащюниых рядов В -{b{|i l.,n пз. массива чисел А а j | i 1,п|, -шдапного 13 виде произвольных значений дпончиого кода.

Цель изобретения - расширение об- ласти применения устройства за счет сортировки чисел большей разрядности при сохранении высокого, быстродействия .

На фиг. 1 показана схема устрой- С гиа; на фиг, 2 - сйема блока выделения HiULMeHbmero числа; на фиг. 3 - схем блока исключения наименьшего числа; на фиг. 4 - схема груплы эле- MenToi; lUIU.

Устройство содержит (фиг. 1) п блокои I ныделения наименьшего числа, (п-1) блоков 2 исключения наи- ;:иьшего числа, (п-2) групп элемен- гоБ И,Ш 3, груплы информационных вхо дор/кодов чисел А, А., ..., А,, группы 1шформадионных выходов кодов уно- р.чдоченмрях чисел В В ... В,,.

Блок 1 выделения наименьшего числа содержит nxm схем 4 анализа, го- ризонтальные ряды которых соеД1шены последовательно по линиям переноса и разрспенрш. Выходы переноса последних в рядах люгических схем с номерами 4 ,„ , ... ,,. . . , 4 п образуют выходы Z,, Z,..., Z блок1фования, а инфор г-мцнонные выходы вертикальных рядов лог11ческ1з схем 4 объединены и обра- ит1(;1Орманионные выходы Ь, Ь, ..., Ij 1 блока. Входы разрешения пер- ;юго столбца схем анализа соединены с входом логического нуля, а входы устроГютва лереноса являются входами олокирования Р,, Р,..., Рр входных чисе:1 блока. Информационные входы го ризонта-чьных рядов логических схем образу/а груллы А ,, А ,.,,..., А „ входо к одпн чисел,

С::сма 4 анализа состоит из двух- иходового элемента ИЛИ 5, элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6 и трехвходового з ;с мента ИЛИ 7. Два входа элемента 5 об-ьединены с двумя входами эле illlll 7 и образуют входы переноса Р и разрешения R логической схемы Tperufi вход элемента ИЛИ 7 соединен с первым входом элемента ИСГЛЮ ШОЩЕЕ 11ТИ б м информациошам входом а схе мы анализа. Второй вход элемента 6 и

выход элемента 7 образуют информа- ционньп выход Ь, а выходы элементов ИЛИ 5 и ИСКЛЮЧАЮЩЕЕ ИЛИ 6 являются выходами переноса и разрешения соответственно .

Блок 2 исключения наименьшего числа (фиг. 3) состоит из п элементов ИЛИ, первые входы которых образуют входы блока, а выходы каждого i-ro элемента- (, п-1}) соединены с. (1+1)-ми входами всех элементов с номерами от (i+l) до п. Выходами блока являются выходы элементов ИЛИ.

Устройство работает следующим образом.

Двоичные коды чисел исходного массива параллельно подаются на группы входов А , А 2,..., А „так, что а,. - старший разряд, а, - младший. Способ формирования этих кодов не ,ограничивается. Например, они могут быть записаны в буферном регистре, как это сделано в прототипе.

Все коды чисел параллельно поступают на все п блоков 1 выделения наименьшего числа. В первом из них происходит выделение наименьшего числа, код которого формируется на группе выходов В. Одновременно на выходах Z,, Z, ..., Z f, вырабатываются уровни логического 0 на тех выходах, номер которых соответствует номеру группы входов А,,..., А р с наименьшим числом. Таким образом, если во входной комбинации имеется несколько одинаковых и наименьших чисел, то на выходах Z,, Zj,..,, Zр также присутствует несколько уровней логического нуля. В блоке 2 исключения наименьшего числа по сигналам Z,, Z ,., ., Z выбирается и передается на выход Р. в виде уровня логической единицы тот которьм имеет на 1меньший номер j, т.е. из множества одинаковых наименьших чисел выбирается одно с наименьшим номером. Сигналы Р.,, Р,..., РГ, поступают на входы Р, Р,,, . .. , Р„ второго блока 1 и уровень логической единицы на линии Р . исключается наименьшее число, выделенное в блоке 1 из дальнейшего рассмотрения. Таким образом, блок 1, выделяет наименьшее из оставшихся чисел и т.д. На выходах В „ сформировано наибольше число.

Для формирования ускоренного переноса исключающих сигналов предназначены группы элементов ИЛИ 3. При это

сигнал Pj 1 одновременно действует на соответствующие входы Р, всех последующих блоков вьщеления наименьшего числа, практически одновременно исключая число А. из анализа.

Па выходах В,, В.,..., В„ сформирована упорядоченная последовательность кодов чисел из входного массива А,, Aj,

АПБлок 1 вьщеления наименьшего числа построен по комбинационной схеме и работает следующим образом.

На горизонтальные ряды схем 4 ана лиха подаются двоичные коды исходных чисел так, что а - соответствует- старшему разряду, а ,. - младшему. Из комбинации входных кодов анализируются только те, для которых на входах Р,- и Р; присутствуют уровни логического нуля.

В блоке 1 использован алгоритм поразрядного сравнения чисел. Такое сравнение выполняется вертикальными рядами схем анализа. Если хотя бы в одном числе в старшем разряде присутствует 0, то этот 0 передается на выход элемента ИЛИ 7 (при наличии уровней 0 на двух других его входах) и соответственно на информа- Щ10ННЫЙ выход логической схемы 4. Та как 1тформационные выходы вертикальных рядов схем анализа объединены, то этот уровень логического нуля блокирует все уровни логической единицы на выходах элемента ИЛИ 7 других схем анализа, на которых поданы заведомо большие числа.

При наличии такого блокирования на выходе элемента ИСКЛПЧАИи ЕЕ ИЛИ 6 вырабатывается уровень логической единицы, который поступает на выход разрешения данной схемы 4 анализа и, транспортируясь через все остальные схемы анализа в горизонтальном ряду, исключает данное заведомо большее число из рассмотрения, а на выходе Ь формируется уровень 0.

Предположим, что во втором разряде из оставшихся чисел все имеют уровни 1, тогда и на выходе Ь будет уровень 1. Если в третьем разряде хотя бы в одном из оставшихся чисел будет присутствовать уровень 0, то на bj будет 0, а из дальнейшего рассмотрения будут исключены те числа, в которых а ,5 1

В последнем т-м вертикальном столбце анализируется последний младший разряд. Те числа из оставшжся, в которых а , 1 0, и есть наименьшие. При этом на выходах блокирования Z

соответствующим наименьшим числом выработаются уровни логического нуля, на остальных - логической единицы.

Предложенное решение блока I выделения наименьшего числа отличается

высоким быстродействием, которхэе оценивается как (m+l)r и не зависит от количества чисел п.

Формула изобретения

1. Устройство для упорядочения п

чисел, содержащее п блоков выделения наит-1еиьшего числа и группу элементов ИЛИ, отличающееся тем, что, с целью расширения области применения за счет сортировки чисел

большей разрядности, в него введены (п-1) блоков исключения наименьшего числа и (п-3) групп элементов ИЛИ, причем информационные входы устройства подключены соответственно к поразрядно объединенным информационным входам всех блоков выделения наименьшего числа, выходы блокирования i-ro блока вьщеления наименьшего числа

(i 1,..., п-1) соединены с соответствующими входами i-ro блока исключения наименьшего числа, выходы j-го блока исключения наименьшего числа (J 2,..., п-1) соединены с соответствующими входами первой группы входов элементов ИЛИ К-й группы (К 1,..., п-2), выходы которых соединены с соответствующими входами разрешения ()-го блока выделения наименьшего числа, выходы элементов ИЛИ 1-й группы (1 1,..., п-3) соединены с соответствующими входами второй группы входов элементов ИЛИ (1+1)-й группы, выходы первого блока исключе

ния наименьшего числа соединены с

соответствующими входами второй группы входов элементов ИЛИ первой группы, группы входов блокирования первого и группы входов разрешения первого

и второго блоков вьщеления наименьшего числа соединены с входом лoг fчec- кого нуля устройства, информационные выходы р-го блока вьделения наименьшего числа являются р-ми инАормационными выходами устройства (р 1 , . . . , п).

2. Устройство по п. 1, от л и - чающееся тем, что блок выделения наименьшего числа сод( матрицу (пл т) схем анализа (п - число строк, m - число столбцов), схема анализа содержит первый и второй элементы ИЛИ, элемент ИСКЛЮЧАЮПЕЕ ИЛИ, причем первый и второй входы пе.рвого элемента ИЛИ соответственно соединены с первым и вторым входами второго элемента ИЛИ, трет11й вход которого соединен с первьм входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, второй вход которог соединен с выходом второго элемента ИЛИ, причем первый и второй входы первого элемента ИЛИ ij-й схемы анализа (i 1,...,п, j 2,...,m) COOT ветственно соединены с выходами первого элемента ИЛИ и элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 1(з-1)-й схемы анализа, в

1-м столбце (1 1,., га) выходы вто рых элементов ИЛИ всех схем анализа объединены по схеме монтажного И и являются выходом блокирования блока 914деления наименьшего числа, li-й информационный выход блока вьщеления наименьшего числа соединен с первым входом элемента ИСКЛЮЧАЮЩЕЕ ИЛИ li-й схемы аиализа, первый и второй входы первого элемента ИЛИ (11)-и схемы анализа соединены соответственно с . i-M входом блокирования и i-м входом разрешения блока выделения наименьшего числа, выходы первого элемента ИЛИ im-й схемы анализа являются i-м информационным выходом блокирования блока вьщеления наименьшего числа.

Изобретение относится к автоматике и вычислительной технике и может быть использовано при построении средств обработки данных. Цель изобретения расширение области применения за счет сортировки чисел большей разрядности. Устройство содержит N блоков 1 выделения наименьшего числа, (N-1) блоков 2 исключения наименьшего числа и (N-2) групп элементов ИЛИ 3. Блок выделения наименьшего числа содержит матрицу (N^.M) схем анализа. Схема анализа содержит два элемента ИЛИ и элемент ИСКЛЮЧАЮЩЕЕ ИЛИ. Устройство построено по комбинационной схеме, не требует синхронизации, отличается простотой, однородностью структуры и высоким быстродействием. Быстродействие устройства зависит от количества одновременно обрабатываемых чисел. 1 з.п. ф-лы, 4 ил.

Д/fty

1т //п

f,

5