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

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

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

Ближайшим к заявляемому по технической сущности является устройство, содержащее блоки управления, памяти и сравнения, 2 коммутатора, 2 регистра и триггер. По ходу поступления информации

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

Цель изобретения - расширение области применения за счёт возможности сорти- ровки информации по времени ее поступления.

Поставленная цель достигается тем, что в устройство для сортировки информации, содержащее счетчик 2, регистра, блоки памяти и сравнения, триггер 2 коммутатора и

ч о ел ел о

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

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

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

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

работы устройства (фиг. 3 - в режиме приема информации, фиг. 4 - в режиме выдачи). Устройство содержит (фиг. 1) счетчик 1, первый 2 и второй 3 регистры, блоки 4 памяти и 5 сравнения, триггер 6, первый 7 и второй 8 коммутаторы, блок 9 синхронизации, третий коммутатор 10, первый 11 и второй 12 тактирующие входы, входы задания направления сортировки 13, приема 14,очистки 15 и установки 16, выходы 17 строба и

18 конца выдачи, информационные выходы

19 и входы 20, выход 21 конца очистки.

Информационный вход счетчика 1 соединен с выходом второго коммутатора 8, входы суммирования, вычитания и установи - соответственно, с первым 9.1 -третьим выходами блока 9 синхронизации, вход сброса - с выходом 9.4 и выходами сброса

первого 2 и установки второго 3 регистров, информационные входы которых подключены к выходу третьего коммутатора 10, адресному входу блока 4 памяти и третьему входу блока 5 сравнения, синхровходы - к

синхровходу триггера 6, первому тактирующему входу блока 9 и первому тактирующему входу 11 устройства, первые входы разрешения записи - соответственно, к, третьему 5.3 и четвертому 5.4 выходам блока 5, вторые - к выходу 9,6, к информационному входу блока 4 и к управляющему входу третьего коммутатора 10, а выходы, соответственно, к первому и второму информационным входам блока 5 и коммутатора 8. Вход записи блока 4 соединен с выходом 9.5, а выход - с информационным входом триггера 6, первый вход сброса которого подключен ко вторым тактирующим входам блока 9 и 12 устройства, второй - к

стробирующему входу первого коммутатора 7 и ко вторым управляющим входам блока 9 и 14 устройства, а выход-к выходу

17 строба устройства. Первый 5.1 и второй 5.2 выходы блока 5 подключены, соответственно, к первому и второму информационным входам коммутатора 7, выход которого соединен с выходом 18 конца выдачи устройства, а управляющий вход под ключей к управляющему входу коммутатора

8 и первым управляющим входам 13 устройства и блока 9, третий управляющий и установочный входы которого подключены, к соответствующим входам 15, Обустройства. Первый информационный вход коммутатора 10 соединен с информационным входом 20 устройства, а второй - с информационным выходом 19 устройства и счетчика 1, выход переноса которого подключен к выходу 21 конца очистки устройства.

По входам 11, 12 поступают тактирующие импульсы, соответственно, Т1, Т2. По ходам 13-16 поступают сигналы, соответтвенно, сортировки по убыванию УБ, прима информации ПР, очистки памяти 04 и начальной установки НУ. С выхода 17 поступает сигнал СТРОБ, с 18 - сигнал конца выдачи KB, С выхода 19 поступает выходная информация Овых, на вход 20-входная DBx. С выхода 21 поступает сигнал конца очистки КО. С первого выхода 5.1 блока 5 поступает сигнал , со второго 5., с 5.3-ОА, с 5., где А-С значения информации на, соответственно, первом-третьем входах блока 5.

: Блок 9 синхронизации содержит (фиг..2) элементы И-ИЛИ 22, коммутатор 23,, элементы И 24, 25, ИЛИ 26 и И-НЕ 27, 28. С выходов элементов И-НЕ 27, 28 через выхоы, соответственно, 9.1, 9.2 поступают сигналы инкремента и декремента, с выходов коммутатора 23 через 9,3, 9.4 - установки и сброса счетчика 1. С элементов И 24 через 9,6 и И 25 через 9,5 поступают сигналы, соответственно, на информационный вход и вход записи-блока 4 памяти.

На фиг. 3 обозначены: а-в - сигналы, соответственно, ПР, 04, НУ; г-д - тактирующие импульсы, соответственно, Т1, Т2; е - сигнал сброса счетчика 1 на выходе-9.4 блока 9; ж - сигнал инкремента счетчика на выходе 9.1; з - состояние регистра 2; и - выход блока 4 памяти; к - выход переноса счетчика Т..

На фиг. 4 обозначены: а - сигнал НУ; б, в - импульсы Т1, Т2; Г - сигнал 04; д - выход блока 4 памяти; е - выход триггера 6; ж - выход коммутатора 7.

Реализованный вариант предлагаемого устройства предназначен для сортировки информации, состоящей максимум из 256 8-разрядных байтов. Счетчик 1 выполнен на К555ИЕ7, регистры 2,3 - на основе К555ТМ8, блок 4 памяти - на КР564РУ2.. Блок 5 сравнения содержит два компаратора на К555СП1. Триггер 6 выполнен на К555ТМ2, коммутаторы 8, 10-на К555КП 11, коммутатор 7 - на основе К555ЛР4. Блок 9 также выполнен на серии К555, в частности, элемент И-ИЛИ 22 - на основе К555ЛР11, коммутатор 23 - на К555ЛИ1.

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

Режим очистки памяти задается сигналами ПР (фиг. За), 04 (фиг. 36). В блоке 9 синхронизации элемент И-ИЛИ 22 устанавливает на своем выходе 1, что разрешает прохождение Т2 через элемент И-НЕ 27 на выходе 9.1. Коммутатор 23 подключает вход 16 к выходу 9.4. Элемент И 24 устанавливает

