A hie adeg

5 - Sintesi di Reti Combinatorie

Ugo DalLago

DipartimentodiS ienzedell'Informazione

UniversitàdegliStudidiBologna

Anno A ademi o2007/2008

◮

Supponiamodi voler ostruireuna rete ombinatoria he

soddis erteproprietà.

◮

Primadi tutto: ome possiamo spe i areil omportanento

he larete ombinatoriadeve avere?

◮

Ciò he i interessaè ilsuo omportamentofunzionale.

◮

Larete ombinatoriadovrà avereun ertonumeromdi

entrate.

◮

Larete ombinatoriadovrà avereun ertonumerondi us ite.

◮

Ilsuo omportamentoattesosaràpoispe i atotramiten

funzionibooleaneinmvariabili.

◮

Sappiamo poi hedata unafunzione booleanaesistesempre il

modo di ostruire un'espressionebooleanaad essa

orrispondente e,da quest'ultima,sipassa fa ilmente aduna

rete ombinatoria.

◮

Non èperò hiarose ilnumero totaledi portelogi he

impiegate siain qual hesenso minimale.

A B C 0 0 0 0 0 1 0 1 0 0 1 1

M 0 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1

0 1 1 1

(a) (b)

ABC A

A

B

C

B C A

A

B C

ABC

ABC

ABC

M 1

4

8 5

6

7 B

2

C 3

⇓ ⇑

ABC

+

^ABC

+

^ABC

+

^ABC

◮

Fissatouninsieme

{

^A1

, . . . ,

^An

}

^{divariabilibooleane,un}

mintermineè unprodotto diletterali nel quale tuttele

variabiliappaiono esattamenteuna volta.

◮

Adesempio,sel'insiemedivariabilidiriferimentoè

{

^A

,

^B

,

^C

,

^D

}

^{,alloraABCD eABCD sono}mintermini,mentre A

+

^{BCD eA CD nonlosono.}

◮

Ogni mintermineè in orrispondenza onunassegnamento di veritàallevariabili.

◮

Ogniminterminehavalore1sesi onsideral'assegnamentoad

esso orrispondente,mentre havalore0in qualunquealtro

assegnamentodiverità.

◮

Cias un mintermineè solitamenteindi ato on m

j

,dovej è il

numero naturalerappresentato dall'assegnamentodiverità

orrispondente almintermine.

◮

Daten variabili,esistono 2 n

minterminidistinti.

A B C m

0 m

1 m

2 m

3 m

4 m

5 m

6 m

7

0 0 0 1 0 0 0 0 0 0 0 ABC m

0

0 0 1 0 1 0 0 0 0 0 0 ABC m

1

0 1 0 0 0 1 0 0 0 0 0 ABC m2

0 1 1 0 0 0 1 0 0 0 0 ABC m

3

1 0 0 0 0 0 0 1 0 0 0 ABC m

4

1 0 1 0 0 0 0 0 1 0 0 ABC m

5

1 1 0 0 0 0 0 0 0 1 0 ABC m6

1 1 1 0 0 0 0 0 0 0 1 ABC m

7

◮

Il on ettodi maxtermineè duale aquellodi mintermine.

◮

Fissatouninsieme

{

^A1

, . . . ,

^An

}

^{divariabilibooleane,un}

maxtermine èuna sommadi letterali nelquale tutte le

variabiliappaiono esattamenteuna volta.

◮

Adesempio,sel'insiemedivariabilidiriferimentoè

{

^A

,

^B

,

^C

}

^,

alloraA

+

^B

+

^{C eA}

+

^B

+

^{C sono}maxtermini,mentre A

+

^B

+

^C

+

^{D eA B}

+

^{C nonlosono.}

◮

Ogni maxtermineè in orrispondenza onunassegnamento di

veritàalle variabili.

◮

Dualmentea iò hesu edeperimintermini, ogni

maxterminehavalore0sesi onsideral'assegnamentoadesso

orrispondente,mentrehavalore1inqualunquealtro

assegnamentodiverità.

◮

Cias un maxtermineè solitamenteindi ato onM

j

,dovej èil

numero naturalerappresentato dall'assegnamentodiverità

orrispondente almaxtermine.

◮

