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

(72 Авторыобретен и ко и Н Н Шубин 71) Заяаитель РОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ ЧИСЕЛ агвемому рядочения х регист- -ИЛИ, входаторы, счете э Изобретение относится к автоматике и вычислительной технике н может быть использовано при реализации технических средств ЭВМ н создании устройств обработки статистическсй информации.Известно устройство дпя ранжирования чисел, содержащее регистры сдвига, счетчики, схему сравнения, схему реверсивного ранжирования, вычнтвющую схему, элементы ИЛИ, И, временную схему, устройство управления и выходное ус 1 ройства с соответствующими связями,обес печиввющими его работоспособность 13.Недостаток этого устройства - ограннченные функциональные возможности; позволяет только присваивать ранги без упорядочения данных по рангвмм,Наиболее близким к предпляется устройство дпя упо сеп, содержащее И копьцев в, управляющие элементы И ны пементы И-ИЛИ, дешиф чики, элементы И, ИЛИ, регистр, схемусравнения, узел синхронизации, первыйвыход которого соединен с установочными входами кольцевых регистров, с управляющим входом схемы сравнения и свходом первого счетчика, выходы которого подключены к входам первого дешифратора и установочным входам второгосчетчика, выходы котороо соединены свходами второго дещнфрвторв, каждый1-ый выход первого дешифраторг, где 1==.1, 2, ., ( И), соединен с-ымвходом первого управляющего элементаИ-ИЛИ н с первым входом 1-го входного элемента И-ИЛИ, выход каждого1-го входного элемента И-ИЛИ подкпсчен к входу 1-го кольцевого регистра,выход каждого 1-го кольцевого регистра соединен с (1+И)-ым входом первого управляющего эпементв И-ИЛИ, выход которого подключен к первому информационному входу схемы сравнения и, кпервому входу первого элемента И, выход которого соединен с первым установочным входом регистра, первый выход которого поаклкчен к вторым входам 1, 2(И) входных элементов И-ИЛИ каждыйый выход второго дещнфратора соединен с 1-ым входом второго управляющего элемента И-ИЛИ, каждый -ый выход второго дещифратора, где1, 2, , (И), подключен к третьим входам (5+1)-го входного элемента И-ИЛИ, (И) выход второго дещиф ратора соединен с первым входом И-го ,вхоаного элемента И-ИЛИ, выход которого соединен с входом И-го кольцевого регистра, выход которого подключен к И-му входу второго управляющего элемента И-ИЛИ, выход каждого К-го копьцевого регистра, где К-"2(и) соединен с (К+И) входом второго управляющего элемента И-ИЛИ, выход, которого подключен к второму информационному входу схемы сравнения и к первому входу второго элемента И, выход которого соединен с вторым установочным входом регистра, второй выход которого поцключен к четвертым входам 2, 325 (И) входных элементов И-ИЛИ и к второму входу И -го элемента И-ИЛИ, первый выход схемы сравнения соединен с вторыми входами элементов И и с первым управляющим входом узла синхронизации, второй выход которого подключенк информационному входу регистра и квторым установочным входам кольцевыхрегистров, второй выход схемы сравнениясоединен с первым входом элемента ИЛИ второй вход которого подключен к третьему выходу узла синхронизации, а выход - к информационному входу второго счетчика, выход которого соединен с вторым управляющим входом узла синхронизации 2),Недостатком. устройства являются ограниченные функциональные возможности,так как оно позволяет лищь упорядочитьцифровые данные по возрастанию (убыванию),Бель изобретения - расширение функциональных возможностей устройства засчет ранжирования цифровых данных иих упорядочения в зависимости от рангаили признака (адреса) числа.Поставленная цепь достигается тем,что в устройство для упорядочения чисел,содержащее й кольцевых сдвигающих регистров, элементы (И) И-ИЛИ, двавходных элемента И, (И) входных эпемента 2 И-ИЛИ, дешифраторы, счетчики,элементы И, ИЛИ, регистр, узел синхронизации, первый выход которого соединен 3 932488 ас установочными входами кольцевых регистровс управляющим входом схемысравнения и с входом первого счетчика,выходы которого подключены к входампервого дещнфраторв н установочным входам второго счетчика,выходы которогосоединены с входами второго дещифратора,каждый 1-ый выход первого дещифратора, где 3 =1, 2, (И), соединен с10 1-ым входом первого элемента (И) ИИЛИ, первый выход первого аещифраторасоединен с первым входом первого входного элемента И, выход которого подключен к входу первого кольцевого сдвнгающего регистра, а каждый И+1 -ыйвыход первого дешифратора, где 1 = .1,2, , (И), соединен с первым входом-го входного элемента 2 И-ИЛИ, выходкаждого из которых подключен к входу(3+1)-го кольцевого сдвигаюшего регистра, выход каждого -го кольцевого сдвигаюшего регистра соединен с (1+И)-ымвхоаом первого элемента (и) И-ИЛИ,выход которого подключен к первому информационному входу схемы сравнения ик первому входу первого элемента И, выход которого соединен с первым установочным входом регистра, первый выходкоторого подключен к вторым входам первого входного элемента И и 1, 230(И)-го входных элементов 2 И-ИЛИ,каждый 1 -ый выход второго дещифратора соединен с м-ым входом второгоэлемента Ь) И-ИЛИ, каждый-ыйвыход второго аешифратора подключен ктретьему входу -го входного элемента2 И-ИЛИ, (И)-ый выход второго дешифратора соединен с первым входом второго входного элемента И, выход которогосоединен с входом М-го кольцевого сдви 40 гаюшего регистра, выход которого подключен к й-му входу второго управляющего элемента (И) И-ИЛИ, выход каждого +1)-го кольцевого сдвигаюшегорегистра соединен с (+И)-ым входом вто 45 рого элемента .(1 ъ 1) И-ИЛИ, выход которого подключен к второму информационному входу схемы сравнения и к первомувходу второго элемента И, выход которого соединен с вторым установочным вхо 50 дом регистра, второй выход которого подключен к четвертым входам 1, 2(И)-го входных элементов 2 И-ИЛИ ик второму входу второго входного элемен та И, первый выход схемы сравнения сое 55 динен с вторыми входами элементов И ис первым управляющимвкодом узла син,хронизации, второй выход которого подключен к информационному входу регистра и к вторым установочным входам копьцевых сдвнгаюших регистров, второй выход схемы сравнения соединен с первым входом первого элемента ИЛИ, второй вход которого подключен к третьему вы- в ходу узла синхронизации, а выход - к информационному входу второго счетчика, дополнительно введены регистры, счетчик, сумматор, элемент дешифрации числе И.элементы И, ИЛИ, две группы р разре шаюших элементов И, каждый первый вход 1-го разрешающего элемента И двух групп подключен к 1 -му выходу первого дешифрвтора, первые входы двух И-ых разрешающих элементов И подключены к выходу 15 элемеята дешифрации числа И, вход которого подключен к выходу сумматора и к вторым входам -ых разрешающих элементов И первой группы, гдем 1, 2, и, выход каждого -го разрешаюше го элемента И первой группы подкпючен к входам разрядов Г-го кольцевого сдвигаюшего регистра, вторые входы-ых разрешающих элементов И второй группы подключены к выходу второго регистре, вход которого связан с выходом третьего элемента И, а выход каждого -го разрешающего элемента И второй группы соединен с входами разрядов -го кольцевого сдвигающего регистра, третьи входы разрешающих элементов И двух групп подключены к выходу четвертого элемента И, первый вход которого связан с (И)-ым выходом второго дешифратора и вторым управяяюшим входом узла синхронизации, а второй вход - с четверМ тым выходом узла синхронизация и первым входом пятого элемента И, выход которого подключен к входу третьего регистра, выход которого соединен с пер 46 вым входом третьего элемента И, второй вход которого соединен с выходом первого счетчика и первым информационным входом сумматора, второй информацион,ный вход .которого подключен к выходуфф пятого элемента И вход "Сброс" сумма тора связан с первым выходом узла синхронизации и с первым входом второго элемента ИЛИ, второй вход которого соединен с первым выходом схемы сравнения, выход второго элемента ИЛИ связан с входом "Сброс третьего счетчика, выход которогс подключен к второму входу пятого элемента И, а счетным входом - к третьему выходу схемы сравнения и третьему входу первого элемента ИЛИ,На чертеже предстевпена блок-схемаустройства. Устройство содержит кольцевые регистры 1, 1, , 1, сдвига, элементы И 2,-2, 3,-3, 4,-4 5-9, эпементы 2 ИИЛИ 101-10элементы (И) И-ИЛИ 11 и 12, дешифрвторы 13 и 14, регистры 15-17, счетчики 18-20, сумматор 21, элементы ИЛИ 22 и 23, схему 24 сравнения, узел 25 синхронизации, элемент 26 дешифрации числа, Кольцевые регистры 1 -1 сдвига яа и разрядов,гпредназначенные дпя записи и хранения ранжируемых чисел (К разрядов с 1 по К), признаков (адресов) чисел (Р-разрядов с К+1 по с) ), максимального ран- га числа (разряды с ф+1 по ), минимального ранга чиспа (разряды с 8+1 по ю), связаны следующим образом: цер вый регистр по входу подключен к вы- . ходу элемента И 2, по выходу связан с вторым входом элемента (Ь) И-ИЛИ 11; регистры 1;1, связаны по входу, с выходом соответствующего элементе 2 И-ИЛИ 10 у 10 ь 1, а цо выходу с соответствующими четными с четвертого по 2 (И)-ый входами эпементов (И-ХГЙ-. ИЛИ 11 и нечетными с первого по (2 И)-ый входами элемента (И) И-ИЛИ 12; регистр 1 по входу подключен к выходу элемента И 2 а яо выходу - к (2)-3)-му входу элемента (и) ИИЛИ 12. Кроме того, разряды с (ф+1) по г регистров 1,-1 подкпючены к вы ходам соответствующих элементов И 4- 4 и, а разряды с (1+1) по ю- к выходам элементов И 3-3 Схема 24 сравяеяия сравнивает два числа А и В путем вычитанич (А-В) и работает в двух режимахф- выбор максимального чиспа; Я - выбор минимального числа. В зависимости от режима работы устройства в . схеме 24 сравнения сравниваются рвнжируемые числа (режим ранжирования и упорядочения по рангам) ипи признаки (адреса) чисел (режим упорядочения по признакам (адресам). По входам схема 24 сравнения подключена к выходам элементов (И) И-ИЛИ 11 и 12, которые также связаны с первыми входами элементов И 5 и 6 соответственно. Первый выход схемы 24 сравнении, сигнал на котором появляется в случае АЪВ - дпя Т режима, А В - дпя ц режима, подключен к первому входу элемента ИЛИ 23, выход которого связан со счетным входом счетчика 19, Второй выход схемы 24 сравнения, сигнал нв котором появляется в случае А=В, подключен к второму входу элемента ИЛИ 23 и счетному входу счетчика 20 для подсчета количества рав 7 9324 ных чисеп, выход которого связан с первым входом элемента И 9, в выход поспеднего соединен с входом регистра 17 и первым входом сумматора 21, выход которого подключен к первым входам эле- % ментов И 4 -411 и через элемент 26 дешифрации числа к третьим входам эпементов И Эи 4 Инверсный выход регистра 17 подключен к первому входу эпемента И 7, выход которого связан с вхо дом регистра 16 по выходу подключенного к первым входам эпемента И 3 -31Третий выход схемы 24 сравнения, сигнал на котором появляется в спучае АВ для 1 режима; А 7 В - для Й режима, 1 связан с вторыми входами элементов И, 5 и 6, входом узла 25 синхронизации и первым входом элемента ИЛИ 22, выход которого подключен к входу Сброс счетчика 20. Счетчик 18 на (1-1) дпя пы 26 счета адреса чиспв А по входу подключен к выходу узла 25 синхронизации, а по выходу связан с установочным входом счетчика 19 на И первонвчапьное состояние которого соответствует значению 2 Э счетчика 18 с добавлением +1, вторыми вхоаами элемента И 7 и сумматора 21, входом дешифратора 13, выходы которого соединены соответственно с нечетными с первого по (2 И-Э)-ый входами эпемента Эй (И) И-ИЛИ 11, первыми входами элементов И 2,1 и 2 И-ИЛИ 10,-1011,1 третьими входами элементов И 3-3 ,41- 4, тВыход счетчика 19 подключен к входу дешифратора 14, выходы которого свя. эаны с соответствующими четными с вто. рого по 2 (И-ый входами эпемеитв (И). И-ИЛИ 12, четвертыми входами элементов 2 И-ИЛИ 10-10,1 и первым входом эпемента И 2 . Первый выход ае шифратора 14 подключен также к входу узла 25 синхронизации и первому входу элемента И 8, выхоа которого связан с вторыми входами элементов И Э -Э 1, 4-4. Регистр 15 - кольцевой регистр43. сдвига для перестановки двух чисеп - подключен следующим образом: вход первого числа - к выходу элемента И 5, в выход к вторым входам эпементов И 2 и 2 И-ИЛИ 101-1011 .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 " (соответственно счетчик 1 9 в состояние "2"). Первоначальное состояние регистра 17 0", следовательно, в регистр 16 через эпемент И 7 запишется число, находящееся в счетчике 18, т.е. "1", Числа, нолученные в счетчиках 18 и 19, дешифрируются, и на одной из выходных шин дешифраторов 13 и 14 соответственно появляется сигнал, т.е. открываются по одному иэ входов эпементы И 2 3,1 41эпемент 2 И-ИЛИ 10 элементы (И) И-ИЛИ 11 и 12, Через эпемент Ь) И-ИЛИ 11 в схему 24 сравнения поступает число А с регистра 1, в через элемент (И) И-ИЛИ 12 чйсло В с регистра 1, Поспе сравнения чисеп возможны спеауюшие варианты работы устройства: если АВ, то с первого выхода схемы 24 сравнения через элемент ИЛИ 23 сигнал поступает в счетчик 19 и переключает его в состояние 3", работа устройства продопжвется; если А=В, то со второго выхода схемы 24 сравнения через элемент ИЛИ 23 сигнал поступает в счетчик 19 и переключает его в состояние "3", одновременно этот же сигнал подается нв счетный вход счетчика 20 и увепичиввют его значение нв 1 , работа устрой ства продолжается; если АВ, то появляется сигнвп на третьем выходе схемы 24 сравнения, открывающий по одному входу элементы И 5 и 6, сбрасываюший счетчик 20 в состояние "0" через элемент ИЛИ 22 и одновременно поступающий в узел синхронизации 25, который по этому сигналу вырабатывает сигнал, разрешающий сдвиг в регистре 15 и работу кольцевых регистров 1 -11, сдвига в режиме записи. Числа А и В через эпементы И 5 и 6 соответственно поступают в регистр 15, сдвигаются и записываются в соответствующие кольцевые регистры 1,1 и 1 сдвига, через эпементыИ 2, и 2 И-ИЛИ 10, т.е. А - в Регистр 1 да В - в регистр 1 После записи9 9324 .чисел по сигналам от узла 25 синхронизации счетчик 19 переключается в состояние "3", в кольцевые регистры.1 -1сдвига в режим считывания, и работа устройства продолжается. Как только в счег- %чике 19 будет число И, по сигналу с выхода дешифрвтора 14 через интервал времени, необходимый аля сравнения д-горанжнруемого числа, узел 25 синхронизации вырабатывает сигнал, разрешающийзапись рангов чисел в разряды с (ф+1)по И 1 регистров 1 -1 и, т.е, открывающий элементы И 3-3 и, 4,1-4 и, 8 и 9. Число, находящееся в счетчике 20, переписывается в регистр 17 и в сумматор 21, 1 фгае складывается с числом, нахоаящимся в счетчике 18, Число, находящееся в регистре 16, записывается в разряды с (И+1) по Ф регистра 1 через элемент И Э и соответствует минимальному раи- щфгу рвнжируемого числа, а число, находящееся в сумматоре 21 - через элемент И 4 в разряды с (+1) по р регистра 11 и соответствует максимальному рангу, В регистр 16 через элемент И 7 эапи- уз сыввется число, находящееся в счетчике 18, лишь в том случае, когда в регистре 17 записан "0". Через интервал времени, необходимый для записи рангов числа, в узле 25 синхронизации вырабатывается сигнал, переключающий счетчик 18 в состояние "2, соответственно счетчик 19 в состояние 3. Работа устройства продолжается до полного ранжирования чисел яих упорядочения в зависимости33 от ранга. 3 режим - режим упорядочения по признакам (адресам). Предполагается, что в режимев регистрах 1-1 И уже записаны ранжируемые числа (К-разрядов), признаки чисел (Р-разрядов) в ранги чисел. Упорядочение чисел вместе с рангами проводится по признакам (адресам) чисел, записанным в разряды с (К+1) по Ч, каждого регистра, Сравнение в схеме 24 сравнения проводится только43 по значениям укаэанных Р-разрядов. В остальном работа устройства по упорядочению чисел вместе с рангами аналогична работе устройства в режиме 1.1Технико-экономический эффект изобре- фз теиия заключается в том, что за счет введения двух регистров, счетчика, сумматора, элементов И, ИЛИ расширяются функции устройства. При относительной простоте технической реализапии нв стан- И дартных элементах цифровой вычислитель-ной техники предлагаемое устройство поз воияет присваивать ранги множеству.чисел,10в также производить упорядочение Чисел в соответствии с значением ранга, или упорядочивать числа вместе с присвоенными им рангами по ранее присвоенным признакам (адресам), Автоматическое выполнение этих функпнй с помощью предлагаемого устройства приводит к сокрашению времени, повышает верность результатов и обеспечивает дальнейшую автоматизацию всего процесса обработки статистической информации,ф о р м у л в изобретенияУстройство для упорядочения чисел, содержащее И кольцевых сдвнгаюшнх регистров, элементы (И) И-ИЛИ, два входных элемента И (И) входнык элемента 2 И-ИЛИ, дешифраторы, счетчики, элементы И, ИЛИ, регистр, узел синхронизации, первый выход которого соединен с установочными вкодами кольцевых регистров, с управляющим входом схемы сравнения и с входом первого счетчика, выходы которого подключены к входам первого аешифратора и установочным входам второго счетчика, выходы которого соединены с входами второго дешифрвтора, каждый 1-й выход первого дешифратора, где 1= 1, 2, (И), соединен с 1-м входом первого элемента (И) И-ИЛИ, первый выход первого дешифратора соединен с первым входом первого входного элемента И, выход которого подключен к входу первого кольцевого сдвигающего регистра, в каждый (+1)-й выход первого дещифрвтора, где= 1, 2, , (2), соединен с первым входом ф-го входного элемента 2 И-ИЛИ, выхоа вждого иэ которых подключен к входу (+1)-го кольцевого сдвигавшего регистра, выход каждого 1-го кольцевого сдвигвющего регистра соединен с (1+тих)-мвходом первого элемента (И) И-ИЛИ, выход которого подключен к первому информационному входу схемы сравнения и к первому входу первого элемента И, выкод которого соединен с первым установочным входом регистра, первый выход которого подключен к вторым входам первого входного элемента И и 1, 2, , (И)-го входных элементов 2 И-ИЛИ, каждый 1-й выход .второго дешифратора соединен с 1-м входом второго элемента (и) И-ИЛИ, каждый у-й выход второго дешифрвтора подключен к третьему входу )-го входного эиементв 2 И-ИЛИ (И)-й выход второго дешифраторв сое 932динен с первым входом второго входного элемента И, выход которого соединен с входом И -го кольцевого сдвигаюшего регистра, выход которого подключен к И-му входу второго управляющего элемен та (И) И-ИЛИ, выход каждого (+1)-га кольцевого сдвигаюшего регистра соединен с +И)-м входом второго элемента (И) И-ИЛИ, выход которого подключен к второму информационному входу схемы 0 сравнения и к первому входу второго элемента И, выход которого соединен с вторым установочным входом регистра, вто рой выход которого подключен к четвертым входам 1 у 2 уау (Ищ 2)-го ВхОдных ф элементов 2 И-ИЛИ и к второму входу второго входного элемента И, первый выход схемы сравнения соединен с-вторыми входами элементов И и с первым управляющим входом узла синхронизации, второй выход которого подкшочен к информационному входу регистра и к вторым установочным входам кольцевых сдвигаюших регистров, второй выход схемы срав нения соединен с первйм входом первого элемента ИЛИ, второй вход которого подключен к третьему выходу узла синхронизации, а выход - к информационному входу второго счетчика, о т л и ч а ю ш ее с я тем, что, с целью расширения функциональных возможностей за счет ранжиро вания питеровых данных и их упорядочения в зависимости от ранга или признака (адреса) числа, в него дополнительно введены регистры, счетчик, сумматор, элемент дешифрации числа И,элементы И, ИЛИ, Зф две группы м разрешающих элементов И,4каждый первый вход 1-го разрешающею элемента И двух групп подключен к 1-му выходу первога дешифратора, первые входы двух и-х разрешающих элементов И под 4 циочены к выходу элемента дешифрации числа И, вход которого подключен к выходу сумматора и к вторым входам -х разрешающих элементов И первой груп.гуг 488 12пы, где 6 = 1, 2, , , выход каждого 8-го разрешающего элемента И первой группы подключен к входам разрядов 0-гокольцевого сдвигвюшего регистра, вторые входы 8-х разрешающих элементов И второй группы подкшочены к выходу второго регистра, вход которого связан с выходом третьего элемента И, а выход каждого -го разрешающего элемента И второй группы соединен с входами разрядов6-го кольцевого сдвигаюшего регистра, третьи входы разрешающих элементов И двух групп подключены к выходу четвертого элемента И, первый вход которого связан с (М)-м выходом второго дешифратора и вторым управляющим входом узла синхронизации, а второй вход - с четвертым выходом узла синхронизации и первым входом пятого элемента И, выход которого подкшочен к входу третьего регистра, выход которого соединен с первым входом третьего элемента И, второй вход которого соединен с выходом первого счетчика и первым информациойным входом сумматора, второй информационный вход которого подключен к выходу пятого элемента И, вход "Сброс сумматора связан с первым выходом узла синхрони запии и с первым входом второго элемента ИЛИ, второй вход которого соединен с первым выходом схемы сравнения, выход второго элемента ИЛИ связан с входом "Сброс третьего счетчика, выход которого подключен к второму входу пятого элемента И, а счетным входом - к третьему выходу схемы сравнения и третьему входу первого элемента ИЛИ,Источники информации,принятые во внимание при экспертизе 1, Патент США В 3829664,ка З Об Р 7/02, опублик. 1974,2, Авторское свидетельство СССР по заявке % 2814319/1824, д кл. О 06 Р 7/06, 1979 (прототип).