Устройство для сортировки чисел

ОП ИСАНИЕ ИЗОБРЕТЕНИЯ Союз СоветскихСоциалистическихРеспублик К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(22) Заявлено 25. 02. 81 (21) 3250579/18-24с присоединением заявки Мо(23) ПриоритетОпубликовано 2309.82Бюллетень Мо 35 151 М. Кл. з С Об Р 7/04 Государственный комитет СССР по деаам мзобретений и открытий(33) УДК 681325, 5 (088. 8) Дата опубликования описания 23,09. 82 ит СОРТИРОВКИ Ч 1(54).УСТРОИ и Изобретение относится к автоматике и вычислительной технике и предназначено для логической обработки информации, в частности для сортировки ч сел по величине.Известно устройство для сортировки чисел, содержащее элементы памяти, схемы сравнения и мажоритарный элемент. Сортировка осуществляется последовательным анализом одноименных разрядов сортируемых чисел 1 3;.Известно также устройство для сортировки информации, содержащее матрицу ячеек, каждая йтз которых состоит из триггера со.входными элементами И,.элемента НЕ, элементов И и ИЛИ, причем соответствующие логические выходы каждой ячейки соединены с одноименными логическими входами смеж- ных ячеек матрицы. Работа устройства осуществляется по шагам, В каждом шаге производится последовательный анализ одноименных разрядов всех сортируемых чисел, причем на первом шаге анализируются старшие разряды 23.Недостатком известных устройств является их низкое быстродействие.Наиболее близким техническим реше,нием к изобретению является устройство для сортировки чисел, состоящее ЗО из ячеек, каждая из которых содержитпервую и вторую группы выходов, соединенных с одноименными входами состветственно первой и второй групп входов данной и очередной ячейки, и триггеров (и - количество разрядов в сортируемых числах), 2 п входных элементов И, выходных элементов И, дешифратор, имеющий п входов и щ = 2" выходСв, (щ) элементов НЕ, группу наа элементов И и а элементов" ИЛИ.В каждой ячейке выход Е-го триггераОс = , и) соединен с 1 с-ьюл входомдешнфратора и с первым входом 1 с-говыходного элемента И, второй входкоторого .соединен с вторым входомячейки, Первый вход 2 М-го входногоэлемента И соединен с выходом 1 с-гоэлемента НЕ. Вторые входы входныхэлементов И соединены с первым входом ячейки. Выходы (21 с)-го и 2 Е-говходных элементов И ячейки соединенысоответственно с единичным и нулевымвходами к-го триггера. Первый вход 3элемента И (ь = Г, й) группы соединен с выходом дешнфратора. Второйвход: Р элемента И группы соединенс третьим входом ячейки. Остальные(1-1) входов Р элемента И группы соединены соответственно с выходами960800 первого, второго (У)-го элементоНР вЕ. Выход Х элемента И группы соединен с первым входом элемента ИЛИи с (пг-У+ 1) входом пг-го элементаИЛИ. Первый вход (2 Е) входного элемента И соединен с входом М-го элемента НЕ, выходом Е-го выходного элемента .И и с Й-входом первой группывходов ячейки. Входы остальных элементов НЕ каждой ячейки соединены с одноименными входами первой группы 1входов. Второй вход р элемента ИЛИ(р = 1, пг) каждой ячейки соединенсвыходом р элемента ИЛИ и с р выходом второй группы выходов ячейки.Выход.щ-го элемента ИЛИ соединен свыходом ячейки,Сортировка информации,в устройствеосуществляется путем параллельногоанализа разрядов сортируемых чисел 31.Недостатком такого устройства является его сложность,Цель изобретения - упрощение устройства.Поставленная цель достигается тем,что в устройство для сортировки чисел, содержащее узел управления йи ячеек анализа, каждая из которыхсостоит из регистра, группы выходныхэлементов И, дешифратора, группыэлементов ИЛИ, причем информационная группа входов регистра соедине- З 0на соответственно с группой информационных входов устройства, выходыразрядов регистра подклниены соответственно к информационным входам выходных элементов И группы и ко входам дешифратора, каждый 1"ый. выходдешифратора, где 1 = 1, 2, , в сбединен с первым входом (д)-го элемента ИЛИ группы, первый выход цешифратора подключен к первому выходу 40ячейки анализа, выход каждого 3-гоэлемента ИЛИ группы, где 31, 2,щ), соединен с (3+1)-ым выходом ячейки анализа, выход выходного элемента И 1-ой ячейки анализа 45подключен к 1-му выходу устройства,выход узла управления соединен совходами опроса ячеек анализа, введены элементы ИЛИ-НЕ, причем каждый1-.ый выход каждого Е-го узла айали-.,за соединен с К-ым входом 1-го элемента ИЛИ-НЕ, а выход каждого 1-гоэлемента ИЛИ-НЕ подключен к 1-му входу блокировки всех ячеек анализа,каждая ячейка анализа дополнительносодержит элементы ИЛИ, И, триггер,причем выход каждого 3-го элемента Игруппы соединен с 3-ым входом элемента ИЛИ, выход которого подключен к.управляющему входу дешифратора и кпервому входу элемента И, выход которого соединен со входом установкив единичное состояние триггера, прямой выход которого подключен к первым управляющим входам выходных элементов И группы, вход опроса ячейки 65 анализа подключен ко вторым учравля=ющим входам выходных элементов Игруппы и ко второму входу элемента ИФвход. установки в нулевое состояниетриггера каждой ячейки анализа. соединен со входом запуска устройства,каждый 1-ый вход блокировки ячейкианализа соединен с (1+1) -ми входами1 г 2 г.п+1)-го элементов Игруппы,0 При этом узел управления содержитгенератор, триггер, элемент И, входггенератора соединен с первым входомсэлемента И, вход установки в нулевоесостояние триггера подключен ко,входу запуска устройства, вход установки в единичное состояние триггерасоединен со входом останова устройства, прямой выход триггера подключен ко второму входу элемента И вы-.Фход которого соединен с выходом узла.управления.На чертеже представлена структуРная схема устройства для сортировкичисел.Устройство содержит и ячеек 1 г,11 ,, 1анализа, элементы ИЛЙ-НЕ2 21, , 2 щ, генератор 3, триггер 4 запуска, управляющий элементИ 5Каждая ячейка 1 анализа содержитдешифратор б, выходные элементы И 7,регистр 8, элементы И 91, 91, , 9 щгруппы, элемент ИЛИ 10, элемент И 11,триггер 12, группу информационныхвходов 13 устройств, группу выходов14 устройства, выходы 151, 15,15 элементов ИЛИ ячейкй, входы 16 г,16,, 16 е блокировки ячеек анализа, вход 17 запуска устройства,вход 18 останова устройства.Каждое слово состоит из кода чис"ла (и-Я разрядов) и 3-разрядногокода признака этого числа.Выходные элементы И 7 ячейки обеспечивают выдачу потребителю. словаиз регистра 8 в случае, если онооказывается результатом сортировкиПередача слова потребителю осуществляется по соответствующим выходамгруппы выходов 14 устройства.Дешифратор 6 ячейки преобразуетз-разрядный призна числа слова регистра 8 из двоичной системы счисления,в однопозиционный код в виде разрешающего потенциала на одном из Мего выходовЭлемент И 9 с номером 1 группыкаждой ячейки предназначен. для анализа (1+1)-го выхода дешифратора бданной ячейки и выходов первых 1элементов ИЛИ-ИЕ.2 устройства,Элемент ИЛИ 10 ячейки управляетчерез выходные элементы И 7 процес.сом считывания слова регистра 8 потребителю и через элементы И 11 триггером 12, который позволяет исклю 1чить данную ячейку из дальнейшегоанализа путем подачи на управляющийвход дешифратора б запрещающего потенциала, Ячейка исключается из дальнейшего анализа, если в результатесортировки слово регистра 8 даннойячейки передается потребителю. Элемент ИЛИ-НЕ 2 с номером 1 = 1 предназначен для анализа потенциалов первых выходов дешифраторов б всех яче.е а элементы ИЛИ-НЕ 2 с номерами2,М- для анализа потенциалов 10выходов (1-1)-ых элементов И 9 группывсех ячеек. Генератор 3, триггер 4запуска и управляющий элемент И 5представляют собой блок управленияустройства, 15Устройство работает следующим образом,Устройство осуществляет сортировкуслов, содержащихся в регистрах 8 ячеек айализа, по убыванию (возрастанию) о.значений их признаков.Устройство работает по тактам. Длительность такта определяется периодомследования импульсов генератора.3,В каждом такте устройство выделяетиз сортируемого массива и выдает потребителю слова, значения признаковкоторых максимальные (минимальные).Дпя запуска устройства на его первыйвход 17 подается сигнал фПуск" ко-.торый устанавливает в нулевое состоянке триггеры 12 каждой ячейки итриггер 4 запуска, с нулевых выходовкоторых разрешающий потенциал подается на управляющий вход дешифратораб соответствующей ячейки и на вход.управляющего элемента И 5 устройствасоответственно.Если в текущем такте среди признаков сортируемых слов найдется хотя 40бы один с значением И, то на первомвыходе дешифратора б ячейки анализа,где хранится слово с этим признаком,образуется разрешающий потенциал,который через первый элемент ИЛИ-НЕ2 поступает на вход первого и всехпоследующих элементов И 9 группы всехячеек в качестве запрещающего потенциала. Таким образом, единичный потенциал на входах элемента И 10 имеетместо только в тех ячейках, в регистрах 8 которых хранится слово,значение признака которого равно М.Единичный потенциал с выхода элемента ИЛИ 10 с посуплене очередйогоимпульса генератора 3 обеспечиваетвыдачу слова данной ячейки через выходные элементы И 7 потребителю и:. через элемент И 11 - установку триггера 12 в единичное состояние, который, в свою. очередь, обеспечивает по Одачу запрещающего потенциала с нулевого выхода 16 на управляющий входдешифратора б,. исключив тем самым признак слова регистра 8 данной ячейкииз сортировки в последующих тактах. 65 Если в текущем такте среди признаков сортируемых слов нет признаков с значением М, но есть с значением (М), то на выходе первого элемента ИЛИ-НЕ 2 образуется единичный потенциал, который поступает на входы первого и всех последующих элементов И 9 группы всех ячеек в качестве разрешающего потенциала. На выходе первого элемента И 9 группы и втором входе элемента ИЛИ 10 ячейки, в регистре 8 которой хранится слово с признаком (М), образуется единичный потенциал,который аналогично предыдущему случаю обеспечивает выдачу слова из регистра 8 потребителю и исключение . его признака из сортировки в последующих тактах и т.д,Дпя прекращения процесса сортировки на второй вход 18 устройства подается сигнал "Остайов", который устанавливает триггер 4 запуска в единичное состояние, иСключив тем самымвозмозаность прохождения импульсов генератора 3 через управляющий элемент И 5.Для сортировки путем выделения слов. по возрастанию значений их признаков необходимо на входы дешифратора б каждой ячейки подать инверсныевыходы регистра 8.. Сопоставительный анализ предлагаемого и известного устройств показывает, что выигрыш в оборудовании от использования устройства составляет 15 и более процентов.формула изобретения1. Устройство для сортировки чисел,содержащее узел управления и и яче-. ек анализа, каждая иэ которых состоит из регистра, группы выходных элементов И, дешифратора, группы элементов ИЛИ, причем информационная группа входов регистра соединенасоответственно с группой информационных входов устройства, выходи разрядов регистра подключены соответственно к информационным входам выходныхэлементов И группы и ко входам дешифратора, каждый 1-ый выход дешифратора, где 1 = 1, 2, , в соединен с первым входом (1-1)-го элемента ИЛИ группы, первый выход дешифратора подключен к первому выходу ячейки анализа, выход каждого 3-го элемента ИЛИ группы, где 3 = 1, 2, (а), соединен с (3+1)-ым выходом ячейкй анализа, выход выходного элемента И 1-ой ячейки анализа подключенк 1-му выходу устройства, выход узла управления соединен со входами опроса ячеек анализа, о т л и ч а ю щ ее с я тем, что, с целью упрощения устройства, в него введены элементыИЛИ-НЕ, причем каждый 1-ый выход каж960800 ИИПИ Заказ 7282/58 Тираж 731 Подписно Патентф Ужгород, ул.Проектная; илиал дого Е-го узла анализа соединенс М-им входом 1-го элемента ИЛИ-НЕ,а выход каждого 1-го элемента ИЛИ-НКподключен к 1-му входу блокировкивсех ячеек анализа, каждая ячейкаанализа дополнительно содержит элемен тц ИЛИ, И, триггер, прнчем выход каждого 3-го элемента И группы соединенс 3-ым входом элемента ИЛИ, выходкоторого. подключен к управляющемувходу деииратора и к первому входу 1 О.элемента И, выход которого соединенСо входом. установки в единичное состояние триггера, прямой вьиод которого подключен к.первым управляющимвходам выходных элементов И группы,вход опроса ячейки анализа подключенко вторым управляющим входам выход.ных элементов И группы и ко второмувходу элемента И, вход установкив нулевое состояние триггера каждойячейки анализа соединен со входомзапуска устройства, каждый 1-ыйвход блокировки ячейки анализа соединен с (1+1)-ми входами 1, 2,(и+1)-го элементов И группы,2. Устройство по п. 1, о т л и ч аю щ е е с я тем, что узел управления содержит генератор, триггер, элемент И, вход генератора соединен спервым входом элемента И, вход установки в нулевое состояние триггераподключен ко входу запуска устройства, вход установки в единичное состояйие триггера соединен со входомостанова устройства, прямой выходтриггера подключен ко второму входуэлемента И, выход которого соединенс выходом узла управления.Источники инФормации,принятые во внимание при экспертизе1. Авторское свидетельство СССР46396.8 ф иле 6 06 Р7/00 ф 19732. Авторское свйдетельство СССРф 424141 с клф 6 06 Р 7/ОО 19723. Авторское свидетельство СССРР 590728, кл. 6 Об Р 7/ОО, 1976