Analogamente al aso dei mintermini,date n variabili,esistono n

A B C M

0 M

1 M

2 M

3 M

4 M

5 M

6 M

7

0 0 0 0 1 1 1 1 1 1 1 A

+

B

+

C M0

0 0 1 1 0 1 1 1 1 1 1 A

+

B

+

C M

1

0 1 0 1 1 0 1 1 1 1 1 A

+

B

+

C M

2

0 1 1 1 1 1 0 1 1 1 1 A

+

B

+

C M

3

1 0 0 1 1 1 1 0 1 1 1 A

+

B

+

C M4

1 0 1 1 1 1 1 1 0 1 1 A

+

B

+

C M

5

1 1 0 1 1 1 1 1 1 0 1 A

+

B

+

C M

6

1 1 1 1 1 1 1 1 1 1 0 A

+

B

+

C M

7

◮

Sappiamo già heogni funzione puòessereespressa ome

somma di minterminiinmodo univo o.

◮

Se un'espressione èesprimibile omeuna somma

m

i

1

+

^mi 2

+ . . . +

^min

di mintermini,indi heremo tale

espressione on

P

m

(

ⁱ1

,

ⁱ2

, . . . ,

ⁱn

)

^.

◮

Peresempio,selavoriamo ontrevariabiliA,B eC,lasomma

diminterminiABC

+

^ABC

+

^ABC,ovverom0

+

^m2

+

^m5 si

puòs riverean he

P

m

(

⁰

,

²

,

⁵

)

^.

◮

Se una funzione booleana sipuòesprimere ome sommadi

mintermini

P

m

(

ⁱ¹

,

ⁱ2

, . . . ,

ⁱn

)

^{,allora ilsuo} omplemento si puòesprimere an h'essatramitelasommadi mintermini

P

m

(

^j1

,

^j2

, . . . ,

^jk

)

^{,dovegli indi ij}1

, . . . ,

^jk

sonotuttie soligli

indi i henon ompaiononellasequenza i

1

,

ⁱ2

, . . . ,

ⁱn .

◮

Un'espressioneperil omplementodellafunzionedes ritta

nell'esempiopre edenteè

P

m

(

¹

,

³

,

⁴

,

⁶

,

⁷

)

^.

◮

Si osservi omela sommadi tuttiipossibiliminterminisia

equivalente alla ostante1.

◮

Osserviamoinnanzitutto ome perogni j l'espressionem

j sia

equivalente aM

j

e,vi eversa, ome M

j

siaequivalente am

j .

◮

Se una funzione booleana sipuòesprimere ome sommadi

mintermini

P

m

(

ⁱ¹

,

ⁱ2

, . . . ,

ⁱn

)

^{,allora sipuò esprimere an he}

tremitel'espressione

X

m

(

^j1

,

^j2

, . . . ,

^jk

),

dove gliindi ij

1

, . . . ,

^jk

sono tuttiesoli gliindi i henon

ompaiono nellasequenza i

1

,

ⁱ2

, . . . ,

ⁱn .

◮

Ma aquestopunto osserviamo ome

X

m

(

^j1

,

^j2

, . . . ,

^jk

) =

^mj1

+

^mj2

+ . . . +

^mj

k

=

^mj 1

·

^mj 2

· . . . ·

^mj k

=

^Mj 1

·

^Mj 2

· . . . ·

^Mj k

.

Il prodotto ottenuto,detto prodotto di maxtermini,è

indi ato spesso om

Q

M

(

^j1

,

^j2

, . . . ,

^jk

)

^{ed è una}

◮

Le sommedi minterminisi possono generalizzare asommedi

prodotti diletterali henonsiano ne essariamentesommedi

mintermini.

◮

Una sommadi prodottisempli e peruna ertafunzione può essereottenuta manipolando algebri amentelarelativasomma

di mintermini:

◮

Adesempio:

ABC

+

^ABC

+

^ABC

=

^ABC

+

^AB

(

^C

+

^C

)

=

^ABC

+

^AB

=

^A

(

^BC

+

^B

)

=

^A

((

^B

+

^B

)(

^C

+

^B

))

=

^A

(

^C

+

^B

) =

^AC

+

^AB

◮

