LCM processor algorithm and VHDL

An LCM processor is a custom single-purpose processor (FSMD). Because a divider is costly, it finds the LCM by repeated addition: it generates the multiples of a and of b in step until they are equal; the first common multiple is the LCM.

Algorithm

read a, b
if a = 0 or b = 0 then lcm = 0
else
    ma = a;  mb = b
    while ma != mb
        if ma < mb then ma = ma + a
        else            mb = mb + b
    lcm = ma

Example: a = 4, b = 6: (ma,mb) = (4,6) -> (8,6) -> (8,12) -> (12,12), so LCM = 12.

Datapath and state diagram (FSMD)

 a_in -> [A] --+--> [ma + A] -> [MA]--+
 b_in -> [B] --+--> [mb + B] -> [MB]--+--> [ =0, =, < ]
                                      |        |
                          result <- MA        status
                                               v
                         start -> [ FSM controller ] -> done

         start=0 (wait)
          +----+
          v    |
        ( IDLE )
          |  start=1 : A,MA<=a_in ; B,MB<=b_in
          v
 +-----( CHECK )-----+
 |  MA<MB |  | MA>MB | MA=MB or a=0 or b=0
 |        v  v       v
 | ( ADDA )  ( ADDB ) ( DONE ) done=1
 |  MA<=MA+A  MB<=MB+B   |  start=0
 |    |         |        v
 +----+---------+      ( IDLE )
  (ADDA, ADDB return to CHECK)

State table

VHDL code

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity lcm is
  port (
    clk    : in  std_logic;
    reset  : in  std_logic;                  -- asynchronous, active high
    start  : in  std_logic;
    a_in   : in  unsigned(7 downto 0);
    b_in   : in  unsigned(7 downto 0);
    done   : out std_logic;
    result : out unsigned(15 downto 0)
  );
end entity lcm;

architecture fsmd of lcm is
  type state_t is (S_IDLE, S_CHECK, S_ADDA, S_ADDB, S_DONE);
  signal state : state_t;
  signal a, b   : unsigned(15 downto 0);     -- the two operands (kept)
  signal ma, mb : unsigned(15 downto 0);     -- running multiples of a and b
begin
  process (clk, reset)
  begin
    if reset = '1' then
      state <= S_IDLE;
      a <= (others => '0'); b <= (others => '0');
      ma <= (others => '0'); mb <= (others => '0');
    elsif rising_edge(clk) then
      case state is
        when S_IDLE =>
          if start = '1' then
            a  <= resize(a_in, 16);
            b  <= resize(b_in, 16);
            ma <= resize(a_in, 16);          -- first multiple of a
            mb <= resize(b_in, 16);          -- first multiple of b
            state <= S_CHECK;
          end if;
        when S_CHECK =>
          if a = 0 or b = 0 then
            ma <= (others => '0');           -- LCM defined as 0 here
            state <= S_DONE;
          elsif ma = mb then
            state <= S_DONE;                 -- common multiple found
          elsif ma < mb then
            state <= S_ADDA;
          else
            state <= S_ADDB;
          end if;
        when S_ADDA =>
          ma <= ma + a;                      -- next multiple of a
          state <= S_CHECK;
        when S_ADDB =>
          mb <= mb + b;                      -- next multiple of b
          state <= S_CHECK;
        when S_DONE =>
          if start = '0' then
            state <= S_IDLE;
          end if;
      end case;
    end if;
  end process;

  done   <= '1' when state = S_DONE else '0';
  result <= ma;
end architecture fsmd;

Notes: the code was analysed and simulated with GHDL: lcm(4,6) = 12, lcm(3,5) = 15, lcm(12,18) = 36, lcm(0,9) = 0. The result register is 16 bits wide because the LCM of two 8-bit numbers can need up to 16 bits.