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

 

УСТРОЙСТВО ДЛЯ СДВИГА ИНФОРМАЦИИ , содержащее коммутирующие ячейки, информационные входы которых являются информационными входамиустройства , а выходы -.выходами уст-. ройства, отличающееся тем, что, с целью расширения функциональных возможностей устройства путем реализации расстановки элементов массива, в него введены восемь сумматоров и четыре узла формирования кодов расстановки, каждый из которых включает элемент НЕ и группу из четырех мультиплексоров, соответствующие управляющие входы которых, объединены, в первом узле формирования кодов расстановки управляющие входы мультиплексоров соединены соответственно с входами первого и второго разрядов кода маски расстанов си устройства, информационные входы первого мультиплексора подключены соответственно к шине логической 1 устройства , через элемент НЕ к входу третьего разряда кода маски расстановки устройства и к шине логического О устройства, информационные входы второго мультиплексора - к входу третьего разряда кода маски расстановки устройства, к шинам логического О и 1 устройства и через элемент НЕ - к входу третьего разряда кода маски, расстановки устройства, информационные входы третьего мультиплексора соединены попарно с шинами логического О и 1 устройства, информационные входы четвертого мультиплексора объединены и соединены с входом третьего разряда к.ода расстановки кода маски устройства, управляющие входы мультиплексоров второго узла формирования кодов расстановки подключены соответственно к входам четвертого и пятого разрядов кода маски расстановки, а информационные входы первого мультиплексора соедине (Л ны попарно с входами логической 1 и логического О устройства, три инС . формационных входа второго мультиплексора подключены к шине логической 1, а четвертый -,к шине логического О устройства, первый информационный вход третьего мультиплексора соединен с шиной логического О устройства, а три остальных через элемент НЕ - с входом шестого разряда кода маски расстановки устройства , информационные входы четвертого мультиплексрра - с шиной логи-, ческого О устройства, с входом шестого разряда кода маски расстановки устройства и пшной логической 1 устройства, управляющие входы мультиплексора третьего узла формирования кодов расстановки подключены соответственно к входам первого и второго разрядов кода маски расстановки устройства , информационные входы первого и второго мультиплексоров по- ; парно объединены и подключены к входу

СООЭ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

09) 01) з 5)) а 06 F 7/38

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

И ABTOPCHOMV СВИДЕТЕЛЬСТВУ

3CHCOfe (21) 3556578/24-24 (22) ?2.02.83 (46) 07.10.84. Бюл. У 37 (72) M.Ñ. Белков, Е.А. Братальский, В.С. Иванбва и Я.И.. Свирский (53) 681.325(088.8) (56) 1. Авторское свидетельство СССР

Ф 864?81, кл. С- 06 F 7/38, 1979.

2; Авторское свидетельство СССР

В 439017, кл. G 06 F 7/38, 1973 (прототип). (54) (57 ) УСТРОЙСТВО ДЛЯ СДВИГА ИНФОРКАЦИИ, содержащее коммутирующие ячейки, информационные входы которых являются информационными входами. устройства, а выходы — выходами уст-. ройства, о т л и ч а ю щ е е с я тем, что, с целью расширения функциональных возможностей устройства путем реализации расстановки элементов массива, в него введены восемь сумматоров и четыре узла формирования кодов расстановки, каждый из которых включает элемент НЕ и группу из четырех мультиплексоров, соответствующие управляющие входы которых. объединены, в первом узле формирования кодов расстановки управляющие входы мультиплексоров соединены соответственно с входами первого и второго разрядов кода маски расстановКи устройства, информационные входы первого мультиплексора подключены соответственно к шине логической "1" устройства, через элемент HE к входу третьего разряда кода маски расстановки устройства и к шине логического "0" устройства, информационные входы второго мультиплексора — к входу третьего разряда кода маски расстановки устройства, к шинам логического "0" и "1" устройства и через элемент НŠ— к входу третьего разряда кода маски расстановки устройства, информационные входы третьего мультиплексора соединены попарно с шинами логического "0" и "1" устройства, информационные входы четвертого мультиплексора объединеныи соединены с входом третьего разряда кода расстановки кода маски устройства, управляющие входы мультиплексоров второго узла формирования кодов расстановки подключены соответственно к входам четвертого и пятого разрядов кода маски расстановки, а информационные входы первого мультиплексора соединены попарно с входами логической "1" и логического "0" устройства, три информационных входа второго мультиплексора подключены к шине логической "1", а четвертый ",к шине логического "0" устройства, первый информационный вход третьего мультиплексора соединен с шиной логического

