+ Post New Thread
Results 1 to 4 of 4
  1. #1
    Newbie level 1
    Points: 17, Level: 1

    Join Date
    Jun 2017
    Posts
    1
    Helped
    0 / 0
    Points
    17
    Level
    1

    binary dividing: restoring method

    Hello,

    i have to understand how the restoring method works and found a very helpful source code:

    Code:
    ----------------------------------------------------------------------------
    -- restoring.vhd
    --
    -- Implements a sequential version of restoring division algorithm
    -- section 3.2 Loop-unrolling and digit-serial processing
    -- x = xn-1 xn-2 ... x0: natural
    -- y = yn-1 yn-2 ... y0: natural
    -- condition: x < y
    -- quotient q =  0.q1 ... qp: non-negative fractional
    -- remainder r = rn-1 rn-2 ... r0: natural
    -- x = (0.q1 q2 ... qp)·y + (r/y)·2-p with r < y
    --
    ----------------------------------------------------------------------------
    
    LIBRARY IEEE;
    USE IEEE.STD_LOGIC_1164.ALL;
    USE IEEE.STD_LOGIC_ARITH.ALL;
    USE IEEE.STD_LOGIC_UNSIGNED.ALL;
    ENTITY restoring IS
      GENERIC(n: NATURAL:=8; p: NATURAL:= 6);
    PORT(
      x, y: IN STD_LOGIC_VECTOR(n-1 DOWNTO 0);
      clk, reset, start:IN STD_LOGIC;
      quotient: OUT STD_LOGIC_VECTOR(1 TO p);
      remainder: OUT STD_LOGIC_VECTOR(n-1 DOWNTO 0);
      done: OUT STD_LOGIC
    );
    END restoring;
    
    ARCHITECTURE circuit OF restoring IS
      SIGNAL r, next_r: STD_LOGIC_VECTOR(n-1 DOWNTO 0);
      SIGNAL long_y, two_r, dif: STD_LOGIC_VECTOR(n DOWNTO 0);
      SIGNAL load, update: STD_LOGIC;
      SIGNAL q: STD_LOGIC_VECTOR(1 TO p);
      
      SUBTYPE index IS NATURAL RANGE 0 TO p-1;
      SIGNAL count: index;
      TYPE state IS RANGE 0 TO 3;
      SIGNAL current_state: state;
      
    BEGIN
      long_y <= '0'&y;
      two_r <= r&'0';
      dif <= two_r - long_y;
      WITH dif(n) SELECT next_r <= dif(n-1 DOWNTO 0) WHEN '0', two_r(n-1 DOWNTO 0) WHEN OTHERS;
    
      remainder_register: PROCESS(clk)
      BEGIN
        IF clk'EVENT AND clk = '1' THEN
          IF load = '1' THEN r <= x;
          ELSIF update = '1' THEN r <= next_r;
          END IF;  
        END IF;
      END PROCESS;
      remainder <= r;
    
      quotient_register: PROCESS(clk)
      BEGIN
        IF clk'EVENT AND clk = '1' THEN
          IF load = '1' THEN q <= (others => '0');
          ELSIF update = '1' THEN q <= q(2 TO p)&NOT(dif(n));
          END IF;  
        END IF;
      END PROCESS;
      quotient <= q;
    
      counter: PROCESS(clk)
      BEGIN
        IF clk'EVENT and clk = '1' THEN
          IF load = '1' THEN count <= 0; 
          ELSIF update = '1' THEN count <= (count+1) MOD p;
          END IF;
        END IF;
      END PROCESS;
    
      next_state: PROCESS(clk)
      BEGIN
        IF reset = '1' THEN current_state <= 0;
        ELSIF clk'EVENT AND clk = '1' THEN
          CASE current_state IS
            WHEN 0 => IF start = '0' THEN current_state <= 1; END IF;
            WHEN 1 => IF start = '1' THEN current_state <= 2; END IF;
            WHEN 2 => current_state <= 3;
            WHEN 3 => IF count = p-1 THEN current_state <= 0; END IF;
          END CASE;
        END IF;
      END PROCESS;
    
      output_function: PROCESS(clk, current_state)
      BEGIN
        CASE current_state IS
          WHEN 0 TO 1 => load <= '0'; update <= '0'; done <= '1';
          WHEN 2 => load <= '1'; update <= '0'; done <= '0';
          WHEN 3 => load <= '0'; update <= '1'; done <= '0';
        END CASE;
      END PROCESS;
      
    END circuit;
    Source: http://www.arithmetic-circuits.org/g...vhdl_codes.htm

    I started a simulation with modelsim, set the clock, set x and y.

    'quotient' have to hold the result, but it is "empty".

    Can anybody help me to run the simulation and make a division?

    Thanks

    •   Alt13th June 2017, 20:32

      advertising

        
       

  2. #2
    Super Moderator
    Points: 26,817, Level: 39
    ads-ee's Avatar
    Join Date
    Sep 2013
    Location
    USA
    Posts
    6,096
    Helped
    1495 / 1495
    Points
    26,817
    Level
    39

    Re: binary dividing: restoring method

    Did you set start to 1? You need that to kick off the FSM.

    Note, the output_function process should not have clk in the sensitivity list, that is a potential gotcha as synthesis ignores the sensitivity list (it only looks at the state) even though simulation will enter the process each time the clock toggles (both rising and falling). With all their PhDs and MS degrees you would think they would know that.



    •   Alt14th June 2017, 01:36

      advertising

        
       

  3. #3
    Advanced Member level 5
    Points: 33,920, Level: 44
    Achievements:
    7 years registered

    Join Date
    Jun 2010
    Posts
    6,209
    Helped
    1816 / 1816
    Points
    33,920
    Level
    44

    Re: binary dividing: restoring method

    Quote Originally Posted by ads-ee View Post
    Did you set start to 1? You need that to kick off the FSM.

    Note, the output_function process should not have clk in the sensitivity list, that is a potential gotcha as synthesis ignores the sensitivity list (it only looks at the state) even though simulation will enter the process each time the clock toggles (both rising and falling). With all their PhDs and MS degrees you would think they would know that.
    Its the problem with free code off the internet. Almost always written by hobbiests who dont really understand the language, or come anywhere near decent coding practice (and never document it).
    Also note - the "next_state" process is missing reset from it's sensitivity list too! luckily, they get away with it as the initial value for current_state is 0 anyway (and who uses integers for state machines? - are you deliberately avoiding all the synthesis optimisation?).


    To The OP: Why not share your testbench also?

    - - - Updated - - -

    I also note this beauty:

    count <= (count+1) MOD p

    Using a divider unnecessarily (potentially). Normal people would write:

    Code:
    if count = p-1 then 
      count = 0
    else 
      count <= count + 1;
    end if;



    •   Alt14th June 2017, 09:32

      advertising

        
       

  4. #4
    Super Moderator
    Points: 26,817, Level: 39
    ads-ee's Avatar
    Join Date
    Sep 2013
    Location
    USA
    Posts
    6,096
    Helped
    1495 / 1495
    Points
    26,817
    Level
    39

    Re: binary dividing: restoring method

    Quote Originally Posted by TrickyDicky View Post
    Its the problem with free code off the internet. Almost always written by hobbiests who dont really understand the language, or come anywhere near decent coding practice (and never document it).
    You must not have checked the site where this code came from (the site is written by a bunch of PhDs and MS degree holders in electrical engineering). I now understand why we see so many students with equally poor understanding of HDL languages and such poor coding practices.



--[[ ]]--