Forum Discussion

Altera_Forum's avatar
Altera_Forum
Icon for Honored Contributor rankHonored Contributor
17 years ago

state machine troubles

I am trying to code a multiplier using booths algorithim and it has to be a state machine. I'm pretty sure that I have booths coded correctly but I am running into some problems having the state switch in the process. I have 3 states and I think what is happening is that it has to end the process before it has the change in state assigned and is therefore not going through the program but I am not sure how to fix this. I cannot use any loops or := in my program. If you have any advice or examples that I can look at I would appreciate it.

Amy

8 Replies

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    17 years ago

    A state machine generally isn't supposed to perform more than one state transition per clock cycle. Implement booth algorithm as state machine involves a serial mutiplier in any case.

  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    17 years ago

    Amy, It sounds as if this is just a problem with the way you have written your state machine. Perhaps if you posted a skeleton of your code we could point you in the right direction.

    For complex state machines I tend to split my code into three parts, the state register, next state logic, and state output logic.

    Steve
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    17 years ago

    --- Quote Start ---

    WHEN RUN =>

    CASE P(1 DOWNTO 0) IS

    WHEN "00" =>

    WHEN "11" =>

    WHEN "01" =>

    P <= P + A;

    WHEN "10" =>

    P <= P + S;

    END CASE;

    P(0) <= P(1);

    P(1) <= P(2);

    P(2) <= P(3);

    P(3) <= P(4);

    P(4) <= P(5);

    P(5) <= P(6);

    P(6) <= P(7);

    P(7) <= P(8);

    P(8) <= P(9);

    P(9) <= P(10);

    P(10) <= P(11);

    P(11) <= P(12);

    P(12) <= P(13);

    P(13) <= P(14);

    P(14) <= P(15);

    P(15) <= P(16);

    Count <= Count + 1;

    IF Count > 8 THEN

    state <= STOP;

    END IF;

    --- Quote End ---

    I have not looked at you code in great detail but are you aware that in your state RUN (quoted above), the assignments to signal P (P <= P + A; or P <= P + S;) made in the case statement will be overridden by the shift register assigments (P(0) <= P(1);) etc. All except bit P(16), which has no further assigments.

    Assignments are made at the end of process execution.

    Not sure is this is relevant to you algorithm but you might like to take a look
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    17 years ago

    If you took the adder logic out of the process and made that bit combinatorial this would resolve the error Vernmid highlighted with only minor changes to your code.

    Also, don't you need some logic to drive P(16) otherwise the result can never be negative.

    Steve
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    17 years ago

    On further investigation I have found the following:

    You need to maintain the sign after the shift, and you need to exit to state STOP earlier otherwise you exit to STOP at the end of the 9th cycle.

    Here are the mod's: 

    process (Resetn, Clock)
  begin
    if Resetn = '0' then
      state <= START;
      z     <= (others => '0');
    elsif (Clock'event and Clock = '1') then
      case state is
        when START =>
          Count <= "00001";
          A     <= x & "000000000";
          S     <= (not x + 1) & "000000000";
          P     <= "00000000" & y & '0';
          state <= RUN;
        when RUN =>
          P(0)  <= Ptmp(1);
          P(1)  <= Ptmp(2);
          P(2)  <= Ptmp(3);
          P(3)  <= Ptmp(4);
          P(4)  <= Ptmp(5);
          P(5)  <= Ptmp(6);
          P(6)  <= Ptmp(7);
          P(7)  <= Ptmp(8);
          P(8)  <= Ptmp(9);
          P(9)  <= Ptmp(10);
          P(10) <= Ptmp(11);
          P(11) <= Ptmp(12);
          P(12) <= Ptmp(13);
          P(13) <= Ptmp(14);
          P(14) <= Ptmp(15);
          P(15) <= Ptmp(16);
          P(16) <= Ptmp(16); -- Keep the sign
          Count <= Count + 1;
          if Count > 7 then -- Exit at the end of the 8th cycle
            state <= STOP;
          end if;
        when others =>
          z     <= P(16 downto 1);
          state <= STOP;
      end case;
    end if;
  end process;
 
  -- Took this out of the process and made it combinatorial.
  -- Output of the adder is registers by the shift register.
  with P(1 downto 0) select
    adderIp <=
    "00000000000000000" when "00",
    "00000000000000000" when "11",
    A                   when "01",
    S                   when others;
 
  Ptmp <= P + adderIp;

    I have simulated this and it works for a few test cases, but you will need to check it as I am not that familiar with Booth's algorithm.

    As an asside the 17 lines of code for the shift register could be replaced with one line:

    P <= Ptmp(16) & Ptmp(16 downto 1);

    Steve
  • Altera_Forum's avatar
    Altera_Forum
    Icon for Honored Contributor rankHonored Contributor
    17 years ago

    I figured out what my problem was I ended up making my addition and my shift two different states and that worked for me. Thank you for all your help