"0" устройства, а три остальных через элемент НŠ— с входом шестого разряда кода маски расстановки уст- . ройства, информационные входы четвертого мультиплексора — с шиной логи-,. ческого "0" устройства, с входом шестого разряда кода маски расстановки устройства и шиной логической "1" устройства, управляющие входы мультиплексора третьего узла формирования кодов расстановки подключены соответственно к входам первого и второго разрядов кода маски расстановки устройства, информационные входы первого и второго мультиплексоров попарно объединены и подключены к входу

1117áЗ .третьего разряда кода маски расстановки устройства и к этому же входу через элемент НЕ, информационные вхо-, ды третьего мультиплексора соединены через элемент НЕ с входом третьего разряда кода маски расстановки устройства, подключенным также к объединенным информационным входам четвер. того мультиплексора, управляющие входы мультиплексоров четвертого узла формирования кодов расстановки подключены соответственно к входам четвертого и пятого разрядов кода маски расстановки устройства, информационные входы первого мультиплексора попарно объединены и подключены соответственно к шинам логической "1" и

"0" устройства, информационные входы второго мультиплексора попарно объединены и подключены соответственно к шинам логического "О" и "1" устройства, первый информационный вход третьего мультиплексора соединен через элемент НЕ с входом шестого разряда кода маски. расстановки устройства, который, соединен с осталь? ными информационными входами третьего мультиплексора, информационные входы четвертого мультиплексора попарно объединены и соединены соответственно с входом шестого разряда кода маски расстановки устройства и с этим же входом через элемент НЕ, входы константы устройства соединены с входами первого разряда первой группы входов сумматора, входы второго разряда первой группы входов которого подключены к выходам мультиплексоров первого и третьего узлов формирования кодов расстановки, а входы третьего разряда первой группы входов сумматора — к выходам мультиплексоров второго и четвертого узлов формирования кодов-расстановки, входы второй группы всех сумматоров соеди-, нены с входами кода сдвига устройства, каждая коммутирующая ячейка содержит восемь мультиплексоров, соответствующие информационные вхоДы которых объединены, а управляющие под ключены к выходам соответствующего сумматора.

Изобретение относится к цифровой вычислительной технике и может быть использовано для расстановки и сдвига информации.

Известно устройство для сдвига информации, содержащее регистр числа, регистр сдвига и коммутирующие ячейки .(1) .

Устройство производит сдвиг всех элементов информации на одинаковое число позиций за один такт работы, :однако не позволяет осуществить их расстановку на разное число позиций. Наиболее близким по технической сущности к предлагаемому является устройство сдвига, содержащее блок

;управления, регистр информационных .слов и информационный сдвигающий блок состоящий из нескольких ярусов комму" .тирующих элементов, входы коммутирующих элементов первого яруса соедине. ны с выходами регистра информацион- . ных слов, выход j -го коммутирую щего элемента j -го яруса соединен

2 с входом j -го коммутирующего эле1 мента (1+1)-ro яруса и с входом

1-2-го коммутирующего элемента (+1)-ro яруса, первый вход соединен

5 с выходом 1-го коммутирующего элемента (i-1)-го, яруса, а второй вход — с выходом j +2 -ro коммутирующего элемента (i -1)-ro яруса, блок управления содержит регистр кодов управления и

10 сдвигающий блок кодов управления, состоящий из несколъких ярусов логичес- . ких элементов, причем первый выход

