Конвейерный сумматор Советский патент 1990 года по МПК G06F7/49 

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

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

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

Конвейерный сумматор содержит входные шины 1 и 2, суммирующие ячейки 3- 8, последовательно соединенные такти- руемые элементы 9.1-9.5 памяти, выходную шину 10.

Работу конвейерного сумматора рассмотрим на примере суммирования вось- миразрядных () чисел в I-коде Фи- боначчи ().

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

10101010

10000100

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

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

Коды по входным шинам 1 и 2 поступают на входы суммирующих ячеек 3.1- 3.8. На суммирующих ячейках 3.1-3.8 начинается первый этап процесса сум- мирования. По тактовому сигналу (не показан), поступающему на тактирующие входы суммирующих ячеек, значения первой промежуточной суммы и значения переносов запоминаются в суммирующих ячейках 3.1-3.8 (пункты 3 и 4 таблицы) . Значения разрядов промежуточной суммы с выходов сумм (выходов первых тактируемых элементов памяти) сум0

0

5

0

5

Q

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

Таким образом, время сложения в конвейерном сумматоре определяется временем работы одной суммирующей ячейки, т.е.

Т где С

ЈF+T

тэ л

S ТЭГ)

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

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

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

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

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

5956

По шестому тактовому сигналу на суммирующих ячейках 8.1-8.8 начинает ся шестой, последний этап суммирования. Но окончании шестого этапа суммирования на выходах суммирующих ячеек 8.1-8.8 и выходе тактируемого элемента 9.5 памяти появляется результат суммирования, поступающий на

выходную шину Ю, причем содержимое тактируемого элемента 9.5 памяти является старшим разрядом результата

суммирования. i

Таким образом, для данного случая

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

0 р-коде Фибоначчи необходимо -r+k

5

этапов суммирования, где --- п

целое число.

5

5

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

Конвейерный сумматор, содержащий матрицу из n x m суммирующих ячеек, где п - разрядность суммируемых чи- Q сел , m - число столбцов матрицы,

п , , , п где т -7+K-, C log2-- - целое число,

р - номер кода Фибоначчи, причем первые входы (i,j)-x суммирующих ячеек, где i - номер строки матрицы, j - номер столбца матрицы, для которых i 1,...,n, , подключены к соответствующим весовым разрядам первой входной шины конвейерного сумматора, вы-

ход суммы каждой (i,j)-и суммирующей ячейки, для которой ,...,n, j 1,...,m-1, соединен с первым входом соответствующей (i,j+1)-u суммирующей ячейки, выход суммы каждой сумс мирующей ячейки последней строки матрицы соединен с разрядами выходной шины суммы конвейерного сумматора, вторые входы (i,j)-x суммирующих ячеек, для которых , ,...,m, под-

Q ключены к шине Лог.О, в каждой суммирующей ячейке первый и второй входы подключены к соответствующим входам сумматора, выход суммы которого соединен с входом первого тактируемого элемента памяти, выход которого соединен с выходом суммы суммирующей ячейки, выход переноса которой соединен с выходом второго тактируемого элемента памяти, вход которого под-

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

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

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