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

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

Цель изобретения - повышение надежности.

На чертеже изображена схема устройства,

Устройство содержит генератор 1 импульсов, счетчик 2, блок 3 памяти, коммутатор 4, элементы 5 и 6 запрета реверсивный счетчик 7, триггер 8,элементы И 9, 10 и 11, ИЛИ 12, НЕ 13 и 14, элемент 15 задержки, группу информационных входов 16, вход 17 разрешения записи, вход 18 начальной уста- ковки, тактовый вход 19, входы 20 и 21 записи и считывания, вход 22 начала- сортировки, группу информационных выходов 23 и выход 24 разрешения считывания.

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

В режиме очистки памяти сигнал с входа 18 начальной установки устанавливает счетчики 2 и 7 (не показано) в нулевое состояние. На входе 17 разрешения записи ус,танавливается О, запрещающий запись в счетчик 2, на входах 20 и 21 - потенциал О,разрешающий передачу через коммутатор и элемент НЕ 13 импульсов с выхода генератора 1, на выходах элементов i6 и 7 запрета - нулевой уровень.После этого на вход 22 подается сигнал, который устанавливает триггер 8 в единичное состояние. Далее с генератора 1 на счетчик 2 поступает пачка из 2 импульсов, где m - количество разрядов счетчика 2. Одновременно та же инвертированная пачка импульсов через коммутатор 4 и элемент НЕ 13 поступает на вход записи/считывания блока 3 памяти, устанавливая .его в режим записи. После полного пересчета счетчика 2 во всех ячейках блока 3 памяти записаны нули.

В режиме сортировки на входе 17 устанавливается потенциал I, разрешая запись чисел в счетчик 2 с информационных входов 16. На входах 20 и 21 устанавливаются соответственно уровни 1 и О, разрешая поступление на выход коммутатора 4 сигналов с тактового входа 19. В этом режиме на выходе элемента 5 зацрета устанавливается единичный потенциал, на выходе элемента 6 запрета -,нулевой потенциал. Сортируемьш массив из п различных по величине га-разрядных

чисел (п 2 °) поступает на входы 16, записывается в счетчик 2 и с его выхода поступает на адресные входы блока 3 памяти. Синхронно с каждым

числом на тактовый вход 19 поступает тактовый импульс, который через коммутатор 4 и элемент НЕ 13 поступает на вход записи/считывания блока 3 памяти. При этом сначала устанавливается режим чтения и, если состояние соответствующей ячейки памяти нулевое (т.е. поступившее число ранее не встречалось в сортируемом массиве), то через коммутатор 4,элемент 15 задержки и открытый элемент И 9 тактовый импульс поступает на суммирующий вход реверсивного счетчика 7.

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

По окончании режима сортировки задается режим считывания.

На входах 17, 20 и 21 устанавливаются соответственно потенциалы О, О и 1, на выходе элемента 5 - нулевой уровень, на выходе элемента 6 - единичный уровень. На вход 22 поступает сигнал, снимающий установку триггера 8 в единичное состояние. На вход 18 начальной установки подается импульс, устанавливающий счетчик 2 в нулевое состояние. С генератора 1 поступает пачка из импульсов. При этом на выходе 24 формируется 1 в случае наличия в сортируемом массиве числа, значение которого в порядке возрастания установлено на выходах 23.

При считывании из ячейки единичного значения импульс от генератора 1 через коммутатор 4, элемент 15 задержки и открытый элемент И 10 поступает на вычитающий вход реверсивного счетчика 7. Если при этом счетчик окажется в нулевом состоянии, то задним фронтом сигнала с вьЬсода элемента ИЛИ 12 триггер 8 устанавливается в нулевое состояние, чем вызывает прекращение поступления импульсов на счетный вход счетчика 2.

Если количество считанных единиц больше количества сортируемых, чисел, триггер 8 устанавливается в нулевое состояние раньше окончания режима считывания. Если количество единиц меньше, после окончания режима считы

вания на выходе элемента ИЛИ 12 устанавливается единичный уровень.

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

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

o

5

0

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

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

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

и

СЮ

Редактор Е. Копча

Составитель В. Горохов

Техред И.Попович Корректор А. Обручар

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

ВНИИПИ Государственного комитета СССР

по делам изобретений и открытий 113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Изобретение относится к области автоматики и вычислительной техники. Цель изобретения - повьшение надежности. Устройство содержит генератор импульсов, счетчики, блок памяти (БП), триггер, коммутатор, элементы И, ИЛИ-НЕ, элементы запрета и задержки. Сортируемые числа записываются в БП в виде единичного значения ячейки с адресом, равным поступившему числу. Одновременно, если данное число встречалось ранее в сортируемом массиве, значение реверсивного счетчика (PC) увеличивается на единицу. При считывании, которое производится последовательно по всем ячeйкa, БП, значение в PC уменьшается на единицу при наличии единицы в данной ячейке БП. После окончания процесса сортировки в PC при отсутствии ошибок находится нулевое значение. 1 ил. ю