Устройство для упорядочения п чисел

 

Цель изобретения - расширение области применения за счет формирования упорядоченного массива чисел, меньших наперед заданного. Сущность: в устройство введены регистр заданного числа, дополнительный дешифратор, первая группа из ( -2) элементов ИЛИ, вторая группа из элементов ( -1) элементов И, дополнительный шифратор, регистр размера массива и триггер режима.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (19) (И) (51)5 G 06 F 7 06

3; иА j 1Ц .у

2. "- СЕ-., t y éÑ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н А ВТОРСНОМУ СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (61} 1203509 (21) 3919534/24-24 (22) 27.06,85 (46) 15.0 1,90. Бюл, № 2 (72) В,Г,Попов, В.P ..Насибуллин и М.Н.Фатыхов, (53) 681„325 (088.8) (56) Авторское свидетельство СССР № 1203509, кл. С 06 F 7/06, 1,984. (54)(57) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ и ЧИСЕЛ по авт. св. ¹ 1203509, о т л и ч а ю щ е е с я тем, что, с целью расширения области применения за счет формирования упорядоченного массива чисел, меньших наперед заданного, в него введены регистр заданного числа, дополнительный дешифратор, первая группа из (m — 2) элементов ИЛИ, вторая группа из и элементов ИЛИ, группа из (n — 1) элементов И, дополнительный шифратор, регистр размера массива и триггер режима, вход установки в единичное состояние которого соединен с входом задания режима упорядочивания ограниченного массива устройства, а вход установки в нулевое состояние с входом задания режима упорядочения всего массива устройства и входом установки в ноль регистра заданного числа, вход управления записью которого подключен к прямому выходу триггера режима, а выходы разрядов соединены с входами дополнительного дешифратора, первый выход которого соединен с первыми входами элементов ИЛИ первой группы, и инверсным входом первого элемента И первого

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

ИЛИ второй группы, р-й выход дополнительного дешифратора (р = 3, 4..., m — 1) соединен с р-ым входом (р-1)ro элемента ИЛИ первой группы, вы-.ход q-го элемента ИЛИ первой группы, где q = 1,2,..., (m — 2) соединен с дополнительным инверсным входом (q + 1)-го элемента И первого узла преобразования кодов и дополнительными инверсными входами (q + 1)-го а ф

q-го, (q — 1)-го,..., (m — 3)-ro ,дополнительных элементов И соответственно 2-го, З-ro, (m — 1)-ro узлов преобразования кодов, выходы

С:

i-го выходного регистра (i=1,2...n) подключены к входам i-го элемента

