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

 

Г. А. Ерошко и Н. Н. Шубина (72) Авторы изобретения (71) Заявитель (54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ ЧИСЕЛ

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

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

Недостаток этого устройства - ою ра15 ннченные функциональные возможности; позволяет только присваивать ранги без упорядочения данных по рангамм..

Наиболее близким к предлагаемому является устройство дпя упорядочения чисел, содержащее )ч кольцевых регистров, управляюшие элементы И-ИЛИ, входные элементы И-ИЛИ, дешифраторы, счетчики, элементы И, ИЛИ, регистр, схему сравнения, узел синхронизации, первый выход которого соединен с установочными входами кольцевых регистров, с управляющим входом схемы сравнения и с входом первого счетчика, выходы которого подключены к входам первого дешифратора н установочным входам второго счетчика, выходы которого соединены с входамн второго дешифратор&, каждый (-bN выход первого дешифратора, где 1=

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

И-ИЛИ и с первым входом j-го входного элемента И-ИЛИ, выход каждого

1-го входного элемента И-ИЛИ подк почен к входу j-го кольцевого регистра, выход каждого 1-го кольцевого регистра соединен с (1 +И вЂ” 1)-ым входом первого управляющего элемента И-ИЛИ, выход которого подключен к первому информационному входу схемы сравнения и. к первому входу первого элемента И, выход которого соединен с первым установочным входом регистра, первый выход которого подклкчен к вторым входам 1, 2, ..., (И-1) входных элементов И-ИЛИ, каждый j «ый выход второго дешнфратора соединен с j-ым входом второго управпяюшего -элемента И-ИЛИ, каждый

)-ый выход второго дешифратора, где

1, 2, ..., (И-2), подкпючен к третьим входам (+1)-го входного эпемента И-ИЛИ, (p-1) выход второго дешиф» ратора соединен с первым входом И-ro ,входного элемента И-ИЛИ, выход кото рого соединен с входом Н-го кольцевого регистра, выход которого подключен к -му входу второго управпяюшего эпемента И-ИЛИ, выход каждого К-ro копьцевого регистра, где К-"2...„(й-1) соединен с (К+И-1) входом второго управпяюшего элемента И-ИЛИ, выход, которого подкпючен к второму информационному входу схемы сравнения и к первому входу второго эпемента И, выход которого соединен с вторым установочным входом регистра, второй выход .которого подключен к четвертым входам 2, 3, ..., 25 (И-1) входных элементов И-ИЛИ и к второму входу И -го эпемента И-ИЛИ, первый выход схемы сравнения соединен с вторыми входами элементов И и с первым управляюшим входом узна синхронизации, второй выход которого подкпючен к информационному входу регистра и к вторым установочным входам копьцевых регистров, второй выход схемы сравнения соединен с первым входом эпемента ИЛИ второй вход которого подключен к третьему выходу узла синхронизации, а выход — к информационному входу второго счетчика, выход которого соединен с вторым управляюшим входом узла синхронизации f2).

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

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

Поставленная цепь достигается тем, что в устройство дпя упорядочения чисеп, содержашее И копьцевых сдвигаюших регистров, эпементы (И-1) И-ИЛИ, два входных элемента И, (И-2) входных эпе» мента 2И-ИЛИ, дешифраторы, счетчики, эпементы И, ИЛИ, регистр, узел синхронизации, первый выход которого соединен

3 932488 а с установочными входами копьцевых регистров„с управпяюшим входом схемы сравнения и с входом первого счетчика, выходы которого подключены к входам первого дешифратора н установочным входам второго счетчика,выходы которого соединены с входами второго дешифратора, каждый j-ый выход первого дешифратора, где j =1, 2, ..., (И-1), соединен с

