GCD Calculator using FSM and Datapath Design

This project implements a Greatest Common Divisor (GCD) calculator in Verilog, showcasing two different approaches to solving the same mathematical problem. The project emphasizes digital hardware design principles by comparing:

1. Behavioral Verilog model using a while loop and modulus (%) operator
2. Fully synthesizable FSM and Datapath architecture based on the subtraction-driven Euclidean algorithm
3. C reference implementation used as a software model for verification, testbench comparison, and generating test vectors

While both approaches are functionally correct, this project is primarily built around the FSM + Datapath design, which mirrors the internal workings of a CPU and is suitable for actual hardware implementation.

Project Overview

The main learning goal of this project was to explore the controller + datapath design pattern, which is foundational in modern CPU architecture. The FSM handles sequencing and logic control, while the datapath performs the arithmetic operations.

Additionally, an alternate Verilog implementation using a while loop and % modulus operator is included to compare both hardware feasibility and performance considerations.

Design Approaches

Approach 1: Behavioral Verilog using while + % (Simulation Only)

This model follows the traditional GCD approach taught in programming courses — repeatedly applying modulus until one operand becomes zero.

while (a != 0 && b != 0) {
    if (a > b)
        a = a % b;
    else
        b = b % a;
}
gcd = (a == 0) ? b : a;

• Functional in simulation
• Not synthesizable
• Uses % operator and while loop, which do not map directly to logic gates
• Module: GCD_while.v, GCD_while_tb.v

This version is helpful for early-stage functional validation, but not suitable for synthesis or FPGA/ASIC design.

Approach 2: FSM + Datapath using Subtraction (Synthesizable)

This is the core of the project. It builds a hardware-friendly GCD unit by breaking the design into:

• Datapath:
  • Subtractor
  • Comparator
  • Registers (PIPO)
  • MUXes
• Controller FSM:
  • Issues control signals (lda, ldb, sel1, sel2, sel3)
  • Monitors condition flags (Lt, Gt, Et)
  • Determines which operand to update each cycle

This architecture mimics how processors execute arithmetic through datapaths and control units, making it an excellent exercise in VLSI and digital system design.

Approach 3: C Reference Model for GCD

Alongside the Verilog implementations, this project also includes a C-based GCD calculator.
This serves as a golden reference model for verifying correctness against a predefined test data file.

• Fast and portable — runs in software on any system
• Useful for validating the hardware RTL outputs
• Files: GCD_using_C.c, gcd_test_data.txt

Why I Chose the FSM-Based Subtraction Approach

While both methods compute the GCD correctly, the final design was centered around the subtraction method for hardware feasibility:

In digital hardware, modulus (%) is slower and resource-heavy compared to subtraction. Since both approaches require repetitive operations until convergence, the subtraction method is computationally more efficient in a circuit. Subtraction is just an adder with inversion and carry-in, while modulus requires division hardware or iterative logic, making it costlier and slower.

Thus, I opted to go with the FSM + Datapath design and treated the behavioral model as a learning milestone rather than the final implementation.

Architecture Overview

FSM Controller

Controller Flowchart

The FSM transitions through 6 states:

FSM State Diagram

Datapath Components

Datapath Flowchart

Datapath Circuit

Output Snapshots

Example terminal output for FSM + Datapath design (from testbench with inputs 4 and 24):

GCD calculation completed
GCD of the two numbers is: 4

Subtraction-Based FSM Model Output

Modulus-Based While Loop Output

Synthesis Results

The Controller + Datapath GCD design was synthesized successfully, confirming that the architecture is fully hardware realizable.

Synthesis Screenshot

Overview Schematic

Detailed Schematic

Generated Netlist Schematic

A schematic was auto-generated during synthesis, showcasing how the datapath and FSM logic are mapped into gates and registers.

Overview Schematic
🔗 Overview Schematic PDF

Detailed Schematic
🔗 Detailed Schematic PDF

Repository Structure

├── hdl/
│   ├── rtl/
│   │   ├── datapath.v
│   │   ├── controller.v
│   │   ├── pipo.v
│   │   ├── subtractor.v
│   │   ├── comparator.v
│   │   ├── mux_2x1.v
│   │   ├── GCD_while.v
│   │
│   ├── tb/
│       ├── gcd_tb.v
│       ├── GCD_while_tb.v
│
├── images/
│   ├── block_diagram.jpeg
│   ├── controller_flowchart.jpeg
│   ├── fsm_diagram.jpeg
│   ├── datapath_flow.jpeg
│   ├── output_subtraction.gif
│   ├── output_modulus.gif
│   ├── schematic.png
│   ├── schematic_1.png
│
├── GCD_Using_C/
│   ├── GCD_using_C.c
│   ├── gcd_test_data.txt
│
├── README.md
├── LICENSE

Project Files

Tools Used

Conclusion

This project demonstrates two distinct ways to compute GCD in Verilog — one focused on hardware synthesis and the other on algorithmic clarity:

• The FSM-based subtraction model is modular, synthesizable, and suited for real hardware.
• The while + modulus approach offers quick simulation modeling but is not synthesizable and impractical in hardware.

Through this, I gained a deeper understanding of:

• FSM and datapath partitioning
• Hardware implementation vs behavioral modeling
• Trade-offs in algorithm selection based on speed and synthesizability

License

Open for educational and personal use under the MIT License