Vai alla Home Page About me Courseware Federica Living Library Federica Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica
 
 
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