---
title: "Design LCM single-purpose processor"
subject: "Embedded System"
chapter: 2
key: "semester_6/embedded_system:spp-lcm-datapath-controller"
source: https://www.bctengineer.com/q/semester_6/embedded_system/spp-lcm-datapath-controller
site: BCT Engineering
---

# Design LCM single-purpose processor

Embedded System · Chapter 2: Hardware Design Issues

- Asked in: 2069 Bhadra, 8 marks
- 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/spp-lcm-datapath-controller
- Whole chapter: https://www.bctengineer.com/md/semester_6/embedded_system/chapter-2

## Question

Design a processor that calculates the LCM of two numbers. Show the design of data path only and construct the diagram of controller.

## Short answer

Method: maintain X = multiples of a, Y = multiples of b; if X<Y, X = X+a else Y = Y+b until X=Y. Datapath: registers A(a), B(b), X, Y; adders with muxes to load or add; comparator generates eq/lt flags. Controller: FSM with states S0 (wait), S1 (compare), S2 (X add), S3 (Y add), S4 (output).

## Answer

The design uses the additive LCM method: keep two running multiples, X (of a) and Y (of b), and repeatedly add to the smaller one until they become equal. That common value is the LCM. (Inputs a and b are positive integers.)

#### Algorithm
```text
 LCM(a, b):
   X = a; Y = b
   while (X != Y):
       if (X < Y) X = X + a
       else       Y = Y + b
   output X
```
Example a = 4, b = 6: (X, Y) = (4,6) -> (8,6) -> (8,12) -> (12,12). LCM = 12.

#### FSMD
| State | Condition | Actions | Next |
|---|---|---|---|
| S0 wait | start = 0 | done = 0 | S0 |
| S0 | start = 1 | A = a, B = b, X = a, Y = b | S1 |
| S1 compare | X = Y | none | S4 |
| S1 | X < Y | none | S2 |
| S1 | X > Y | none | S3 |
| S2 | always | X = X + A | S1 |
| S3 | always | Y = Y + B | S1 |
| S4 output | always | out = X, done = 1 | S0 |

#### Datapath (only)
```text
  a -> [A]        [B] <- b
        |  X+A      |  Y+B
        v           v
  +--> [adder]   [adder] <--+
  |       |          |      |
  |   mux(a,X+A)  mux(b,Y+B)
  |       v          v      |
  +----- [X]        [Y] ----+
          |  \      /  |
          |   [comparator]--> eq, lt  (to controller)
          v
        out = X
```
Components: registers A, B, X, Y (X and Y are 16 bits, since the LCM of two 8-bit numbers can need up to 16 bits), two adders (or one shared adder with a mux), two 2:1 multiplexers (load the input or the add result), one comparator giving *eq* (X = Y) and *lt* (X < Y), and an output buffer. Control inputs to the datapath: loadA/B, X_sel, X_ld, Y_sel, Y_ld, out_en.

#### Controller (FSM)
Inputs: start, eq, lt. Outputs: X_ld, Y_ld, selects, done. Five states, 3-bit state register.
```text
 start, status flags --> +-------------+   +-----------+
 (from datapath)         | Next-state  |-->| State     |
                         | logic       |   | register  |
                         +------^------+   +-----+-----+
                                |   current state |
                                +-----------------+
                                                  v
                                           +-------------+
                                           | Output logic|--> control
                                           +-------------+    signals
```

| State | Control signals asserted |
|---|---|
| S0 | none (waiting) |
| S1 | none (comparison only) |
| S2 | X_sel = add, X_ld = 1 |
| S3 | Y_sel = add, Y_ld = 1 |
| S4 | out_en = 1, done = 1 |

## Check yourself

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

1. How does the additive LCM method work?
   A. Repeatedly subtract the smaller from the larger
   B. Keep multiples X of a and Y of b; add to the smaller until X = Y
   C. Multiply a by b and divide by 2
   D. Add a and b until the sum is even
   Answer: B. The common value reached by the running multiples is the LCM. (Key point: LCM method)

2. For a = 4, b = 6, what is the final (X, Y)?
   A. (24, 24)
   B. (10, 10)
   C. (12, 12)
   D. (8, 12)
   Answer: C. (4,6) -> (8,6) -> (8,12) -> (12,12), so LCM = 12. (Key point: LCM trace)

3. Which status signals does the comparator send to the controller?
   A. start and done
   B. loadA and loadB
   C. out_en only
   D. eq (X = Y) and lt (X < Y)
   Answer: D. The controller needs eq and lt to choose between ending, adding to X, or adding to Y. (Key point: Comparator outputs)

4. Why are registers X and Y 16 bits for 8-bit inputs?
   A. The LCM of two 8-bit numbers can reach 16 bits
   B. Because the adder is 16 bits wide by default
   C. To store the start signal
   D. Because 8-bit registers cannot be loaded
   Answer: A. The LCM can be as large as a*b, so it may need up to 16 bits. (Key point: Register width)

## Related in Embedded System

- [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
- [Factorial single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-factorial) — Embedded System, chapter 2
- [Single-purpose processor for power](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-power) — Embedded System, chapter 2, asked 2×
- [Dual-purpose processor: median and variance](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Adual-purpose-median-variance) — Embedded System, chapter 2
- [Fibonacci single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-fibonacci) — Embedded System, chapter 2, asked 2×
- [LCM processor algorithm and VHDL](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-lcm-processor) — Embedded System, chapter 9, asked 2×

## Related in other subjects

- [Single-phase AC voltage controller with R load](https://www.bctengineer.com/question.md?key=semester_7%2Fpower_electronics%3Aacvc-r-load-rms) — Power Electronics, chapter 6, asked 6×
- [DMA controller block diagram and transfer](https://www.bctengineer.com/question.md?key=semester_5%2Fcomputer_organization_and_architecture%3Adma-controller) — Computer Organization and Architecture, chapter 7, asked 6×
- [Digital PD controller design for plant 1/s²](https://www.bctengineer.com/question.md?key=semester_6%2Fdigital_control_system%3Apd-design-double-integrator) — Digital Control System, chapter 4, asked 2×
- [Derivative feedback controller: block diagram and effect](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Aderivative-feedback-bd-effect) — Control Systems, chapter 7, asked 2×