Posts: 247
Threads: 5
Joined: Jan 2010
MULTIPLIER ACCUMULATOR COMPONENT
VHDL IMPLEMENTATION- A Project REPORT
Introduction
As integrated circuit technology has improved to allow more and more
components on a chip, digital systems have continued to grow in complexity. As digital
systems have become more complex, detailed design of the systems at the gate and
flip-flop level has become very tedious and time consuming. For this reason, use of
hardware description languages in the digital design process continues to grow in
importance. A hardware description language allows a digital system to be designed
and debugged at a higher level before conversion to the gate and flip-flop level. Use of
synthesis CAD tools to do this conversion, is becoming more widespread. This is
analogous to writing software programs in a high level language such as C, and then
using a compiler to convert the programs to machine language. The two most popular
hardware description languages are VHDL and Verilog.
The MAC unit provides high-speed multiplication, multiplication with cumulative
addition, multiplication with cumulative subtraction, saturation, and clear-to-zero
functions. These operations are extensively used in Fast Fourier Transforms required
by the MP3 Chip. The 16 bit multiplier accumulator unit is based on the multiplier
accumulator specification of the Analog Devices ADSP2181 chip.
Field Programmable Gate Arrays (FPGAs) are being used increasingly in
embedded general purpose computing environments as performance accelerators.
This new use beyond the traditional usage as glue logic and as a rapid prototyping
enabler has also renewed interest in the FPGA architecture. The fine grain
reconfigurability of the FPGA architecture makes it an ideal candidate for use in
system-on-chip environments that strive to integrate heterogeneous programmable
architectures
2.1 Multiplication of positive numbers
The usual paper-and-pencil algorithm for multiplication of integers
represented in any positional number system is illustrated in the fig.1 for the binary
system assuming positive 4-bit operands. The product of two n-digit numbers can be
accommodated in 2n digits. So the product in this example fits into 8 bits. In the binary
system, multiplication of the multiplicand by 1 bit of multiplier is easy. If the multiplier
bit is 1, the multiplicand is entered in the appropriately shifted position to be added
with other shifted multiplicands to form the product. If the multiplier is 0, then 0s are
entered.
It is possible to implement positive operand binary multiplication in purely
combinational two-dimensional logical array, as shown in fig.2. The main component
in each cell is an adder circuit. The AND gate in each cell determines whether a
multiplicand bit mj is added to the incoming partial product PPi to generate the
outgoing partial product PP(i+1) if qi =1.If qi =0, PPi is passed vertically downward
unchanged. PP0 is obviously all 0s,and PP4 is the desired result. The multiplicand is
shifted one bit position left per row by the diagonal signal path.
Although the above combinational multiplier is quite easy to understand, it
may be impractical to use when dealing with long numbers, because it uses a large
number of gates and performs only a single function.
2.2 Signed-operand multiplication
Multiplication of signed operands generating a double-length product in
the 2â„¢s complement number system requires a few remarks on that representation
scheme.The accumulation of partial products by adding versions of the multiplicand as
selected by the multiplier bits is still the general strategy.
When we add a negative multiplicand to a partial product ,we must
extend the sign bit value of the multiplicand to the left as far as the extent of the
eventual product. The extension of a positive number is achieved by the addition of
zeros at the left end. In the same way a negative number is converted into a number
with larger number of bits and same value by adding required number of 1s to the left
.combining both we conclude that in 2â„¢s complement representation a number is
converted into another number of larger number of bits and same value by extending
the sign bit to the left as many times as required. This operation is called sign
extension.
Now consider the case of negative multipliers. A straight forward solution
is to form the 2â„¢s complement of both the multiplier and multiplicand and proceed as in
the case of a positive multiplier. This is possible because complementation of both the
operands does not change the value or the sign of the product. Another method that
works correctly for negative numbers in 2â„¢s complement representation is to add shifted versions of the multiplicand, properly sign extended ,just as in the case of
positive multipliers, for all 1 bits of the multiplier to the right of the sign bit. Then add “
1*multiplicand, properly shifted, if there is a 1 in the sign bit position of the multiplier.
The sign position is thus viewed in the same way as the other positions, except that it
has a negative weight. The general version of this property of the 2â„¢s complement
representation will be used in the next section describing Booth algorithm.
The MAC Design
Many digital signal processing algorithms, including FFT, filtering/equalization,
and demodulation, make use of multiplier accumulators (MAC). A complex MAC
operates on two sequences of complex number {xi} and {yi}. The MAC multiplies
corresponding elements of the sequences and accumulates the sum of the products.
Each complex number is represented in Cartesian form, consisting of a real
and an imaginary part. If we are given two complex numbers x and y, their product is a
complex number p, calculated as follows:
p_real = x_real × y_real - x_imag × y_imag
p_imag = x_real × y_imag + x_imag × y_real
The sum of x and y is a complex number s calculated as follows:
s_real=x_real+y_real
s_imag = x_imag + y_imag
MAC calculates its results by taking successive pairs of complex numbers, one
each from the two input sequences, forming their complex product and adding it to an
accumulator register. The accumulator is initially cleared to zero and is reset after
each pair of sequences has been processed.
Data is represented with a 16 bit, two's complimented fixed -point binary
representation. Each of the real and imaginary parts of the two complex numbers and
the complex output of the MAC uses the same representation where bit 15 is the sign
bit and the binary point is assumed to be between bits 15 and 14. This format will
facilitate numbers in the range -1 (inclusive) to +1 (exclusive) with a resolution of
2×exp(-15). This raises the possibility of overflow occurring while summing a
sequence of numbers, so we include an overflow status signal in the design. Overflow
can occur in two cases. First, intermediate partial sums may fall outside the range -1
to +1. We can reduce the likelihood of this happening by expanding the range used to
13
represent intermediate results to -16 to +16. However, if an intermediate sum falls
outside of the expanded range, the summation for the entire sequence is in error, so
the overflow signal must be set. It remains set until the accumulator is cleared,
indicating the end of the summation. The second overflow case happens if the final
sum falls outside the range of values representable by the MAC output. This may be
a transient condition, since a subsequent product, when added to the sum, may bring
the sum back in range. Assert the overflow signal only during a cycle in which the
final sum is out of range, rather than latching the overflow until the end of summation.
We implemented a 16 bit multiplier accumulator unit based on the multiplier
accumulator specification of the Analog Devices ADSP2181 chip. The MAC uses two
16 bit registers to obtain the data from the DMD (data memory data) bus and PMD
(program memory data) bus. The 16 bit data from the registers will be used in
multiplication and accumulation process in multiplier and adder unit accordingly.
Output will be placed on the RBUS or back to DMD or PMD bus.The MAC Unit can be
broken up into two distinct units: a data storage path and a data processing path. The
data storage path consists of a set of registers that hold data values. The data
processing path consists of multiplier unit and adder unit, which perform data
multiplication and accumulation sequentially. The control signals provided by the iunit
(instruction unit) designate what process the MAC will perform to get the desired
data in one clock cycle
In the MAC design, both the multiplier and adder are complete custom
designs. The multiplier uses the combination of a Booth bit pair encoding algorithm, a
sign extension technique, and a carry look ahead adder. The Booth encoding
algorithm is a technique that will reduce the number of partial products generated.
Using the booth-encoding algorithm, fewer partial products will have to be added and
therefore the overall speed of the multiplication will be faster. The top level diagram of
MAC is given in the next page( fig.7).
Full project report:
[attachment=1145]
