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

 

О П И" С А Н И E

ИЗОБРЕТЕНИЯ

Союз Советских

Социалистических

Республик

<11798820

К АВТОРСКОМУ СВИ ЕТЕЛЬСТВУ (61) Дополнительное к авт. сеид-ву (22) Заявлено 29.11.78 (21) 2716350/18-24

<Я)М. К . с присоединением заявки М (23) Приоритет

G 06 F 7/38

Государственный комитет

СССР по делам изобретений и открытн й

Опубликовано 230131.Бюллетень Н9 3

Дата опубликования описания 2 30181 (53) УДК 681. 3 (088.8) (72) Авторы изобретения

В.Ф. Гусев, В.Н. Иванов, В.П. Михайлов, М.3. Шагивалеев и A.Ó. Ярмухаметов (71) За яв итель (54) УСТРОЙСТВО ДЛЯ СДВИГА ИНФОРМАЦИИ

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

В настоящее время конструкторами

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

:практически во все алгоритмы реализации внутренних языков, причем в состав алгоритмов, как правило, включаются несколько типов операций сдвига, например, выравнивание порядков, 15 выравнивание мантисс операндов, нормализация результатов в плавающей запятой. Поэтому важно выполнять .сдвиг как можно быстрее и с наименьшими аппаратурными затратами. В связи с 20 переходом элементной базы ЭВМ на БИС возникает также проблема создания регулярной схемы, которая хорошо разбивается на законченные модули приемлемой величины как по количеству элементов в модуле, так и по количеству выводов (внешних контактов).

Известно устройство для сдвига информации, содержащее несколько схемных подуровней, соединенных кас кадно. Каждый подуровень выполняет сдвиг информации на заранее заданную величину и включается в работу в зависимости от поданного кода параметра сдвига (1). ,Недостатком данного устройства является большая задержка информации при прохождении всех каскадов схем сдвига °

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

Переключательные элементы управляют передачей информации между входными проводниками как при сдвигах вправо, так и влево. Это устройство обладает более высоким быстродействием (2).

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

798820

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

Изв стное устройство имеет несомненные преимущества, так как обладает высоким быстродействием за счет малой глубины логики и хорошо компануется в большой интегральной схе- 2О ме (3) .

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

Дель изобретения — сокращение количества оборудования устройства.

Поставленная цель достигается тем, 30 что устройство для сдвига информации, содержащее матрицу элементов И, шины управления, подключенные к соответствующим элементам И диагоналей матри-, цы, входные и выходные информациойные шины, причем выходы элементов И каждого столбца матрицы подключены к соответствующему элементу ИЛИ, содержит входной коммутатор, подключенный информационными входами к входным информационным шинам, а выходами к элементам И соответствующих строк матрицы, и выходной коммутатор, информационные входы котороro соединены с элементами ИЛИ соответствующих столбцов матрицы, выходы соединены с выходными информационными шинами, а управляющий вход подключен к управляющему входу входного коммутатора и к входу задания напраьления сдвига устройства.

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

60 мутатора через элемент НЕ, а второй его вход подключен к (n-1-1)-му информационному входу коммутатора, где 1 = 0,1,2,...,...,n-1 — разряды обрабатываемой информации.

Эффект достигается путем перекомпановки входной и выходной информации на соответствующих коммутаторах °

На фиг.l изображена блок-схема устройства для сдвига информации; на фиг.2 — матрица элементов для сдвига информации; на фиг.З вЂ” диаграмма, поясняющая сдвиг информации; на фиг.4 — столбец матрицы элементов

И для сдвига с подключением их выходов ко входу соответствующих элементов ИЛИ; на фиг.5 - входной коммутатор; на фиг.б — выходной коммутатор; на фиг.7 — диаграмма сдвига одного байта информации на три разряда вправо. устройство для сдвига информации (фиг.l) содержит входной коммутатор

1, информационные входы которого подключены ко входным информационным шинам 2, выходы 3 коммутатора 1 соединены с матрицей 4 элементов И, к которой подключены также шины уп— равления 5. Выходной б коммутатор своими информационными входами 7 подключен к выходам матрицы 4, а выходами — к выходным информационным шинам 8. Управляющие входы 9 и 10 соответственно входного 1 и выходного б коммутаторов соединены с управляющим входом 11 задания направления сдвига устройства.

Матрица элементов 4 И (фиг. 2) содержит логические элементы 12 И. Го-. ризонтальный ряд элементов 12 И образует строку 13 матрицы 4, а вертикальный ряд элементов 12 И.образует столбец 14 матрицы 4. Диагонали 15 матрицы 4 образованы рядом элементов

