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

Изобретение относится-к автоматике и вычислительной технике и может быть использовано при реализации технических средгтв ЭВМ и создании устройств обработки статистической информации. Известно устройство для определения минимального числа, содержащее два двоичных счетчика, элементы И, ИЛИ, триггеры и узел равнозначности 1 . Недостаток этого устройства - огра ниченные функциональные возможности: определяет только минимальное из последовательности следующих одно за другим чисел и запоминает последнее текущее значение. Наиболее близким к предлагаемому по техническому решению является устройство для сортировки чисел, содержа щее п кольцевых регистров сдвига, входы которых соединены между собой и подключены к входной шине устройства, прямые выхода всех кольцевых регистров сдвига соединень со входами первой схемы ИЛИ и с одним из входов соответствующей схемы равнозначности, а инверсные выходы - со входами второй схемы ИЛИ, выходы схем ИЛИ подключены ко.входам схемы И, второй вход каждой из схем равнозначности соединен с шиной управления, а их управляющие входы подключены к выходу схемы И, выходы схем равнозначности связаны со входами сброса соответствующих кольцевых регистров сдвига 2. Недостаток устройства заключается в том, что оно имеет ограниченные функциональные возможности, так как позволяет определять только экстремальное число из п сравниваеьалх чисел с потерей информации о значениях остальных чисел. Цель изобретения - расширение функциональных возможностей устройства за счет упорядочения чисел как по возрастанию, так и по убыванию. Поставленная цель достигается тем, что в устройстве для сортировки чисел.

содержащем n кольцевых регистров, управляющие элементы И-ИПИ, входные элементы И-ШШ, дешифраторы, счетчики, элементы И, ИЛИ, регистр, узел синхронизации, первый выход которого соединен с установочными входами кольцевых регистров, с управляющим входом cxeNOii сравнения и со входом первого счетчика, выходы которого подключены ко входам первого дешифратора и уста- ю новочшлм входам второго счетчика, выходы которого соединены со входами второго дешифратора, каждый i-ый выход первого дешифратора, где i i,2,...(n -l) соединен с i-ым вхо- 15

ом первого управляющего элемента | -ИЛИ и с первым входом i-ro входного элемента И-ИЛИ, выход каждого i-ro входного элемента И-ИЛИ подключен Ко входу I-го кольцевого регистра, выход 20 каждого i-го кольцевого регистра соединен с (i+n - )-ым входом первого управляняцего элемента И-ИЛИ, выход которого подключен к первому информационному входу сравнения и к 25 первому входу первого элемента И, выход которого соединен с первым установочным входом регистра, первый выход которого подключен ко вторым входам 1,2,...,(п-|)-го вхрдных эле- зо

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

входного элемента И-ШМ, (п-1)-ый выход второго дешифратора соединен с первьЕм входом п-го входного элемента И-ШШ, выход которого соединен со входом п-го кольцевого регистра, выход которого подключен к п-му входу второго управляющего элемента И-ИЛИ, выход каждого К-го кольцевого регистра, где К 2,...,{п-1) соединен с (к n - 1) входом второго управляющего элемента И-ШШ, выход которого I подключен ко второму информационному

входу схемы сравнения и к первому вхо .„ ду второго элемента И, выход которого соединен со вторым установочным входом регистра, второй вход которого подключен к четвертым входам 2,3..., (n-l) входных элементов И-ИШ и ко jj второму входу п-го элемента И-ИЛИ, первый выход сравнения соединен со вторыми входами элементов И с первым управляющим входом узла синхро(ниэации, второй выход которого подключен к информационному входу регистра и ко вторым установочным входам кольцевых регистров, второй выход схемы сравнения соединен с первым входом элемента ИЛИ, второй вход которого подключен к третьему выходу узла синхронизации, а выход - к информационному входу второго счетчика, выход которого соединен со вторым управляющим входом узла синхронизации.

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

Устройство содержит кольцевые регистры Ц -1, элементы И-ИЛИ , узел 3 синхронизации, регистр А, схему 5 сравнения, элементы И-ШШ 6 и 7, дешифраторы 8 и 9, счетчики 10 и 11, элемент.ИЛИ 12, элементы И 13 и 14, вход 15 запуска.

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

I .

По стартовому импульсу узел 3

синхрониза1Ц1и вырабатывает сигнал, который задает режим выбора максимального или минимального числа схемы сравнения, разрешает работу кольцевых регистров в режиме считывания и устанавливает счетчик 10 в состояние 1. Выход счетчика 10 соединен с установочным входом счетчика I1 таким образом, что его первоначальное состояние соответствует значению счетчика 1 с добавлением единицы, задает режим выбора максимального или минимального числа схеме 5 сравнения и разрешает работу кольцевых регистров I в режиме считывания. Числа, полученные в счетчиках депшфрируются и на одной из выходных шин дешифраторов 8 и 9 соответственно появляется сигнал, т.е. открываются по одному из входов элемент И-ИЛИ 6, элемент И-ИЛИ 2, по одному из входов элемент И-ИЛИ 2, сортветствукщий кольцевому регистру и по одному из входов элемент И-ИЛИ 7. Через элемент И-ИЛИ 6 в схему 5 сравнения поступает число А с первого кольцевого регистра Ц , а через элемент И-ШШ 7 число В со второго кольцевого регистра 12. После сравнения чисел возможны два варианта работы устройства. Если А В, то с первого выхода схемы 5 сравнения через элемент ИЛИ 12 сигнал поступает в счетчик 11 и переключает его в состояние 3. Работа устройства продолжается. Если А В, то появляется сигнал на втором выходе схемы 5 срав нения, открывающий по одному входу элементы И 13 и 14 и одновременно по ступающий в узел 3 синхронизации, ко торый по этому сигналу вырабатывает сигнал, разрешающий сдвиг в регистре 4 и работу кольцевых регистров 1 в режиме записи. Числа А и В через элементы И 13 и 54 соответственно поступают в регистр 4, сдвигаются и записываются в соответствующие кольцевые регистры 1 через элементы И-ИЛИ 2 и И-ИЛИ 2 (в данном случае А - во второй, В - в первые кольцевые регистры 1). После записи чисел по сигналамот узла 3 синхронизации счетчик 1I переключается в состояние 3, а кольцевые регистры 1 7 в режи считывания и работа устройства продолжается. Как только в счетчике II будет число п, по сигналу с выхода счетчика II в узле 3 синхронизации вырабатывается сигнал, переключающий счетчик 10 в состояние 2, соответ венно счетчик П-в состояние 3. Работа схемы продолжается до полног упорядочения чисел. Предлагаемое устройство при относительной простоте технической реали зации и большом количестве стандартн элементов вычислительной техники обе печивает выполнение функций сравнения чисел и их упорядочения по возрастанкю или убыванию. Оно имеет более щирокие функциональные возможности по сравнению с известным. Формула изобретения Устройство для сортировки чисел, содержащее п кольцевых регистров, управлякицие элементы И-ИЛИ, входные элементы И-ИЛИ, дешифраторы, счетчики, элементы И, ИЛИ, регистр, узел синхронизации, первый выход которого соединен с установочными входами кольцевых регистров, с управляющим входом схемы сравнения и со входом первого счетчика, выходы которого подключены ко входам первого дешифра тора и установочным входам второго счетчика, выходы которого соединены со входами второго дешифратора, от личающееся тем, что, с целью расширения функциональных возможностей за счет упорядочения чисел как по возрастанию, так и по убыванию, в нем каждый i-ый выход первого дешифрагора, где i 1,2,..., (n-l) соединен с 1-ым входом первого управляющего элемента И-ИЛИ и с первым входо( i-ro входного элемента И-ШШ, выход каждого 1-го входного элемента И-ИЛИ подключен ко входу t-го кольцевого регистра, выход каж- дого i-го кольцевого регистра соединен с (5+ п - 1)-ым входом первого управляющего элемента И-ИЛИ, выход которого подключен к первому информационному входу схемы сравнения и к первому входу первого элемента И, выход которого соединен с первым установочным входом регистра, первый выход которого подключен ко вторым входам I,2,...,(п-1)-го входных элементов И-ИЛИ, каждый -ый выход второго дешифратора соединен с -ым входом второго управляющего элемента И-ИЛИ, каждый j-ый выход второго дешифратора, где j 1,2,... ,,(п-2), подключен к третьим входам (j+j)-ro входного элемента И-ИЛИ, {п-1)-ый выход второго дешифратора соединен с первым входом п-го входного элемента И-ИЛИ, выход которого соединен со входом п-го кольцевого регистра, выход которого подKjao4eH к п-му входу второго управляющего элемента И-ИЛИ, выход каждого К-го кольцевого регистра, где К 2,...,(п-0 соединен с (К+n-l) Ьходом второго управляющего элемента И-ШШ, выход которого подключен ко второму информационному входу схеглл сравнения и к первому входу второго элемента И, выход которого соединен со вторым установочным входом ре истра, второй выход которого подключен к четвертым входам 2,3,...,(п-0 входных элементов И-ИШ и ко второму входу п-го элемента И-ШШ, первый выход схемы сравнения соединен со вторыми входами элементов И и с первым управляющим входов узла синхронизации, второй выход которого подключен к информационнону входу регистра и ко вторым установочньм входам кольцевых регистров, второй выход схемы сравнения соединен с первым входом элемента ИЛИ, второй вход которого под1слючен к третьему выходу узла синхронизации, а выход - к информационному входу второго счетчика, выход которого соеди