Устройство для сортировки данных

 

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

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

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

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

14 (21) 4765629/24 (22) 05.12.89 (46) 30.11.91. Бюл. М 44 (71) Львовский политехнический институт им. Ленинского комсомола (72) О.К, Мешков, И.Б. Боженко и П.А. Кондратов (53) 681.325.5(088.8) (56) Авторское свидетельство СССР

М 1183956, кл. G 06 F 7/06, 1985.

Авторское свидетельство СССР

ЬВ 1546962, кл. G 06 F 7i06,1988. (54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ

ДАННЫХ (57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки информации. Цель изобретения — повышение быстродействия. Устройство содержит коммутатор 1, блок 4. Ж, 1695290 А1 памяти, преобразователи 2 и 6 кода данных, регистры 3 и 7, управляемые шифраторы 5 и

8. В устройство вводится неупорядоченный список. Признак нахождения в списке запоминается в байте признаков по адресу, соответствующему младшим разрядам кода данных, а сам байт запоминается по адресу, соответствующему старшим разрядам кода данных. Дополнительно по старшим разрядам кода данных запоминается признакбайта, содержащего признак нахождения в списке. Затем производится приоритетная выборка байтов, содержащих признаки нахождения в списке и в соответствии с их значениями, приоритетный опрос разрядов этих байтов. Управля- Я емые шифраторы позволяют вести выдачу упорядоченного списка как по возрастанию, так и по убыванию. 5 ил.

1695290

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

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

Устройство содержит (фиг. 1) коммутатор 1, преобразователь 2 кода данных, регистр 3, блок 4 памяти, управляемый шифратор 5, преобразователь 6 кода дан-ных, регистр 7, управляемый шифратор 8.

,входы 9 — 13, информационные выходы 14 и

15, выход 16 конца ввода и вход 17 установки.

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

На фиг, 4 обозначены: а, б — синхроимпульсы Т1 и Т2 соответственно; в, г — соответственно старшие и младшие разряды кода данных, поступающие в устройство; д, е — первый и второй разряды регистра 7; ж — и — соответственно первый, второй и последний разряды выхода блока 4 памяти; к — м — первый, второй и последний выходы преобразователя 2; н — и — первый, второй и последний разряды регистра 3;

На фиг, 5 обозначены: а, б — синхроимпульсы Т1 и Т2; . e — сигнал приема списка на входе 10;

1,5

r, д — первый и второй разряды регистра 7; е — информационный выход шифратора 8; ж — выход конца работы шифратора 8; з, и — первый и второй выходы преобразователя 6; к — м — выходы блока 4 памяти; н — информационный выход шифратора 5; о — выход конца работы шифратора 5; и-с — выходы преобразователя 2; т — ф — выходы регистра 3.

Предлагаемое устройство предназначено для упорядочивания списка из максимум 27 данных разрядностью 7. В качестве старших принято 4 разряда. Блок 4 памяти представляет собой матрицу 8 х 16, реализованную на основе К531РУ8. Первый преобразователь 2 выполнен как преобразователь трехразрядного двоичного в восьмиразрядный позиционный код, первый шифратор 5 — как преобразователь восьмиразрядного позиционного в трехраэрядный двоичный код, вторые преобразователь 6 и шифратор 8 — соответственно как преобразователи 4 — 16 и 16 — 4. Устройство реализовано на основе серии К555, в частности коммутаторы 1,21 — на К555КП11, регистры 3, 7 — на К555ТМ8, дешифратор 18— на К555ИД7, шифратор 23 — на К555ИВ1, сумматоры 24 — на К555ЛП5.

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

Режим ввода списка задается установкой единичного сигнала на входе 10 и поступлением синхросигналов Т1 (фиг. 4а) и Т2 (фиг, 4б). B промежутках между сигналами

Т2 и Т1 поступают коды данных (фиг. 4; в, г) по входу 13, которые коммутатор 1 подключает на свой выход.

В преобразователе 6 дешифратор 18 преобразует значение старших разрядов данных в унитарный код, который элементами ИЛИ 19 складывается в предыдущим состоянием регистра 7, и это новое значение через коммутатор 21 поступает на.ино формационные входы регистра 7, куда записывается по заднему фронту J2 (фиг.

4, д, е). При этом по "1" на своем втором управляющем входе шифратор 5 поддерживает "1" на своем выходе конца работы, подключенном к входу разрешения записи регистра 7. Так. в регистре 7 устанавливаются признаки нахождения в списке, соответствующие старшим разрядам поступающих кодов данных.

Из блока 4 по состоянию старших разрядов данных выбирается соответствующий байт признаков (фиг. 4 ж-и), В преобразователе 2 этот байт складывается по ИЛИ с унитарным кодом, сформированным де1695290 шифратором 18 преобразователя 2 иа младших разрядов кода данных (фиг, 4, к-м) и через коммутатор 21 передается на информационный вход регистра 3, куда и заносится по переднему фронту Т1 (фиг. 4, н — и).

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

Выдача упорядочиваемого списка задается сбросом в "0" сигнала П Р (фиг. 5. в). При этом информационный выход шифтора 5, находившийся по единичному значению сигнала ПР в состоянии "все единицы", переходит в состояние, соответствующее состоянию выхода блока 4 (фиг. 5, н). Если на выходе блока 4 присутствует хотя бы один признак присутствия в списке, выход конца работы шифтора 5 сбрасывается (фиг. 5, о) и запись в регистр 7 запрещается, Сортировка списка по возрастанию задается уровнем "0" на входе 9. По нему в управляемых шифраторах 5 и 8 коммутатор

22 передает входной код на информационные входы приоритетного шифратора 23, который на своих информационных выходах формирует код, срответствующий признаку, которому присвоен наибольший приоритет. Сумматоры 24 при наличии "0" на своих первых входах передают этот код на информационный выход управляемого шифратора. Сортировка по убыванию задается установкой "1" на входе 9. По ней коммутатор 22 передает младший разряд на своем входе на старший разряд своего выхода, и наоборот. Например, код

10000011 на входе коммутатора 22 передается на вход шифратора 23 как код

11000001. Тем самым приэнакус наименьшим приоритетом присваивается наибольший приоритет. По уровню "1" на своих первых входах сумматоры 24 инвертируют сформированный шифратором 23 код. Тем самым при изменении приоритетов признаков коды, присвоенные этим признакам, сохраняются. На фиг. 5 отображена сортировка по возрастанию.

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

7, которому присвоен наивысший приоритет. Например, уровню "1", в первом разряде регистра 7 (фиг. 5, г) соответствует код

0000 (фиг. 5, е). Этот код коммутатор 1 передает на вход дешифратора 18 преобразователя 6, в результате чего соответствующий элемент И 20 блокирует передачу признака нэ выход коммутатора 21 (фиг. 5, з).

По состоянию на информационном вы5 ходе шифратора 8 из блока 4 памяти выбирается байт признаков (фиг. 5, к — м), который в зависимости от состояния шифратора 5, которое коммутатор 1 передает на вход преобразователя 2, модифицируется аналогич10 ным образом.

По переднему фронту Т1 (фиг. 5, а) модифицированный байт признаков младших . разрядов заносится в регистр 3 (фиг. 5, т-ф). Кроме того, по Т1 с информационных

15 выходов устройства принимается код отсортированных данных: с выхода 14— младшие разряды, с выхода 15 — старшие.

По Т2 (фиг. 5, б) модифицируется байт признаков блока 4.

20 После того,-как все признаки на выходе блока 4 оказываются сброшенными, на информационном выходе шифратора 5 устанавливается единичный код, à íà его выходе запроса — уровень "1". По нему разрешает25 ся запись задним фронтом Т2 модифицированного байта признаков старших разрядов в регистр 7. Код на выходе шифратора 8 изменяется. Например, после сброса признака в первом разряде регист30 ра 7 по "1" в его втором разряде (фиг. 5, д) шифратор 8 формирует код 0001. По нему из блока 4 выбирается следующий байт признаков, и процесс выдачи отсортированного списка продолжается.

35 После того, как из блока 4 будет выбран байт, соответствующий последней из "1", в регистре 7, и все его разряды будут обнулены, по заднему фронту 12 последняя из

"1" регистра 7 сбрасывается. Информаци-40 онный выход шифратора 8 устанавливает-. ся в состояние 1111. На выходе конца работы шифратора 8 устанавливается "1" (фиг. 5, ж), которая передается на выход 16 как сигнал конца выдачи. Выдача сигналов

45 Т1 и Т2 прекращается. Все разряды регистров 3 и 7 и ячейки блока 4 обнулены, и устройство готово к приему очередного списка.

При включении питания ячейки памяти

50 устанавливаются произвольно. Для их начального обнуления проводится предварительная операция вывода, для чего на вход

17 подается сигнал начальной установки регистра 7 в единичное состояние. Затем

55 на входе 10 устанавливается "0", а на входы 11 и 12 начинают поступать Т1. В про-. цессе выдачи происходит поочереднэя выборка всех байтов блока 4 и их обнуление. Окончание обнуления определяется по сигналу КВ на выходе 16.

1695290

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

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

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

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

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

b TZ

8юл

2 ею

ORGY(eAOnf и DS7

К Гтй

Л Гго Х м Гмю7

Н RfrrnfoRDwnZ

1695290 а тю

Ютя

bnp

2 Юп дИстР

Е Юст ж Ест

З rcrr

И ЯтЯ .и Ю7 я С&о .д &и

Л Empt р Г/4лг

8 Fivp7 лЮМ

УРЮ ю2 ф7ЯЮ„ 7

Составитель Е. Иванова

Редактор А. Лежнина . Техред М.Моргентал Корректор Т. Палии

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

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

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

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