i0 е-ым входом первого элемента (й-1) ИИЛИ, первый выход первого дешифратора соединен с первым входом первого вход ного эпемента И, выход которого подключен к входу первого кольцевого сдвнгаюшего регистра, а каждый (+1 -ый выход первого дешифратора, где j = .1, 2, ..., (И-2), соединен с первым входом

)-го входного элемента 2И-ИЛИ, выход каждого из которых лодкпючен к входу (3 +1)-го кольцевого сдвигаюшего регистра, выход каждого g-го кош цевого сдвигаюшего регистра соединен с (е+И-1)-ым входом первого эпемента (ln-l) И-ИЛИ, выход которого подкпючен к первому информационному входу схемы сравнения и к первому входу первого эцемента И, выход которого соединен с первым установочным входом регистра, первый выход которого подключен к вторым входам первого входного элемента И и 1, 2„..., 30 (И-2)-го входных элементов 2И-ИЛИ, каждый -ый выход второго дешифратора соединен с -ым входом второго эпемента ф1-1) И-ИЛИ, каждый j -ый выход второго дешифратора подкцючен к третьему входу )-го входного элемента

2И-ИЛИ, 0в-1)-ый выход второго дешифратора соединен с первым входом второго входного элемента И, выход которого соединен с входом М-го копьцевого сдвигаюшего регистра, выход которого подключен к й-му входу второго управпяюшего элемента (H-1) И-ИЛИ, выход каждого ()+1 )-го копьцевого сдвигаюшего регистра соединен с (j+H)-ым входом второго э цемента . (1 ) И-ИЛИ, выход которого подключен к второму информационному входу схемы сравнения и к первому входу второго эпемента И, выход которого соединен с вторым установочным вхо50 дом регистра, второй выход которого подкпючен к четвертым входам 1, 2, ..., (й-2)-го входных эпементов 2И-ИЛИ и к второму входу второго входного эпемен та И, первый выход схемы сравнения соединен с вторыми ВхоАаМН эпементов И и с первым управпяюшим вкодом узла син,хронизации, второй выход которого под ключен к информационному входу регист932488 ра и к вторым установочным входам копь цевых сдвигающих регистров, второй выход схемы сравнения соединен с первым входом первого элемента ИЛИ, второй вход которого подключен к третьему выходу узла синхронизации, а выход - к информационному входу второго счетчика, дополнительно введены регистры, счетчик, сумматор, элемент дешифрации числе Иэлементы И, ИЛИ, две группы р разре- 0 шающкх элементов И, каждый первый вход

