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

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

Известно устройство для упорядочивания чисел:, содержащее память для хранения подлежащих сортировке кодов чисел,-, буферные регистры, схемы сравнения узлы адресации, селекторы, узел передачи lj ,

Недостатком такого устройства является низкая производительность, обусловленная нерациональными- затра, тами времени на последоват€У1ьное сравнение кодов упорядочиваемой информации и затратами времени на выполнение oпepaцvIй над адресами кодов

Наиболее близкиг по технической сущности к предлагаемому устройству является устройство для з порядочива.ния чисел, содержащее п групп входных элементов И,; п входных регистров п групп элементов И перезаписи, (п-1) группу по п-в каждой группе схем сравнения, (п-1) группу по к в каждой группе триггеров, блок синхронизации группу элементов ИЛИ, реверсивные счетчикИг элементы И-НЕ, злементы задержки, блок памяти, причем информационные входы устройства соединены через группы входных элементов И с входами регистров, выходы каждого :.го входного регистра через элементы перезаписи подключены к первым иноюрмационньМ входам схем сравнения 1-й группы, выходы каждой схемы сравнения i rpynnbij где .,25 . . „ ,,П5 j t s2;,, „ 5 (n-l) S соединены с входаг-ш установки в еди ничное и нулевое состояния соответ™ ственно j-ro триггера i -и группы, вторые информационные входы каждой схемы сравненг1я подключены к выходам элементов И перезаписи (1+1)й группыJ выходы триггеров через элементы задержки и элементы

|Ю1И подключены к входам реверсивного Счетчика5 вьшоды которых через элементы И-НЕ и элементов ИЛИ подключены к входам блока пар-шти блок синхронизации содерлдат формиро ватели импульсов, элементы задержки триггеры элементы ИЛИ, И, И-НЕ счетчик, генератор тактовых 1-п пульсов с соответствующими связями 2 ,

Недостатком известного устройства является сложность технической реаши

зации при упорядочивании больших массивов информации.

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

Поставленная цель достигается тем что устройство для упорядочиван1 я чисел, содержащее блок памяти, tiepвый и второй счетчики,триггер, первый, второй и третий элементы ШШ, элемент И и блок синхронизации, включающий первый и второй триггеры, генератор тактовых импульсов и первый элемент И, первый вход которого подключен к выходу генератора тактовых импульсов, вход запуска устройства подключен к входу установки в 1 первого триггера,- содержит коммутатор и буферный запоминающий блок, информационные входы которого соединены с информационной шиной устройства, подключенной также к входам первого элемента ШШ и первой группе входов коммутатора, вторая группа входов которого подключена к выходам разрядов первого счетчика, а выходы - к адресным входам буферного запоминающего блока, выходы которого соединены с входами второго элемента ИЛИ и информационными входами блока памяти, адресные входы которого соединены с выходами разрядов второго счетчика, счетный вход которого соединен с выходом третьего элемента ИЛИ, первый вход которого соединен с прямым выходом триггера и первым входом элемента И, выход которого подключен к входу синхронизации триггера, Jянфopмaциoнный вход ко- торого соединен с выходом первого элемента ШШ, блок синхронизации дополнительно содержит второй и третий элементы И, причем вход конца записи устройства соединен с входом установки в О первого триггера блока синхронизации, прямой выход которого соединен с управляющим входом коммутатора, входом разрешения записи буферного запоминающего блока и первым входом второго элемента И блока синхронизации, второй вход которого подключен к выходу генератора тактовых импульсов, а выход соединен с входом записи буферного запоминающего блока, вторым входом элемента И, инверсный вьЕход первого триггера блока синхронизации подключен к второму входу первого элемента И, выход которого соединен с первым вхо

31

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

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

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

Блок 8 синхронизации содержит

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

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

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

Триггеры 11 и 16 представляют собой синхронные триггерыВ-типа, сра батывающие по заднему фронту синхросигнала. Триггер 15 - триггер Я-5-типа

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

