a VHDL implementation of a non restoring division algorithm directly on signed numbers

The module "division_signed" (see symbol)
calculates the signed quotient and the signed remainder of a dividend and a divisor.

The calculation is done without converting the dividend and the divisor into unsigned numbers.

This is an advantage compared to the module "division" available at this website,

because no conversion hardware and no conversion time (1 clock cycle) is needed for the inputs and

no additional databit (introduced by the conversion) must be handled by the division algorithm (which

would increase division time by 1 clock cycle, if 1 databit is handled in 1 clock cycle).

So the module "division_signed" can be faster by 2 clock cycles compared to the module "division".

The number of bits of dividend and divisor are configured by generics.

Dividend, divisor, quotient and remainder are numbers in 2's complement format.

The quotient is first not calculated as a binary number but as a number with bit values +1 or -1.

After the division the quotient is converted into a 2's complement number.

Both quotient and remainder are fixed in some cases.

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.

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_signed" 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_convert 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_convert 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_division | 0 | none | Latency of the division (in clock cycles) When g_latency_division is 0, then the division is implemented as a combinatorial design. |

g_latency_convert | 0 | 1 | Latency of the sub-module division_signed_convert which converts the quotient into binary format and
fixes quotient and remainder in some cases (in clock cycles). When g_latency_convert is 0, then the sub-module is a combinatorial design. When g_latency_convert 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_signed_step |
The division_signed_step compares the sign of last partial remainder (or the dividend in the first step) and the divisor.
If they are equal, then the divisor will be subtracted and a quotient bits "+1" will be noted. |

division_signed_convert |
The division_signed_convert module converts an number with bit-values +1 or -1 into a 2's complement number.
The division_signed_convert module fixes quotient and remainder in some cases. |

division_signed_control |
The division_signed_control module enables the shift registers in which dividend bits and quotient bits are stored. The division_signed_control module activates a ready signal for the division if g_latency_division is different from 0. |

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_signed is used.

There is also no limitation for the generic g_latency_division, but the smaller the value is chosen,

the harder it will get to reach timing closure.

The optimal value for g_latency_division is equal to g_dividend_width-1.

Then in 1 clock cycle 1 bit of the dividend is consumed.

(Compared to the module "division" one bit less has to be worked on, as the sign bit is not converted into a data bit.)

If g_latency_division is smaller than g_dividend_width-1, 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 is smaller than g_dividend_width-1 and g_dividend_width-1 cannot be divided by g_latency_division

without a remainder, then leading dividend bits (with the same value as the sign bit) are internally added until the remainder has the value 0.

If g_latency_division is bigger than g_dividend_width-1, then also additional dividend bits (with the same value as the sign bit) are added until

the extended width of the dividend is equal to g_latency_division+1.

Source code for HDL-SCHEM-Editor and HDL-FSM-Editor of the VHDL-module "division_signed" and its testbench (Number of downloads =
83 ).

With these files the schematics and the state-diagram of module division_signed 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_signed" (Number of downloads =
46 ).

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

All testbench VHDL-files of the testbench of the module "division_signed" (Number of downloads =
39 ).

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

You should extract all archives into a folder named "division_signed".

Then you must replace "M:/gesicherte Daten/Programmieren/VHDL/division_signed" 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_signed_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".

Version 1.0 (26.06.2024):

- Initial version

If you detect any bugs or have any questions,

please send a mail to "matthias.schweikart@gmx.de".