Устройство для сортировки информации

) 4 С 06 Г 7/06 СУДАРСТВЕННЫЙ КОМИТЕТ СССРО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ(57) устройст носитс ычислительной теники исполь ва н 24 Предлагаемоея к области в и может быть во от но,чных пэо р, при построении отл плексов для определения стотности мме. Цель команд иэобре ви С(56) АвторскоеИф 1183956, кл.Авторское сУ 1196849, кл. Бюл, В 1о, Н.Н.Прокопенко,В.В.Кривего88,8)свидетельство СССРС 06 Г 7/06, 1984.детельство СССР06 Р 7/06, 1984. отладочнои прогр ния - Упрощение уво содержит тригсчетчик Ь, генератор тактовых импульсов 8, группу элементов 2 И-ИЛИ 9,блок памяти 10, реверсивный счетчик11, дешифратор нуля 12, коммутатор13, элементы И, ИЛИ. После записисортируемых чисел в устройство вячейках блока памяти по адресам, равным величине чисел, будет записаноколичество одинаковых чисел в массиИзобретение относится к вычислительной технике и может быть исполь зовано, например, при построении отладочных комплексов для определениячастотности команд в отладочной программе.Цель изобретения - упрощение устройства,На фиг,1 представлена функциональная схема устройства для сортировкиинформации; на фиг.2 - временнаядиаграмма записи и ранжирования чисел; на фиг.3 - временная диаграммасмены рабочих режимов устройства.Предлагаемое устройство содержитинформационные входы 1, тактовыйвход 2, вход "Конец массива" 3, триггеры 4 и 5, счетчик 6, элемент И 7,генератор 8 тактовых импульсов, группу элементов 2 И-ИЛИ 9, блок 1 О памяти, ревероивный счетчик 11, дешифратор 12 нуля, коммутатор 13, распределитель 14 тактовых импульсов, элемент И 15, элемент ИЛИ 16, выходы 17,элемент 2 И-ИЛИ-НЕ 18, элемент 19 задержки,Устройство работает в режиме приема и сортировки чисел и режиме чтения отсортированных чисел.В режиме приема по входу 1 наустройство подаются числа, сопровождающиеся синхроимпульсами СИ, поступающими по входу 2 (фиг.2, строки1 и 2),По переднему фронту синхроимпульсаСИ при вводе каждого числа триггер 5устананливаетсн в единичное состояние, а триггер 4 через элемент И 16 -н нулевое (подтверждается исходное),При этом триггер 4 сигналом с выхода ве, При опросе блока памяти на выход устройства считываются адресаблока памяти, содержащие не нулевуюинформацию, причем каждый из этихадресов будет выведен столько раз,сколько единиц содержит код, зафиксированный в ячейке блока памяти сэтим адресом. 3 ил. устанавливает счетчик 6 адреса нануль, а триггер 5 сигналом с выходаоткрывает первое плечо элементов2 И-ИЛИ 9, обеспечивает режим сложения реверсивного счетчика 11 и черезэлемент И 7 запускает генератор 8,который формирует на своем выходе серию импульсов, период которых определяет работу распределителя 14 такто 10 вых импульсов (фиг.2, строки 3 и 5).Распределитель 14 формирует на своемвыходе пять тактовых импульсов(фиг.2, строки 6-10)Каждый из этих импульсов (У,-У)15 определяет шаг работы устройства.Следовательно, процесс записи чиселпроизводится за пять последовательновыполняемых микрокоманд,На первом шаге микрокомандой У,20 блок 10 памяти переводится в режим"Чтение" информации, т.е. на выходеблока считывается содержимое ячейки,адрес которой определяется величинойчисла. Число при этом через первоеплечо группы элементов 2 И-ИЛИ 9 поступает на адресный вход блока 10 памяти.По заднему фронту первой микрокоманды У содержимое А, ячейки блока1памяти фиксируется на счетном регистре 11 знак присвоения;содержимое блока памяти с адресом, определяемым величиной числа. тем, что дешифратор, 12 для выделения нулевогозначения числа, то рассмотривают подробнее процедуру записи информации в реверсивный счетчик 11.Особенность этой процедуры прояв 5 ляется, когда предыдущее (перед записью) состояние реверсивного счетчика нулевое. Дешифратор 12 выделяет нулевое состояние реверсивного счетчика 11 и единичным сигналом с его выхода реверсивный счетчик должен обнуляться. Однако в момент действия микрокоманды У, работа дешифратора через элемент 2 И-ИЛИ-НЕ 18 запреще" на, поэтому обнуляющий сигнал с К входа реверсивного счетчика 11 снят на время действия микрокоманды У, и создается условие для записи информации в реверсивный счетчик 11 по управляющему С-входу, но при этом 20 должно выполняться условие+", )( +, (2)55 где л задержка микрокоманды Уна блоке 19 задержки;время установки первогоразряда счетного регистра. где- задержка на элементе9 252 И-ИЛИ-НЕ 18;1 д - задержка в дешифраторе 12;время записи информации винверсивный счетчик,В противном случае для выполненияусловия (1) в обнуляющую цепь необ 30ходимо ввести линию задержки,Второй шаг - во время действиямикрокоманды У в рассматриваемомрежиме - холостой,На третьем шаге передним фронтом З 5микрокоманды У производится суммирование единицы к содержимому реверсивного счетчика 11, зафиксированному на первом шаге. При этом имеетсяособый случай, когда содержимое ре Оверсивного счетчика нулевое и дешифратор 12 может выделить обнуляющийсигнал для установки в нуль содержимого реверсивного счетчика, В этомслучае прибавление единицы к нулю 45стало бы невозможным. Для устраненияэтого явления на элементе 2 И-ИЛИ-НЕ18 в третьем такте рассматриваемогорежима выделяется запрещающий работудешифратора 12 сигнал, что обеспечивает выполнение суммирования.Приэтом должно выполняться условие На четвертом шаге микрокоманлой У1блок памяти переводится в режим записи информации. Измененное содержимоереверсивного счетчика 11 фиксируетсяв ячейку блока памяти с адресом, определяемым величиной подаваемого повходу 1 числа (фиг,2),На пятом шаге триггер сбрасывается в нулевое состояние и процесс приема очередного числа прекращается.Устройство готово для приема следующего числа. Процедура приема повторяется до тех пор, пока на устройство не поступает сигнал Конец массива,Таким образом, сами сортируемыечисла не заносятся в блок памяти, ониявляются лишь адресами для соответствующих ячеек блока памяти, в каждойиз которых суммируется количествопоступлений одинаковых по величинечисел,Поскольку при поступлении на устройство сортируемые числа отмечаютсячислами в соответствующих ячейкахОЗУ, то эти числа несут информацию овеличине сортируемого числа и о количестве поступлений одинаковых чиселна вход устройства.Если теперь на адресный вход блокапамяти подать ряд натуральных чисел,допустим, от нуля до п, а на выходустройства выводить числа из пятогоряда, повторяя их столько раз, сколько единиц содержится в соответствующей ячейке блока памяти или запрещатьвыдачу соответствующего числа, еслив соответствующей ячейке блока памятисодержится нуль, то на выходе устройства воспроизведена последовательность чисел в соответствии с порядком формирования натурального рядачисел,Таким образом, порядок ранжирования можно менять, изменяя начальнуюустановку счетчика 6 или систему егосчета,В соответствии с изложенным поясняют работу устройства в режимечтения чисел.Режим чтения чисел осуществляетсяпосле поступления на вход устройствасигнала "Конец массива по шине 3,который устанавливает триггер ч всостояние единицы (фиг.З, строки1 и 2),Триггер 5 сброшен на нуль, 1365075На четвертом шаге (У ) блок памяти переводится в режим записи, Производится запись содержимого реверсивного счетчика, измененного на третьем шаге, в ячейку блока 10, памяти, адрес которой определяется содержимым счетчика 6,На пятом шаге микрокомандой (У )5 через элемент И 15 изменяется содержимое счетчика 6, если дешифратор 12 выделяет нулевое состояние реверсивного счетчика 11 и разрешает работу 50 55 Сигйалом с ц-выхода открывается второе плечо группы элементов 2 И-ИЛИ 9, реверсивцый счетчик переводится в режим вычитания, разблокировывает 5 ся (снимается обнуляющий потенциал) счетчик 6 адресов, разрешается работа коммутатора 13, через элемент ИЛИ 7 запускается генератор 8 тактовых импульсов, формирующий серию синхроим пульсов, на базе которой распределитель 14 формирует пять микрокоманд, определяющих пять шагов работы устройства в рассматриваемом режиме.На первом шаге (микрокоманда У ) 15 значение содержимого счетчика 6 поступает на адресный вход блока 10 памяти, которое микрокомандой 1, переводится в режим чтения. Задним фронтом микрокоманды содержимое соответ ствующей ячейки блока памяти фиксируется в реверсивном счетчике 11. Значение счетчика 6 поступает на коммутатор 13 (фиг,3, строки 5, 10 и 14) . 25На втором шаге (У ), если значение содержимого счетного регистра 11 не нулевое, коммутатор 13 формирует на выходе 17 устройства значение счетчика 6 (фиг.3, строки 6, 11, 12 30 и 14).Если на регистре 11 зафиксирован нуль, то дешифратор 12 запрещает работу коммутатора 13, и на выход 17 устройства информация не поступает.На третьем шаге (У ) через эле 3мент 19 задержки производится вычитание единицы из содержимого реверсивного счетчика 11. Если содержимое последнего нулевое, то вычитание не 40 производится, так как через дешифратор 12 нуля на обнуляющий Р-вход счетчика подается обнуляющий сигнал, и реверсивный счетчик 11 остается в нулевом состоянии (фиг.3, строки 457 и 11). элемента И 15, в противном случае содержимое счетчика 6 не изменяется,Работа устройства в соответствиис описанной цикличностью повторяется до тех пор, пока счетчик 6 не выделяет сигнал переполнения и це сбрасывает на нуль через элемент ИЛИ 16триггер 4, после чего работа устройства прекращается. На выходе 17 устройства выделяется последовательностьчисел, ранее (в первом режиме) поступившая на вход устройства.Следовательно после записи сортируемых чисел в устройство в ячейкеблока памяти зафиксирован код, характеризующий количество поступлений,равных по модулю числам, величина(модуль) которых идентифицируетсяадресом соответствующей ячейки блокапамяти.При опросе блока памяти на выходвыведены (считаны) адреса ячеек блока памяти, содержащие не нулевую информацию, Причем каждый из этих адресов на выход устройства выведен столь"ко раз, сколько едичиц содержит код,зафиксированный в ячейке блока памяти с этим адресом,формула изобретения Устройство для сортировки информации, содержащее счетчик, блок памяти, реверсивный счетчик, дешифратор нуля, коммутатор, триггер, два элемента ИЛИ, генератор тактовых импульсов и распределитель тактовых импульсов, причем выходы разрядов счетчика соединены с соответствующими информационными входами коммутатора, информационные выходы блока памяти соединены с соответствующими информационными входами реверсивного счетчика, выходы разрядов которого соединены с информационными входами дешифратора нуля и соответствующими информационными входами блока памяти, вход разрешения чтения которого сое- динен с первым выходом распределителя тактовых импульсов, о т л и ч а ющ е е с я тем, что, с целью упрощения устройства, оно содержит второй триггер, элемент И, элемент 2 И-ИЛИ-НЕ, элемент задержки и группу элементов 2 И-ИЛИ, причем тактовый вход устройства соединен с входом установки в единичное состояние первого триггера и первым входом первого элемента ИЛИ, выход которого соединен с входом ус1365075 триггера. Выходногистр. /Выходшины СийВыход ЯТриггера 5Выход ОТриггера СВыход нулюЮидраторо В У( ф ъ Щ ) с 4 ъ%) ( ф ь цз сз,РодотаОЗУУО ОабстасчетногоРсгистраО тановки в нулевое состояние второго триггера, вход установки в единичное состояние которого является входом "Конец массива" устройства, а инверс 5 ный выход соединен с первым входом второго элемента ИЛИ, первым управляющим входом коммутатора, входом разрешения вычитания реверсивного счетчика, входом установки в нулевое состояние счетчика и управляющими входами первых элементов И, элементов 2 И-ИЛИ группы, информационные входы которых подключены к выходам соответСтвующих разрядов счетчика, выход переполнения которого соединен с вторым входом первого элемента ИЛИ, а счетный вход подключен к выходу элемента И, инверсный вход которого соединен с выходом дешифратора нуля, входом установки в нулевое состояние реверсивного счетчика и вторым управляющим входом коммутатора, стробирующий вход которого соед:анен с вторым выходом распределителя тактовых им пульсов, а выходы являются выходами устройства, информационный вход первого триггера подключен к входу логического нуля устройствч, а прямой выход соединен с вторым входом второго элемента ИЛИ, управляющими входами вторых элементов И, элементов2 И-ИЛИ группы, входом разрешениясложения реверсивного счетчика и первым входом первого элемента И, элемента 2 И-ИЛИ-НЕ, второй вход которого подключен к третьему выходу распределителя тактовых импульсов и через элемент задержки к счетному входу реверсивного счетчика, синхровходкоторого соединен с первым выходомраспределителя тактовых импульсов иобъединенными входами второго элемента И, элемента 2 И-ИЛИ-НЕ, выход которого подключен к управляющему входудешифратора нуля, выход второго элемента ИЛИ соединен с входом запускагенератора тактовых импульсов, выходкоторого соединен с входом распределителя тактовых импульсов, четвертыйвыход которого соединен с входом разрешения записи блока памяти, адресныевходы которого соединены с выходамисоответствующих элементов 2 И-ИЛИгруппы, информационные входы вторыхэлементов И которых являются информационными входами устройства, пятыйвыход распределителя тактовых импульсов подключен к прямому входуэлемента И и синхровходу первого1365015 Конецмассиоа Выход мул аиаратора Раоот ОЗУ/О Выход цементаРабогп чет чик Составитель Е,ИвановТехред Л. Сердюкова Гирня ор М,Бланар рре Подпиитета СССРткрытий Заказ 661 ВНИИПИ Г по дел 13035, Моск4/ аб л. Проектна Производственно-полиграфическое предприятие, г, Ужго ВыходТриггерами ВыходТриггерами Я ас %)з Ъ ЧЗсъч о Цъ С 3. РооотасчетногоРегистра //Рааааоммутотор Тираж 104дарственного кизобретений иЖ, Раушск