Устройство для выбора упорядоченной последовательности данных

 

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

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

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

РЕСПУБЛИН

„.Я0„„1218 1

C51) g G 06 F 7/06

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

H ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTMA (21) 3792520/24-24 (22) 18.09.84 (46) 15.03.86. Бюл. Р 10 (72) А.Х.Ганитулин и В.Г.Попов (53) 681.325(088.8) (56) Авторское свидетельство СССР

Р 903864, кл. G 06 F 7/06, 1979.

Авторское свидетельство СССР

В 1059565, кл. G 06 F 7/06, 1982. (54) УСТРОЙСТВО ДЛЯ ВЫБОРА УПОРЯДОЧЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ДАННЫХ (57) Изобретение относится к автоматике и вычислительной технике.

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

И, ИЛИ, группу из и элементов И и генератор импульсов, информационные входы и выходы, шины Начальное гашение", "Начало операции" и "Размер массива". Новым является введение шифратора и и узлов сравнения, содержащих две группы элементов И, группу элементов ИЛИ и элемент И, и их связей в устройстве. На вход устройства может быть подан массив с( различных по значению чисел, причем и. С помощью устройства чисел сортируются в порядке возрастания, причем (п. Задача сводится к определению минимального числа, записи его в первый регистр результата а и гашению того вхоцного регистра, в котором оно находится, для исключения уже выбранного числа в очередном цикле анализа. Затем этот про- С цесс повторяется, пока не выполнится Р циклов. По завершении р циклов в регистрах результата будет нахо" диться упорядоченная последовательность чисел, составляющая вырезанный массив в Р чисел из исходного массива в Ы чисел, причем с(са и. 1 ил.

Двоичные коды чисел а,, = 101

0 0 0

0 0 1

1 0 0

0 0 0

0 1

0 0

0 0

1 0

0 0

0 0

0 0 а = 0(1 аз = 001 а = 100

0 . 0

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

0 0

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

0 0

1 121

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

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

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

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

НЕ 4, группу элементов И 5, шифратор

6, группы элементов И 7, регистры

8 результата, выходы 9 регистров 8, коммутатор 10, информационные выходы 11 устройства, блок управления

12, выходы 13 блока управления 12, группу элементов HE 14, узлы сравнения 15, в которые входят группы элементов И 16, группа элементов

ИЛИ 17 и элемент И 18, элемент

1ШИ 19, группу входных элементов

И 20, группу входных элементов

ИЛИ 21, информационные входы 22 устройства, вход "Начало операции"

23, вход "Начальное гашение" 24, выход конца сортировки 25, шину

"Размер массива" 26.

Блок управления 12 содержит элемент ИЛИ 27, триггер управления 28, элемент И 29, генератор импульсов

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

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

На вход устройства может быть подан массив с различных по значе8381 2 нию чисел, причем (g (и. (: помощью устройства необходимо расставить 3 чисел в порядке их возрастания, причем P (n. Задача сводится к определению минимального числа, записи его в первый регистр результата и гашению того входного регистра, в .котором оно находится, для исключения уже выбранного числа в очеред10 ном цикле анализа. Затем процесс повторяется, пока не выполнится р циклов. По завершении р циклов в регистрах результата будет находиться упорядоченная последовательность чисел, составляющая вырезанный массив в р чисел из исходного массива в Ы чисел, причем сК (и.

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

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

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

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

Определение минимального числа в первом цикле работы устро:-;ства

40 поясняется табл. 1.

Таблица 1

Номера выходов дешифраторов

2, ..., 2„

1 0 1 1 1

1 0 0 0 0

3 1

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

В дальнейшем это число через элементы И 7„ передается в регистр 8! и одновременно в узлах сравнения

15 производится формирование единичного сигнала для гашения входного третьего регистра, так h = а .

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

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

Та блица 2 х, 0

0

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

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

Х„Х ЧХ„Х .

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

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

О

55 ное значение сигнала формируется в третьем узле сравнения 15, и в очередном цикле производится анализ следующих значений чисел: а„ вЂ” 101; а = 011; аз = 000; a> = 100.

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

Исходное состояние устройства характеризуется тем, что сигналом, поступающим на вход "Начальное гашение" 24, устанавливаются в нулевые состояния регистры 8 результата, через элементы ИЛИ 21 — входные регистры 1 и через элемент ИЛИ 27— триггер управления 28 в блоке управления 12. После этого по входам 22 во входные регистры принимается исходный массив чисел, а по шинам

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

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

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

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

Одновременно по единичному сигналу с выхода элемента ИЛИ 3, на и-й вход которого поступает единичный сигнал с первого выхода дешифратора 2„, через элемент НЕ 4„ зак218381 Я дов регистра 1 и шифратора 6. Посредством элемента И 18 формируется единичный сигнал, когда на его входах действуют единичные сигналы одновременно со,.всех элементов

ИЛИ 17, что означает полное совпадение двоичных кодов шифратора 6 и регистра 1.

Для приведенного примера единич1218381

20 рываются все элементы И 5, При этом возбужденным будет только первый вход шифратора 6. Двоичный код числа с выхода шифратора 6 подается через открытые элементы И 7„ в регистр

8„ результата. Одновременно производится сравнение кодов шифратора 6 и всех регистров 1 в узлах сравнения

15. При этом единичное значение сигнала формируется элементом И 18 узла 15»„ которым регистр 1,„ через открытый элемент И 20», сигналом элемента ИЛИ 19 устанавливается в нулевое состояние, чем исключается выбр нное уже число из анализа в

o:;àðåä»»oì цикле.

Очередной цикл на «инается по импу.»гьсу от генератора 30, который переводит счетчик 31 в очередное состояние, по которому возбуждается вьг»год 13 блока управления 12.

Габота по анализу, передаче числа в регистр 8 результата и гашению

»зходного регистра, где находится 25 очередное наименьшее число, производится аналогично описанной.

В последнем и-и цикле большее число окажется в регистре 8„ результата. По очередному импульсу от

30 гсператора 30 в блоке управления . 1? триггер 28 устанавливается в нупевае состояние сигналом переполне»;ил счетчика 31, поступающим на инверсный вход триггера через элемент

35, 0111 27. По единичному сигналу с инверсного выхода триггера 28 в ком:»угагоре 10 производится передача содсржимого регистров 8 в шины 11 устройства, представляющего собой возрастающую последовательность из и исходн»ях чисел.

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

При необходимости получения убыва»ш»«ей последовательности из чисел

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

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

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

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

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

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

i-го входного регистра, информацион— ные входы которого являются информационными входами устройства, где

1, 2, ..., n, п — количество сортируемых чисел, соединены с соответствующими входами г-го дешифратора, вход "Начальное гашение" устройства соединен с входами установки в "0»» всех регистров результата, первыми входами входных элементов ИЛИ группы и первым входом элемента ИЛИ,блока управления, в котором выход элемента ИЛИ подключен к входу установки в "0" триггера управления, вход установки в "1" которого соединен с входом "Начало операции" устройства, а прямой выход соединен с первыми входами элементов И группы и элемента И, второй вход которого подключен к выходу генератора импульсов, а выход соединен со счетным входом счетчика, выход-.переполнения которого подключен к второму входу элемента И, а выходы разрядов соединены с соответствующими входами дешифратора, выходы которого подключены к вторым входам элементов И группы, выход

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

1218381 входам входных элементов И группы, выходы которых соединены с вторыми входами соответствующих входных .элементов ИЛИ группы, выходы которых подключены к входам установки в "О" соответствующих входных регистров, шина "Размер массива" устройства подключена к информационным входам счетчика блока управления и входам регистра коммутатора, в котором выходы разрядов регистра соединены с соответствующими входами дешифратора, i — и выход которого подключен к первым входам первой, второй, i-й групп элементов И, вторые входы элементов И i-й группы подключены к выходам разрядов i-го регистра результата, а выходы являются информационными выходами устройства, инверсный выход триггера управления блока управления является выходом конца сортировки устройства и подключен к управляющим входам элементов И всех групп коммутатора, выход Т-го элемента НЕ первой группы подключен к 7-му входу (Р + 1), ..., (m — 1)-ro элемента. И группы, где t = 1, 2, (m — 1), m-разрядность сортируемых чисел, о т л и ч а ю щ е е с я тем, что, с целью сокращения аппаратурных затрат, в него введены шифратор и и узлов сравнения, каждый из которых содержит две группы элементов И . гвуппч элементов ИЛИ и эле1 мент и, причем j ûé выход i-ro дешифратора, где j = 1, 2. ..,, m, соединен с i-м входом j-го элемента

ИЛИ группы, выход 1. — го элемента ИЛИ группы соединен с входом Г-ro элемента НЕ первой группы, выход первого элемента ИЛИ группы соединен с первым входом шифратора, а выход (7 +

1p + 1) элемента ИЛИ группы — с (f +

+ 1)-м входом 0-ro элемента И группы, выход которого соединен с (f +

+ 1)-м входом шифратора, j-й выход которого подключен к информационным входам j õ элементов И всех групп, входу j-го элемента НЕ второй группы и к первым входам j-x элементов

И первых групп всех узлов сравнения, вторые входы j-x элементов И первой

2п группы f-ro узла сравнения соединены с прямыми выходами j-x разрядов

i-ro входного регистра, инверсные выходы которых подключены к первым входам соответствующих элементов И

2S второй группы i-ro узла сравнения, вторые входы j-x элементов И вторых групп всех узлов сравнения подключены к выходам j-го элемента НЕ второй группы, в i-м узле сравнения выходы

j-x элементов И первой и второй групп подключены к входам j-го элемента ИЛИ группы, выход которого подключен к j-му входу элемента И, выход которого подключен к второму входу -го входногоэлемеита Игруппы.

1218381

ВИИИПИ Заказ 1132/56 Тираж 673 Подписное

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