Устройство для сортировки двоичных чисел

Устройство для сортировки двоичных чисел

Иллюстрации

Показать все

Реферат

 

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ДВОИЧНЫХ ЧИСЕЛ, содержащее матрицу И- Ш ячеек анализа, где п - количество чисел и число строк,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), соединен с управляющим входом элемента запрета

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

3GD G 06 F 7/06

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

«11 j ÄI-,,) j i:. iÀ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3576571/18-24 (22) 08 ° 04. 83 (46) 23.07. 84. Б10л. Р 27 (72) Н.И.Крылов и Н.Н.Шубина (53) 681.322(088.8) (56) 1. Авторское свидетельство СССР

В 746502,- кл. G 06 F 7/04, 1978.

2. Авторское свидетельство СССР

У 526888, кл. G 06 F 7/06, 1974 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ДВОИЧНЫХ ЧИСЕЛ, содержащее матрицу

Ь tn ячеек анализа, где fl — количество чисел и число строк, rn — число разрядов чисел и число столбцов, каждая ячейка анализа включает элемент И, элемент ИЛИ и элемент запрета, причем в каждой ячейке анализа управляющий вход элемента запрета соединен с первым входом элемента ИЛИ данной ячейки, к второму входу которого подключен выход элемента И этой ячейки, шина прямого кода j -ro разряда q -го числа устройства, где

1,2, ...,n, 1 = 1,2,..., п, подключена к информационному входу элемента запрета 11 -й ячейки анализа, шина инверсного кода 1 -го разряда

i-ro числа устройства подключена

1 к первому входу элемента И i -й ячейки анализа, кроме того, устройство дополнительно содержит элемент задержки, в первой и и -й строках — элемент НЕ, элемент запрета и триггер,,в строках с второй по (и-1)-ю — элемент НЕ, элемент запрета, триггер, элемент ИЛИ, а в каждом столбце многовходовый элемент ИЛИ и элемент И съема ) -го разряда числа, информационный вход которого соединен ! с выходом 1-ro многовходового элемента ИЛИ и вторыми входами элементов И -х ячеек анализа всех строк, выход элемента И съема 1 -го разряда числа является выходом 1 -ro разряда числа устройства, входы 1 -го многовходового элемента ИЛИ соединены с выходами элементов запрета 1 -х ячеек анализа всех строк, выход элемента ИЛИ k -й ячейки анализа 1 -й строки, где k = 1,2,..., (т-1), соединен с управляющим входом элемента запрета (1+1)-й ячейки анализа 1 -й строки, а выход элемента ИЛИ < -й ячейки анализа i -й строки через элемент НЕ i -й строки — с первым информационным входом элемента запрета соответствующей строки, выход которого подключен к входу установки в нулевое состояние триггера -й строки, в каждой Р -й строке, где = 2, 3,..., (й - t ), выход элемента HJIH h -й ячейки анализа через элемент НЕ -й строки соединен с первым входом элемента ИЛИ P -й строки, выход которого подключен к второму входу элемента ИЛИ и управляющему входу элемента запрета (8+1)-й строки, выход элемента ИЛИ II -й ячейки анализа первой строки через элемент НЕ первой строки соединен с вторым входом элемента ИЛИ н управляющим входом элемента запрета второй строки, вторые информационные входы элементов запрета всех строк подключены к выходу элемента задержки, .а входы установки в единичное состояние триггеров всех строк — к шине начальной установки устройства, о т л и ч а ющ е е с я тем, что, с целью расшире1104504 ния области применения устройства за счет обеспечения выдачи упорядоченной последовательности чисел в заданном интервале без потерь информации при одинаковых числах, в него введены регистры максимального и минимального чисел, блок сравнения и элемент И управления выдачей числа, в каждую строку — элемент ИЛИ запрета выдачи < -го числа, а в каждую ячейку анализа — два элемента запрета и второй элемент ИЛИ, причем прямои выход 1 -ro разряда регистра максимального числа соединен с первыми информационными входами вторых элементов запрета ) -х ячеек анализа всех строк, а инверсный выход 1 -ro разряда максимального числа — с первыми информационными входами третьих

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

