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

 

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

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

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

РЕСПУБЛИН пи 4 С 06 Р 7/08

Фиг. /

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4115631/24-24 (22) 24.06.86 (46) 23.03.88. Бюл. Р 11 (72) В.П.Боюн и А.A.Ñòîëÿðîâ (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Р 1073770, кл. G 06 F 7/06, 1983.

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

Р :183956, кл. Г 06 F 7/06, 1985..ЯВ 1383336 А1 (54) УСТРОЙСТВО ДЛЯ УПОРЯДО !ЕНИЯ МАСCHBA ОСЕЛ (57) Изобретение относится к вычислительной технике и может использоваться при построении систем сбора и обработки информации. Цель изобретения — распир ение функциональных возможностей за счет упорядочения массивов чисел с учетом знака и повторе) 3833 ния равных чисел при выводе. Устройство содержит блок памяти 11, мультиппексор 10, два триггера 12, 14, реверсивный счетчик 13, группу элементов И 15-1 — )5-(N+1), формирователь импульсов 20, два элемента И )8, 19, два элемента НЕ 8, 17 и элемент ИЛИ

16, При упорядочении массива чисел осуществляется запись в блок памяти признаков наличия чисел по адресу, задаваемому значением числа. Считы36 вание информации производится счетчиком с линейным нарастанием или убыванием возможных значений числа. Блок памяти управляет выводом чисел из счетчика и разрешает дальнейшее, линейное нарастание или убывание его кода. Дополнительный дешифратор управляет режимом ввода и записи начальных условий в счетчик и два триггера памяти начальных условий.2 з.п. ф-лы, 3 ил.

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

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

)Ia фиг.1 дана функциональная схема устройства для упорядочения массива чисел; на фиг.2 — схема блок памяти; на фиг ° 3 — - схема ячейки памяти, входящей в состав блока памяти.

Устройство для упорядочения массива чисел ),фиг.)) содержит управляющий вход 1 информации, вход 2 "Сброс", вход 3 задания режима сортировки чисел при выводе упорядоченного массива, входы 4-1 — -N модуля, вход 5 знака, вход 6 записи чисел, тактовый вход 7, элемент НЕ 8, элемент И

9, мультиплексор 10, блок 11 памяти, D-триггер 12, 1!."разрядный счетчик 13, !

7-триггер 14,группу из N+1 элементов

И 15-1 — .15-Ы четвертый элемент И

15-(N+1), элемент ИЛИ 16, элемент НЕ

17, элементы HE 18 и 19, формирователь 20 импульса по переднему фронту входного сигнала, дешифратор 21 нуля, выходы 22 1 — 22-)), выход 23 знака упорядоченных чисел, синхронизирующий выход 24, управляющий выход

25.

Блок 11 памяти содержит вход 26 выбора режима, тактовый вход 27, синхронпзирующий вход 28 конца цикла ввода, вход 29 "Сброс", адресные входы 30--1 -- 30-N, адресный вход 31

2 знака числа, формирователь 32 импуль" са, элемент НЕ 33, группу элементов

И 34-1 — 34-(И+1), группу элементов

И 35-1 35-(И+1) ячейки 36-) — 36(M+

Э

+1) памяти, группу элементов И 37-137-(И+1), элемент ИЛИ 38, преобразователь 39 двоичного кода в позиционный, выход 40 блока памяти.

10 Ячейки 36-1 — 36-(И+1) памяти содержат синхронизирующий вход 41 кон:ца цикла ввода, суммирующий 42 и вычитающий 43 входы, вход 44 "Сброс", синхронизирующий вход 45, реверсив)5 ный счетчик 46, дешифратор 47 нуля, регистр 48, элемент И 49, информаци-онный выход 50.

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

20 Для ввода чисел упорядоченного массива необходимо подать на вход 2 (фиг.1) импульс, осуществляющий установку в нулевое состояние реверсивного счетчика 46 (фиг.3), установить

25 единичный потенциал на входе ), переключающий мультиплексор 10 (фиг.1) в режим передачи информации с входа