12 И, параллельными главной диагонали матрицы 4. Количество строк 13, столбцов 14 и диагоналей 15 равно количеству двоичных разрядов в сдвигаемой информации и обозначено через и. Каждой из строк 13, диагоналей 15 и каждому столбцу 14 присвоен позиционный номер от 0 до и-1. Причем верхняя строка 13 (на фиг.2) имеет номер О, номера следующих 13 строк сверху вниз соответствуют натуральному ряду чисел 1,2,3,...1.,1+1 и нижняя строка 13 имеет номер п-l.

Крайний левый столбец 14 (фиг.2) имеет номер О, номера следующих столбцов слева направо соответствуют натуральному ряду чисел 1,2,3,..., j„j+l„... . Крайний правый столбец имеет номер и-1. Крайняя правая диагональ 15 (наиболее длинная) имеет номер О, номера следующих диагона лей справа налево соответствуют натуральному ряду чисел 1,2,3,..., К, К+1,.. ° . Крайняя левая диагональ (которая выражается в один элемент) 798820

S0

dO

65 имеет номер п-1. Таким образом, количество элементов 12 И матрицы 4 равно -" ††"- . Входные шины 16 матрицы 4 подключены ко всем элементам 12

И соответствующих строк 13, а выход в ные шины 17 матрицы 4 подключены ко сем элементам 12 И соответствующИх столбцов 14. Входные шины.16 матрицы

4 подключены к выходу 3 (фиг.l) вход ного коммутатора 1, а выходные шины

17 2) со входом 7 (фиг.l) выходного коммутатора б. Шины управления 5 (фиг.2) соединяются со всеми элементами 12 И соответствующих диагоналей 15 матрицы 4.

На фиг.4 показан конкретный пример выполнения одного столбца 14 матрицы 4. K одним входам 18 элементов

12 И годключены í-.oäíûå шины 16 матрицы 4. К другим входам 19 подключены соответствующие им шины управления 5. Выходы 20 элементов 12 И подключаются к выходной шине 17 ° Выходная шина 17 образована с помощью проводного элемента 21 ИЛИ, как это показано на фиг.4. Выход 22 элемента

21 ИЛИ подключен к соответствующему информационному входу 7 (фиг.l) вы ходного коммутатора 6 °

Входной коммутатор 1 состоит из групп 23-26 элементов. В каждую группу 23-26 входят логические элементы

27 и 28 И, а также логический элемент 29 ИЛИ. Число групп 23-26 соответствует количеству двоичных разрядов в сдвигаемой информации и обозначено через и. Каждой группе 23-26 присвоен номер от 0 до и-1. Так на фиг.5 группе 23 присвоен номер О, группе 24 присвоен номер i группе

25 присвоен номер и-1-1 и, наконец, группе 26 присвоен номер и-1. Входные шины 2, количество которых равно

Количеству разрядов сдвигаемой информации и и которые пронумерованы с 0 по и-1 в соответствии с номерами разрядов входной информации, подключены

>к входам 30 элементов 27 И групп

23-26, имеющих но лер i, соответствующий номеру шины 2 и входу 31 элементов 28 групп 23-26, номера которых определены как n-i-l где 1 - номер шины 2.

На фиг.5 шина 2 с номером О подключена к входу 30 элемента 27 И группы 23 и ко входу 31 элемента 28

И группы 25. Шина 2 с номером п-1 подключена ко входу 30 элемента 27

И группы 26 и ко входу 31 элемекта

28 И группы 23. Шина с номером i подключена ко входу 30 элемента 27 И группы 24, и леющей также номер 1, и ко входу 31 элемента 28 И группы

25, имеющей номер n-i-1. Шина 2, имеющая номер и-1-1 подключена ко входу 30 элемента 27 И группы 25 и ко входу 31 элемента 28 И группы 24.

Другие входы 32 элементов 27 И объединены и подключены к управляющему входу 9 входного коммутатора 1.

Другие входы 33 элементов 28 И также объединены и подключены к управляющему входу 9 входного коммутатора 1 через элемент 34 НЕ.

Выходы элементов 28 и 27 И каждой )группы 23-26 подключены ко входам элемента 29 ИЛИ той же группы.

Выходы элементов 29 ИЛИ являются соответствующими выходами 3 входного коммутатора 1, причем выход элемента 29 ИЛИ каждой группы 23-26 подключен ко входной шине 16 (фиг.2), соединенной со строкой 13 матрицы 4 (соединение не показано), имеющей тот же номер, что и связанная с ней

