Конвейерный сумматор

 

Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных конвейерных процессорах для суммирования многоразрядных чисел, представленных в минимальной форме в фибоначчиевой системе исчисления. Цель изобретения - упрощение устройства при сложении чисел, представленных в фибоначчиевой системе исчисления. Конвейерный сумматор содержит входные шины 1 и 2, суммирующие ячейки 3-8, тактируемые элементы памяти 9,1-9,5 и выходную шину 10. Коды слагаемых по входным шинам 1 и 2 поступают на входы сумматоров суммирующих ячеек 3<SB POS="POST">1</SB>-3<SB POS="POST">8</SB>. Значения промежуточных сумм и переносов запоминаются в соответствующих тактируемых элементах памяти суммирующих ячеек и по очередному тактовому сигналу поступают на следующую строку суммирующих ячеек конвейерного сумматора. Результат суммирования поступает на выходную шину 10. 1 ил., 1 табл.

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

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

РЕСПУБЛИК (19) (11) (51)5 С 06 49

О И )) НИЕ ИЗОБРЕТЕНИЯ

2 (54) КОНВЕЙЕР НЬП1 СУММАТОР

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

flO ИЗОБРЕТЕНИЯМ И ОТНРЦТИЯМ

ПРИ ГКНТ СССР

H АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

1 (21) 4445552/24-24 (22) 31.05.88 (46) 07.02.90. Вюл. Р 5 (71) Научно-производственное объединение космических исследований (72) Я.А.Мамедов, Ф.А.Мамедов и И.З.Животовский (53) 681.325(088.8) (56) Авторское свидетельство СССР

Р 570896, кл. G 06 F 7/49, 1977.

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

N - 1067499, кл. G 06 F 7/50, 1982. (57) Изобретение относится к вычислительной технике и может быть использовано в высокопроизводительных конвейерных процессорах для суммирования многоразрядных чисел, представленных в минимальной форме в фибоначчиевой системе исчисления. Цель изобретенияупрощение устройства при сложении чисел, представленных в фибоначчиевой системе исчисления. КонвейерньИ сум1541595 запоминаются в соответствующих тактируемых элементах памяти суммирующих ячеек и по очередному тактовому сиг5 налу поступают на следующую строку суммирующих ячеек конвейерного сумматора. Результат суммирования поступает на выходную шину 10. 1 ил., 1 табл.

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

Цель изобретения — упрощение устройства при сложении чисел, представленных в минимальной форме в фибоначчиевой системе исчисления.

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

Конвейерный сумматор содержит входные шины 1 и 2, суммирующие ячейки 38, последовательно соединенные такти- 30 руемые элементы 9.1-9.5 памяти, выходную шину 10, - Работу конвейерного сумматора рассмотрим на примере суммирования вось" миразрядных (n=8) чисел в I-коде Фи- 35 боначчи (р=1) .

Наиболее неблагоприятная ситуация возникает при сложении следующих кодовых комбинаций:

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

Конвейерный сумматор работает сле- 45 дующим образом.

Коды по входным шинам 1 и 2 поступают на входы суммирующих ячеек 3,13.8. На суммирующих ячейках 3.1-3.8 начинается первый этап процесса сум- О мирования. По тактовому сигналу (не показан), поступающему на тактирующие входы суммирующих ячеек, значения первой промежуточной суммы и значения переносов запоминаются в суммирующих ячейках 3.1-3.8 (пункты 3 и 4 таблицы). Значения разрядов промежуточной суммы с выходов сумм (выходов первых тактируемых элементов памяти) суминтор содержит входные шины 1 и 2, суммирующие ячейки 3-8, тактируемые элементы 9.1-9.5 памяти и выходную шину 10. Киды слагаемых по входным шинам i и 2 поступают на входы сумматоров суммирующих ячеек 3 "3 . Значения промежуточных сумм и переносов мирующих ячеек 3.1-3.8 поступают одновременно на первые входы соответствующих суммирующих ячеек 4.1-4.8, а значения разрядов кода переноса с выходов переносов (выходов вторых тактируемых элементов памяти) суммирующих ячеек 3.8-3.3 поступают на третьи входы суммирующих ячеек 4.6-4.1. Значения разрядов кода переносов с выходов переносов суммирующих ячеек

