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

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

K АЬТОРСКОМУ СЬИДЬТЬЛЬСТЬУ

Сова Советсюа

Социалистических

Республик (11) 610107

1 f ! (й) Дополнительное к авт. саид-ву (22) ЗаЯвлено10.08.75 (21) 2112564/18-24 с присоединением заявки № (23) Приоритет (43). Опублнковано05.06 78.Бюллетень %21

2 (6!) М. Кл.

Ст 06 P 7/06

Гкфврстекккмк ккмкткт

Савета Мкккстров СССР кк дклаи кзобретеккй к бткрыткк (68) УДК 681.325. ,066 (088,8 ) (46) Дата опубликовании описания а, еs, 1g

В. Ф. Власов и В. Г. Гребенников (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ

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

Известно устройство для сортировки двоичных чисел. содержащее N приемных сдвиговых регистров, выходы которых соединены со входами логической цепи управления вентилями сброса, выходы которой через переключатели режима работы соединены с вентилями сброса (1f.

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

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

Недостатком этого устройства является низкое быстродействие.

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

На чертеже изображена структурная схема устройства.

Устройство содержит сдвигающие регистры .

1 анализируемых чисел, узел 2 анализа количества единиц, элементы 3 преобразования, узел 4 сравнения, регистр 5 результата, входные шины 6, 7. . Устройство работает следующим образом.

Сдвигающие регистры с помощью сдвиговых импульсов, подаваемых на входную шину 6 устройства, заполняют анализируемыми числами, начиная со старшего разряда. На входную шину 7 устройства подают сигнал, который переводит все элементы 3 преобразования в ре6I0I07 жим пропускания выходных сигналов сдвигающих регистров на входы узла 2 анализа количества единиц. На вход 8 подают константу сравнения А = N + 1- — R, где N — количест- во анализируемых чисел, R — ранг выбираемого числа. 5

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

N чисел с помощью элементов 3 преобразования. В первом такте на входы узла 2 анализа количества единиц через элементы 3 преобразования поступают значения стари их разрядов N чисел. Узел 2 анализа количества единиц подсчитывает количество единиц, содержащихся в старших разрядах N чисел, и вы- 15 дает результат подсчета на узел 4 сравнения для сравнения с константой сравнения А, Если выходной результат узла анализа ко-. личества единиц больше или равен константе сравнения, то на выходе узла 4 сравнения образуется единица, если меньше — то нуль.

Выходное значение узла 4 сравнения записывают в регистр 5 результата в качестве старшего разряда выделяемого числа, а также подают на управляющие входы элементов преобразования 3.

Каждый элемент преобразования . 3 запирает выходной сигнал соответствующего сдвигающего регистра. 1 и выдает на соответствующий вход узла 2 анализа количества единиц значение «О» в течение всех последующих тактов работы устройства, если на выходе сдвигающего регистра 1-«0» и на выходе узла сравнения.4 — «I »; каждый элемент 3 преоб-. разования запрещает выходной сигнал соответствующего сдвигающего регистра l и выдает на соответствующий вход узла анализа количества единиц 2 значение «1» в течение всех последующих тактов работы устройства, если на выходе сдвигающего регистра 1

«!» и на выходе узла сравнения 4-«0»; во всех остальных случаях элемент 3 преобразования пропускает выходной сигнал сдвигаю- 4в щего регистра l на вход узла 2 анализа количества единиц, Во втором такте на входную шину 6 подают импульс сдвига, с помощью которого информация в сдвигающих регистрах 1 и регистре 5. результата сдвигается на один разряд, .и на входы элементов 3 преобразования пос.. упают разряды с номером на единицу меньше старшего. Выходные сигналы сдвигающих регистров 1 пройдут на входы узла 2 анализа количества единиц только через те элементы 3 преобразования, которые не заперлись в первом такте, запертые элементы 3 преобразования будут выдавать на соответствующие входы v3ла 2 анализа количества единиц постоянные значения «О» или «!» до конца сортировки, Выходное значение узла анализа количества 2 единиц подают на узел 4 сравнения для сравнения с константой сравнения А. Выходное значение узла 4 сравнения записывают в регистр 5 результата в качестве цифры выделяемого числа с номером разряда на единицу меньше старшего, а также подают на управляющие входы. элементов 3 преобразования.

Каждый элемент 3 преобразования, для которого выполнялось условие запирания, запирает выходы сдвигающих регистров I в первом такте, и во всех последующих тактах выдает на узел 2 анализа количества единиц константы «О» или «1». Элементы 3 преобразования, для которых условие запирания не выполнялось, пропускают выходные сигналы сдвигающий регистров. i на соответствующие входы узла 2 анализа количества единиц.

В третьем и последующих тактах устройство работает аналогично.

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

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

Источники информации, принятые во внимание при экспертизе:

I. Авторское свидетельство СССР № 285347, кл. 0 06 F 7/00, 20.03.64.

2. Заявка № 21!2553/24 от!0.03.75, по которой принято решение о выдаче агторского свидетельства.

Редактор Г Марховская

Заказ 3011 37

Составитель В. Белкин

Техред О. Луговая Корректор Н. Тупипв

Тираж 826 Подписное

ElHHHflH Государственного комитета Совета Министров СССР по делам изобретен ий и открытий

113035, Москва, Ж-35; Раушская наб. д. 4/5

Филиал ППП «Патента, г. Ужгород, ул. Проектная. 4