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

1

Изобретение относится к вычислительной технике и может использоваться при построении систем сбора и обработки информации.

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

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

Предлагаемое устройство (фиг, П содержит тактовый вход 1, установочный вход 2, вход 3 задания режима, информационные входы 4-1-4-т, счетчик 5 результата, схемы 6-1-6-т сравнения , блок 7 обнаружения равных чисел, счетчик 8 адреса, блок 9 памяти, первый, второй и третий элементы И 10,11 и 12, элемент НЕ 13, элемент ИЛИ 14, элемент 15 задержки, выходы 16-r-16-N,

Блок 7 обнаружения равных чисел (фиг, 2) содержит тактовый вход 17, информационные входы 18-1-18-т, формирователи 19-1-19-т импульсов, триггеры 20-1-20-т, группы элементов И 21-1-21-т, 22-1-22-(т-1), элемент ИЛИ 23, элемент ШШ-НЕ 24, второй 25 и первый 26 выходы связи.

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

На тактовый вход 1 подается последовательность тактовых импульсов, а на вход 3 задания режима нулевой потенциал, обеспечивающий перевод блока 9 памяти в режим записи вход- ньгх кодов, закрьгоающий второй элемент И П, и через элемент НЕ 13, открьтающий третий элемент И 12. На информационные входы 4-1-4-т устройства поступают числа, которые необходимо упорядочить, С окончанием импульса на установочном входе 2 устройства оно готово к работе, при этом на выходе 26 блока 7 обнаружения разных чисел устанавливается единичный потенциал, так как все ег триггеры 20-1-20-т находятся в нуле Iвом состоянии.

Выходной единичный потенциал с выхода 26 блока 7 обнаружения равных чисел разрешает прохождение тактовых импульсов с тактового входа 1 устройства через первый элемент И 10 на тактовый иход счетчика 5 резуль

20

46089Z

тата. С приходом каждого тактового

импульса на его вход содержимое счетчика 5 результата увеличивается на единицу, а состояние других элемен- тон не. изменяется до тех пор, пока не установится число на выходе счетчика 5 результата, равное меньшему из чисел, -поступивших на информационные входы устройства. С наступлением 10 этого момента на выходе соответствующей схемы 6 сравнения устанавливается единичный потенциал, обеспечивающий через формирователь 19 импульсов (фиГо 2) перевод соответст15 вующего триггера 20 в единичное состояние. При этом на выходе элемента ИЛИ-НЕ 24 устанавливается нулевой потенциал, запрещающий прохож- дение импульсов через первый элемент И 10, а тактовый импульс в блоке 7 обнаружения равных чисел обеспечивает выделение одного импульса на выходе 25 блока 7 обнаружения равных чисел через открытый соответ25 ствутощим триггером 20 элемент И 21 и элемент ИЛИ 23 и одновременно сброс триггера 20 в нулевое состояние и установку единичного потенциала на выходе элемента ИЛИ-НЕ 24.

Импульс с выхода 25 блока 7 обнаружения равных чисел, пройдя через открытый третий элемент И 12 и эле- мент ИЛИ 14 на вход счетчика В адреса,, устанавливает на его выходах первое значение адреса Этот же им35 пульс, пройдя через элемент 15 задержки, осуществляет за-пись минимального числа с выхода счетчика 5 результата по адресу, установленному на выходах счетчика 8 адреса Время задержки элемента 15 задержки должно выбираться из условия L / Сп +

30

л -Счв

П

где t

ип

45

SO

- время задержки элемента И 12;

ИAИ14 задержки элемента ИЛИ 14;

- максимальное время задержки счетчика В адреса, Далее устройство работает аналогично, осуществляя запись по следук - щим адресам все нарастающих чт сел вплоть до максимального числа во входном мае сив е Таким образом, на выходах счетчи- 55 ка 5 результата могут быть выделены в нгфастающем порядке все числа из входной последовательности. Наличие того или иного числа подтверждает

импульс иа выходе 25 блока 7 обнаружения равных чисел

Эти числа записываются в блок 9 памяти по нарастающим адресам, начиная с первого адреса, и в случае необходимости могут быть многократн считаны. Для этого необходимо подат единичный сигнал на вход 3 устройства, который переведет блок 9 памяти в режим Считывание, и установить счетчик 8 адреса в нулевое состояние подачей импульса на установочный вход 2 устройства. С подачей каждого тактового импульса на вход 1 устройства счетчик 8 адреса устанавливает последующее значение адреса на адресных входах блока 9 пмяти, на выходах которого проявляют ся числа входного массива в нарастающем порядке.

Вместо суммирукяцего счетчика 8 адреса может быть применен реверсивный счетчик, что позволит осуществлять считывание на выходах устройства чисел либо в нарастающемj ли€о в убьшающем порядке

В случае, если входной массив содержит R равных чисел, устройство работает следующим образом С установкой на выходе счетчика 5 результата числа, равного R одинаковым числам, на выходах R схем 6 сравнения устанавливается единичный потенциал, который обеспечивает установку в единичное состояние R триггеров 20 блока 7 обнаружения равных чисел. Элемент ИЛИ-НЕ 24 запрещает прохождение тактовых импульсов через первый элемент И 10 на вход счетчика 5 результата, на выходах кото- рого установлено значение равных чисел. С приходом каждого из последующих тактовых импульсов-на вход блока 7 обнаружения равных чисел один из его триггеров 20 устанавливается в нулевое состояние, при этом на выходе 25 блока 7 выделяется один импульс, обеспечивающий установку нового значения адреса и запись кода с выхода счетчика 5 результата по каждому значению адреса С установкой каждого из предьздущих триггеров в нулевое состояние единичным потенциалом с его инверсного выхода разрешается прохождение тактовых импульсов через элемент И 2i на после- дугэдие элементы И 21 и 22, пока все равные числа не будут переписаны в блок 9 памяти по соответствующим ад460894

ре сам-, Элемент lillH-HE 24 поддерживает нулевой потенциал на входе первого элемента И 10 до тех пор, пока все триггеры 20 не будут установлены в нулевое состояние.

Таким образом, предлагаемое устройство может осуществлять запоминание упорядоченного массива либо в нарастающем, либо в убывающем порядке Q и запоминание равных чисел в массиве.

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

1 .-Устройство для упорядочивания чисел, содержащее m схем сравнения, где m - число упорядочиваемых чисел, первые группы входов которых соединены с входами упорядочиваемых чисел устройства, а вторые группы входов

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

тем, что, с целью расширения области применения за счет обеспечения фиксации равных чисел, запоминания упорядоченного массива и повьппения быстродействия устройства, в него введены блок памяти, счетчик адреса, элемент НЕ, элемент задержки и блок обнаружения равных чисел, i-й информационный вход которого (, 2,,..т) соединен с выходом i-й схемы сравнения, а тактовый вход - с тактовым

входом устройства и первыми входами первого и второго элементов И, выход отсутствия равных чисел блока обнаружения равных чисел соединен с вторым входом первого элемента И, а выход

наличия числа -с первым входом тре- элемента И и через элемент задержки - с входом записи блока памя-, ти, информационные входы которого соединены с выходами разрядов счетчика результата, счетный вход которого соединен с выходом первого эле- мента И, а адресный вход блока памяти соединен с выходом счетчика адреса, счетный вход которого соединен с выходом элемента ИЛИ, входы которого соединены с выходами второго и третьего элементов И, вход считывания блока памяти соединен с входом зада- ния режима устройства, с вторым вхоом второго элемента И и через элемент E -с вторым входом третьего элемента И, вход начальной установки счетчика | адреса соединен с установочттым входом устройства, выходы блока памяти являются выходами устройства.

2. Устройство по п. 1, о т л и - чающееся тем, что блок обнаружения равных чисел содержит m формирователей импульсов, m триггеров, m элементов И первой группы и (m-l) элементов И второй группы, элемент ИЛИ и элемент ШШ-НЕ, 1-й информационный вход.обнаружения равных чисел соединен через i-й формирователь ) импульсов с единичным установочным входом 1-го триггера, прямой выход которого соединен с первым входом i-ro элемента И первой группы, выход которого соединен с входом установки в О i-ro триггера и подключен к i-му входу элемента НЛИ, выход которого является вы- ходом наличия числа блока обнаружения равных чисел, прямые выходы всех

