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

со

05 ел

о

СП

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

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

1

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

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

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

Предлагаемое устройство содержит информационные входы 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 сигналом с выхода

5

Ю

15 0

5

0

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

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

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

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

СР

«:ОЗУ А.7,

- знак присвоения;

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

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

Особенность этой процедуры проявляется, когда предыдущее (перед записью) состояние реверсивного счетчика нулевое. Дешифратор 12 вьщеляет нулевое состояние реверсивного счетчика 11 и единичным сигналом с его выхода реверсивный счетчик должен обнуляться. Однако в момент действия микрокоманды Y, работа дешифратора через элемент 2И-Р1ПИ-НЕ 18 запрещена, поэтому обнуляющий сигнал с R- входа реверсивного счетчика 11 снят на время действия микрокоманды Y , и создается условие для записи информации в реверсивный счетчик 11 по управляющему С-входу, но при этом должно выполняться условие

с:, + д) 1зп, (1)

где I - задержка на элементе

2И-ИЛИ-НЕ 18;

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

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

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

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

( - ) 2.,- ,

(2)

где задержка микрокоманды Yj

на блоке 19 задержки; 0. - время установки первого

разряда счетного регистра,

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

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

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

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

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

30

на вход устройства.

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

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

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

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

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

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

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

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

На первом шаге (микрокоманда Y ) значение содержимого счетчика 6 поступает на адресный вход блока 10 памяти, которое микрокомандой Y, переводится в режим чтения. Задним фронтом микрокоманды содержимое соответствующей ячейки блока памяти фиксируется в реверсивном счетчике 11. Значение счетчика 6 поступает на коммутатор 13 (фиг.З, строки 5, 10 и 14).

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

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

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

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

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

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

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

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

адресом соответствующей ячейки блока памяти.

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

Формула изобретения

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

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

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

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

Выход Г агистр. 1 Л.

Выход шины си 2

Выход Q Триггера 5

Выход а Триггера 4

Bt/Jtod бибратораВ

Работа ОЗУЮ

Работа счетного Регистра il

10

50758

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

20

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

Фиг 2

Конец naccuSa

Выход Триггера4

Выход Jриг г ера 5

Вь/ход нульти Sufpamopa 8

11 1

ч «о

а

Ра fото ОЗУЮ

Работа

сметного Регистра f{

Работа коммутатора /3

Bbfxod эленента.И 15

Работа счетчика б