- 2078 Chaitra
LCM processor with state table
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.
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.
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
X = a; Y = b
while (X != Y):
if (X < Y) X = X + a
else Y = Y + b
output X // LCM
State diagram
S0 --start=1--> S1 (compare X, Y)
S0 --start=0--> S0
S1 --X<Y--> 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<Y; S1 -> 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
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.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- Design LCM single-purpose processor · Embedded System, chapter 2
- LCM processor algorithm and VHDL · Embedded System, chapter 9 · asked 2×
- Fibonacci single-purpose processor · Embedded System, chapter 2 · asked 2×
- Factorial single-purpose processor · Embedded System, chapter 2
- C program: sum of two 8-bit BCD numbers · Embedded System, chapter 9
- GCD processor algorithm and VHDL · Embedded System, chapter 9 · asked 3×
- Poker test, 10,000 five-digit numbers (2072) · Simulation and Modeling, chapter 6 · asked 4×
- Poker test, 1000 four-digit numbers (2070 Magh) · Simulation and Modeling, chapter 6 · asked 3×
- Poker test, 1000 four-digit numbers (2069) · Simulation and Modeling, chapter 6 · asked 3×
- Poker test, 10,000 five-digit numbers (2074) · Simulation and Modeling, chapter 6 · asked 2×