О на выходе 9.6, по которому коммутатор 10 подключает к адресному входу блока 4 памяти выход разрядов счетчика 1. На втором входе сброса триггера 6 и стробирующем входе коммутатора 7 устанавливается 1 и выдача сигналов СТРОБ и KB блокируется, .

По сигналу НУ (фиг. Зв) коммутатор 23 передзет на выход 9.4 сигнал сброса счетчи0 ка 1 (фиг. Зе). По Т1 (фиг. Зг) элемент И 25 формирует на выходе 9.5 сигнал записи, и в блок 4 заносится О с выхода 9.6 по адресу, сформированному счетчиком 1 (фиг. Зи). По Т2 (фиг. Зд) элемент И-НЕ 27 формирует

5 сигнал инкремента (фиг. Зж) и счетчик 1 модифицируется. По установке счетчика 1 в единичное состояние он выдает сигнал переноса (фиг. 3 к), который выдается на выход 21 как сигнал КО. По нему сигнал 04 может

0 быть сброшен, и устройство может начать работу в режиме ввода списка.

Режим ввода задается установкой в 1 сигнала ПР и в О прочих управляющих сигналов. Элементы И-НЕ 27, 28 блокируют

5 поступление на счетчик 1 сигналов модификации. Элемент И 24 устанавливает на выхо- . де 9.6 1 и коммутатор 10 подключает к адресному входу блока 4 вход 20.

По НУ регистр 2 устанавливается в ну0 левое (фиг. Зз), регистр 2 - в единичное состояние. По Т1 в блок 4 заносится признак присутствия в списке no-адресу, определенному информацией на входе 20. В блоке 5 эта информация сравнивается с состоянием

5 регистров 2, 3, Если значение входной информации превышает значение состояния регистра 2, на выходе 5.3 блока 5 устанавливается 1, и по Т1 входная информация заносится в регистр 2. Если значение со0 стояния регистра 3 превышает значение входной информации, то 1 устанавливается на выходе 5.4, и выходная информация по Т1 заносится в регистр 3. Тем самым в регистре 2 устанавливается мак5 симальное, а в регистре 3 минимальное значение входной информации.

Режим выдачи задается установкой сигнала ПР в О. Если выдача осуществляется по возрастанию, сигнал УБ устанавли0 вается в О, если по убыванию - в 1. Блокировка с триггера 6 и коммутатора 8 снимается. При сортировке по возрастанию коммутатор 8 подключает.к информационному входу счетчика 1 .выход регистра

5 3, а коммутатор 7 подключает к выходу 18 выход 5.1. При сортировке по убыванию подключаются, соответственно, выходы регистра 2 и 5,2 блока 5, В блоке 9 при сортировке по возрастанию элемент И-НЕ 27 разрешает прохождение Т2 на выход 9.1,

при сортировке по убыванию И 28 разрешает прохождение Т2 на 9.2. Коммутатор 23 подключает вход 16 к выходу 9.3. Элемент И 24 устанавливает на выходе 9.6 О, по которому коммутатор 10 подключает к адресному входу блока 4 информационный выход счетчика 1, а запись в регистры 2, 3 блокируется. И 25 блокирует запись в блок

4.

По НУ (фиг. 4а) счетчик 1 устанавливается в зависимости от режима выдачи, в минимальное либо максимальное значение поступившей информации. Блок 4 памяти выбирается по адресу, сформированному счетчиком (фиг. 4д). Если по этому адресу присутствует признак нахождения в списке, то по Т Т (фиг. 46), триггер 6 устанавливается в 1 и сбрасывается по Т2 (фиг. 4в). Тем самым на выходе 17 формируется сигнал СТРОБ (фиг. 4е), индентифицирующий присутствующее на выходе 19 состояние счетчика 1, как отсортированную информацию. По Т2 счетчик 1 модифицируется, и блок 4 выбирается по следующему адресу. Сигнал KB (фиг. 4ж) формируется, если при сортировке по возрастанию состояние счетчика 1 становится равным состоянию регистра 2, что фиксируется уровнем 1 на выходе 5.1. При сортировке по убыванию 1 на выходе 5.2 фиксирует совпадение состояний счетчика 1 и регистра 3.. Устройство может перейти в режим ввода и до окончания выдачи введенного списка. Для этого ПР вновь устанавливается в 1, коммутатор 10 отключает от адресного входа блока 4 информационный выход счетчика 1, подключает к нему вход 20, и в блок 4 вновь заносится признак нахождения в списке. Последующая выдача может быть начата либо с нового экстремального значения информации, либо с предыдущего состояния счетчика 1, В последнем случае при переходе к режиму выдачи НУ на вход 16 не поступает.

При необходимости сопровождения выдачи списка очисткой блока 4 установка в О сигнала ПР сопровождается установкой в 1 сигнала 04 (фиг. 4г). В этом случае элементы ИЛИ 26, И 25 разрешают прохождение Т.1 на запись О с выхода 9.6 в блок 4. Блок 4 становится очищенным с окончанием выдачи списка.

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано в системах обработки информации. Цель изобретения - расширение области применения за счет сортировки информации по времени ее поступления. Устройство содержит счетчик 1, два регистра 2 и 3, блоки памяти 4, сравнения 5 и синхронизации 9, триггер 6, три коммутатора 7, 8, 10. В устройство вводится неупорядоченный список. Там он запоминается по адресам, соответствующим вводимой информации. Одновременно определяется максимальное и минимальное значение информации. При выводе нормализованного списка память опрашивается в этом интервале. В процессе вывода устройство может переключаться на ввод дополнительной информации. 4 ил.