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

1

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

Цель изобретения - сокращение аппаратурных затрат.

На чертеже приведена функциональная схема устройства..

Устройство содержит входные регистры 1, дешифраторы 2, группу элементов ШИ 3, группу элементов НЕ 4, группу элементов И 5, шифрато 6, группы элементов И 7, регистры 8 результата, выходы 9 регистров 8, коммутатор 10, информационные выходы 11 устройства, блок управления 12, выходы 13 блока управления 12, группу элементов НЕ 14, узлы сравнения 15, в которые входят группы элементов И 16, группа элементов ИЛИ 17 и элемент И 18, элемент IfflH 19, группу входных элементов И 20, группу входных элементов ИЛИ 21, информационные входы 22 устройства, вход Начало операции 23, вход Начальное гашение 24, выход конца сортировки 25, шину Размер массива 26,

Блок управления 12 содержит элемент ИЛИ 27, триггер управления 28, элемент И 29, генератор импульсов 30, счетчик 31, .дешифратор 32, группу элементов И 33. Коммутатор 10 содержит регистр 34, дешифратор 35 и группу элементов И 36,

Рассм-отрим принципы построения и работу устройства.

На вход устройства может быть подан массив d различных по значеДвоичные коды чисел

Выходные сигналы элементов ИЛИ 3

Входные сигналы шифратора 6

3812

нию чисел, причем о1 п. С помощь устройства необходимо расставить р чисел в порядке их возрастания, причем J3 ё- п. Задача сводится к оп- 5 ределению минимального числа, записи его в первый регистр результата и гашению того входного регистра, в .котором оно находится, для исключения уже выбранного числа в очеред- 0 ном цикле анализа. Затем процесс повторяется, пока не.выполнится р циклов. По завершении р циклов в регистрах результата буд.ет находиться упорядоченная последовательность , 15 чисел, составляющая вьгрезанньш массив в Р чисел из исходного массива в Ы- чисел, причемЫ п.

I

Управление-формирование упорядо- .

20 ченного массива производится блоком управления на основе анализа требуемого размера массива.

Коммутатор обеспечивает вьщачу упорядоченного массива из регистров 25 результата.

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

Пусть имеется массив из четырех чисел ai 101, а,, 011, а 001, а,, 100,

Определение минимального числа в первом цикле работы устройства поясняется табл, 1.

Таблица 1

35

40

I

Номера выходов дешифраторов 21 2j,

.3

Из анализа табл. 1 видно, что номера возбуженных выходов дешифраторов 2, а также соответствующих элементов ШТИ 3 однозначно отражают значения чисел, содержащихся во входных регистрах 1. С помощью элементов НЕ 4 и элементов И 5, подключенных к выходам элементов ИЛИ 3, формируется распределительный входной код для шифратора 6. Так как возбужденным является первый вход шифратора, то на его выходах формируется двоичный код Ц 001, т.е. наименьшее число из исходного массива.

В дальнейшем это число через элементы И 7 передается в регистр Qj и одновременно в узлах сравнения 15 производится формирование единичного сигнала для гашения входного третьего регистра, так Ь-, а .

В каждом узле сравнения производится поразрядное сравнение прямых и обратных кодов выходных сигналов шифратора 6 и регистров 1.

Работа узла сравнения для одного разряда поясняется табл. 2.

Таблица 2

ТГьГГ Г Г-Ь1---Т--1- -Г Г

о00

О

1

О

1

О

О

11 1

;«««,

Примечание. Х и Xj- значения одноименных разрядов двух чисел, Y - значение сигнала сравнения, т.е. равенства разряда.

Из табл. 2 следует, что Y Xj Лл

В соответствии с табл. 2 вьтолне узел сравнения 15 для каждого входного регистра 1. Единичные значения выходного сигнала узла сравнения используются для гашения соответствующего регистра 1.

В узле сравнения 15 в первой группе элементов И 16 производится сравнение прямых кодов k разрядов регистров 1 и шифратора 6, а во второй группе элементов И 16 - обратных кодов. Для каждого из k разрядов используется элемент ИЛИ 17, объединяющий выходные сигналы элементов И 16 соответствующих разря18381 .4

дов регистра 1 и шифратора 6. Посредством элемента И 18 формируется единичный сигнал, когда на его входах действуют единичные сигналы 5 одновременно со, -всех элементов IfflM 17, что означает полное совпадение двоичных кодов шифратора 6 и регистра 1.

Для приведенного примера единич- 10 ное значение сигнала формируется в третьем узле сравнения 15, и в очередном цикле производится анализ следующих значений чисел: а 101; ai 011; аз 000; а,, 100.

15

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

образом.

Исходное состояние устройства характеризуется тем, что сигналом, поступающим на вход Начальное гаQ шение 24, устанавливаются в нулевые состояния регистры 8 результата, через элементы ИЛИ 21 - входные регистры 1 и через элемент ШlIi 27 - триггер управления 28 в блоке управ-

5 пения 12. После этого по входам 22 во входные регистры принимается ис- ходньй массив чисел, а по шинам Размер массива 26 - значение требуемого размера выходного массива

.. в регистр 34 коммутатора 10 в прямом коде и в счетчик . 31 - в дополнительном коде. По окончании приема исходных чисел сигналом, поступающим по входу Начало операции 23, триггер управления 28 блока управле ния 12 устанавливается в единичное состояние.

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

В дешифраторе 35 возбужден п-й выход, разрешающей формирование выходных сигналов на шинах 111 , ..., 11 устройства.

