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

Изобретение относится к вычислительной технике, в частности, к устройствам обработки информации путем сдви ga и может быть использовано в элек-:тронных вычислительных машинах. В настоящее время конструкторами ЭВМ все большее внимание обращается Она быстрое выполнение операций сдвига. Это связано с тем, что сдвиг ;Входит в качестве составного элемента практически во все алгоритмы реализации внутренних языков, причем в состав алгоритмов, как правило, включаются несколько типов операций сдвига, например, выравнивание порядков, выравнивание мантисс операндов, норма лизация результатов в плавгиоЕцей запятой. Поэтому важно выполнять .сдвиг как можно быстрее и с наименьшими аппаратурными затратами. В связи с переходом элементной базы ЭВМ на БИС возникает также проблема создания регулярной схемы, которая хорошо разбивается на законченные модули приемлемой величины как по количеству элементов в модуле, так и по количест ву выводов (внешних контактов). Известно устройство для сдвига информации, содержащее несколько схемных подуровней, соединенных касч кадно. Каждый подуровень выполняет сдвиг информации на заранее заданную величину и включается в работу в зависимости от поданного кода параметра сдвига 1. Недостатком данного устройства является большая задержка информации при прохождении всех каскадов схем сдвига. Известно также устройство сдвига информации, содержащее переключательные элементы, образованные в прямоугольную матрицу, которое позволяет выполнить сдвиг за один проход данных путем одновременного возбуждения проводников, управляющих сдвигом. Переключательные элементы управляют передачей информации между входными проводниками как при сдвигах вправо, так и влево. Это устройство, обладает более высоким быстродействием 2. Однако существенным недостатком известного устройства является то, что оно содержит большое количество переключательных элементов, пропорциональное квадрату разрядности сдвигаемой информации. Указанное обстоятельство затрудняет выполнение данного устройства средствами микроэлектроники.

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

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

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

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

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

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

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

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

На фиг.1 из рбражена блок-схема устройства для сдвига информации; на фиг.2 - матрица элементов для сдвига информации; на фиг.З - диаграмма, поясняющая сдвиг информации; на фиг.4 - столбец матрицы элементов И для сдвига с подключением их выходов ко входу соответствующих элементов ИЛИ; на фиг.5 - входной коммутатор; на фиг.6 - выходной коммутатор; на фиг.7 - диаграг/1ма сдвига одного байта информации на три разряда вправо.

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

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

имеет номер п-1. Таким образом, количество элементов 12 И матрицы 4 равно , Входные шины 16 матрицы 4 подключены ко всем элементам 12 И соответствукадих строк 13, а выход ые шины 17 матрицы 4 подключены ко всем элементам 12 И соответствующих столбцов 14. Входные шины 16 матрицы 4 подключены к выходу 3 (фиг.1) входного коммутатора 1, а выходные шины 17 (фиг.2) соединяются со входом 7 (фиг.1) выходного коммутатора 6. Шины управления 5 (фиг.2) соединяются со всеми элементами 12 И соответствующих диагоналей 15 матрицы 4.

На фиг.4 показан конкретный пример выполнения одного столбца 14 матрицы 4. К одним входам 18 элементов 12 И подключены входные шины 16 матрицы 4. К другим входам 19 подключены соответствующие им шины управления 5. Выходы 20 элементов 12 И подключаются к выходной шине 17. Выходная шина 17 образована с помощью проводного элемента 21 ИЛИ, как это показано на фиг.4. Выход 22 элемента 21 ИЛИ подключен к соответствующему информационному входу 7 (фиг.1) выходного коммутатора 6.

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

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

25 присвоен номер n-i-1 и, наконец, группе 26 присвоен номер п-1. Входные шины 2, количество которых равно количеству разрядов сдвигаемой информации п и которые пронумерованы с О по п-1 в соответствии с номерами разрядов входной информации, подключены ж входам 30 элементов 27 И групп 23-26, имеющих номер 1, соответствующий номеру шины 2 и входу 31 эл хентов 28 групп 23-26, номера которых определены как n-i-1, где i - номер шины 2.

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

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

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

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

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

Выходы элементов 29 ИЛИ являются Ьоответствующими выходами 3 входного кок 4утатора 1, причем выход элемента 29 ИЛИ каждой группы 23-26

подключен ко входной шине 16 (фиг.2), соединенной со строкой 13 матрицы 4 (соединение не показано), имеющей тот же номер, что к связанная с ней

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

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

коммутатор 1 и содержит группы элементов, в каждую ив которых объединены элементы 39 и 40 И и элемент 41 ИЛИ. I

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

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

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

же номер, что и соответствующая

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

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

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

сдвига. Сдвинутая информация поступает на информационные входы 7 выходного коммутатора С и через его выходы 8 - на выход устройства. Направление сдвига задается по входу 11 заДания направления сдвига устройства.

Этот управляющий сигнал поступает одновременно на управляющие входы 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 позиции влево, т.е. в соответствии с номером . выбранной диагонали. Таким образом, матрица элементов 4 И в конкретном примере может выполнять сдвиг только рлево на количество разрядов от О до п-1.

0 в одном столбце 14 матрицы 4

(фиг.4) одновременно может быть включен только один логический элемент 12 И, так как активная диагональ 15 (фиг.2) пересекает каждый столбец

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

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

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

5 На его управляющий вход 9 подается сигнал направления сдвига. В конкретном примере для сдвига влево подается положительный сигнал,который открывает по входам 32 элементы 27 И

0 в каждой группе 23, тем самым позволяя передачу информации с входных шин 2 на выходы 3 входного коммутатора 1 разряд в разряд, т.е. транслируя их без всякого преобразования.

5 Тот же управляющий сигнал с управляющего входа 9 через элемент 34 НЕ закрывает элементы 28 И по их входам 33. Информация, сдвигаемая на матрице элементов 4 И влево, как это было показано, и через выходной коммутатор б (фиг.б) поступает на выход устройства. Выходной коммутатор б работает аналогично входному коммутатору 1, т.е. управляющий сигнал, поступающий на его управляющий вход 10

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

0 проходит на его выходы 8.

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

При этом на управляющие входы 9 и 10 входного 1 и выходного 6 коммутаторов соответственно поступает в конкретном примере сигнал отрицательной полярности, который препятствует прякюму прохождению информации, закрывая по входам 32 (фиГоБ) элементы 27 И и по входгш 44 (фиг.6) элементы 39 И. Инвертированный на

5 элементе 34 НЕ (фиг.5) и,-46 (фиг.6)

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

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

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

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

Формула изобретения 1. Устройство для сдвига информации, содержащее матрицу элементовИ

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

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

5 которых подключены ко входам Злемента ИЛИ, выходы элементов ИЛИ каждой группы соединены с соответствующими выходами коммутаторов, первый вход первого элемента И каждой группы

0 подключен к управляющему входу коммутатора, а второй подключён к i-му информационному входу коммутатора, первый вход второго элемента И той жа группы подключен к управляющему

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

0 Источники информации,

принятые во внимание при экспертизе

1.Патент США 3914744, кл. 340-172.5, 1975.

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

3.Патент США 3961750, КЛ. 235-164, 1976 (прототип).

11

-1

N

фм.1

П

а

j J

3

4

L

б

5 №

/t-l-/

Фиг,5 .

7ff

Ф ф

Теряются

7г