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

(54) УСТРОЙСТВО ДЛЯ УПОРЯДОЧЕНИЯ ЧИСЕЛ

Изобретение относится к аьтомачпке и вычисли те пь ной технике и может быть использовано при реализации технических средств ЭВМ и создании устройств обработки статистической информации. Известно устройство для ранжирове- ния чисеп, содержащее регистры сдвига, счетчики, схему сравнения, схему pieBepсивного ранжирования, вычитающую , элементы ИЛИ, И, временную схему, устройство управления и выходное уст ройства с соответствующими связями,обес печивакмпими его работоспособность ll. Недостаток этого устройства - огра.нцченные функциональные возможности; позволяет только присваивать ранги без упорядочения по рангамм. Наиболее близким к предлагаемому является устройство для упорядочения чисеп, содержащее И кольцевых регистров, управляющие элементы И-ИЛИ, вход ные элементы И-ИЛИ, дешифраторы, счет чики, элементы И, ИЛИ, регистр, схему сравнения, узеп синхронизации, первый выход которого соединен с установочными входами кольцевых регистров, с управляющим входом схемь5 сравнения и с входом первого счетчика, выходы которого подключены к входам первого дешифратора и установочным входам второго счетчика, выходы KOTOpoio соединены с входами второго дешн чратора, каждый {-ый выход первого дешифраторе, где , 2, ..., (и-1), соединен с - ым входом первого управляющего элемента И-ИЛИ и с первым входом i -го входного элемента И-ИЛИ, выход каждого il-ro входного эпемекта И-ИЛИ подключен к входу i-ro кольцевого регистра, выход каждого i-ro кольцевого регистра соединен с (1 Я 1 )-ь:м входом первого управляющего элемента И-ИЛИ, выход которого под к гаечек к первому информационному входу схемы сравнения и, к первому входу первого элемента И, выхса которого соединен с первым установочным входом регистра, первый выход которого подключен к вторым входам 1, 2, ..,, (И-1) входных элементов И-ИЛИ, каждый -ый выход второго деши( ра соединен с i-ым входом второго управляющего элемента И-ИЛИ, каждый j-ый выход второго дешифратора, где j 1, 2 (И-2), подключен к третьим входам (j+l)-ro входного элемента И-ИЛИ, (и-1) выход второго дешифратора соединен с первым входом И -го .входного элемента И-ИЛИ, выход котоiporo соединен с входом кольцевого регистра, выход которого подключен к и-му входу второго управлякииего эле мента И-ИЛИ, выход каждого К-го кольцевого регистра, где К-2, ,.., (и-1) сое динен с () входом второго управляющегй элемента И-ИЛИ, выход .которого подключен к второму информационному входу схемы сравнения и к первому входу второго элемента И, выход которого соединен с вторым установочным входом регистра, второй выход которого под ключен к четвертым входам 2, 3, ..., (И-1) входных эпементсФ И-ИЛИ и к второму входу И -го элемента И-ИЛИ, первый выход схемы сравнения соединен с вторыми вхсюами элементов Ии с первым управляющим входом уэпа синхронизации, второй выход которого подключён к икформационному входу регистра и к втсфым установочным входам кольцеш 1х регистров, второй выход схемы сравнения соединен с первым входом элемента ИЛИ второй вход которого подключен к третьему выходу узла синхронизации, а выход - к информационному входу второго счетчика, выход которого соединен с вто рым управляющим входом узла синхронизации 2. Недостатком устройства являются ограниченные функциональные возможности, так как оно позволяет лишь упорядочить цифровые данные по возрастанию (убыванию). Цель изобретения - расширение функ иионапьных возможностей устройства за счет ранжирования цифровых данных и их упорядочения в зависимости от ранга или признака (адреса) числа. Поставленная цель достигается тем, что в устройство для упорядочения чисеп содержащее И кольцевых сдвигающих регистров, элементы (У1-1) И-ИЛИ, два входных элемента И, (и-2) входных элемента 2И-ИЛИ, дешифраторы, счетчики, элементы И, ИЛИ, регистр, узел синхронизации, первый выход которого соединен с установочными входами кольцевых регистров,, с управляющим входом схемы сравнения и с входом первого счетчика, выходы которого подключены к входам первого дешифратора и установочным входам второго счетчика, выходы которого соединены с входами второго дешифратора, каждый i-ый выход первого дешифратора, где , 2, ..., (И-1), соединен с -i-biM входом первого элемента (vi-1) ИИЛИ, первый выход первого дешифратора соединен с перкз1м входом первого входного элемента И, выход которого подключен к входу первого кольцевого сдвигаюшего регистра, а каждый ( + 1 -ый выход первого дешифратора, где j.l, 2, .,., (Уь2), соединен с первым входом -го входного элемента 2И-44ЛИ, выход каждого из которых подключен к входу (j+l)-ro кольцевого сдвигающего регистра, выход каждого -f-ro кольцевого сдвигающего регистра соединен с (1+И-1)-ым входом первого элемента (w-1) И-ИЛИ, выход которого подключен к первоь информационному входу схемы сравнения я к первсмиу входу первого эцемента И, выход которого соединен с первым установочным входом регистра, первый выход которого подключен к вторым входам первого входного элемента И и 1, 2 (И-2)-го входных элементов 2И-ИЛИ, каждый 1 -ый второго дешифратора соединен с i-ым входом второго элемента &1-1) И-ИЛИ, каждый -ый выход второго дешифратора подключен к третьему входу j-ro входного элемента 2И-ИЛИ, (И-1 )-ый выход второго дешифратора соединен с первым вхснюм второго входного элемента И, выход которого соединен с входом й-го кольцевого сдвигающего регистра, выход которого подключен к И-му входу второго управляк щего элемента (м-1) И-ИЛИ, выход каждого (J+1 )-го кольцевого сдвигающего регистра соединен с (}Ч-И)-ым входом второго элементами-) И-ИЛИ, выход которого подключен к второму информационному входу схемы сравнения и к первому входу второго элементе И, выход которого соединен с вторым установочным входом регистра, второй Шз1ход которого подключен к четвертым входам 1, 2, .,., (и-2)-го входных элементов 2И-ИЛИ и к второму входу второго входного элемента И, первый &1ход схемы сравнения соеДинен с вторыми входами элементов И и с первым управляющим входом узла син.хронизации, второй выход которого под ключей к информационному входу регист59pa и к вторым установочным входам копь цевых сдвигающих регистров, второй вьГход схемы сравнения соединен с первым входом первого элемента ИЛИ, второй вход которого подклиочен к третьему выходу узпа синхронизации, а выход - к информационному входу второго счетчика, дополнительно введены регистры, счетчик сумматор, элемент дешифрации числа Н элементы И, ИЛИ, две группы И разрешающих элементов И, каждый первый вход 4-го разрешающего элемента И двух груп подключен к 1-му выходу первого дешифратора, первые входы двух и-ых разреша юших элементов И подключены к выходу элемента дешифрации числа И, вход которого подключен к выходу сумматора и к вторым входам разрешающих элементов И первой группы, где Р«1, 2, ,.., и, выход каждого 6-го разрешаюшего элемента И первой группы подключен к входам разрядов С-го кольцевого сдви- Тающего регистра, вторые входы р -ых разрешающих элементов И второй подключены к выходу второго регистра, вход которого связан с выходом третьего элемента И, а выход каждого С-го разрешающего элемента И второй груш1Ы соединен с входами разрядов кольцевого сдвигающего регистра, третьи входы разрешающих элементов И двух групп подключены к выходу четвертого элемента И, первый вход которого связан с (И-1)-ьшг иыходом второго дешифратора и вторым управпЕяющим входом узла синхронизации, а второй вход - с четвертым выходом узла синхронизации и первым входом пятого эпемента И, шлход которого подключен к входу третьего регистра, выхсш которого соединен с пер- вым входом третьего эпемента И, второй вход которого соединен с выходом первого счетчика и первым информационным входом сумматора, второй информаиион.ный вход тсоторого подключен к выходу пятого элемента Ид вход Сброс сумма тора связан с первым ззыходом узла синхронизации и с первым входом второго элемента ИЛИ, второй вход которого соединен с первым выходом схемы сравнения, выход второго элемента ИЛИ связан с входом Сброс третьего счетчика, вы ход которого подключен к второму входу пятого элемента И, а счетным входом - к третьему выходу схемы сравнения и третьему входу первого элемента ИЛИ. На чертеже представлена блок-схема устройства. 886 Устройство содержит копьцевые регис-гры 1, i, ..., ly, сдвига, элементы И , , -9, элементы 2ИИЛИ элементы (И-1) И-ИЛИ 11 и 12, дешифратор 13 и 14, регистры 15-17, счетчики 18-20, сумматор 21, элементы ИЛИ 22 и 23, схему 24 сравнения, узел 25 синхронизации, эпемент 26 дешифрации числа. Кольцевые регистры l.-ly, сдвига на и разрядов, предназначенные для записи и хранения ранжируемых чисел (К разрядов с 1 по К), признаков (адресов) чисел (Р-раэрядов с К+1 по t), максимального ранга числа (разряды с +1 по ), минимального ранга числа (разряды с fl+1 по т), связаны следующим образом: первый регистр по входу подключен к вы- . ходу элемента И 2, по выходу связан с вторым входом элемента (h-1) И-ИЛИ 11; регистры lj,-ly,y( связаны по входу/ с выходотл соответствующего эпемента 2И-ИЛИ lOi-lOn-l, а по выходу с соответствуюшими четными с четвертогопо 2()-ый входами эпек ентов (H-IfHИЛИ 11 и нечетными с первого по (2Vi5)-ый входами элемента (И-1) И-ИЛИ 12; регистр Ij по входу подключен к выходу элемента И 2 а по выхсяу - к ()-му входу элемента (и-1) ИИЛИ 12. Кроме того, разряды с () по г регистров l;|-lj подключены к выходам соответствующих элементов И 4. 4V1, а разряды с (v+l) по ш- к шлхоаам элементов И 3 З Схема 24 сравнения сравнивает два числа А и В путем вычитания (А-В) а работает в авух режвмах: I - выбор максимального числа; 1 - выбор миттмального числа. В зависимости от режима работы устройства в схеме 24 сравнения сравниваются ранжируемые числа (режим ранжирования и упорядочения по рангам) или признаки (адреса) чисел (режим упорядочения по признакам (адресам). По входам схема 24 сравнения подключена к к 1ходам элементов (И-1) И-ИЛИ 11 и 12, которые также связаны с первыми входами элементов И 5 и 6 соответственно. Первый выход схемы 24 сравнения, сигнал на котором появляется в случае - для режима, А В - для ц режима, подключен к первому входу элемента ИЛИ 23, выход которого связан со счетным входом счетчика 19. Второй выход схемы 24 сравнения, сигнал на котором появляется в случае , подключен к второму входу элемента ИЛИ 23 и счетному входу счетчика 2О для подсчета количества рав-ных чисел, выход которого связан с первым входом элемента И 9, а выход поспеднего соединен с входом регистра 17 и первым входом сумматора 21, выход которого подключен к первым входам элементов И 4-4 и через элемент 26 дешифрации числа к третьим входам элемен4y, Инверсный выход регисттов И 3j и ра 17 подключен к первому входу элемента И 7, выход которого связан с входом регистра 16, по выходу подключенно го к первы входам элемента И 3. -3,. Третий выход схемы 24 сравнения, сигнал на котором появляется в случае для I режима; А В - для 1 режима, связан с вторыми входами элементов И ; 5 и 6, входом узла 25 синхронизации и первым входом элемента ИЛИ 22, выход которого подключен к входу Сброс счет чика 20. Счетчик 18 на (V)-l) для подсчета адреса числа А по входу подключай к к 1ходу узла 25 синхронизации, а по выходу связан с установочным входом счетчика 19 на И, первоначальное состояние которого соответствует значению счетчика 18 с добавлением +1, вторыми вх М1ами элемента И 7 и сумматора 21, входом дешифратора 13, выходы которого соединены соответственно с нечетными с первого по ()-41й входами элемента () И-ИЛИ 11, первыми входами элементов И 2 и 2И-ИЛИ iCVL-lOy.третьими входами элементов И ,. Выход счетчика 19 подключен к входу дешифратора 14, выходы которого связаны с соответствующими четными с второго по 2 {Wl --ыЛ входами элемента (W-1). И-ИЛИ 12, четвертыми входами элементов 2И-ИЛИ .и первым входом элемента И 2. Первый выход дешифратора 14 подключен также к входу узла 25 синхронизации и первому входу элемента И 8, выход которого связан с вторыми входами элементов И З.-Зь . Регистр 15 - кольцевой регистр сдвига для перестановки двух чисел - под ключен следующим образом: вход перво го числа - к выходу элемента И 5, а вы ;ход к вторым входам элементов И 2 и 2И-ИЛИ - 1Оя-1О, вход второго числа к выходу элемента И 6, а выход - к вто рому входу элемента И 2 и третьим входам элементов 2И-ИЛИ ..Узе 25 синхронизации связан с регистрами l.-l., 15, схемой 24 сравнения, сумматором 21, счетчиком 18, элементами ИЛИ 22 и 23, вторыми входами элемен тов И 8, 9 и предназначен для управления работой устройства. 93 88 Устройство работает в двух режимах. I режим - режим ранжирования и упорядочения по рангам. В этом режиме устройство работает следующим образом. По стартовому импупьсу 27 узел 25 синхронизации вырабатывает сигнал, который задает режим выбора максимального или минимального ранжируемого числа в схеме 24 сравнения, разрешает работу кольцевых регистров сдвига 1 -1 в режиме считывания, сбрасывает счетчик 20 (через элемент ИЛИ 22) и сумматор 21 в О и устанавливает счетчик 18 в состояние (соответствеиир счетчик 19 в состояние 2). Первоначальное состояние регистра 17 О, следовательно, в регистр 16 через элемент И 7 запишется число, находящееся в счетчике 18, т.е. 1. Числа, полученные в счетчиках 18 и 19, дещн4фируются, и на одной из выходных шин дешифраторов 13 и 14 соответственно появляется сигнал, т.е. отк{Я 1ваются по оаному из входов элеменТЫ И 2, 3, 4f, элемент 2И-ИЛИ 10 элементы (и-) И-ИЛИ 11 и 12. Через элемент (и-1) И-ИЛИ 11 в схему 24 сравнения поступает число А с регистра 1, а через элемент (И-1) И-ИЛИ 12 число В с регистра 1. После сравнения чисел возможны следующие варианты работы устройства: если А В, то с первого выхода схемы 24 сравнения через элемент ИЛИ 23 сигнал поступает в счетчик 19 и переключает его в состояние 3, работа устройства продолжается; если , то со второго выхода схемы 24 сравнения через элемент ИЛИ 23 сигнал поступает в счетчик 19 и переключает его в состояние 3, одновременно этот же сигнал подается на счетный вход счетчика 2О и увеличивают его значение на , работа устройства продолжается; если А В, то появляется сигнал на третьем выходе схемы 24 сравнения, открывающий по одному входу элементы И 5 и 6, сбрасывающий счетчнк 2О в состояние О через элемент ИЛИ 22 и одновременно поступак щнй в узел синхронизации 25, который по этому сигналу вырабатывает сигнал. разрешающий сдвиг в регистре 15 и работу кольцевых регистров 1. -1 сдвига в режиме записи. Числа А и В через элементы И 5 и 6 соответственно поступают в регистр 15, сдвигаются и записываются в соответствующие кольцевые регистры 1 и 12.сдвига, через элементы И 2 и 2И-ИЛИ 1б,2, т.е. А - в регистр Ijj а В - в регистр 1. После записи

чиеел по сигналам от уапа 25 синхронизации счетчик 19 переключается в состояние 3, а кольцевые регистр 1.-1, сдвига в режим считывания, и работа устройства продолжается. Как только в счетчике 19 будет чиспо И, по сигналу с выхода дешифратора 14 через интервал времени, необходимый для сравнения -и-го ранжируемого числа, узел 25 синхронизации вырабатывает сигнал, разрешающий запись рангов чисел в разряды с (J,+1) по Vn регистров , т.е. открывающий элементы И ,, . 8 и 9. Число, находящееся в счетчике 2О, переписывается в регистр 17 и в сумматор 21, где складывается с числом, находящимся в счетчике 18. Число, находящееся в регистре 16, записывается в разряды с ) по W регистра 1 через элемент И 3 и соответствует минимальному ранГУ ранжируемого числа, а число, находящееся в сумматоре 21 - через элемент И 4 в разряды с () по г регистра 1 и соответствует максимальному рангу. В регистр 16 через элемент И 7 запи- сывается число, находящееся в счетчике 18, лишь в том случае, когда в регистре 17 записан О. Через интервал времени, необходимый для записи рангов числа, в узле 25 синхронизации вырабатывается сигнал, переключающий счетчик 18 в состояние 2, соответственно счетчик 19 в состояние 3. Работа устройства продолжается до полного ранжирования чисел я их упорядочения в зависимости от ранга. Т режим - режим упорядоче1гая по признакам (адресам). Предполага ется, что в режиме Ц в регистрах Iji-lyi уже записаны ранжируемые числа (К-раэрядов), признаки чисел (Р-разрядов) в ранги чисел. Упорядочение чисел вместе с рангами проводится по признакам (адресам) чисел, записанным в разряды с (К+1) по (Ц, каждого регистра. Сравнение в схеме 24 сравнения проводится только по значениям указанных Р-разрядов. В остальном работа устройства по упорядочению чисел вместе с рангами анаПогична работе устройства в режиме 1. I

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

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

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

Устройство для упорядочения чисел, содержащее И кольцевь1х сдвигающих регистров, элементы (И-1) И-ИЛИ, два входных элемента И,(и-2) входных элемента 2И-ИЛИ, дешифраторы, счетчики, элементы И, ИЛИ, регистр, узел синхронизации, первый выход которого соединен с установочными входами кольцевых регистров, с управляющим входом схемы :сравнения и с входом первого счетчика, I выходы которого подключены к входам первого дешифратора и установочным входам второго счетчика, выходы которого соединены с входами второго дешифратора, каждый 1-й выход первого дешифратора, где 1- 1, 2, ..., (и-1), соединен с i-M входом первого элемента (И-1) И-ИЛИ, первый ш,1ход первого дешифратора соединен с первым входом первого входного элемента И, выход которого подключен к входу первого кольцевого сдвигаюшего регистра, а каждый (+1)-й выход первого дешифратора, где 1, 2, ,.., (И-2), соединен с первым входом j-ro входного элемента 2И-ИЛИ, выход каждого из которых подключен к входу (И)-го кольцевого сдвигающего рдагистра, выход каждого 1-го когшцевого сдвигающего регистра соединен с (i+w-l )-м входом первого элемента (И-1) И-ИЛИ, выход которюго подключен к первому информационному входу схемы сравнения и к первому входу первого элемента И, выход которого соединен с первым установочным входом регистра, первый выход которого подключен к вторым входам первого входного элемента И и 1, 2, ..., ()1-2)-го входных элементов 2И-ИЛИ, каждый i-й выход второго дешифратора соединен с 1 -м входом второго элемента (и-1) И-ИЛИ, каждый j-и выход второго дешифратор подключен к третьему входу j-ro входного элемента 2И-ИЛИ (И-1)-й выход второго деил1()фатора соединен с первым входом второго входного элемента И, выход которого соединен с входом И -го кольцевого сдвигающего регистра, выход которого подкточен к W-My входу второго управляющего элемента (И-1) И-ИЛИ, выход каждого (.j+l)-ro кольцевого сдвигающего регистра соединен с (;)+И)-м входом второго элемента (И-1) И-ИЛИ, выход которого подключен к второму информационному входу схемы сравнения и к первому входу второго элемента И, выход которого соединен с вторым установочным входом регистра, второй выход которого подключен к четвертым входам 1, 2, .,,, (И-2)-го входных элементов 2И-ИЛИ и к второму входу второго входного элемента И, первый вы ход схемы сравнения соединен с вторыми входами элементов И и с первым управЛЧД5ШИМ входом уэпа синхронизации, второй выход которого подключен к информационному входу регистра и к вторым установочным -входам кольцевых сдвигающих регистров, второй выход схемы сравнения соединен с первУм входом первого элемента ИЛИ, второй вход которого подключен к третьему выходу узла синхронизации, а выход - к информационному входу второго счетчика, отличаюш е,е с я тем, что, с целью расширения функшюнальных возможностей за счет равжирования ци| ровых данных и их упорядочения в зависимости от ранга или признака (адреса) числа, в него дополнительно введены регистры, счетчик, сумматор, элемент дешифрации числа И, элементы И, ИЛИ, две группы И разрешающих элементов И, каждый первый вход -t-ro разрешающего элемента И двух гигпп подкшочен к i-му выходу первого дешифратс а. первые входы И-х разрешающих элементов И нодлшочены к выходу элемента дешифрации числа И, вход которого подключен к Еа 1коду сумматора и «к вторым входам S-X разрешающих элементов И первой груп 9 8812 пы, где 6-1, 2, ..., V), выход каждого -го раз.рещаюшего элемента И первой группы подключен к входам разрядов f-ro кольцевого сдвигающего регистра, вторые входы С-х разрешающих элементов И второй группы под к точены к выходу второго регистра, вход которого связан с выходом третьего элемента И, а выход каждого 6 -го раз{зещающ(его элемента И второй группы соединен с входами {разрядов 6-го кольцевого сдвигаврщего регистра, третьи входы раарешаюцдах элементов И двух групп подключены к выходу четвертого эиемента И, первый вход которого связан с (И-1)-м выходом второго дешифратора и вторым управляющим входом узла синхронизации, а второй вход - с четвертым выходом узла синхронизации и первым входом пятого элемента И, выход которого подкшочен к входу третьего регистра, выход которого соединен с первым входом третьего элемента И, второй вход ктарого соеаинен с выходом первого счетчика и первым информаш1онш 1м входом сумматора, второй инфорк1ационный вход которого подключен к выходу пятого элемента И, вход Сброс сумматора связан с первым 1№ходом узла синхронизахши а с входом второго эпемента И/В1, вто|юй вход которого соединен с первым шлходом схемы сравнения, выход второго элемента ИЛИ связан с входом СОрос третьего счетчика, выход которого подкшочеа к второму входу пятого эяемевта И, а счетным входом - к третьек г №1Ходу схемы сравнения и третьему гюрвого элемента ИЛИ, Источники информации, 1финя-гые во внимание пра экспертизе 1.Патент США Мз 3829664, кли G Об F 7/О2, опубгак. 1974. 2.Авторское свидетельство СССР по заявке М 2814319/18-24,ci кя. G Об F 7/О6, 1979 (прототип).