Изобретение относится к вычислительной технике и может быть использовано для сортировки массива двоичных чисел в порядке убывания (возрастания) их величины, а также для 5 выбора и упорядочения чисел в определенном интервале.

Известно устройство для сравнения m n -разрядных двоичных чисел, содержащее m элементов равнозначнос-1î ти,AD †триггер, элементы И, ИЛИ (1).

Недостатком данного. устройства является низкое быстродействие, а именно для определения очередного числа в заданном интервале требует- 15 ся тактов работы.

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

I .ячейки каждой строки через элемент HE соединен с первым сигнальным входом

1О!

5 элемента запрета и первым входом элемента ИЛИ той же строки, выход эле- 20 мента ИЛИ каждой строки соединен с вторым входом элемента ИЛИ и управляющим входом элемента запрета последующей строки, вторые сигнальные входы элементов запрета каждой строки. 25 соединены с выходом элемента задержки, к входу которого подключена тактовая шина, а выход элемента запрета каждой строки подключен к единичному входу триггера той же строки (2}. 30

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

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

Поставленная цель достигается тем, что в устройство для сортировки двоичных чисел, содержащее матри- 45 цу и, И ячеек анализа, где п — количество чисел и число строк, rn — число разрядов чисел и число столбцов, каждая ячейка анализа включает элемент И, элемент ИЛИ и элемент з апре- 50 та, причем в каждой ячейке анализа управляющий вход элемента запрета соединен с первым входом элемента ИЛИ данной ячейки, к второму входу котоРого подключен выход элемента И этой 55 ячейки, шина прямого кода 1 -ro разряда i -ro числа устройства, где 1

1,2,..., n,1 = 1,2,..., tn, подключена к информационному входу элемента запрета )1 -и ячсйки анализа, шина инверсного кода 1 -го разряда е -го числа устройства подключена к первому входу элемента H

1,2, (ш — 1), соединен с управляющим входом элемента запрета (4 †) — и ячейки анализа i -й строки, а выход элемента ИЛИ -й ячейки аналиI за 1 -й строки через элемент НЕ < -й строки с первым информационным входом элемента запрета соотвеTc òâóêÿöeé строки, выход которого подключен к входу ус— тановки в нулевое состояние триггера t -й строки, в каждой - — и строке., где = 2,3,..., (n-1), выход элемента ИЛИ n — и ячейки анализа через элемент НЕ 0 -й строки соединен с первым входом элемента ИЛИ 8 — и строки, выход которого подключен к второму входу элемента ИЛИ и управляющему входу элемента запрета (! +1)-й строки, выход элемента ИЛИ И -й ячейки анализа первой строки через элемент HE первой строки соединен с вторым входом элемента ИЛИ и управляющим входом элемента запрета второй строки, вторые информационные входы элементов запрета всех строк подключены к выходу элемента задержки, а входы установки в единичное состояние триггеров всех строк — к шине начальной установки устройства, введены регистры максимального и минимального чисел, блок сравнения и элемент И управления выдачей числа, в каждую строку — элемент ИЛИ запрета вьдачи .1-го числа, а в каждую ячейку анализа — два элемента запрета и второй элемент ИЛИ, причем прямой выход 1 -Io

1104504 разряда регистра максимального числа соединен с первыми информационныMi$ входами вторых элементов запрета i -х ячеек анализа всех строк, а инверсный выход f -го разряда максимального числа — с первыми информационными входами третьих элементов запрета ) -х ячеек анализа всех строк, выходы разрядов регистра минимального числа подключены к соответствующим входам первой. группы блока сравнения, соответствующие входы вто. рой группы которого соединены с выходами g --x многовходовых элементов ИЛИ, первый выход блока .сравнения 15 подключен к первому входу элемента И управления выдачей числа, второй вход которого подключен к шине тактовых импульсов устройства, а выходк управляющим входам элементов И 20 съема числа всех столбцов и входу элемента задержки, второй выход блока сравнения является выходом конца

-работы устройства, в каждой ячейке анализа выходы второго и третьего 25 элементов запрета соединены с первым и вторым входами второго элемента ИЛИ, вторые информационные входы второго и третьего элементов запрета -й ячейки анализа соединены соответст- ЗО венно с шинами инверсного и прямого кода 1 -го разряда i -го числа устройства, выход второго элемента ИЛИ k -й ячейки анализа 1 -й строки под ключен к управляющим входам второго. 35 и третьего элементов запрета и третьему входу элемента ИЛИ (k+1)-й ячейки анализа этой строки, выходы третьих элементов запрета всех ячеек анализа и .инверсный выход триггера (-й стро- 40 ки соединены с входами s — го элемента ИЛИ запрета выдачи 1-ro числа, выход которого соединен с управляющим входом первого элемента запрета

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

На фиг. 1 представлена схема устройства, на фиг. 2 — схема ячейки.

Устройство содержит ячейки 1, образующие матрицу 11, m, где m — разрядность числа, а И вЂ” количество чисел, регистр максимального числа, состоящий из триггеров 2, регистр минимального числа, состоящий из триггеров 3, схему 4 сравнения, эле менты ИЛИ 5-7, элементы И 8 и 9,элементы HF. 10, элементы 11 запрета, триггеры 12, элемент 13 задержки, тактовую шину 14, шину 15 сброса, выходы 16 разрядов числа, выход 17 устройства, на котором появляется сигнал окончания работы устройства. Кроме этого, каждая ячейка 1 (фиг. 2) содержит триггер 18 разряда числа, элементы 19-.21 запрета, элемент И 22, элементы ИЛИ 23 и 24, входы 25-29, выходы 30-33.

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

В исходном состоянии в регистрах, образованных триггерами 18 ячеек записаны сортируемые числа. В регистры максимального, образованного триггерами 2, и минимального, образованного триггерами 3, чисел записываются числа равные соответственно верхней и нижней границам интервала. В каждом также из массив.а и двоичных чисел вьщеляется экстремальное, например максимальное число на выходах элемента ИЛИ 6, не превьппающее верхней границы интервала. Если выделенное число больше нижней гра— ницы интервала, то оно при поступлении импульса на вход. передается через элементы И 8 на выходные шины устройства.

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

Таким образом, производится передача всех чисел, находящихся в заданном интервале, на выход устройства в порядке убывания их значений.

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

При процессе запрета выдачи чисел, превышающих верхнюю границу интервала, выполняется, начиная со старшего разряда, последовательный поразряд1104504

25

7 ный анализ максимального и сортируемых чисел

Пусть в старшем разряде максимального числа "1", тогда на первый вход элемента 20 запрета каждой ячейки первого столбца поступает единичный .сигнал, При этом если в старшем раз. ряде < -го числа (1 = 1,2,..., « ) имеется "0", то единичный сигнал с инверсного выхода триггера 18 посту-. пает на второй вход элемента 20 запрета 1 -й ячейки 1 первого столбца, и, следовательно, на его выходе имеется единичный сигнал, который поступает через элемент ИЛИ 24 на выход 32 ячейки и далее на вход 28 следующей ячейки, запретив тем самым анализ последующих разрядов i -го числа, так как оно меньше максимального.

Если в старшем разряде 1 -ro числа имеется "1", то единичный сигнал с вь хода триггера 18 поступает на вход элемента 21 запрета 1 -й ячейки первого столбца. Таким образом, элементы.20 и 21 запрета открыты только по одному входу и на их выходах, а следовательно, и на выходе 32 ячейки не имеется единичного сигнала, т. е. нет запрета на анализ следующего разряда.

Пусть в старшем разряде максималь. ного числа 0", тогда на первый вход элемента 21 запрета каждой ячейки первого столбца поступает единичный . сигнал. При этом, если в старшем разряде i -го числа "0", то единичный сигнал с выхода триггера 18 поступает на вход элемента 20 запрета 1 -й ячейки 1 первого столбца. Таким образом, элементы 20 и 2 1 запрета открыты только по одному входу и на их выходах, а следовательно, и на выходе 32 ячейки не имеется единичного сигнала, т.е. нет запрета на анализ следующего разряда t -го числа. Если в старшем разряде -ro числа "1", то единичный сигнал с выхода триггера 18 поступает на второй вход эле.мента 21 запрета i -й ячейки 1 пер вого столбца и, следовательно, на

- его выходе имеется единичный сигнал, который поступает на выход 33 ячейки и через элемент ИЛИ 24 на выход 32 ячейки и далее на вход 28 следующей ячейки, запрещая тем самым анализ последующих разрядов i -го числа.

С выхода 33 сигнал поступает через элемент ИЛИ 5 на вход 25 первой ячейки 3 -ro числа, далее через эл»мент ИЛИ 23 ячейки на вход 25 следующей ячейки i -го числа, и т.д., запрещая тем самым выдачу -го чис5 ла, так как оно больше максимального.

Для тех чисел, при анализе старших разрядов которых нет запрета на анализ следующего разряда, осуществляется аналогичным образом анализ следующего разряда и т.д.

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

Одновременно с процессом запрета выдачи чисел, превышающих верхнюю границу интервала, осуществляется процесс выделения максимального числа из чисел, находящихся в заданном интервале. Этот процесс также осуществляется путем последовательного поразрядного анализа сортируемых чисел, начиная со старшего разряда.

При этом, если в старших разрядах сортируемых чисел, исключая числа запрещенные к выдаче, "0", то на выходе 30 ячеек старши:. разрядов, а также на выходе элемента ИЛИ 6 тоже "0". Если в старших разрядах сортируемых чисел, исключая числа запрещенные к выдаче, "1", то на входах элементов 19 запрета ячеек старших разрядов чисел ."1" и, следовательно, на выходе 30 этих ячеек, а также на выходе элеме«та ИЛИ 6 тоже "1". Если в старших разрядах сортируемых чисел, исключая число запрещенных к выдаче, неравенство, т.е. в данном разряде этих чисел имеется как "0", так и "1", происходит формирование на выходе элемента ИЛИ 6 "1" и исключение нз процесса анализа всех более младших разрядов тех чисел, у которых в данном разряде имеется "0", следующим образом. Так как имеется хотя бы одно число, у которого в старшем разряде "1", то «а входах элемента 19 запрета ячейки старшего разряда этсt.п числа "1", и, следовательно,. «а выходе 30 этой ячеики, у которых в стари«:х разрядах "0" появляются единичные сигналы на входах элемента И 22 и, следовательно, на выходе 31 ячейки. Единичный сигнал с выхода 31 ячейки стар1104504

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

Аналогично проводится анализ последующих разрядов оставшихся чисел, по окончании которого на выходах элементов ИЛИ 6 и первой группы входов схемы 4 сравнения сформируется код максимального числа из чисел, не превьш|ающих значение числа, записанного в регистре максимального числа.

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

Для возможности считывания всех одинаковых чисел сигнал с выхода элемента НЕ 10 первого максимального числа поступает на упрахряющие входы элементов 11 запрета всех последующих чисел (для второго непосред ственно, а для остальных через элементы ИЛИ 7), запрещая прохождение сигналов через элементы 11 запрета на входы триггеров 12.

Таким образом, при наличии нескольких одинаковых чисел они последовательно опрашиваются и выдаются. Пос— ле выдачи всех чисел одного значения происходит выбор описанным способом

I следующего наибольшего числа и выдача его. После выдачи всех чисел в заданном интервале триггеры 12 устанавливаются в исходное единичное состояние подачей на них импульса сброса по шине 15.

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

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

1104504

Фиг1

1104504

Составитель Е.Иванова

ТехредМ.Гергель Корректор O.Луговая

Редактор Н. Бобкова

Филиал ППП "Патент", г.ужгород, ул.Проектная, 4

Заказ 5261/35 Тираж 699 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4(5