Le blog de f-leb

Dans un flux de données binaire tel que 1 0 0 1 1 0 ... , détecter une séquence particulière est un exercice de logique séquentielle que l’on peut résoudre grâce à une approche par machine à états finis (Finite State Machine FSM).

Par exemple, la machine à états finis du graphe ci-dessous permet de détecter la séquence 1 1 0 1 :

S0, S1, S1 et S3 sont les états de la machine, et les étiquettes au niveau des arcs orientés définissent les transitions (les conditions de passage d’un état à un autre) et l’état de la sortie. L’étiquette de chaque transition est un couple état entrée/état sortie.
Par exemple, (S0)---1/0--->(S1) signifie que l’état passe de S0 à S1 si l’entrée (le bit courant du flux) est égale à 1, et dans ce cas la sortie passe à 0. Pour une description complète, chaque état (Si) a forcément deux arcs qui partent : un pour l’entrée égale à 0, un autre pour l’entrée égale à 1.
Dans une détection de séquence, on veut naturellement que la sortie passe à 1 si la bonne séquence 1 1 0 1 est détectée, ici sur l’arc (S3)---1/1--->(S0).

Remarquez que la machine décrite n’autorise pas de chevauchement dans la séquence. Par exemple dans le flux 1 1 0 1 1 0 1, on pourrait voir la séquence apparaître deux fois :

• 1 1 0 1 1 0 1
• 1 1 0 1 1 0 1

Mais dans ce cas, le 1 en 4^e position chevaucherait les deux séquences, ce qui n’est pas autorisé d’après le graphe. Seule la 1^re séquence sera détectée par notre machine.

Cette description de machine à états finis où la sortie dépend à la fois de l’état courant (Si) et de l’entrée constitue une machine de Mealy.

Voici un exemple de détection obtenu en simulation :

Simulation : la séquence 1 1 0 1 est détectée deux fois

L’entrée din est asynchrone mais la lecture du flux en entrée, la détection et les transitions opèrent sur front montant de l’horloge.

En logique séquentielle, le traitement s’effectue avec trois processus :

• un processus combinatoire qui calcule l’état futur à partir de l’entrée et de l’état présent ;
• un processus séquentiel où l’état présent est mis à jour par l’état futur et mémorisé sur front montant de l’horloge (ou remis à l’état initial (S0) sur un signal Reset asynchrone) ;
• un processus combinatoire qui calcule la sortie à partir de l’entrée et de l’état présent.

d'après https://www.emse.fr/~dutertre/docume...es_a_etats.pdf

Voici le module complet de détection de la séquence en Verilog avec les trois processus :

Code verilog :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
module top(clk, rst, din, dout); // détection de séquence 1101

    input clk, rst, din;
    output reg dout;
    
    localparam S0 = 2'b00,
                    S1 = 2'b01,
                    S2 = 2'b10,
                    S3 = 2'b11;


    (* syn_encoding = "user" *) reg [1:0] state;
                                         reg [1:0] state_next;
    
    /*  Mise à jour de l’état présent par l’état futur sur les fronts montant 
         d’horloge (reset asynchrone inclus) */
    always @(posedge clk or posedge rst) begin
        if (rst) 
            state <= S0;        
        else 
            state <= state_next;    
    end

    /* Calcul des sorties à partir de l'entrée et de l’état présent */
    always @(posedge clk or posedge rst) begin
        if (rst) 
            dout <= 1'b0;       
        else 
            dout <= (state == S3) && din; // sortie dépend de l'entrée et de l'état
    end

    /*  Calcul de l’état futur à partir de l'entrée et de l’état présent */
    always @(*) begin
        case (state)    // selon l'état présent
            S0 : state_next <= din ? S1 : S0;
            S1 : state_next <= din ? S2 : S0;
            S2 : state_next <= din ? S2 : S3;
            S3 : state_next <= S0;
        endcase
    end
    
endmodule

Le système analysé est bien une machine à états finis

Vous noterez l’attribut syn_encoding redéfini à "user" pour l’encodage des états :

Code verilog :

Sélectionner tout - Visualiser dans une fenêtre à part

(* syn_encoding = "user" *) reg [1:0] state;

Voir Intel® Quartus® Prime Pro Edition Help version 22.2 - syn_encoding Verilog HDL Synthesis Attribute.

Sans cette redéfinition, Quartus superpose à l’encodage des états défini par l’utilisateur un autre encodage par défaut (d’autres encodages sont possibles : one-hot, Gray, etc. Chacun pour éviter des états transitoires indésirables). J’ai fait cela pour que Quartus laisse tels quels mes états définis sur 2 bits dans le code à la synthèse du projet :

Code verilog :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
	localparam 	S0 = 2'b00,
			S1 = 2'b01,
			S2 = 2'b10,
			S3 = 2'b11;

Et j’ai pu ainsi comparer le circuit synthétisé avec celui issu de mes calculs établis sur les tables de vérité écrites « à la main »

Eh bien le synthétiseur est au moins aussi fort que moi (certes, il est quand même bien plus rapide). Ce n’est pas que je n’avais pas confiance, mais j’aime bien me rendre compte par moi-même pour comprendre…

Regardez le circuit synthétisé ci-dessous :

Les blocs state~4 et state~5 sont les bascules qui mémorisent respectivement le bit de poids faible et le bit de poids fort de l’état (Si). Les blocs state~6 et state~7 sont les blocs de logique combinatoire qui calculent l’état suivant en fonction de l’état présent et de l’entrée din.
Le schéma n’est pas facile à suivre, mais j’ai fait apparaître à gauche le détail du bloc state~7. Sur le papier, j’avais oublié la simplification de l’équation qui amène une porte XOR. Le synthétiseur ne l’a pas loupée, lui ! Je valide le circuit généré...