How to generate a CSA tree?

Depending on your requirements (area/speed), I would build a booth 2 or booth 3 multiplier and just use '+' for addition. That would allow the synthesis tool to choose the best adder for your requirement. Of course a '*' should do almost the same, except I don't think many synthesis tools support booth 3 architectures.

Regards, rudi ======================================================== ASICS.ws ::: Solutions for your ASIC/FPGA needs ::: ..............::: FPGAs * Full Custom ICs * IP Cores ::: FREE IP Cores ->

Sleep Mode wrote: : Hi all,

: I am trying to design a 16-bit integer multiplier in VHDL and I want to use : a Carry-Save-Adder (CSA) tree for generating the interim subproducts : and -then- with an additional CPA (or other) adder to add them to the final : 32-bit product; i.e. I want to build a full-tree multiplier.

: My question is whether there is some automatic (core) generator for the : CSA-tree interconnections since it is rather complicated to do it by hand... : If not, is there any fast method of drawing it manually (pen-and-paper) so : that I can translate it to VHDL later on?

For example, XST infers a quite fast multiplier for the verilog statement

assign ab = a*b;

when no hardware multipliers are available or LUT style is choosen. So you don't need to care for the inner workings.

Regarding Peter's proposal about using parts with hardware multipliers: They either give headaches for the Test boards, as the parts only come as fine pitch BGAs (VirtexII) or they will give you headache with getting them, as they are not yet released (Spartan III). And both Virtex II and Spatan III are no longer 5 Volt tolerant, often giving additional headache with interfacing other parts.

Bye

Yes I agree. Chris, try it and see.

True, but that may be a "Home Related Requirement" (HRR).

-- Mike Treseler

What is your target? If it is an FPGA with fast carry chains, then it generally

doesn't make sense to use a CSA architecture unless it is for an educational exercise. In most technologies, fast adders are more resource intensive than the simplest adder (a ripple carry adder). A CSA adder tree postpones the carry so that only one of the more expensive adders is needed; all the other adds are just half adders. This provides the speed of a multiplier implemented using fast adders throughout without the attendant expense. In the case of an FPGA with a fast carry chain, the lowest cost adder (a ripple carry adder using the fast carry chain) also happens to be the fastest, in fact with the Xilinx architecture the fast carry chain adders use HALF the resources one without the fast carry chain uses because the carry half of the half adders is in dedicated logic that is there whether you use it or not. Since the cheapest adder in the FPGA is also the fastest, there is no need to resort to schemes such as a CSA (a wallace tree is a CSA adder tree arranged as a tree structure). The one place a CSA architecture makes sense with the FPGA is if you are really out there on the speed such that you are pipelining the carry in the adder in order to achieve the speed.

--

--Ray Andraka, P.E. President, the Andraka Consulting Group, Inc.

"They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759

generally

algorithmically

--

--Ray Andraka, P.E. President, the Andraka Consulting Group, Inc.

"They that give up essential liberty to obtain a little temporary safety deserve neither liberty nor safety." -Benjamin Franklin, 1759