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

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

Иллюстрации

Показать все

Реферат

 

Предлагаемое устройство относится к области вычислительной техники и может быть использовано, например , при построении отладочных комплексов для определения частотности команд в отладочной программе. Цель изобретения - упрощение устройства. Устройство содержит триггеры 4 и 5,

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

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

РЕСПУБЛИК (51) 4 С 06 F 7/06

, т;г.

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 4084827/24-24 (22) 04.07.86 (46) 07,01.88. Бюл. Н 1 (72) В.А.Кривего, Н.H.Ïðîêoïåíêî, А.Н.Бобыльков и В.В.Кривего (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Ф 1183956, кл. G 06 Г 7/06, 1984.

Авторское свидетельство СССР

У 1196849, кл. С 06 F 7/06, 1984.

„„SU„„1365075 А1 (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ (57) Предлагаемое устройство относится к области вычислительной техники и может быть использовано, например, при построении отладочных комплексов для определения частотности команд в отладочной программе. Цель изобретения — упрощение устройства.

Устройство содержит триггеры 4 и 5, 1365075

CP: = c ОЗУ А, З где ОЗУ А.1

В связи с

40 предназначен счетчик Ь, генератор тактовых импульсов 8, группу элементов 2И-ИЛИ 9, блок памяти 10, реверсивный счетчик

11, дешифратор нуля 12, коммутатор

13, элементы И, ИЛИ. После записи сортируемых чисел в устройство в ячейках блока памяти по адресам, равным величине чисел, будет записано количество одинаковых чисел в массиИзобретение относится к вычислительной технике и может быть использовано, например, при построении отладочных комплексов для определения частотности команд в отладочной программе.

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

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

Предлагаемое устройство содержит информационные входы 1, тактовый вход 2, вход "Конец массива" 3, триггеры 4 и 5, счетчик 6, элемент И 7, генератор 8 тактовых импульсов, группу элементов 2И-ИЛИ 9, блок 10 памяти, ревероивный счетчик 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)., Каждый из этих импульсов (Y,-Y<) определяет шаг работы устройства.

Следовательно, процесс записи чисел производится за пять последовательно выполняемых микрокоманд.

На первом шаге микрокомандой У, 20 блок 10 памяти переводится в режим

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

По заднему фронту первой микрокоманды Y содержимое А . ячейки блока

1 памяти фиксируется на счетном регистре 11 знак присвоения; содержимое блока памяти с адресом, определяемым величиной числа. тем, что дешифратор. 12 для выделения нулевого

1365075 значения числа, то рассмотривают подробнее процедуру записи информации в реверсивный счетчик 11.

Особенность этой процедуры прояв5 ляется, когда предыдущее (перед записью) состояние реверсивного счетчика нулевое. Дешифратор 12 выделяет нулевое состояние реверсивного счетчика 11 и единичным сигналом с его выхода реверсивный счетчик должен обнуляться. Однако в момент действия микрокоманды У, работа дешифратора через элемент 2И-ИЛИ-НЕ 18 запреще" на, поэтому обнуляющий сигнал с К- 15 входа реверсивного счетчика 11 снят на время действия микрокоманды У, и создается условие для записи информации в реверсивный счетчик 11 по управляющему С-входу, но при этом 2р должно выполняться условие (n +л ) л (1) (л + л )<л + (2)

55 где л„ задержка микрокоманды У на блоке 19 задержки; время установки первого разряда счетного регистра.

n„

1 где ". — задержка на элементе э 25

2И-ИЛИ-НЕ 18;

1д — задержка в дешифраторе 12; время записи информации в инверсивный счетчик.

В противном случае для выполнения условия (1) в обнуляющую цепь необ30 ходимо ввести линию задержки.

Второй шаг — во время действия микрокоманды У в рассматриваемом режиме — холостой.

На третьем шаге передним фронтом З5 микрокоманды Y производится сумми3 рование единицы к содержимому реверсивного счетчика 11, зафиксированному на первом шаге. При этом имеется особый случай, когда содержимое ре- 4О версивного счетчика нулевое и дешифратор 12 может выделить обнуляющий сигнал для установки в нуль содержимого реверсивного счетчика, В этом случае прибавление единицы к нулю 45 стало бы невозможным. Для устранения этого явления на элементе 2И-ИЛИ-НЕ

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

На четвертом шаге микрокоманлой У

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

На пятом шаге триггер сбрасывается в нулевое состояние и процесс приема очередного числа прекращается.

Устройство готово для приема следующего числа. Процедура приема повторяется до тех пор, пока на устройство не поступает сигнал Конец массива .

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

Поскольку при поступлении на устройство сортируемые числа отмечаются числами в соответствующих ячейках

ОЗУ, то эти числа несут информацию о величине сортируемого числа и о количестве поступлений одинаковых чисел на вход устройства.

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

Таким образом, порядок ранжирования можно менять, изменяя начальную установку счетчика 6 или систему его счета.

В соответствии с изложенным поясняют работу устройства в режиме чтения чисел.

Режим чтения чисел осуществляется после поступления на вход устройства сигнала "Конец массива по шине 3, который устанавливает триггер 4 в состояние единицы (фиг.3, строки

1 и 2).

