Signed multiplier in VHDL or Verilog
 --------------------------------------

genmul.py is a Python script for generating a signed multiplier
in synthesizable VHDL or Verilog code.

The multiplier is implemented in terms of basic logic blocks: inverters,
booth encoders, half adders, full adders and carry propagation logic.
These basic blocks are provided as a small VHDL or Verilog library.
The top-level multiplier instantiates many of these basic blocks
and wires them together.


  Algorithm
  ---------

Radix-4 Booth encoding is used to construct a signed multiplier and
to reduce the number of partial products. The partial products are
combined with a Dadda tree to form two binary words. These two words
are added to obtain the final result. The final adder uses a Brent-Kung
carry-lookahead tree.

The generated multiplier can be purely combinatorial or it can optionally
contain one or two pipeline stages. Pipeline stages are created by inserting
an array of flip-flops between the Dadda tree and the final adder and/or
in the final output of the multiplier.

Geoff Knagge gives a good introduction to Booth encoding on his website,
http://www.geoffknagge.com/fyp/booth.shtml.

The method for merging partial products is described in L. Dadda,
"Some schemes for parallel multipliers", Associazione Elettrotecnica et
Elettronica Italiana, 1965.

A carry-lookahead adder is described in R. P. Brent, H. T. Kung,
"A Regular Layout for Parallel Adders", IEEE Transactions on Computers, 1982.


  Examples
  --------

To generate a signed 24x18-bit pipelined multiplier in VHDL:
  genmul.py --lang=vhdl 24 18 1 > mymul.vhdl

To generate a signed 8x8-bit combinatorial multiplier in Verilog:
  genmul.py --lang=verilog 8 8 0 > mymul.v


  Applications
  ------------

None really.
This is a hobby project.

These multipliers have never been used in a production system.
In fact these multipliers have never even been tested in actual hardware.

Generated multipliers of several word lengths have been extensively
tested in simulation and appear to work correctly.

Generated multipliers are synthesizable with Xilinx ISE 14 and Vivado 2014.
Resource utilization and timing are reasonable. About 500 LUTs are used
for an 18x18-bit multiplier on Virtex-7. This is in the same ballpark as
the LUTs used by the Xilinx synthesizer when forced to synthesize a built-in multiplication operator without DSPs.

However, modern FPGAs contain hardwired DSP blocks which provide multipliers
that are faster and more resource-efficient than the digital circuits
generated by genmul.py. Nobody in their right mind would use genmul.py
for practical FPGA-based multipliers.

--