VHDL optimal division

[VHDLStarter]

Hey there, I am having problems modifying my basic division code to an optimal solution using state machines. The simple state machine design is basically to subtract at each clock cycle. I have an example of it below:

library IEEE;
   use IEEE.std_logic_1164.all;
   use ieee.numeric_std.all;
   --use ieee.std_logic_arith.all;
   use Ieee.std_logic_unsigned.all;

entity div is
  Port (dividend, divisor : in std_logic_vector(9 downto 0);
        RSTb, CLK : in std_logic;
        quotient, remainder : out std_logic_vector(9 downto 0));
end div;

architecture div_arch of div is
  
  type STATE_TYPE is (s0, s1, s2);

  signal CURRENT_STATE, NEXT_STATE: STATE_TYPE;
  signal ONE : unsigned (9 downto 0):="0000000001";
  signal next_dividend, current_dividend, next_remainder, next_quotient, current_quotient : std_logic_vector (9 downto 0):="0000000000";
  
begin
    
-- Process to hold combinational logic
 process(clk,rstb,dividend,divisor,next_remainder,next_quotient,Next_state,next_dividend, CURRENT_STATE)
 begin
 

case current_state is
when s0 =>  if(unsigned(current_dividend) > unsigned(divisor)) then
              next_state <= s1;
            elsif(unsigned(current_dividend) = unsigned(divisor))then
              next_remainder <= "0000000000";
              next_state <= s0; 
            elsif (unsigned(current_dividend) < unsigned(divisor))then
              next_remainder <= "0000000000"; 
              next_state <= s0;             
            else
             next_state <= s0;
            end if;
            current_dividend<=dividend;
            next_dividend <= dividend;  
            next_quotient <= "0000000000";
            current_quotient <= "0000000000";
            next_remainder <= "0000000000"; 
               
when s1 =>  if(unsigned(current_dividend) >= unsigned(divisor)) then
              next_state <= s1;

              
                  next_dividend <= std_logic_vector(unsigned(current_dividend) - unsigned(divisor)); 
                  next_quotient <= std_logic_vector(unsigned(current_quotient) + unsigned(one));
                 
            else
             next_remainder <= current_dividend;
              next_state <= s2;
                 
            end if;