А на выход С, разрешающий открыться группе входных элементов И 34-1

30 34-(И+1) (фиг.2) для прохождения импульсов с тактового входа 27 (фиг.2) на суммирующий вход счетчика 46 и закрывающий нулевым сигналом с выхода элемента НЕ )7 прохождение такто35 .вых импульсов с входа 7 через элемент И 18 на вход N-разрядного счетчика 13, а также с выхода элемента

НЕ 33 на элементы И 37-1 — 37(M+1).

Кроме того, необходимо подать синх40 ронно с импульсами записи на входе 6 числа упорядоченного массива на вхо1383336 ды 4-1 - 4-N модули чисел, а на вход 5 -. знаки чисел.

Каждым импульсом записи на входе

6, проходящем через элемент ИЛИ 16 на вход "Запись" счетчика 13 и тактовый вход триггера 14, осуществляется запись очередного числа (модуля в счетчик и знака в триггер) °

*В связи с тем, что мультиплексор

10 открыт для прохождения импульса записи с входа А на выход С с его выхода, этот импульс поступает на тактовый вход 27 блока памяти. В это же время с выхода счетчика 13 модуль числа, а с выхода D-триггера 14 знак числа подаются на адресные входы

30-1 — 30-N и 31 блока 11 памяти.

Двоичный код модуля и знака числа преобразуется преобразователем 39 в 20 позиционный. При этом на одном из выходов преобразователя 39 устанавливается уровень логической единицы, разрешающий прохождение тактового импульса с входа 27 через соответствую- 25 щий элемент И 34-1 - 34-(М+1) на суммирующий вход относящегося в нему счетчика каждой из ячеек 36-1 - 36(М+1). Счетчик каждой из ячеек

36-) — 36-(М+1) осуществляет фиксацию наличия соответствующего ему числа на информационных входах устрой-, ства. В связи с тем, что при установке каждого конкретного адреса происходит нарастание кода счетчика каж дой из ячеек 36-1 — 36-(М+1) на одну единицу, разные числа в упорядоченном массиве могут следовать в произвольном порядке. Число разрядов счетчиков 46, следовательно, и регистров 40

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

Таким образом, после подачи всех 45 чисел упорядоченного массива на входы 4-1 — 4-N и 5 устройства в счетчиках 46 каждой из ячеек 36-1 — 36(М+1) памяти блока 11 памяти устанавливаются коды, пропорциональные количеству равных чисел в упорядоченном массиве. Эти коды задним фронтом сигнала Ввод-вывод" на входе l устройства с помощью элемента НЕ 33н формирователя 32 переписываются из счетчиков 46 в регистры 48 каждой из ячеек 36-1 — 36-(М+1) памяти.

Для вывода упорядоченного массива необходимо подать на входы 4 1

4-N вход 5 и вход 3 код, соответствующий требованиям начальным условиям по таблице.

Необходимо также осуществить запись соответствующих кодов начальных условий в счетчик 13, триггеры 14 и

12 путем подачи импульса записи на вход 6 устройства и установить на входе 1 устройства нулевой потенциал, переключающий мультиплексор 10 в режим передачи сигнала с входа В на выход С, закрывающий группу входных элементов И 34-1 — 34-(М+1),разрешающий открываться входным элементам И 35-1 — 35-(M+I), выходным элементам И 37-1 - 37-(М+1) и элементу

И 18.

Пусть, например, необходимо вывести положительные числа в порядке их возрастания. После подачи соответствующих указаний см. таблиду потенциалов на входы 3-5 устройства триггер 12 устанавливается в единичное состояние, предписывающее работу счетчика 13 в режиме суммирования, сам счетчик 13 устанавливается в нулевое состояние, т.е. значение минимального числа, а триггер 14 — в единичное состояние, соответствующее положительным числам.

