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

1

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

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

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

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

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

Целью изобретения является повышение бы.стродействия.

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

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

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

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

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

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

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

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

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

будут выдавать на соответствующие входы узла 2 анализа количества единиц постоянные значения «О или «I до конца сортировки. Выходное значение узла анализа количества 2 единиц подают на узел 4 сравнения для сравнения с константой сравнения А. Выходное значение узла 4 сравнения записывают в регистр 5 результата в качестве цифры выделяемого числа с номером разряда на единицу меньше старшего, а также подают на

управляющие входы, элементов 3 преобразования.

Каждый элемент 3 преобразования, для которого выполнялось условие запирания, запирает выходы сдвигающих регистров i в первом такте, и во всех последующих тактах выдает

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

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

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

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

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

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

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

0 2. Заявка № 2112553/24 от 10.03.75, по которой Принято решение о выдаче авторского свидетельства.

«