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

СОЮЗ СОВЕТСКИХ СОЦИАЛИСТИЧЕСКИ 695290 А ЕСПУБЛИ(51)5 6 06 Р 7 О БРЕТ ПИСАНИ АВТОРСКОМУ СВ ЕТЕЛЬСТВ ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИПРИ ГКНТ СССР(71) Львовский политехнический институт им, Ленинского комсомола(56) Авторское свидетельство СССР М 1183956, кл. 6 06 Р 7/06, 1985.Авторское свидетельство СССР й 1546962, кл. 6 06 Г 7/06,1988,(54) УСТРОЙСТВО ДЛЯ СОРТИРОВКИ ДАННЫХ(57) Изобретение относится к вычислительной технике и может быть использовано в системах обработки информации, Цель изобретения - повышение быстродействия. Устройство содержит коммутатор 1, блок 4 памяти, преобразователи 2 и 6 кода данных, регистры 3 и 7, управляемые шифраторы 5 и 8. В устройство вводится неупорядоченный список, Признак нахождения в списке запоминается в байте признаков по адресу, соответствующему младшим разрядам кода данных, а сам байт запоминается по адресу, соответствующему старшим разрядам кода данных. Дополнительно по старшим разрядам кода данных запоминается признакбайта, содержащего признак нахождения в списке. Затем производится приоритетная выборка байтов, содержащих признаки нахождения в списке и в соответствии с их значениями, приоритетный опрос разрядов этих байтов, Управля- Я емые шифраторы позволяют вести выдачу упорядоченного списка как по возрастанию, так и по убыванию. 5 ил.10 Изобретение относится к вычислительной технике и автоматике и может быть использовано в системах обработкиинформации при реализации техническихсредств цифровых вычислительных машин идискретной автоматики,Цель изобретения - повышение быстродействия устройства,На фиг, 1 приведена функциональная,функциональная схема преобразователякода данных; на фиг, 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поступают соответственно младшие (Омл)и старшие (Ост) коды данных упорядоченного списка, на выход 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;в - сигнал приема списка на входе 10; 1,5 20 25 30 35 40 45 50 55 г, д - первый и второй разряды регистра 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 б). В промежутках между сигналами Т 2 и Т 1 поступают коды данных (фиг. 4; в, г) по входу 13, которые коммутатор 1 подключает на свой выход.В преобразователе 6 дешифратор 18 преобразует значение старших разрядов данных в унитарный код, который элементами ИЛИ 19 складывается в предыдущим состоянием регистра 7, и это новое значение через коммутатор 21 поступает на.иноформационные входы регистра 7, куда записывается по заднему фронту Т 2 (фиг.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, 3).По состоянию на информационном вы 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 на входе 1 О устанавливается "0", а на входы 11 и 12 начинают поступать Т 1. В про-,цессе выдачи происходит поочереднэявыборка всех байтов блока 4 и их обнуление. Окончание обнуления определяется посигналу КВ на выходе 16, 1695290Таким образом, осуществляется запоминание поступающего неупорядоченного списка данных по значениям их кодов и выдача нормализованного списка в порядке его убывания, либо возрастания. Дополнительное запоминание признаков байтов, содержащих признак нахождения в списке, позволяет исключить из процесса выдачи "холостой" опрос памяти и тем самым существенно сократить процесс сортировки. Формула изобретения Устройство для сортировки данных, содержащее. коммутатор, первый преобразователь кода данных, первый регистр, блок памяти и первый управляемый шифратор, информационные входы которого подключены к выходам блока памяти и информационным входам первой группы первого преобразователя кода данных, управляющий вход которого является входом задания приема списка устройства и соединен с управляющим входом коммутатора, вход задания режима устройства соединен с первым управляющим входом первого управляемого шифратора, -информационные выходы которого являются информационными выходами первой группы устройства и соединены с входами первой группы коммутатора, входы второй группы которого являются информационными входами устройства, выходы первой группы коммутатора соединены с адресными входами блока памяти, выходы второй группы - с информационными входами второй группы первого, преобразовэтеля кода данных, выходы которого соединены с информационными входами первого регистра, синхровход которого является первым тактовым вхо дом устройства, а выходы подключены к информационным входам блока памяти, вход записи которого является вторым тактовым входом устройства, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродейст вия устройства, в него введены второй преобразователь кода данных, второй регистр и второй управляемый шифратор, выходы которого являются информационными выходами второй группы устройства и под ключены к входам третьей группыкоммутатора, выход конца работы является выходом конца ввода устройства, управляющий вход подключен к входу задания режима устройства, а информаци онные входы подключены к выходам второго регистра и информационным входам первой группы второго преобразователя кода данных, информационные входы второй группы которого соединены с выходами 25 первой группы коммутатора, управляющийвход - с входом задания приема списка устройства и вторым управляющим входом первого управляемого шифратора, а выходы подключены к информационным входам 30 второго регистра, синхровход которого подключен к второму тактовому входу устройства, вход разрешения записи соединен с выходом конца работы первогоуправляемого шифратора, а вход установки в единич ное состояние является входом начальнойустановки устройства,