Число К а(,,а,,. о. ,аг( из входного числового массива N записывается в буферный запоминающий блок 1 (фиг. 2), предварительно обнуленный, по адресу К, {ао,а, ,.. , ,апТ,. При отсутствии числа К; из входного мас034

сива N соответствующего блока 1 по данному адресу сохраняется нулевая информация.

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

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

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

Работа устройства начинается по сигналу Пуск, поступающему по входу 13 на первый вход 21 блока 8 синхронзации (фиг.4а). По этому сигналу первый триггер 15 по S-входу устанавливается в единичное состояние (фиг. 4). Уровень логической единицы с прямого выхода первого триггера 15 через четвертый выход 28 блока 8 синхронизации поступает на управляющий вход буферного запоминающего блока 1, переводя его в резким записи, и на управляющий вход коммутатора 3, переключая его на передачу информации из кодовой шины 12 .числа на адресные входы буферного запоминающего блока 1, Одновременно с этим сигнал Пуск устанавливает в единичное состояние по S-входу триггер 16 (фиг. 4 Ь), с выхода которого сигнал уровнем логической единицы поступает на управляющий вход генератора 20 импульсов и запускает его (фиг. 4). Импульсы с выхода генератора 20 импульсов через открытый по первому входу элемент И 17 уровнем логической единицы с прямого выхода триггера 15 в виде синхроимпульсов СИ1 поступают на первый выход 25 блока 8 синхронизации и далее на вход записи буферного запоминающего блока 1, на счетный вход триггера 11 через открытый элемент И 10 и на выходную щину синхронизации устройства (фиг. 4в).

Информация из числового массива N поступает по шине 12 устройства на

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

Одновременно с этим число К из входного массива чисел поступает на входы первого элемента ИЛИ 4, с выхода которого при , сигнал уровня логической единицы поступает на информационный вход триггера 11 (фиг. 4) и по заднему фронту импульсов,, поступающих на его синхровход, подтверждает его состояние. При наличии во входном массиве N хотя бы одного нулевого числа (К 0) на выходе первого элемента ИЛИ образует ся сигнал уровня логического нуля (фиг. 4), и триггер 11 переводится в нулевое состояние. Отрицательный перепад уровня, образованный на выходе триггера 11 (фиг. 4з) поступает через третий элемент ИЛИ 9 (фиг. 4 на счетный вход второго счетчика 7, и увеличивает его состояние на единицу, фиксируя тем самым в блоке 2 памяти нулевое число с нулевым приоритетом. Кроме того, сигнал уровня логического нуля с выхода триггера 11 поступает на второй вход элемента И и блокирует его, таким образом триггер 11 фиксирует только одно нулевое число при его наличии во входном числовом массиве N. Для окончания цикла записи входного массива чисел N в буферньй запоминающий блок 1 по входу 14 подается сигнал КЗП (фиг, ), который поступает через второй вход 22 блока 8 синхронизации на R-вход первог триггера 15 и устанавливает его в н левое состояние (фиг. А), при этом уровень логического нуля с прямого выхода триггера 15 через четвертый выход 28 блока 8 синхронизации поступает на управляющий вход буферно го запоминающего блока 1, переводя его в режим чтения, и на управляющи вход коммутатора 3, переключая его на передачу информации на адресные

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

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

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

первый вход третьего элемента И 19, второй вход которого через четвертый вход 24 блока 8 синхронизации подключен к выходу второго элемента ИЛИ 5. Таким образом, устройство

переводится в режим перезаписи информации из буферного запоминающего блока 1 в блок 2 памяти.

Первый и второй счетчики 6 и 7 являются счетчиками адреса соответ.ственно буферного запоминающего блока 1 и блока 2 памяти. Первый счетчик 6 находится в обнуленном состоянии и указывает нулевой адрес буферного запоминающего блока 1, состояние второго счетчика 7 определяется наличием нулевого числа во входном массиве чисел N и указывает либо нулевой адрес блока 2 памяти, либо первый. I Информация, считываемая из буферного запоминающего блока 1, поступает на информационные входы блока 2 памяти и на входы второго элемента ИЛИ 5, на выходе которого образуется сигнал с задержкой t-g (в время выборки информации из буферного запоминак)щего блока 1), который через четвертый вход 24 блока 8 синхронизации стробирует по второму входу третий элемент И 19, ня выходе которого формируются синхроимпульсы СИЗ, поступающие на вход записи блока 2 памяти и синхровкод второго счет- чика 7. По нулевому адресу буферного запоминающего блока 1, а также по адресам, по которым не происходила запись, находится нулевая информация, которая, будучи считанная из буферного запоминающего блока 1, поступает на входы второго, элемента ИЛИ 5 (фиг. 4л) и вызывает появление на его выходе уровня логического нуля. 7 который блокирует по.второму входу третий элемент И 19 блока 8 синхронизации и, таким образом, в данном случае синхроимпульсы СИЗ не формируются (фиг. 4ч), запись в блок 2 па мяти не происходит, второй счетчик 7 своего состояния не изменяет. По заднему фронту СИ2 первый счет чик 6 изменяет свое состояние, т.е. переключает буферный запоминающий блок 1 на следующий адрес К. При наличии по заданному адресу числа К оно считывается из буферного запоминающего блока 1, причем на выходе второго элемента ИЛИ 5 появляется уровень логической единицы (фиг. 4) который открывает элемент И 19 блока 8 синхронизации, и на его выходе формируется импульс СИЗ (фиг. 4м), который через третий выход 27 блока 8 синхронизации поступает на вход записи блока 2. памяти и записывает в него по заднему фронту число К по адресу В(. Одновременно по заднему фронту СИЗ через третий элемент ИЛИ 9 (фиг1 4н) переключается второй счетчик 7 на следующий адрес Вл, а по заднему фронту СИ2 первый счетчик переключается .на адрес К и т.д. После опроса последнего адреса буферного запоминающего блока на выходе переноса первого счетчика 6 форми руется импУльс переноса (фиг. 4 о) , кото рый поступает через третий вход 23 бло ка 8 синхронизации на синхровход второго триггера 16 и по заднему фронту устанавливает его в нулевое состояние (фиг. .4Ь), блокируя тем самым генератор 20 импульсов. На это 038 . режим перезаписи информации из бу- ферного запоминающего блока 1 в блок 2 памяти прекращается. Таким образом, посл,е перебора всех адресов буферного запоминающего блока 1 в блоке 2 памяти будут записаны в порядке возрастания адреса (приоритета) Кщ упорядочиваемых чисел из входного массива. Объем буферного запоминающего блока 1 определяется по формуле QM4 2 где п - разрядность числа. Объем блока 2 памяти определяется по формуле бп ° г Преимуществом предлагаемого устройства является упрощение устройства высокое быстродействие, так как отсутствует последовательный перебор чисел с целью определения максимального (минимального) числа из оставшихся. Кроме того, практически нет ограничения на качество упорядочиваемых чисел (ограничивается емкостью буферного запоминаю0|его устройства) , можно получить однородную наращиваемую структуру, устройство позволяет легко вводить ранжирование чисел или дополнительные признаки для решения конкретной задачи. Применение предлагаемого устройства по сравнению с известным устройством упорядочивания чисел в составе базового устройства А8 позволило сократить оборудование на 30%.

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

АЗресКа

Hynftaj имфе нацшЛ

AOpecKt MfecKi t

А9ресК„

Нуле f ал информяцо

АвресКн

ВП

АдресЬн-i

ЧисаоКт ASpecbfi

ЧиСПО Kff

Фиг 3 . гъп У-LJ Ч лТТЛ гип