Basic Binary Division: The Algorithm and the VHDL Code - LEKULE

Breaking

21 May 2018

Basic Binary Division: The Algorithm and the VHDL Code

This article will review a basic algorithm for binary division.
Based on the basic algorithm for binary division we'll discuss in this article, we’ll derive a block diagram for the circuit implementation of binary division. We’ll then look at the ASMD (Algorithmic State Machine with a Data path) chart and the VHDL code of this binary divider.

Resources

Consider checking out related articles I've published in the past that may help you better understand this subject:

The Paper-and-Pencil Approach for Binary Division

To begin, consider dividing 11000101 by 1010.
Just as in decimal division, we can compare the four most significant bits of the dividend (i.e., 1100) with the divisor to find the first digit of the quotient. We are working with binary numbers, so the digits of the quotient can be either zero or one.
Since 1100 is greater than 1010, the first digit of the quotient will be one. The obtained digit must be multiplied by the divisor and the result must be subtracted from the dividend. Hence, we have



Now, we should write the next bit of the dividend (shown in red) to the right of the difference and continue the procedure just as we do in a decimal division. Hence, we obtain



The above example shows the decimal equivalent of the parameters as well as the letters used to represent them. We can verify the calculations by evaluating

and that
.
To get a better insight into the implementation of the division algorithm, we rewrite the above example as:



First, the divisor is subtracted from the four most significant bits of the dividend. The result of this subtraction, i.e. 0010, is shown in blue.
We can replace the four MSBs of the dividend with 0010 and obtain

. The four LSBs of
, which are the same as the four LSBs of the dividend, are shown in red. Note that we no longer need the original dividend and we can replace it with
. From an implementation point of view, this means that we can use the register which was originally storing the value of the dividend to store
.     
For the second subtraction, the divisor is shifted to the right by one bit. After subtraction, we obtain

. Again, the bits obtained from subtraction are shown in blue and the unaltered bits of
are shown in red. We can now update the dividend register with
.
This procedure goes on until the final subtraction in which the LSB of the shifted divisor is aligned with the LSB of the dividend. After this final subtraction, the remainder will be less than the divisor.
Note that, as we proceed with the algorithm, the high order bits of the

terms become zero (in this article, we’ll use
to refer to the
terms where
and
). This suggests that some bit positions of the dividend register will be no longer required. In the next section, we’ll see which bit positions are redundant. In the above example, the bit positions that can be discarded are underscored.

How to Implement the Division Algorithm?

As you can see from the above example, the division algorithm repeatedly subtracts the divisor (multiplied by one or zero) from appropriate bits of the dividend. Therefore, subtraction and shift operations are the two basic operations to implement the division algorithm.
After each subtraction, the divisor (multiplied by one or zero) is shifted to the right by one bit relative to the dividend. For the circuit implementation, we will shift the dividend to the left rather than shifting the divisor to the right (you can check that the latter requires more registers).
Besides, the numerical example shows that, as we proceed with the algorithm, some significant bits of the

terms are no longer required and can be discarded. Which bit positions are we allowed to discard?
Obviously, to perform the subtraction, the bit position of the

term right above the MSB of the divisor is required. For example, if we consider an arbitrary subtraction of the division algorithm as shown in Figure 1, the bit position denoted by
is clearly required. What about the higher order bits of the
term?


Figure 1

In Figure 1, the result of the subtraction is shown in blue and the bits of the difference that are the same as the

term are shown in red. Similar to the decimal division, the difference (
) is less than the divisor (
). Hence, we have



This means that

can be non-zero but all the bits to the left of
are zero. Therefore, in each subtraction, we only need one extra bit of the
term to the left of the divisor’s MSB. In the example of the previous section, the bit positions that can be discarded are underscored. This suggests that, as we proceed with the algorithm, we can use a smaller and smaller register to store the
terms. Usually, the vacated locations of this register are used to store the quotient bits. This will be discussed in a minute.  
A simplified block diagram for dividing an eight-bit number by a four-bit number is shown in Figure 2. The nine-bit register,

, stores the value of the dividend and the four-bit register,
, is used to store the divisor.
is the extra bit which will be used to store the bit of the
term to the left of the divisor’s MSB. At the beginning of the algorithm, this bit is set to zero.


Figure 2

Proceeding with the algorithm, the content of the Z register will be updated (with subtraction result) and shifted to the left. After each shift operation, the LSB of the Z register will be empty. This empty memory element will be used to store the quotient bit just obtained.
Just like the paper and pencil approach, we can compare