13 группа 23-26 (фиг.5) входного коммутатора 1.

На фиг.б показан пример выполнения выходного коммутатора 6. Он собран по той же схеме, что и входной

З1 коммутатор 1 и содержит группы 35-38 элементов, в каждую ив которых объединены элементы 39 и 40 И и элемент

41 ИЛИ.

Входы 42 элементов 39 И и входы

2Б 43.элементов 40 И объединены по тому же закону,,что и во входном ком-. мутаторе 1 и подключены к информационным входам 7 выходного коммутатора б. Другие входы 44 элементов

39 39 И объединены и подключены к управляющему входу 10 выходного коммутатора 6. Другие входы 45 элементов

40 И также объединены и подключены к управляющему входу 10 выходного кому мутатора 6 через элемент 46 НЕ. Столбцы 14 матрицы 4 через соответствующие выходные шины 17 соединены со входами 7 выходного коммутатора 6, связанные с группами 35-38, имеющими тот же номер, что и соответствующие столбцы 14 матрицы 4 (соединение на фиг.б не показано). Выходы элементов 41 ИЛИ являются выходами выходного коммутатора б и подключены к выходным шинам 8, имеющим тот

45 же номер, что и соответствующая группа 35-38 соответствующей нумерации разрядов выходной информации.

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

Сдвигаемая информация подается на устройство по входным шинам 2 (фиг.l), проходит через коммутатор

1 и по выходам 3 входного коммутатора 1 поступает на матрицу элементов

4 И. Собственно сдвиг информации выполняется матрицей элементов 4 И.

Для этого по шине управления 5 на матрицу элементов 4 И подаются управляющие сигналы, задающие величину сдвига. Сдвинутая информация поступает на информационные входы 7 выходного коммутатора С и через его выходы 8 — на выход устройства. Направление сдвига задается по входу 11 задания направления сдвига устройства.

798820

Этот управляющий сигнал поступает одновременно на управляющие входы 9 и

10 входного 1 и выходного 6 коммутаторов соответственно.

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

В основу устройства положен принцип зеркальности операции сдвига.

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

Поскольку наиболее емкой по затратам оборудования частью устройства сдвига является матрица элементов 4

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

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

Сдвиг информации выполняется косоугольной матрицей элементов 4 И (иг.2) . Сдвигаемая информация поступает по входным шинам 16 матрицы на все строки 13 матрицы, таким образом, что на каждый логический элемент 12 И одной строки 13 поступает один разряд информации. На шины управления 5 подается управляющий сигнал, задающий величину сдвига, причем на ту диагональ 15 матрицы 4, номер которой соответствует величине сдвига подается активизирующий сигнал (например, положительный), а на все прочие диагонали 15 — запрещающий (например, нулевой) . Включаются все элементы 12 И соответствующей диагонали 15, подавая информацию на выходные шины 17 матрицы 4., Процесс сдвига поясняется диаграммой (фиг. 3) . Разряды восьмираэрядного слова входной информации изображены слева. Жирной линией выделена диагональ 3. В верхней части диаграммы изображена информация после сдвига. Как видно из диаграммы, был выполнен сдвиг на 3 позиции влево, т.е. в соответствии с номером выбранной диагонали. Таким образом, матрица элементов 4 И в конкретном примере может выполнять сдвиг только влево на количество разрядов от 0 до п-1.

ЗО

Ю

S0

ЬО

В одном столбце 14 матрицы 4 (фиг.4) одновременно может быть включен только один логический элемент

12 И, так как активная диагональ 15 (фиг.2) пересекает каждый столбец только один. раз, а значит, только на один из входов 19 (фиг.4) всех элементов 12 И одного столбца 14 будет подан сигнал разрешения. На выход 22 логического элемента 23 ИЛИ поступает тот разряд информации, который подключен ко нторому входу 18 активного элемента 12 И.

Перед поступлением на матрицу элементов 4 И (фиг.1) информация проходит входной коммутатор 1 (фиг.5).

Ha его упранляющий вход 9 подается сигнал направления сдвига. В конкретном примере для сдвига влево подается положительный сигнал, который открывает по входам 32 элементы 27 И в каждой группе 23, тем самым позволяя передачу информации с входных шин 2 на выходы 3 входного коммутатора 1 разряд в разряд, т.е. транслируя их без всякого преобразования.

