A.S.E.A.S.E. 12.12.11
ARCHITETTURA DEI SISTEMI ARCHITETTURA DEI SISTEMI ELETTRONICIELETTRONICILEZIONE N° 12LEZIONE N° 12
• Teorema di SHENNONTeorema di SHENNON• Implicanti, Inclusivi, Implicanti PrincipaliImplicanti, Inclusivi, Implicanti Principali• Mappe di KarnaughMappe di Karnaugh• Sintesi ottimaSintesi ottima• Esempio di minimizzazioneEsempio di minimizzazione• Considerazioni su soluzioni diverseConsiderazioni su soluzioni diverse• Tecniche strutturate di minimizzazioneTecniche strutturate di minimizzazione• Sintesi a due livelliSintesi a due livelli• Sintesi a più di due livelliSintesi a più di due livelli• Reti a più usciteReti a più uscite
A.S.E.A.S.E. 12.12.22
Teorema di espansione di Teorema di espansione di ShannonShannon
• Data la funzioneData la funzione
• Vale la seguente uguaglianzaVale la seguente uguaglianza
• OvveroOvvero
ni xxxxf ,....,,.....,, 21
ninini xxxfxxxxfxxxxxf ,..,1,..,,,..,0,..,,,..,,..,, 212121
ninini xxxfxxxxfxxxxxf ,..,0,..,,,..,1,..,,,..,,..,, 212121
A.S.E.A.S.E. 12.12.33
EsempioEsempio
• Data la funzioneData la funzione
• RisultaRisulta zywxxwzyxwf )(,,,
)()(
)0(1)1(0
)0(0)1(1
,,0,,,1,,,,
yzwxzywx
zywwxzywwx
zywwxzywwx
zywfxzywfxzyxwf
A.S.E.A.S.E. 12.12.44
OsservazioneOsservazione
• Applicando in modo iterativo il teorema di Applicando in modo iterativo il teorema di ShannonShannon
• Quindi il teorema di Shennon consete di Quindi il teorema di Shennon consete di ricavare sempre la forma SPricavare sempre la forma SP
1,....,1,1,1....1,....,1,1,0....
1,1,...,0,0,0...0,1,....,0,0,0...1,....,0,0,0....0,....,0,0,0....
,....,,1,1,....,,0,1,....,,1,0,....,,0,0
,....,,1,....,,0,....,,
321321
13211321
321321
321321
321321
212121
fxxxxfxxxx
fxxxxxfxxxxxfxxxxfxxxx
xxfxxxxfxxxxfxxxxfxx
xxfxxxfxxxxf
nn
nnnn
nn
nn
nn
nnn
A.S.E.A.S.E. 12.12.55
EsempioEsempio
• Data la funzioneData la funzione
• RisultaRisulta zyxyxzyxf )(,,
xyzzyxyzxzyxzyx
xyzzxyzyxzyxyzxzyxzyxzyx
xyzzxyzyxzyxyzxzyxzyxzyxzyxwf
)1)11(00()0)11(00()1)01(01()0)01(01()1)10(10()0)10(10()1)00(11()0)00(11(
)1)11(11()0)11(11()1)01(01()0)01(01()1)10(10()0)10(10()1)00(00()0)00(00(,,,
A.S.E.A.S.E. 12.12.66
ImplicantiImplicanti
• Date due funzioni Date due funzioni ff11 e e ff22 di di nn variabili variabili
• ff11 implicaimplica ff22 se non c’è un assegnazione di se non c’è un assegnazione di valori alle valori alle nn variabili tale che risulti variabili tale che risulti ff11 =1 e =1 e ff22 =0 =0
• Per funzioni booleane Per funzioni booleane completamente definitecompletamente definite
• Se Se ff11 vale vale 11 anche anche ff22 vale vale 11 – (Il fatto che (Il fatto che ff11 vale vale 11 implicaimplica che anche che anche ff22 vale vale 11))
• Ovvero Se Ovvero Se ff22 vale vale 00 anche anche ff11 vale vale 00
A.S.E.A.S.E. 12.12.77
Esempio 1Esempio 1
• Per Per zxyzxyzyxf
yzxyzyxf
,,,,
2
1
xx yy zz ff11 ff2200 00 00 00 0000 00 11 00 1100 11 00 00 0000 11 11 11 1111 00 00 00 0011 00 11 00 0011 11 00 11 1111 11 11 11 11
A.S.E.A.S.E. 12.12.88
Esempio 2Esempio 2
• Per Per ))((,,
))()((,,4
3zyyxzyxf
zxzyyxzyxf
xx yy zz ff33 ff4400 00 00 00 0000 00 11 00 0000 11 00 11 1100 11 11 11 1111 00 00 00 0011 00 11 11 1111 11 00 00 1111 11 11 11 11
A.S.E.A.S.E. 12.12.99
OsservazioneOsservazione
• Per una Per una ff funzione nella forma funzione nella forma SPSP– Ogni termine di prodotto è Ogni termine di prodotto è
implicante di implicante di ff
• Per una Per una ff funzione nella forma funzione nella forma PSPS– La funzione La funzione ff è implicante di ciascun è implicante di ciascun
temine di sommatemine di somma
)( 21 nxxx
)( 21 nxxx
A.S.E.A.S.E. 12.12.1010
InclusioneInclusione
• Dati due termini di prodotto Dati due termini di prodotto pp11 e e pp22– pp11 includeinclude pp22 se e solo se tutti i letterali di se e solo se tutti i letterali di pp22 sono sono
presenti in presenti in pp11
• Dati due termini di somma Dati due termini di somma ss11 e e ss22– ss11 includeinclude ss22 se e solo se tutti i letterali di se e solo se tutti i letterali di ss22 sono sono
presenti in presenti in ss11
• Se Se pp11 include include pp22 allora allora pp11 implica implica pp22• Se Se ss11 include include ss22 allora allora ss22 implica implica ss11
A.S.E.A.S.E. 12.12.1111
EsempioEsempio
• Il termine di prodottoIl termine di prodotto• IncludeInclude il termine di prodotto il termine di prodotto• Quindi Quindi implicaimplica
• Il temine di sommaIl temine di somma• IncludeInclude il termine di somma il termine di somma• Quindi Quindi implicaimplica
yxp 2
zyxp 1
1p 2p
zyxs 1
zxs 2
2s 1s
A.S.E.A.S.E. 12.12.1212
Implicanti principaliImplicanti principali
• OsservazioniOsservazioni– Tutti i termini di prodotto di una funzione Tutti i termini di prodotto di una funzione
booleana, nella forma SP, sono implicati della booleana, nella forma SP, sono implicati della funzionefunzione
– Tutti i mintermini di una funzione sono Tutti i mintermini di una funzione sono implicantiimplicanti
• Un termine di prodotto che è implicante di Un termine di prodotto che è implicante di una funzione è detto una funzione è detto Implicante Principale Implicante Principale se non include nessun altro implicate della se non include nessun altro implicate della funzione con un numero minore di letteralifunzione con un numero minore di letterali
A.S.E.A.S.E. 12.12.1313
EsempioEsempio
• Per la funzione definita dalla tabella di verità Per la funzione definita dalla tabella di verità • Sono implicati diSono implicati di
• I termini I termini
non sono implicanti principalinon sono implicanti principali• I terminiI termini
implicanti principaliimplicanti principali
( include , include ( include , include
xx yy zz ff00 00 00 1100 00 11 1100 11 00 1100 11 11 1111 00 00 0011 00 11 1111 11 00 0011 11 11 00
zyxzyx e
zyx e
zyzyxxzyx ,,,
f
zyzyxxzyx
A.S.E.A.S.E. 12.12.1414
Sintesi ottimaSintesi ottima
• È necessario definire una funzione È necessario definire una funzione COSTOCOSTO da da minimizzareminimizzare
• Definiti Definiti letteraliletterali le variabili dirette o le variabili dirette o complementate presenti in una funzionecomplementate presenti in una funzione
• Date due forme diverse della stessa funzione Date due forme diverse della stessa funzione • La forma “La forma “AA ” ha un costo minore della ” ha un costo minore della
funzione “funzione “BB ” se ” se AA contiene meno letterali. contiene meno letterali.• Minimizzare una funzione vuol dire trovare la Minimizzare una funzione vuol dire trovare la
forma con meno letteraliforma con meno letterali• Si possono definire altre funzioni COSTO in Si possono definire altre funzioni COSTO in
funzione della tecnologia realizzativafunzione della tecnologia realizzativa
A.S.E.A.S.E. 12.12.1515
Ottimizzazione mediante le Ottimizzazione mediante le Mappe di KarnaughMappe di Karnaugh
• Passo 1Passo 1• individuare sulla mappa individuare sulla mappa tuttitutti gli implicanti gli implicanti
di ordine superiore possibile che coprono di ordine superiore possibile che coprono tutta la funzionetutta la funzione
• Passo 2Passo 2• Scegliere un insieme Scegliere un insieme più piccolo possibilepiù piccolo possibile
di implicanti principali che coprono la di implicanti principali che coprono la funzionefunzione
• NOTANOTA• L’ottimizzazione si fa per ispezione visivaL’ottimizzazione si fa per ispezione visiva
A.S.E.A.S.E. 12.12.1616
Esempio Esempio
• Per la funzione prima vista :Per la funzione prima vista :
• si ha:si ha:
• La scelta 3 da luogo ad una funzione La scelta 3 da luogo ad una funzione migliore delle altremigliore delle altre
11101111101
1100
10110100abcd
bcdacacbz
11101111101
1100
10110100abcd
11101111101
1100
10110100abcd
A.S.E.A.S.E. 12.12.1717
Esempio di minimizzazioneEsempio di minimizzazione
• Data la funzione precedentemente vista:Data la funzione precedentemente vista:
aa bb cc zz
00 00 00 11
00 00 11 00
00 11 00 11
00 11 11 00
11 00 00 11
11 00 11 11
11 11 00 11
11 11 11 00
Si ha:
bacz
0000 0101 1111 1010
00 11 11
11 11 11 11
a
b, c
A.S.E.A.S.E. 12.12.1818
Condizioni non specificateCondizioni non specificate
» Può capitare che in particolari applicazioni alcune Può capitare che in particolari applicazioni alcune configurazioni degli ingressi non si possano configurazioni degli ingressi non si possano verificare, quindi l’uscita per tali uscite non è verificare, quindi l’uscita per tali uscite non è specificata (specificata (Don’t-Care ConditionsDon’t-Care Conditions))
» Se i Se i don’t caredon’t care si considerano “0” si ottiene si considerano “0” si ottiene la prima funzionela prima funzione
» Se i Se i don’t caredon’t care si considerano “1” si ottiene si considerano “1” si ottiene la seconda funzionela seconda funzione
01111
0111
11011
10011
01101
00101
11001
0001
11110
00110
01010
00010
1100
10100
11000
10000
zdcba
110
1111
101
11100
10110100
ab
cdbcdadcacabdbacbaz
cacdabaz
A.S.E.A.S.E. 12.12.1919
Un cattivo esempioUn cattivo esempio
0001111110011111010110000011101110101101010111001101000110111100110110011101010100100001100110010011010000000000uwzdcba
11101111
11011100
10110100abcd wzwzwzu
dcbau
cdbadcbadabcdcabcdbadcbadcbadcbau
bababaz
dcdcdcw
A.S.E.A.S.E. 12.12.2020
Tecniche strutturateTecniche strutturate
• Il procedimento di sintesi per “ispezione Il procedimento di sintesi per “ispezione visiva” si può utilizzare fino a 4 ÷visiva” si può utilizzare fino a 4 ÷ 5 variabili5 variabili
• Il procedimento di sintesi per “ispezione Il procedimento di sintesi per “ispezione visiva” può essere anche descritto come visiva” può essere anche descritto come processo formale strutturato processo formale strutturato
• Metodo di Quine McCluskeyMetodo di Quine McCluskey• Può essere tradotto in un programmaPuò essere tradotto in un programma• La complessità del programma cresce in La complessità del programma cresce in
modo esponenziale con l’aumentare delle modo esponenziale con l’aumentare delle variabilivariabili
• I programmi attuali usano tecniche I programmi attuali usano tecniche euristicheeuristiche
A.S.E.A.S.E. 12.12.2121
Livelli di logicaLivelli di logica
• Data una rete combinatoriaData una rete combinatoria
• DefinizioneDefinizione• Livelli di logica della rete = numero MAX di blocchi base Livelli di logica della rete = numero MAX di blocchi base
attraversati passando da un ingresso a una uscutaattraversati passando da un ingresso a una uscuta
• NOTANOTA• La negazione degli ingressi non contaLa negazione degli ingressi non conta
db
a
c
g
y
x
1
23
4
A.S.E.A.S.E. 12.12.2222
Sintesi a due livelliSintesi a due livelli
• Le tecniche fin ora viste sono di sintesi a Le tecniche fin ora viste sono di sintesi a due livellidue livelli
11110111111
01100
10110100abcd
dcbaadacabz
a
z
d
c
b
A.S.E.A.S.E. 12.12.2323
Sintesi a tre livelliSintesi a tre livelli
• Si usa un numero inferiore di porte e con Si usa un numero inferiore di porte e con meno ingressimeno ingressi
11110111111
01100
10110100abcd
dcbadcba
dcbaadacabz
a
zdc
b
A.S.E.A.S.E. 12.12.2424
Reti a più usciteReti a più uscite
• Casi vistiCasi visti• più ingressi una uscitapiù ingressi una uscita
• Tecniche di minimizzazione visteTecniche di minimizzazione viste• Una sola uscitaUna sola uscita
• Casi frequenti nella praticaCasi frequenti nella pratica• più ingressi più uscitepiù ingressi più uscite
• La minimizzazione delle singole uscite La minimizzazione delle singole uscite (separatamente) non garantisce la (separatamente) non garantisce la minimizzazione dell’intera reteminimizzazione dell’intera rete
• Il procedimento di minimizzazione Il procedimento di minimizzazione globale risulta molto complessoglobale risulta molto complesso
A.S.E.A.S.E. 12.12.2525
EsempioEsempio
• Rete a due usciteRete a due uscite• zz ww
11110
10110100acd
11110
10110100acd
addcz cadcw
dcdcaw
addcaz
A.S.E.A.S.E. 12.12.2626
ConclusioniConclusioni
• Sintesi ottimaSintesi ottima• Esempio di minimizzazioneEsempio di minimizzazione• Considerazioni su soluzioni diverseConsiderazioni su soluzioni diverse• Tecniche strutturate di minimizzazioneTecniche strutturate di minimizzazione• Sintesi a due livelliSintesi a due livelli• Sintesi a più di due livelliSintesi a più di due livelli• Reti a più usciteReti a più uscite