с триггеров соединены с входами элемента ИЛИ-НЕ, выход которого является выходом отсутствия чисел блока обнаружения равных чисел, инверсный , выход J-ro триггера (j , 2,...m-l)

10 соединен с первым входом j-ro элемента И второй группы, выход которого соединен с вторым входом (j+l)-ro элемента И первой группы, вторые входы i-x элементов И первой и второй

15 групп объединены, вторые входы первых элементов И первой и второй груп подключены к тактовому входу блока обнаружения равных чисел.

/б-К

ио

/8-7

19-1

ZO-1

18-г

19-2

2Q-Z

IB-m

19-m- S

анв

Составитель A. Александров Редактор H. Тупица Техред Э.Чижмар Корректор И.Муска

- --,- - - -- - -- - --.-.- -и.---.- - -«--.---- --- - - - -- - -- --

Заказ 4000/41 Тираж 671Подписное

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб,, д, 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

2;-/

i

22-1

2У-2

Z3

25

22-2-1

f-J

L.I

26

Фмг.г

Изобретение относится к вычислительной технике и может исполь- , эоваться при построении с:истем сбора и обработки информации. изобретения является расширение области применения за счет обеспечения возможности фиксации равных чисел и запоминания упорядоченного массива, а также повышения быстродействия. Устройство содержит счетчик адреса, счетчик результата, m схем сравнения, где m - число упорядочиваемых чисел, блок обнаружения равных чисел, блок памяти, элементы И, ИЛИ, НЕ. Блок обнаружения равных чисел содержит формирователи импульсов, триггеры, элементы И, ИЛИ, ШШ-НЕ. Предлагае- ;мое устройство позволяет осуществить .запоминание упорядоченного массива чисел, вывод упорядоченного массива чисел в нарастающем либо в у(Я гаающем порядке и запоминание равных чисел в массиве. 1 з.п. ф-лы,-,2 ил. (Л