Reti Logiche 1 - uniroma2.it · 22/06/2010 Corso di Reti Logiche 2005/06 14 Ma il sistema oltre a...

Reti Logiche 1

Prof. B. Buttarazzi

A.A. 2009/2010

Sommario

• Introduzione alle reti sequnziali

• La definizione di ASF

• ASF di Mealy e Moore

22/06/2010 Corso di Reti Logiche 2009/10

• ASF di Mealy e Moore

• Diagrammi di stato e Tabelle di flusso

• Automi equivalenti

• Minimizzazione di ASF

• Esempi

Le reti combinatorie sono caratterizzate da un modello che definisce in

modo univoco la corrispondenza tra ingresso e uscite z=f(x)

Introduzione alle reti sequenziali

Reti combinatorie

22/06/2010 Corso di Reti Logiche 2005/06 3

Porte logiche

combinatorie

ingressiuscite

Reti combinatorie

• Una rete combinatoria con n ingressi ed m uscite

realizza m funzioni booleane con n ingressi.

• Assegnando alle variabili binarie x1x2….xn (che

rappresentano i segnali di ingresso) tutte le

possibili configurazioni di ingresso il

comportamento della rete si specifica tramite la

tabella di verità di ciascuna funzione di uscita

z1z2….zm .

Limite delle Reti Combinatorie

• Una Rete Combinatoria realizza una (o m ) funzione booleana

• ma non è in grado di realizzare un algoritmo

– Ad esempio un addizionatore ripple-carry con 4 FA

– Ad esempio un addizionatore ripple-carry con 4 FA realizza la funzione di somma con input parallelo a 4bit

però…….

– nessuna RC è in grado di realizzare da sola l’algoritmo della somma ovvero una generica somma a n-bit con input sequenziale.

Addizionatore per numeri binari rappresentati su 4 bit (e

risultato rappresentato

su 5 bit) ottenuto

dalla connessione di

4 moduli FA.

FULLADDER

Esempio di RC

4 moduli FA.

FULLADDER

Proviamo a calcolare la somma di 2 numeri

rappresentati su 3bit con I/O sequenziale

RC con I/O Sequenziale

X = (x2, x1, x0) = 011, Y = (y2, y1, y0) =110

X+Y = (r3, z2, z1, z0) =1001

Somma per dati sequenziali

Questo problema non può essere risolto da una Rete Combinatoria.

Occorre una rete capace di memorizzare il riporto e riassegnarlo

all’ingresso, quindi capace di dare risposte non solo in funzione

dell'ingresso corrente, ma anche dello stato corrente della sua memoria

interna.

X+Y = 101

•Occorre la memorizzazione del riporto!

•Occorre introdurre linea di ciclo!

Memoria ad 1 bit

X+Y = 0101errato!

Somma 3-bit con I/O sequenziale

errato!

correttoX+Y = (r3, z2, z1, z0) =1001

Reti Logiche per la somma

a b r s

0 0 0 0

Addizionatore Parallelo

Addizionatore

Addizionatore Seriale

Addizionatore

0 0 0 0

0 1 0 1

1 0 0 1

1 1 1 0

Tabella di veritàSchema a Blocchi

Addizionatore

1-bitb r

Memoria

Rete Logica Combinatoria Rete Logica Sequenziale

Addizionatore Seriale

Combinatoria

Full Adder

uscitaingresso

L’addizione è ottenuta mandando

in ingresso al Full Adder il riporto calcolato al passo precedente

Full Adder

futuro

presente

Una Rete sequenziale è caratterizzate dal fatto che le uscite non

dipendono solo dall'ingresso all'istante t ma anche dalla sequenza degli

ingressi applicati a partire dalla condizione iniziale.

Rete Sequenziale

Combinatoria

uscitaingresso

futuro

presente

In una Rete Sequenziale se indichiamo:

• x le variabili di ingresso

• z le variabili di uscita

• y le variabili che rappresentano lo stato attuale,

• Y le variabili che rappresentano lo stato futuro

Rete Sequenziale

• Y le variabili che rappresentano lo stato futuro

allora la relazione tra ingresso e uscita si articola in due funzioni:

Y= δ(x,y)

z = ω(x,y)

funzione di transizione di stato

funzione di uscita

Y= δ(x,y)

z = ω(x,y)Le due funzioni indicano che quando arrivano in ingresso dei segnali (x) l’output z prodotto dal sistema dipende sia dal valore di segnali in ingresso (x) sia dallo stato attuale (y). in cui si trova il sistema

Rete Sequenziale

Ma il sistema oltre a produrre l’output z, secondo la funzione di uscita ω, passerà dallo

stato attuale y a quello successivo Y secondo la funzione di transizione δ, che tiene conto del tipo di input e dello stato attuale.

Il numero di elementi di memoria dipende dai diversi stati in cui potrà trovarsi il sistema:

- un elemento di memoria (1 bit) permette di

Rete Sequenziale

- un elemento di memoria (1 bit) permette di rappresentare 2 stati (0,1).

- n elementi di memoria (n bit) posso rappresentare 2n

stati distinti.