j †-.. го логического элемента 1 -ro яруса сдвигающего блока управления сое15 динен с входами ) -го и j --2" го логических элементов (<+1)-ro яруса, .второй и третий выходи соединены соответственно с третьйм.и четвертым входами -го коммутирующего элемента

20 j-го яруса информационного сдвигающего блока, а входы соединены соответственно с выходами j --ro .и j -2 -го .логических элементов .(i -1)-го яруса сдвигающего блока кодов управления, 25 входы первого яруса которого соеди- .

3 11176 иены с выходами регистра кодов управления (Г) .

Устройство позволяет осуществить кольцевой сдвиг всех элементов информацни, но не позволяет осуществить расстановку информации.

Цель изобретения - расширение функциональных возможностей устройства путем реализации расстановки элементов массива информации. Под 10 расстановкой понимается раздвижка плотно расположенных элементов входного массива информации на различное число позиций с сохранением исходного порядка следования под управлением маски и кода сдвига. Маской называется двоичный код, где единицами отмечены те позиции, на которые под-. лежит расставить элементы входного массива информации. Величина кода. сдвига определяет смещение центра плотнбго входного массива относительно середины строки информации, где под серединой строки инфбрмации понимается граница между третьим и четвер- 25 тым байтами информации, а под центром плотного массива — граница между байтами, расставляемыми в левой половине и байтами, расставляемыми в правой половине строки. ЭО

Поставленная цель достигается тем, что в устройство для сдвига информации, содержащее коммутирующие ячейки,, информационные входы которых являются информационными входами устройства, а35 выходы — выходами устройства, введены восемь сумматоров и четыре узла формирования кодов расстановки, каждый из которых включает элемент НЕ и группу из четырех мультиплексоров, соответ- 40 ствующие управляющие входы которых объединены, в первом узле формирования кодов расстановки управляющие входы мультиплексоров соединены соответственно с входами первого и второ- 45 го разрядов кода маски расстановки устройства, информационные входы первого мультиплексора подключены соот-. ветственно к шине логической "1" устройства, через элемент НЕ к входу тре- 50 тьего разряда кода маски расстановки устройства и к шине логического "0" устройства, информационные входы вто" рого мультиплексора -,к входу третьего разряда кода маски расстановки 55 устройства к шинам логического "О" и "1" устройства и через элемент НЕ к входу третьего разряда кода маски

32 4 расстановки устройства, информационные входы третьего мультиплексора соединены попарно с шинами логического "0" и "1" устройства, информационные входы четвертого мультиплексора объединены и соединены с входом третьего разряда кода расстановки кода маски устройства,, управляющие входы мультиплексоров второго узла формирования кодов расстановки подклю1, чены соответственно к входам четвертого и пятого разрядов кода маски расстановки, а информационные входы первого мультиплексора соединены попарно с входами логической "1" и логического "0" устройства, три ин" формационных входа второго, мультиплексора подключены к шине логической

"1", а четвертый — к шине логического

"0" .устройства, первый информационный вход третьего мультиплексора соединен с шиной логического "0" устройства, а три остальных через элемент НŠ— с. входом шестого, разряда када маски расстановки устройства, информационные входы четвертого мультиплексора с шиной логического "0" устройства, с входом шестого разряда кода маски .расстановки устройства и шиной логической ".1" устройства, управляющие входы мультиплексоров третьего узла формирования кодов расстановки подключены соответственно к входам первого и второго разрядов кода маски расстановки устройства, информационные входы первого и второго мультиплексоров попарно объединены и подключены к входу третьего разряда . кода маски расстановки устройства и к этому же входу через элемент НЕ,;. информационные входы третьего мульти плексора соединены через элемент НЕ с входом третьего разряда кода маски расстановки устройства, подключенныьцi также к объединенным информационным входам четвертого мультиплексора, управляющие входы мультиплексоров четвертого узла формирования кодов расстановки подключены соответствен, но к входам четвертого и пятого раз-, . рядов кода маски расстановки устройства, информационные входы первого ,мультиплексора попарно объединены и подключены соответственно шинам логической "1" и "О" устройства, ин4ормационцые входы второго мульти:плексора попарно объединены и подключены соответственно к шинам логиЯ ческого "0" и "1" устройства, первьй