Триггер 5 сброшен на нуль.

1365075

На четвертом шаге (Y ) блок памяти переводится в режим записи, Производится запись содержимого реверсивного счетчика, измененного на третьем шаге, в ячейку блока 10, памяти, адрес которой определяется со- . держимым счетчика 6.

На пятом шаге микрокомандой (7 )

5 через элемент И 15 изменяется содержимое счетчика 6, если дешифратор 12 выделяет нулевое состояние реверсивного счетчика 11 и разрешает работу

55

Сигйалом с Ч-выхода открывается второе плечо группы элементов 2И-ИЛИ

9, реверсивный счетчик переводится в режим вычитания, разблокировывает5 ся (снимается обнуляющий потенциал) счетчик 6 адресов, разрешается работа коммутатора 13, через элемент ИЛИ 7 запускается генератор 8 тактовых импульсов, формирующий серию синхроим- 0 пульсов, на базе которой распределитель 14 формирует пять микрокоманд, определяющих пять шагов работы устройства в рассматриваемом режиме.

На первом шаге (микрокоманда Y ) 15

1 значение содержимого счетчика 6 поступает на адресный вход блока 10 памяти, которое микрокомандой Y переводится в режим чтения. Задним фронтом микрокоманды содержимое соответ- 20 ствующей ячейки блока памяти фиксируется в реверсивном счетчике 11.

Значение счетчика 6 поступает на коммутатор 13 (фиг.3, строки 5, 10 и 14). 25

На втором шаге (Y z), если значение содержимого счетного регистра 11 не нулевое, коммутатор 13 формирует на выходе 17 устройства значение счетчика 6 (фиг.3» строки 6, 11, 12 30 и 14).

Если на регистре 11 зафиксирован нуль, то дешифратор 12 запрещает работу коммутатора 13, и на выход 17 устройства информация не поступает.

На третьем шаге (Y ) через эле3 мент 19 задержки производится вычитание единицы из содержимого реверсивного счетчика 11. Если содержимое последнего нулевое, то вычитание не 40 производится, так как через дешифратор 12 нуля на обнуляющий P-вход счетчика подается обнуляющий сигнал, и реверсивный счетчик 11 остается в нулевом состоянии (фиг.3, строки 45

7 и 11). элемента И 15, в противном случае содержимое счетчика 6 не изменяется.

Работа устройства в соответствии с описанной цикличностью повторяется до тех пор, пока счетчик 6 не выделяет сигнал переполнения и не сбрасывает на нуль через элемент ИЛИ 16 триггер 4, после чего работа устройства прекращается. На выходе 17 устройства выделяется последовательность чисел, ранее (в первом режиме) поступившая на вход устройства.

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

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

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

2И-ИЛИ, причем тактовый вход устройства соединен с входом установки в единичное состояние первого триггера и первым входом первого элемента ИЛИ, выход которого соединен с входом ус1365075 триггера.

Выход ногистр. I

Выход шины CU2

Выход 47

Триггера о

Выход 47

Триггера 4

Выход нулю дидратора В ф ъ

Щ ) <

<4

< %>

o <<

Ъ ( ь з с, Padoma

ОЗУ/О

Работа счетного

Регистра fl

Фиг.Я тановки в нулевое состояние второго триггера, вход установки в единичное состояние которого является входом

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

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

1365075

Конец массида

Юь!ход

Триггерами

ВыхОд

Триггерами

Выход мул аиаратора

Раата счетчика Ю

Редактор М.Бланар

Заказ 6611/42 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4 о с %) о9 м b Ъ Ь

og о< о.

Рааата

ОЗУ/О

Раоата счетного

Регистра /

Раааа коммутатор

Выход

Лююща.

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

Техред Л. Сердюкова Корректор В.Гирняк