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

ОПИСАНИЕ ИЗОБРЕТЕНИЯ Союз Советских Социалистических Республик(22) Заявлено 29.11.78 (21) 2716350/18-24 (51)М. КЛ. с присоединением заявки йо(23) Приоритет 6 06 Г 7/38 Государственный комитет СССР яо дедам изобретений и открытий(54) УСТРОЙСТВО ДЛЯ СДВИГА ИНФОРМАЦИИ 30 Изобретение относится к вычислительной технике, в частности, к устройствам обработки информации путем сдвига и может быть использовано в элек-. тронных вычислительных машинах.В настоящее время конструкторами ЭВМ все большее внимание обращается она быстрое выполнение операций сдвига. Это связано с тем, что сдвиг ,входит в качестве составного элемента практически во все алгоритмы реализации внутренних языков, причем в состав алгоритмов, как правило, включаются несколько типов операций сдвига, например, выравнивание порядков, 15 выравнивание мантисс операндов, нормализация результатов в плавающей запятой. Поэтому важно выполнять .сдвиг как можно быстрее и с наименьшими аппаратурными затратамиВ связи с 20 переходом элементной базы ЭВМ на БИС возникает также проблема создания регулярной схемы, которая хорошо разбивается на законченные модули приемлемой величины как по количеству 25 элементов в модуле, так и по количеству выводов (внешних контактов).Известно устройство для сдвига информации, содержащее несколько схемных подуровней, соединенных кас кадно. Каждый подуровень выполняет сдвиг информации на заранее заданную величину и включается в работу в зависимости от поданного кода параметра сдвига 1.,Недостатком данного устройства является большая задержка информации при прохождении всех каскадов схем сдвигаИзвестно также устройство сдвига информации, содержащее переключательные элементы, образованные в прямоугольную матрицу, которое позволяет выполнить сдвиг за один проход данных путем одновременного возбуждения проводников, управляющих сдвигом. Переключательные элементы управляют передачей информации между входными проводниками как при сдвигах вправо, так и влево. Это устройство, обладает более высоким быстродействием 2).Однако существенным недостатком известного устройства является то, что оно содержит большое количество переключательных элементов, пропорциональное квадрату разрядности сдвигаемой информации. Указанное обстоятельство затрудняет выполнение данного устройства средствами микроэлектроники.Березкин Корректор О. Ковинская Редак ак илиал ППП Патентф, г.ужгород, ул.Проектная, 4 юеВ ВШ0048/бб Тираж 756ВНИИПИ Государственного .по делам изобретений113035, Москва, Ж, Раушс Подписиомитета СССРоткрытийая наб., д.4/5го соединены с элементами ИЛИ соответствующих столбцов матрицы, выходы соединены с выходными информационными шинами, а управляющий входподключен к управляющему входу вход"ного коммутатора и к входу задания напраьления сдвига устройства.Кроме того поставленная цель достигается и тем, что выходной и вход 4 рй коммутаторы содержат группы элементов по числу разрядов обрабатываемой информации н каждом, состоящиеиз двух элементов И, выходы которыхподключены ко входам элемента ИЛИ,выходы элементов ИЛИ каждой группысоединены с соответствующими выходами коммутаторон, первый вход первого элемента И каждой группы подключен к управляющему входу коммутатора, а второй подключен к 1-му информационному входу коммутатора, первый вход второго элемента И той же группы подключен к управляющему входу ком 455560 Наиболее близким решением к предлагаемому является устройство для сдвига информации, содержащее группу логических элементов, образованных в матрицу, шины управления, подключенные к соотнетствующим элементам диагонали матрицы, входные и выходные информационные шины, а также дополнительную матрицу с шинами упранления и элементами ИЛИ для объединения результатов сдвига с выходов той или другой матрицы, Каждая из матрицкосоугольная и предназначена для сдвига либо вправо, либо влево и включается в работу в зависимости от поданного управляющего сигнала направления сдвига.15Изв.стное устройство имеет несомненные преимущества, так как обладает высоким быстродействием за счет малой глубины логики и хорошо компануется в большой интегральной схе ме (3) .Однако недостатком этого устройства является значительное количество логических вентилей, в частности, наличие двух матриц сдвига, из кото- . 25 рых при работе схемы одновременно используется только одна.Дель изобретения - сокращение количества оборудования устройства.Поставленная цель достигается тем, 30 что устройство для сдвига информации, содержащее матрицу элементов И, шиныупранления, подключенные к соответствующим элементам И диагоналей матри-,цы, входные и выходные информациойные шины, причем выходы элементов И каждого столбца матрицы подключены к соответствующему элементу ИЛИ, содержит входной коммутатор, подключенный информационными входами к входным информационным шинам, а выходами к элементам И соответствую" щих строк матрицы, и выходной коммутатор, информационные входы которомутатора через элемент НЕ, а второй его вход подключен к (и-1)-му информационному входу коммутатора, где 1 = 0,1,2п- разряды обрабатываемой информации.Эффект достигается путем перекомпановки входной и выходной инФормациина соответствующих коммутаторахНа фиг.1 изображена блок-схема устройства для сднига информации;на фиг.2 - матрица элементов для сдвига информации; на фиг.З - диаграмма, поясняющая сдвиг информации; на фиг.4 - столбец матрицы элементов И для сдвига с подключением их выходон ко входу соответствующих элементов ИЛИ; на фиг.5 - входной коммутатор; на фиг.б - выходной коммутатор; на фиг.7 - диаграмма сдвига одногобайта информации на три разряда вправо. устройство для сдвига информации(фиг.1) содержит входной коммутатор 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 до и. Причем верхняя строка 13 (на фиг.2) имеет номер О, номера следующих 13 строк сверху вниз соответствуют натуральному ряду чисел 1,2,3,1,1+1 и нижняя строка 13 имеет номер п. Крайний левый столбец 14 (фиг.2) имеет номер 10, номера следующих столбцов слева направо соответствуют натуральному ряду чисел 1,2,3 3,3+1, . Крайний правый столбец имеет номер и. Крайняя правая диагональ 15 (наиболее длинная) имеет номер О, номера следующих диагона лей спрана налево соответствуют натуральному ряду чисел 1,2,3, К К+1,. Крайняя левая диагональ (которая выражается в один элемент)0 55 40 65 имеет номер п, Таким образом, количеств элементов 12 И матрицы 4 равно вв " . Входные шины 16 матрицы 4 подключены ко всем элементам 12 И соответствующих строк 13, а выходные шины 17 матрицы 4 подключены ко сем элементам 12 И соответствующИх столбцов 14. Входные шины.16 матрицы 4 подключены к выходу 3 (фиг.1) вход ного коммутатора 1, а выходные шины 17 (фиг2) соединяются со входом 7 (фиг,1) выходного коммутатора б. Шины управления 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 со" ответствует количеству двоичных разрядов в сдвигаемой информации и обоз" начено через и, Каждой группе 23-26 присвоен номер от 0 до и. Так на фиг.5 группе 23 присвоен номер О, группе 24 присвоен номер 1, группе 25 присвоен номер и-1 и, наконец, группе 26 присвоен номер и. Входные шины 2, количество которых равно количеству разрядов сдвигаемой информации и и которые пронумерованы с О по ив соответствии с номерами разрядов входной информации, подключены к входам 30 элементов 27 И групп 23-26, имеющих номер 1, соответствующий номеру шины 2 и входу 31 элементов 28 групп 23-26, номера которых определены как и-1, где 1 - номер шины 2. На Фиг.5 шина 2 с номером О подключена к входу 30 элемента 27 И группы 23 и ко входу 31 элемента 28 И группы 25. Шина 2 с номером иподключена ко входу 30 элемента 27 И группы 26 и ко входу 31 элемекта 28 И группы 23. Шина с номером 1 под" ключена ко входу 30 элемента 27 И группы 24, имеющей также номер 1, и ко входу 31 элемента 28 И группы 25, имеющей номер и-1. Шина 2, имеющая номер и-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(соединение не показано), имеющейтот же номер, что и связанная с ней1 группа 23-26 (Фиг.5) входного коммутатора 1.На Фиг.б показан пример выполнения выходного коммутатора б. Он собран по той же схеме, что и входной3) коммутатор 1 и содержит группы 35-38элементов, в каждую ив которых объединены элементы 39 и 40 И и элемент41 ИЛИ,Входы 42 элементов 39 И и входы25 43 элементов 40 И объединены по тому же законучто и во входном ком-.мутаторе 1 и подключены к информационным входам 7 выходного коммутатора б. Другие входы 44 элементов30 39 И объединены и подключены к управляющему входу 10 выходного коммутатора б. Другие входы 45 элементов40 И также объединены и подключены куправляющему входу 10 выходного кому мутатора б через элемент 46 НЕ. Столбцы 14 матрицы 4 через соответствующие выходные шины 17 соединены совходами 7 выходного коммутатора б,связанные с группами 35-38, имеющи"ми тот же номер, что и соответству 40 ющие столбцы 14 матрицы 4 (соединение на Фиг.б не показано), Выходыэлементов 41 ИЛИ являются выходамивыходного коммутатора б и подключены к выходным шинам 8, имеющим тот4 же номер, что и соответствующаягруппа 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 И в конкретномпримере может выполнять сдвиг тольковлево на количество разрядов от 0 доп. 10 15 20 25 ЗО 35 Ю 45 50 55 ЬО 6 В одном столбце 14 матрицы 4(фиг.4) одновременно может быть включен только один логический элемент12 И, так как активная диагональ 15(фиг.2) пересекает каждый столбецтолько один раз, а значит, толькона один из входов 19 (фиг.4) всехэлементов 12 И одного столбца 14 будет подан сигнал разрешения. На выход 22 логического элемента 23 ИЛИпоступает тот разряд информации, который подключен ко нторому входу 18активного элемента 12 И.Перед поступлением на матрицуэлементов 4 И (фиг.1) информацияпроходит входной коммутатор 1 (фиг.5),На его упранляющий вход 9 подаетсясигнал направления сдвига. В конкретном примере для сдвига влево подается положительный сигнал, которыйоткрывает по входам 32 элементы 27 Ив каждой группе 23, тем самым позволяя передачу информации с входныхшин 2 на выходы 3 входного коммутатора 1 разряд в разряд, т.е. транслируя их без всякого преобразования,Тот,же управляющий сигнал с управляющего входа 9 через элемент 34 НЕ закрывает элементы 28 И по их входам 33.Информация, сдвигаемая на матрицеэлементов 4 И влево, как это былопоказано, и через выходной коммутатор б (фиг.б) поступает на выходустройства. Выходной коммутатор б работает аналогично входному коммутатору 1, т.е. управляющий сигнал, поступающий на его управляющий вход 10отпирает по входам 44 нсе элементы36 И и.чеоез элемент 46 НЕ запираетпо входам 45 элементы 40 И.Информация с информационных входов 7 выходного коммутатора б без измененийпроходит на его выходы 8.При выполнении устройством операции сднига в направлении, котороене может обеспечить косоугольная матрица элементов 4 И производится преобразование ее на входном 1 и выходном б коммутатсрах,При этом на управляющие входы 9и 10 входного 1 и выходного б коммутаторов соответственно поступаетв конкретном примере сигнал отрицательной полярности, который препятствует прямому прохождению информации, закрывая по входам 32 (фиг.5)элементы 27 И и по входам 44 (фиг,б)элементы 39 И. Инвертированный наэлементе 34 НЕ (фиг.5) и; 46 (фиг.б)управляющий сигнал открывает по входам 33 (фиг.5) элементы 28 И и по входам 43 (фиг.б) элементы 40 И, разрешая прохождение информации на выходы 3 и 8 коммутаторов 1 и б соответственно по зеркальному закону.Выполнение сдвига вправо поясняется диаграммой (фиг.7), На фиг.7 а показана исходная информация, которую требуется сдвинуть вправо на 3 разряда. На фиг.7 б показана та же информация, поступающая на матрицу 4 после преобразования, показанного косыми стрелками между фиг,7 а и 7 б. На фиг.7 в показана информация после ее сдвига влево на матрице 4. На фит.7 г показана информация после выходного 15 преобразования, т.е. итоговая информация., Как видно из диаграммы, прои" зошел сдвиг вправо на три позиции, т.е, разряд а, переместился в четвертую клетку разрядной сетки, а, -1 3) в пятую и т.д.Для выполнения устройства средствами микроэлектроники, а именно в виде большой интегральной схемы (БИС) надо выбрать компромисс между быстродействием устройства и его рассейваемой мощностью. При применении МОП-технологии ограничения на количество элементов невелико, однако скорости работы устройства неудовлетворительныедля ЭВМ средней и боль- ЗО шой мощности. Выполнение данного устройства на биполярной технологии имеет существенные ограничения по количеству вентилей на кристалле и по допустимой рассеиваемой мощности 35 корпуса БИС.Представленная здесь структура позволяет выполнять БИС сдвига на быстрых элементах, так как вследствие сокращения количества логичес" 4 р ких элементов матрицы сдвига, общее количество элементов БИС укладывается в предельно допустимые технологические допуски.Формула изобретения 451. Устройство для сдвига информации, содержащее матрицу элементов И,шины управления, подключенные к соответствующим элементам И диагоналей матрицы, входные и выходные информационные шины, причем выходы элементов И каждого столбца матрицы подключены к соответствующему элементу ИЛИ, о т л и ч а ю щ е е с я тем, что, с целью сокращения количества оборудования, оно содержит входной коммутатор, подключенный информационными входами к входным информационным шинам, а выходами к элементам И соответствующих строк матрицы, и выходной коммутатор, информационные входы которого соединены с элементами ИЛИ соответствующих столбцов матрицы, выходы соединены с выходными ин- формационными шинами, а управляющий вход подключен к управляющему входу входного коммутатора и к входу задания направления сдвига устройства.2; Устройство по п.1, о т л и ч а ю щ е.е с я темо что входной и выходной коммугаторы содержатгруппы элементов по числу разрядов обраЬатываемой информации в каждом, состоящие из двух элементов И, выходы которых подключены ко входам элемента ИЛИ, выходы элементов ИЛИ каждой группы соединены с соответствующими выходами коммутаторов, первый вход первого элемента И каждой группы подключен к управляющему входу коммутатора, а второй подключен к 1-му информационному входу коммутатора, первый вход второго элемента И той же группы подключен к управляющему входу коммутатора через элемент НЕ, а второй его вход подключен к (и-1)-му информационному входу коммутатора, где 1=0,1,2празряды обрабатываемой информации.Источники информации,принятые во внимание при экспертизе 1. Патент СНА 9 3914744,кл340-172.5, 1975. 2. Патент Франции 9 2242727,кл. С 06 Р 7/00, 1975. 3. Патент СЫА Р 3961750,кл. 235-164, 1976 (прототип) .