--- title: "GCD processor algorithm and VHDL" subject: "Embedded System" chapter: 9 key: "semester_6/embedded_system:vhdl-gcd-processor" source: https://www.bctengineer.com/q/semester_6/embedded_system/vhdl-gcd-processor site: BCT Engineering --- # GCD processor algorithm and VHDL Embedded System · Chapter 9: Microcontrollers in Embedded Systems - Asked in: 2069 Bhadra, 8 marks; 2071 Bhadra, 3+5 marks; 2073 Bhadra, 2+6 marks (asked 3 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-gcd-processor - Whole chapter: https://www.bctengineer.com/md/semester_6/embedded_system/chapter-9 ## Question Write an algorithm and VHDL code (finite state machine, with state diagram) for a custom processor that calculates Greatest Common Divisor (GCD) of two numbers. ## Short answer The GCD processor uses Euclid’s subtraction: load a and b; while a≠b and both nonzero, subtract the smaller from the larger; result is max(a,b). Implemented as an FSMD with states IDLE, CHECK, SUBA, SUBB, DONE. VHDL uses a state machine with registers A,B, comparators, and subtractors. ## Answer 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 ```text 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) ```text 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 ```text start=0 (wait) +----+ v | ( IDLE ) | start=1 : A<=a_in, B<=b_in v +-----( CHECK )-----+ | a>b | | a b | none | SUBA | 0 | | CHECK | a < b | none | SUBB | 0 | | SUBA | - | A <= A - B | CHECK | 0 | | SUBB | - | B <= B - A | 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 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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. How does the GCD processor update A and B? A. It divides A by B B. It subtracts the smaller from the larger C. It adds A and B D. It multiplies A and B Answer: B. If a > b then a = a - b, else b = b - a, until they are equal. (Key point: Euclid subtraction) 2. When does the machine move from CHECK to DONE? A. When a > b B. When start = 0 C. When a = b, or a or b is zero D. After exactly 8 cycles Answer: C. At equality the common value is the GCD; zero operands also end the loop. (Key point: Termination) 3. What does the FSM controller do in the FSMD? A. It stores the operands B. It performs the subtraction itself C. It converts the clock D. It uses status from the comparators to control datapath loads and subtraction Answer: D. The FSM sequences control signals using comparator status; registers and subtractors form the datapath. (Key point: FSMD structure) 4. Why is result = max(A,B)? A. At DONE the GCD is the larger (equal or non-zero) value of A and B B. It always returns A C. It returns the minimum D. It returns A + B Answer: A. When A = B both hold the GCD; if one is 0 the non-zero one is the GCD. (Key point: Result) 5. In S_DONE, why does the machine wait for start = 0 before returning to IDLE? A. To reset the registers B. To avoid immediately restarting while start is still held high C. To double the result D. To start a subtraction Answer: B. Otherwise a held start would trigger a new computation immediately. (Key point: DONE handshake) ## Related in Embedded System - [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× - [Sequence detector 1011 state diagram and VHDL](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Avhdl-sequence-detector-1011) — Embedded System, chapter 9 - [Two categories of semi-custom IC](https://www.bctengineer.com/question.md?key=semester_6%2Fembedded_system%3Asemi-custom-two-categories) — Embedded System, chapter 8, asked 2× ## Related in other subjects - [Greatest and smallest of ten numbers](https://www.bctengineer.com/question.md?key=semester_1%2Fcomputer_programming%3Afortran-greatest-smallest-ten) — Computer Programming, chapter 11 - [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×