Устройство для сдвига информации Советский патент 1984 года по МПК G06F7/38 

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

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

1

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

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

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

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

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

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

сдвигающий блок кодов управления, состоящий из нескольких ярусов логических элементов, причем первьй выход f-го логического элемента i -го яруса сдвигакнцего блока управления соединен с входами j и j-2 -го логических элементов G41)-го яруса, второй и третий выходы соединены соответственно с третьим и четвертым входами j -го коммутирукяцего элемента

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

входы первого яруса которого соеди- . йены с вькодамй регистра кодов управ ления . - Устройство позволяет осуществить кольцевой сдвиг всех элементов инфор мации, но не позволяет осуществить расстановку информахщи. Цель изобретения - расширение функциональных возможностей устройства путем реализации расстановки элементов массива информации, Под расстановкой понимается раздвижка плотно расположенных элементов входного массива информации на различное число позиций с сохранением исходног порядка следования под управлением маски и кода сдвига. Маской называется двоичный код, где единицами отмечены те позиции, на которые подлежит расставить элементы входного мас,сйва информации. Величина кода сдвига определяет смещение центра плотH iro входногомассива относительно середины строки информации, где под серединой строки информации понимается граница между третьим и четвертым байтами информации, а под центром плотного массива - граница между байтами, расставляемыми в левой половине и байтами, расставляемыми в правой половине строки. Поставленная цель достигается тем что в устройство для сдвига информации , содержащее коммутирующие ячейки информационные входы которых являются информационными входами устройства, а выходы - выходами устройства, введены восемь сумматоров и четыре узла форми рования кодов расстановки, каждый из которых включает элемент НЕ и группу из четырех мультиплексоров, соответ- ствующие управляющие входы которых объединены, в первом узле формирования кодов расстановки управляющие входы мультиплексоров соединены соответственно с входами первого и второго разрядов кода маски расстановки устройства, информационные входы первого мультиплексора подключены cooT-f ветственно к шине логической 1 уст ройства, через элемент НЕ к входу тре-, тьего разряда кода маски расстановки устройства и к пшне логического О устройства, информационные входы вто рого мультиплексора - к входу третьего разряда кода маски расстановки устройства, к шинам логического О и 1 устройства и через элемент НЕ к входу третьего разряда кода маски расстановки устройства,- информационные входы третьего мультиплексора соединены попарно с шинами логического О и 1 устройства, информационные входы четвертого мультиплексора объединены и соединены с входом третьего разряда кода расгстановки кода маски устройства, управляющие входы мультиплексоров второго узла : формирования кодов расстановки подключены соответственно ic входам четвертого и пятого разрядов кода маски расстановки, а информационные входы первого мультиплексора, соединены попарно с входами логической 1 и логического О устройства, триин- ; формацнонных входа второго, мультиплексора подключены к шине логической 1, а четвертый - к шине логического О .устройства, первый информационный вход третьего мультиплексора соединен с шиной логического О устройства, а три остальных через элемент НЕ - с входом шестого, разряда кода маски ; расстановки устройства, информационные входы четвертого мультиплексора с шиной логического О устройства, с входом шестого разряда кода маски расстановки устройства и шиной логической 1 устройства, управляющие входы мультиплексоров третьего узла формирования кодов расстановки подключены соответственно к входам первого и второго разрядов кода маски расстановки устройства, информационные входы первого и второго мультиплексоров попарно объединены и подключены к входу третьего разряда кода маски расстановки устройства . и к этому же входу через элемент НЕ, информационные входы третьего мультиплексора соединены через элемент НЕ с входом третьего раз.ряда кода маски расстановки устройства, йодключенны i также к объединенным информационнь1М входам Четвертого мультиплексора, управляющие входы мультиплексоров четвертого узла формирования кодов расстановки подключены соответстбенно к входам четвертого и пятого раз-. рядов кода мабки расставовки устройства, информационные входы первого ; мультиплексора попарно объединены И подключены соответственно шинам логической 1 и О устройства. ин|)ормацион«ые входы второго мультнплексора попарно объединены и подключены соотвеЧственно к шинам логического О и t устройства, первый 511 информационный вход третьего мультиплексора соединен через элемент НЕ с входом шестого разряда кода маски расстановки устройства, который соединен с остальными информационными :входами третьего мультиплексора, информационные входы четвертого мультиплексора попарно объединены и соединены соответственно с выходом шес;Того разряда кода маски расстановки устройства и с этим же входом через элемент НЕ, входы константы устройст ва соединены с входами первого разря да первой группы входов сумматора, входы второго разряда первой группы входов которого подкгаочены к выходам мультиплексоров первого и третьего узлов формирования кодов расстановки а входы третьего разряда первой груп пы входов сумматора - к выяодам. муЛь-20 типлексоров второго и четвертого узлов формирования кодов расстановки, входы второй группы всех су№1аторов , соединены с входами кода сдвига устройства, каждая коммутирующая ячейка содержит восемь мультиплексрров, соответствующие информационные входы к торых объединены, а управляющее подключены к выходам соответствующего сумматора. На фйр. 1 представлена блок-схема устройства для сдвига информации (во семь байтов)} на фиг. 2 - функционал , ная схема коммутирующей ячейки на восем входов и восемь выходов (типа 8 и 8 ) }на фиг. 3 - пример реализации узлов фор мирования кодов расстановки; на фиг. 4 - .схема сумматора. Устройство содержит информационные входы 1, выходы 2, входы 3 константы, входы 4 кода маски расстановки, входы 5 кода сдвига, узлы 6-9 формирования кодов расстановки, сумматоры 10, коммутирзгемцие ячейки 11. Каждая коммутирующая ячейка содержит восемь мультиплексоров 12. Кажды узел формирования кодов расстановки ;совержит четыре мультиплексора 13-16 элемент НЕ 17. Устройство работает следующим образом; . Коды расстановки формируются в дв этапа: сначала формируются.коды шин :;управления расстановкой от середины |Строки влево и вправо, а затем эти коды кЬррект1фуются путем сложения :С кодс1М сдвига и тем самым учитывается смещение исходного плотного масК . сива относительно середины строки информации. Узлы 6-9 формируют коды управления расстановкой. Эти узлы могут быть реализованы известными методами логического синтеза в соответствии с таблицами интенсивности,1-4. В табл. 1 (узел 6) и 2 (узел 7), определены восемь вторых разрядов (Р2) трехразрядных кодов управления расстановкой Н-Би-7 Р2. В табл. 3 (узел 8) и-4 (узел 9) определены третьи разряды (РЗ) кодов управления расстановкой Н-БО-7 РЗ.Первые разряды кодов управления расстановт кой НН50-7 Р1. равны константе; , 00001 ill, которая подается на входы константы устройства. Расстановка элементов правой и левой половин строки информащш производится независимо, поэтому формирование кодов управления расстановкой существенно упрощается. В таблице истинности приняты;: М-РО-7 - маска, разряды От7 Н-БО-7 Р23 - коды управления расстановкой байты Q-7j разряды 23. Из таблиц 1-4 видно, что второй и третий разряды кодов управления расстановкой зависят от малого-числа переменных (1-3 переменных) и их реализация не вызывает трудностей (фиг. 3). На сумматорах коды управления расстановкой Н-БО-7 Р1-3 суммируются с кодом сдвига СЛ-Р1-3. Устройство работает следующим образом. В исходном состоянии на входы 1 подаются коды информации А-БО-7 РО-3 (восемь байтов БО-7 по девять разрядов 0-9), на входы 4 и 5 подаются коды управления: маска расстановки М-О-7 и код сдвига СД-Р1-3. Сначала в узлах 6-9 формируются коды управления расстановкой, которые поступают на первые группы входов сумматоров 0|-10g. На эти же входы сумматоров подается старший разряд кодов управления расстановкой Н-БО-7 Р0 00001 tit. Далее сумматоры прйбавля ют к этим кодам константу сдвига , СД-Р1-3. На выходах сумматоров формируются коды У-ГО-7Р1-3,которые постзшают на управляющие входы коммутирувщих ячеек ГЦ-11,. Затем ячейки 11|-11 выполняют требуемую коммутацию и вьщают расставленную инг юрмацию В-БО-7 РО-8.; 7 1 Пример, Дан код маски расста новки: M-POfJ pOlO 1001 t. Код сдвига равен: , т.е. исходный плотный массив расположен в первых четырех байтах (элементах) строки входной информации. На выходе узлов 6-9 формируются коды в соответствии с. таблицами 1-4. И-БО-7 Р2 01011100, Н-БО-7 Р3 10011001. Коды управления расстановкой имеют следующий вид: Н-БО-7 Р1-3 (X, 010, X, 011, Х,Х, 100, 101), На выходе узлов после сум мирования с константой СД-Р1-3 форми руются коды У ГО-7 Р1-3 « (X, 000, X, 001,Х,Х 010, 011). В результате коммутахщи на выход устройства ввдается код В-БО-7 РО-8 А-БХ, 0,Х,1,Х,Х, 2,3 РО-8. Таким образом произведена расстановка элементов плотного входного массива на позиции, помеченные еди.ницами маски расстановки. знаком X обозначены коды управления и позиции выходного растановленного массива, соответствующие нулям маски расстановки. Но в предлагаемом устройстве операций над элементами мас сива входной информации, отмеченными нулями маски для простоты описания не рассматриваются. В действительности под нулями маски также происходит расстановка элементов массива информации, следующего за первым мае сивом, расставляемы- по единицам, .но с изменением исходного порядка следования на обратный. Аналогично может быть произведена расстановка элементов информации ; исходного массива, местоположение которого задано кодом сдвига на любые позиции, определяемые кодом маски. Устройство позволяет также реализовать кольцевой сдвиг без расстановКИ. Для этого на вторые управляющие входы устройства подается код маски Все IV, а на третьи управляющие вхоН ды подается код сдвига (влево) I СД-РО-2. Например, для сдвига массива начинающегося с крайней левой позиций, на три позиции вправо, необходимо подать код маски Все 1 и код сдвига СД-РО-2 101. Из рассмотренных примеров следует правильность функционирования устройства т.е. возможность выполнения расстановки массива под управлением маски и кода сдвига. В ряде случаев обработки больших массивов требуется организовать слияние двух и более отдельных массивов в один таким образом, чтобы элементы одного массива были расположены между элементами другого. Эта задача ревается путем расстановки элемен4 ов массивов. Испо|1ьзование предлагаемого устройства для расста новки информации в составе многопро цессорной вычислительной системы зволяет реализовать этот н другие алгорит а1 с вьюокой производительностью. M-Pt-3 Т P2Г РЗ

М-Р4-6

рб

о /

1 о 1 о t о 1 1,117632

Та 6 ли ц а 2

4-7 Р2

:o:ii:

Б5

Б6 О

Б7

О

1

О 1 О

.1 о

О

О

О

1

1 1 о о

1 о

О

1

1 1.

1

1 10 ,Т а б лица 1 i Н-БО-3 Р2 f В1; I Б2 т БЗ

A-eff- 7ffff e

Риг.2