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

 

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

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

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

РЕСПУБЛИК (я)5 G 06 Е 7/06

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4881112/24 (22) 11.11.90 (46) 15.02.93. Бюл. N 6 (71) Львовский политехнический институт им, Ленинского комсомола (72) И. Б. Боженко и О, К. Мешков (56) Авторское свидетельство СССР

N 1183956, кл, G 06 F 7/06, 1984.

Авторское свидетельство СССР . йг 1501039, кл. G 06 F 7/06, 1988. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ИНФОРМАЦИИ (57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки информации. Цель изоИзобретение относится к вычислительной технике и может быть использовано в системах обработки информации, Известно устройство, которое содержит блоки синхронизации и памяти, счетчик и элементы И. В режиме ввода в память по адресу, соответствующему поступившей информации; заносится признак нахождения в списке. При считывании на выход передаются состояния счетчика, соответствующие считанному из блока памяти признаку. Недостатком устройства являются необходимость опроса всех ячеек памяти, независимо от поступившей информации.

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

„„Я2 „„1 795450 А1 бретения — расширение области применения за счет сортировки информации по времени ее поступления, Устройство содержит счетчик 1, два регистра 2 и 3, блоки памяти

4, сравнения 5 и синхронизации 9, триггер

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

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

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

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

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

Новая совокупность известных злемен- 50 тов позволяет, наряду с сортировкой информации по ее значению, вести сортировку по времени ее поступления, Кроме того, совмещение процессов ввода и вывода дает дополнительный выигрыш в быстродействии, 55 по оценочным данным, в 1,3 раза., На фиг. 1 изображена функциональная схема предлагаемого устройства; на фиг, 2 — функциональная схема блока синхронизации; на фиг, 3, 4 — временные диаграммы работы устройства (фиг. 3 — в режиме приема информации, фиг. 4 — в режиме выдачи).

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

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

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

Информационный вход счетчика 1 соединен с выходом второго коммутатора 8, входы суммирования, вычитания и установи . — соответственно, с первым 9,1 — третьим 9.3 выходами блока 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, 16 устройства.

Первый информационный вход коммутатора 10 соединен с информационным входом

20 устройства, а второй — с информационным .выходом 19 устройства и счетчика 1, выход переноса которого подключен к выходу 21 конца очистки устройства.

1795450

10

20

30

40

50

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

С выхода 21 поступает сигнал конца очистки

КО. С первого выхода 5,1 блока 5 поступает сигнал A=C, со второго 5.2-В=С, с 5.3-С>А, с 5.4-С<В, где А-С значения информации . на, соответственно, первом-третьем входах блока 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 на выходец.4 блока 9; ж — сигнал инкремента счетчика на выходе 9.1; з — состояние регистра 2; и— выход блока 4 памяти; к — выход переноса счетчика 1.

На фиг. 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 (фиг. Зб). В блоке 9 синхронизации элемент И-ИЛИ 22 устанавливает на своем выходе "1", что разрешает прохождение Т2 через элемент И-НЕ 27 на выходе 9.1. Коммутатор 23 подключает вход

16 к выходу 9.4. Элемент И 24 устанавливает

"0" на выходе 9.6, по которому коммутатор

10 подключает к адресному входу блока 4 памяти выход разрядов счетчика 1, На втором входе сброса триггера 6 и стробирующем входе коммутатора 7 устанавливается

"1" и выдача сигналов СТРОБ и КВ блокируется..

По сигналу НУ (фиг. 3e) коммутатор 23 передает на выход 9.4 сигнал сброса счетчика 1 (фиг. 3e). По Т1 (фиг. Зг) элемент И 25 формирует на выходе 9.5 сигнал записи, и в блок 4 заносится "0" с выхода 9,6 по адресу, сформированному счетчиком 1 (фиг, Зи). По

Т2 (фиг. Зд) элемент И-НЕ 27 формирует сигнал инкремента (фиг. Зж) и счетчик 1 MQдифицируется. По установке счетчика 1 в единичное состояние он выдает сигнал переноса (фиг. 3 к), который выдается на выход

21 как сигнал КО. По нему сигнал 04 может быть сброшен, и устройство может начать работу в режиме ввода списка.

Режим ввода задается установкой в "1" сигнала ПР и в "0" прочих управляющих сигналов. Элементы И вЂ” НЕ 27, 28 блокируют поступление на счетчик 1 сигналов модификации. Элемент И 24 устанавливает на выходе 9,6 "1" и коммутатор 10 подключает к адресному входу блока 4 вход 20.

По НУ регистр 2 устанавливается в нулевое (фиг. Зз), регистр 2 — в единичное состояние. По Т1 в блок 4 заносится признак присутствия в списке по адресу, определенному информацией на входе 20. В блоке 5 эта информация сравнивается с состоянием регистров 2, 3. Если значение входной информации превышает значение состояния регистра 2, на выходе 5.3 блока 5 устанавливается " 1", и по Т1 входная информация заносится в регистр 2. Если значение состояния регистра 3 превышает значение входной информации, то "1" устанавливается на выходе 5.4, и выходная информация по Т1 заносится в регистр 3. Тем самым в регистре 2 устанавливается максимальное, а в регистре 3 минимальное значение входной информации.

Режим выдачи задается установкой сигнала ПР в "0". Если выдача осуществляется по возрастанию, сигнал УБ устанавливается в "0", если по убыванию — e "1".

Блокировка с триггера 6 и коммутатора 8 снимается. При сортировке по возрастанию коммутатор 8 подключает. к информационному входу счетчика 1.выход регистра

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

27 разрешает прохождение Т2 на выход 9.1, 1795450

15

25

35

45

55 при сортировке по убыванию И 28 разрешает прохождение Т2 на 9.2, Коммутатор 23 подключает вход 16 к выходу 9.3. Элемент

И 24 устанавливает на выходе 9.6 "0", по которому коммутатор 10 подключает к адресному входу блока 4 информационный выход счетчика 1, а запись в регистры 2, 3 блокируется, И 25 блокирует запись в блок

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

1 и регистра 3.

Устройство может перейти в режим ввода и до окончания выдачи введенного списка. Для этого ПР вновь устанавливается в "1", коммутатор 10 отключает от адресного входа блока 4 информационный выход счетчика 1, подключает к нему вход

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

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

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

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

1795450

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

Составитель И.Боженко

Техред M,Ìîðãåíòàë Корректор Н.Слободяник

Редактор. Производственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина, 101

Заказ 431 Тираж Подписное

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

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