Il ir uitologi o relativoad una sommadi prodotti onsiste in ungruppo di porteANDseguite dauna portaOR.

◮

Adesempio:

◮

Dualmente allesommediprodotti,possiamo ostruire

prodotti di sommediletterali henonsiano ne essariamente

prodotti dimaxtermini.

◮

An he inquesto aso lamanipolazione algebri a puòaiutar ia ottenere unprodotto di sommesempli e apartire daun

prodotto di maxtermini:

◮

Adesempio:

(

^A

+

^B

+

^C

)(

^A

+

^B

+

^C

)(

^A

+

^B

+

^C

)(

^A

+

^B

+

^C

)(

^A

+

^B

+

^C

)

= (

^A

+

^B

)(

^C

+

^C

)(

^A

+

^B

)(

^C

+

^C

)(

^A

+

^B

+

^C

)

=

^A

(

^B

+

^B

)(

^A

+

^B

+

^C

)

=

^AA

+

^A

(

^B

+

^C

)

=

^A

(

^B

+

^C

)

◮

Il ir uitologi o relativoad unprodotto disomme onsiste in

ungruppo di porteORseguite dauna porta AND.

◮

Adesempio:

◮

Nel asodei ir uitirelativiasommedi prodottieaprodotti di

sommesiparla diimplementazioni a duelivelli.

◮

Ingenerale, potremmoaverea he fare on ir uiti he non

possono essereespressi suduelivelli,maè hiaro he le

implementazioniadue livellisiano omunqueuniversiali.

◮

De idere seutilizzareun'implementazione aduelivelli oppure

multilivello(treopiù livelli)è una de isione riti aalivello

progettuale.

◮

Nelseguitodes riveremo unate ni a disempli azioneperle implementazioniadue livelli.

◮

Sipuò omunqueutilizzarelasempli azionealgebri a, ome

giàanti ipato.

◮

Talete ni a,però, risultadidi ileimplementazione. In

parti olare,èdi iledeterminarese èstataottenuta

l'espressionepiùsempli e.

◮

Verrannoinve eutilizzatele mappediKarnaugh, heorono

unapro eduradirettaperlasempli azionedifunzioni

◮

Inuna mappa di Karnaugh si puòspe i arelatabella di

veritàdi una funzione booleana.

◮

Adogni asella dellamappa diKarnaugh orrispondeun

assegnamento diverità

◮

Adierenza di iò hesu ede on letabelledi verità,nelle mappe diKarnaugh,l'adia enza si atrale elle orrisponde

all'adia enza logi adei orrispondenti assegnamentidi verità

◮

Inaltreparole, elletraloroadia enti orrispondonoad

assegnamentidiveritàallevariabili hedieris anonelvalore

assegnatoadunasingolavariabile.

◮

Esistonoal unepi ole dierenzetra ivaristilidi rappresentazionedellemappe diKarnaugh.

◮

Inquestosenso,èbeneesseresu ientementeessibilied

esserein gradodilavorare onqualunquestile.

◮

Neilu idi,utilizzeremoinparti oareunostileleggermente

diversodaquelloutilizzatonellibro.

AB

1 1

1 0

A

B

A B F

0 0 1

0 1 1

1 0 1

1 1 0

ABC

1 1

0 0

1 1

0 1

A

B

C

A B C F

0 0 0 1

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 1

1 1 0 0

1 1 1 1

ABCD

1 1

1 0

0 1

1 0

0 1

1 0

0 1

1 0

A

B

C

D

◮

Sappiamo heogni elladiunamappadiKarnaugh orrisponde ad unassegnamento divaloredi veritàallevariabili booleane.

◮

...equindiaun mintermineea unmaxtermine.

◮

Consideriamoora una mappadi Karnaugh a n variabili e

s egliamok

≤

^{n tra quellein gio o.}

◮

Supponiamo he lek variabili s elteassumanoognuna un

valorebinariossatoa priori, mentrele altren

−

^{k possano}

prendere qualunquevalorebinario.

◮

Inquesto modoabbiamo impli itamentedenito uninsiemedi

assegnamenti diverità, ui orrisponderàuna regione (insieme

di elle)dellamappa di Karnaugh, he hiamiamo

raggruppamento (o rettangolo,o a oppiamento).

◮

