Устройство для упорядочивания чисел

 

УСТРОЙСТВО ДЛЯ УПОРЯДОЧИВА-. НИЛ ЧИСЕЛ, содержащее блок памяти, первый и второй счетчики, триггер, первый, второй и третий элементы ИЛИ, элемент И и блок синхронизации, включающий первый и второй триггеры, генератор тактовых импульсов и первый элемент И, первый вход которого подключен к выходу генератора тактовых импульсов, вход запуска устройства подключен к входу установки в 1 первого триггера, о т л и ч а юц е е с я тем, что, с целью его упрощения , оно содержит коммутатор и буферный запоминающий блок, информационные входы которого соединены с информационной виной устройства, подключенной также к входам первого элемента ИЛИ и первой группе входов коммутатора , вторая группа входов которого подключена к выходам разрядов первого счетчика, а выходы - к адресным входам буферного запоминающего блока, выходы которого соединены с входами второго элемента ИЛИ и информационными входами блока памяти, адресные входы которого соединены с выходами разрядов второго счетчика, счетный вход которого соединен с вы ходом третьего, элемента ИЛИ, первый вход которого соединен с прямьм выходом триггера и первым входом элемента И, выход которого.подключен к входу синхронизации триггера, информационный вход которого соединен с выходом первого элемента ИЛИ, блок синхронизации дополнительно содержит второй и третий элементы И, причем вход конда записи устройства соединен с входом установки в О первого триггераблока синхронизации, прямой выход которого соединен с управляющим входом коммутатора, входом разрешения записи буферного запоминающего блока и первым входом второго элемента И блока синхронизации, второй вход ко (Л торого подключен к выходу генератора тактовых импульсов, а выход соединен с входом записи буферного запоминающего блока, вторым входом элемента И, выход первого тригге ,ра блока синхронизации подключен к второму входу первого элемента И. выход которого соединен с первым входом третьего элемента. И и счетным входом первого счетчика, выход переполнения которого соединен с синхровходом второго триггера блока синсо хронизации, вход установки в единичное состояние которого подключен к входу запуска устройства, информационный вход второго триггера блока синхронизации соединен с шиной логического нуля, а выход - с управляющим входом генератора тактовых импульсов , второй вход третьего элемента И блока синхронизации подключен к выхлду второго элемента ИЛИ, а выход соединен с входом записи блока памяти и вторым входом третьего элемента ИЛИ.

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

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

РЕСПУБЛИК (!9) ())) 4(5!) G 06 F 7/06 «

««" =,«..

««}

« /«

:c") " «@ jg p

Я,) ь,., r

ОПИСАНИЕ ИЗОБРЕТЕ К ABTOPCHOMY СВИДЕТЕЛЬСТВУ

ГОСУДАРСТ8ЕННЫЙ НОМИТЕТ. СССР

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

«

« (21) 3639556/24-24 (22) 06.09.83 (46) 07.03.85. Бюл. - 9 (72) А.Н. Елагин, А.А. Филимонов, В.Е, Тимофеенко и F..ß. Ваврук (53) 681.325.5(088.8) (56) 1. Патент США № 3931612, кл. G 06 F 7/02, 1976.

2. Авторское свидетельство СССР № 932487, кл. G 06 F 7/06, 1980 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ УНОРЯДОЧИВА- .

НИЯ ЧИСЕЛ, содержащее блок памяти, первый и второй счетчики, триггер, первый, второй и третий элементы ИЛИ, элемент И и блок синхронизации, включающий первый и второй триггеры, генератор тактовых импульсов и первый элемент И, первый вход которого подключен к выходу генератора тактовых импульсов, вход запуска устройства подключен к входу установки в

"1" первого триггера, о т л и ч а юц е е с я тем, что, с целью его упрощения, оно содержит коммутатор и буферный запоминающий блок, информационные входы которого соединены с информационной ниной устройства, подключенной также к входам первого элемента ИЛИ и первой группе входов коммутатора, вторая группа входов кото1 рого подключена к выходам разрядов первого счетчика, а выходы — к адресным входам буферного запоминающего блока, выходы которого соединены с входами второго элемента ИЛИ и инфор.мационными входами блока памяти, адресные входы которого соединены с выходами разрядов второго счетчика, счетный вход которого соединен с выФ ходом третьего. элемента ИЛИ, первый вход которого соединен с прямым выходом триггера и первым входом элемента И, выход которого. подключен к входу синхронизации триггера, информаци-. онный вход которого соединен с выходом первого элемента ИЛИ, блок синхронизации дапблнительно содержит второй и третий элементы И, причем вход конда записи устройства соединен с входом установки в "0 первого триггера блока синхронизации, прямой

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

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

1144

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

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

