ELEMANIA
Digitale - Riconoscimento di sequenze
Automi per il riconoscimento di sequenze

Un'applicazione tipica degli automi è il riconoscimento di sequenze di simboli, come avviene per esempio nei compilatori e negli interpreti dei linguaggi di programmazione per riconoscere la correttezza sintattica delle istruzioni (operazione detta parsing).

In telecomunicazioni gli automi possono essere usati per riconoscere determinate sequenze di 0 e di 1 all'interno di un flusso binario di dati. Supponiamo per esempio che la fine di una trasmissione di bit venga segnalata dalla sequenza 1101 (in realtà di solito le sequenze sono formate da 8 bit, ma scegliamo una sequenza più breve per semplicità di esempio). Quando l'automa riconosce questa sequenza di bit, deve segnalarlo portando a 1 il valore dell'uscita.

Il diagramma degli stati è il seguente:

Come al solito la numerazione degli stati è arbitraria. I valori dell'uscita prodotta sono indicati in rosso su ogni stato.

Partiamo dallo stato 000 (stato iniziale). Finché non viene ricevuto un bit 1, l'automa rimane bloccato su questo stato (come indica l'arco di transizione che si richiude sullo stato stesso). La ricezione del primo 1 ci fa spostare nello stato 001.

Se a questo punto viene ricevuto uno 0 (cioè un simbolo non valido), l'automa si riporta allo stato di partenza 000. Altrimenti, se riceve un 1, passa allo stato 010. Qui viene atteso un valore 0 (in caso contrario, si rimane su 010, cioè l'1 appena ricevuto viene considerato come il secondo 1 dell'inizio di una nuova sequenza), che fa passare allo stato 011 e poi un 1 finale che conduce allo stato 100 e manda a 1 l'uscita (perché è stata riconosciuta la sequenza 1101).

La tabella delle transizioni è la seguente:

Ingresso Stato precedente Stato successivo
I Q2 Q1 Q0 Q2 Q1' Q0'
0 0 0 0 0 0 0
0 0 1 0 0 0
0 0 1 0 0 1 1
0 0 1 1 0 0 0
0 1 0 0 0 0 0
1 0 0 0 0 0 1
1 0 0 1 0 1 0
1 0 1 0 0 1 0
1 0 1 1 1 0 0
1 1 0 0 0 0 1

La tabella delle verità per il calcolo delle transizioni conterrà 16 righe, ma di queste solo 10 sono usate (le rimanenti sono indifferenze). La tabella per il calcolo delle uscite contiene invece 8 righe di cui solo cinque sono usate (quelle corrispondenti agli stati del contatore). Lasciamo al lettore come facile esercizio la sintesi di queste tabelle.

 

precedente - successiva

Sito realizzato in base al template offerto da

http://www.graphixmania.it