Inanalogia onquantoavviene nei minterminienei

maxtermini, possiamoasso iareadogni raggruppamento:

◮

Unprodottodiletterali hevale 1solonegliassegnamentidel

raggruppamento.

◮

Unasommadi letterali, hevale0solonegliassegnamentidel

ABCD

A

B

C

D

Prodotto Corrispondente: CD

SommaCorrispondente: C

+

^D

ABCD

A

B

C

D

Prodotto Corrispondente: AC

SommaCorrispondente: A

+

^C

ABCD

A

B

C

D

ProdottoCorrispondente: ACD

Somma Corrispondente: A

+

^C

+

^D

ABCD

A

B

C

D

Prodotto Corrispondente: CD

SommaCorrispondente: C

+

^D

ABCD

A

B

C

D

Prodotto Corrispondente: C D

SommaCorrispondente: C

+

^D

◮

Supponiamodi avere adisposizioneuna mappa diKarnaugh

relativa ad unafunzione booleana.

◮

Supponiamodi rius ireatrovareuna operturapertuttigli1 presenti nellamappa,ossia uninsiemedi raggruppamentitali

he:

◮

Tuttigli1presentinellamappa ompaianoall'internodi

almenoun raggruppamentonell'insieme.

◮

Nessunoraggruppamento ontengauna ellavalorizzataa0.

◮

Intalmodo,abbiamo impli itamentetrovatouna somma di

prodotti perlafunzionedi partenza: basterà onsiderarela

somma deiprodotti orrispondentia tuttiiraggruppamenti

dell'insieme.

◮

Non èperòdetto hela opertura he abbiamo ostruito sia

ottimale, ossia ontenga unnumero minimodi

raggruppamenti.

◮

Una opertura pertuttigli1 sipuò però sempredeterminare:

◮

Basta onsiderareogni ellavalorizzataa 1 omeun

◮

Lapro edura heabbiamo appena des rittopuò essere

fa ilmente generalizzata al aso duale,quelloin ui

l'espressioneprodotta èunprodotto di sommediletterali.

◮

Siamoin questo asointeressati aduna opertura pertuttigli

0 presenti nellamappa,ossia uninsiemediraggruppamentitali

he:

◮

Tuttigli0presentinellamappa ompaianoall'internodi

almenoun raggruppamento

◮

Nessunoraggruppamento ontengauna ellavalorizzataa1.

◮

Perottenere unprodotto di somme orrispondente alla

funzione basteràin questo aso onsiderareil prodotto

orrispondente atutti iraggruppamentidell'insieme(ognuno

dei quali,sappiamo, orrisponde aduna somma).

◮

An he inquesto aso la opertura prodottapuònon essere

ottimale, masipuòsempre ostruireuna opertura

orrispondente ad unprodotto dimaxtermini.

ABCD

1 1

0 1

1 1

0 1

1 1

0 1

1 1

0 0

A

B

C

D

Somma diProdotti: C

+

^BD

+

^AD

ABCD

1 1

0 1

1 1

0 1

1 1

0 1

1 1

0 0

A

B

C

D

Prodottodi Somme:

(

^C

+

^D

)(

^A

+

^B

+

^C

)

◮

Aquesto punto, abbiamo bisognodi dare un ertonumero di

nozioni. Supponiamo datauna funzione booleana F.

◮

Un impli anteèunprodotto diletterali E tale he lafunzione F vale 1ogniqualvolta E vale 1.

◮

Possiamopensareadunimpli ante omeadun

raggruppamentodellamappadiKarnaughdiF he ontenenta

solo1.

◮

Un primoimpli ante èunimpli ante E tale he larimozione

di unletteraledaE dà luogoad unprodotto he nonè un

impli ante.

◮

Dalpuntodi vistadellemappediKarnaugh,unprimo

impli anteèun impli ante henonèinteramente ontenutoin

nessunaltroimpli ante.

◮

Se un ertoassegnamento di veritàrendeveraF ed esisteun

uni o primoimpli ante E heè vero in orrispondenza ditale

assegnamento,alloraE è unprimoimpli ante essenziale.

◮

Seesisteuna elladellamappadiKarnaughdi F heè

valorizzataa1e heèin lusainunsolo primoimpli ante,tale

