GCD processor algorithm and VHDL

A GCD processor is a custom (single-purpose) processor built as an FSMD: a datapath (registers, comparator, subtractors) controlled by a finite state machine. It uses Euclid's subtraction method.

Algorithm

read a, b
while (a != b and a != 0 and b != 0)
    if a > b then a = a - b
    else          b = b - a
gcd = max(a, b)   -- = a if a = b, or the non-zero one

Example: gcd(48,18): (48,18) -> (30,18) -> (12,18) -> (12,6) -> (6,6) so gcd = 6.

Datapath (FSMD)

 a_in -->[Reg A]--+--> [ =, >, =0 comparators ]--+
 b_in -->[Reg B]--+                             status
     ^load ^A-B  ^load ^B-A                        |
     |     |     |     |                           v
     +-----+-----+-----+<-- control --+------------+
 result <-- max(A,B)                   | FSM        |<- start
                                       | controller |-> done
                                       +------------+

State diagram

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

State table

VHDL code

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

entity gcd is
  port (
    clk    : in  std_logic;
    reset  : in  std_logic;                 -- asynchronous, active high
    start  : in  std_logic;                 -- pulse to begin
    a_in   : in  unsigned(7 downto 0);
    b_in   : in  unsigned(7 downto 0);
    done   : out std_logic;                 -- '1' when result is valid
    result : out unsigned(7 downto 0)
  );
end entity gcd;

architecture fsmd of gcd is
  type state_t is (S_IDLE, S_CHECK, S_SUBA, S_SUBB, S_DONE);
  signal state : state_t;
  signal a, b  : unsigned(7 downto 0);      -- datapath registers
begin
  process (clk, reset)
  begin
    if reset = '1' then
      state <= S_IDLE;
      a <= (others => '0');
      b <= (others => '0');
    elsif rising_edge(clk) then
      case state is
        when S_IDLE =>
          if start = '1' then
            a <= a_in;                      -- load operands
            b <= b_in;
            state <= S_CHECK;
          end if;
        when S_CHECK =>
          if a = b or a = 0 or b = 0 then
            state <= S_DONE;                -- finished
          elsif a > b then
            state <= S_SUBA;
          else
            state <= S_SUBB;
          end if;
        when S_SUBA =>
          a <= a - b;                       -- a := a - b
          state <= S_CHECK;
        when S_SUBB =>
          b <= b - a;                       -- b := b - a
          state <= S_CHECK;
        when S_DONE =>
          if start = '0' then               -- wait for start to be released
            state <= S_IDLE;
          end if;
      end case;
    end if;
  end process;

  done   <= '1' when state = S_DONE else '0';
  result <= a when a >= b else b;           -- max(a,b): gcd, also right if one operand is 0
end architecture fsmd;

Notes: the code was analysed and simulated with GHDL (gcd(48,18) = 6, gcd(7,5) = 1, gcd(0,9) = 9, gcd(100,75) = 25). Registers A and B hold the datapath state; result is max(A,B), which is the GCD when the machine reaches DONE.