Journal Verilog && récursivité(récursivité(récursivité( ERROR: STACK OVERFLOW

Cher journal,

Hier, j'ai découvert que l'on pouvait faire du code récursif en Verilog.

Le verilog, qu'est-ce que c'est que quoi ?

Verilog est un vieux langage de description matériel. Il sert à modéliser des circuits qui pourront être ensuite simulé et être implémenté sur un FPGA ou en ASIC.

En guise d'exemple, voici un petit module qui fait clignoter une DEL :

`define CLOCK_FREQUENCY 25000000 // Number of clock tick in 1 second - 25Mhz
`define LED_TICKS_COUNT `CLOCK_FREQUENCY // Switch the LED state every second

module LedBlink(o_led, i_clock, i_nreset);
    output reg o_led;
    input i_clock, i_nreset;

    reg [24:0] r_counter; // 25 bits counter, up to 33,554,341
    always @(posedge i_clock, negedge i_nreset) begin
        if (!i_nreset) begin
            // Reset the counter and switch off the LED
            r_counter <= 0;
            o_led <= 0;
        end else if (r_counter == `LED_TICKS_COUNT) begin
            // Reset the counter and switch the LED state
            r_counter <= 0;
            o_led <= !o_led;
        end else begin
            // Update the counter
            r_counter <= r_counter + 1;
        end
    end
endmodule

Le code ci dessus est équivalent à ce circuit :

Paramètres

Il est possible de rendre les modules plus génériques via l'utilisation de paramètres dont la valeur est définissable lors de instanciation du module. Par exemple, au lieu d'avoir un module qui fait des additions sur 8 bits et un autre sur 16 bits, il est possible d'en avoir qu'un seul dont la taille est générique :

module Adder(z, a, b);
    // Paramètre permettant de définir la taille de l'adder
    parameter WIDTH = 8; // Valeur par défaut

    // La taille des entrées/sorties dépend du paramètre WIDTH
    output [WIDTH - 1:0] z;
    input [WIDTH - 1:0] a, b;

    assign z = a + b;
endmodule

module Foo(z1, z2, a, b);
    output [7:0] z1;
    output [15:0] z2;
    input [15:0] a, b;

    // Instantiation de l'adder en utilisant la valeur par défaut du paramètre
    Adder adder8(.z(z1), .a(a[7:0]), .b(b[7:0]));

    // Instantiation de l'adder en choississant la valeur du paramètre
    Adder #(.WIDTH(16)) adder16(.z(z2), .a(a), .b(b));
endmodule

La récursivité avec un exemple à la con

Il est possible de créer une nouvelle instance d'un module en lui même et de jouer avec les paramètres pour définir la condition d'arrêt.

Nous allons prendre l'exemple d'un registre à décalage. Une manière de l'écrire serait de la manière suivante :

 module ShiftRegister(q, d, clk);
     parameter WIDTH = 8;

     output reg q;
     input d, clk;

     reg [WIDTH - 2:0] data;
     always @(posedge clk) begin
         {q, data} <= {data, d};
     end
 endmodule

Mais pourquoi faire simple et propre quand on peut utiliser de la récursion ? Mr Olivier Cogis, mon professeur d'algorithmie, disait qu'une forêt est une forêt vide ou un arbre et une forêt. Réutilisons ce principe pour définir notre registre à bascule :

 module ShiftRegister(q, d, clk);
     parameter WIDTH = 4;

     output q;
     input d, clk;

     if (WIDTH <= 0) begin
         // Forêt vide
         assign q = d; // passthrough
     end else begin
         // Un arbre
         reg data;
         always @(posedge clk) begin
             data <= d;
         end

         // Une forêt
         ShiftRegister #(.WIDTH(WIDTH - 1)) sr(.q(q), .d(data), .clk(clk));
     end
 endmodule

Multiplexeur

Bon, je ne vais te mentir, l'exemple ci dessus n'est pas vraiment une bonne pratique. Mais il a le mérite d'être pour introduire le sujet. Par contre, j'ai trouvé un cas où la récursion est bien pratique : l'écriture d'un multiplexeur, mux de son petit nom.

Le mux de base, le mux 2, possède 2 entrées (d'où le nom), un sélecteur S et d'unes ortie Z. Quand S vaut 0, on retrouve la valeur de A sur la sortie Z sinon celle de B. Sa table de vérité est

B A S | Z
---------
X 0 0 | 0
X 1 0 | 1
0 X 1 | 0
1 X 1 | 1

que l'on peut simplifier en

S | Z
-----
0 | A
1 | B

Bref, c'est l'opérateur ternaire de l'électronique (Z = S ? B : A).

En chaînant les mux2 sous forme d'arbre, il est possible d'obtenir des multiplexeurs plus grands, tel que le mux4 :

et le mux 8 :

Comme tu est très perspicace, tu auras remarqué que un mux 2^S est constitué de 2 mux 2^(S - 1) et un mux 2. Le mux 4 (S = 2) est ainsi constitué de 2 mux 2 reliés par un mux 2 et le mux 8 (S = 3) est constitué de 2 mux 4 relié par un mux 2.

module Mux(z, d, s);
    parameter S = 3;

    output z;
    input [2 ** S - 1:0] d;
    input [S - 1:0] s;

    if (S == 1) begin
        assign z = s ? d[1] : d[0];
    end else begin
        wire z1, z2;
        Mux #(.S(S - 1)) mux1(.z(z1), .d(d[2 ** (S - 1) - 1:0]), .s(s[S - 2:0]));
        Mux #(.S(S - 1)) mux2(.z(z2), .d(d[2 ** S - 1:2 ** (S - 1)]), .s(s[S - 2:0]));
        assign z = s[S - 1] ? z2 : z1;
    end
endmodule