Synthesis of Arithmetic Circuits: FPGA, ASIC and Embedded Systems

13.1 NATURAL NUMBERS

Let Y be an n-bit positive number and X a natural number belonging to the range 0 ≤ X < Y, so that it can also be represented as an n-bit number. The circuit corresponding to the basic division algorithm 6.1 (with q(i) substituted by q(p − i) in order that the least significant bit of q be q(0)) is an iterative circuit made up of p cells, which implement the division_step procedure (Figure 13.1). The divider structure is shown in Figure 13.2 (combinational and sequential implementations). In the binary case the division_step block (base-2 division step, Algorithm 6.2) consists of an (n + 1)-bit subtractor and an n-bit 2-to-1 multiplexer (Figure 13.1). The corresponding cost C(n, p) and computation time T(n, p) are equal to

Figure 13.1 Basic cell of a binary restoring divider.

and

Example 13.1 (Complete VHDL source code available.) Generate a generic n-bits base-2 restoring divider. The division step of Figure 13.1 is:

entity restoring_cell is port ( a_by_2: in STD_LOGIC_VECTOR (N downto 0); b: in STD_LOGIC_VECTOR (N-1 downto 0); q: out STD_LOGIC; r: out STD_LOGIC_VECTOR (N-1 downto 0) ); end restoring_cell; architecture cel_arch of restoring_cell is signal subst: ...