Как только на входе 1 устройства устанавливается нулевой потенциал, элемент И 18 открывается единичным потенциалом с выхода элемента НЕ 17 для прохождения тактовых импульсов с входа 7 устройства на тактовый вход счетчика 13 и через мультиплексор 10 на тактовый вход блока 11 памяти.

Нулевой выходной код счетчика 13 и единичный потенциал с выхода триггера 14 подаются на адресные выходы

30-1 - ЗО-N, 31 блока 11 памяти, который осуществляет проверку присущ ствия в упорядоченном массиве такого кода. Информация об этом хранится в ячейках 36-1 - 36-(М+1) памяти. В случае, если при записи упорядоченно го массива этот код присутствует, по соответствующему адресу в счетчике

46 устанавливается единичный код, если таких чисел несколько, код в счетчике 46 соответствует количеству нулевых чисел со .знаком плюс в упорядоченном массиве, если этого числа в массиве нет, в счетчике нулевой код, установленный перед вводом чисел yhoрядоченного массива сигналом "Сброс"

5 13833 на входе 2 устройства, входе 27 блока 11 памяти и входе 44 ячеек 36-1

36-(М+!) памяти.

Дешифратор 47, выход которого является выходом ячейки 36 памяти, от5 мечает выходным сигналом наличие нулевого кода в счетчике 46 и единичным кода, отличного от нулевого.

Аналогично производится проверка наличия чисел в,порядоченном массиве, отличных от нуля.

Установка на адресных входах

30-1 - 30-М и 31 блока 11 памяти некоторого кода приводит при считывании к обращению к i-й ячейке памяти. . Это осуществляется подключением ее выхода 50, т.е. выхода дешифратора

47, через открытые единичным потенциалом с выхода элемента НЕ 33 и с 20 выхода преобразователя 39 элементы И

37"1 — 37(М+1) и элемент ИЛИ 38 к вы ходу 40 запоминающего устройства.

Следовательно, если число в счетчике 46 отлично от нуля, т.е. при запи- 2 си присутствуют числа, соответствую щие адресу i-й ячейки, на выходе блока 11 памяти устанавливается логическая единица, разрешающая прохождение при считывании выходного кода счетчи- 30 ка 13, потенциала с выхода триггера

14 и тактового импульса с выхода открытого элемента И 18 через элементы

И 15-1 — 15-(N+!) и 19 на выходы

22-1 — 22-N, 23 и 24 устройства.

В связи с тем, что выход дешифратора 47 нуля соединен с одним входом элемента И 49, на второй вход которого подается тактовый сигнал, в случае, если код в счетчике отличен от нуля, тактовый импульс через открытый элемент И 49 подается на вычитающий вход счетчика 46.

Таким образом, с каждым тактовым импульсом в счетчике 46 код убывает на единицу до тех пор, пока дешифра тор нуля не запретит прохождение тактовых импульсов через элемент И 49 нулевым сигналом на его выходе.

Одновременно дешифратор 47 при наличии равных чисел в упорядоченном массиве запрещает прохождение тактовых импульсов в счетчик 13 с помощью элемента HE 8 и элемента И 9 до тех пор, пока код в i-м счетчике 46 не станет нулевым. Как только это прои- 55 зойдет, нулевой выходной потенциал дешифратора 47 ячейки 36 памяти через элемент НЕ 8 разрешает прохожде6

Зб ние последующего тактового импульса с выхода элемента И 18 через элемент И 9 на вход счетчика 13.

В соответствии с этим как только будут считаны все нулевые числа из соответствующей ячейке. Зб памяти следующим за этим тактовым импульсом, счетчик 13 устанавливается в состояние 0...01 и начинается проверка наличия таких чисел в упорядоченном массиве, которая может быть рассмотрена аналогично.

