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

яерст.лЧ г-1ыход которого подключен к . входу разрешения считывания регистра признака числа, элемента И в узлр упраплсння элемент зад;:ржfCH с вторым ХОДОМ ВТОрОГО

элемента i k-й ячейки анализа и cci счетчьм входом счетчика узла управления,; иход устано1 ки в ноль которого по-лкльгчен к запуска устройства и первому входу элемента ИЛМ, выход которого соединен с входом установки в нулег1ое состояние триггера опроса к:-и ячейки анрлиза, выход переполнения счетчика в узле управдел-гия подключен к второму входу эдемента и второму входу эле-1мента К -и ячейки анализа.

УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ЧИСЕЛ, содержао;ее N ячеек анализа, где N число сортируемых чисел, элементы ИЛИ-НЕ, элементы И и узел управления, включаюпи-ш генератор импульсов, элемент И и триггер, каждая ячейка анализа содержит дешифратор, группу выходных элементов И, группу элементов И, элементы И, , триггер, регистры числа и признака числа, причем информационные, входы регистров числа и признака числа k-M ячейки анализа соединены с информап.т-юнньми входами k-ft группы соотBC-TCTHeHiiO числа и признака числа ycTpoiiCTBa, где . 2,..., N , выходы разрядов регистров подключены к инр ормационным входам соответствующих выходных элементов И группы, выходы которых соединены с выходами V-и группы устройства, выходы /i CT piuHx разрядов регистра признака числа соединены с входами дешифратора, 1-и выход которого, где i 2,.,., о, d 2, подключен к первому входу (i-l)-ro элемента И группы, первый выход дешифратора подключеь; к первому выходу ячейки анализа и первому входу элемента ИЛИ, выход -го элемента И группы, где ,2,..., (d-1) соединен с (j+1)-M выходом ячейки анализа и (j-t-l)-M входом элемента ИЛИ, j-й выход V-и ячейки анализа соединен с Ic-M входом j-ro элемента ИЛИ-НЕ, выход которого соединен с входами элементов И с j-ro по (с-2)-й, второй вход j-ro элемента И группы каждой ячейки анализа соединен с выходом (j-l)-ro элемента И, выход первого элемента ИЛTi-HE соединен с вторым входом первого элемента И группы каждой ячейки анализа, вход пуска устройства соединен с входами установки в нулевое состояние триггеров всех ячеек анализа и входом установки в ji единичное состояние триггера узла (Л управления, вход установки в нулевое состояние которого подключен к входу останова устройства, в узле управления выход генератора импульсов сое- S динен с первым входом элемента И, |второй вход которого подключен к прямому выходу триггера узла управления, отличающееся тем, что, с целью повышения быстродействия в узел управления введены элемент задержки, элемент ИЛИ и счетчик, а в каждую ячейку анализа введены триггер опроса, элемент НЕ и второй элемент И, первый вход которого через элемент НЕ соединен с выходом элемента ИЛИ, выход второго элемента И соединен с входом установки в единичное состояние триггера опроса,выход которого подключен к входу разделения записи дешифратора и первому входу элемента И, выход которого соединен с управляющими входами выхода ных элементов И и входом установки в единичное состояние триггера, ин

3П

элемента И, выход пс-рвого элемента ИЛИ-НЕ сое/инен с вторым входом первого эл мсита И группы каждой ячейки анализа. Сортировка информации в устройстве осуществляется одновреме НБтм анализом разрядов признаков всех сортируемых чисел 2

Недостатком данного устройства также является его сложность.

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

Поставленная пель достигается тем, что в устройстве для сортировки чисел,, содержащем N ячеезс аиализа, где N - число сортируемт чх чисел, элементы 1ШИ-НЕ, элементы И и узел управления, включающий генератор импульсов, элемент И и триггер каждая ячейка анализа содержит дешифратор, группу вькод.чых э.пементов V-., группу элемантов И, элементы И, ИЛИ, триггер, регистры числа и призпака числа, причем информационные входы регистров числа и признака 1;-й ячейки анализа соединены с информационньЕми входами группь соответственно числа и призркака числа устройства, где 1 ,2,,,,, N , Быход з1 разрядов регистpO i подключены к информационньк входa ; соответствующих выходных элементов И Группы. выходы которых соедиHeHbi с Бьжодами k-и группы устройства, выходы Ii старших разрядов регистра признака числа соединены с входами дешифратора, i-й выход которого, где 2,..., d, о 2, подключен к первому входу (--1)-го элемента И группы, первый, выход дешифратора подключен к первому выходу ячейки анализа и первому входу элеме -:та ШИ, выход i -го элемента И гру:;пы, где j 1,2,... (cl-i) соетинен с (i + i)-M выходом ячейки анализа и (i + 1)--м входом элемента ИЛИ, j-й выход -и ячейки анализа соединен с -м входом i - г о э л и м е 1 гг а ПИ - Н К , в ьгх о д которого с;р:динен с входами элементов с 1-го по ,)-и, второй пход го элемента Pi группе каждой ячейки ана,ггиза соедиьон с выходом ( j--1) элемента И, выход первого ШГИ-НЕ соединен с втоPDIM нходпм первого : j:eMeHTa И группы каждой ячейки а: ал1-за, вход запуска устройства соединен: с входами устанорки в нулеясн. сосгоя:- ие триггеров