3.7-3 ° 1 поступают на вторые входы суммирующих ячеек 4.8-4.2. Значения разрядов кода переноса с выхода суммирующей ячейки 3.8 поступают на вход первого тактируемого элемента 9.1 памяти, где запоминаются при поступлении второго тактового сигнала. Этим заканчивается первый этап суммирования. Вообще каждый этап суммирования в кодах Фибоначчи заканчивается формированием промежуточной суммы и кода переноса, а весь процесс суммирования заканчивается с получением нулевого кода переноса. После окончания каждого этапа суммирования в конвейерный сумматор могут быть введены числа для сложения, Таким образом, время сложения в конвейерном сумматоре определяется временем работы одной суммирующей ячейки, т.е, Л Л

Т="е+ r ò я где з время переходных rlpo цессов сумматора и тактируемогб элемента памяти соответственно.

По второму тактовому сигналу на суммирующих ячейках 4.1-4,8 начинается второй этап суммирования, по окончании которого на выходах суммирующих ячеек 4.1-4.8 появляются значения разрядов второй промежуточной суммы и кода переноса (пункты 5 и 6). На этом этапе суммирования и. в дальнейшем на суммирующих ячейках 4.8, 5.8, 6.8, 7.8 и 8.8 в силу свойств суммирования чисел в кодах Фибоначчи в ми

5 154159 нимальной форме переносы возникать не будут. Значения разрядов второй промежуточной суммы с выходов суммирующих ячеек 4.1-4.8 поступают на первые входы соответствующих суммирующих ячеек 5 ° 1-5.8. Зчачения разря. дов кода переноса с выходов суммирующих ячеек 4.1-4.8 поступают на вторые и третьи входы соответствую10 щих суммирующих ячеек 5.1-5.8 аналогично описанному в первом этапе суммирования.

По третьему тактовому сигналу на суммирующих ячейках 5.1-5.8 начинается третий этап суммирования. При этом содержимое тактируемого элемента 9.1 памяти переписывается в элемент 9.2 памяти. По окончании третьего этапа суммирования на соответст- 20 вующих выходах суммирующих ячеек 5.15.8 появхгяются значения третьей промежуточной суммы и кода переноса (пункты 7 и 8). Значения разрядов промежуточной суммы с выходов суммирующих ячеек 5.1-5.8 поступают на первые входы соответствующих суммирующих ячеек 6.1-6.8. Значения разрядов кода переноса с выходов суммирующих ячеек 5.1-5.8 поступают на вто- 30 рые и третьи входы соответствующих суммирующих ячеек 6.1-6.8 аналогично описанному в предыдущем этапе суммирования.

По четвертому тактовому сигналу на суммирующих ячейках 6.1-6.8 начинается четвертый этап суммирования.

По окончании четвертого этапа суммирования, проходящего аналогично предыдущим этапам, на выходах сумми40 рующих ячеек 6.1-6.8 появляются значения четвертой промежуточной суммы и кода переноса (пункты 9 и 10), которые поступают на входы суммирующих ячеек 7.1-7.8, а содержимое из тактируемого элемента 9.2 памяти переписывается в эхгемент 9.3 памяти.

По пятому тактовому сигналу на суммирующих ячейках 7.1-7,8 начинается пятый этап суммирования, по окончании которого, проходящего аналогично предыдущим этапам, на выходах суммирующих ячеек 7.1-7.8 появляются значения пятой промежуточной суммы и кода переноса (пункты 11 и 12), кото55 рые поступают на входы суммирующих ячеек 8.1-8.8, я содержимое из такти-! руемого элемента 9. 3 памяти переписывается в элемент 9.4 памяти.

11с шестому тактовому сигналу ня суммирующих ячейках 8,1-8.8 начиняет ся шестой, последний этап суммирования. По окончании шестого этапа суммирования ня выходах суммирующих ячеек 8.1-8.8 H выходе тактируpMoI элемента 9.5 памяти появляется результат суммирования, поступающий на выходную шину 10, причем содержимое тактируемого элемента 9.5 памяти является старшим разрядом результата суммирования. !

