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 M₁=(I₁,Q₁,U₁,τ₁,ω₁), M₂=(I₂,Q₂,U₂,τ₂,ω₂) opportunamente collegate costituiscono una rete unica M=(I,Q,U,τ,ω).

Partizionamento degli stati

Progetto per decomposizione

• Decomposizione di M=(I,Q,U,τ,ω):
  • Trovare, se esistono, due macchine, M₁=(I₁,Q₁,U₁,τ₁,ω₁) e M₂=(I₂,Q₂,U₂,τ₂,ω₂), con Q⊆Q₁×Q₂.
  • Trovare un modo di collegare M₁ ed M₂ (e quindi definire I,Q,U,τ,ω delle due macchine) per realizzare una macchina M_c=(I,U,Q₁×Q₂,τ_c,ω_c) ⊇ M

Partizionamento degli stati

Premesse

• Partizione su Q: suddivide l’insieme Q in “blocchi” disgiunti
• P₀: 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 P₁×P₂=P₀ e M₁,M₂ sono associate rispettivamente a P₁,P₂ allora M₁,M₂ possono essere le componenti di una decomposizione di M
• Risulta infatti così Q⊆Q1×Q2. condizione essenziale per decomporre M in M₁,M₂

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

• 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

Insiemi autodipendenti

Decomposizione per insiemi autodipendenti

• Variabili di stato “autodipendenti”
  • Un sottoinsieme Y₁⊂Y si dice autodipendente se ogni variabile y_iεY₁ può essere ottenuta indipendentemente dalle variabili y_j∉Y₁, 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

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.

Prossima lezione

Esercitazione di riepilogo