Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Bruno Fadini » 19.Minimizzazione delle macchine sequenziali. Teoria - Modulo 4


Reti logiche

Minimizzazione delle macchine sequenziali. Teoria.

Argomenti

  • Macchine complete ed incomplete
  • Equivalenza
  • Compatibilità ed inclusione
  • Minimizzazione degli stati
  • Algoritmi di minimizzazione

Macchine complete e incomplete

Applicabilità di una sequenza

  • Una sequenza di ingressi J è applicabile a M in q – si dice a M(q) – se è definita u=λ(q, J), la funzione che fornisce l’uscita u che si ottiene applicando alla macchina la sequenza di ingressi J a partire da uno “stato iniziale” q.
  • Se la funzione di uscita λ è definita ovunque, la macchina si dice completa, incompleta altrimenti
  • Per le macchine incomplete esistono sequenze non applicabili

Equivalenza

Stati equivalenti (macchine complete)

  • Due stati (della stessa macchina o di macchine diverse) sono equivalenti se producono la stessa sequenza di uscite per qualsiasi sequenza di ingressi
  • Definizione ricorsiva
    • Due stati sono equivalenti se, per ciascun ingresso sono eguali le uscite e sono equivalenti gli stati successivi

Macchine equivalenti (complete)

Due macchine complete M e M’ sono equivalenti se per ciascuno stato q di M esiste almeno uno stato q’ di M’ ad esso equivalente e viceversa

Macchine equivalenti (incomplete)

  • Non tutte le sequenze di ingresso sono applicabili
  • Il concetto è sostituito da quelli di Compatibilità tra stati ed inclusione tra macchine

Compatibilità ed inclusione

Compatibilità fra stati

  • Due stati sono compatibili se per ogni sequenza di ingressi applicabile ad entrambi, le uscite prodotte sono identiche.
  • La compatibilità NON è una relazione di equivalenza
    • Non gode della proprietà transitiva; p.e.: q1~q2, q2~q3, l(q1,J)=a, , l(q2,J)=-, l(q3,J)=b

Definizione ricorsiva

  • Due stati sono compatibili se sono eguali le uscite per ciascun ingresso applicabile e compatibili gli stati successivi (se definiti)
  • Per le macchine complete la compatibilità è l’equivalenza

Compatibilità ed inclusione

Inclusione fra macchine

  • Concettualmente: una macchina include un’altra se “fa qualcosa in più”
  • Formalmente:
    • M’(q’) include M(q): M’(q’) ⊇ M(q) ⇔ ∀(J applicabile a M(q)) : λ(q’,J)=λ(q,J)
    • M’ include M: M’⊇ M ∀(q∈M) ∃ (q’∈M’) : M’(q’) ⊇ M(q)

Minimizzazione degli stati

Minimizzazione e classi di equivalenza

  • Data una macchina M se ne vuole trovare una equivqlente, M’, con un numero minimo di stati.
  • La famiglia delle classi di equivalenza degli stati di M è la soluzione: M’ ha uno stato per ogni elemento C della famiglia con:
    • uscita: pari alla uscita degli elementi di C, tutti eguali per essere questi equivalenti fra loro,
    • stato seguente: quello determinato da C stesso; essendo infatti gli stati di Ci equivalenti fra loro, devono avere tutti per seguenti stati equivalenti e quindi appartenere ad un unico elemento C’ della famiglia delle classi di equivalenza.
    • M’ ha un numero di stati minimo, per le proprietà delle classi di equivalenza.

Minimizzazione degli stati

Minimizzazione e classi di compatibilità massime

  • Per le macchine incomplete, proprietà analoghe a quelle delle classi di equivalenza, ma più complesse, hanno le classi di compatibilità massime – vedi approfondimenti
  • Si procede analogamente, con le seguenti peculiarità:
    • M’ include M (non è equivalente)
    • La soluzione potrebbe non essere minima, ma in generale presenta una macchina a “stati ridotti”
    • Si possono avere più soluzioni, potendo uno “stato seguente” essere incluso in più elementi distinti della famiglia di compatibilità massima

Minimizzazione degli stati

Classi di equivalenza e di compatibilità

  • Ne segue che per minimizzare occorre ricercare le classi di equivalenza (macchine complete) o gli insiemi di compatibilità massima (macchine incomplete)
  • Diversi metodi
    • Algoritmo del partizionamento (o suddivisione degli elementi per macchine incomplete)
    • Row merging (macchine complete)
    • Paull-Unger (preferibile per macchine complete)

Algoritmi di minimizzazione

Il partizionamento degli stati

Si potrebbe procedere così:

  • Si ritiene in partenza che l’insieme di stati Q costituisca una famiglia F={Q} di stati “presumibilmente equivalente”.
  • Si individuano in Q le disequivalenze e Q si partiziona in più sottoinsiemi, Q1,Q2,… disgiunti (Qi∩Qj = ∅);
  • Si assume quindi F={Q1,Q2,…}, proseguendo iterativamente sui sottoinsiemi, finché non esistono più disequivalenze.
  • Per la ricerca delle disequivalenze si opera come segue:
    1. Si cercano disequivalenze a causa delle uscite,
    2. Iterativamente, sii cercano disequivalenze a causa deglii stati seguenti, calcolando per ogni elemento di F l’insieme degli stati seguenti e verificando se questo è incluso nella famiglia F

Algoritmi di minimizzazione

La famiglia presumibilmente compatibile

Per le reti incomplete si procede come in precedenza, adattando l’algoritmo alle peculiarità della incompatibilità:

  • F={Q} è la famiglia di “presunta massima compatibilità”.
  • Invece di un partizionamento di Q, accertato che q1~q2, si pone Q1=Q-q1, Q2=Q-q2 e quindi Q1∩Q2 ≠ ∅).

Algoritmi di minimizzazione

Il row merging (solo per reti complete)

  • Due righe della tabella di stato, se si riconoscono equivalenti, possono essere “fuse”:
    • Una delle due scompare
    • Il riferimento nelle righe rimaste alla riga scomparsa è sostituito da un riferimento alla riga equivalente rimasta

Algoritmi di minimizzazione

Metodo di Paull-Unger (preferito per reti complete)

  • Organizza il procedimento in una matrice diagonale, dove gli elementi sono le coppie di stati e contengono:
    1. Il simbolo di non equivalenza (X) se la coppia è caratterizzata da usite diverse per almeno uno degli ingressi
    2. Le coppie di stati condizionanti l’equivalenza se non è possible segnarle immediatamente come X oppure ~
  • Per le caselle di tipo 2 si procede poi iterativamente, segnando con X le caselle contenenti coppie già riconosciute disequivalenti.

Al termine, le caselle senza X sono di coppie equivalenti: a queste poi si deducono le classi di equivalenza.

Prossima lezione

Minimizzazione delle macchine sequenziali. Esempi ed esercizi

I materiali di supporto della lezione

B. Fadini, A. Esposito, Teoria e Progetto delle Reti Logiche, Napoli Liguori Ed., II ed, 1994. Cap. VI

U. De Carlini, B. Fadini, Macchine per l'elaborazione delle informazioni, Napoli Liguori Ed., II ed., 1995 (Capitoli III e VII)

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion