Устройство для упорядочения массива чисел Советский патент 1988 года по МПК G06F7/08 

ння равных чисел при выводе. Устрой- ство содержит блок памяти 1 1, мульти плексор 10, два триггера 12, 14, ре- версивный счетчик 13, группу элементов И 15 - i5(N+l), формирователь импульсов 20, два элемента И 18, 19, два элемента НЕ 8, 17 и элемент ИЖ 16. При упорядочении массива чисел осуществляется запись в блок памяти признаков наличия чисел по адресу, задаваемому значением числа. Считы-

83336

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

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

1

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

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

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

Устройство для упорядочения массива чисел (фиг.1)-содержит управляю- шд-ш вход 1 информации, вход 2 Сброс вход 3 задаьшя режима сортировки чисел при выводе упорядоченного массива, входы 4-1 - 4-N модуля, вход 5 знака, вход 6 записи чисел, тактовый вход 7, элемент НЕ 8, элемент И 9, ryльтиплeкcop 10, блок 11 памяти, ЕИтриггер 12, | разрядный счетчик 13 СИтриггер .14,группу из N+1 элементов И 15-1 15-N четвертый элемент И 15-(N+t), элемент ИЛИ 16, Элемент НЕ 17, элементы НЕ 8 и 19, формирователь 20 импульса по переднему фронту входного сигнала, дешифратор 21 нуля, выходы 22 - 22-N, выход 23 зна ка упорядоченных чисел, синхронизирующий выход 24, управляющий выход 25.

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

10

15

20

25

30

35

40

знака числа, формирователь 32 импульса, элемент ПЕ 33, группу элементов И 34-1 - 34-(М+1), группу элементов . И 35-1 35-(М+1), ячейки 36-1 - 36(М+ +1) памяти, группу элементов И 37-1 - 37-(М-И), элемент ИЛИ 38, преобразователь 39 двоичного кода в позиционный, выход 40 блока памяти.

Ячейки 36-1 - 36-(М+1) памяти содержат синхронизирующий вход 41 кон-

гца цикла ввода, суммирующий 42 и вычитающий 43 входы, вход 44 Сброс, синхронизирующий вход 45, реверсивный счетчик 46, дешифратор 47 нуля, регистр 48, элемент И 49, информаци-

-онный выход 50.

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

Для ввода чисел упорядоче.нного массива необходимо подать на вход 2 (фиг.1) импульс, осуществляюший установку в нулевое состояние реверсивного счетчика 46 (фиг.З), установить единичный потенциал на входе 1, переключающий мультиплексор 10 (фиг.1) в режим передачи информации с входа . А на выход С, разрешающий открыться группе входных элементов И 34-1 - 34-(М+1) (фиг.2) для прохождения импульсов с тактового входа 27 (фиг.2) на суммируюп1ий вход счетчика 46 и закрывающий нулевым сигналом с выхода элемента НЕ 17 прохождение такто-

.вых импульсов с входа 7 через элемент И 18 на вход N-разрядного счетчика 13, а также с выхода элемента НЕ 33 на элементы И 37-1 - 37(М+1). Кроме того, необходимо подать синхронно с импульсами записи на входе 6 числа упорядоченного массива на вхо-

31

ды 4-1 - 4-N модули чисел, а на вход 5 -: знаки чисел.

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

«В связи с тем, что мультиплексор 10 открыт для прохождения импульса записи с входа А на выход С с его вы хода, этот импульс .поступает на тактовый вход 27 блока памяти. В это же время с выхода счетчика 13 модуль числа, а с выхода D-триггера 14 знак числа подаются на адресные входы 30-1 - 30-N и 31 блока 11 памяти. Двоичный код модуля и знака числа преобразуется преобразователем 39 в позиционный. При этом на одном из выходов преобразователя 39 устанавливается уровень логической единицы, разрешающий прохождение тактового им пульса с входа 27 через соответствую щий элемент И 34-1 - 34-(М+1) на суммирующий вход относящегося в нему счетчика каждой из ячеек 36-1 - 36- (М+1). Счетчик каждой из ячеек 36-1 - 36-(М+1) осуществляет фиксацию наличия соответствующего ему числа на информационных входах устрой- cfBa. В связи с тем, что при установке каждого конкретного адреса происходит нарастание кода счетчика каждой из ячеек 36-1 - 36-(М+1) на одну единицу, разные числа в упорядоченном массиве могут следовать в произвольном порядке. Число разрядов счетчиков 46, следовательно, и регистров 48 должно выбираться из условия максимально возможного количества разных чисел в упорядоченном массиве.

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

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

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

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

