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

НИИ области применения устройства за счет обеспечения вьщачи упорядоче ной последовательности чисел в задан ном интервале без потерь информации при одинаковых числах, в него введены регистры-максимального и минималь ного чисел, блок сравнения и элемент И управления выдачейчисла, в каждую строку - элемент ИЛИ запрета выдачи i -го числа, а в каждую ячейку анализа - два элемента запрета и второй элемент ИЛИ, причем прямой выход j-го разряда регистра максимального числа соединен с первыми Информационными входами вторых элементов запрета j -х ячеек анализа всех строк, а инверсный выход j -го разряда максимального числа - с первыми информационными входами третьих элементов запрета j-х ячеек анализа всех строк, выходы разрядов регистра минимального числа подключены к соответствующим входам первой группы блока сравнения, соответствующие входы второй группы которого соединены с выходами J -X многовходовых элементов .ИЛИ, первьм выход блока сравнения подключен к первому входу элемента И управления выдачей числа второй вход которого подключен к шине тактовых импульсов устройства, а 1 А выход - к управляющим входам элементов И съема числа всех столбцов и входу элемента задержки, второй выход блока сравнения является выходом конца работы устройства, в каждой ячейке анализа выходы второго и третьего элементов запрета соединены с первым и вторым входами второго элемента ИЛИ, вторые информационные входы второго и третьего элементов запрета1 -й ячейки анализа соединены соответственно с шинами инверсного и прямого кода j -го разряда i -го числа устройства, выход второго элемента ИЛИ k-и ячейки анализа i -и строки подключен к управляющим входам второго и третьего элементов запрета и третьему входу элемента ИЛИ ()-й ячейки анализа этой строки, выходы третьих элементов запрета всех ячеек анализа и инверсный выход триггера i-и строки соединены с входами i -го элемента ИЛИ запрета вьщачи i-го числа, выход которого соединен с управляющим входом первого элемента запрета первой ячейки анализа i -и строки, управляющие входы второго и третьего элементов запрета ячеек анализа первого столбца всех строк подключены к нулевой шине устройства.

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ, содержащее матрицу И- Ш ячеек анализа, где п - количество чисел и число строк,m - число разрядов чисел и число столбцов, каждая ячейка анализа включает элемент И, элемент ИЛИ и элемент запрета, причем в каждой ячейке анализа управляющий вход элемента запрета соединен с первым входом элемента ИЛИ данной ячейки, к второму входу которого подключен выход элемента И этой ячейки, шина прямого кода j -го разряда 1 -го числа устройства, где i 1,2,...,п, j 1,2,...,ni, подключена к информационному входу элемента запрета ij -и ячейки анализа, шина инверсного кода J -го разряда i-ro числа устройства подключена к первому входу элемента И i j -и ячейки анализа, кроме того, устройство дополнительно содержит элемент задержки, в первой и п -и строках - элемент НЕ, элемент запрета и триггер, ,в строках с второй по (п-1)-ю - элемент НЕ, элемент запрета, триггер, элемент ИЛИ, а в каждом столбце многовходовый элемент ИЛИ и элемент И съема j-го разряда числа, информационный вход которого соединен с выходом )-го многовходового элемента ИЛИ и вторыми входами элемейтов И j-X ячеек анализа всех строк, выход элемента И съема j -го разряда числа является выходом -го разряда числа устройства, входы j -го многовходового элемента ИЛИ соединены с выходами элементов запрета j -х ячеек анализа всех строк, выход элемента ИЛИ k -и ячейки анализа i -и строки, где k 1,2,..., (m-1), соединен с управляющим входом элемента запрета