1117632 информационный вход третьего мультиплексора соединен через элемент НЕ с входом шестого разряда кода маски расстановки устройства, который сое- динен с остальными информационными 5 входами третьего мультиплексора, ин-, формационные входы четвертого мультиплексора.попарно объединены и соединены соответственно с выходом шес- .,того разряда кода маски расстановки .16 устройства и с этим же входом через элемент НЕ, входы константы устройства соединены с входами первого разряда первой группы входов сумматора, входы второго разряда первой группы, 15 входов которого подключены к выходам мультиплексоров первого и третьего узлов формирования кодов расстановкии а входы третьего разряда первой группы входов сумматора — к вынодам муЛь- 26 типлексоров второго и четвертого ysлов формирования кодов расстановки, входы второй группы всех сумматоров, соединены с входами кода сдвига устройства, каждая коммутирующая ячейка 2 содержит восемь мультиплексоров, соответствующие информационные входы которых объединены, а управляющие подключены к выходам соответствующего сумматора. 36

На фиг. 1 представлена блок-схема. устройства для сдвига информации (восемь байтов); на фиг. 2 — - функциональ, ная схема коммутирующей ячейки на восемь и входов и восемь выходов (типа 8 и 8 ); на з фиг. 3 — пример реализации узлов Формирования кодов расстановки, на фиг.

4 — .схема сумматора.

Устройство содержит информационные входы 1, выходы 2, входы 3 константы, входы 4 кода маски расстановки,. входы 5 кода сдвига, узлы 6-9 формирования кодов расстановки, сумматоры 10, коммутирующие ячейки 11.

Каждая коммутирующая ячейка содержит восемь мультиплексоров 12. Каждый .узел формирования кодов расстановки

:содержит четыре мультиплексора 13-16 .элемент НЕ 17.

Устройство работает следующим об- 5О р.азом .

Коды расстановки формируются в два этапа: сначала формируются коды шин

: управления расстановкой от середины

1строки влево и вправо, а затем эти . коды корректируются путем сложения

:c кодом сдвига и тем самым учитывается смещение исходного плотного мас." сина относительно середины строки информации.

Узлы 6-9 формируют коды управления расстановкой. Эти узлы могут быть реализованы известными методами логического синтеза в соответствии с таблицами интенсивности,1-4.

В табл. f (узел 6) и 2 (узел 7), определены восемь вторых разрядов (Р2) трехразрядных кодов управления расстановкой Н-ÁO-7 Р2.

В табл. 3 (узел 8) и- 4 (узел 9), определены третьи разряды (РЗ) кодов управления расстановкой Н-БО-7 РЗ.Первые разряды кодов управления расстановкой Н-БО-7 Р1, равны константе:

00001111, которая подается на входы константы устройства.

Расстановка элементов правой и левой половин строки информации производится независимо, поэтому формирование кодов управления расстанов- . кой существенно упрощается.

В таблице истинности приняты:;

И-PO-7 — маска, разряды 0-. 7

Н-БО-7 Р23 — коды управления расстановкой байты 0-7 1 разряды 23.

Из таблиц 1-4 видно, что второй и третий разряды кодов управления расстановкой зависят от малого числа переменных (1-3 переменных) и их реализация не вызывает трудностей (фиг. 3).

На сумматорах 101-10g коды управления расстановкой Н-БО-7 Р1-3 суммируются с кодом сдвига СД-Р1-3.

Устройство работает следующим образоие

В исходном состоянии на входы 1 содаются коды информации А-Б0-7 РО-З. (восемь байтов БО-7 по девять разрядов 0-9), иа входы 4 и 5 подаются коды управления: маска расстановки

И-0-7 и код сдвига СД-Pf-3. Сначала в узлах 6-9 формируются коды управ« . ления расстановкой, которые поступают на первые группы входов сумматоров 101-Þ8. На эти же входы сумма.торов подается старший разряд кодов управления расстановкой Н-Б0-7 РО=.