◮

Esiste una pro edura formale perlasempli azionedi una

mappa diKarnaugh inuna sommadiprodotti:

1. Primadi tutto,o orre determinaretutti i primi impli anti.

◮

NellamappadiKarnaugh,basteràdeterminaretuttii

raggruppamenti ontenentisoltanto ellevalorizzate on1e

henonsonoin lusiinaltriraggruppamentidellostessotipo.

2. O orre poiisolare i primi impli anti essenziali.

◮

NellamappadiKarnaugh,bisognerà apirequalitraiprimi

impli anti ontengonosoltanto elle ontentuteinaltriprimi

impli anti. Tali impli antinonsonoessenzialievannos artati.

3. L'espressione sempli atasi ottiene ome sommalogi adei

prodotti orrispondentiaiprimi impli antiessenzialie ad

eventuali primi impli antinon essenziali,mane essariad

ottenere una opertura.

◮

O orreassi urarsi heogniprimoimpli antenonessenziale

in lusonellasomma ontengauna ellavalorizzata a1non

ontenutainnessunaltroprimoimpli antein lusonella

ABCD

1 0

0 1

0 0

0 0

0 0

1 1

1 1

0 1

A

B

C

D

ABCD

1 0

0 1

0 0

0 0

0 0

1 1

1 1

0 1

A

B

C

D

ABCD

1 0

0 1

0 0

0 0

0 0

1 1

1 1

0 1

A

B

C

D

ABC D

+

^ABC

+

^BCD

+

^ABC

+

^ACD

ABCD

1 0

0 1

0 0

0 0

0 0

1 1

1 1

0 1

A

B

C

D

AB C D

+

^ABC

+

^BCD

+

^ABC

+

^ABD

◮

Se o orre ostruireunprodottodi sommeanzi héuna somma

di prodotti,sipossono sfruttarealsolito leproprietà

dell'algebra diBoole.

◮

Data una funzionebooleanaF,si onsiderail suo omplemento F.

◮

UnamappadiKarnaughperF èfa ilmenteottenibiledauna

mappaperlafunzionedipartenza: bastainvertire ias unbit.

◮

Si appli apoialla mappa diKarnaugh per F lapro eduradi

sempli azione, ottenendo una sommadi prodotti.

◮

Nonène essariomodi arelamappadiKarnaughdiF.

◮

Appli ando poileproprietà diDeMorgan edi doppia

negazione, sarà sempli etrasformarel'espressione ottenuta in

unprodotto di sommeperF.

◮

Adesempio,seF

=

^AB

+

^BCD,allora

F

=

^F

=

^AB

+

^BCD

=

^AB

·

^BCD

= (

^A

+

^B

)(

^B

+

^C

+

^D

)

= (

^A

+

^B

)(

^B

+

^C

+

^D

)

◮

Spessosu ede heuna funzionebooleana,vista ome

spe i a diuna rete ombinatoria,non sia ompletamente

spe i ata,ossia he adal uni assegnamentidi valoridi

veritàalle variabili non orrisponda nessunvaloredi verità.

◮

Ciòsipuò veri arein almenodue situazioni:

◮

Al unipossibiliinputnon sipresentano maiin prati ae,di

onseguenza,nonèrilevanteilvaloredell'output.

◮

Larete ombinatoriasual uniinputpuò produrre

indierentementeunodeiduevaloriinoutput.

◮

Il fatto heuna funzione nonè spe i atain orrispondenzadi

unassegnamento di valoridi veritàallevariabiliè indi ato da

una X nella orrispondente elladella relativamappa di

Karnaugh.

◮

Nella fasedi sempli azione, poi,le X possono assumere indierentementei valori0 e1. Las elta dipende daquale

delledue possibilitàgeneral'espressionepiùsempli e.

◮

L'espressioneottenutaassumerà valoribenpre isian hein

orrispondenzaagliassegnamenti uilafunzionedi partenza

ABCD

X 1

X 1

0 X

0 1

0 0

0 1

0 0

0 1

A

B

C

D

SommadiProdotti: AD

+

^CD

ABCD

X 1

X 1

0 X

0 1

0 0

0 1

0 0

0 1

A

B

C

D

SommadiProdotti: AB

+

^CD