The module "division"
a VHDL and Verilog implementation of the non restoring division algorithm

The module "division" (available as VHDL or Verilog design) (see symbol) calculates the signed quotient and the signed remainder of a dividend and a divisor.

The number of bits of dividend and divisor are configured by generics.
Dividend, divisor, quotient and remainder are numbers in 2's complement format.
Before the division is started, the incoming operands are converted into unsigned numbers.
After the division quotient and remainder are converted back into signed numbers.
For quick access to the bits of the dividend, the dividend is first stored in the quotient flipflops and
then replaced by the upcoming quotient bits through shift operations.
The latency of the module can be configured by generics independently from the width of the operands.
The VHDL version of the module has 2 architectures: One which implements the non restoring division algorithm and a second which uses the VHDL division operators "/" and "rem".

This means, the module is configurable by generics in order

• to fulfill any requirements regarding the number of bits of the operands and
• to fulfill any requirements regarding its latency.

But of course there is no guarantee that timing closure can be reached with the selected values
for the generics, as the timing depends on the technology which is used at synthesis.

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

Ports:

Port name	Direction	Description
res_i	input	asynchronous reset input, 1-active Can be clamped to 0 when all latency generics have the value 0.
clk_i	input	clock input Can be clamped to 0 when all latency generics have the value 0.
start_i	input	This input expects an 1-active impulse of 1 clock cycle width in order to start the calculation. When all latency generics have the value 0 then back to back pulses can be used.
dividend_i(g_dividend_width-1:0)	input	Signed dividend (g_dividend_width is a generic). The input is latched at start=1 and can be changed afterwards.
divisor_i(g_divisor_width-1:0)	input	Signed divisor (g_divisor_width is a generic). The input must be stable during the calculation.
ready_o	output	1-active impulse of 1 clock cycle width, when the calculation is ready (When all latency generics have the value 0 it gets active in the same clock cycle in which start_i gets active).
quotient_o(g_dividend_width:0)	output	Signed quotient. Valid at ready_o=1 until the next start of a calculation or until the end of the next calculation if g_latency_negate is different from 0.
rem_o(g_divisor_width-1:0)	output	Signed remainder. Valid at ready_o=1 until the next start of a calculation or until the end of the next calculation if g_latency_negate is different from 0.

Generics/Parameters:

Generic/Parameter name	Minimum Value	Maximum Value	Description
g_dividend_width	2	none	Number of bits of the dividend The first bit represents the sign as the operands have to be coded in 2's complement.
g_divisor_width	2	none	Number of bits of the divisor The first bit represents the sign as the operands have to be coded in 2's complement.
g_latency_abs	0	1	Latency of the sub-module division_abs which removes the sign bit (in clock cycles) When g_latency_abs is 0, then the sub-module is a combinatorial design. When g_latency_abs is bigger than 1, it is handled as 1.
g_latency_division_unsigned	0	none	Latency of the sub-module division_unsigned which performs the division with unsigned operands (in clock cycles) When g_latency_division_unsigned is 0, then the sub-module is a combinatorial design.
g_latency_negate	0	1	Latency of the sub-module division_negate which fixes the sign of quotient or remainder (in clock cycles) When g_latency_negate is 0, then the sub-module is a combinatorial design. When g_latency_negate is bigger than 1, it is handled as 1.

The module "division" is a hierarchical module, which is built by these submodules:

