Multipliers:Multiplier Based on a Redundant Binary Adder Tree.

Multiplier Based on a Redundant Binary Adder Tree

There is another fast multiplier based on a rather regular structure called a multiplier based on a redundant binary adder tree [11]. In it, multiplicand-multiples are generated first as in other parallel multipliers, being regarded as redundant binary numbers, and are summed up pairwise by means of redundant binary adders connected in binary tree form. Then, finally, the product represented in the redundant binary representation is converted into the ordinary binary representation. The redundant binary representation, also called the binary signed-digit representation, is a binary representation with a digit set {1, 0, 1}, where 1 denotes –1 [1]. An n-digit redundant binary number A = [an–1an–2 …a0] has the value i =0 ai × 2 , where ai takes a value 1, 0, or 1. There may be several redundant binary numbers which have the same value. For example, [0101], [0111], [1101], [1 11 1], and [101 1] all represent 5.

Because of this redundancy, we can add two redundant binary numbers without carry propagation.

Let us consider the addition of two redundant binary numbers, that is, the augend, A = [an–1an–2 …a0], and the addend, B = [bn–1bn–2 …b0] to derive the sum, S = [snsn–1 …s0], where each of ai, bi, and si takes a value –1, 0, or 1. The addition without carry propagation is done in two steps. In the first step, an intermediate carry ci+1, and intermediate sum di in the i-th position are determined such that ai + bi = 2ci+1 + di is satisfied (the 2 of 2ci+1 means shifting ci+1 to the next higher digit position as a carry), where each of ci+1 and di is –1, 0, or 1. In this case, ci+1 and di are determined such that a new carry will not be generated in the second step. In the second step, in each digit position, sum si is determined by adding intermediate sum di and intermediate carry ci from the next lower position, where ci takes a value, –1, 0, or 1.

Suppose one of addend digit ai and addend digit bi is 1 and the other is 0. If ci +1 = 0 and di = 1 in the first step, a new carry will be generated for ci = 1 from the next lower digit position in the second step. So, if there is a possibility of ci = 1, we choose ci +1 = 1 and di = 1. On the other hand, if there is a possibility of ci = 1, we choose ci +1 = 0 and di = 1. This makes use of the fact that 1 can be expressed by [01] and [11] in the redundant binary number representation. Whether ci becomes 1 or 1 can be detected by examining ai–1 and bi –1 in the next lower digit position but not further lower digit positions. For other combinations of the values of ai, bi, and ci, ci+1 and di can be similarly determined.

In the second step, si is determined by adding only two digits, ci and di. Suppose ci = 1. Then si is 0 or 1, based on whether di is 1 or 0. Notice that two combinations, ci = di = 1 and ci = di = 1, never occur. For other combinations of the values of ci and di, si is similarly determined. Consequently, sum digit si at each digit position can be determined by the three digit positions of the angend and addend, ai , ai –1 and ai –2, and bi, bi –1, and bi –2.

A binary number is a redundant binary number as it is, so there is no need for converting it to the redundant binary number representation. But conversion of a redundant binary number to a binary number requires an ordinary binary subtraction. Namely, we subtract the binary number that is derived by replacing every 1 by 0 and 1 by 1 in the redundant binary number, from the binary number that is derived by replacing 1 by 0. For example, [11011] is converted to [00111] by the subtraction [10001] – [01010]. We need borrow propagate subtraction for this conversion. This conversion in a multiplier based on a redundant binary adder tree corresponds to the final addition in the ordinary multipliers.