Assignment Chef icon Assignment Chef
All German tutorials

Programming lesson

RTL-Design eines GCD-Rechners auf FPGA: Schritt-für-Schritt-Anleitung für das CDA 4203L Lab 5

Lerne, wie du einen GCD-Rechner (Größter gemeinsamer Teiler) auf einem FPGA mit RTL-Design implementierst. Diese Anleitung erklärt Datapath, FSM und Verilog-Code für das CDA 4203L Lab 5 – ideal für Studierende der Computertechnik.

GCD FPGA RTL Design GCD CDA 4203L Lab 5 GCD Rechner Verilog FPGA GCD Implementierung Größter gemeinsamer Teiler FPGA Datapath Control Path GCD Moore FSM GCD Verilog GCD Code GCD Testbench FPGA Labor Anleitung Computer System Design Lab GCD Algorithmus Hardware GCD RTL Tutorial GCD FPGA Projekt GCD Simulation Verilog

RTL-Design eines GCD-Rechners auf FPGA: Schritt-für-Schritt-Anleitung für das CDA 4203L Lab 5

Im Rahmen des Labors 5 des Kurses CDA 4203L (Computer System Design Lab) im Frühjahr 2025 geht es um die Implementierung eines GCD-Rechners (Größter gemeinsamer Teiler) auf einem FPGA. In dieser Anleitung zeigen wir dir, wie du die RTL-Architektur (Register-Transfer-Level) für zwei 4-Bit-Zahlen entwirfst und in Verilog umsetzt. Dabei kombinieren wir die Theorie aus der Vorlesung mit praktischen Tipps für die Laborarbeit.

Der GCD (Greatest Common Divisor) ist ein fundamentales Konzept in der Zahlentheorie und findet Anwendung in der Kryptographie, Fehlerkorrektur und digitalen Signalverarbeitung. In diesem Lab lernst du, wie du diesen Algorithmus als Hardware-Modul auf einem FPGA realisierst – eine wichtige Fähigkeit für angehende Computerarchitekten und Embedded-Entwickler.

Überblick über die GCD-Architektur

Die GCD-Berechnung erfolgt nach dem Euklidischen Algorithmus: Solange die beiden Zahlen X und Y nicht gleich sind, wird die größere durch die Differenz ersetzt. Am Ende ist der GCD in beiden Registern gespeichert. Die Hardware-Architektur besteht aus einem Datapath (Datenpfad) und einem Control Path (Steuerwerk, FSM).

Der Datapath enthält Register, einen Subtrahierer, einen Vergleicher (Less-than, Not-equal) und Multiplexer. Die FSM steuert die Abläufe: Laden der Startwerte, wiederholte Subtraktion und Ausgabe des Ergebnisses.

Datapath-Design mit strukturellem Verilog

Der Datapath wird aus einzelnen Komponenten zusammengesetzt. Jede Komponente wird als separates Modell in Verilog beschrieben – die meisten sind kombinatorisch, nur die Register sind getaktet. Wichtig: Die Register haben einen Enable-Eingang von der FSM und einen separaten Reset.

Hier ein Beispiel für ein 4-Bit-Register mit Enable und synchronem Reset:

module register_4bit (clk, reset, enable, d, q);
 input clk, reset, enable;
 input [3:0] d;
 output reg [3:0] q;
 always @(posedge clk) begin
 if (reset) q <= 4'b0;
 else if (enable) q <= d;
 end
endmodule

Weitere benötigte Komponenten sind:

  • Subtrahierer (kombinatorisch): berechnet X - Y oder Y - X.
  • Less-than-Vergleicher: gibt 1 aus, wenn X < Y.
  • Not-equal-Vergleicher: gibt 1 aus, wenn X != Y.
  • Multiplexer (2-zu-1): wählt zwischen X und Y basierend auf dem Less-than-Signal.

Alle diese Komponenten sind rein kombinatorisch, d.h. sie haben keine internen Zustände und reagieren sofort auf Eingabeänderungen. Das ist entscheidend für die korrekte Funktion des Datapaths.

Control Path mit Moore-FSM

Die FSM (Finite State Machine) ist das Herzstück der Steuerung. Sie wird in behavioralem Verilog nach der Moore-Topologie entworfen: Die Ausgänge hängen nur vom aktuellen Zustand ab. Die FSM erhält Signale vom Datapath (z.B. x_lt_y, x_neq_y) und steuert die Enable-Signale der Register sowie die Auswahl der Multiplexer.