Изобретение относится к вычислительной технике и может быть исполь зовано для сортировки массива двоич ных чисел в порядке убывания (возрастания) их величины, а также для выбора и упорядочения чисел в определенном интервале. Известно устройство для сравнения т-п-разрядных двоичных чисел, содержащее m элементов равнозначно ти, VnD-триггеров , элементы И, ИЛИ Недостатком данного, устройства является низкое быстродействие, а именно для определения очередного в заданном интервале требуется ti тактов работы. Наиболее близким к изобретению по технической сущности является устрой ство для сортировки двои ных чисел, содержащее матр1-щу ячеек, каждая из которых содержит элемент И, элемент ИЛИ и элемент запрета. Кроме того, устройство содержит элемент задержки и в, каждой строке - элемент НЕ, элемент запрета,элемент ИЛИ и триггер, а в каждом столбце - многовходовый элемент ИЛИ и элемент И съема числа, причем первый вход элемента И каждой ячейки соединен с первым входом ячейки, второй вход - с вторым входом ячейки, а выход - с первым входом элемента ИЛИ этой ячейки, второй вход которого соединен с управляющим входом элемента запрета этой же ячейки и с третьим входом ячейки, а выход - с первым выходом ячейки и с третьим входом последующей ячейки данной строки, вторые входы ячеек соединены с шиной съема соотвстствующего разряда, которая подключена к первому входу соответствующего элемента И съема числа, к вторым входам которых подключена тактовая шина, четвертый вход ячейки соединен с сигнальным входом элемента запрета, выход которого подключен к второму выходу ячейки, второй выход каждой ячейки каждого столбца соединен с соответствующим входом многовходового элемента ИЛИ, выход которого соединен с шиной съема соответствутадего разряда, третий вход первой ячейки каждой строки соединен с единичным выходом триггера той же строки, а первый выход последней ячейки каждой строки через элемент НЕ соединен с первым сигнальным входом элемента запрета и первым входом элемента ИЛИ той же строки, выход элемента -ИЛИ каждой строки соединен с вторым входом элемента ИЛИ и управляющим входом элемента запрета последующей строки, вторые сигнальные входы элементов за прета каждой строки соединены с выходом элемента задержки, к входу которого подключена тактовая шина, а выход элемента запрета каждой строки подключен к единичному входу триггера той же строки 2

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

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

