Устройство для сортировки информации
Изобретение относится к вычислительной технике и может быть использовано в системах обработки данных. Цель изобретения - повышение быстродействия за счет параллельного выполнения процессов выдачи упорядоченной последовательности и подготовки устройства к приему последующей сортируемой последовательности. Устройство имеет три режима работы: очистка памяти, сортировка, считывание. Однако в отличие от устройства-прототипа очистка памяти производится в два раза быстрее и только для первой сортируемой последовательности. Для последующих сортируемых последовательностей режим очистки совмещается с режимом считывания. 2 ил.
СООЗ СОВЕТСНИХ
СОЦИАЛИСТИЧЕСНИХ
РЕСПУБЛИН
А1 (51) С 06 Г 7/00
ГОСУДАРСТВЕННь1Й КОМИТЕТ
ПО ИЗОБРЕТЕНИЯМ И ОТКРЬГГИЯМ
ПРИ ГКНТ СССР
И ABTOPCHOMV СВИДЕТЕЛЬСТВУ
1 (21) 4049759/24-63 (22) 03,04,86 (46) 15.11.90. Бюл. N: 42 (72) В,С.Лунинов (53) 681,325(088.8) (56) Авторское свидетельство СССР
N 1073770, кл. С 06 F 7/00, 1984.
Авторское свидетельство СССР
Р 1183956, кл, С 06 F 7/06, 1985. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ (57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки данИзобретение относится к вычислительной технике и может быть использовано в системах обработки информации.
Цель изобретения — повышение быстродействия устройства.
На фиг. 1 приведе a структурная схема устройства; на фиг. 2 — структурная схема блока синхронизации.
Устройетво для сортировки информации содержит блоки 1 и 2 памяти, счетчики 3 и 4, блок 5 сичхронизации, элемент lE б, информационные входы 7 и 8, входы 9-11 управления, информационные выходы 12 и 13, выходы 14 и 15 управления, элементы
ИЛИ .6-19, элементы 20 и 21 задержки, элементы И 22-26, элемент И"ИИ 27, триггеры 28 и 29, счетный триггер 30, Блок 5 синхронизации содержит генератор 31 импульсов, регистр 32, „„5U„„1бО6972 ных. Цель изобретения - повышение быстродействия за счет параллеЛьного выполнения процессов выдачи упорядоченной последовательности и подготовки устройства к приему последующей сортируемой последовательности. Устройство имеет три режима работы: очистка памяти, сортировка, считывание, Однако в отличие от устройствапрототипа очистка памяти производится в два раза быстрее и тол -ко для первой сортируемой последовательности.
Для последующих сортируемых последовательностей режим очистки совмещается с режимом считывания, 2 ил. че ифратор 33, чементы И 34-36 формирователь 37.
Устройство работает следующим образом, Режим Очистка памяти", Режим задается комбинацией "01" на входах
9 и 10 управления устройства. Кодовая комбинация с входов 9 и 10 управления сигналом с генератора 31 импульсов переписывается в регистр 32 и дешифрируется дешифратором 33. Высокий уровень сигнала на выходе Очистка дешифратора 33 разрешает прохождение синхроимпульсов через элемент И 34, элементы ИЛИ 16 и 17 на тактовые входы счетчиков 3 и 4 и через элементы ИЛИ 18 и 19 на входы управления блоков 1 и 2 памяти, Иа информационньж входах блоков 1 и 2 памяти присутствует низкий уровень сигнала.
Производится запись нулевых битов ин1606972 формации по всем адресам блоков 1 и
2 памяти. Длительность Т присутствия комбинации "01" на входах 9 и 10 управления должна удовлетворять усло5 вию
Т М, где t; — период тактовых импульсов генератора 31;
Б — информационная емкость блоков
1 и 2 памяти.
Режим очистки памяти используется только перед сортировкой первой по1 ! следовательности чисел.
Режим "Сортировка". Режим задается комбинацией "10" на входах 9 и 10 управления устройства. При этом на .выходе "Сортировка" дешифратора 33 присутствует высокий уровень сигна- 20 ла, который поступает на информационные входы блоков 1 и 2 памяти и разрешает прохождение через элемент
И 36 сигналов сопровождения данных сортируемой последовательности. Дан- 25 ные сортируемой последовательности поступают на входы 7 (младший разряд) и 8 устройства. В зависимости от значения младшего разряда данные с входа 8 сигналами с выходов элементов
И 22 и 23 записываются в счетчик 3 или 4, а затем через элементы 20 и
21 задержки и элементы ИЛИ 18 и 19 производится запись в соответствующий блок 1 и 2 памяти единичного бита данных.
Режим "Считывание". Кодовая комбинация "11", которой на входах 9 и 10 управления задается режим считывания, t1 вызывает появление на выходе Считычание1 дешифратора 33 высокого уро:аня сигнала. Одновременно с этим снимается высокий уровень сигнала с выхода "Сортировка" дешифратора 33, что приводит к срабатыванию формирователя 37, выходной сигнал которого устанавливает в нулевые состояния счетчики 3 и 4 и триггеры 28-30. Высокий уровень сигнала на выходе дешифратора 33 разрешает прохождение синхроимпульсов через элемент И 35 на входы триггеров 28 и 30 и элементов
И 24 и 25. Триггер 28 устанавливается в единичное состояние по заднему фронту первого синхроимпульса. Триг 55 гер 30 изменяет свое состояние по зад- нему фронту каждого синхроимпульса.
Сигналы с выходов элементов И 24 и
25 поступают на входы стробирования элемента И-ИЛИ 27, на другие входы
1 1 которых поступают выходные сигналы блоков 1 и 2 памяти. Сигналы с выходов элементов И 24 и 25 через элементы ИЛИ 16 и 17 поступают на счетные входы счетчиков 3 и 4 и через элементы ИЛИ на входы управления блоков
1 и 2 памяти. Триггер 28 блокирует прохождение первого синхроимпульса с выхода элемента И 25 через элемент
И 26. Триггер 29 устанавливается в единичное состояние сигналом перепал" нения счетчика 3 и блокирует чтение данных из блока 1 памяти. В режиме
fl и Считывание производится поочередное чтение бита данных из блоков 1 и 2 памяти. Чтение производится по последовательно возрастающим адресам, формируемым на счетчиках 3 и 4, Если при чтении считывается единичный бит, то на выходе элемента И-ИЛИ 27 появляется сигнал, поступающий на выход 14 управления и свидетельствующий о необходимости считывания данных с выходов счетчика 3 и триггера
30, которые поступают на информационные выходы 12 (младший разряд) и
13 устройства, Одновременно с чтением данных иэ блоков 1 и 2 памяти производится и их очистка, т,е, запись нулевых битов данных пс тем адресам (ячейкам} блоков памяти, данные из которых были перед этим считаны.
Сигнал переполнения счетчика 4, т.е. сигнал на выходе 15 управления свидетельствует об окончании режима чтения и устанавливает регистр 32 в состояние "00", Таким образом, в режиме считывания на выходе устройства числа появляются в возрастающей последовательности, Формула и з о б р е т ения
Устройство для сортировки информации, содержаще первый блок памяти, адресные входы которого соединены с выходом первого счетчика, элемент НЕ и блок синхронизации, первый, вторсй и третий входы которого являются входами управления устройства, о т л и" ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены второй счетчик и второй блок памяти, адресные входы которого соединены с выходом второго счетчика, последовательно соединенные первый! б06972
Риг.1 элемент И, первый элемент задержки и первый элемент ИЛИ, последовательно соединенные второй элемент И, второй элемент задержки и второй элемент
ИЛИ, третий элемент ИЛИ и подключеннь»»» к его первому входу третий элемент И, последовательно соединенные четвертый и пятый элементы И и четвертый элемент ИЛИ, первый и второй 10 триггеры, счетный триггер и элемент
И-ИЛИ, первый и второй ннформацнонные входы которых соединены соответственно с информационными выходами первого и второго блоков памяти, информационные входы которых соединены. с вторым выходом блока синхронизации, первый выход которого соединен с вторым входом третьего и четвертого элементов ИЛИ, третий выход блока синхро- 20 низации подключен к первым входам первого и второго элементов И, вторые входы которых соединены через элемент
HE четвертый выход блока синхронизации подключен к входам начальной ус- 25 тановки первого и второго счетчиков, первого и второго триггеров и счетного триггера, а пятый выход блока синхронизации подключен к первым входам 9 третьего и четвертого элементов И, к входу первого триггера, выхоц которого соединен с вторым входом пятого элемента И, и к входу счетного триггера, первый и второй выходы которого соответственно через третий и четвертый элементы И подключены к соответствующим входам стробирования элемента И-ЕЛИ, к блокирующему входу которого через второй триггер подключен управлякяций выход первого счетчика, управляющий выход второго счетчика соединен с четвертым (допол»»ительным) входом блока синхронизации, выходы третьего и четвертого элементов ИЛИ подключены к тактовым входам соответственно первого и второго счетчиков и к управляющим входам первого и второго блоков памяти соответственно через первый и второй элементы ИЛИ, выходы первого и второ" го элемента И соединены с входами разрешения записи соответственно первого и второго счетчиков, при этом входы записи первого и второго счетчиков и второй вход второго элемента
И являются входами данных сортируемой последовательности.
1606972
Составитель В,Харцхаев
Редактор E.Êoï÷à Техред Л.Олийнык Корректор «I.Муска г
Заказ 3550 Тираж 562 Подписное
ВНИКПИ Государственного комитета пэ .зобретениям и открытиям при ГКНТ СССР
113035, Москва, Ж-35, .Раушская наб,, д. 4/5
Производственно-издательский комбинат "Патент", r. Ужгород, ул, Гагарина, 101