Наиболее близким па технической сущности к предлагаемому устройству является устройство для упорядочива.ния чисел, содержащее п групп входных элементов И, и входных регистрав,-, и групп элементов И перезаписи, (n — 1) группу по п в каждой группе схем сравнения, (n-1) группу по к в каждой группе триггеров, блок синхронизации, группу элементов ИЛИ, реверсивные счетчики, элементы И-НЕ, элементы задержки, блок памяти, приЗО чем информационные входы устройства соединены через группы входных элементов И с входами регистров, выходы каждого 1.-го входного регистра через элементы перезаписи подключены M к первым информационным входам схем сравнения -й группы, выходы каждой j é схемы сравнения i-группы, где i=1.2...,.,n. j=1,2„, (п-1), соединены с входами установки в еди- @

Рп

Ф ничное и нулевое состояния соответственно j-го триггера -й группы, вторые информационные входы каждой

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

Недостатком известного устройства является сложность технической реали1ОЗ 2 зации при упорядочивании больших массивов информации.

Цель изобретения — упрощение устройства °

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

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

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

На фиг. 1 схематически представлен алгоритм упорядочивания чисел; на фиг, 2 — блок-схема устройства; на фиг. 3 — блок-схема блока синхронизации; на фиг. 4 — временная диаграмма, поясняющая работу устройства.

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

И 10, триггер 11, информационную шину 12, вход 13 запуска, вход 14 конца записи, 1

Блок 8 синхронизации содержит первый триггер 15, второй триггер 16, первый, второй и третий элементы . 35

И 17 — 19, генератор 20 импульсов, входы 21-24, выходы 25-28 °

Счетчики 6 и 7 представляют собой двоичные счетчики, срабатывающие по заднему фронту синхросигиала. 40

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

Триггеры 11 и 16 представляют собой синхронные триггеры1)-типа, срабатывающие по заднему фронту синхросигнала. Триггер 15 - триггер 8-9-типа.50

Сущность работы устройства заключается в следующем (фиг. 1).

Число K„=(a,aq а„ иэ входного числового массива И записывается в буферный запоминающий блок 1 55 (фиг. 2), предварительно обнуленный, ло адресу К;= (ae,à,,...,a„). При отсутствии числа К, из входного мас103 сива N соответствующего блока 1 ло данному адресу сохраняется нулевая информация.

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

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

В исходном состоянии буферный. запоминающий блок 1, блок 2 памяти, первый 6 и второй 7 счетчики, первый 15 и второй 16 триггеры блока 8 синхронизации обнулены, триггер 11 установлен в единичное состояние.

Работа устройства начинается по сигналу "Пуск", поступающему ло входу 13 на первый вход 21 блока 8 синхронизации (фиг.4а) . По этому сигналу первый триггер 15 по S-входу устанавливается в единичное состояние (фиг. 40). Уровень логической единицы с прямого выхода первого триггера 15 через четвертый выход 28 блока

8 синхронизации поступает на управляющий вход буферного запоминающего блока 1, переводя его в режим записи, и на управляющий вход коммутатора 3, переключая его на передачу информации из кодовой шины 12 .числа на адресные входы буферного запоминающего блока 1. Одновременно с этим сигнал . Пуск" устанавливает в единичное состояние по S-входу триггер 16 (фиг. 4Ь), с выхода которого сигнал уровнем логической единицы поступает на управляющий вход генератора 20 импульсов и запускает его (фиг. 4 ).

Импульсы с выхода генератора 20 импульсов через открытый по первому входу элемент И 17 уровнем логической единицы с прямого выхода триггера 15 в виде синхроимпульсов СИ1 поступают на первый выход 25 блока 8

О синхронизации и далее на вход записи буферного запоминающего блока 1, на счетный вход триггера 11 через открытый элемент И 10 и на выходную шину синхронизации устройства (фиг. 4e).

Информация из числового массива

N поступает по шине 12 устройства на

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

СН1 поступающих на вход записи в соответствии с адресом, формируемым 5 коммутатором 3. При этом, так как коммутатор 3 подклйчает на адресные входы буферного запоминающего блока

1 информацию с первых входов, подклю. ченных к шине 12 устройства, число

К из входного массива N записываетЬ ся по адресу К, число К < — по адресу К и т.д.

Одновременно с этим число К из входного массива чисел поступает на 15 входы первого элемента ИЛИ 4, с выхода которого при К О, сигнал уровня логической единицы поступает на информационный вход триггера 11 (фиг. 4i) и по заднему фронту импуль. 20 сов,. поступающих на его синхровход, подтверждает его состояние. При наличии во входном массиве М хотя бы одного "нулевого" числа (К = О) на выходе первого элемента ИЛИ образует- 2 ся сигнал уровня логического нуля (фиг. 4 ), и триггер 11 переводится в нулевое состояние. Отрицательный перепад уровня, образованный на выходе триггера 11 (фиг. 45) поступает 30 через третий элемент ИЛИ 9 (фиг. 4а) на счетный вход второго счетчика 7, и увеличивает его состояние на единицу, фиксируя тем самым в блоке 2 яти нулевое число с нулевым" приоритетом. Кроме того, сигнал уровня логического нуля с выхода триггера 11 поступает на второй вход элемента И и блокирует его, таким образом триггер 11 фиксирует только одно ".нулевое число" при его наличии во входном числовом массиве N.

Для окончания цикла записи входного массива чисел N в буферный запоминающий блок 1 по входу 14 подается сигнал КЗП (фиг. 4 ), который поступает через второй вход 22 блока 8 синхронизации íà P;вход первого триггера 15.и устанавливает его в нулевое состояние (фиг. 4 ), при этом уровень логического нуля с прямого выхода триггера 15 через четвертый выход 28 блока 8 синхронизации поступает на управляющий вход буферного запоминающего блока 1, переводя его в режим чтения, и на управляющий вход коммутатора 3, переключая его на передачу информации на адресные входы буферного запоминающего блока

1 с вторых выходов, подключенных к информационным выходам первого счетчика 6. Одновременно с этим сигнал уровня логического нуля поступает на первый вход первого элемента И 17 блока 8 синхронизации и блокирует

его, а сигнал уровня логической единицы с инверсного выхода триггера

15 открывает по первому входу второй элемент И 18, на выходе которого появляются синхроимпульсы СИ2 (фиг. 4 s), поступающие на второй выход 26 блока 8 синхронизации и на первый вход третьего элемента И 19, второй вход которого через четвертый вход 24 блока 8 синхронизации подключен к выходу второго элемента ИЛИ 5. Таким образом, устройство переводится в режим перезаписи информации из буферного запоминающего блока 1 в блок 2 памяти.

Первый и второй счетчики 6 и 7 являются счетчиками адреса соответ;ственно буферного запоминающего блока ll и блока 2 памяти. Первый счетчик 6 находится в обнуленном состоянии и указывает нулевой адрес буферного запоминающего блока 1, состояние второго счетчика 7 определяется наличием "нулевого" числа во входном массиве чисел N и указывает либо нулевой адрес блока 2 памяти, либо первый, Информация, считываемая из буферного запоминающего блока 1, поступает на информационные входы блока 2 памяти и на входы второго элемента

ИЛИ 5, на выходе которого образуется и сигнал с задержкой (— время выборки информации из буферного запоминающего блока 1), который через четвертый вход 24 блока 8 синхронизации стробирует по второму входу третий элемент И 19, на выходе которого формируются синхроимпульсы СИЗ, поступающие на вход записи блока 2 памяти и синхров од второго счет чика 7.

По нулевому адресу буферного запоминающего блока 1, а также по адресам, по которым не происходила запись, находится "нулевая" информация, которая, будучи считанная из буферного запоминающего блока 1, поступает на входы второго, элемента ИЛИ 5 (фиг. 4n) и вызывает появление на его выходе уровня логического нуля, 1144

Адрес Н

/Фуле1ая аи<аариая

А арес b»

АФрес32

АФес b2

Адрес НС

А ресН2

Аарес Н

Наес/а.е фа рармаа

Ааресs

А Юресаа-/

Адрес Ь,» который блокирует по,второму входу третий элемент И 19 блока 8 синхронизации и, таким образом, в данном случае синхроимпульсы СИЗ не формируются (фиг. 4 ц), запись в блок 2 памяти не происходит, второй счетчик своего состояния не изменяет.

По заднему фронту СИ2 первый счетчик 6 изменяет свое состояние, т.е. переключает буферный запоминающий блок 1 на следующий адрес К1. При наличии по заданному адресу числа К

1 оно считывается из буферного запоминающего блока 1, причем на выходе второго элемента ИЛИ 5 появляется уровень логической единицы (фиг. 4ь), который открывает элемент И 19 блока 8 синхронизации, и на его выходе формируется импульс СИЗ (фиг. 4щ), который через третий выход 27 блока

8 синхронизации поступает на вход записи блока 2.памяти и записывает в него по заднему фронту число К 1 по адресу В 1. Одновременно по заднему фронту СИЗ через третий элемент д

ИЛИ 9 (фиг . 4н) переключается второй счетчик 7 на следующий адрес В», а по заднему фронту СИ2 первый счетчик переключается на адрес К и т.д.

После опроса последнего адреса буферного запоминаюшего блока на вы ходе переноса первого счетчика 6 формируется импульс переноса(фиг.4о),который поступает через третий вход 23 блока 8 синхронизации на синхровход второго триггера 16 и по заднему

35 фронту устанавливает его в нулевое состояние (фиг. 4 L) блокируя тем самым генератор 20 импульсов. На этом

1ОЗ 8 . режим перезаписи информации из буферного запоминающего блока 1 я блок

2 памяти прекращается °

Таким образом, после перебора всех адресов буферного запоминающего блока 1 в блоке 2 памяти будут записаны в порядке возрастания адреса (приоритета) К> упорядочиваемых чисел из входного массива.

Объем буферного запоминающего блока 1 определяется по формуле (1= и ° 2 и. Sl3 где n — - разрядность числа.

Ф

Объем блока 2 памяти определяется по формуле (= nlog n.

Бп

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

Применение предлагаемого устройства по сравнению с известным устройством упорядочивания чисел B составе базового устройства А8 позволило сократить оборудование на ЗОЖ.

1144103

1144103 о

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

Редактор P. Цицика Техред А.Кикемезей Корректор В. Синицкая

Заказ 931/40 Тираж 710 Подписное

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

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

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