Устройство для упорядочения слов

Союз Советских Социалистических Республик(51) М. К присоединением заявки Ю23) Приоритет 6 Р 7/О Государственный комет Совета Мнннотров ССС оо делам нзооретеннй н отноытнй(088,8) Опублнков Дата онуб ковано описано 72) Авторы пвобретенааЯ УПОРЯДОЧЕНИЯ Изобретение относится к цифровой вычислительной технике, может быть использовано всистемах обработки данных,Известно устройство упорядочения п слов,содержащее регистр исходной информации, регистр управления из и групп разрядов, регистррезультата и логические элементы 111,Недостатком устройства является недостаточное быстродействие в случае упорядочениябольших массивов слов,Наиболее близким техническим решением 1 аявляется устройство для упорядочения п слов;содержащее регистр исходной информации, регистр управления из п групп разрядов, регистррезультата 21.Однако недостаточное быстродействие в уст.ройстве обусловлено значительной задержкой 1 апробега информации через большое число яру.сов элементарных сортировщиков.Целью изобретения является повышениебыстродействия устройства упорядочения. Этодостигается тем, что оно содержит и дешифраторов, 1 и узлов уплотнения, 4 и коммутаторов; причем входы 1-го (1 = 1 - ; п) дешифра-.тора соединены с выходами старших разрядовт-ой группы регистра управления, первая группа входов каждого 1-го (1 = 1 + 4 п ) узлауплотнения соединена с соответствующим раз Ь рядным выходом регистра исходной информации, вторая группа входов. - с выходом младших разрядов соответствующей группы регнст. ра управления, а третья группа входов каждого 1-гО узла уплотнения соединена с выходом соответствующего дешифратора, первая и вторая группы выходов 1-го узла уплотнения соединены соответственно с первой и второй группой входов.1-го коммутатора, а выходы всех коммутаторов - со входамн регистра результата.На фнг. 1 показана блок. схема устройства упорядочения для слов; на фнг, 2 приведена блок-схема устройства для и - 1 б.Устройство содержит регистр исходной информации 1, регистр управления 2 из и групп разрядов, регистр результата 3, дешнфраторов 4, 4 п узлов уплотнения 5, каждый с 3-мя группами входов н 2-мя группами выхо. дов, и тп коммутаторов б с 2-мя группами входов каждый; входы 1-го дешнфратора 4 (1 = 1 - ; и) соедмнены с выходамн старших разрядов 1.ой группы регистра управленнтт 2; в 1-м узле уплотнения Ь (1 = 1 в ; 4 п ) первая группа входов соединена с выходами регистра исходной информации 1, вторая группа входов - с выходами младших разрядов сверх групп регистра управления 2, а третья группазс 1-ми выходами дешифраторов 4, первая и вторая группь 1 выходов 1-го узла уплотнения 5 соединены соответственно с первой и второй группой входов 1-го коммутатора б, а выходы всех коммутаторов б - со входами регистра результата 3.Узлы 5, б могут быть реализованы различными известными способами. На фиг, 3 и фиг. 4 приведен пример реализации этих узлов.Узел уплотнения 5 содержит блок сумматоров 7, уплотннтель кодов сдвига 8, уплотннтель информации 9 и уплотнитель младших разрядов 1 О. В узле уплотнения 5 первая группа входов соединена с информационными входами уплотнения 9, а первая группа выходов - с выходами уплотнителя 9; вторая группа выходов соединена с информационными входами уплотнителя О.Входы уплотнители кодов сдвига 8 соединены с выходами блока сумматоров 7, а вцходц узла 8 - с управляющими входами уплотнителей 9 и 10.Коммутатор 6 содержит блок дешифраторов и 4 п концентраторов 2. Первая группа входов коммутатора 6 соединена с информационными входами всех концентраторов 12; вто 5 1 О го рая группа входов этого коммутатора - со входами блока дешифраторов 11, выходы которогосоединены с управляющими входами концеитраторов 12, Выходы концентраторов 12 являютсявыходами коммутатора б,Блоки 7 - 12 могут выполняться различнцми известными способами.Устройство упорядочения работает следующим образом,В нщальном состоянии в регистр 1 заносится исходная информация (п слов), а в регистр управления 2 - номера слов в упорядо.ченном массиве (адреса), Длина каждого адреса - одгп. разрядов, Код 1-го адреса Э(1 = 1 - ; п) имеет группу старших и группумладших разрядов. Каждая группа имеет длину ф- одФ разрядов; 1.я группа старших разрядов поступает на 1-дешифратор 4 и дешифрнруется в нем; Группа младших разрядов всехадресов и исходная информация из регистра 1подаются иа 1-й.узел уплотнения 5 (1 =. 1 - ;1 п)е выходы всех дешифраторов 4 образуют 1-ю. маску управления, которая выделяет информацию и соответствующие группы младших разрядов адресов, значения которых лежат в интервале:(1 - 1) 4 л- - ; 1 п - 1В узле 5 под управлением 1-ой маски происходит выделение и уплотнение п слов и, соответствующих им, групп младших разрядов. Напри.меринформация х хв хз х 4 хь хв х 7 хвмаска О О 1 О 1 1 1 0результат хз хв хв ху 0 О О ОВ результате, на первой группе выходовузла 5 формируется плотный массив Мп слов,а на второй группе выходов - плотный массив соответствующих групп младших разрядов адресов.Таким образом, производится предварительное упорядочение исходной информации постаршим разрядам адресов.60 Затем с выхода )-го узла 5 О слов и групп младших разрядов .адресов подаются на 1-й коммутатор 6, где происходит упорядочение информации по младшим разрядам адресов.На выходе коммутаторов 6 все слова оказываются окончательно расставленными по адресам регистра управления 2. Упорядоченный массив слов заносится в регистр результата 3 и на этом работа устройства заканчивается, На рис. 2 в качестве примера показана блок-схема быстродействующего устройства упорядочения для 16 слов.В начальном состоянии в регистр 1 эаносится исходная информация (6 слов), а в региструправления 2 - номера слов в упорядоченном массиве (адреса), Длина каждого адреса 4 разряда. Код 1-го адреса (- : 6) имеет группу старших н группу младших разрядов, каждая группа имеет длину 2 разряда, 1-я группа старших разрядов поступает на 1-Й дешифратор 4 и дешифрируется в нем. Группц младших разрядов всех адресов и исходная информация (16 слов) из регистраподаются на 1-й узел уплотнения 5 (1 =- 1 - : 4); .е выходы всех дешифраторов 4 образуют 1-ю маску управления, которая выделяет информацию и соответствующие группы младших разрядов адресов, значения которых лежат в интервале: 4( - 1) - : - 4 - 1.Найример, первые выходы всех дешифраторов 4 образуют маску, которая в первом узле 5 из 16 слов и 16 групп младших разрядов адресов выделяет те, адреса которых лежат в интервале: 0 - ; 3.В узле 5 под управлением 1-й маски проис ходит выделение и уплотнение 4 слов и соответствующих им групп младших разрядов, В результате на первой группе выходов узла 5 формируется плотный массив 4 слов, а на второи группе выходов - плотный массив соответствующих групп младших разрядов адресов.Таким образом, производится предварительное упорядочение исходной информации по старшим разрядам адресов.Затем с выхода. 1-го узла 5 слова 4 и 4 группы младших разрядов подаются иа 1-й коммутатор б, где происходит упорядочение информации уже по младшим разрядам адресов.Разовая коммутация - есть произвольная перестановка и исходных разрядов (или слов).Пример 1;информация х хв хз х 4 хв хв ху хвадреса 3 1 2 4 7 8 6 5результат . х, х, х х 4 х хв хв хвКонцентрация . есть выборка одного изисходных разрядов (или слов).Пример 2.информация х,1 хх хз х 4 хв хв ху хвадресвыборки 5результат хвНа выходе коммутаторов все слова оказываются окончательно упорядоченными по адресам регистра управления 2. Далее упорядоченный массив слов заносится в регистр результата 3 и на этом работа устройства заканчивается.Таблица16 64 256 1024 24 36 46 58 80 216 448 800 и, словТтТр,т Таким образом, применение предложенногоустройства позволяет существенно сократитьвремя упорядочения массива слов. Например,при реализации такого устройства иа ннтегральных схемах серии 133 (Логика - 2) за 1 мк,сек. можно упорядочить массив нз 256 слов, ана устройстве - прототипе (при прочих равных условиях) - лишь из 32 слов,Затраты оборудования в предлагаемом устройстве (1.,) и в устройстве - прототипе (ЕДсоставляют:1. -" С,.вГв4 С 5 п Ьщ 3 игде С и С - некоторые константы, зависящие от набора логических элементов и реализации основных узлов. Быстродействие предлагаемого устройства, т.е, время упорядочения слов, равно:. Т ля = СОдиТ,.: =С 1 он,пгде: С н С - некоторые константы, зависящие от набора логических элементов.В таблицеприведены результаты расчета Т для п в пределах от 16 до 1024 слов. Для сравнения там же приведено быстродействие устройства - прототипа (ТдТ = .Сз одт пгде: Сэ - некоторая константа, зависящая от набора логических элементов. Отсюда следует, что характер роста 1., и1. в широких пределах примерно одинаков и дополнительные затраты оборудования при полученном выигрыше быстродействия незначительны.Формцла изобретенияУстройство для упорядочения и слов, со. щ держащее регистр исходной ннформацнн, ре.гистр управления из п групп разрядов, регистр результата, отличающееся тем, что с целью повышения быстродействия, оно содержит и де.шифраторов, 4 п узлов уплотнения, /и коммутаторов, причем входы-го (1 1 - ; п) дешнф.ратора соединены с выходами старших разрядов -ой группы регистра управления, первая группа входов каждого-го (1 = 1 - :4 п) узла уплотнения соединена с соответствующим раз.рядным выходом регистра исходной информаго ции, вторая группа входов с выходом младших разрядов соответствующей группы регист.ра управления, третья группа входов каждого 1-го узла уплотнения соединена с выходом соответствующего дешифратора, первая и вторая группы выходов 1-го узла уплотнения соединены соответственно с первой и второй группой входов)-го коммутатора, выходы - всех коммутаторов - со входами регистра результата,Источники информации, принятые во внимание при экспертизе;1, США патент 3428946, 340 в 1.2, 1972, 2, Папернов А. А Подымов В, Я. Методыупорядочения информации в цифровых системах, М Наука, 1973, стр, 133 - 138.Редактор Р. Антонов Заказ 2802/33 Составитель РЯвТек ред О, ЛуговаяТираж 826 ктор Н, Тупица, д, 4/5Проектная,ИПИ Государственного комитета Совета Мпо делам изобретен иВ н открыт13035, Москва, Ж, Раущская иаб Филиал ППП айатент, г, Ужгород, ул.