---
title: "LCM processor algorithm and VHDL"
subject: "Embedded System"
chapter: 9
key: "semester_6/embedded_system:vhdl-lcm-processor"
source: https://www.bctengineer.com/q/semester_6/embedded_system/vhdl-lcm-processor
site: BCT Engineering
---

# LCM processor algorithm and VHDL

Embedded System · Chapter 9: Microcontrollers in Embedded Systems

- Asked in: 2072 Asoj, 3+5 marks; 2074 Bhadra, 3+5 marks (asked 2 times)
- Video: [Designing Single Purpose Processor To Calculate GCD (HCF).](https://www.youtube.com/watch?v=Wy344fMRnOo) — AFlick
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_6/embedded_system/vhdl-lcm-processor
- Whole chapter: https://www.bctengineer.com/md/semester_6/embedded_system/chapter-9

## Question

Write an algorithm and VHDL code for a custom processor that calculates Least Common Multiple (LCM) of two numbers (as a finite state machine).

## Short answer

The FSMD finds LCM by repeated addition: ma = a, mb = b; if ma < mb, ma += a else mb += b, until ma = mb. States IDLE, CHECK, ADDA, ADDB, DONE. Result is final ma (or 0 if a or b is zero).

## Answer

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

```text
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)

```text
 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

| State | Condition | Datapath action | Next | done |
|---|---|---|---|---|
| IDLE | start = 0 | none | IDLE | 0 |
| IDLE | start = 1 | A, MA <= a_in; B, MB <= b_in | CHECK | 0 |
| CHECK | a = 0 or b = 0 | MA <= 0 | DONE | 0 |
| CHECK | MA = MB | none | DONE | 0 |
| CHECK | MA < MB | none | ADDA | 0 |
| CHECK | MA > MB | none | ADDB | 0 |
| ADDA | - | MA <= MA + A | CHECK | 0 |
| ADDB | - | MB <= MB + B | CHECK | 0 |
| DONE | start = 0 | none | IDLE | 1 |
| DONE | start = 1 | none | DONE | 1 |

#### VHDL code

```vhdl
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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How does the processor find the LCM without a divider?
   A. By dividing a by b
   B. By generating multiples of a and b until they are equal
   C. By subtracting the numbers
   D. By multiplying a and b only
   Answer: B. It repeatedly adds a to ma and b to mb until ma = mb, the first common multiple. (Key point: LCM method)

2. If ma < mb, which update is done?
   A. mb = mb + b
   B. ma = 0
   C. ma = ma + a
   D. mb = 0
   Answer: C. The smaller multiple is advanced so the two meet at the least common value. (Key point: Which to advance)

3. For a = 4, b = 6, what is the final common value?
   A. 24
   B. 10
   C. 6
   D. 12
   Answer: D. (4,6) -> (8,6) -> (8,12) -> (12,12), so LCM = 12. (Key point: Example)

4. Why is the result 16 bits wide for 8-bit inputs?
   A. The LCM of two 8-bit numbers can need up to 16 bits
   B. To store the state
   C. VHDL needs 16 bits
   D. To hold GCD
   Answer: A. The LCM can be as large as the product of the operands. (Key point: Result width)

## Related in Embedded System

- [GCD processor algorithm and VHDL](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-gcd-processor) — Embedded System, chapter 9, asked 3×
- [Design LCM single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-lcm-datapath-controller) — Embedded System, chapter 2
- [LCM processor with state table](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-lcm-state-table-2digit) — Embedded System, chapter 2

## Related in other subjects

- [Algorithm for numbers divisible by 9 not 6](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Aalgo-flowchart-divisible-9-not-6) — Computer Programming, chapter 2
- [Differentiate Finite State Machine and Automata](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsm-vs-fsa-difference) — Discrete Structure, chapter 2, asked 2×