96054

всех ячеек анализа и входом установки р, единичное состояние триггера узла уп -авления, вход установки в нулевое состояние которого подклто- 5 чен к входу останова устройства, в

узле управления выход генератора им,пульсов соединен с первым входом эле-1ента И, второй вход которого подклтсчен к прямому выходу триггера

0 узла управления, в узел управления введены элемент задержки, элемент ИЛИ и счетчик, а в ячейку анализа введены триггер опроса, элемент НЕ II второй элемент И, первый

5 вход которого через элемент НЕ

coejir.HeH с вькодом элемента ИЛИ, выхо,, второго э.г;емента И соединен с входом установки в единичное состояние -i-pnrrepa опроса, выход которого

0 подключен к входу разделения записи деатифрглора и первому входу элемента И; выход которого соединен с управляющими входами выходных элементов И и входом установки в един1 ч-

5 ное состояние Tpiirrepa, инверсный выход которого подключен к входу разрешения считывания регистра признака числа, вьгход элемента И в узле управления через элемент задержки соединен с вторым входом второго элемента И k-й ячейки анализа и со счетным входом счетчика узла управления, вход установки в ноль которого подключен к входу запуска устройства и первому входу элемента ИЛИ, выход которого соединен с входо -. установки в нулевое состояние триггера опроса k-й ячейки анализа, выход переполнения счетчика в узле управления подключен к второму входу элемента ЯПИ и второму входу злемепта И V.-и ячейки анализа

па чертеже представлена структурная схема предлагаемого устройства

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

Устройство содержит ячейки 1 анализа, элемента ИЛ -1-НЕ 2, элементы ИЗ узел Д управления, регистр 5 признака числа, регистр 6 числа, группу

