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

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

Иллюстрации

Показать все

Реферат

 

Изобретение относится к вычислительной технике и может быть использовано для анализа процессов, в частности для определения функции распределения случайных процессов и для других вычислений, требующих сортировки значений переменных в зависимости от их величины и является усовершенствованием устройства Т... по а.с. № 1182510. Цель изобретения - повышение быстродействия устройства. Устройство содержит генератор I импульсов , группу регистров 4 и счетчиков 5, триггер 3, элемент И 4, группы элементов И 8, 10 и 16, два элемента И-НЕ 6 и 12, элемент задержки , группу триггеров 11 и группу элементов ИЛИ 9, элемент НЕ 17, дополнительный элемент 18 задержки. Введение третьей группы элементов И 16 позволяет производить предварительный анализ сортируемых чисел, если все они содержат в i-м разряде код О, то происходит увеличение содержимого всех счетчиков на вели чину 2. Соответственно количество тактов, затрачиваемых на сортировку, уменьшается на 2, что повышает быстродействие устройства. 1 ил. ел 14)

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

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

РЕСПУБЛИК (19) 01) (51)4 G 06 F 7!06

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ (61) 1182510 (21) 4046222/?4-24 (22) 31.03.86 (46) 07.07.87. Бил. Ф 25 (72) В.Н. Горшков, В.П. Невский, А.М ° Заяц и В ° Г. Терехов (53) 681.325 5 (088.3) (56) Авторское свидетельство СССР

Р 1182510, кл. G 06 F 7/06, 1984. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВЕИ ЧИСЕЛ (57) Изобретение относится к «ычислительной технике и может быть использовано для анализа процессов, в частности для определения функции распределения случайнь|х процессов и для других вычислений, требующих сортировки значений переменных в зависимости от их величины и является усовершенствованием устройства по а. с. Ф 1182510. Цель изобретения повышение быстродействия устройства.

Устройство содержит генератор 1 импульсов, группу регистров 4 и счетчиков 5, триггер 3, элемент И 4, группы элементов И 8, 10 и 16, два элемента И вЂ” НЕ 6 и 12, элемент задержки, группу триггеров II и группу элементов ИЛИ 9, элемент НЕ 17, дополнительный элемент 18 задержки.

Введение третьей группы элементов И

16 позволяет производить предварительный анализ сортируемых чисел, если все они содержат в 1-м разряде код "0", то происходит увеличение

С2 содержимого всех счетчиков на вели» е чину 2. Соответственно количество тактов, затрачиваемых на сортировку, уменьшается на 2, что повьппает быстродействие устройства. 1 ил.