Submodule name	Functionality
division_abs	The module division_abs calculates the absolut value of its input operand. It is instantiated twice, one instance for the dividend, the other for the divisor. The number of bits at its output is the same as at its input because only then the smallest possible negative number can be converted into a positive one.
division_unsigned	The division_unsigned module calculates quotient and remainder. Dividend and divisor must be unsigned. If your operands are already unsigned, you can use this module standalone. The module division_unsigned uses the sub-module division_unsigned_step which performs 1 step of the algorithm and is instantiated several times depending from the value at g_latency_division_unsigned. The module division_unsigned also uses the sub-module division_unsigned_control, which enables registers and activates the ready_o output.
division_negate	The division_negate module converts an unsigned number into a 2's complement number. It is instantiated twice, one instance for the quotient, one for the remainder.
division_unsigned_step	The division_unsigned_step observes the last determined quotient bit. If it is 1, then the last subtraction was allowed and the divisor will be subtracted again. If it is 0, then the last subtraction was too big and must be undone here. At the same time the new subtraction must also be executed. Both actions in sum result in adding the divisor instead of subtracting it (non restoring algorithm).
division_unsigned_control	The division_unsigned_control module enables the shift registers in which dividend bits and quotient bits are stored. The division_unsigned_control module activates the ready output of module division_unsigned if g_latency_division_unsigned is different from 0.

The VHDL version of the module division has 2 architectures named "struct" and "div_operator".

The architecture "struct" is based on the non restoring division algorithm of unsigned numbers whilst
the architecture "div_operator" uses the VHDL division- und rem- operator.

The architecture "div_operator" ignores all g_latency generics and calculates the result in 1 clock cycle.
Therefore it is not recommended to use this architecture in a productive design, as the non restoring division
algorithm causes very deep combinatorial pathes and will often prevent reaching timing closure.
This architecture was used to develop the testbench.

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

There is also no limitation for the generic g_latency_division_unsigned, but the smaller the value is chosen,
the harder it will get to reach timing closure.

The optimal value for g_latency_division_unsigned is equal to g_dividend_width.
Then in 1 clock cycle 1 bit of the dividend is consumed.
(When the incoming dividend and divisor are converted to unsigned numbers, their number of bits is increased by one,
in order to be able to convert the smallest negative number into a positive one.
Compared to the module "division_signed", which works directly with signed numbers, therefore one bit more has to be worked on.)

If g_latency_division_unsigned is smaller than g_dividend_width, then more than 1 bit of the dividend must be processed in 1 clock cycle.
This makes reaching timing closure more difficult.

If g_latency_division_unsigned is smaller than g_dividend_width and g_dividend_width cannot be divided by g_latency_division_unsigned
without a remainder, then leading dividend bits (with value 0) are internally added until the remainder has the value 0.

If g_latency_division_unsigned is bigger than g_dividend_width, then also additional dividend bits (with value 0) are added until
the extended width of the dividend is equal to g_latency_division_unsigned.

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

• hdl_editor_designs.zip

All module VHDL-files of the module "division" (Number of downloads = 84 ).
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 "division" (Number of downloads = 245 ).
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 "division".
Then you must replace "M:/gesicherte Daten/Programmieren/VHDL/division" 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 except division_unsigned_control,
for which the HDL must be generated by HDL-FSM-Editor.
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.1 (18.10.2024):

• When configured with g_latency_division_unsigned=1, a not needed timing path was left in the design, which is now broken.

06.06.2024:
A misunderstanding regarding the name of the division algorithm was found and fixed:
Instead of "restoring division" the correct name of the algorithm is "non restoring division".

Version 1.0 (07.05.2024):

• Initial version

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

• hdl_editor_designs_verilog.zip

All module Verilog-files of the module "division" (Number of downloads = 202 ).
These files were generated by HDL-SCHEM-Editor and HDL-FSM-Editor:

• Verilog_designs.zip

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

• Verilog_testbenches.zip

Relocation hints:

You should extract all archives into a folder named "division".
Then you must replace "M:/gesicherte Daten/Programmieren/Verilog/division" 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 except division_unsigned_control,
for which the HDL must be generated by HDL-FSM-Editor.
Of course there is only need for generating HDL, if you change something at the modules, because you can find the HDL in Verilog_designs.zip and Verilog_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.1 (18.10.2024):

• When configured with g_latency_division_unsigned=1, a not needed timing path was left in the design, which is now broken.

06.06.2024:
A misunderstanding regarding the name of the division algorithm was found and fixed:
Instead of "restoring division" the correct name of the algorithm is "non restoring division".

Version 1.0 (07.05.2024):

• Initial version

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