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 les changements d'états sont opérés sur front montant de l’horloge.
Pour des besoins fonctionnels, la sortie est resynchronisée sur l'horloge (mais ce n'est pas obligatoire).

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 SystemVerilog :

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 Sequence (  // détection de séquence 1101
	input  logic clk, rst, din,
	output logic dout
	);

	  
	typedef enum logic[1:0] {S0, S1, S2, S3, ERR='X} state_t;
	state_t state, state_next; // état courant, état futur
	logic dout_async;
	 
	 
	/* Combinatoire des états
		Calcul de l’état futur à partir de l'entrée et de l’état présent */
	always_comb begin
		state_next = ERR; // état futur inconnu par défaut
		if (rst)
			state_next = S0;		
		else 
			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
    
	/*  Mise à jour de l’état présent par l’état futur sur les fronts montants d’horloge */
	always_ff @(posedge clk) begin
		state <= state_next;    
	end

	/* Combinatoire de la sortie
	    Calcul des sorties à partir de l'entrée et de l’état présent */
	always_comb begin       
		dout_async = (state == S3) && din; // sortie dépend de l'entrée et de l'état
	end
	
	always_ff @(posedge clk) begin  // resynchronisation de la sortie
		dout <= dout_async;    
	end
  
endmodule

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

Edit : mise à jour le 20/08/2024