Тот,же управляющий сигнал с управляющего входа 9 через элемент 34 HE закрывает элементы 28 И по их входам 33.

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

36 И и.чеоез элемент 46 НЕ запирает по входам 45 элементы 40 И.Информация с информационных входов 7 выходного коммутатора б без изменений проходит на его выходы 8.

Нри выполнении устройством операции сднига в направлении, которое не может обеспечить косоугольная матрица элементов 4 И производится преобразование ее на входном 1 и выходном 6 коммутатсрах.

При этом на управляющие входы 9 и 10 входного 1 и выходного б коммутаторов соответственно поступает в конкретном примере сигнал отрицательной полярности, который препятствует прямому прохождению информации, закрывая по входам 32 (фиг.5) элементы 27 И и по входам 44 (фиг.б) элементы 39 И. Инвертированный на элементе 34 HE (фиг.5) и; 46 (фиг.б) 798820

10 управляющий сигнал открывает по входам 33 (фиг.5) элементы 28 И и по входам 43 (фиг. 6) элементы 40 И, разрешая прохождение информации на выходы 3 и 8 коммутаторов 1 и 6 соответственно по зеркальному закону.

Выполнение сдвига вправо поясняется диаграммой (фиг.7). На фиг.7а показана исходная информация, которую требуется сдвинуть вправо на 3 разряда. На фиг.7б показана та же инфор.— мация, поступающая на матрицу 4 после преобразования, показанного косыми стрелками между фиг.7а и 7б. На фиг.7в показана информация после ее сдвига. влево на матрице 4. На фид.7г показана информация после выходного преобразования, т.е. итоговая информация.. Как видно из диаграммы, произошел сдвиг вправо на три позиции, т.е. разряд а, переместился в четвертую клетку разрядной сетки, а, - 20 в пятую и т.д.

Для выполнения устройства средствами микроэлектроники, а именно в виде большой интегральной схемы (БИС) надо выбрать компромисс между быстродействием устройства и его рассеиваемой мощностью. При применении

МОП-технологии ограничения на количество элементов невелико, однако скорости работы устройства неудовлетворительные для ЭВМ средней и большой мощности. Выполнение данного устройства на биполярной технологии имеет существенные ограничения по количеству вентилей на кристалле и по допустимой рассеиваемой мощности 35 корпуса БИС.

Представленная здесь структура позволяет выполнять БИС сдвига на быстрых элементах, так как вследствие сокращения количества логичес- 4р ких элементов матрицы сдвига, общее количество элементов БИС укладывается в предельно допустимые технологические допуски.

Формула изобретения 45

1. Устройство для сдвига информации, содержащее матрицу элементов И, шины управления; подключенные к соответствующим элементам И диагоналей матрицы, входные и выходные информационные шины, причем выходы элементов И каждого столбца матрицы подключены к соответствующему элементу

ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью сокращения количества оборудования, оно содержит входной коммутатор, подключенный информационными входами к входным информационным шинам, а выходами к элементам И соответствующих строк матрицы, и выходной коммутатор, информационные входы которого соединены с элементами

ИЛИ соответствующих столбцов матрицы, выходы соединены с выходными ин- формационными шинами, а управляющий вход подключен к управляющему входу входного коммутатора и к входу задания направления сдвига устройства.

2; Устройство по п.1, о т л и ч а ю щ е.е с я темо что входной и выходной коммугаторы содержат группы элементов по числу разрядов обраЬатываемой информации в каждом, сос тоящие из двух элементов И, выходы которых подключены ко входам элемента ИЛИ, выходы элементов ИЛИ каждой группы соединены с соответствующими выходами коммутаторов, первый вход первого элемента И каждой группы подключен к управляющему входу коммутатора, а второй подключен к i-му информационному входу коммутатора, первый вход второго элемента И той же группы подключен к управляющему входу коммутатора через элемент НЕ, а второй его вход подключен к (n-1-1)-му информационному входу коммутатора, где i=0,1,2,...,...,n-1 разряды обрабатываемой информации.

Источники информации, принятые во внимание при экспертизе

1. Патент CUA 9 3914744, кл. 340-172.5, 1975.

2. Патент Франции 9 2242727, кл. G 06 Р 7/00, 1975.

3. Патент CLlA 9 3961750, кл. 235-164, 1976 (прототип) .

Фиа 7

Составитель В. Березкин

Редактор Н. Рогулич Техред A.Бабииец Корректор О. Ковинская е

Заказ 10048/66 Тираж 756 Подписное

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

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

Ю

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