The module "multiply_karatsuba"
a recursive VHDL implementation of the Karatsuba multiplication algorithm

The recursive VHDL module "multiply_karatsuba" (see symbol) calculates the signed product of a multiplicand and a multiplier with the Karatsuba algorithm.

• The module "multiply_karatsuba" is a recursive VHDL model, this means,
  there is a submodule in which the same submodule is instantiated.
• The module "multiply_karatsuba" calculates the product in 1 clock cycle.
• The number of bits of multiplicand and multiplier are configured by generics.
• Product, multiplicand and multiplier are numbers in 2's complement format.
• As the karatsuba algorithm cannot handle 2's complement format, the operands are converted
  to unsigned operands and the unsigned product is at last converted back into 2's complement.
• The module uses flipflops only for storing the product.
• The module has 2 architectures: One which implements the Karatsuba algorithm
  and a second which uses the VHDL multiplication operator '*'.

The Karatsuba algorithm is based on dividing the factors (multiplicand and multiplier) into an upper half and a lower half.
The multiplication is then realized by products calculated only with this halfs.
This dividing does not work with negative numbers in 2's complement, so the factors are first converted to unsigned.
Their sign is remembered and later on used to convert the always positive product back into 2's complement.
The Karatsuba algorithm expects the factors to have the same number of bits.
So the factor with less bits is extended to have the same number of bits as the other factor.
As the number of bits is halfed at each stage of the Karatsuba algorithm, the bit number
of the factors is extended to a power of 2.

The module "multiply_karatsuba" was developed with HDL-SCHEM-Editor.

Ports:

Port name	Direction	Description
res_i	input	asynchronous reset input, 1-active
clk_i	input	clock input
start_i	input	This input expects an 1-active impulse of 1 clock cycle width in order to start the calculation.
multiplicand_i(g_multiplicand_width-1:0)	input	Signed multiplicand (g_multiplicand_width is a generic)
multiplier_i(g_multiplier_width-1:0)	input	Signed multiplier (g_multiplier_width is a generic)
ready_o	output	1-active impulse of 1 clock cycle width, when the calculation is ready (in the next clock cycle after start_i=1).
product_o(g_multiplicand_width+g_multiplier_width-1:0)	output	Signed product. Valid at ready_o=1.

Generics:

Generic name	Minimum Value	Maximum Value	Description
g_multiplicand_width	2	none	Number of bits of the multiplicand The first bit represents the sign as the operands have to be coded in 2's complement.
g_multiplier_width	2	none	Number of bits of the multiplier The first bit represents the sign as the operands have to be coded in 2's complement.

The module "multiply_karatsuba" is a hierarchical module, which uses only the submodule multiply_karatsuba_step.
This submodule multiply_karatsuba_step has only instances of itsself, so there are several submodules used, but they are all from tpye multiply_karatsuba_step.

Submodule name	Functionality
multiply_karatsuba_step	This submodule implements the Karatsuba algorithm. The incoming unsigned operands must have a identical number of bits. This number of bits must be a power of 2. The incoming operands are divided into 2 halfs with identical bit width. These half sized operands are connected to other multiply_karatsuba_step modules located inside multiply_karatsuba_step. This leads to recursive hardware.

There are no limitations for the generics g_multiplicand_width and g_multiplier_width (except that they must be bigger than 1).
These generics are most of the time determined by the environment, where the module multiply is used.

Source code for HDL-SCHEM-Editor and HDL-FSM-Editor for module "multiply_karatsuba" and its testbench (Number of downloads = 40 ).
With these files the schematics and the state-diagram of module "multiply_karatsuba" can be loaded into HDL-SCHEM-Editor or HDL-FSM-Editor and can be easily read and modified:

• hdl_editor_designs.zip

All module VHDL-files of the module "multiply_karatsuba" (Number of downloads = 38 ).
These files were generated by HDL-SCHEM-Editor and HDL-FSM-Editor:

• VHDL_designs.zip

All testbench VHDL-files of the testbench of the module "multiply_karatsuba" (Number of downloads = 22 ).
These files were generated by HDL-SCHEM-Editor and HDL-FSM-Editor:

• VHDL_testbenches.zip

Relocation hints:

You should extract all archives into a folder named "multiply_karatsuba".
Then you must replace "M:/gesicherte Daten/Programmieren/VHDL/multiply_karatsuba" in all "hdl_editor_designs/*.hse" source files by your path to this directory.
Now you can navigate through the design by HDL-SCHEM-Editor and generate HDL by HDL-SCHEM-Editor for all modules .
Of course there is only need for generating HDL, if you change something at the modules, because you can find the HDL in VHDL_designs.zip and VHDL_testbenches.zip.
If you want to simulate or modify the modules by HDL-SCHEM-Editor you also must adapt the information in the Control-tab of the toplevel you want to work on.
There you must define a "Compile through hierarchy command", an "Edit command", the path to your HDL-FSM-Editor and a "Working directory".

Change log:

Version 1.0 (07.04.2024):

• Initial version

If you detect any bugs or have any questions,
please send a mail to "matthias.schweikart@gmx.de".