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.

for the generics, as the timing depends on the technology which is used at synthesis.

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

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_dividend_width: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. |

Generic/Paramter 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 |

division_unsigned |
The division_unsigned module calculates quotient and remainder.
The module division_unsigned uses the sub-module division_unsigned_step which performs 1 step of the algorithm 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. |

division_unsigned_control |
The division_unsigned_control module enables the shift registers in which dividend bits and quotient bits are stored. |

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 =
85 ).

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:

All module VHDL-files of the module "division" (Number of downloads =
21 ).

These files were generated by HDL-SCHEM-Editor and HDL-FSM-Editor:

All testbench VHDL-files of the testbench of the module "division" (Number of downloads =
76 ).

These files were generated by HDL-SCHEM-Editor and HDL-FSM-Editor:

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".

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 =
30 ).

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:

All module Verilog-files of the module "division" (Number of downloads =
84 ).

These files were generated by HDL-SCHEM-Editor and HDL-FSM-Editor:

All testbench Verilog-files of the module "division" (Number of downloads =
81 ).

These files were generated by HDL-SCHEM-Editor and HDL-FSM-Editor:

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".

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".