=00001111. Далее сумматоры прибавляап к этим кодам константу сдвига

СД-Р1-3. На выходах сумматоров формируются коды У-Г0-7.Р1-3,которые поступают на управляющие входы комму-. тирующих ячеек 11 -11 . Затем ячей.ки 111-1 1q выполняют требуемую коммутацию и. выдают расставленную ин-, формацию В-БО-7 Р0-8.

Пример. Дан код маскй расстановки: М-РОф70101001t. Код сдвига равен: СД=Р1Ф3=110, т.е. исходный плотный массив расположен в первых четырех байтах (элементах) строки. входной информации.

На выходе узлов 6-9 формируются коды в соответствии с. таблицами 1-4. ,Я-БО-7 Р2 01011100, Н-БО-7 Р3=10011001.

Коды управления расстановкой имеют следующий вид:

Н-БО-7 Р1-3 (Х, 010, Х, 011

Х,Х, 100, 101.).

На выходе узлов 101-10я после суммировайия с константой СД-Р1-3 форми: руются коды . У FO-7 Р1"3 (Х, 000, Х, 001,Х,Х, 010, 011) .

В результате коммутации на выход устройства выдается код

В-БО-7 PO-8 ** А-БХ, О,Х,1,Х,Х, 2,3 Р0-8.

Таким образом произведена расстановка элементов плотного входного массива на позиции, помеченные "еди.ницами" маски расстановки.

Зчаком Х обозначены коды управления и позиции выходного растановлен:ного массива, соответствующие "нулям"

- маски расстановки. Но в предлагаемом устройстве операции над элементами массива входной информации, отмеченными

"нулями" маски для простоты описания не рассматриваются. В действительности под "нулями™ маски также происходит расстановка элементов массива информации, следующего за первым мас17632 сивом, расставляемы..-| по "единицам",,но с изменением исходного порядка следования на обратный.

Аналогично может быть произведе5 на расстановка элементов информации: исходного массива, местоположение которого задано кодом сдвига, на лю-

I. бые позиции, определяемые кодом мас- ки. Устройство позволяет также реализовать кольцевой сдвиг 6es расстанов ки. Для этого на вторые управляющие: входы устройства подается код маски

"Все 17, а на третьи управляющие вхо ды подается код сдвига (влево)

СД-РО-2. Например, для сдвига массива,начинающегося с крайней левой позиции, на три позиции вправо, необходимо подать код маски "Все 1" и код сдвига СД-РО-2 101.

20 Из рассмотренных примеров следует правильность функционирования устройства т.е. возможность выполнения расстановки массива под управлением маски и кода сдвига.

В ряде случаев обработки бопьщих массивов требуется организовать слияние двух и более отдельных массивов в один таким образом, чтобы элементы одного массива были расположе30 ны между элементами другого. Эта задача реааетс» путем расстановки элементов массивов. Использование ,предпагаемого устройства для расста. новки информации в составе многопро

35,QeccopHoO вычислительной системы по зволяет реалнзовагь этот и другие алгоритмй с высокой производительностью

1,117632.,Таблица 1 ввюввююююююююю«

H-Б0-3 Р2

М".Р1-3,0

0

0

О

О

0

0

Таблица..2

Н-Б 4-7 Р2

М-Р4-6

Бб . В7

Б5

0

0

0

0

0

0

0 юввввю юююю

Р1 Р2

° В ююююlo ююю (1 ююввв

БО: Б1, Б2,; Б.3

l ю юю ю юю ю ю ввюююююююююююю

1 0 0

1117632

О

О.

О.0

О

О 0

0

Таблица 4

;Н-Б4-7 Р3

0 0

О

0

О

Таблица 3 аии,ев а а С ю

Н-БО-3 Р3

1 17632

1117632

l 1 17632 Риз.4

Составитель Е. Иванова ,Редактор E. Лушникова Техред М,Гергель Корректор А. Зимокосов

Заказ 722.1/33 .Тираж 698 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ЫТП "Патент", г. Ужгород, ул. Проектная, 4