В связи с тем, что числа в счетчике 13 линейно нарастают и производится последовательная проверка наличия каждого из этих чисел, на выходах устройства 22-1 — 22-N 23 выделяются в нарастающем порядке числа, присутствовавшие в упорядоченном массиве до тех пор, пока не установится в счетчике 13 нулевое число, что отме-" чается дешифратором 21. Если вслед за этим не вводятся новые начальные условия, счетчик 13 циклически повторяет вывод положительных чисел в порядке нарастания. Если вводятся новые начальные условия (см. таблицу), счетчик 13 и триггер 14.обеспечивают циклический вывод положительных чи сел в порядке убывания (в этом случае счетчик работает на вычитание), отрицательных чисел в порядке возрастания (счетчик 13 работает на вычитание), отрицательных чисел в порядке убывания (счетчик 13 работает на суммирование). Работу устройства в этих режимах рассмотреть несложно по аналогии с описанным.

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

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

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

13833

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

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

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

D-триггеров, к входу разрешения записи счетчика и первому информационному входу мультиплексора, вход блока памяти соединен с выходом мультиплексора, тактовый вход устройства соеди.нен с вторым входом первого элемента И, выход .которого соединен с пер- . вым входом второго и третьего элементов И и с вторым информационным вхо- 4О дом мультиплексора, выход второго элемента И соединен с тактовым входом счетчика, вход выбора режима которого соединен с прямым выходом второго триггера, прямой выход первого .45 триггера подключен к (0+1)-му адресному входу блока памяти и первому входу четвертого элемента И, второй вход которого соединен с вторыми входами элементов И группы и через второй элемент НЕ с вторым входом второ50

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

"Знак" устройства, выход третьего элемента И является синхронизирующим выходом устройства.

2. Устройство по п.l, о т л и— ч а ю щ е е с я тем, что блок памяти содержит первую, вторую и третью группы элементов И по (М+1) элементов в каждой (где М вЂ” количество элементов массива чисел), группу из (М+1) ячеек памяти, преобразователь двоичного кода в позиционный, формирователь импульсов, элемент ИЛИ и элемент НЕ, причем адресные входы блока памяти подключены к входам преобразователя двоичного кода в позиционный, вход выбора режима блока памяти соединен с первыми входами элементов И .первой группы и через элемент НЕ с первыми входами элементов

И второй и третьей групп и входом формирователя импульсов, тактбвый вход блока памяти соединен с вторыми взводами элементов И первой и второй групп, вторые входы i-го элемента И третьей группы (где i = 1,..., М+1) соединен с выходом i-й ячейки памяти, третьи входы элементов И всех трех групп соединены с соответствующими выходами преобразователя двоичного кода в позиционный, выход i-х элементов И первой и второй групп подключены соответственно к суммирующему и вычитающему входам i-й ячейки памяти, вход сброса блока памяти соединен с входами сброса всех ячеек памяти, первый синхровход каждой ячейки памяти соединен с синхронизирующими входами блока памяти, второй синхровход ячеек памяти соединен с выходом формирователя сигналов, выходы элементов И третьей группы соединены с входами элемента ИЛИ, выход которого является выходом блока памяти.. 3 ° Устройство по пп. 1 и 2, о т— л и ч а ю щ е е с я тем, что ячейка памяти содержит реверсивный счетчик, регистр, дешифратор нуля, элемент И, причем суммирующий вход ячейки памяти соединен с суммирующим входом реверсивного счетчика, вход сброса ячейки памяти соединен с входом начальной установки реверсивного счетчика, первый синхровход ячейки памяти объединен с управляющим входом.регистра, второй синхровход соединен с

1.3833 36

10 в порядке возрастания

00...0 в порядке убыва, ния

11...1

0 в порядке возрастания

11... 1

0 в порядке убывания

00...0

0 входом разрешения записи реверсивного счетчика, вычитающий вход ячейки памяти соединен с первым входом элемента И, выход которого соединен с вычитающим входом реверсивного счетчика, выходы разрядов реверсивного счетчика соединены с информационными

Режим ввода Входы 4-1

Положительные числа

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

I — 4-N Вход 5 Вход 3

138333б

Составитель B.Æóðàâëåâ

Техред Л.Олийнык Корректор Г.Решетник

Редактор Л.Лангазо

Заказ 1297/47 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4