5

0

5

0

5

0

5

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

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

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

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

на входе 2 устройства, входе 27 бло- ка П памяти и входе 44 ячеек памяти.

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

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

Установка на адресных входах ЗО 3O-N и 31 блока 1 1 памяти не- которого кода приводит при считыва- НИИ к обращению к ячейке памяти. Это осуи1ествляется .подключением ее выхода 50, т.е. выхода дешифратора 47, через открытые единичным потенциалом с выхода элемента НЕ 33 и с выхода преобразователя 39 элементы И 37-1 - 37(М+1) и элемент ИЛИ 38 к выходу 40 запоминакяцего устройства. Следовательно, если число в счетчике 46 отлично от нуля, т.е. при запи си присутствуют числа, соответствую- щие адресу i-й ячейки, на выходе блока 11 памяти устанавливается логическая единица, разрешающая прохождение при считывании выходного кода счетчи ка 13, потенциала с выхода триггера 14 и тактового импульса с выхода от- крытого элемента И 18 через элементы И 15-1 - 15-(Ы+1) и 19 на выходы 22-1 - 22-N, 23 и 24 устройства.

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

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

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

Q

0 5 Q

5

0

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

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

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

счетчик 13 и триггер 14 обеспечивают циклический вывод положительных чисел в порядке убывания (в этом случае счетчик работает на вычитание), отрицательных чисел в порядке возрастания (счетчик 13 работает на вычитание), отрицательных чисел в порядке убывания (счетчик 13 работает на суммирование). Работу устройства в этих режимах рассмотреть несложно по аналогии с описанным.

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

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

блока памяти с первого по N -H и с соответствующими первыми входами элв ментов И группы, вторые входы кото рых соединены с выходом блока памяти, управляющий вход устройства соединен . с управляюпшм входом мультиплексора, выходы элементов И группы являются выходами устройства, отличаю щ е е с я тем, что, с целью расшире ния функциональных возможностей за счет упорядочения массивов чисел с учетом знака и повторения равных чи сел при выводе, в него введены два 1 -триггера, четыре элемента И, второй элемент НЕ, формирователь импуль сов и дешифратор нуля, причем управляющий вход устройства соединен с входом выбора режима блока памяти и через первый элемент НЕ с первым входом первого элемента И, вход сброса блока памяти соединен с входом Сброс устройства, вход Знак устройства соединен с информационным входом первого триггера, вход задания регдама сортировки устройства соединен с информационным входом второго триггера, вход Запись устройства соединен с первым входом элемента ИЛИ, выход которого подключен к тактовым входам первого и второго D-триггеров, к входу разрешения записи счетчика и первому информационно- му входу мультиплексора, вход блока памяти соединен с выходом мультиплексора, тактовый вход устройства соединен с вторым входом первого элемента И, выход которого соединен с первым входом второго и третьего элементов И и с вторым информационным входом мультиплексора, выход второго элемента И соединен с тактовым входом счетчика, вход выбора режима которого соединен с прямым выходом второго триггера, прямой выход первого триггера подключен к (N+l)-My адресному входу блока памяти и первому входу четвертого элемента И, второй вход которого соединен с вторыми входами элементов И группы и через второй элемент НЕ с вторым входом второго элемента И, выходы разрядов счет- чика соединены с соответствующими входами дешифратора нуля, выход которого соединен с входом-формирователя импульсов и является управляющим выходом устройства, выход формирователя импульсов соединен с вторым входом элемента ИЛИ и с синхронизирую-

5

0

5

0

5

0

5

0

5

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

91383

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

Режим ввода

Т

Входы 4-1

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

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

00...О

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

Отрицательные числа

П...1

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

П...1

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

00.. .0

0

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

I

-к|вход 5 Г

Вход 3