В дешифраторе 32 блока управления 12 возбужден первьш выход, и так как триггер 28 находится в еди ничном состоянии, элементом И 33i яа выходе 13 формируется единичный сигнал, разрешающий работу элемен-. тов И 7 .

Одновременно по единичному сигна5 лу с выхода элемента ИЛИ 3, на п-й вход которого поступает единичный сигнал с первого выхода дешифратора 2п, через элемент НЕ 4 зак0 ,,

5

рываются псе элементы И 5. При этом возбужденным будет только первый вход шифратора 6. Двоичный код числ с выхода шифратора 6 иодается через открытые элементы И 7) в регистр результата. Одновременно произ-t водится сравнение кодов шифратора 6 и всек регистров 1 в узлах сравнени 15, При этом единичное значение сигнала формируется элементом И 18 узла 15(.,, которым регистр 1, через открытьш элемент И 20 н сигналом элемента ИЛИ 19 устанавливается в нулевое состояние, чем исключается выбранное . число из анализа в очеродном цикле.

Очередной цикл начинается цо импульсу от генератора 30, к.оторый переводит счетчик 31 в очередное состояние, по которому возбугкдается выход 13г блока управления 12. Рабоч а но анализу, передаче числа в регистр 82 результата и гашению входного регистра, где находится о чередное наименьшее число, производится аналогично описанной.

В последнем п-м цикле большее число окажется в регистре 8 результата. По очеред 1ому импульсу от генератора 30 в блоке управления ,12 триггер 28 устанавливается в ну- певое состояние сигналом переполнения счетчика 31, поступающим на ин- версньй вход триггера через элемент I DIIl 27. По единичному сигналу с инверсного выхода триггера 28 в ком- яутаторе 10 производится передача содержимого регистров 8 в ншны 11 устройства, представляющего собой возрастающую последовательность из п исходных чисел.

Сигнал с инверсного выхода Триггера 28, поступающий по шине 25, например, в ЭВМ, используется в качестве сигнала, разрешающего обработку сформированной последовательности чисел-.

При необходимости получения убы- последовательности из чисел на входные лмны 22 устройства числа подаются в обратном коде.

Если необходимо получить последовательность чисел, вырезанную из п исходных чисел, по lUHHe 26 подается ДВО1Г-1НЫЙ код требуемого размера, отфеделяю1ций число циклов работы устройства. При этом работа устройства не отличается от описанной за

to

15

20

25

30

35

0

5

50

55

исключением того, что в дешифраторе 35 коммутатора 10 будет возбужден выход, номер которого соответствует размеру требуемого массива и открывающий соответствующее число элементов И 36.

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

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

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

мент и, причем j-ый выход i-ro дешифратора, где j 1, 2, ..., m, соединен с i-м входом j-ro элемента ИЛИ группы, выход f-ro элемента ИЛИ группы соединен с входом f-ro элемета НЕ первой группы, выход первого элемента ИЛИ группы соединен с первым входом шифратора, а выход ( + + 1) элемента ИЛИ группы - с (t + + 1)-м входом t-ro элемента И группы, выход которого соединен с (С + -t- 1)-м входом шифратора, j-й выход которого подключен к информационным входам J-X элементов И всех групп, входу j-ro элемента НЕ второй группы и к первым входам j-x элементов И первых групп всех узлов сравнения вторые входы j-x элементов И перво группы f-ro узла сравнения соединены с прямыми выходами j-x разрядов i-ro входного регистра, инверсные вьпходы которых подключены к первым входам соответствующих элементов И второй группы i-ro узла сравнения, вторые входы j-x элементов И вторых групп всех узлов сравнения подключе к выходам j-ro элемента НЕ второй группы, в i-M узле сравнения выходы j-x элементов И первой и второй групп подключены к входам j-ro элемента ИЛИ группы, выход которого подключен к j-му входу элемента И, выход которого подключен к второму ВХОДУ -го входногоэлемента Игруппы.

t5

I

ВИШПИ Заказ 1132/56 Тираж 673 Подписное Филиал ППП Патент, г.Ужгород, ул.Проектная, 4

Изобретение относится к автоматике и вычислительной технике. Целью изобретения является сокращение объема оборудования. Устройство содержит п входных регистров, п дешифраторов,п регистров результата, п групп элементов И, группы входных элементов И и ИЛИ, группу элементов ИЖ, элемент ИЛИ, две группы элементов НЕ, коммутатор, состоящий из п групп элементов И, дешифратора и регистра, блок управления, содержащий триггер управления, счетчик, дешифратор, элементы И, ИЛИ, группу из п элементов И и генератор импульсов, информационные входы и выходы, шины Начальное гашение, Начало операции и Размер массива. Новым является введение шифратора и п узлов сравнения, содержащих две группы элементов И, группу элементов ИЛИ и элемент И, и их связей в устройстве. На вход устройства может быть подан массив й( различных по значению чисел, причем ot п. С помощью устройства JJ чисел сортируются в порядке возрастания, причем р п. Задача сводится к определению минимального числа, записи его в первый регистр результата и гашению того входного регистра, в котором оно находится, для исключения уже выбранного числа в очередном цикле анализа. Затем этот процесс повторяется, пока не вьтолнит- ся р циклов. По завершении р циклов в регистрах результата будет находиться упорядоченная последовательность чисел, составляющая вырезанный массив в j5 чисел из исходного массива в d чисел, причем , 1 ил. Q е (Л § to 00 OS 00