Таким образом, для данного случая за шесть этапов возможно суммирование чисел, представленных восьмиразрядным I-кодом Фибоначчи. В общем случае для суммирования и-разрядных чисел в и р-кодр Фибоначчи необходимо +k

p+ 1 и этапов суммирования, где k=log р+1 целое число.

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

Конвейерный сумматор, содержащий матрицу из и х пг суммирующих ячеек, где и — разрядность суммируемых чисел, m — число столбцов матрицы, и и где m=---+k, k=log --- — целое число, p+1 р+1 р — номер кода Фибоначчи, причем первые входы (i,j)-х суммирующих ячеек, где i — - номер строки матрицы, j — - номер столбца матрицы, для которых i=

1,...,п, =1, подключены к соответствующим весовым разрядам первой входной ыины конвейерного сумматора, выход суммы каждой (i,j)-й суммирующей ячейки, для которой =1,...,п> 3=

=1,...,m-1, соединен с первым входом соответствующей (i,j +1)-й суммирующей ячейки, выход суммы каждой суммирующей ячейки последней строки матрицы соединен с разрядами выходной шины суммы конвейерного сумматора, вторые входы (i,j)-х суммирующих ячеек, для которых 1=1, )=2,...,m, подключены к шине "Лог.О", в каждой суммирующей ячейке первый и второй входы подключены к соответствующим входам сумматора, выход суммы которого соединен с входом первого тактируемого элемента памяти, выход которого соединен с выходом суммы суммирующей ячейки, выход перенося которой соединен с выходом второго тактируемого элемента памяти, вход которого под1541595 ячеек, для которых i=1,...,n, j=1, подключены к соответствующим весовым. разрядам второй входной шины конвейерного сумматора, выход переноса (i,j)-й суммирующей ячейки, для которой i=1,...,n-f,j=1,...,m — 1, подключен к второму входу (i+1 j +1)-й суммирующей ячейки, а выход переноса каждой суммирующей ячейки, для которой i=p+2,...,n-1, j =1,...,m-1, подключен к третьему входу (i — p-1, j+1) и суммирующей ячейки, третьи входы суммирующих ячеек р+1 старших разрядов всех столбцов, для которых

j=2,...m, подключены к шине "Лог.0". ключен к выходу переноса сумматора, отличающийся тем, что, с целью упрощения сумматора при сложении чисел представленных в мини5 мальной форме в Фибоначчиевой системе исчисления, в него дополнительно введены m- 1 последовательно соединен> ных тактируемых элементов памяти, причем вход первого тактируемого элемента памяти соединен с выходом переноса суммирующей ячейки, для которой i--n, j=1 а выход последнего тактируемого элемента памяти соединен с выходом переноса конвейерного сумматора, вторые входы суммирующих

Пункты Коды

Веса разрядов I-кода Фибоначчи Десятичный

3421 138 5 3 2 1 1

1 0 1

0 0

0 0 1

1 0 0 1

1 0 0 0

0 0 1 0

1 0 1 0

0 0 0 0

1 0 1 0

0 0 0 0

1 0 1 0

0 0 0 0

1 0 1 0

О 0 0 0

33

23 (1-я) (2-я) (3-я) (4-я) (5-я) 56

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

Техред Л.Олийнык: Корректор Л.Патай

Редактор А,Козориз

Заказ 281 Тираж 561 Подписно

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

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

Производственно-издательский комбинат "Патент", г.ужгород, ул . Гагарина, 101

2

4

6

8

11 .12

13

14

Первое слагаемое

Второе слагаемое

Промежуточная сумма

Код переноса (1-й)

Промежуточная сумма

Код переноса (2-й)

Промежуточная сумма

Код переноса (3-й)

Промежуточная сумма

Код переноса (4-й)

Промежуточная сумма

Код переноса (5-й)

Результат, Переносы

0 1 0 1 0

0 0 1 0 0

0 1 1 1 0

0 0 0 0 0

0 1 1 1 0

0 1 0 0 0

0 0 1 1 0

1 0 0 1 0

1 0 1 0 0

0 0 1 0 0

1 0 0 0 0

0 1 0 0 1

1 0 0 1

0 0 0 0 0