5-ro разрешающего элемента И двух групп подключен к 1-му выходу первого дешифратора, первые входы двух И-ых разрешающих элементов И подключены к выходу 15 элемента дешифрации числа И, вход которого подключен к выходу сумматора и к вторым входам с-ых разрешающих элементов И первой группы, где Р «1, 2, ..., и, выход каждого (-ro разрешающе- 20

ro элемента И первой группы подкпючен к входам разрядов Р-ro кольцевого сдви гающего регистра, вторые входы Р -ых разрешающих элементов И второй группы подключены к выходу второго регистре, вход которого связан с выходом третье.го элемента И, а выход каждого (-го разрешающего элемента И второй группы соединен с входами разрядов f,-го коа цевого сдвигающего регистра, третьи входы разрешающих элементов И двух групп подключены к выходу четвертого элемента И, первый вход которого связан с (И-1)-ым выходом второго дешифратора и вторым управняющим входом узла синхронизации, а второй вход - с четвер3$ тым выходом узла синхронизации и первым входом пятого элемента И, выход которого подключен к входу третьего регистра, выход которого соединен с перЩ вым входом третьего элемента И, второй вход которого соединен с выходом первого счетчика и первым информационным входом сумматора, второй информацион,ный вход -которого подключен к выходу фф пятого элемента И вход Сброс" сумма. тора связан с первым выходом узла синхронизации и с первым входом второго элемента HIM, второй вход которого соединен с первым выходом схемы сравнения, выход второго элемента ИЛИ связан с входом "Сброс третьего счетчика, выход которогс подключен к второму входу пятого элемента И, а счетным входом— к третьему выходу схемы сравнения и третьему входу первого элемента ИЛИ.

На чертеже представпена блок-схема устройства.

Устройство содержит копьцевые регистры 1, 1, ..., 1„, сдвига, элементы И

2 -2>, 3, -3, 4,-4>, 5-9, эпементы 2ИИЛИ 101-10 элементы (И-1) И-ИЛИ

11 и 12, дешифраторы 13 и 14, регистры 15-17, счетчики 18-20, сумматор

21, элементы ИЛИ 22 и 23, схему 24 сравнения, узел 25 синхронизации, элемент 26 дешифрации числа. Кольцевые регистры 1 -1 сдвига на и разрядов, предназначенные дпя записи и хранения ранжируемых чисел (К разрядов с 1 по

К}, признаков (адресов) чисел (P-разрядов с К+1 по с) ), максимапького ран- га числа (разряды с ф+1 по ), минимального ранга чиспа (разряды с 13+1 по vn), связаны следующим образом: пер. вый регистр по входу подкшочен к вы- . ходу элемента И 2,, по выходу связан с вторым входом элемента (И-1) И-ИЛИ

ll; регистры 1 ;1 „, связаны по входу, с выходом соответствующего элемента

2И-ИЛИ 10д«10к <, а о выходу с соответствующими четными с четвертого по

2 (И-1)-ый входами элементов (И-ХГЙ- .

ИЛИ 11 и нечетными с первого о (2N5)-ый входами элемента (И-1) И-ИЛИ

12; регистр 1„, по входу подключен к выходу элемента И 2 а о выходу - к (2) -3)-му входу элемента (и-1) ИИЛИ 12. Кроме того, разряды с (ф+1) по г регистров 1, -1 подключены к вы ходам соответствующих элементов И 44

4и, а разряды с ()"+1) по ю- к выходам элементов И 3 -3 „Схема 24 сравнения сравнивает два числа А и В путем вычитанич (А-В) и работает в двух режимах: — выбор максимального чиспа; Я вЂ” выбор минимального числа. В зависимости от режима работы устройства в . схеме

24 сравнения сравниваются ранжируемые числа (режим ранжирования и упорядочения по рангам) ипи признаки (aapeca) чисел (режим упорядочения по признакам (адресам). По входам схема 24 сравнения подключена к выходам элементов (g-1) И-ИЛИ 11 и 12, которые также связаны с первыми входами эпементов

И 5 к 6 соответственно. Первый выход схемы 24 сравнении, сигнал на котором появляется в случае А В - дпя Т режима, А< В - дпя gi р еж им а, подключен к первому входу элемента ИЛИ 23, выход которого связан со счетным входом счетчика 19, Второй выход схемы 24 сравнения, сигнал на котором появляется в случае А=В, подключен к второму входу элемента ИЛИ 23 и счетному sxoay счетчика 20 для подсчета количества рав7 9324 ных чисеп, выход которого связан с первым входом элемента И 9, в выход поспеднего соединен с входом регистра 17 и первым входом сумматора 21, выход которого подключен к первым входам эле- ментов И 4 -4 и через элемент 26 де1 шифрации числа к третьим входам эпементов И Э„и 4„,. Инверсный выход регистра 17 подключен к первому входу эпемента И 7, выход которого связан с вхо- 1п дом регистра 16, по выходу подключенного к первым входам эпемента И 3 -3>.

Третий выход схемы 24 сравнения, сигнал на котором появляется в спучае А<В для I режима; А7  — для Й режима, 1$ связан с вторыми входами элементов И, 5 и 6, входом узла 25 синхронизации и первым входом элемента ИЛИ 22, выход которого подключен к входу Сброс счетчика 20. Счетчик 18 на (И-1) дпя по1 » 2п счета адреса чиспв А по входу подключен к выходу узла 25 синхронизации, а по выходу связан с установочным входом счетчика 19 на И, первоначацьное состояние которого соответствует значению 2у счетчика 18 с добавлением +1, вторыми входами элемента И 7 и сумматора 21, входом дешифратора 13, выходы которого соединены соответственно с нечетными с первого по (2И-Э)-ый входами эпемента (И-1) И-ИЛИ 11, первыми входами элементов И 2. и 2И-ИЛИ 10 -10 ртретьими входами элементов И 3 -3 1,4 4 1, .Выход счетчика 19 подключен к входу дешифратора 14, выходы которого связаны с соответствующими четными с вто. рого по 2 (И-1 -ый входами эпемеита (И-1). И-ИЛИ 12, четвертыми входами элементов 2И-ИЛИ 10 -10 и первым входом эпемента И 2 . Первый выход дешифратора 14 подключен также к входу узла 25 синхронизапии и первому входу элемента И 8, выход которого связан с вторыми входами элементов И 3 -Эи, 1

4„-4>. Регистр 15 - кольцевой регистр

43сдвига для перестановки двух чисеп - подключен следующим образом: вход aepsoro числа - к выходу элемента И 5, а вы ход к вторым входам эпементов И 2 и 2И-ИЛИ 101-10> А вход второго чиспа1 36 к выходу элемента И 6, а выход - к второму входу элемента И 2, и третьим входам элементов 2И-ИЛЙ 10 -10 .Узеп

25 синхронизации связан с регистрами

1 -1, 15, схемой 24 сравнения, сумматором 21, счетчиком 18, элементами

$5

ИЛИ 22 и 23, вторыми входами эпементов И 8, 9 и предназначен для управпе ния работой устройства.

88 8

Устройство работает в двух режимах. режим - режим ранжирования и упорядочения по рангам. В этом режиме устройство работает спедуюшим образом. По стартовому импупьсу 27 уэеп 25 синхронизации вырабатывает сигнап, который задает режим выбора максимапьного ипи минимального ранжируемого числа в схеме 24 сравнения, разрешает работу кольцевых регистров сдвига 1 -1> в режиме считывания, сбрасывает счетчик 20 (через элемент ИЛИ 22) и сумматор 21 в

0 и устанавливает счетчик 18 в состояние 1 (соответственнр счетчик 19 в состояние «2"). Первоначальное состояние регистра 17 0", следовательно, в регистр 16 через эпемент И 7 запишется число, находящееся в счетчике 18, т.е. "1". Числа, нолученные в счетчиках

18 и 19, дешифрируются, и на одной из выходных шин дешифраторов 13 и 14 соответственно появпяется сигнал, т.е. открываются по одному иэ входов эпементы И 2, 3,, Q, эпемент 2И-ИЛИ 10 элементы (И-1) И-ИЛИ 11 и 12. Через эпемент (п-1) И-ИЛИ 11 в схему 24 сравнения поступает число A с регистра

1, в через элемент (И-1) И-ИЛИ 12 чйсло В с регистра 1 . Поспе сравнения чисеп возможны спедующие варианты работы устройства: если А> В, то с первого выхода схемы 24 сравнения через элемент ИЛИ 23 сигнал поступает в счетчик 19 и переключает его в состояние 3, работа устройства продопжвется; если А=В, то со второго выхода схемы 24 сравнения через элемент ИЛИ

23 сигнал поступает в счетчик 19 и переключает его в состояние 3, одновременно этот же сигнал подается нв счетный вход . счетчика 20 и увепичиввют его значение нв 1, работа устрой« ства продолжается; если А <В, то появляется сигиап на третьем выходе схемы

24 сравнения, открывающий по одному входу эпементы И 5 и 6, сбрасываюший счетчик 20 в состояние "0 через элемент ИЛИ 22 и одновременно поступающий в узел синхронизации 25, который по этому сигналу вырабатывает сигнал, разрешающий сдвиг в регистре 15 и работу кольцевых регистров 1 -1, сдвига в режиме записи. Числа А и В через эпементы И 5 и 6 соответственно поступают в регистр 15, сдвигаются и записываются в соответствующие кольцевые регистры 1, и 1 сдвига, через эпементы

И 2, и 2И-ИЛИ 10, т.е. А - в регистр

1д„а  — в регистр 1, . После записи

9 9324 чисел по сигналам от узла 25 синхронизации счетчик 19 переключается в состояние 3, в кольцевые регистры.1 -1 сдвига в режим считывания, и работа устройства продолжается. Как только в счет % чике 19 будет число И, по сигналу с выхода дешифрвтора 14 через интервал времени, необходимый аля сравнения -g-го ранжнруемого числа, узел 25 синхронизации вырабатывает сигнал, разрешающий запись рангов чисел в разряды с (ф+1) по И1 регистров 1 -1н, т.е. открывающий элементы И 3 -3и, 4.1-4и, 8 и 9. Число, находящееся в счетчике 20, переписывается в регистр 17 и в сумматор 21, 13 гае складывается с числом, нахоаяшимся в счетчике 18. Число, находящееся в регистре 16, записывается в разряаы с (И+1) по N регистра 1 через элемент

И Э и соответствует минимальному ран- 3в гу ранжируемого числа, а число, находящееся в сумматоре 21 - через элемент

И 4 s разряды с (+1) по р регистра

1 и соответствует максимальному рангу, В регистр 16 через элемент И 7 записывается число, находящееся в счетчике

18, лишь в том случае, когда в регист-. ре 17 записан "0". Через интервал времени, необходимый для записи рангов числа, в узле 25 синхронизации вырабатывается сигнал, переключающий счетчик 18 в состояние «2», соответственно счетчик

19 в состояние 3 . Работа устройства продолжается до полного ранжирования чисел я их упорядочения в зависимости

3f от ранга. 7t режим - режим упорядочения по признакам (адресам). Предполагается, что в режиме 3 в регистрах 1 -1И уже записаны ранжируемые числа (К-разрядов), признаки чисел (P-разрядов) в ранги чисел. Упорядочение чисел вместе с рангами проводится по признакам (адресам) чисел, записанным в разряды с (К+1) по g каждого регистра. Сравнение в схеме 24 сравнения проводится только

43 цо значениям укаэанных P-разрядов. В остальном работа устройства по ynopsaoчению чисел вместе с рангами аналогична работе устройства в режиме I.

Технико-экономический эффект изобре- 3В тения заключается в том, что за счет введения двух регистров, счетчика, сумматора, элементов И, ИЛИ расширяются функции устройства. При относительной простоте технической реализапии нв стан- 33 дартных элементах цифровой вычислительной техники предлагаемое устройство поз воняет присваивать ранги множеству. чисел.

10 в также производить упорядочение Чисел в соответствии с значением ранга, или упорядочивать числа вместе с присвоенными им рангами по ранее присвоенным признакам (адресам). Автоматическое выполнение этих функций с помощью предлагаемого устройства приводит к сокращению времени, повышает верность результатов и обеспечивает дальнейшую автоматизацию всего процесса обработки статистической информации.

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

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

И-ИЛИ, первый выход первого дешифратора соединен с первым входом первого входного элемента И, выход которого подключен к входу первого кольцевого сдвигаюшего регистра, а каждый (+1)-й выход первого дешифрвтора, где = 1, 2, . ° ., (2), соединен с первым входом

)-го входного элемента 2И-ИЛИ, выход каждого иэ которых подключен к входу (j+1 )-го кольцевого сдвигающего регистра, выход каждого 1-го кольцевого сдвигвюшего регистра соединен с (1+тих-1)-м входом первого элемента (И-1 ) И-ИЛИ, выход которого подключен к первому информационному входу схемы сравнения и к первому входу первого элемента И, выкод которого соединен с первым установочным входом регистра, первый выход которого подключен к вторым входам nepsoro входного элемента И и 1, 2, ..., (И-2)-го входных элементов 2И-ИЛИ, каждый 1-й выхоа .второго дешифратора соединен с 1-м входом второго элемента (и-1) И-ИЛИ, каждый j-й выход второго дешифрвтора подключен к третьему входу j-го входного элемента 2И-ИЛИ (И-1)-й выход второго дешифраторв сое932 динен с первым входом второго входного элемента И, выход которого соединен с входом И -го кольцевого сдвигаюшего регистра, выход которого подключен к

И-му входу второго управляющего эпемен- 5 та (И-1) И-ИЛИ, выход каждого (+1)-го кольцевого сдвигаюшего регистра соединен с ()+И)-м входом второго элемента (И-1) И-ИЛИ, выход которого подключен к второму информационному входу схемы 0 сравнения и к первому входу второго элемента И, выход которого соединен с вторым установочным входом регистра, вто« рой выход которого подключен к четвертым входам 1, 2, ..., (И-2)-го входных д элементов 2И-ИЛИ и к второму входу второго входного элемента И, первый выход схемы сравнения соединен с-вторыми входами элементов И и с первым управляюшим входом узла синхронизации, второй выход которого подкшочен к информационному входу регистра и к вторым установочным входам кольцевых сдвигаюших регистров, второй выхо@ схемы сравнения соединен с первйм входом первого элемента ИЛИ, второй вход которого подключен к третьему выходу узла синхронизации, а выход - к информационному входу второго счетчика, о т л и ч а ю ш ее с я тем, что, с целью расширения функциональных возможностей за счет ранжиро-вания цифровых данных и их упорядочения в зависимости от ранга или признака (адреса) числа, h него дополнительно введены регистры, счетчик, сумматор, элемент дешифрация числа И,элементы И, ИЛИ две группы м разрешающих элементов И, r каждый первый вход 1-го разрешающею элемента И двух групп подключен к i-му выходу первога дешифратора, первые входы двух и-х разрешающих элементов И под4циочены к выходу элемента дешифрации числа И, вход которого подключен к выходу сумматора и 4к BTopbg4 BxogBM

8-х разрешающих элементов И первой груп-..

pr

488 12 пы, где 6 = 1, 2, ...,, выход каждого б-го разрешающего элемента И первой группы подключен к входам разрядов Р-го кольцевого сдвигвющего регистра, вторые входы 8-х разрешающих элементов И второй группы подкшочены к выходу второго регистра, вход которого связан с выходом третьего элемента И, а выход каждого f-ão разрешающего элемента И второй группы соединен с входами разрядов С-го кольцевого сдвигаюшего регистра, третьи входы разрешающих элементов И двух групп подключены к выходу четвертого элемента И, первый вход которого связан с (М-1)-м выходом второго дешифратора и вторым управляющим входом узла синхронизации, а второй вход — с четвертым выходом узла синхронизации и первым входом пятого элемента И, выход которого подкшочен к входу третьего регистра, выход которого соединен с первым входом третьего элемента И, второй вход которого соединен с выходом первого счетчика и первым информациойннм входом сумматора, второй информационный вход которого подключен к выходу пятого элемента И, вход "Сброс сумматора связан с первым выходом узла синхрони залии и с первым входом второго элемента ИЛИ, второй вход которого соединен с первым выжаом схемы сравнения, выход второго элемента ИЛИ связан с входом "Сброс третьего счетчика, выход которого подключен к второму входу пятого элемента И, а счетным входом - к третьему выходу схемы сравнения и треI тьему всходу nepsoro элемента ИЛИ.

Источники информации, принятые во внимание при экспертизе

1, Патент США № 3829664, кн. е 06 F 7/02, опублик. 1974.

2. Авторское свидетельство СССР по заявке ¹ 2814319/18»24, d кл. G 06 Р 7/06, 1979 (прототип).