--- title: "LCM processor with state table" subject: "Embedded System" chapter: 2 key: "semester_6/embedded_system:spp-lcm-state-table-2digit" source: https://www.bctengineer.com/q/semester_6/embedded_system/spp-lcm-state-table-2digit site: BCT Engineering --- # LCM processor with state table Embedded System · Chapter 2: Hardware Design Issues - Asked in: 2078 Chaitra - 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-state-table-2digit - Whole chapter: https://www.bctengineer.com/md/semester_6/embedded_system/chapter-2 ## Question Design a single purposed processor that gives the LCM of two digit 8-bit numbers. Start with the algorithm, translate it into state diagram and state transition table. Also draw the required data-path. ## Short answer Algorithm: initialize multiples X=a, Y=b; while not equal, add a to smaller. State diagram: S0 wait, S1 compare, S2 X+=a, S3 Y+=b, S4 output. Transition table encodes states in 3 bits; S1 branches on eq (to S4), lt (to S2), else S3. Datapath: A,B,X,Y registers, adders for X+A and Y+B, muxes, comparator for eq/lt. ## Answer **Assumptions:** the two inputs a and b are 8-bit positive numbers (two decimal digits, at most 99); registers are 16 bits. Method: keep X (a multiple of a) and Y (a multiple of b); add to the smaller until X = Y. #### Algorithm ```text X = a; Y = b while (X != Y): if (X < Y) X = X + a else Y = Y + b output X // LCM ``` #### State diagram ```text S0 --start=1--> S1 (compare X, Y) S0 --start=0--> S0 S1 --X S2 (X = X + A) --> S1 S1 --X>Y--> S3 (Y = Y + B) --> S1 S1 --X=Y--> S4 (out = X, done = 1) --> S0 ``` Transitions: S1 -> S2 if X S3 if X>Y; S1 -> S4 if X=Y; S2 -> S1; S3 -> S1; S4 -> S0. #### State transition table (state encoding: S0 = 000, S1 = 001, S2 = 010, S3 = 011, S4 = 100) | Present state | start | eq | lt | Next state | Actions / outputs | |---|---|---|---|---|---| | S0 (000) | 0 | x | x | S0 | done = 0 | | S0 (000) | 1 | x | x | S1 (001) | A, B, X, Y loaded | | S1 (001) | x | 1 | x | S4 (100) | none | | S1 (001) | x | 0 | 1 | S2 (010) | none | | S1 (001) | x | 0 | 0 | S3 (011) | none | | S2 (010) | x | x | x | S1 (001) | X = X + A | | S3 (011) | x | x | x | S1 (001) | Y = Y + B | | S4 (100) | x | x | x | S0 (000) | out = X, done = 1 | #### Datapath ```text a -> [A]--+ +--[B]<- b v v [ + ] <- X Y -> [ + ] | | mux(a | X+A) mux(b | Y+B) v v [X] ------+------ [Y] | v | | [ comparator ]-> eq, lt v output (LCM) ``` Components: registers A, B, X, Y; two adders; two multiplexers; one comparator (eq, lt); output buffer. The controller above drives the loads and mux selects. Example a = 12, b = 18: X/Y: (12,18) -> (24,18) -> (24,36) -> (36,36): LCM = 36. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. If X < Y in the compare state, what happens next? A. Go to S2 and set X = X + A B. Go to S3 and set Y = Y + B C. Go to S4 and output D. Return to S0 Answer: A. The smaller value, X, is increased by A, then control returns to S1. (Key point: Decision in S1) 2. When does the processor go from S1 to S4? A. When X < Y B. When X = Y C. When start = 0 D. When X > Y Answer: B. Equality means X is the common multiple; S4 outputs it and sets done = 1. (Key point: Termination) 3. For a = 12, b = 18, what is the output? A. 18 B. 216 C. 36 D. 72 Answer: C. (12,18) -> (24,18) -> (24,36) -> (36,36), so LCM = 36. (Key point: Example result) 4. How many bits are needed to encode the five states S0-S4 in binary? A. 2 B. 5 C. 4 D. 3 Answer: D. Five states need ceil(log2 5) = 3 bits (S0 = 000 ... S4 = 100). (Key point: State encoding) ## Related in Embedded System - [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 algorithm and VHDL](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-lcm-processor) — Embedded System, chapter 9, asked 2× - [Fibonacci single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-fibonacci) — Embedded System, chapter 2, asked 2× - [Factorial single-purpose processor](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Aspp-factorial) — Embedded System, chapter 2 - [C program: sum of two 8-bit BCD numbers](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3A8051-bcd-sum-c) — Embedded System, chapter 9 - [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× ## Related in other subjects - [Poker test, 10,000 five-digit numbers (2072)](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Apoker-test-numerical-2072-ashwin) — Simulation and Modeling, chapter 6, asked 4× - [Poker test, 1000 four-digit numbers (2070 Magh)](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Apoker-test-numerical-2070-magh) — Simulation and Modeling, chapter 6, asked 3× - [Poker test, 1000 four-digit numbers (2069)](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Apoker-test-numerical-2069-bhadra) — Simulation and Modeling, chapter 6, asked 3× - [Poker test, 10,000 five-digit numbers (2074)](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Apoker-test-numerical-2074-magh) — Simulation and Modeling, chapter 6, asked 2×