Устройство для упорядочения слов Советский патент 1978 года по МПК G06F7/00 

С j-ми выходами дешифраторов 4, первая и вторая группы выходов j-ro узла уплотнения 5 соединены соответственно с первой и второй группой входов j-ro коммутатора б, а выходы всех коммутаторов 6 - со входами регистра результата 3. Узлы 5, 6 могут быть реализованы различными известными способами. На фиг. 3 и фиг. 4 приведен пример реализации этих узлов. Узел уплотнения 5 содержит блок сумматоров 7, уплотнитель кодов сдвига 8, уплотнитель информации 9 и уплотнитель младших разрядов 10. В узле уплотнения 5 первая группа входов соединена с информационными входами уплотнения 9, а первая группа выходов - с выходами уплотнителя 9; вторая группа выходов соединена с информационными входами уплотнителя 10. Входы уплотнителя кодов сдвига 8 соединены с выходами блока сумматоров 7, а выходы узла 8 - с управляющими входами уплотнителей 9 и 10. Коммутатор 6 содержит блок дешифраторов ii н Л концентраторов 12. Первая группа входов коммутатора 6 соединена с информационными входами всех концентраторов 12; вторая группа входов этого коммутатора - со входами блока дешифраторов 11. выходы которого соединены с управляющими входами концентраторов 12. Выходы концентраторов 12 являются выходами коммутатора б. Блоки 7-12 могут выполняться различными известными способами. Устройство упорядочения работает следующим образом. . В йадальном состоянии в регистр I заносится исходная информация (п слов), а в регистр управления 2 - номера слов в упорядоченном массиве (адреса). Длина каждого адреса - Ibg2n разрядов. Код i-ro адреса (i 1 ч- п) имеет группу ста|ршнх и группу младших разрядов. Каждая группа имеет длину 4- Iog2n разрядов; i-я группа старших разрядов поступает на i-дешифратор 4 и дешифрируется в нем. Группа младших разрядов всех адресов к исходная информация из регистра 1 подаются на j-и узел уплотнения 5 (j 1 -r-Vn) j- выходы всех дешифраторов 4 образуют j-ю маску управления, которая выделяет информацию и соответствующие группы младших разрядов адресов, значения которых лежат и нитервале: (j - 1) -г- jvfff- I В узле 5 под управлением j-ой маски происходит выделение и уплотнение п слов и, соответспзующих им, групп младших разрядов. Напримеринформация Xi Ху Xz x х XQ x. к маска00101110 результатХг х л:в Jt 0000 В результате, на первой группе выходов узла 5 формируется плотный массив VTT слов, а на второй группе выходов - плотный массив соответствующих групп младших разрядов адресов,, Таким образом, производится предварительное упорядочение исходной информации по старшим разрядам адресов. Затем с выхода j-ro узла 5ViT слов и групп младших разрядов адресов подаются на j-fi коммутатор 6, где происходит упорядочение информации по младшим разрядам адресов. На выходе коммутаторов б все слова оказываются окончательно расставленными по адресам регистра управления 2. Упорядоченный массив слов заносится в регистр результата 3 и на этом работа устройства заканчивается. На рис. 2 в качестве примера показана блок-схема быстродействующего устройства упорядочения для 16 слов. В начальном состоянии в регистр 1 заносится исходная информация (16 слов), а в регистр управления 2 - номера слов в упорядоченном массиве (адреса). Длина каждого адреса 4 разряда. Код i-ro адреса (i 1 ч- 16) имеет группу старших и группу младших разрядов, каждая группа имеет длину 2 разряда, i-я группа старших разрядов поступает на i-й дешифратор 4 и дешифрируется в нем. Группы младших разрядов всех адресов и исходная информация (16 слов) из регистра 1 подаются на J-fi узел уплотнения 5 (j 1-4-4); j-e выходы всех дешифраторов 4 образуют j-ю маску управления, которая выделяет информацию и соответствующие группы младших разрядов адресов, значения которых лежат в интервале: 4(j - 1) -f. Д{ 1 -7- tj1. Например, первые выходы всех дешифраторов 4 образуют маску, которая в первом узле 5 из 1 в слов и 16 групп младших разрядов адресов выделяет те, адреса которых лежат в интервале; 0-7-3. В узле 5 под управлением j-й маски происходит выделение и уплотнение 4 слов и соответствующих им групп младших разрядов. В результате на первой группе выходов узла 5 формируется плотный массив 4 слов, а на второй группе выходов - плотный массив соответствующих групп младших разрядов адресов. Таким образом, производится предварительное упорядочение исходной информации по старшим разрядам адресов. Затем с выхода |-го узла 5 слова 4 и 4 группы младших разрядов подаются на j-ft коммутатор б, где происходит упорядочение информации уже по младшим разрядам адресов. Разовая коммутация - есть произвольная перестановка п исходных разрядов (или слов). пример /. информация х JC2 г Х4 х& х Xi х адреса3-1247865 результатХз х Хг х Xj х Же Хъ Концентрация есть выборка одного из исходных разрядов (или слов). Пример 2. информация х x-i хз х хв хв х х адрес. выборки 5 результат jcs На выходе коммутаторов все слова оказываются окончательно упорядоченными по адресам регистра управления 2, Далее упорядоченный массив слов заносится в регистр результата 3 и на этом работа устройства заканчивается. Быстродействие предлагаемого устройства, т.е. время упорядочения слов, равно: Т( Т чпл + Т.п„л. . Т 3/1.0 GI logz Tvo«« С2 lOgzfl где: СI и Сг - некоторые константы, зависящие от набора логических элементов. В таблице 1 приведены результаты расчета Ti для п в пределах от 16 до 1024 слов. Для с-равнения там же приведено быстродействие устройства - прототипа (Т) Тг 5 Сз log п где: Сз - некоторая константа, зависящая от набора логических элементов. Табли ца i Таким образом, применение предложенного устройства позволяет существенно сократить время упорядочения массива слов. Например, при реализации такого устройства на интегральных схемах серии 133 («Логика-2) за 1 мк. сек. можцр упорядочить массив из && слов, а на устройстве - прототипе (при прочих рав ных условиях) - лишь из 32 слов. Затраты оборудования в предлагаемом устройстве (Li) ив устройстве - прототипе (Lj) составляют: LI 1.2 Cs-n-logfn где €4 и С 5 - некоторые константы, зависящие от набора логических элементов и реализации основных узлов. Отсюда следует, что характер роста I,i и 12 в широких пределах примерно одинаков и дополнительные затраты оборудования при полученном выигрыше быстродействия незначительны. Формула изобретения Устройство для упорядочения п сло§, со-, держащее регистр исходной информация, регистр управления из п групп разрядов, регистр результата, отличающееся тем, что с целью повышения быстродействия, оно содержит п дешифраторов, (пузлов уплотнения, ПГ коммутаторов, причем входы i-ro (i 1 - п) дешифратора соединены с выходами старших разрядов i-ой группы регистра управления, первая группа входов каждого -го (j 1 ) узла уплотнения соединена с соответствующим разрядным выходом регистра исходной информации, вторая группа входов с выходом младщих разрядов соответствующей группы регистра управления, третья группа входов каждого j-ro узла уплотнения соединена с выходом соответствующего дешифратора, первая и вторая группы выходов -го узла уплотнения соединены соответственно с первой и второй группой входов j-ro коммутатора, выходы - всех коммутаторов - со входами регистра результата. Источники информации, принятые во внимание при экспертизе: 1.США патент 3428946, 340-146.2, 1972. 2.Папернов А. А. Подымов В. Я. Методы упорядочения информации в цифровых системах, М., «Наука, 1973, стр. 133-138.

IJ

9u.t

I