when s2 =>  --dead state to wait for reset. Not really needed.
               
  end case; 

    --asynchronous, active low    
    if(rstb = '0') then
      current_state <= s0;
      quotient <= "0000000000"; 
      remainder <= "0000000000"; 
      current_dividend <= dividend;
      next_dividend <= dividend;
    elsif(clk'event and clk = '1') then
      current_state <= next_state;
      current_dividend<=next_dividend;      
      current_quotient <= next_quotient;
      quotient <= current_quotient;  
      remainder <= next_remainder;
    end if;  
    
end process;        
end div_arch;



configuration div_arch_cfg of div is
  for div_arch
  end for;
end div_arch_cfg;

The above works just fine. I posted it to give you an idea of what the previous solution was. However, the optimal solution revolves around either a series of if statements or for loops to compare the dividend and the divisor. This is where I start to get confused.

My current idea is to follow this method with some modifications for binary:

In practice, when dividing a large number by a much smaller number, you would shift the smaller number one or more places to the left by setting it up on the dials to the left of where it would normally be, leaving the right-hand dials set to zero. The degree to which you shift it would be dictated by common sense and mental arithmetic - if you can't subtract it even once from the other number, then you have gone too far! You would then subtract this shifted number as many times as possible to obtain the first digit of the result, reset all your dials to shift it back to the right, repeatedly subtract again to find the next digit, and continue this process until you reach your original number again and can no longer subtract even that.

Using our example of 128÷4, you would end up doing this:

Shift 4 one place to the left - it becomes 40.
Shift 4 another place to the left - it becomes 400. This is bigger than 128, so we have gone too far. We shall start with the previous result, which was 40. So:
128 - 40 = 88 (turning the handle once)
88 - 40 = 48 (turning it twice)
48 - 40 = 8 (turning it three times)
We can no longer subtract 40, so we have now found the first digit of the answer to be 3.
Now we shift our number back to the right so that it becomes 4 again, and once more start counting turns of the handle.
8 - 4 = 4 (turning the handle once)
4 - 4 = 0 (turning it twice)

We can no longer subtract 4 (our original number), so we have found the last digit of the answer to be 2. In other words, the answer is 32, the result we got before - but we have had to wind the handle round only five times in order to obtain it, not thirty-two times!

About Assembly Language - Division

You have to shift it over in decimal or basically multiply by 10 on the start. I tried to use * and "and" to multiply, but that did not work. I managed to get around this by shifting the bits over by 3 then adding the divisor * 2.

ex:

dividend/divisor = divisor shift left 3 times + divisior *2 = divisor * 10

4/2 -> divisor in binary = 10 -> 10000 -> (10000 + 10 +10) = 10100 = 20

As you can see I successfully multiplied the divisor by 10 using this method. However, after I do that I need to judge to see if I need to go back to the previous version of the divisor or not. After the value of the divisor is determined I would follow the steps in the above description with two separate counters. After each counter is finished I would have to combine the numbers. I could do this with an if statement determining if the second counter is greater than a number.

EX. if counter is greater than a certain value then shift a certain amount of times and add to first counter, if it is less than just shift x amount of times and add to first counter, etc. That is my reasoning behind combining the two different counts in the above description.

Unfortunately, I am having a lot of trouble implementing my logic for the optimal divison. Below is code that isn't finished with a lot of comments (WIP):

library IEEE;
   use IEEE.std_logic_1164.all;
   use ieee.numeric_std.all;
   --use ieee.std_logic_arith.all;
   use Ieee.std_logic_unsigned.all;

entity div is
  Port (dividend, divisor : in std_logic_vector(9 downto 0);
        RSTb, CLK : in std_logic;
        quotient, remainder : out std_logic_vector(9 downto 0));
end div;

architecture div_arch of div is
  
  type STATE_TYPE is (s0, s1, s2);

  signal CURRENT_STATE, NEXT_STATE: STATE_TYPE;
  signal ONE : unsigned (9 downto 0):="0000000001";
  signal TWO : unsigned (9 downto 0):="0000000010";
  signal current_divisor,storage,count,count2,next_divisor,next_dividend, current_dividend, next_remainder, next_quotient, current_quotient : std_logic_vector (9 downto 0):="0000000000";
  signal shiftC : integer range 0 to 1024 := 0; 
  --signal onec :  std_logic_vector (9 downto 0):="0000000000";
  signal temp,temp2,temp3 : std_logic_vector (9 downto 0);

  --signal tf : boolean := true; 
  
--function  
--function shiftL (divisor, i : std_logic_vector(0 downto 9)) return std_logic_vector is
 --  result : std_logic_vector(0 downto 9);
 -- begin
  --  result <= divisor * i;
  --return(result);
--end shiftL;
--end function  
 --procedure shiftL (divisor, i : std_logic_vector(0 downto 9)) is
    --begin 
         
 -- end procedures shiftL ;     
  
begin
    
-- Process to hold combinational logic
 process(clk,rstb,dividend,divisor,next_remainder,next_quotient,Next_state,next_dividend, CURRENT_STATE)
 begin
 

case current_state is
when s0 =>  if(unsigned(current_dividend) > unsigned(divisor)) then
              next_state <= s1;
            elsif(unsigned(current_dividend) = unsigned(divisor))then
              next_remainder <= "0000000000";
              next_state <= s0; 
            elsif (unsigned(current_dividend) < unsigned(divisor))then
              next_remainder <= "0000000000"; 
              next_state <= s0;             
            else
             next_state <= s0;
            end if;
            current_dividend<=dividend;
            next_dividend <= dividend;
            current_divisor<=divisor;
            next_divisor <= divisor;    
            next_quotient <= "0000000000";
            current_quotient <= "0000000000";
            next_remainder <= "0000000000"; 
            temp <= "0000000000"; 
            temp2 <= "0000000000";
            temp3 <= next_divisor;
               
when s1 =>    
              if(unsigned(dividend) >= unsigned(current_divisor)) then
              next_state <= s1;
              
              
              --starting calc to shift
               
              
              for i in 0 to 9 loop
                if(unsigned(dividend) >= unsigned(temp)) then 
                  
                  --temp3 <= next_divisor;
                  next_divisor <= std_logic_vector(unsigned(current_divisor) sll 3);
                  temp2 <= std_logic_vector(unsigned(divisor) + unsigned(divisor));
                  temp <= std_logic_vector(unsigned(next_divisor) + unsigned(temp2));
                  --next_divisor <= "0000000000"; 
                  
                else
                  exit;
                      
                    end if;
                  end loop;
                    --we need to go back one mutliple if we go over
                    --next_divisor <= temp; 
                    
                    --next_divisor <= temp; 
                    --next_divisor <= std_logic_vector(unsigned(current_divisor) srl 3);
                    --temp2 <= std_logic_vector(unsigned(divisor) - unsigned(divisor));
                   -- temp <= std_logic_vector(unsigned(next_divisor) - unsigned(temp2));
                     
 
              
             
             
             
             if(unsigned(dividend) >= unsigned(current_divisor)) then 

            end if;
             
             --storage signal
             storage <= current_dividend;
             
             
             
             
              --wind up
              --for i in 0 to 9 loop
             -- if(storage < current_divisor) then
              --  exit;
             -- end if;
             
             -- storage <= storage - current_divisor;
             --count <= std_logic_vector(unsigned(count) + 1);
           -- end loop;

 
            ----wind down
            --for i in 0 to 9 loop
             -- if(storage  < current_quotient) then
             --   exit;
             -- end if;
             
             --  storage <= storage - next_divisor;
            --   count2 <= std_logic_vector(unsigned(count2) + 1);
            --end loop;
               
               
                --if(unsigned(dividend) >= unsigned(current_divisor)) then                 
               --next_dividend <= std_logic_vector(unsigned(current_dividend) - unsigned(next_divisor)); 
                --next_quotient <= std_logic_vector(unsigned(current_quotient) + unsigned(one));
                --end if;
              --end loop;
            
               
                 
            else
              --next_remainder <= current_dividend;
              --next_state <= s2;
              
              
           end if;

when s2 =>  --Dead state to wait for reset
               
  end case; 

    --asynchronous, active low    
    if(rstb = '0') then
      current_state <= s0;
      quotient <= "0000000000"; 
      remainder <= "0000000000";
      count <= "0000000000";
      count2 <= "0000000000";
      current_dividend <= dividend;
      next_dividend <= dividend;
      current_divisor<=divisor;
      next_divisor <= divisor;
      
    elsif(clk'event and clk = '1') then
      current_state <= next_state;
      current_dividend<=next_dividend;      
      current_quotient <= next_quotient;
      current_divisor <= next_divisor;
      quotient <= current_quotient;  
      remainder <= next_remainder;
    end if;  
    
end process;        
end div_arch;



configuration div_arch_cfg of div is
  for div_arch
  end for;
end div_arch_cfg;

Is there an easier way to do this? If not, can someone maybe help me get to the desired optimal level of division? Thank you.

 

[TrickyDicky]

as a first step, if you really want to stick with your async/sync coding style, I would stick it into separate processes (an async one and a sync one). YOur current coding style isnt really recommended.

Secondly - why not try using a single process and making everything synchronous?

Why are you storing everything as std_logic_vectors? whats wrong with sticking with unsigned? It saves you having a type conversion on almost every line of code. This holds true for ports aswell - theres nothing wrong with using unsigned.

For loops are pretty bad in VHDL, especially in asynchronous logic. When a design is compiled the loop is unrolled to the worst case. I would only ever use them for parallel logic, not logic generation. From you're logic you're creating a chain of 10 comparators. But the main problem is that all of the signals inside the loop are signals. This means only the final assignments are given, which means the loop is not doing what you intended. You want to use variables instead of signals inside your loop.

So there are a lot of fundamental errors, and Im advising you do some major changes to your code, especially your coding style.

 

[VHDLStarter]

Thanks for the reply. This was an assignment. I forgot to mention that. The asynchronous reset was a specification. I will put it in a separate process. However, it also said to use (10 bit) unsigned quantities. In the past were were mostly using vectors so I thought we were suppose to use vectors again, but I was wrong. Thanks for pointing that out. As for the for loop, that is exactly what was happening to me. I will try to use variables like you said. Thank you so much for the feedback. That really helped.

 

[TrickyDicky]

THe asynchronous code Im talking about isnt the reset - its all the code inside the process thats not in either the clock section or async reset section.

VHDL should follow one of these code templates:


Registers with async reset:

process(clk, reset) --ONLY clock and reset in here
begin
  if reset = '1' then
    --async reset
  elsif rising_edge(clk) then
    --registers
  end if;
end process;

Asyncrhonous process

process(a,b,c) --ALL inputs here
begin
  output <= some combination of a/b/c
end process

You should never mix the two, like you have.

 

[std_match]

This was an assignment. I forgot to mention that. The asynchronous reset was a specification. I will put it in a separate process. However, it also said to use (10 bit) unsigned quantities.

You are trying to do a decimal division and it is possible, but more complicated.
You linked to a document about assembly language division. Look at the "Binary division". That is much easier.
With binary division there is zero or one subtractions before you do the shifting, and the binary shifting is extremely simple.

 

[VHDLStarter]

You are trying to do a decimal division and it is possible, but more complicated.
You linked to a document about assembly language division. Look at the "Binary division". That is much easier.
With binary division there is zero or one subtractions before you do the shifting, and the binary shifting is extremely simple.

I am okay with binary, it's just I had a little trouble understanding the steps involved:

We shift 10 as far as we can (two places) to the left until it becomes %101000 and subtract this from %110010 to get the first digit.
%110010- %101000 = %1010 (First digit is 1)
Now we shift %101000 back one place to the right and try to subtract %10100 from what remains of the 25 we started off with.
%1010 - %10100 (Next digit is 0 - it 'won't go'!)
Shift right, get %1010 and try again:
%1010 - %1010 = %0 (Successful subtraction - next digit is 1)

Can you please elaborate on these steps? For example, 73/4 or 1001001 / 100. How would the answer be generated as well as the remainder? Thanks again.

THe asynchronous code Im talking about isnt the reset - its all the code inside the process thats not in either the clock section or async reset section.

You should never mix the two, like you have.

Alright, thanks for the information. I will make it in a separate process.

 

[std_match]

Can you please elaborate on these steps? For example, 73/4 or 1001001 / 100. How would the answer be generated as well as the remainder? Thanks again.

Shift the divisor so the leftmost '1' is aligned with the leftmost '1' of the dividend,
and remember the shift length:

1001001
1000000 (shifted left 4 bits)

Subtract if possible, and shift. Generate a '1' in the result if the subtraction
was possible, otherwise '0'. Repeat:

 1001001
-1000000
========
 0001001 (subtraction, result = 1)
-0100000 (shifted 1 bit right)
========
 0001001 (no subtraction, add '0' to the result -> 10)
-0010000 (shifted)
========
 0001001 (no subtraction, add '0' to the result -> 100)
-0001000 (shifted)
========
 0000001 (subtraction, add '1' to the result -> 1001)
-0000100 (shifted)
========
 0000001 (no subtraction, add '0' to the result -> 10010)

The dividend is now shifted back to the original position.
You have the integer result "10010" = 18
and the remainder "0000001" = 1

You can now continue to shift the dividend to the right to calculate the fraction bits,
or be satisfied with the remainder.

 

[VHDLStarter]

Thanks so much. That really cleared things up. The only thing I am still confused about is the initial shift. How would I compare the numbers bit by bit to know how many times to shift it? Also, I am interested in the fraction portion for the remainder. The answer should be 18.25. How would I shift to get the .25 part? I am also confused about what would happen if you had a fraction from the start like 3/4 or 11 / 100. Thank you so much for the help so far. The binary method seems like it will be a lot easier like you suggested. I just need help ironing out some of those details. Thanks again.