Устройство для сортировки двоичных чисел Советский патент 1976 года по МПК G06F7/00 

1

ИзОбретение отаооится IK области вычислительной техники и предиазначено для сорти|ров:ки Массива двоичяых чисел в порядке убывания или возрастания их величины.

Известно устройство СС рТИ рОВКИ ДВОИЧ.ЦЫХ

чисел, iROTOpoe может быть использовано для решения указаиной задачи. Устройство работает ПО прииЦИ:пу упорядоченной выборки с Использованием свойств ассоциативеой памяти. Для потока и выделения оч ередного сортируемого призяаКа необходимо выполнить большое число элементарных логи чеоких операций.

В Д1руг01М устройстве :каждое число «з заданного множества увеличивается до тех пор, пока одно из них не достигнет зар:анее заданной величины. Логика обнаружения, связанная с этИМ числом, В:ключается и указывает как и а адрес числа во 1множестве, так и на само экстремальное число. Это устройство содержит п каналов счетчиков, соединенных по входу с источником чисел, а по выходу с детекторами фиксированного числа и через логическую схему- со счетчиком адреса экстремального числа и счетчиком кодов.

Прототипом изобретения является устройство для сортировки информации. Это уст1ройство содержит мат1рицу ячеек, каждая из которых содержит элементы «И и «ИЛИ, причем первый вход элемента «И соединен с

первым входом ячейки, а выход - с первым входом элемента «ИЛИ, выход которого соединен с первым выходом ячейки и со вторым входом последующе данной строки, третьи входы ячеек соединены с шиной съема соответствующего разряда, которая подключена к цервым входацм элементов «И съема чисел, ко вторым входам которых подключена тактовая шина.

Недостатком данного устройства является значительное время задерж1ки вывода экстремального числа, особенно цри наличии в .массиве нескольких одинаковых максимальных чисел.

Целью изобретения является увеличение быстродействия устройства.

Для достижения, этой цели каждая ячейка содержит элемент запрета, сигнальный вход которого соединен с четвертым входо1М ячейки, а выход - со вторым выходом ячейки, второй вход элемента «И соединен с третьим входом ячейки, а второй вход элемента «ИЛИ - с управляющим входо м элемента запрета и с вторым входом ячейки, кроме того, устройство дополнительно содержит элемент задержки и в каждой строке - элемент «НЕ, элемент запрета, элемент «ИЛИ и триггер, в (каждом столбце - многовходовой элемент «ИЛИ, причем второй выход каждой ячейки 1каждого столбца соединен с соответствующим входом

iMHOroBXOAOBoro элемента «ИЛИ, выход которо го Соединен с шшюй съема соответсгвующего р.азряда, второй вход первой ячейки Каждой строки соеди-нен с единичным выходо-м триггера той же строки, а первый выход последней ячейки каждой строчки через «НЕ ооедИИея с первым сигнальным входом элемента запрета и первым входом элемента «ИЛИ той же строки, выход элемента «ИЛИ каждой строки соединен со вторы:м входом эле;мента «ИЛИ и уп ра:вляющим входом элемента запрета последуюш,ей строки, вторые сигнальные входы элементов занрета каждой строки соединены ic выходоМ злел1е«та задержки, ко входу которого подключена тактовая шина, а выход элемента запрета каждой строки подключен к единичному входу триггера той же строки.

На чертеже нредставлеиа схема устройства.

Она содержит ячейки, образующие матрицу 1, элементы «НЕ 2, элементы запрета 3, элементы «ИЛИ 4, триггеры 5, элементы задержки 6, мнОГовходовые элемепты «ИЛИ 7, элементы «И съема чисел 8. Кроме того, каждая ячейка содержит элемент «И 9, элемент запрета 10, элемент «ИЛИ 11.

С блока впешней памяти иа устройство сортировки поступают п,т |ра3рядных двоичных чисел а-т ...ai,em 0,,,-i...ei...,rtm «m-1 tti CO старшим разрядом слева, представленных в пряMOiM и инверсном коде. Шипы прямых кодов всех чисел поразрядно через элементы запрета 10 соединены со входами п-входовых э;1еМентов «ИЛИ 4, выходы которых поразрядно соединены с первыми входами элементов «И 9, вторые входы которых подключены к шинам тех же разрядов инверсных кодов. Для каждого числа выходы элементов «И 9 поразрядно соедипяются с одним из входов элементов «ИЛИ И, выходы которых подключаются ,к управляюш,И|М входа;м элементов запрета 10 и вторым входОМ элементов «ИЛИ И следующего ;младшего разряда. Выход элемента «ИЛИ 11 старшего разряда подключается также К управляющему входу .схемы запрета 10 того же разряда.

Выход схемы «ИЛИ И младшего разряда каждого чисЛа кроме первого а и последнего п через элемент «НЕ 2 подключен к первОму сигнально1му входу элемента запрета 3 и к первому входу элемента «ИЛИ 4, выход которого подключен к управляющему вхо1ду элемента запрета 3 и второму входу элемента «ИЛИ 4 числа с большим номером. Выход элемента «ИЛИ И первого числа подключен через элемент «НЕ 2 к первому сигнальн0му входу элемента запрета 3 первого числа и к )правляющему входу элемента, запрета 3 и второму входу «ИЛИ 4 второго числа, а выход элемента «ИЛИ 11 последнего числа через элемент «НЕ 2 соединяется с сигнальным входом элемента, запрета 3 этого же числа.

Выходы элемептов запрета 3 соединены с единичными входа ми триггеров 5, единичпые выходы Которых соединены со вторыми входами элементов «ИЛИ И старшего разряда соответствующих чисел, а вторые сигнальные входы элементов запрета 3 через элемент задержки 6 соединены с та.ктовой шиной с которой Соединяются также первые входы эле.ментов «И 8 съема чисел, вторые входы которых соединены с выходами .многоеходовых элементов «ИЛИ 7.

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

В каждом TaiKTe из массива я двоичных числе выделяется экстремальное, иапример маКсимальное, число, которое поступает па элементы «И 8 съема чисел через них передается во внешнюю буферную память. После

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

буфер.ную намять. Таким образом производится .передача всех чисел во внешнее устройство в порядке убы.вания илИ возрастания их значений.

Рассмотрим раздельно пропесс выделения

максимального числа из массива я чисел и НрОЦесс формирования убывающей последовательнОСти этих чисел.

При появлени.и на шинах кодов исследуемых чисел выполняется, пачииая со старШего

разряда, их последовательный поразрядный анализ. В случае неравенства в анализируемых разрядах, т. е. если в данном разряде всех .чисел имеется .как «О, так и «1, происходит исключение из процесса а.нализа всех

более 1мл.адших разрядов тех чисел, у которых в данном разря.де имеется «О. Это исключение пр.оизводится путем по.дачи «1 на управляющие входы элементОВ запрета 10, соответствующих разрядов.

Пусть значение старших .разрядов всех чисел равны «О. В этом случа.е на выходе элемента «ИЛИ И первого разряда и соответственно на BTO.pOiM вхо.де элем.ентов «И 9 и их выводах будет присутствовать «О, что обеспечива.ет прохождение пря.мых кодов во втором разряде .всех чисел на входы соответствующего .многовходового элемента «ИЛИ 7.

В случае, если значения старших разрядов всех чисел равны «1, то состояние устройства аналогично вышеони1санно1му, так как на нервом входе элементов «И 9, подключенных к шинам инверсного кода, будет «О.

Если в старшем разряде чисел имеется неравенство, то произойдет совпадение «1 на

входах элементов «И 9; подключенных к шинам инверсного кода чисел, у которых в старшем разряде имеется «О, и ща выходе этих схем .появится «1. Это приведет к появлению «1 на выходах элементов «ИЛИ 11 н на управляющих входах элементов занрета 10 относящихся к числам, имеющим в старшем разряде «О. В результате эти числа исключаются из дальнейшего анализа, так как запрещается прохождение значений прямых кодов

на эле.мент «ИЛИ 7 всех последующих мла.дших разрядов. Оставшиеся числа а1нализи,руются во втором Разряде и т. д. Помеле окОНчания сра внения в Мла.дшсм (первом) раЗ:ряде, «а выходе элементов «ИЛИ 11 этого разряда будет присутствовать «О только в том случае, если 1на выходах всех элементов «И 9 того же числа, к которому относится данный элемент «ИЛИ 11, будет также «О. Это возможно только iB TOiM случае, если ни в одHOIM разряде этого числа «е был сформирован сигнал запрета в более младшие разряды, т. е. если это число -максимально.

Таким образом, по окончании поразрядного анализа «а выходах 1м«оговходовых элементов «ИЛИ 7 формируется код максим-ального числа, а «а выходах элементов «ИЛИ 11 младшего разряда всех чисел - инверсный позиционный код номера чи1сла значение а оторого ма1кси ма-льно.

С выходов |МНОГО-входовых элементов «ИЛИ 7 код максимального числа поступает на первые входы элементов «И 8, съема чисел, на другие Объединенные входы которых поступает тактовый импульс, в момент появления которого производится съем жода н передача его на выход устройства:.

Тактовый импульс, задержанный на время своей длительности на элементе задержки 6 постунает на все элементы запрета 3, соединенные но первым сигнальнЫМ входа с инвертированными на элемента-х «НЕ 2 выходами нознционното кода номера числа. При совпадении задержанного тактового импульса с оитналОМ тех шин позиционного кода, которые соответствуют максимальным для рассматриваемого мо мента числам, на выходе первого по порядку элемента 3 возникает импульс. Последний перебрасывает соответствующий триггер 5, выходной сигнал которого через элементы «ИЛИ 11 исключает из дальнейшего анализа данное число, запрешая его прохождение через элементы запрета 10.

Для возм1ожности считывания Всех одинаковых чисел сигнал с шины позиционного кода neipBOFo Макси1мального чи1сла поступает на управляющие вхОДЬ элементов запрета 3 всех последующих чисел (для второго непосредственно, а для 0|Стальных через элементы «ИЛИ 4), запрещая прохождения сигналов через элементы запрета 3 на входы триггеров 5.

Таким образом нри наличии нескольких одинаковых чисел они последовательно опрашиваются и Передаются во внбшн:юю буферную намять. После съема всех чисел одного значения происходит выбор описанны1М выше способом следующего наибольшего числа и по следующей его съем очер-едным тактовым импульсом. После съема всех чисел триггеры 5 восстанавливаются в исходное со стояние подачей на них импульса сброса.

Если требуется передать в буферную память возрастающую последовательность чисел, то устройство должно обеспечить выделение минимального чИСла из имеющегося 1массива

чисел. ДТЯ этого необходимо для каждого числа поменять поразрядно одна с другой точки подключения шли прямого и inniCipciioro кодов. Тогда в каждый МОМсЯТ времени на

выходах многовходовых элемеитов «ИЛИ 7

будет присутствовать минимальное число из

имеющегося массива, чисел, представлеНное в

инверсном коде.

Предлагаемое устройство характеризуется

большим быстродействием по сравнению с известными, которое определяется только задержками на элементах схемы. Кроме того, стройство позволяет без потерь информации сортировать произвольные масси:вы, включающие, нанрИМер, ряд одинаковых чисел.

Фор м у л а изо ю р е г е н н я

Устройство для сортировки двоичных чисел, содержащее матрицу ячеек, -каждая из которых содержит элементы «И и «ИЛИ причем первый вход элемента «И соединен с

первым входом ячейки, а выход - с первым входом элемента «ИЛИ, выход Которого соедин-ен с первым выходом ячейки « со вто-рым входом последующей ячейки данной строки, третьи входы ячеек соединены с шиной съема

соответствующего разряда, которая подключена К первым входам элементов «IT съема чисел, :ко вторым входа1М которых подключена тактовая шина, отличающееся тем, что, с целью увеличения быстродействия, каждая

ячейка содержит элемент запрета, сигнальный вход которого соединен с четвертым входо1М ячейки, а выход - со вторым выходом ячейки, второй вход элемента «И соединен с третьим входо:М ячейки, а второй вход элемента

«ИЛР1 - с управляющим входом элемента запрета и с вторым входом ячейки, кроме того, стройство дополнительно содержит элемент задержки и в каждой строке - элемент «ИЕ, элемент запрета, элемент «ИЛИ и

триггер, в Каждом столбце-Многовходовой элемент «ИЛИ, причем второй выход каждой ячейки каждого столбца соединен с соответствующим входом многовходового эле-мента «ИЛИ, выход которого соединен с шиной

съема соответствующего разряда, второй вход первой ячейки -каждой строки соедиНен -с единичным выходом триггера той же строки, а первый выход последней ячейки каждой стро-кп через элемент «ИЕ соединен с первым

сигнальным входом элемента запрета и первым входом элемепта «ИЛИ той же строки, выход элемента «ИЛИ калудой строки соединен со вторым входом элемента «ИЛИ и vnравляющим входом элемента запрета- последую-пд,ей строки, вторые сигнальные входы эле.ментов запрета а-саждой строки 1соединепы с выходом элемента задержки, ко вход} кото-рого подключена тактовая шина, а выход эле-мента заирета каждой Строки подключ-ен к

единичному триггера той же строки.

1 -J-j-i f-1

ff.r.ll Ш/

I -Н

Ч Mu u л

.Да L...

10;

Jh-t