Esercizio 32riconoscitore di sequenza con automa di Mealy

1. Automa di Mealy

Gli stati ricordano quanto della sequenza 101 è già stato visto (come suffisso degli ultimi bit):

• $S_0$: nessun prefisso utile (l'ultimo bit era 0 e non fa parte di un 10 iniziale, oppure siamo all'inizio);
• $S_1$: l'ultimo bit era 1 (prefisso 1);
• $S_2$: gli ultimi due bit erano 10 (prefisso 10).

Transizioni, con uscita scritta come $X/Z$:

Perché: da $S_1$ (visto 1) con $X = 0$ si ha 10 → $S_2$; con $X = 1$ si ha 11: l'ultimo 1 può ancora iniziare una nuova sequenza → resta $S_1$. Da $S_2$ (visto 10) con $X = 1$ la sequenza 101 è completa: $Z = 1$ e, per la sovrapposizione, l'ultimo 1 è già il prefisso 1 di una nuova sequenza → $S_1$ (non $S_0$); con $X = 0$ si ha 100: nessun prefisso utile → $S_0$.

Servono 3 stati: l'uscita dipende anche dall'ingresso (Mealy).

2. Sintesi con flip-flop D

3 stati → $\lceil \log_2 3 \rceil = 2$ flip-flop. Codifica: $S_0 = 00$, $S_1 = 01$, $S_2 = 10$ ($Q_1 Q_0 = 11$ non usato: condizione di indifferenza).

Con i flip-flop D l'ingresso $D$ di ciascun flip-flop è il valore di stato prossimo. Mappe di Karnaugh (righe $Q_1 Q_0$, colonna $X$):

$Q_1'$: vale 1 solo per $Q_1 Q_0 X = 010$; la riga $110$ è indifferente e permette un gruppo da 2 ($Q_1 = 0$ o $1$, $Q_0 = 1$, $X = 0$):

$$D_1 = Q_1' = Q_0\,\overline{X}$$

$Q_0'$: vale 1 per $001$, $011$, $101$ (e $111$ indifferente): in tutti i casi con $X = 1$, gruppo da 4:

$$D_0 = Q_0' = X$$

$Z$: vale 1 solo per $101$; con l'indifferenza in $111$ il gruppo è $Q_1 X$:

$$Z = Q_1 X$$

Circuito: un AND con ingressi $Q_0$ e $\overline{X}$ che pilota $D_1$; un filo da $X$ a $D_0$; un AND con ingressi $Q_1$ e $X$ per l'uscita. Due flip-flop D, due porte AND e un inverter.

3. Automa di Moore

Se l'uscita deve dipendere solo dallo stato, serve uno stato in più che significhi "appena ricevuta 101" ($S_3$, con $Z = 1$): 4 stati, 2 flip-flop lo stesso ma una rete di stato prossimo più complicata, e l'uscita è valida nel ciclo successivo a quello dell'ultimo bit.

Da $S_3$ (visto 101): con $X = 0$ gli ultimi bit sono 10 → $S_2$; con $X = 1$ l'ultimo 1 ricomincia → $S_1$.

4. Simulazione

import random

def rete(sequenza):
    """Mealy `101` con sovrapposizione: Q1' = Q0 X', Q0' = X, Z = Q1 X."""
    q1 = q0 = 0
    uscite = []
    for x in sequenza:
        z = q1 & x                         # uscita dello stato attuale e dell'ingresso
        q1, q0 = q0 & (1 - x), x           # fronte di clock: i D diventano il nuovo stato
        uscite.append(z)
    return uscite

def riferimento(sequenza):
    s = "".join(map(str, sequenza))
    return [1 if s[max(0, i - 2): i + 1] == "101" else 0 for i in range(len(s))]

for _ in range(2000):
    seq = [random.randint(0, 1) for _ in range(random.randint(0, 30))]
    assert rete(seq) == riferimento(seq)
print("2000 sequenze casuali concordano")

seq = [1, 0, 1, 0, 1, 1, 0, 1]
print(seq, rete(seq))                      # [1, 0, 1, 0, 1, 1, 0, 1] [0, 0, 1, 0, 1, 0, 0, 1]

Traccia su $X = 1\,0\,1\,0\,1\,1\,0\,1$ (stato $Q_1Q_0$ prima del fronte → $Z$ → nuovo stato):

L'uscita vale 1 al terzo bit (101), al quinto (101 sovrapposta a quella precedente: l'ultimo 1 del primo 101 è il primo del secondo) e all'ottavo.

Errori comuni

• Tornare in $S_0$ (invece che in $S_1$) dopo aver riconosciuto 101: si perderebbe la sovrapposizione.
• Mettere l'uscita sugli stati in un automa di Mealy, o sugli archi in un automa di Moore.
• Dimenticare una transizione: per ogni stato e per ogni valore di $X$ ne serve una.
• Non sfruttare le condizioni di indifferenza dello stato $11$ nella semplificazione.
• Confondere stato prossimo $Q'$ (ciò che i flip-flop D memorizzano al prossimo fronte) con lo stato attuale $Q$.