Устройство для сдвига информации

СООЭ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 9) 01) А зб С 06 Г 7/38 ВСБСОЖ ЗОБ ТЕЛЬСТВ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ ОПИСАНИ И АВТОРСКОМУ(56) 1. Авторское свидетельство СССРР 864281, кл. С. 06 Р 7/38, 1979.2; Авторское свидетельство СССР9 439017, кл. С 06 Р 7/38, 1973(54)(57) УСТРОЙСТВО ДЛЯ СДВИГА ИНФОРМАЦИИ, содержащее коммутирующиеячейки, информационные входы которых являются инФормационными входамиустройства, а выходы - выходами уст-,ройства, о т л и ч а ю щ е е с ятем, что, с целью расширения Функциональных возможностей устройства путем реализации расстановки элементовмассива, в него введены восемь сумматоров и четыре узла формированиякодов расстановки, каждый из которых включает элемент НЕ и группуиз четырех мультиплексоров, соответствующие управляющие входы которых.объединены, в первом узле Формирования кодов расстановки управляющиевходы мультиплексоров соединены соответственно с входами первого и второго разрядов кода маски расстановКиустройства, информационные входы первого мультиплексора подключены соответственно к шине логической "1" устройства, через элемент НЕ к входутретьего разряда кода маски расстановкиустройства и к шине логического "0" устройства, информационныевходы второго мультиплексора - к входу третьего разряда кода маски расстановки устройства, к шинам логического "О" и "1" устройства и черезэлемент НЕ - к входу третьего разряда кода маски. расстановки устройства,информационные входы третьего мультиплексора соединены попарно с шинамилогического "О" и "1" устройства, информационные входы четвертого мультиплексора объединеныи соединены с входомтретьего разряда кода расстановкикода маски устройства, управляющиевходы мультиплексоров второго узлаФормирования кодов расстановки подключены соответственно к входам четвертого и пятого разрядов кода маски расстановки, а информационныевходы первого мультиплексора соединены попарно с входами логической "1"и логического "О" устройства, три инФормационных входа второго мультиплексора подключены к шине логической"1", а четвертый ",к шине логи"ческого "О" устройства, первый информационный вход третьего мультиплексора соединен с шиной логического"0" устройства, а три остальных через элемент НЕ - с входом шестогоразряда кода маски расстановки уст-,ройства, информационные входы четвертого. мультиплексора - с шиной логи-,.ческого "О" устройства, с входом шестого разряда кода маски расстановкиустройства и шиной логической "1"устройства, управляющие входы мультиплексора третьего узла формированиякодов расстановки подключены соответственно к входам первого и второгоразрядов кода маски расстановки устройства, информационные входы первого и второго мультиплексоров попарно объединены и подключены к входу,Редактор Е. 2.1 /33ВНИИПИ дписное комитета СССРоткрытийская наб., д. 4/5 ал 1 ШП "Патент", г. Ужгород, ул. Проектная, 4.Тираж 698Государственногопо делам изобретений35, Москва, Ж, Раук ванова Корректор А, Зимокосов11176,3 третьего разряда кода маски расстановки устройства и к этому же входу через элемент НЕ, информационные вхо-, ды третьего мультиплексора соединены через элемент НЕ с входом третьего разряда кода маски расстановки устройства, подключенным также к объединенным информационным входам четвер того мультиплексора, управляющие входы мультиплексоров четвертого узла формирования кодов расстановки подключены соответственно к входам четвертого и пятого разрядов кода маски расстановки устройства, информационные входы первого мультиплексора попарно объединены и подключены соответственно к шинам логической "1" и "О" устройства, информационные входы второго мультиплексора попарно объединены и подключены соответственно к шинам логического "О" и "1" устройства, первый информационный вход третьего мультиплексора соединен через элемент НЕ с входом шестого разряда кода маски. расстановки устройства, который, соединен с осталь 2ными информационными входами третьего мультиплексора, информационныевходы четвертого мультиплексора попарно объединены и соединены соответственно с входом шестого разряда кода маски расстановки устройства и сэтим же входом через элемент НЕ, входы константы устройства соединеныс входами первого разряда первой группы входов сумматора, входы второгоразряда первой группы входов которого подключены к выходам мультиплексоров первого и третьего узлов формирования кодов расстановки, а входы тре"тьего разряда первой группы входовсумматора - к выходам мультиплексоров второго и четвертого узлов формирования кодов-расстановки, входывторой группы всех сумматоров соеди-,нены с входами кода сдвига устройства, каждая коммутирующая ячейкасодержит восемь мультиплексоров, соответствующие информационные вхоДыкоторых объединены, а управляющие подключены к выходам соответствующегосумматора.Наиболее близким по технической сущности к предлагаемому является устройство сдвига, содержащее блок ;управления, регистр информационных .слов иинформационный сдвигающий блок состоящий из нескольких ярусов комму" .тирующих элементов, входы коммутирующих элементов первого яруса соедине. ны с выходами регистра информационнык слов, выход 1 -го коммутирующего элемента 1 -го яруса соединен Изобретение относится к цифровой вычислительной технике и может быть использовано для расстановки и сдвига информации.Известно устройство для сдвига информации, содержащее регистр числа, регистр сдвига и коммутирующие ячейки 1 Д .Устройство производит сдвиг всех элементов информации на одинаковое число позиций за один такт работы, однако не позволяет осуществить их расстановку на разное число позиций. Ъс входом-го коммутирующего эле 1мента (+1)-го яруса и с входом1-2-го коммутирующего элемента(1 +1)-го яруса, первый вход Соединен 5 с выходом-го коммутирующего элемента 6-1)-го, яруса, а второй вход - свыходом 1+2 -го коммутирующего элемента (1-1)-го яруса, блок управлениясодержит регистр кодов управления и 1 О сдвигающий блок кодов управления, состоящий из несколъких ярусов логичес- .ких элементов, причем первый выход) в .го логического элемента 1 -го яруса сдвигающего блока управления сое динен с входами ) -го и 1-2" го логических элементов (+1)-го яруса,.второй и третий выходи соединены соответственно с третьйм.и четвертымвходами 1 -го коммутирующего элемента 20 1-го яруса информационного сдвигающего блока, а входы соединены соответственно с выходами 1 -го.и 1 -2 1-гологических элементов .( "1)-го ярусасдвигающего блока кодов управления, 25 входы первого яруса которого соеди-,3 11176 иены с выходами регистра кодов управленияУстройство позволяет осуществить кольцевой сдвиг всех элементов информацйи, но не позволяет осуществить расстановку информации.Цель изобретения - расширение Функциональных возможностей устройства путем реализации расстановки элементов массива информации, Под 10 расстановкой понимается раздвижка плотно расположенных элементов входного массива информации на различное число позиций с сохранением исходного порядка следования под управлением маски и кода сдвига. Маской называется двоичный код, где единицами отмечены те позиции, на которые под-. лежит расставить элементы входного массива информации. Величина кода. сдвига определяет смещение центра плотнбго входного массива относительно середины строки информации, где под серединой строки информации понимается граница между третьим и четвер тым байтами информации, а под центром плотного массива - граница между байтами, расставляемыми в левой половине и байтами, расставляемыми в правой половине строки. ЭО 1Поставленная цель достигается тем, что в устройство для сдвига информации, содержащее коммутирующие ячейки информационные входы которых являются информационными входами устройства, а 35 выходы - выходами устройства, введены восемь сумматоров и четыре узла форми.рования кодов расстановки, каждый из которых включает элемент НЕ и группу из четырех мультиплексоров, соответ ствующие управляющие входы которых объединены, в первом узле формирования кодов расстановки управляющие входы мультиплексоров соединены соответственно с входами первого и второ го разрядов кода маски расстановки устройства, информационные входы пер" ваго мультиплексора подключены соот- ветственно к шине логической "1" устройства, через элемент НЕ к входу тре-, 50 тьего разряда кода маски расстановки устройства и к шине логического "О" устройства, информационные входы вто рого мультиплексора -,к входу третьего разряда кода маски расстановки 55 устройства к шинам логического "О" и "1" устройства и через элемент НЕ к входу третьего разряда кода маски 32 4 расстановки устройства, информационные входы третьего мультиплексора соединены попарно с шинами логического "О" и "1" устройства, информационные входы четвертого мультиплексора объединены и соединены с входом третьего разряда кода расстановки кода маски устройства управляющие входы мультиплексоров второго узла Формирования кодов расстановки подключены соответственно к входам четвертого и пятого разрядов кода маски расстановки, а информационные входы первого мультиплексора соединены попарно с входами логической "1" и логического "О" устройства, три ин" формационных входа второго, мультиплексора подключены к шине логическойа четвертый - к шине логического "О" .устройства, первый информационный вход третьего мультиплексора соединен с шиной логического "О" устройства, а три остальных через элемент НЕ - с. входом шестого, разряда када маски расстановки устройства, информационные входы четвертого мультиплексора с шиной логического "О" устройства, с входом шестого разряда кода маски .расстановки устройства и шинойлогической ".1" устройства, управляющие входы мультиплексоров третьего узла формирования кодов расстановки подключены соответственно к входам первого и второго разрядов кода маски расстановки устройства, информационные входы первого и второго мультиплексоров попарно объединены и подключены к входу третьего разряда кода маски расстановки устройства и к этому же входу через элемент НЕ,;. информационные входы третьего мульти- плексора соединены через элемент НЕс входом третьего разряда кода маски расстановки устройства, подключенньв% также к объединенным информационным входам четвертого мультиплексора, управляющие входы мультиплексоров четвертого узла Формирования кодов расстановки подключены соответствен, но к входам четвертого и пятого раз-, ,рядов кода маски расстановки устройства, информационные входы первого ,мультиплексора попарно объединены и подключены соответственно шинам логической "1" и "О" устройства, информационные входы второго мультиплексора попарно объединены и подключены соответственно к шинам логиЯческого "О" и "1" устройства, первьйинформационный вход третьего мультиплексора соединен через элемент НЕс входом шестого разряда кода маскирасстановки устройства, который сое-динен с остальными информационными 5входами третьего мультиплексора, ин-,формационные входы четвертого мультиплексора.попарно объединены и соединены соответственно с выходом шес-.,того разряда кода маски расстановки ,16устройства и с этим же входом черезэлемент НЕ, входы константы устройства соединены с входами первого разряда первой группы входов сумматора,входы второго разряда первой группы, 15входов которого подключены к выходаммультиплексоров первого и третьегоузлов формирования кодов расстановкиа входы третьего разряда первой группы входов сумматора - к вынодам муЛьтиплексоров второго и четвертого узлов формирования кодов расстановки,входы второй группы всех сумматоров,соединены с входами кода сдвига устройства, каждая коммутирующая ячейка 2содержит восемь мультиплексоров, соответствующие информационные входы которых объединены, а управляющие подключены к выходам соответствующегосумматора. МНа фиг. 1 представлена блок-схемаустройства для сдвига информации (восемь байтов); на фнг. 2 - функциональ, ная схема коммутирующей ячейки на восемьивходов и восемь выходов (типа 8 и 8 ) ф на зфиг. 3 - пример реализации узлов формирования кодов расстановки, на фиг.4 - .схема сумматора,Устройство содержит информационные входы 1, выходы 2, входы 3 константы, входы 4 кода маски расстановки,. входы 5 кода сдвига, узлы 6-9.формирования кодов расстановки, сумматоры 10, коммутирующие ячейки 11.Каждая коммутирующая ячейка содержит восемь мультиплексоров 12, Каждыйузел формирования кодов расстановки,содержит четыре мультиплексора 13-16,элемент ВЕ 17.Устройство работает следующим об Ор.азом,Коды расстановки формируются в дваэтапа: сначала формируются коды шинуправления расстановкой от середины1 строки влево и вправо, а затем эти. коды корректируются путем сложения ..с кодом сдвига и тем самым учитывается смещение исходного плотного мас." сина относительно середины строкиинформации.Узлы 6-9 формируют коды управления расстановкой. Эти узлы могут бытьреализованы известными методами логического синтеза в соответствии стаблицами интенсивности,1-4.В табл. 1 (узел 6) и 2 (узел 7),определены восемь вторых разрядов(Р 2) трехразрядных кодов управлениярасстановкой Н-БОР 2,В табл. 3 (узел 8) и(узел 9),определены третьи разряды (РЗ) кодовуправления расстановкой Н"Б 0-7 РЗ.Первые разряды кодов управления расстановкой Н-БОР 1, равны константе:00001111, которая подается на входыконстанты устройства.Расстановка элементов правой илевой половин строки информации производится независимо, поэтому формирование кодов управления расстанов- .кой существенно упрощается.В таблице истинности приняты:;И-РО- маска, разряды О-.7Н-БОР 23 - коды управления расстановкой байты 0-7 разряды 23.Из таблиц 1-4 видно, что второйи третий разряды кодов управления расстановкой зависят от малого числа переменных (1-3 переменных) и их реализация не вызывает трудностей (фиг. 3).На сумматорах 101-108 коды управления расстановкой Н-БОР 1-3 суммируются с кодом сдвига СД-Р 1-3.Устройство работает следующим образомегВ исходном состоянии на входы 1 но- даются коды информации А-Б 0-7 РО-З.(восемь байтов БОпо девять разрядов 0-9), на входы 4 и 5 подаются коды управления: маска расстановки И-7 и код сдвига СД-Р 1-3. Сначала в узлах 6-9 формируются коды управ".ления расстановкой, которые поступают на первые группы входов суииаторов 101-ЮВ. На эти же входы сумма.- торов подается старший разряд кодов управления расстановкой Н-Б 0-7 РОд =00001111, Далее сумматоры прибавляют к этим кодам константу сдвига СД-Р 1-3. На выходах сумматоров формируются коды У-Г 0-7.Р 1-3,которые поступают на управляющие входы коммутирующих ячеек 114 -11 . Затем ячей.ки 111-1 1 выполняют требуемую коммутацию и. выдают расставленную ин-, 4 юРмацию В-БОРО.П р и м е р. Дан код маскй расстановки: М-РОф 7.01010011, Код сдвигаравен; СД=Р 1 Ф 3=110, т.е. исходныйплотный массив расположен в первыхчетырех байтах (элементах) строки.входной информации.На выходе узлов 6-9 формируютсякоды в соответствии с. таблицами 1-4.,Н-БОР 2 01011100,Н-БОР 3=10011001.Коды управления расстановкой имеют следующий вид:Н-БОР 1-3 (Х, 010, Х, 011,Х,Х, 100, 101.).На выходе узлов 10-108 после суммировайия с константой СД-Р 1-3 форми:руются кодыУ ГОР 1-3 (Х, 000, Х, 001,Х,Х,010, 011)В результате коммутации на выходустройства выдается кодВ-Б 0-7 РОф А-БХ, О,Х,1,Х,Х,2,3 Р 0-8.Таким образом произведена расстановка элементов плотного входногомассива на позиции, помеченные "еди.ницами" маски расстановки.Зчаком Х обозначены коды управления и позиции выходного растановлен:ного массива, соответствующие "нулям". маски расстановки. Но в предлагаемомустройстве операции над элементами массива входной информации, отмеченными"нулями" маски для простоты описанияне рассматриваются. В действительности под нулями" маски также происходит расстановка элементов массиваинформации, следующего за первым мас 17632сивом, расставляемы.- по "единицам",,но с изменением исходного порядкаследования на обратный.Аналогично может быть произведе на расстановка элементов информацииисходного массива, местоположениекоторого задано кодом сдвига, на лю-бые позиции, определяемые кодом мас-ки. Устройство позволяет также реализовать кольцевой сдвиг без расстановмки. Для этого на вторые управляющие:входы устройства подается код маски"Все 17, а на третьи управляющие входы подается код сдвига (влево) 15 СД-РО. Например, для сдвига массиваначинающегося с крайней левойпозиции, на три позиции вправо, необходимоподать код маски "Все 1"и код сдвига СД-РО101.20 Из рассмотренных примеров следуетправильность функционирования устройства т.е. возможность выполнениярасстановки массива под управлениеммаски и кода сдвига.В ряде случаев обработки бопьщихмассивов требуется организовать слияние двух и более отдельных массивовв один таким образом, чтобы элементы одного массива были расположе ны между элементами другого. Этазадача реааетс путем расстановкиэлементов массивов. Использование,предлагаемого устройства для расстановки информации в составе многопро,цессорной вычислительной системы позволяет реалнзовагь этот и другиеалгоритмй с высокой производитель- ностью,О 0 О 0 О 0 О О ОО 0 0 0 О 0 О 0 О О О 0 0 0 0 О Таблица 2 Н-Б 4-7 Р 2 М-Р 4-6 Бб , Б 7 Б 5 О О 0 О О О 0 О О О О О О 0 О О 0 О О О О О 1 О О 0 О О е 4 е ФВЮВВВВР 1 Р 2 ЕВЕЕЕЕЕЮЕЕ тВВВВ БО Б 1, Б 2,: БЗ Е ЮВВФВ Ю ЕФВ Е Е ФВЕЕЮЮЮЮЮЮЕЮЮЮВ