ИЗ О() pe Т(I(I(0 О 1 ° 0 (I 1 ò(.Slfl((тl(IC JIII

Te lit ной ТCÕ1111K C и МО)1<ОТ б!)Il (1(ГПО

Цель изобретения — повышение быстродсйст«IIl!T устройства.

Нл чертеже г(редстл(<ленл cxet (a предллгаемого устройства.

Устройство для сортировки и чисел содержит генератор 1 импульсов, эле— .tc.(г И 2, триггер 3, группу нз и pe(I(((fpo«3 4...4 „«! ()че (<11!((ов 5, °...

1) ° ев)

) le!le((I И-III. 6, э leмент 7 -.лдерж т (.(!) группу из и элементов И о,,... )

8,, rpi.(Illy I(з элементо(3 ИЛИ 9

9., E

10,,...,10» 1 p (lil ((.. - I p!1(i epo)3

11 „,..., 11, элемент И-!!Е 12, !)ходы

1:3<)...,13„ сортируомьп: чисел, «3(( х д(1 14,..., I 4„pe(t(còðo(3, 13(txnLIII

l5,,...,15, счетчиков, группу эле«< .II f0â И 16, элс мент ИЕ 17, дополнигс. («.1(«)! элемент 18 э "

3; < ускл (1 выход 20 кош((! сортировки.

1)с!11(<(((((a ЛЛДОРжКП (ПЛ(УЛЬСОВ Э te:"< «тл 7 мош г(е периода c

Спт Г -i(i!(<) ) ) pet! ft;1 Ill 11 ) I <) С дС

«I;l< ОI< f 1(11 1<",1 > 1« .!1:, <111(< IIOj

У< тро cтво p(l()ol,:! т леду(0

lI(ipeLT, сс ртировкой (3 рс гистры 4 и счетчик(! 5 по вхот(ам 1 3„)... ) 13 (3 IP(I<-ЫВЛI<)тС)f ЧИС:IË, II(т;).)Ie)f:ËÏÈÅ СОРТИРР(т i,() (1!110I (t(В О ((IO I(.IÐ((f(

3:,с)дтl 13 13К ((сч;!(<)т и((форм(((;ион((ые

I! i/Òi )т) т)<()т(< ((1((

)(I < i()Pl 1 тб I (<(e Гт(нlт 1() 17())<, С Г О СУ— м < () с)т к()f(Kpe fit((х условий I(p«we«(efkI(< тб Ст!)Оl!С l-(<Л, Пр, I пс) с т у((г(еш<1(нл вход 19 импульс нс o нуcf(c)I<îão с пг ллл отрицательI(01) IfOJISIpITO(I fI3 нл (ыхо с )лс мен га

1<1, т (,.0ptf((p)) С 1 <.)t (. !((If((«ftf (Й СПГНЛЛ, щс < т(О()1 !1 Cff КЛК ((Лрап<(Е((Ь«11,1(1, тЛК И ((гтс)(сдо(<;! (cл! <(< 1.-< с((особом 1< зла(!сп1322257 2 поступающий на первые входы всех элементов И 16. Если все сортируемые числа в каком-либо или нескольких разрядах содержат "0"), то за счет сигналов на инверсных выходах регистров 4 откроются соответствующие элементы И 16. Это обеспечивает установку в 1" определенных разрядов всех счетчиков 5.

1О Через время задержки элемента

18 сигнал отрицательной полярности поступает на единичные входы триггеров 3 и Il,,...,ll устанавливая их в единичное состояние. С прямого выхода триггера 3 на первый вход элемента И 2 поступает сигнал "1". С прямых выходов триггеров ll,. ° ., ) ° ° ° )

11„ поступают сигналы на вторые входы элементов И 8,,...,8„. Импульсы с выхода генератора 1 поступают через элемент И 2, элементы И 8,...,8 н элементы ИЛИ 9,,...,9 на счетные

7 входы счетчиков 5„,...,5(,.

По каждому импульсу счетчики 5 увеличивают свое состояние на "I"., Импульс переполнения, в первую очередь) появляется на выходе счетчика, в котором было записано максимальное число. Этот отрицательный импульс по нулевому входу переключает в нулевое состояние соответствующий триггер 11 группы триггеров. С инверсного выхода этого триггера разрешающий сигнал поступает на второй вход со35 1<етст«бующего элемента И 1О и на вход элемента И-НЕ 12.

Одновременно отрицательный импульс переполнения поступает на соответствующий вход элемента И-НЕ 6. С его выхода положительный импульс, задержанный на элементе 7 задержки через

Открытый соответствующий элемент И

l0 соответствующий элемент ИЛИ 9 поступает на счетный вход сп1 ответствующего счетчика 5 и увеличивает его состояние на "1" ° Если счегчик 5 вырабатывает сигнал пере(<олнения при единичных сигналах во всех рлзрядах,он переходит в состояние, 50 когда во всех разрядах нулевые сигналы, Следующий импульс переполнения возникает на выходе того счетчика, в котором записано число, являющееся максимальным из оставшихся. Этим

55 отрицательным импульсом по нулевому входу сбрасывается в нулевое состояние следующий соответствующий триггер 11 из группы триггеров. С его

1 322257 4

1О

20

40 инверсного выхода разрешающий сигнал поступает на соответствующий вход элемента И-НЕ 12 и на второй вход соответствующего элемента И 10. С выхода элемента 7 задержанный импульс переполнения через открытые элементы

И 10 группы, через элементы ИЛИ 9 группы увеличивает на "1" состояние счетчиков, в которых выработался сигнал переполнения. Аналогично процесс сортировки продолжается для других чисел.

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

l1, с инверсного выхода которого сигнал разрешения поступает на второй вход соответствующего элемента И 10 и на соответствующий вход элемента

И-НЕ 12. При этом на входы элемента И-НЕ 12 с инверсных выходов всех триггеров 11 поступают сигналы "1" и по задержанному импульсу переполнения с выхода элемента 7 на выходе элемента И-НЕ 12 появляется сигнал нСортировка завершенан отрицательной полярности, который по нулевому входу сбрасывает в нулевое состояние триггер 3.

Сигнал "0" с прямого выхода триггера 3 поступает на первый вход элемента И 2 и запрещает прохождение импульсов генератора 1 на счетчики

5,,...,5 . Одновременно задержанный е ° ° ° э ° импульс переполнения с выхода элемента 7 через открытые элементы

И 10, элементы ИЛИ 9 увеличивает состояние счетчиков 5„,...,5„ на "1".

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

Пример. Необходимо произвести сортировку четырех чисел, которые записаны в следующем порядке: в регистре 4 и счетчике 5 находится максимальное число 00110 (младший

55 разряд справа ), в регистре 4 и счетчике 5 — второе по величине число 00101, в регистре 4 и счетчике 5 — число 00010, минимальное, число 00001 находится в регистре 4

1 и счетчике 5, . Счетчики 5 вырабатывают сигнал переполнения в случае, когда во всех разрядах будут "1".

При поступлении на вход 19 импульсного пускового сигнала отрицательной полярности на выходе элемента HE 17 формируется единичный сигнал, поступающий на первые входы всех элементов И 16. Так как в двух старших разрядах сортируемых чисел содержится код "0", то за счет сигналов на инверсных выходах регистров 4 открываются два соответствующих элемента И 16. Это обеспечивает установку в "1" двух старших разрядов всех счетчиков 5: в счетчике

5 находится число 11110, в счетчике

5 — число 11101, в счетчике 5 число 11010 и в счетчике 5, — число

11001.

Через время задержки элемента 18 импульсы генератора 1 начинают поступать на счетные входы счетчиков

5,...,5 . Импульс переполнения, в у ° ° ° 1 первую очередь, появится на выходе счетчика 5>, так как в нем было записано максимальное число. Импульс переполнения по нулевому входу сбросит в нулевое состояние триггер 11

3 в результате чего элемент И 8 зак3 роется для прохождения им ульсов генератора, а с инверсного выхода триггера ll> на второй вход элемента И 10 и на третий вход элемента

И-НЕ 12 поступит сигнал "1".

Одновременно импульс переполнения поступит через элемент И-НЕ 6 на элемент 7 задержки. Задержанный импульс переполнения через элемент И 10, элемент ИЛИ 9 запишет "0" в счет3 чик 5> . Следующим импульс переполнения возникнет на выходе счетчика 5

В по которому сбросится в нулевое состояние триггер l lq Элемент И 8 закроется для прохождения импульсов генератора с инверсного выхода триггера ll, сигнал "1" поступит на второй вход элемента И 10 и на второй вход элемента И-НЕ 12.

Задержанный импульс переполнения с выхода элемента 7 через элементы

И 10 и ИЛИ 9 запишет "0" в счетчик 5, а через элементы И 1О,.ИПИ 9

1322257

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

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

Техред А. Кравчук Корректор С. Шекмар

Редактор П. Гереши

Заказ 28б4/44 Тираж 672 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул, Проектная, 4

"1" в счетчик 5 . Следующи 1 им3 пульс переполнения появится на втором выходе счетчика 5>, по которому сбросится в нулевое состояние триггер

11 . Элемент И 8 закроется для про2 2 хождения импульсов генератора 1 на счетчик 5 . Сигнал "1" с инверсного выхода триггера 11 поступит, на второй вход элемента И 10 и на четвертый вход элемента И-НЕ 12 ° 10

Задержанный импульс переполнения с выхода элемента 7 через соответствующие элементы запишет "011 в счетчик 5, "1" — в счетчик 5, "2" в счетчик 5 . Последний импульс переполнения будет выработан на втором выходе счетчика 5» по которому устанавливается в нулевое состояние триггер 11, и будет запрещено прохождение .импульсов генератора 1 через 20 элемент И 8< .

С инверсного выхода триггера сигнал "1" поступит на второй вход элемента И 1О„ и на пятый вход элемента

И-HE 12. Так как на входы элемента

И-HE 12 с инверсных выходов триггеров 11 11 поступают сигналы

"1", по сигналу с выхода элемента 7 на выходе элемента И-НЕ 12 вырабатывается отрицательный сигнал 1 Сортировка завершена, по которому по нулевому входу сбрасывается в нулевое

6 состояние триггер 3 и запрещается прохождение импуль сов генератора 1 через элемент И 2.

Одновременно задержанный импульс переполнения с выхода элемента 7 через соответствующие элементы запишет 011 в счетчик 5„ 1111 — в счетчик

5, "2" — в счетчик 5, "3" — в счетчик 5 . Таким образом, в счетчик 5 будут записаны коды, соответствующие величине подлежащих сортировке чисел.

Устройство для сортировки чисел по .авт.св. 111 1182510, о т л и ч а ющ е е с я тем, .что, с целью повышения быстродействия, в него введены третья группа из м элементов И, элемент HE и дополнительный элемент задержки, выход которого соединен с единичными входами всех триггеров, а вход является входом запуска устройства и соединен через элемент НЕ с первыми входами элементов И третьей группы, инверсные выходы -х разрядов регистров группы, где =1,2,..., m подключены к входам с второго по (n+1)-й элемента И третьей группы, выход которого соединен с дополни11 11 тельными входами установки в 1 x-x разрядов всех счетчиков.