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 » 24.Sistemi complessi e decomposizione - Modulo 4


Reti logiche

Sistemi complessi e decomposizione

Argomenti

  • Divide et impera
  • Collegamento fra macchine sequenziali
  • Partizionamento degli stati
  • Esempio di decomposizione seriale
  • Insiemi autodipendenti
  • Progetto con componenti standard
  • Reti collegate gerarchicamente

Divide et impera

  • Tendenza all’aumento della complessità dei sistemi in termini di funzionalità offerte
  • Meglio controllare molti progetti semplici che non uno complesso
  • Scomposizione di un sistema complesso in sottosistemi in grado di operare in cooperazione fra loro
  • Nel contesto delle reti sequenziali, due reti M1=(I1,Q1,U111), M2=(I2,Q2,U222) opportunamente collegate costituiscono una rete unica M=(I,Q,U,τ,ω).

Collegamento fra macchine sequenziali

Parallelo

Rete combinatoria per l’elaborazione delle uscite

Seriale (Serie-Parallelo)

  • In parallelo nel tempo
  • In serie nello spaziio

M1=(I1,Q1,U111), M2=(I2,Q2,U222) opportunamente collegate mostrano il comportamento di una macchina M=(I,Q1×Q2,U,τ,ω).


Partizionamento degli stati

Progetto per decomposizione

  • Decomposizione di M=(I,Q,U,τ,ω):
    • Trovare, se esistono, due macchine, M1=(I1,Q1,U111) e M2=(I2,Q2,U222), con Q⊆Q1×Q2.
    • Trovare un modo di collegare M1 ed M2 (e quindi definire I,Q,U,τ,ω delle due macchine) per realizzare una macchina Mc=(I,U,Q1×Q2cc) ⊇ M

Partizionamento degli stati

Premesse

  • Partizione su Q: suddivide l’insieme Q in “blocchi” disgiunti
  • P0: ogni blocco è di un solo stato di Q (partizione banale)
  • Partizione chiusa: l’insieme degli stati seguenti del blocco è incluso in un blocco della partizione
  • Prodotto di due partizioni, P1 e P2: partizione che si ottiene da tutte le intersezioni possibili fra i blocchi di P1 e quelli di P2
  • Macchina associata ad una partizione: ogni stato della macchina è un gruppo delle partizioni

Teorema

  • Se P1×P2=P0 e M1,M2 sono associate rispettivamente a P1,P2 allora M1,M2 possono essere le componenti di una decomposizione di M
  • Risulta infatti così Q⊆Q1×Q2. condizione essenziale per decomporre M in M1,M2

Partizionamento degli stati

Decomposizione seriale e parallela

  • Decomposizione seriale
    • Se solo una delle tra P1 e P2 è chiusa esiste una decomposizione seriale di M.
  • Decomposizione parallela
    • Se P1 e P2 sono entrambe chiuse esiste una decomposizione parallela di M

Esempio di decomposizione seriale

Riconoscitore di codice 8-4-2-1

Si può realizzare usando un contatore che effettui il conteggio dei 4 bit.


Esempio di decomposizione seriale

  • La partizione (0; 1; 2,3; 4,5) è chiusa
  • La macchina ad essa associata cicla fra gli stati ordinatamente associati ai blocchi → contatore
  • Occorre trovare una seconda partizione, tale che il suo prodotto con la prima sia la partizione nulla;
    • (0,1,2,4; 3,5) oppure (0,1,2,5; 3,4)
    • P1 = (0;1;2,3;4,5). P2 = (0,l,2,4;3,5)
  • Poichè solo P1 è chiusa la decomposizione è seriale

Esempio di decomposizione seriale

Q1= {a, b, c, d }; Q2= {A, B}

a=(0) b=(1) c=(2,3) d=(4,5)

A=(0,1,2,4) B=(3,5)

La coppia (a,A) individua S0, (b,A) individua S1, etc…..


Esempio di decomposizione seriale

Il progetto si completa con la codifica degli stati (a,b,c,d) e (A,B)


Insiemi autodipendenti

Decomposizione per insiemi autodipendenti

  • Variabili di stato “autodipendenti”
    • Un sottoinsieme Y1⊂Y si dice autodipendente se ogni variabile yiεY1 può essere ottenuta indipendentemente dalle variabili yj∉Y1, sempre di Y.
  • Il sottoinsieme Y1 definisce una sottorete M1
    • primo passo per la decomposizione di M.
    • Occorre poi verificare se l’insieme Y2= Y-Y1 è autodipendente.
      • SI → decomposizione parallela
      • NO→ decomposizione seriale

Progetto con componenti standard

Considerazioni generali

  • Riduzione dei costi di produzione
  • Richiede maggiore esperienza del progettista
  • Componenti più diffusi
    • Contatori
    • Registri a scorrimento

Progetto con componenti standard

Reti con registri a scorrimento

  • Se le uscite di una rete sono funzione solo degli ingressi negli istanti (t, t-1, …, t-n) definiti dal segnale di sincronismo, allora si possono usare shift-register binari di lunghezza n in cui memorizzare gli ingressi ed una rete combinatoria per elaborarli.
  • Un contatore può essere utile

Progetto con componenti standard

Esempio

Comparatore seriale fra due stringhe di bit di lunghezza n può essere realizzato con due registri a scorrimento che memorizzano dette stringhe ed un comparatore combinatorio che le confronta.

Reti collegate gerarchicamente

Un modello di collegamento fra reti è quello gerarchico:

  • Reti di livello superiore avvjano quelle di livello eferiore ed attendono da queste l’indicazione di completamento dell’operazione richiesta
  • Questi schemi consentono anche l’esecuzione di operazioni in parallelo mediante attivazione simultanea di più reti.

Prossima lezione

Esercitazione di riepilogo

I materiali di supporto della lezione

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

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