URL: https://linuxfr.org/users/killruana/journaux/verilog-recursivite-recursivite-recursivite-error-stack-overflow Title: Verilog && récursivité(récursivité(récursivité( ERROR: STACK OVERFLOW Authors: jtremesay Date: 2020年05月05日T18:34:31+02:00 License: CC By-SA Tags: verilog Score: 34 Cher journal, Hier, j'ai découvert que l'on pouvait faire du code récursif en [Verilog](https://fr.wikipedia.org/wiki/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é](https://fr.wikipedia.org/wiki/Simulateur_logique) et être implémenté sur un [FPGA](https://fr.wikipedia.org/wiki/Circuit_logique_programmable) ou en [ASIC](https://fr.wikipedia.org/wiki/Application-specific_integrated_circuit). En guise d'exemple, voici un petit module qui fait clignoter une DEL : ```verilog `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 : ![Représentation graphique du module LedBlink](https://i.zcraft.fr/3731841588687449.png) # 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 : ```verilog 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 ``` ![Diagramme montrant les adders 8 et 16 bits](https://i.zcraft.fr/5260641588690216.png) # 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](https://fr.wikipedia.org/wiki/Registre_%C3%A0_d%C3%A9calage). Une manière de l'écrire serait de la manière suivante : ```verilog 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 ``` ![Diagramme du registre à décalage](https://i.zcraft.fr/7771791588691210.png) 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 : ```verilog 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 ``` ![Diagramme du registre à décalage recursif](https://i.zcraft.fr/4591761588692227.png) # 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](https://fr.wikipedia.org/wiki/Multiplexeur), mux de son petit nom. ![Un mux 2](https://upload.wikimedia.org/wikipedia/commons/thumb/3/39/Multiplexer_2-to-1.svg/175px-Multiplexer_2-to-1.svg.png) 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 : ![Diagramme d'un mux 4](https://i.zcraft.fr/3724891588696559.png) et le mux 8 : ![Diagramme d'un mux 8](https://i.zcraft.fr/3453071588696448.png) 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. ```verilog 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 ``` ![Diagramme du mux récursif](https://i.zcraft.fr/1668721588695397.png)

AltStyle によって変換されたページ (->オリジナル) /