ИЛИ второй группы, выход $ --ro эле мента ИЛИ второй группы ((=1,2,..., п-1) соединен с прямым входом р-го элемента И группы, -й инверсный вход

$ -го элемента И группы ($ = 1,2..., n — р) подключен к выходу (n- g +1)го элемента ИЛИ второй группы, выход $ -го элемента И группы соединен с -м входом дополнительного шифратора, и-й вход которого подключен к выходу и-го элемента И первой группы, а выходы дополнительного шифратора соединены с соответствующими входами регистра размера массива, Я выходы которого являются выходами размера массива устройства.

1536372

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

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

Устройство содержит информационные входы 1, входные регистры 2, дешифраторы 3, элементы ИЛИ 4, узлы

5 преобразования кодов, выполненные на элементах И 6, НЕ 7„ И 8, шифраторы.9, выходные регистры 10, выходы 11, триггер 12 режима, регистр заданного числа 13, дополнительный дешифратор 14, группу элементов ИЛИ 15, группу элементов ИЛИ

16, группу элементов И 17, дополнительный шифратор 18, регистр размера массива 19, выходы размера массива

20 устройства, входы 21 заданного числа устройства, входы 22 и 23 задания режима.

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

Упорядочивание исходного массива устройством может выполняться в двух режимах: упорядочивание всего исходного массива; упорядочивание чисел, меньших наперед заданного.

Выбор режима работы обеспечивается триггером режима 12, управляемого по входам 22 и 23. Установка первого режима производится по сигналу с входа 23, переключающему триггер 12 и регистр !3 заданного числа в нулевое состояние.

Для формирования упорядоченного массива во втором режиме в регистр

13 заданного числа поступает граничное значение массива, а по входу 22 триггер режима устанавливается в состояние "1", В обоих режимах упорядочение исходного массива выполняется одинаково.

Пусть необходимо получить упорядоченьгый массив из 4-х чисел, Исходное состояние устройства характеризуется тем, что выходные регистры 10 и регистр 19 установлены в состояние "0", во входные регистры

2 принят по входам 1 массив исходных чисел, и по входу 23 триггер режима и регистр заданного числа установлены в состояние "0", При этом выходные с игк алы дешифра тора 1 4 и с о о тв е тс твенно элементов ИЛИ 15 принимают нулевые значения, аткрь|ваяпо инверсным входам соответствующие элементы

И во всех узлах 5 преобразования кодов.

Пусть в регистры 1 принят массив исходных чисел: а, = 5, а аэ — 4, а5- 2, В соответствии с табл,1 единичные сигналы появляются на пятом выходе дешифратора 3, первом — дешифратора,3, на четвертом вЂ,цешифратора 39 и на втором — дешифратора 3+.

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

Посредством элементов ИЛИ 4 проводится объединение одноименных выходов дешифраторов. Как следует из табл,l позиционный код ка выходах элементов ИЛИ 4 имеет вид 11011. В соответствии с этим кодом в выходных регистрах 10 необходимо разметить числа в следующем порядке возрастания значения Ь = 1, Ь = 2, Ь = 4, b < = 5. Это обеспечивается соответствующими шифраторами 9, на входы которых необходимо подать следующие позиционные коды:

10000 — на входы шифратора 9

01000 — на входы шифратора 9

00010 — на входы шифратора 9

00001 — на входы шифратора 9

Преобразование исходного позиционного кода, полученного элементами ИЛИ 4, производится соответствующими узлами 5 преобразования кодов.

В узле 5„ на его входы подается позиционный код 11011. При этом единичный сигнал на его входе через элемент НЕ 7 закрывает все элементы

И 8, поэтому на выходе узла 5 формируется код 10000.

Формирование входного кода для второго узла 5 должно выполняться с учетом работы предыдущего узла 5„, т.е. необходимо при анализе исключить выделенное значение числа. Эту функцию выполняют элементы И 6, на сг инверсные входы которых поступают выходные сигналы узла 5», а на прямые сигналы с выходов элементов

ИЛИ 4, т.е.

153637

01111

40 выходы узла 5, обратный код выходы элементов

ИЛИ 4 11011 выходы элементов И 6 01011

В узле 5 из выходных сигналов элементов И 01011 за счет блокиров6 ки элементов И 8 нулевым сигналом с выхода элемента НЕ 7< формируется выходной код 01000, поступающий на шифратор 9

Построение узлов преобразования кодов 5 ...,,5 „. выполнено с учетом мини изации оборудования, что пояс- 15 няется табл .2, когда массив исходных чисел размещается в входных регистрах, причем значения чисел лежат в пределах 1-5 и в этом диапазоне могут принимать одинаковые значе- 20 ния. Из табл.2 видно, что при формировании позиционного кода для очередного узла преобразования, например, для узла 5< нет необходимости в формировании первой позиции кода, для узла 5 — первых двух и так далее, так как единичные сигналы этих позиций уже использованы для форми — . рования знпчений упорядоченных чисел .

Такое положение справедливо до формирования входного кода для узла Е „„ .

При этом число входов шифраторов

9 равно m и при m >n входные сигналы для 1-ro шифратора, где 1 =. 2, 3, и, подаваемые на входы" l, 2..., (1 — 1), равны нулю. Поэтому, хотя

35 эти поразрядные узлы преобразования кодов выполняют одинаковые функции для любого из i-го регистров, когда

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

Формирование этих управляющих сигналов для приведенных выше условий отражено в табл.3.

Пусть для приведенного примера необходимо сформировать упорядоченный массив чисел, меньших числа, равного 4.

Устройство работает следукж1им образом.

Двоичный код 100 по входам 21 принимается в регистр 13 после установки триггера режима 12 по входу

22 в состояние "1", При этом на четвертом выходе дешифратора 14 формируется единичный сигнал . В соответствии с табл ° 3 с помощью дешифратора 14 и элементов ИЛИ 15 формируется следующий позиционный код управляющих сигналов 0011. Нулевыми сигналами с второго выхода дешифратора 14 открыты по инверсным входам элемент И 8 в первом узле преобразования кодов 5 и элемент И 6» во втором узле 5, Нулевым сигналом с выхода элемента ИЛИ 15 открыты в первом узле 5 — элемент И 8, во втором — элемент И 6, в третьем— элемент И 6 . Единичными сигналами с выходов элементов ИЛИ 15, ИЛИ 15з закрыты по инверсным входам остальные элементы И 8 в первом узле 5 и элементы И 6 в остальных узлах 5.

Выбор и расстановка чисел выполняется аналогично рассмотренному выше. При этом выходной массив в регистрах 10 имеет вид Ь» = 1, Ь 2, Ь =0, b,==-о.

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

21 устройства и управляющего сигнала на входе 22, которым устанавливается в "1" триггер режима. По единичному сигналу с выхода триггера, поступающему на вход синхронизации регистра

Ф заданного числа, двоичный код заданного числа принимается в этот регистр. При этом с помощью дешифратора 14 и элементов ИЛИ 15 формируются управляющие сигналы для узлов преоб45

В дальнейшем с помощью элементов

ИЛИ 16 формируется следующий код

1100, Единичным сигналом с выхода элемента ИЛИ 16 закрыт по соответствующему инверсному входу элемент И 17< .

При этом на входах шифратора 18 устанавливается позиционный код 0100, по которому. на выхрдах 20 устройст-. ва формируется двоична код числа 2, означающий, что упорядоченный массив чисел, меньших заданного, размещен в первых двух выходных регистрах 10.

1536372 ли ца l

Таб выхода дешифратора 3,...,-3

Номер

Код числа (Г а< = 101 а = 001 и а = 100

9 а = 010 ф

О 1

О О

1 0

О О

Таблица2 е

Выходные сигналы

Выходные сигналы

Входные

Выходные сигналы элемента

ИЛИ 4

Номер и/и

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

9„ сигналы шифратора

9а элемен та

И 6 узла

5> элемента

И б узла

5 ig

1 10000

2 01000

3 )1000

4 00100

5 10100

6 01100

7 11100

8 00010

9 10010

10 01010

11 1}010

12 00110

13 10110

14 01110

15 11110

16 0000)

17 10001

18 01001

19 11001

20 00101

21 10101

22 01101

23 11101

24 00011

25 10011

26 01011

27 11011

28 00111

29 10111

30 - 01111

1000Î

00 KIO

00001

)00ÎO

0)000

0О000

00001

00001

01001

00001

° OG101

OG1O1

01101

00001

00011

GOO)1

01011

00011

00111

00111

000)0

00001

00001

00O0l

00001

00100

00001

00001

00001

00101

OOOO}

00001

0001 1

00001

00011

00011

1536372

Т а б л и д а

Сигналы блокировки передачи чисел в выходные регистры 10 для заданных кодов

Двоичные коды заданного числа

4 5

Составитель Е.Иванова

Редактор М. Н едолуженко Техред M. Дидык Коррек тор Т. Палий

Заказ 109 Тираж 551 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

Производственно-издательский комбинат "Патент", г.ужгород, ул. Гагарина, 101

011

101

0

1

0

1