Typische Zustände sind:

  • IDLE: Warten auf Start.
  • LOAD_X: Initialisiere X-Register.
  • LOAD_Y: Initialisiere Y-Register.
  • CHECK: Prüfe, ob X != Y; wenn ja, gehe zu SUB, sonst zu DONE.
  • SUB: Führe Subtraktion durch (X = X - Y oder Y = Y - X).
  • DONE: Ergebnis ausgeben.

Ein Ausschnitt der FSM in Verilog (Moore) könnte so aussehen:

module fsm_gcd (clk, reset, start, x_neq_y, x_lt_y, load_x, load_y, sel, done);
 input clk, reset, start, x_neq_y, x_lt_y;
 output reg load_x, load_y, sel, done;
 parameter [2:0] IDLE=0, LOAD_X=1, LOAD_Y=2, CHECK=3, SUB=4, DONE=5;
 reg [2:0] state, next_state;
 always @(posedge clk) begin
 if (reset) state <= IDLE;
 else state <= next_state;
 end
 always @(*) begin
 next_state = state;
 case (state)
 IDLE: if (start) next_state = LOAD_X;
 LOAD_X: next_state = LOAD_Y;
 LOAD_Y: next_state = CHECK;
 CHECK: if (x_neq_y) next_state = SUB; else next_state = DONE;
 SUB: next_state = CHECK;
 DONE: if (!start) next_state = IDLE;
 endcase
 end
 always @(*) begin
 {load_x, load_y, sel, done} = 4'b0;
 case (state)
 LOAD_X: load_x = 1;
 LOAD_Y: load_y = 1;
 SUB: sel = x_lt_y;
 DONE: done = 1;
 endcase
 end
endmodule

Beachte: Die FSM verwendet einen Takt, der idealerweise gegenphasig zum Datapath-Takt läuft, um sicherzustellen, dass die Enable-Signale rechtzeitig an den Registern anliegen. Alternativ kann man den Datapath mit der negativen Flanke takten.

Top-Level-Modul GCD_top

Das Top-Level-Modul instanziiert den Datapath und die FSM und verbindet die Signale. Die Eingänge des Top-Levels sind Takt, Reset, Start und die beiden 4-Bit-Zahlen A und B. Der Ausgang ist der 4-Bit-GCD-Wert.

module GCD_top (clk, reset, start, A, B, gcd_out);
 input clk, reset, start;
 input [3:0] A, B;
 output [3:0] gcd_out;
 wire load_x, load_y, sel, done;
 wire x_neq_y, x_lt_y;
 wire [3:0] X, Y;
 fsm_gcd fsm (clk, reset, start, x_neq_y, x_lt_y, load_x, load_y, sel, done);
 datapath_gcd dp (clk, reset, load_x, load_y, sel, A, B, X, Y, x_neq_y, x_lt_y, gcd_out);
endmodule

Testbench und Simulation

Eine gute Testbench testet verschiedene Zahlenpaare, z.B. (8,4) → 4, (7,3) → 1, (12,8) → 4. Achte darauf, dass die Simulation die korrekte Abfolge der Zustände zeigt und der GCD am Ausgang erscheint. Verwende Wellenformen, um die Signale zu überprüfen.

Ein Beispiel für eine Testbench:

module tb_gcd_top;
 reg clk, reset, start;
 reg [3:0] A, B;
 wire [3:0] gcd_out;
 GCD_top uut (clk, reset, start, A, B, gcd_out);
 initial begin
 clk = 0;
 forever #5 clk = ~clk;
 end
 initial begin
 reset = 1; start = 0; A=0; B=0;
 #10 reset = 0;
 #10 A=8; B=4; start=1;
 #10 start=0;
 #100;
 $display("GCD von %d und %d ist %d", A, B, gcd_out);
 $finish;
 end
endmodule

Häufige Fehler und Tipps

  • Timing-Probleme: Stelle sicher, dass die Enable-Signale der Register stabil sind, bevor die Taktflanke kommt. Verwende bei Bedarf eine doppelte Flankenerkennung oder einen verzögerten Takt.
  • Vergiss nicht den Reset: Alle Register und die FSM müssen einen initialen Reset erhalten.
  • Komponenten korrekt instanziieren: Achte auf die richtige Port-Reihenfolge und Datenbreite.

Fazit

Mit dieser Anleitung bist du in der Lage, den GCD-Rechner für das CDA 4203L Lab 5 zu entwerfen und zu simulieren. Das RTL-Design auf FPGA ist eine grundlegende Fertigkeit, die dir in vielen Bereichen der Digitaltechnik zugutekommt – von der Prozessorentwicklung bis zur KI-Beschleunigung. Viel Erfolg bei deinem Labor!