Поставленная цель достигается тем, что в устройство для сортировки двоичных чисел, содержащее матрицу п. П1 ячеек анализа, где п - количество чисел и число строк, гп - число разрядов чисел и число столбцов, каждая ячейка анализа включает элемент И, элемент ИЛИ и элемент запрета, причем в каждой ячейке анализа управляющий вход элемента запрета соединен с первым входом элемента ИЛИ данной ячейки, к второму входу которого подключен выход элемента И этой ячейки, шина прямого кода j -го разрядам -го числа устройства, гдеi 1,2, ..., п , j 1 ,2 ,.. ., tn , подключен к инфдрманионному входу элемента запрета 1J -II ячейки анализа, шина инверсного кода J -го разряда i -го числа устройства подключена к первому входу элемента И)-и ячейки анализа, кроме тоге, устройство дополнительно содержит элемент задержки, в первой ип-и строках - элемент НЕ, элемент запрета и триггер, в строках с второй по (п-1)-ю - элемент НЕ, элемент запрета, триггер, элемент ИЛИ а в каждом столбце - многовходовый элемент ИЛИ и элемент И съема j -го разряда числа, информационный вход которого соединен с выходом j -го многовходового элемента И.ГГИ и вторыми входами элементов И i -х ячеек анализа всех строк, выход элемента И съема j -го разряда числа является выходом j -го разряда числа устройства, входы J -го МЕЮГОВХОДОВОГО элемента ИЛИ соединены с выходами элементов запрета j -х ячеек анализа всех строк, выход элемента ИЛИ .-и ячейки анализа i -и строки, где k 1,2,.. (m-1), соединен с управляющим входом элемента запрета. (1;-1)-й ячейки анализа -и строки, а выход элемента ИЛИ i-й ячейки анализа 1 -и строки через элемент НЕ { -и строки с первым информационным входом элемента запрета соответствующей строки, выход которого подключен к входу установки в нулевое состояние тригге„ у „ ра ( -и строки, в каждой-t -н cTpoKej

где 2 2,3,..., (п-1), выход элемента И.ПИ п -и ячейки анализа через элемент НЕ I -и строки соединен с первым входом элемента И.Ш- Р -и строк выход которого подключен к второму входу элемента ИЛИ и управляющему входу элемента запрета (( + 1)-й строк выход элемента ИЛИ П -li ячейки анализа первой строки через элемент НЕ первой строки соединен с вторым входом элемента ИЛИ и управляющим входом элемента запрета второй строки, вторые информационные входы элементов запрета всех строк подключены к выходу элемента задержки, а входы установки в единичное состояние триггеров всех строк - к шине начальной установки устройства, введены регистры максимального и минимального чисел, блок сравнения и элемент И управления выдачей числа, в каждую строку - элемент ИЛИ запрета вьщачи -i-го числа, а в каждую ячейку анализа - два элемента запрета и второй элемент ИЛИ, причем прямой выход j -г $11 разряда регистра максимального числа соединен с первыми информационнымн, входами вторых элементов запрети 4 -X ячеек анализа всех строк, а Инверсный выход j -го разряда максимального числа - с первыми информационными входами третьих элементов запрета J -х ячеек анализа всех стро выходы разрядов регистра минимального числа подключены к соответствующим входам первой, группы блока сравнения, соответствующие входы второй группы которого соединены с выходами J-X многовходовых элементов ИЛИ, первый выход блока .сравнени подключен к первому входу элемента И управления вьщачей числа, второй вход которого подключен к шине тактовых импульсов устройства, а выходк управляющим входам элементов И съема числа всех столбцов и входу элемента задержки, второй выход блока сравнения является выходом конца работы устройства, в каждой ячейке анализа выходы второго и третьего элементов запрета соединены с первым и вторш входами второго элемента ИЛ вторые информационные входы второго и третьего элементов запретамч -и ячейки анализа соединены соответственно с шинами инверсного и прямого кода -го разряда i -го. числа устройства, выход второго элемента ИЛИ ( -и ячейки анализа i -и строки подключен к управляющим входам второго и третьего элементов запрета и третье му входу элемента ИЛИ ()-и ячейки анализа этой строки, выходы третьих элементов запрета всех ячеек анализа и инверсный выход триггера -и строки соединены с входами i -го элемента ИЛИ запрета выдачи i-го числа, выход которого соединен с управляющим входом первого элемента запрета первой ячейки анализа i -и строки, управляющие входы второго и третьего Элементов-запрета ячеек анализа первого столбца всех строк подключены к нулевой шине устройства. На фиг. 1 представлена схема уст.ройства; на фиг. 2 - схема ячейки. Устройство содержит ячейки 1, об разующие матрицу Ц. гп , где т раз рядность числа, ad- количество чи сел, регистр максимального числа, состоящий из триггеров iZ, регистр минимального числа, состоящий из триггеров 3, схему 4 сравнения, эле менты И.ПИ 5-7, элементы И 8 и 9,элементь НЕ 10, элементы 11 запрета, триггеры 12, элемент 13 задержки, тактовую шину 14, шину 15 сброса, выходы 16 разрядов числа, выход 17 устройства, на котором появляется сигнал окончания работы устройства. Кроме этого, каждая ячейка 1 (фиг. 2) содержит триггер 18 разряда числа, элементы 19-21 запрета, элемент И 22, элементы ИЛИ 23 и 24, входы 25-29, выходы 30-33. Устройство работает следующим образом. В исходном состоянии в регистрах, образованных триггерами 18 ячеек 1, записаны сортируемые числа. В регистры максимального, образованного триггерами 2, и минимального, образованного триггерами 3, чисел записываются числа равные соответственно верхней и нижней границам интервала. В каждом также из массива ti двоичных чисел вьщеляется экстремальное, например максимальное число на выходах элемента ИЛИ 6, не превыщаюп1ее верхней границы интервала. Если выделенное число больше нижней границы интервала, то оно при поступлении импульса на вход передается через элементы ИЗ на выходные шины устройства. После выдачи максимального числа указ аннь1м способом оно исключается из рассматриваемого массива, а среди оставшихся чисел производится выбор очередного максимального числа и, если оно больше нижней границы интервала, передача его на выходные щины устройства. Если очередное вьщеленное число меньше нижней граНИЩ11 интервала, то на выходную шину 17 поступает сигнал конца анализа. Таким образом, производится передача всех чисел, находящихся в заданном интервале, на выход устройства в порядке убывания их значений. Рассмотрим раздельно процесс запрета выдачи чисел, превьш1ающих верхнюю границу интервала, процесс вьщеления максимального числа из чисел, находящихся в заданном интервале, и процесс формирования убывающей последовательности этих чисел. При процессе запрета выдачи чисел, превьщ1ающих верхнюю границу интервала, выполняется, начиная со старшего разряда, последовательный поразряд7110ный анализ максимального и сортируемых чисел. Пусть в старшем разряде максималь ного числа 1, тогда на первый вход элемента 20 запрета каждой ячейки первого столбца поступает единичный сигнал, При этом,если в старшем разряде -го числа ( 1 1,2,..., И ) имеется О, то единичный сигнал с инверсного выхода триггера 18 поступает на второй вход элемента 20 запрета i -и ячейки 1 первого столбца, и, следовательно, на его выходе имеется единичный сигнал, который поступает через элемент ИЛИ 24 на выход 32 ячейки и далее на вход 28 следующей ячейки, запретив тем самым анализ последующих разрядов j -го чис ла, так как оно меньше максимального Если в старшем разряде -го числа имеется 1, то единичный сигнал с в IXOдa триггера 18 поступает на вход элемента 21 запрета i-и ячейки niepBoro столбца. Таким образом, элементы. 20 и 21 запрета открыты только по одному входу и на их выходах, а следовательно, и на вьгходе 32 ячейки не имеется единичного сигнала т.е. нет запрета на анализ следующего разряда. Пусть в старшем разряде максималь , ного числа О, тогда на первьй вход элемента 21 запрета каждой ячейки первого столбца поступает единичный сигнал. При этом, если в старшем разряде i -го числа О, то единичный сигнал с выхода триггера 18 поступает на вход элемента 20 запрета i -и ячейки 1 первого столбца. Таким образом, элементы 20 и 21 запрета открыты только по одному входу и на их выходах, а следовательно, и на выходе 32 ячейки не имеется единичного сигнала, т.е. нет запрета на анализ следующего разряда i -го числа. Если в старшем разряде -го числа 1, то единичный сигнал с выхода триггера 18 поступает на второй вход элё:Мента 21 запрета -и ячейки 1 столбца и, следовательно, на его выходе имеется единичный сигнал, которьй Поступает на выход 33 ячейки и через элемент ИЛИ 24 на выход 32 ячейки и далее на вход 28 следукяцей ячейки, запрещая тем самым анализ последующих разрядов t го числа. С выхода 33 сигнал поступает через элемент ИЛИ 5 на вход 25 первой ячейки V-го числа, далее зломент ИЛИ 23 ячейки на вход 25 следуклдей ячейки i -го числа, и т.д., запрещая тем самым выдачу i -го числа, так как оно больше максимального. Для тех чисел, при анализе старших разрядов которых, нет запрета на анализ следующего разряда, осуществляется аналогичным образом анализ следующего разряда и т.д. В результате после анализа всех разрядов сортируемых чисел на входах 25 ячеек 1 чисел, значения которьк превьпиают значение максимального числа, имеется единичный сигнал, поступивший через элемент ИЛИ 5 и запрещающий выдачу этих чисел. Одновременно с процессом запрета вьщачи чисел, превьш1ающих верхнюю границу интервала, осутцествляется процесс выделения максимального числа из чисел, находящихся в заданном интервале. Этот процесс также осу- . ществляется путем последовательного поразрядного анализа сортируемых чисел, начиная со старшего разряда. При этом, если в старших разрядах сортируемых чисел, исключая числа запрещенные к выдаче, О, то на выходе 30 ячеек старшю: разрядов, а также на в псоде элемента ИЛИ 6 тоже О. Если в старших разрядах сортируемых чисел, исключая числа запрещенные к выдаче, 1, то на входах элементов 19 запрета ячеек 1 старших разрядов чисел .1 и, следовательно, на выходе 30 эт1тх ячеек, а также на выходе элемента ШШ 6 тоже 1. Если в старших разрядах сортируемых чисел, исключая число запрещенных к вьщаче, неравенство, т.е. в данном разряде этих чисел имеется как О, так и 1, происходит формирование на выходе элемента ИШ 6 1 и исключение из процесса анализа всех более младших разрядов тех чисел, у которых в данном разряде имеется О, следующим образом. Так как имеется хотя бы одно число, у которого в старшем разряде 1, то на входах элемента 19 запрета ячейки старшего разряда этого числа 1, и, следовательно,на вьгходе 30 этой ячейки, у которых в стлршсх разрядах О, появляются единичные сигналы на входах элемента И 22 и, следоательно, на вьгходе 31 ячейки. Единичный сигнал с вькода 31 ячейки стартого разряда этих чисел закрывает по управляющеиу входу элементы 19 запрета всех последунлцих ячеек данных чисел, исключив тем самым из дальнейшего анализа все более младшие разряды этих чисел. Аналогично проводится анализ последукхцих разрядов оставшихся чисел, по окончании которого на выходах элементов ИЛИ 6 и первой группы входов схемы 4 сравнения сформируется код. максимального числа из чисел, не превышающих значение числа, записанного в регистре максимального числа. Процесс формирования убывающей пос

ледовательности этих чисел осуществляется следующим образом. Если сформированный код максимального числа не меньшеj чем записанный в регистре минимального числа, то с первого выхода, схемы 4 сравнения поступает сигнал на первьй вход элемента И 9, на второй вход которого поступает тактовый импульс. При появлении тактового импульса на выходе элемента И 9 возникает сигнал, который разрешает поступление кода максимального числа на выходные шины 16 устройства. Этот же сигнал, задержанный на элемен- те 13 задержки, поступает на все эле-30

менты 11 запрета, соединенные по первым сигнальным входам с инвертированными на элементах НЕ 10 выходами 31 ячеек последнего столбца. При совпадении задержанного сигнала с сигналом тех шин, которые соответствуют максимальным для рассматриваемого момента числам, .на выходе первого по порядку элемента 11 -запрета возникает импульс, который устанавливает триггер 12 в нулевое состояние. С выхода триггера 12 сигнал поступает через элемент ИЛИ 5 на вход 25 ячейки старшего разряда числа, исключив тем самым из дальнейшего анализа данное число, т.е. запрещая его прохождение через элементы 19 запрета.

Для возможности считьшания всех одинаковых чисел сигнал с выхода элемента НЕ 10 первого максимального числа поступает на упра лякицие 110

состояние подачей на них импульса сброса по шине 15.

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

ного числа - минимальное число в ин- версном коде, а в регистр минимального числа - максимальное число в инверсном коде. Тогда в каждый момент времени на выходах элементов ИЛИ 6

имеющегося массива чисел в заданном интервале, представленное в инверсном коде.

Технико-экономический эффект предлагаемого устройства заключается в расширении функциональных возможностей. Устройство позволяет выдавать убывающую (возрастающую) последовательность чисел в заданном интервале определять число ближайшее к заданному из массива чисел. В связи с этим расширяется область применения предлагаемого устройства, например для построения гистограмм. Кроме того, предлагаемое устройство обладает болшим быстродействием, которое определяется: только задержками на элементах схемы, и позволяет без потерь информации сортировать произвольные массивы, включающие, например, ряд одинаковых чисел. 410 входы элементов 11 запрета всех последующих чисел (для второго непосред ственно, а для остальных через элементы ИЛИ 7), запрещая прохождение сигналов через элементы 11 запрета на входы триггеров 12. Таким образом, при наличии нескольких одинаковых чисел они последовательно опрашиваются и вьщаются. После выдачи всех чисел одного значения происходит выбор описанным способом следующего наибольшего числа и выдача его. После вьщачи всех чисел в заданном интервале триггеры 12 устанавливаются в исходное единичное присутствует минимальное число из