with
and decide whether the quotient bit must be zero or one. This is done by the “subtractor and comparator” block of Figure 2. When
, the “comp” signal will be logic high and the “control” unit will store the quotient bit, which is one, in the LSB of the Z register. When
, the obtained quotient bit will be zero and the LSB of the Z register will be zero.
Besides, the “control” unit must decide whether the five MSBs of the Z register needs to be updated or not. The “comp” signal can be used to make this decision as well. Based on our numerical example, we know that, when


, the five MSBs of the Z register must be updated with the difference
. When

, no update is required.

As discussed before, we will shift the content of the Z register to the left rather than shifting the divisor to the right.

Avoiding Overflow

During the last subtraction of the algorithm, the LSB of the dividend will be above the LSB of the divisor (see the 5th subtraction of the numerical example). This means that the value which was loaded to

at the beginning of the algorithm will be at
at the end of the algorithm. In other words, with the implementation of Figure 2, the division algorithm will involve a total of four shifts. We know that the memory locations vacated from these shifts will be used to store the quotient bits. Hence, the quotient must be less than or equal to
. Considering the equation
, we have



Hence,

. Since
is a positive number,
must be greater than
. In other words, at the beginning of the algorithm, we must have
, otherwise, the quotient will be greater than
and we cannot represent it in the vacated locations of the Z register.
As discussed above, the total number of shifts are known for the division algorithm. Therefore, we can use a counter to count the number of shifts and determine when the algorithm is finished. This counter will be reset to zero at the beginning of the algorithm.

The Division Algorithm