Per fare l’analisi e la sintesi delle Reti Sequenziali è utile uno strumento formale adatto a descrivere sistemi con memoria.

Automi a stati finiti

memoria.

L'automa a stati finiti è il modello astratto adatto a rappresentare le reti sequenziali.

Prima di affrontare lo studio delle reti sequenziali analizzeremo, limitatamente agli obiettivi di questo corso, le caratteristiche degli automi a stati finiti.

Introduzione agli Automi

Con il termine automa s’intende un qualunque dispositivo, che esegue in modo autonomo un particolare compito, sulla base di ordini ricevuti.

particolare compito, sulla base di ordini ricevuti.

• Sono esempi di automi la lavatrice, la lavastoviglie, i sistemi di controllo di apertura/chiusura delle banche, i bancomat, i sistemi di controllo degli ascensori, i distributori automatici di bevande, gettoni telefonici, benzina.

• Sono rappresentabili con automi anche sistemi più astratti

Automi

• Sono rappresentabili con automi anche sistemi più astratti come gli analizzatori di linguaggi, i riconoscitori di sequenze, i traduttori.

• Anche i computer sono automi, in particolare sono automi che possono svolgere un ruolo diverso a seconda del programma che in quel momento sta “girando”nella memoria centrale.

Descrivere un automa significa fornire una indicazione, (supportata dall’uso di schemi,grafi, tabelle) delle modalità di funzionamento dell’automa stesso (cosa fa l'automa).

Automi

Quando descriviamo un automa compiamo un procedimento di astrazione preoccupandoci del solo comportamento logico-funzionale dell'automa e non della sua realizzazione fisica.

Noi ci riferiremo ad una particolare classe di automi, quella degli ASF che, da un punto di vista puramente matematico, rappresenta il modello astratto di un sistema con input ed output discreti, che può trovarsi in uno fra n STATI distinti.

Automa a Stati Finiti

Lo stato rappresenta una condizione in cui il sistema si trova tenendo conto degli input ricevuti in precedenza e da esso dipende il comportamento del sistema a fronte di input successivi.

Il comportamento di un automa a stati finiti (ASF)

A è descritto dalla quintupla

Automa a Stati Finiti

A=<I, O, Q, δ, ω >

ove I, O, Q, indicano rispettivamente

• I insieme finito di simboli di input

• O insieme finito di simboli di output

• Q insieme finito di stati interni di cui si assume q ∈Q stato

A=<I, O, Q, δ, ω >

Automi a stati finiti (ASF)

• Q insieme finito di stati interni di cui si assume q0 ∈Q stato

iniziale (di partenza )

mentre δ, ω sono le funzioni che specificano il comportamento dell’automa.

• δ : I×Q→Q è la funzione di transizione di stato (che ha per dominio

il prodotto cartesiano I×Q (ovvero l'insieme delle coppie xi,qi ) e per

codominio Q,) che serve a specificare il nuovo stato raggiunto

dall’automa;

• ω : I×Q→O è la funzione di uscita, che serve a specificare il

simbolo di uscita prodotto dall’automa.

Esistono automi ove l’informazione prodotta in uscita dipende soltanto dallo stato raggiunto dalla macchina.

(ovvero il valore dell’uscita è già associato allo stato dell’automa vedi Latch prossime lezioni) pertanto in tali casi anziché usare il simbolo ω si userà ω’.

Automi

anziché usare il simbolo ω si userà ω’.

Allora distingueremo i due tipi di automi in:

•Automi di Mealy quelli che fanno uso della funzione di uscita ω

•Automi di Moore quelli che fanno uso della funzione di uscita ω’.

Un automa si dice di Mealy (oppure improprio ) quando è

caratterizzato dal fatto che l’uscita (zt) al tempo t, oltre che

dallo stato (qt), dipende anche dagli ingressi nello stesso

istante, in pratica:zt=ωωωω(xt,qt).

Automi

Un automa si dice di Moore (oppure proprio) quando

l’uscita (zt) al tempo t dipende esclusivamente dal valore

assunto dallo stato al tempo t, in pratica:zt =ωωωω’(qt).

Non si deve pensare che gli automi di Moore siano più limitati di quelli di Mealy(rispetto alle cose che possono fare) in quanto è sempre possibile trasformare ogni automa di Mealy nel corrispondente automa di Moore e viceversa.

• x le variabili di ingresso

• z le variabili di uscita

• y le variabili che rappresentano lo stato attuale,

• Y le variabili che rappresentano lo stato successivo (a quello attuale)

allora la relazione tra ingresso e uscita si articola in due fasi:

Rete SequenzialeIn una rete sequenziale

allora la relazione tra ingresso e uscita si articola in due fasi:

Y= G(x,y)

z = F(x,y)

funzione di transizione di stato

funzione di uscita

Facendo corrispondere:

I → x,

O → z

Q → y,Y

δ δ δ δ →→→→ G

ω ω ω ω →→→→ F

Rete Sequenziale

ω ω ω ω →→→→ F

si può osservare la stretta corrispondenza che c’è fra un automa a stati finiti (ASF) A descritto dalla quintupla

A=<I, O, Q, δ, ω >

e una rete sequenziale descritta dalle relazioni ingresso uscita

Y= G(x,y) z = F(x,y)

Le Reti Sequenziali sono esempi di automi di Mealy.

Rappresentazioni di ASF

Per rappresentare il comportamento di un automa ovvero:

•i diversi stati,

•la funzione che calcola, lo stato successivo δ ,

•e la funzione che calcola l'uscita ω ,

generalmente si utilizzano due tipi di rappresentazione equivalenti:

• rappresentazione a grafo: diagramma degli stati;

• rappresentazione a matrice: tabella di flusso;

Nella rappresentazione a grafo, chiamato diagramma

degli stati,

• i nodi rappresentano i possibili stati dell’automa;

Rappresentazione a grafo

• i rappresentano i possibili ;

• gli archi rappresentano le relazioni di passaggio da

uno stato all’altro, secondo il particolare input.

ASF di Mealy

Nel diagramma degli stati dell’Automa di Mealy ogni nodo

rappresenta uno stato.

Ad ogni arco che collega due nodi (stati) q1 q2 è associata una

coppia x/z, dove x è l’ingresso che provoca il cambiamento dallo

stato q1 allo stato q2 e z è l’uscita che ne deriva.

Il generico arco che collega la coppia di nodi (stati) q1 q2 è

etichettato da una coppia di valori x,z tali che

δ(x,q1) = q2 e ω(x,q1) = z.

ASF di Mealy

q1 δ (x, q1)

x / ω(x, q1)

Stato q1 Stato q2

Nel diagramma degli stati dell’Automa di Moore ogni nodo rappresenta

uno stato cui è associata l’uscita corrispondente

Pertanto ogni stato è rappresentato da una coppia q/z ove q denota il

particolare stato e z è l’uscita ad esso associata.

Es: (qi / ω( qi) )

ASF di Moore

Es: (qi / ω( qi) )

Ad ogni arco che collega due nodi (stati q1 q2 ) è associata una sola

etichetta x, che rappresenta l’ingresso che provoca il cambiamento dallo

stato q1 allo stato q2.

q1 / ω( q1) δ (x, q1)

stato q1 stato q2

Il generico arco che collega la coppia di nodi (stati q1 q2 ) è

etichettato da x tale che

δ(x,q1) = q2 ove q2 è associato all’uscita z2 e z2 = ω( q2)

ASF di Moore

q1 / ω( q1) δ (x, q1)

stato q1 stato q2

Nella rappresentazione a matrice, chiamata tabella di flusso di un ASF di MEALY, ogni casella (incrocio riga-colonna) specifica

ASF di Mealy

specifica

• qual è il successivo stato e l’output prodotto dall’automa se esso si trova in un determinato stato e riceve un certo input.

Tabella di flusso di un ASF di Mealy

i1 i2 …. ….

insieme

stati in-1 in

insieme

ingressi

…. ….

......

…. ….

….sk

Ogni riga della tabella rappresenta uno stato dell'automa

Ogni colonna rappresenta una configurazione in ingresso

In ogni incrocio riga colonna è rappresentato lo stato futuro/ simbolo

d'uscita determinato dalla transizione.

i1 i2 …. ….

in-1 inii

ingresso

Tabella di flusso di un ASF di Mealy

…. ….

presentesp/zp stato futuro/

uscita

Nella rappresentazione a matrice, chiamata tabella di flusso un ASF di MOORE, ogni casella specifica

• qual è il successivo stato (e quindi l’output prodotto

Tabella di flusso di un ASF di Moore

• qual è il successivo stato (e quindi l’output prodotto dall’automa) se esso si trova in un determinato stato e riceve un certo input.

......

i1 i2 …. ….

insieme

stati in z

insieme degli

ingressi

colonna

uscite

…. ….

….sk

uscite

Ogni riga della tabella rappresenta uno stato dell'automa .

Ogni colonna (tranne l’ultima) rappresenta una configurazione in ingresso

i1 i2 u…. ….

ingresso

In ogni incrocio riga colonna è

rappresentato solo lo stato futuro,

in quanto il simbolo d'uscita è sull’ultima colonna.

…. ….

.. .. .. ..

…. ….

….sk

sjstato

presente

stato futuro

sp uj uscita

Un Automa di Mealy è

un ASF A1=<I, O, Q, δ, ω >•I insieme finito di simboli di input

•O insieme di valori di output

•Q insieme finito di stati interni di cui si assume q0 ∈Q stato di partenza

•δ : I×Q→Q funzione di transizione serve a specificare il nuovo stato

Riassumendo

•δ : I×Q→Q funzione di transizione serve a specificare il nuovo stato raggiunto dall’automa;

•ω : I×Q→O funzione di uscita, serve a specificare il simbolo di uscita prodotto dall’automa.

dove l’uscita al tempo t, oltre che dallo stato, dipende anche dagli

ingressi nello stesso istante:zt=ωωωω(xt,qt).

Un Automa di Moore è

un ASF A2=<I, O, Q, δ, ω’ >

•I insieme finito di simboli di input

•O insieme di valori di output

•Q insieme finito di stati interni di cui si assume q0 ∈Q stato di partenza

•δ : I×Q→Q funzione di transizione serve a specificare il nuovo stato

Riassumendo

•δ : I×Q→Q funzione di transizione serve a specificare il nuovo stato raggiunto dall’automa;

•ω’ : Q→O funzione di uscita, serve a specificare il simbolo di uscita prodotto dall’automa.

dove l’uscita al tempo t dipende esclusivamente dal valore assunto dallo

stato:zt =ωωωω’(qt).

Diagrammi degli stati

q δ (x, q)

x / ω(x, q)

Automa di MEALY:

L'uscita della rete

dipende dagli ingressi e

dagli stati interni :

z=w(x,q).

Il nodo contiene solo il

Automa di MOORE:

L'uscita della rete

dipende dallo stato

interno: z=w’(q). Il nodo

ha due etichette (q/w(q))

che rappresentano

rispettivamente il nome

Riassumendo

Mooreq δ (x, q)

q/ω(q) δ (x, q)

Il nodo contiene solo il

nome dello stato (q).

Sugli archi ci sono 2

etichette (x/w(X,q) che

rappresentano la

configurazione di

ingresso che determina il

passaggio da uno stato

all'altro e il simbolo

d'uscita.

rispettivamente il nome

dello stato ed il simbolo

d'uscita corrispondente.

Sugli archi vi è solo

un’etichetta (x ) la

configurazione di

ingresso che determina il

passaggio da uno stato

all'altro.

Tabella di Flusso

• Mealy

ingressi x

q δ (x,q) / ω (x,q)

Riassumendo

• Moore

ingressi x

q δ (x,q) ω(q)

Esercizio

• Dato il diagramma degli stati del seguente

Automa dire di che tipo di Automa si tratta

A/1 B/1

• Dal momento che ciascun nodo contiene solo il nome dello stato (q) e

sugli archi ci sono 2 etichette (x/z) che rappresentano la

configurazione di ingresso che determina il passaggio da uno stato

all'altro e il valore dell'uscita per tale configurazione, si tratta di un

Automa di MEALY ⇒ L'uscita della rete dipende dagli ingressi e

Soluzione

Automa di MEALY ⇒ L'uscita della rete dipende dagli ingressi e

dagli stati interni : z=w(x,q).

A/1 B/1

Automa di Mealy determinare la

corrispondente Tabella di Flusso

Esercizio

A/1 B/1

Soluzione

q0 q0/1 q1/0

q1 q0/0 q1/1

Automa di Mealy determinare la

Esercizio

Soluzione

00 01 11 10

Q0 Q0/0 Q0/1 Q1/0 Q0/1

Q1 Q0/1 Q1/0 Q1/1 Q1/0

• Data la seguente Tabella di Flusso

determinare il corrispondente diagramma

degli stati.

Esercizio

q0 q0/0 q1/0

q1 q0/0 q1/1

Soluzione

q0 q0/0 q1/0

q1 q0/0 q1/1

0/0 1/1

Automa di Moore determinare la

Esercizio

q0 /100

q1 /000

q /100

q /000

00 01 11 10 ω

Soluzione

q0 /100

q1 /0 10

q0 q1 q0 q0 1

q1 q1 q0 q1 0

Equivalenza

Due stati q e q’ di un automa A si dicono

equivalenti se

per ogni simbolo di ingresso x

(i)ω (x, q ) = ω (x, q ') (equicomportamento 1-step)

(ii)δ(x, q ) ≡δ (x, q ') (passo induttivo)

Stati equivalenti

Nell’automa di Mealy rappresentato si nota che q0 ≡ q2 in quanto:

• applicando la sequenza di simboli in ingresso AAB allo stato q0

il sistema produce in output 110

� ω (A, q0) =1 ω (A, q2) = 1ω (B, q2) = 0

• applicando la sequenza di simboli in ingresso AAB allo stato q2

il sistema produce in output 110

� ω (A, q2) =1 ω (A, q2) = 1ω (B, q2) = 0

A/1 B/1B/0

A/0A/1 B/1

• In un certo senso, potremmo dire che la presenza degli stati

equivalenti (q0 e q1) in A é ridondante, in quanto gli stati

equivalenti effettuano le stesse transizioni a fronte degli stessi

input.

• Poiché un automa é un modello astratto di una macchina

sequenziale, é intuitivo il fatto che sia conveniente minimizzare

Stati equivalenti

un automa, ovvero trovare un automa equivalente che abbia il

minimo numero di stati.

• Si noti comunque che ridurre il numero degli stati di un automa

(sostituendo tutti gli stati equivalenti con un unico

rappresentante) equivale a ridurre (con legge logaritmica) il

numero di elementi di memoria nel circuito corrispondente.

• applicando la sequenza di simboli in ingresso AAB allo

stato q0 il sistema produce in output 100

� ω (A, q0) =1 ω (A, q2) = 0ω (B, q2) = 0

• ma applicando la sequenza di simboli in ingresso AAB allo

stato q2 il sistema produce in output 000

ControEsempi

� ω (A, q2) =0 ω (A, q2) = 0ω (B, q2) = 0

A/1 B/1B/0

A/0A/0 B/1

Detti q e q’ due stati equivalenti di

un automa A, qualunque sequenza

di simboli di ingresso applicata ad

A nello stato q oppure ad A nello

stato q’ da luogo alla stessa

sequenza di output.

• Partendo dallo stato q0

� δ (B, q0) = q1

• Partendo dallo stato q2

� δ (B, q2) = q0

ControEsempi

� δ (B, q2) = q0

A/1 B/1B/0

A/0A/1 B/1

Equivalenza fra ASF

Due automi dello stesso tipo A e A’ sono

equivalenti se per ogni stato s di A esiste uno

stato s’ di A’ equivalente ad s e viceversa.

Riprenderemo l’aspetto della equivalenza per

la minimizzazione degli automi

Dato un Automa (ovvero data la sua tabella di flusso) il processo di minimizzazione mira ad eliminare gli stati ridondanti dell’automa, eventualmente presenti.

Il processo di minimizzazione degli stati di un automa consiste nei seguenti 3 passi:

Minimizzazione degli stati di un ASF

seguenti 3 passi:

• Trovare una partizione di stati dell’automa suddivisi in classi di equivalenza avente cardinalità minima.

• Scegliere un solo stato per ciascuna classe della partizione

• Sostituire ciascuna classe con il solo stato (nodo) scelto (utilizzando la tecnica della fusione).

Osservazioni

Per determinare l’automa minimo di un dato automa, a differenza di quanto capita per le funzioni booleane, esistono procedure efficienti

•Algoritmo per partizioni successive

•Metodo triangolare

Va comunque osservato che tra le due operazioni di minimizzazione è più importante quella delle funzioni booleane, infatti mentre minimizzare un automa significa ridurre il numero degli stati (rapporto tra numero di elementi di memoria e numero degli stati è k / 2k ) per le funzioni booleane risparmiare un operatore significa ridurre di uno il numero di porte.

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

Per descrivere i vari passi dell’ALGORITMO di minimizzazione

utilizzeremo come esempio la seguente tabella di flusso iniziale:

Minimizzazione di un ASF di Mealy

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,0

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

Metodo delle partizioni:

(i)ω (x, q ) = ω (x, q ') (equicomportamento)

(ii)δ(x, q ) ≡δ (x, q ‘ )(passo induttivo)

Primo step

Π0(Q)= {A,B,C,D,E,F}

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

Partizioniamo l’insieme di stati di partenza in funzione dell’output prodotto

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

Primo step

1 0 1 0

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

Primo step

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

1 0 1 0

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

Primo step

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

1 0 1 0

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

{A,C,D}

Primo step

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

1 0 1 0

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

{A,C,D}

Primo step

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

1 0 1 0

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

{A,C,D,F}

Primo step

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

1 0 1 0

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

{A,C,D,F}, {B}

Primo step

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

1 1 1 0

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

{A,C,D,F}, {B}

Primo step

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

1 1 1 0

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

{A,C,D,F}, {B}

Primo step

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

1 1 1 0

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

Π1(Q)= {A,C,D,F}, {B,E}

Primo step

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

1 1 1 0

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

Π1(Q)= {A,C,D,F}, {B,E}

Primo step

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

1 1 1 0

Per ogni partizione creata vedo se è soddisfatta la regola ii

00 01 11 10 Π0(Q)= {A,B,C,D,E,F}

Secondo step

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

A è equivalente a C se per configurazione

di input (00 01 11 01)l’automa transita

nella stessa classe di equivalenza

Π1(Q)= {A,C,D,F}, {B,E}= {αααα}, {γγγγ}

00 01 11 10

Secondo step

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

Vediamo se A è equivalente a C

(per ogni input deve essere δ(x, q )

≡δ (x, q ') )

00 01 11 10A è equivalente a C se per ogni input

Secondo step

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

A è equivalente a C se per ogni input

(00 01 11 01)l’automa transita nella

stessa classe

δ(x, q ) ≡δ (x, q ')

δ(00, A ) =A ovvero {αααα}, ΑΑΑΑ

e δ(00, C)= C ovvero {αααα} C

Secondo step

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

stessa classe

δ(01, A ) =E ovvero {γγγγ}, ΑΑΑΑ

e δ(01, C)= B ovvero {γγγγ} C

Secondo step

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

stessa classe

δ(11, A ) =A ovvero {αααα}, ΑΑΑΑ

δ(11, C)= C ovvero {αααα} C

Secondo step

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

stessa classe

δ(10, A ) =F ovvero {αααα}, ΑΑΑΑ

δ(10, C)= F ovvero {αααα} C

00 01 11 10

Secondo step

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

Quindi A è equivalente a C in

quanto per ogni input δ(x, q ) ≡

δ (x, q ')

00 01 11 10

Secondo step

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

Ora vediamo se A è equivalente a D

(per ogni input deve essere δ(x, q )

≡δ (x, q ') )

Dai confronti se vede che A ≡ D

00 01 11 10

Secondo step

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,O

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

….ripetendo

Dai confronti se vede che A ≡ D

00 01 11 10

Secondo step

00 01 11 10

A A,1 E,0 A,1 F,0

B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,0

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

Ma A non è equivalente a F in

quanto δ(01, A ) =E ovvero {γγγγ},

δ(01, F)= F ovvero {αααα}

pertanto devo ulteriormente

partizionare l’insieme

Secondo step

Π (Q)= {A,B,C,D,E,F}

Π1(Q)= {A,C,D,F}, {B,E}

Π2(Q)= {A,C,D}, {F},{B,E= {αααα}, {ββββ} , {γγγγ}

Eseguo lo stesso controllo sulla classe {B,E} che

non risulta partizionabile, pertanto l’insieme delle

classi equivalenti è:

{A,C,D}, {F} {B,E},

Secondo step

{A,C,D}, {F} {B,E},

{α}, {β} , {γ}

Tutti gli stati appartenenti ad una stessa classe possono essere sostituiti da uno solo di essi ( rappresentante ) in quanto sufficiente a rappresentarli tutti in una tabella di flusso minima.

Pertanto le classi risultanti sono:

Secondo step

α:=(Α,C,D)

β:=(Β,Ε)

γ:=(F)

A questo punto è possibile aggiornare la tabella di flusso (sostituire le 3 righe A,C,D con α – le 2 righe B,E con β e F con γ

α:=(A,C,D)

β:=(Β,Ε)

γ:=(F)

00 01 11 10

A A,1 E,0 A,1 F,0

Tabella di flusso

γ:=(F)B A,1 B,1 D,1 B,0

C C,1 B,0 C,1 F,0

D D,1 E,0 D,1 F,0

E A,1 E,1 C,1 E,0

F C,1 F,0 F,1 F,0

00 01 11 10

α α,1 β,0 α,1 γ,0

β α,1 β,1 α,1 β,0

γ α,1 γ,0 γ,1 γ,0

D D,1 E,0 D,1 F,0

00 01 11 10

α α,1 β,0 α,1 γ,0

La tabella di flusso minima è:

Tabella di flusso

β α,1 β,1 α,1 β,0

γ α,1 γ,0 γ,1 γ,0

D D,1 E,0 D,1 F,0

E A,1 E,1 C,1 E,0

B C,1 F,0 F,1 F,0

Ogni riga della tabella rappresenta uno stato dell'automa .

Ogni colonna rappresenta una configurazione in ingresso.

Poichè l’automa minimo ha 3 stati (ovvero necessita di

ricordare 3 stati distinti (α,β,γ) ) α,β,γ) ) α,β,γ) ) α,β,γ) ) per la sua implementazione

(sintesi) saranno sufficienti 2 bit, che potremmo codificare nel

Minimizzazione di un ASF di Mealy

(sintesi) saranno sufficienti 2 bit, che potremmo codificare nel

seguente modo:

α=00, β=01, γ=11.α=00, β=01, γ=11.α=00, β=01, γ=11.α=00, β=01, γ=11.

A D B 0

B E C 0

Minimizzazione di un ASF di Moore

(i)ω (x, q ) = ω (x, q ')

(equicomportamento)

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

(equicomportamento)

(ii)δ(x, q ) ≡δ (x, q ‘ )

(passo induttivo)

A D B 0

B E C 0

La minimizzazione di un automa di Moore è più semplice in quanto

la prima partizione si determina osservando direttamente la colonna z

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

Π1(Q)= {A,B,C,D,}, {E,F}= {αααα}, {γγγγ}

A D B 0

B E C 0

Mentre per i passi successivi è identica al caso precedente

Confronto A e B

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

Π1(Q)= {A,B,C,D,}, {E,F}= {αααα}, {γγγγ}

A D B 0

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

Π2(Q)= {A,C,D,}, {B}, {E,F}=

{αααα}, {ββββ} , {γγγγ}

A D B 0

B E C 0

Confronto A e C

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

Π2(Q)= {A,C,D,}, {B}, {E,F}=

A D B 0

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

Π2(Q)= {A,D,}, {B,C}, {E,F}=

A D B 0

B E C 0

Confronto A e D

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

Π2(Q)= {A,D,}, {B,C}, {E,F}=

A D B 0

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

Π2(Q)= {A,D,}, {B,C}, {E,F}=

A D B 0

B E C 0

Confronto B e C

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

Π2(Q)= {A,D,}, {B,C}, {E,F}=

A D B 0

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

Π2(Q)= {A,D,}, {B,C}, {E,F}=

A D B 0

B E C 0

Confronto E e F

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

Π2(Q)= {A,D,}, {B,C}, {E,F}=

A D B 0

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

Π2(Q)= {A,D,}, {B,C}, {E,F}=

A D B 0

B E C 0

Scelgo A,B,E come

rappresentanti delle 3

classi di equivalenza:

B E C 0

C F B 0

D A B 0

E F A 1

F E D 1

classi di equivalenza:

Π2(Q)= {A,D,}, {B,C}, {E,F}=

A A B 0

B E B 0

ASF di Moore ridotto

Π2(Q)= {A,D,}, {B,C}, {E,F}=

B E B 0

E E A 1

A A/1 B/0

Esercizio

Minimizzare l’automa di cui di seguito è riportata la tabella di flusso

A A/1 B/0

B C/1 D/0

C C/1 B/0

D B/0 C/1

A A/1 B/0

B C/1 D/0

C C/1 B/0

Π0(Q)={A,B,C,D}

Soluzione

C C/1 B/0

D B/0 C/1

Metodo delle partizioni:(i)ω (x, q ) = ω (x, q ') (equicomportamento)

(ii)δ(x, q ) ≡δ (x, q ')(passo induttivo)

A A/1 B/0

B C/1 D/0

C C/1 B/0

Π0(Q)={A,B,C,D}

Π1(Q)={A}

Soluzione

C C/1 B/0

D B/0 C/1

Partizioniamo l’insieme di stati di partenza in funzione

dell’output prodotto

A A/1 B/0

B C/1 D/0

C C/1 B/0

Π0(Q)={A,B,C,D}

Π1(Q)={A,B}

Soluzione

C C/1 B/0

D B/0 C/1

A A/1 B/0

B C/1 D/0

C C/1 B/0

Π0(Q)={A,B,C,D}

Π1(Q)={A,B,C}

Soluzione

C C/1 B/0

D B/0 C/1

A A/1 B/0

B C/1 D/0

C C/1 B/0

Π0(Q)={A,B,C,D}

Π1(Q)={A,B,C}

Soluzione

C C/1 B/0

D B/0 C/1

A A/1 B/0

B C/1 D/0

C C/1 B/0

Π0(Q)={A,B,C,D}

Π1(Q)={A,B,C} , {D}

Soluzione

C C/1 B/0

D B/0 C/1

0 1 Π1(Q)={A,B,C}, {D}

Soluzione

A A/1 B/0

B C/1 D/0

C C/1 B/0

D B/0 C/1

Π (Q)={A,B,C}, {D}

= {αααα}, {γγγγ}

δ(0, A ) =A ovvero {αααα},

eδ(0, B)= C ovvero {αααα}

δ(1, A ) =B ovvero {αααα},

mentre

δ(1, B)= D ovvero {γγγγ}

Quindi A non è equivalente a B anche

Soluzione

A A/1 B/0

B C/1 D/0

C C/1 B/0

D B/0 C/1

Quindi A non è equivalente a B anche

se produce lo stesso output pertanto

devo ulteriormente partizionare

l’insieme

Π2(Q)={A,C }, { B}, {D}

1) Cosa deve accadere perché due stati A e B di un automa di Mealy siano equivalenti ?

2) Se viene applicata una stessa sequenza di ingressi a due stati equivalenti di un

Rispondere alle seguenti domande

Esercizio

2) Se viene applicata una stessa sequenza di ingressi a due stati equivalenti di un automa cosa si ottiene ?

3) Data la seguente tabella di flusso, dire perché A non è equivalente a D

A A/1 B/0

B C/1 D/0

C C/1 B/0

D B/0 C/1

4) Data la seguente tabella di flusso, dire quale tra le seguenti relazioni di equivalenza è vera.

a) A≡C

b) B≡C

Esercizio

b) B≡C0 1

A A/1 B/0

B C/1 D/0

C C/1 B/0

D B/0 C/1

Esercizio

Sia data la tabella di transizione seguente dove

X={a,b} Y={0,1} Q={q0, q1, …q7 }

Minimizzare l’automa

___________________________

q0 q1/1 q7/1

q1 q5/1 q3/1

q2 q3/0 q4/1

q3 q2/0 q5/1

q4 q3/1 q2/1

q5 q2/1 q2/1

q6 q2/1 q3/1

q7 q2/0 q0/1

Soluzione

_______________

qE qF/1 qH/1

qF qD/1 qG/1

qD qG/1 qG/1

qG qG/0 qD/1

qH qG/0 qD/1

Riepilogo 1

• AUTOMI:

sono sistemi astratti in grado di modellare il comportamento delle reti sequenziali,

(in genere un automa è un dispositivo che esegue in modo autonomo un particolare compito, sulla base di ordini ricevuti)

• AUTOMA DI MEALY:

è caratterizzato dal fatto che l’uscita al tempo t, oltre che dallo stato, dipende anche dagli ingressi nello stesso istante, in pratica:zt=ωωωω(xt,qt).

• AUTOMA DI MOORE:

è caratterizzato dal fatto che l’uscita al tempo t dipende esclusivamente dal valore assunto dallo stato, in pratica:zt=ωωωω’(qt).

• DIAGRAMMI DEGLI STATI:

Riepilogo 2

q δ (x, q)

x / ω(x, q)

q/ω(q) δ (x, q)

• TABELLE DI FLUSSO:

ingressi x

Mealyq δ (x,q) / ω (x,q)

ingressi x

Mooreq δ (x,q) ω(q)

Mealy Moore

• STATI EQUIVALENTI:

Due automi dello stesso tipo A e A’ sono equivalenti se per ogni stato s di A esiste uno stato s’ di A’ equivalente ad s e viceversa.

• MINIMIZZAZIONE ASF:

Il processo di minimizzazione degli stati di un automa

Riepilogo 3

Il processo di minimizzazione degli stati di un automa consiste nei seguenti 3 passi:

-trovare una partizione di stati dell’automa suddivisi in

classi di equivalenza avente cardinalità minima.

-scegliere un solo stato per ciascuna classe della partizione

-sostituire ciascuna classe con il solo stato (nodo) scelto

(utilizzando la tecnica della fusione).

L’automa minimo è unico (ha tanti stati quante sono le classi di indistinguibilità)

Reti Logiche 1 - uniroma2.it · 22/06/2010 Corso di Reti Logiche 2005/06 14 Ma il sistema oltre a...

Documents

Transcript of Reti Logiche 1 - uniroma2.it · 22/06/2010 Corso di Reti Logiche 2005/06 14 Ma il sistema oltre a...

Algebra di Boole e reti combinatorie - di-srv.unisa.it · ... algebra di Boole e circuiti combinatori ... Corrispondenza fra funzioni logiche e reti logiche: Analisi: ... Algebra

Reti logiche (1) - home page | DEI · 1 1 Reti logiche (1) Algebra booleana e circuiti combinatori 2 Un quadro della situazione In particolare gli argomenti qui trattati interessano

RETI LOGICHE (Baldoni) - pmar.it · RETI LOGICHE SECONDA PROVA SCRITTA DELL'APPELLO DEL 14/04/97 Cognome:_____ Nome:_____ ***** D1 Descrivere la tecnica per aggiungere ad un pacchetto

Reti Logiche T Esercizi reti sequenziali asincronevision.deis.unibo.it/downloads/retilogiche/preparazione_esame_RSA.pdf · Reti Logiche T Esercizi reti sequenziali asincrone ESERCIZIO

Esercizi e Complementi di Reti Logiche - T3LAB · gates (vedi reti logiche) - In alcuni casi le alee possono essere filtrate dagli stessi gates (ad esempio nel caso di ‘lentezza’dei

Cenni alle reti logiche - dit.unitn.itpalopoli/courses/Calc/CalcLect3.pdf · Cosa sono le reti logiche? • Fino%ad%ora%abbiamo%visto%! Rappresentazione%dell’informazione%! Assembler

I circuiti digitali: dalle funzioni logiche ai circuiti ......prima di guardare l’output sufficientemente ampio per permettere a tutti i circuiti la commutazione). ... Identità

Architettura dei Calcolatori 02 Introduzione Alle Reti Logiche

Appunti di reti logiche

Reti logiche: introduzione - wpage.unina.itwpage.unina.it/.../pdf/CE1-2017-L20_reti_logiche_intro.pdf · Alessandro Cilardo –Architettura del calcolatore Circuiti e porte logiche

RETI LOGICHE T - unibo.itvision.deis.unibo.it/downloads/retilogiche/Ese_3_Sincrone.pdf · RETI LOGICHE T Ingegneria Informatica Esercitazione 3 Reti Sequenziali Sincrone Marco Lippi

Corso di Reti Logiche - wpage.unina.itwpage.unina.it/acilardo/rl/MinimizzazioneStatiMacchineSequenziali.pdf · Alessandro Cilardo – Corso di Reti Logiche 2 Le Macchine o Automi

Reti logiche sequenziali - diit.unict.it · Calcolatori Elettronici 3 Prof. Giuseppe Ascia Reti logiche sequenziali In un generico istante ti l’informazione relativa al contenuto

LSS 2017-18 Reti Logiche: introduzione ad Arduinovignatim/didattica/LabSisSeg17/LSS_Arduino_Int… · Reti Logiche: introduzione ad Arduino Piero Vicini (slides teoria: Prof. A. Nigro)

Reti Logiche: Combinatorie e Sequenziali - Home ...tonelli/baiardi/didattica/retilogiche.pdf · 3 F.Baiardi -- AE: Reti Logiche Combinatorie e Sequenziali Matematica Finita • Una

LSS 2014-15 Reti Logiche - Istituto Nazionale di Fisica ... · Reti Logiche PieroVicini A.A.2014-2015. Circuiticombinatorivssequenziali L’outputdiuncircuitocombinatorioe’solofunzionedelvalore

Reti Logiche AW.Fornaciari Sintesi FSM – Prima parte Reti Logiche.

Reti Logiche Domande Orali

Progetto di Reti Logiche A: filtro gaussiano - dresd.org · 3 Progetto di Reti Logiche A: filtro gaussiano Revisioni Data Versione Stato Commento 5/6/2005 1.0 Draft Prima stesura

Reti logiche: analisi, sintesi e minimizzazione Esercitazione · Punto della situazione •Stiamo studiando le reti logiche costruite a partire dalle porte logiche AND, OR, NOT per

RETI LOGICHE (Baldoni) - pmar.it · RETI LOGICHE SECONDA PROVA SCRITTA DELL'APPELLO DEL 14/04/97 Cognome:_ Nome:_ ***** D1 Descrivere la tecnica per aggiungere ad un pacchetto