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