выходньсс элементов И 7, триггер 8, элемент И 9, дешифратор 10, триггер 11 опроса, второй элемент И 12, группу элементов И 13, выходной элеме т ИЛИ 14,. элемент ИЛИ 15 элемент 16 задержки, управляющий элемент И 7, счетчик 18, генератор . 19 iff.-nyjibcoB 5 триггер 20 узла управления, группу информационных входов S: 21; группу выходов 22 устройства, выход 23 счетчика, выход 24 элемента задержки, вход 25 запуска устройства, выход 26 элемента ШТИ блока управления, выход 27 первого элемента ИЛИ-FIE устройства, выходы 28, 29 и 30 первого, второго и i -2-го элементов И устройства соответст венно, вход 31 останова устройства, элемент НК 32.. Каждс е слово сортируемого массива состоит ип кода числа и п-разрядного кода прланака этого числа, Сортиро) чисел осуществляется по убыванию значений их признаков. (Причем выделение числа с максимальным зна гением признака осуществляет по шагам. На каждом uiare осутцествля ется аналиг разрядов признаков всех чисел. Вы/деление одного числа из сотугирурмо1чт массива осуществляется за - 1 / 3 тагов . 1п ист1:1Ы 5 ячеек предназначены для при;.-ма „ хранения и осуществлени сдвига на ;; разрядов одновременно ко/,он признаков чисел. Регис1ры 6 ячеек предназначены а.пу; приема и хранения сортируемых чисел. Запись кодов числа и признака в рег-исрь 5 и 6 осуществляется ; соотиетств тощей группе ин юрмапи ный BxojUii; 21 устройства. Группа выходных элементов И 7 .ячейки обеспечивает выдачу слова из рсгчсуров 5 я 6 потребителю, если он;1 окажете;:, результатом сортирозг:и Передача слова из регистров 5 и Ь п требителю ;1су1п,ествляется по соответствующей группе ин()ормацио1;иых выходов 22 устт)О 1Ства. Триггер 8 предназначен дJ:я исклю че-ИЯ нчеп1 р-1 из дaJ;I)HeЙIIIeгo aiajiHза в случае, если содержимое регпс:т pors 3 н 6 окажется peayJibTaioN сс;р- тиров к ti и будет вьудано потрс-бр те.гпо. Искочючение ячейки из дал(-.ней 1;аг анализа о-су;цествляется путем юддачи запрещающего потенциала с нулезогх) выхода триггера 8 на управляющий вход регистра 5 признака числа. Элемент И 9 обеспечивает вьщачу потребителю через группу выходных элементов И 7 результата сортировки Дещифратор 10 ячейки преобразует (1,-разрядную группу кода признака числа регистра 5 из двоичной cиcтe 5 счисления в однопозиционный код в виде разрешающего п(е Л1иалг. на одном из с/ fro 1ГЛХ- Д1Н. Тригге 1 1 1 опроса исклшчает ячейку из дальнейшего ана.чиза, если Б процессе сортировки -.начеиие а-ылизи1)уемой на данном iiiaie л -разря,:тHoii группы кода признака lie является максималы(1м, -:. лемент 11 9 обеспечивает с.-к-па потребителю. Второй элемент Я 12 обеспс ycTaHCJBKy триггера опроса в €:ли;;ич ное состояние, если в njiouecce спртироржн значение анализиру(-мо;| данном щаге р -разря/пюй группь: кода признака не является кг1ксг:мя -ьньм. Элемент Я 1 3 группь с номером каждой ячейки предназначен цля анализа 1 -1-го ВР:1хода деггифратора 10. В|| ход11ой -элемент ПК 32 ячсйк ; через второй элемент И 12 управляет работой триггера 11 . Элемент НИИ-ИГ 2 с померог-- 1 предназначен для анализа .лов первых выходов д,еп ифраторов 10 i-;;;ex ячеек, а элементы ИТИ-НН 2 с номерами , й-1 - для ана,г(иза по еит иалог выхолов (i-l)-x элементе И 13 группы всех ячеек. Каждый 1-й элемент И 3 прсдназначен для ана.лиза выходог первых j 3 цементов ИЛН-НЕ 2 устр,)йс ва . Элемент ИЛИ 15 прелназкаче- для управлении рабс ий тр1гггеров 1 i oiipoca всех ячеек 1 аналпза. Элемент 16 задержки, лчтразляющи элемент li 17, счетчгк 18, генератор 9 ;i триггер 20 предназнггчены для Ф :рмирован;-1я управляю1цих сшлалг в, обеслечиваюдих работу устрсл-й; гва. (. 18 (осуществляет счет импульсов гсшератооа 19. С :;ост -пле ;и;м с прлхода элемента 16 задержки подряд, Е iiMr:yj;b;-o гекерадора 19 ;;четчи-; оо)миру1-1 и; своем вы;-:о;;е с иг нал 1срепол1Ь;-иия , У с т р о с т в о р л б i: т а е т к с т а к т а м . В каждом такте устройстве Пг.:д1еляет из сортируемо о массив л. сдДО слслк;., з ачение признака которого в данном такте сортировки оказалось наибольшим. Каждый такт разбит на Р тагов. На первом aiaie каж/дого такта в устройстве осуществляется ар1ализ первой группы из разрядов кодов признаков всех сортируемых чисел, К началу очередного шяп каждого такта в регистрах 5 признаков чисел всех ячеек производится кольцевой сдвиг на одну группу разрядов, и устройст во ос тцбствляет в очередном шаге анализ очередной группы из ft разрядов кодов признаков ячеек, значение анализируемой группы разрядов признаков которых на предьщущем шаге оказались наибольшим Длитель.кость одного шага сортировки определяется периодом следования сигналов, формируемых узлом управления, длительность такта сортировки соответствует f периодам следования сигналов блока управления. Для запуска устройства на вход 25 запуска подается сигнал Пуск, который устанавливает в нулевое сос тояние счетчик 18 узла управления, триггер 3 и через элемент ШТИ 15 триггер 11 опроса каждой ячейки анализа, а также устанавливает в единичное состояние триггер 20 узла управления, который разрешает прохождение импульсов генератора 19 :;ерез управляющий -элемент И 17 на вход 16 задержки, С инверсног вывода триггера 8 разрешающий потенциал подается на управляющий вхо регистра 5, обеспечивая прохожг ение старшей группы из /3 разрядов кода признака на вход дешифратора 10, на управляющий вход которото подается разрешающий потенциал с инверс ного выхода триггера 11 опроса. Если в текущем шаге среди групп из .в разрядов анализируемых кодер признаков сортируемых слов найдется котя бы один с наиболывик значением го на первом выходе дегаифраторд 10 ячейки анализа, где хранится слово с этой группой разрядов кода призна ка., образуется разрешающий потенциа которья через первый элемент РШИ-НЕ 2 поступит на второй вход первого элемента И 13 группы каждой ячейки анализа ,а через элементы И 3 -- на вторые входы соответствуюших элемен тов И 13 группы всех ячеек анализа в качестве запрещающего потенциала. с.Зразом, единичный потенциал на входе элемента ИЛИ 1А и нулевой потенциал на выходе элемента КЕ 32 будет иметь место только в тех ячей ках анализа, в регистрах которых хранится слово, значение анализируемой группы разрядов признака которого, равно о1 , причем в остальны 058 ячейках на выходе элемента НЕ 32 образуется единичный потенциал, который с Ьоступлением с выхода 2Д 16 задержки импульса генератора 19 через элемент И 12 устаноЕИ триггер 1 1 опроса в единичное состояние, что обеспечивает исключение ячеек анализа из дальнейшего анализа в данном такте сортировки. Если в текущем шаге среди групп из fb разрядов анализируемых кодов признаков сортируемых слов наибольшим окажется группа с значением (), то единичный потенциал будет иметь место на вторых выходах дешифраторов 10 ячеек анализа, а на выходе первого элемента ИЛИ-НЕ 2 образуешься единичньш потенц}5ал, которьгй рсступает на второй вход первого элемента И 13 группы всех ячеек анализа и на первые входы всех эле sгнтoв И 3 устройства в качестве разрешающего потенциала, при этом нулевой потенциал с выхода второго элемента 1ШИ-НЕ 2 поступит на вторые входы элементов И 3, Нулевой потенциал с выхода 1-го элемента И 3 поступит на второй вход (j+1)-ro элемента- И 13 группы всех ячеек в качестве запрещающего потенциала. На выходе первого элемента И 13 группы и втором входе элемента ИЛИ 14 ячейки анализа, в регистрах 5 и 6 которой хранится слово, значение анализируемой группы разрядов признака которого равно d-1, образуется еди- -ничкьгй потенциал, при этом единичный потенциал с выхода элемента НЕ 32 остальных ячеек анализа аналогично предыдущему случаю обеспечит исключение их из анализа в последующих шагах данного такта сортировки и т„д„ Импульс с выхода 24 элемента 16 задержки поступает на сдвиговый вход регистра 5 всех ячеек, обеспечивая при этом кольцевой сдвиг его содержимого на ft, разрядов так, что на дешифратора 10 будут поступать PS разрядов очередной:-группы кода признака числа. Процесс анализа групп разрядов кодов признаков повторяется до поступления через линию 16 задержки на счетный вход 18 Е импульса генератора 19. С поступлением этого импульса счетчик формирует импульс переполнения, котп9рый через элемент И 9 ячеек, г-.чс зн чение признака числа окажется максршальным в данном такте сортировки, обеспечит г.-штыванис слов;-; из регистров 5 и 6,потребителю и установит триггер 8 в единичное с;ос тояние запрещающий потенциал, с нулевого выхода которого, воздействуя на управляюп;ий вход регистр а 5, исключит ячейку азшлиза из процесса сортировки в пос.педуюших тактах. Кроме того, импульс пер полнения счетчика 18 через элемент ИЛИ 15 установит в нулевое состояние триггеры 11 опроса всех ячеек анализа, что обеспечит вк.тгоче ние в процесс сортировки в очередном такте слов, содержащихся н реги страх 5 и 6 ячеек анализа, KOTO):iie были исключены из анализа в ходе ол

f/

f7 iB Sff МО 05 Для прекра1де ия процесса сортировки на вход 31 останова усгройства. сигнал Сстаион, Но этому сигналу триггер 2С блоки-рует импульсов генератора 19 на ыхпд блока уг;равления. Для сортировки путем вьде.тс 1;ия с.гюв по возрастанию их признаков ироРходимо в каждой ячейке анализа к пход;гм дешифратора 10 годкли чить инр- рсные выходы регистра 5, Оборудование от внедрения предilraeMOTo устройства с-.окр.: 1дается бо;тее чем в 6 раз, при с:ни-жении его быстродействия в Р раз, d с TOI мость одного образг а устройства уменьшается более чем на руп „