With the block diagram of Figure 2, we need to perform the following operations repeatedly:
  1. Load the dividend and the divisor to the Z and D registers, respectively. Reset
  • to zero. Besides, set the value of the iteration counter to zero.
  • If
  • , go to step 3 otherwise set a flag to indicate the overflow condition and end the algorithm.
  • Shift the Z register to the left by one bit. The shift operation will vacate the LSB of the Z register. This empty memory location will be used to store the quotient bit obtained in the next step.
  • Compare
  • with

    (a) If

    , set the LSB of the Z register to one and update the five MSBs of the Z register with the difference
    .
    (b) If

    1. , set the LSB of the Z register to zero and keep the five MSBs of the Z register unaltered.​
    2. Increase the value of the counter by one. If the counter is equal to four, end the algorithm otherwise go to step 3.

    The ASMD Chart and the VHDL Code

    Based on these steps, we can derive the ASMD chart of a 16-bit by 8-bit division as shown in Figure 3.


    Figure 3

    In this diagram, “start” is an input which tells the system to start the algorithm. When the calculations are finished, the “ready” output will be set to logic high to indicate the end of the algorithm. When facing an overflow, the “ovfl” output will go to high.

    The “idle” state loads the z_reg and d_reg registers with the dividend (m) and the divisor (n) inputs, respectively. The iteration counter (i_reg) is also initialized in this state. The overflow condition will be checked and the next state will be chosen accordingly.

    The “shift” state shifts the content of the z_reg register to the left by one bit. This will insert a zero to the right of the z_reg content. However, the value of this bit can change during the next phase of the algorithm.

    The “op” state compares the registers. If the nine MSBs of the z_reg are greater than or equal to the content of d_reg, the LSB of the z_reg will be set to one and the nine MSBs of the z_reg will be updated with the subtraction result which is represented by “sub”. If the nine MSBs of the z_reg are less than the content of d_ref, we don’t have to change z_reg. Then the iteration counter will increase by one and we’ll check the number of shifts. If we have eight shifts the algorithm is finished and the next state is “idle”. If the number of iterations are less than eight, we should go back to the “shift” state and proceed with the rest of the algorithm.

    To read more about deriving the ASMD chart, please see these two articles: How to Write the VHDL Description of a Simple Algorithm: The Data Path and How to Write the VHDL Description of a Simple Algorithm: The Control Path.

    Now, having the ASMD chart, we can write the VHDL code of the algorithm:

                        1 library IEEE;
    2 use IEEE.STD_LOGIC_1164.ALL;
    3 use IEEE. NUMERIC_STD.ALL;
    
    4 entity Divider is
    5     Port (clk, reset : in STD_LOGIC;
    6   start : in STD_LOGIC;
    7   m : in  STD_LOGIC_VECTOR (15 downto 0);     -- Input for dividend
    8            n : in  STD_LOGIC_VECTOR (7 downto 0);    -- Input for divisor 
    9            quotient : out  STD_LOGIC_VECTOR (7 downto 0);    -- Output for quotient
    10          remainder : out  STD_LOGIC_VECTOR (7 downto 0);    -- Output for remainder
    11 ready, ovfl : out STD_LOGIC);    -- Indicates end of algorithm and overflow condition
    12 end Divider;
    
    13 architecture Behavioral of Divider is
       
    14            -- Type for the FSM states
    15   type state_type is (idle, shift, op);     
      
    16 -- Inputs/outputs of the state register and the z, d, and i registers
    
    17 signal state_reg, state_next : state_type;   
    18   signal z_reg, z_next : unsigned(16 downto 0);   
    19   signal d_reg, d_next : unsigned(7 downto 0);
    20   signal i_reg, i_next : unsigned(3 downto 0);
    
    21 -- The subtraction output 
    22 signal sub : unsigned(8 downto 0);
         
    23 begin
    24   --control path: registers of the FSM
    25   process(clk, reset)
    26   begin
    27  if (reset='1') then
    28   state_reg <= idle;
    29  elsif (clk'event and clk='1') then
    30   state_reg <= state_next;
    31  end if;
    32 end process;
      
    33 --control path: the logic that determines the next state of the FSM (this part of
    34 --the code is written based on the green hexagons of Figure 3)
    35 process(state_reg, start, m, n, i_next)
    36 begin
    37  case state_reg is
    38   when idle =>
    39    if ( start='1' ) then
    40     if ( m(15 downto 8) < n ) then
    41     state_next <= shift;
    42     else
    43     state_next <= idle;
    44     end if;
    45    else
    46     state_next <= idle;
    47    end if;
           
    48   when shift =>
    49    state_next <= op;
         
    50   when op =>
    51    if ( i_next = "1000" ) then
    52     state_next <= idle;
    53    else
    54     state_next <= shift;
    55    end if;
           
    56   end case;
    57  end process;
         
    58 --control path: output logic
    59 ready <= '1' when state_reg=idle else
    60      '0';
    61 ovfl <= '1' when ( state_reg=idle and ( m(15 downto 8) >= n ) ) else
    62  '0';
            
    63 --control path: registers of the counter used to count the iterations
    64 process(clk, reset)
    65 begin
    66  if (reset='1') then
    67   i_reg <= ( others=>'0' );
    68  elsif (clk'event and clk='1') then
    69   i_reg <= i_next;
    70  end if;
    71 end process;
       
    72 --control path: the logic for the iteration counter
    73 process(state_reg, i_reg)
    74 begin
    75  case state_reg is
    76   when idle =>
    77    i_next <= (others => '0');
    78        
    79   when shift =>
    80    i_next <= i_reg;
    81    
    82   when op =>
    83    i_next <= i_reg + 1;
    84  end case;
    85 end process;
         
       
       
    86 --data path: the registers used in the data path
    87 process(clk, reset)
    88 begin
    89  if ( reset='1' ) then
    90   z_reg <= (others => '0');
    91   d_reg <= (others => '0');
    92  elsif ( clk'event and clk='1' ) then
    93   z_reg <= z_next;
    94   d_reg <= d_next;
    95  end if;
    96 end process;
       
    97 --data path: the multiplexers of the data path (written based on the register
    98 --assignments that take place in different states of the ASMD)
    99 process( state_reg, m, n, z_reg, d_reg, sub)
    100 begin
    101  d_next <= unsigned(n);
    102  case state_reg is
    103   when idle =>
    104    z_next <= unsigned( '0' & m );
    105    
    106   when shift =>
    107    z_next <= z_reg(15 downto 0) & '0';
        
    108   when op =>
    109    if ( z_reg(16 downto 8) < ('0' & d_reg ) ) then
    110     z_next <= z_reg;
    111    else
    112     z_next <=  sub(8 downto 0) & z_reg(7 downto 1) & '1';
    113    end if;
    114  end case;
    115 end process;
       
    116 --data path: functional units
    117 sub <= ( z_reg(16 downto 8) - unsigned('0' & n) );
       
    118 --data path: output
    119 quotient <= std_logic_vector( z_reg(7 downto 0) );
    120 remainder <= std_logic_vector( z_reg(15 downto 8) );
        
    121 end Behavioral;
    
                      

    An ISE simulation for the above code is shown in Figure 4.


    Figure 4

    You can verify that when the “ready” output goes to logic high, we have

    .

    Conclusion


    This article examined a basic algorithm for binary division. We derived a block diagram for the circuit implementation of the binary division. We also examined the ASMD chart and the VHDL code of this binary divider.

    No comments: