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

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - расширение функциональных возможностей за счет обеспечения сортировки чисел в скользящей выборке. Устройство содержит регистр 1, k групп ячеек анализа ЯА 2 -З-щщщ ( 8 апертура выборки, m - количество разрядов анализируемых чисел), генератор 3 импульсов, триггер 4, счетчик 5, коммутаторы , элементы ИЛИ 7, -7, входы 8, выходы 9 ,«-9 t разрядов чисел отсортированной выборки. ЯА 2 содержит триггер, элементы И, ИЛИ, два коммутатора, информационные управляющие и тактовые входы, вход перекоса , вход управления режимом, информационные выходы, выход переноса. Устройство обеспечивает сортировку в порядке убывания чисел в скользящей выборке, т.е. сначала - сортировка выборки чисел |А (, А,... Аку, на следующем такте - выборки чисел (А 1лг А« А,.г Т| и т.д. 2 ил. (Л

.,SU.„16 41

СОЮЗ СОВЕТСНИХ и «ч

РЕСПУБЛИК

А1 (51)5 С 06 F 7/08 с .

I ..

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

-в с. :е у /

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ

IlPH ГКНТ СССР

К АВТОРСКОМУ СВИДЕ П:ЛЬСТВУ (21) 4490703/24 (22) 04. 10. 88 (46) 23. 04. 91. Бюл. В 15. (72) Ю.Д.Северилов (53) 681. 325. 5 (088. 8) (56) Авторское свидетельство СССР

Ф 1244659, кл. G 06 F 7/04, 1984.

Патент США М- 3505653, кл. 340-172.5, 1970. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ (57) Изобретение относится к автома" тике и вычислительной технике. Цель изобретения — расширение функциональных во змо жно с тей з а с че т о бе с пе че ния сортировки чисел в скользящей выборке.

:Устройство содержит регистр 1, k групп ячеек анализа ЯА 2<1 -2 <п,,„) (k=2 и

2 апертура выборки, m - количество разрядов анализируемых чисел), генератор

3 импульсов, триггер 4, счетчик 5, коммутаторы 6 -6, элементы ИЛИ 7 -7 р входы 8, выходы 9,,-9 разрядов чисел отсортированной выборки. ЯА 2 содержит т.риггер, элементы И, ИЛИ, два коммутатора, информационные управляющие и тактовые входы, вход перекоса, вход управления режимом, информационные выходы, выход переноса.

Устройство обеспечивает сортировку в порядке убывания чисел в скользящей выборке, т.е. сначала — сортировке выборки чисел 1А <, <<б,..., Ак, на следующем такте — выборки чисел

$Ag A» ° ° ° A„ 4+2 и т.д. 2 ил. 9

1644128

Изобретение относится к области автоматики и вычислительной техники.

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

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

Устройство содержит регистр 1, первую и вторую матрицы ячеек анализа, которые содержат k групп ячеек

2„-,2 k (e„l анализа (k = 2 - аперИ тура выборки, m — количество разрядов анализируемых чисел), генератор

3 импульсов, триггер 4, счетчик 5, коммутаторы 6 -6, элементы ИЛИ 7 —

7„, входы 8, выходы 9, -9 щразрядов чисел отсортированной выборки.

Ячейка 2 анализа содержит триггер

10, элементы И 11,-11, элементы

ИЛИ 12 -.12, коммутаторы 131 и 13, информационные входы 14 q и 14<, управляющие входы 151 и 15< тактовые входы 1.6 q и 16, вход 17 переноса, вход 18 управления режимом, информационные выходы 19<-19» выход 20 переноса.

Э

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

При работе устройства в ячейках

2, -2 „, находятся k m-разрядных чисел, отсортированных в порядке убывания (в ячейке 2 - старший разряд самого большого числа), а в ячей ках 2 4 <„, +,1 — 2 „(„„„1 — величина mod N, где N — номер числа в порядке по ст упле н ия.

Очередное анализирующее число поступает на входы 8 и сигналами с выхода а генератора 3 импульсов записывается в регистр f .Îäíoâðåìåíío число, хранящееся в счетчике 5, увеличивается на единицу, а триггер 4 устанав- 45 .ливается в единичное состояние. Далее происходит поиск числа, записанного в триггер ячеек 2 1 -2 „, анализ а k тактов назад (т. е. само го старого из хранящихся s устроистве) °

Это число имеет тот же самый номер (так как емкость счетчика 5 равна k), что и только что поступившее число, и этот номер хранится в триггерах ячеек 2 „„, -2 „1 . Поиск номера числа, равного текущему номеру, хранящемуся в счетчике 5, выполняется в ячейках 2, „1 -2k,(+a) с помощью элементов И 11, 117 и элемента

ИЛИ 12<. На выходе 20 переноса ячейки 2 <„„„1 (ь(, - номер строки, содержащей искомое число) формируется логйческая единица, которая по цепочке из элементов ИЛИ 7 -7 распространяется на управлякщие входы 15 соответствуницих ячеек 2 < — 2,„„„1 .

Кроме того, сформированная на выходе 20 пеРеноса Ячейки 2, m +Ä1 логическая единица через коммутатор 6 поступает на управляющие входы 15 ячеек 2 < - 2 (»„ выбранной строки М, . В результате число, записанное в ячейках 2 -2 „, „), теряется; числа. с их номерами, записанные в ячейках 2р, -2,,„+„1 (ф-(0 +1), (1+2),..., k), переписываются каждое в предыдущую (P-1) строку (т.е. в ячейке 2 (p <)„-2 f5 1),{meal ), а в ячейке 2k 2 к,(»нп1) k-" строки записываются нули.

На втором полутакте сигналом с выхода б генератора 3 импульсов триггер 4 устанавливается в нулевое состояние. Происходит поиск чисел, меньших, чем текущее, находящееся в регистре 1. На выходах переноса ячеек 2 „„- 2 „„строк, содержащих такие числа, формируется логическая единица, которая через коммутаторы бс поступает на входы 15» всех ячеек

2, -2 „„„1 анализа. В результате числа с йх номе рами, записанные в ячейках 2р -2у «п1 (=М, (0 +1), 96+2), ° .. (k-1)) переписываются каждое в последующую (+1)-ю строку (т.е. в ячейки 2(gt j, -2(p,) tmen) ), а затем по сигналу с выхода в генератора 3 импульсов в ячейку строки OC записывается текущее число с его номером.

Таким образом, на выходе 9 устройства на каждом i-м такте работы устройства формируется выборка чисел (А" k+ А1 112 ° ° Ai)» отсортиро ванная в порядке убывания.

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

Устройство для сортировки чисел, содержащее регистр и первую и вторую матрицы ячеек анализа, которое сои держат k-2 групп ячеек анализа соответственно по m и и ячеек анализа в группе, где k — апертура сортировки, m — количество разрядов со ртируемых чисел, причем каждая ячейка анализа содержит триггер, первый, второй, 5

l5

55

5 164 третий и четвертый элементы И и первый элемент ИЛИ, а каждая ячейка анализа. первой матрицы содержит, кроме того, пятый и шестой элементы И и второй элемент ИЛИ, причем вход i-го разряда сортируемого числа устройства, где i=1 2,..., m, соединен с информационным входом i-го разряда ре гистра, выход которо го соединен с первым информационным входом i-й ячейки анализа первой группы первой матрицы, первые информационные выходы iw u j.-й ячеек анализа 1-й группы соответственно первой и второй матриц, где j=1 2, ° ° °,n, 1=1,2,..., (k- 1), соединены с первыми информационными входами соответственно i-й и )-й ячеек анализа (1+1)-й группы той же матрицы, в каждой группе ячеек анализа выход переноса р-й и q-й ячеек анализа соответственно первой .и второй матриц, где р=1,2,..., (тп-1), q1,2, ° .., (n-! ) соединен с входом переноса соответственно (р+

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

4128 6

j-й ячейки анализа первой группы второй матрицы, вторые информационные входы i-й и j-й ячеек анализа 1-х групп соответственно первой и второй матриц подключены к вторым информационным выходам соответственно i-й и j-й ячеек анализа (1+1)-й группы той же матрицы, входы переноса первых ячеек анализа всех групп обеих матриц подключены к входу .логнческой единицы устройства, выходы переноса m-й и и-й ячеек анализа s-й группы соответственно первой и второй матрицы, где s-1,2,..., соединены соответственно с первым информационным входом s-го коммутатора и с первым входом s-ro элемента ИЛИ, выходы которых соединены соответственно с первыми и вторыми управляющнмн входами всех ячеек анализа s-й группы обеих матриц, выход переноса п-й ячейки анализа s-й группы второй матрицы соединен с вторым информационным входом s"ro коммутатора, выход 1-го элемента ИЛИ соединен с вторым входом (1+1)-го элемента ИЛИ, вторые информационные входы всех ячеек анализа k-й .группы обеих матриц подключены к входу логического нуля устройства, входа задания режима всех ячеек анализа первой и второй матриц подключены к входам соответственно логической единицы и логиче с ко го нуля устройства, первый выход генератора импульсов соединен с входом разрешения записи регистра и со счетным входом счетчика, первый н второй выходы генератора импульсов соединены с входами установки триггера соответственно в единичное и нулевое- состояния, прямой выход которого соединен с управляющими входами всех косачуTGTopoB > второй и третий выходы генератора импульсов соединены соответственно с первым и вторым тактовыми входами всех ячеек анализа обеих матриц, второй вход первого и третий вход 1<-х элементов

ИЛИ подключены соответственно к входам логическоro нуля и логической единицы устройства, третий. информаци.онный вход i-й ячейки анализа k-й группы первой матрицы является выходом i-го разряда k-ra числа отсортированной выборки устройства,в ячейках анализа второй матрицы второй информационный вход соединен с первым входом пятого элемента И, выход которого

1644128

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

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

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

Фиг.2

Со с тав и тель В. Го ро хо в

Редактор Е. Папп Техред Л. Сердюкова Коррек тор А. Обручар

Заказ 1241. Тираж 399 Подписное

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

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

Производственно-издательский комбинат "Патент", r.Óærîðîä, ул. Гагарина, 101