Reti logiche

RETI  LOGICHE  

prof.  CANTONI  

Per  realizzare  un  circuito  è  necessario  passare  sei  livelli:  

1. system  level:  

livello  astratto  senza  dettagli  implementativi  

2. register  transfer  level:  gestione  del  flusso  di  dati  con  i  cicli  del  codice  

3. gate  level:  gestione  dei  dati  con  la  realizzazione  di  porte  logiche  (funzioni  booleane)  

4. transistor  level:  costruzione  dei  vari  componenti  con  transistor  CMOS  

5. layout  level:  progetto  della  tavola  di  silicio    

6. mask  level:  realizzazione  finale  del  circuito  

Essendo  che  per  avere  in  mano  un  prodotto  finito  è  necessario  passare  molte  fasi  di  

implementazione,  è  necessario  poter  controllare  ogni  fase  in  modo  tale  da  non  portarsi  dietro  

errori  nella  realizzazione.  

Segnale:  

variabile  fisica  realizzata  con  variabili  digitali  discrete.  Solitamente  vengono  usati  i  valori  

binari  0-­‐1  che  rappresentano  quindi  range  di  valori  fisici.  

Tipici  segnali  sono:  la  tensione  per  la  CPU,  la  luce  per  il  CD  e  

la  carica  elettrica  per  la  RAM.  

LOGICA  BINARIA  

Operatore  logico:   sono  le  porte  (AND,  OR,  NOT,  …)  che  realizzano  funzioni  logiche,  le  quali  

operano  da  variabili  binarie  a  variabili  binarie.    

Si  chiamano   funzioni  booleane:      

Per  rappresentare  una  funzione  vengono  usati  gli  

ipercubi,  ovvero  dei  cubi  di  varie  dimensioni  

dove  ogni  vertice  rappresenta  una  combinazione  della  funzione:  

Si  chiamano   adiacenze  i  vertici  vicini  ovvero  quelli  che  hanno  in  comune  il  cambio  di  una  sola  

variabile.  

VOCABOLARIO  

Literals:  

sono  tutte  le  variabili  più  le  loro  complementate  

• Onset:  vertici  per  cui  

f(x)  =  1  

• Offset:  

vertici  per  cui  

f(x)  =  0  

• Tautologia:   funzione  sempre  in  onset  (ovvero  a  1)  

• Non  soddisfabile:  funzione  sempre  in  offset  (ovvero  a  0)  

•

  1  

OPERATORI  LOGICI  

  Sono  i  tre  operatori  base:  

AND   ( )  indica  “entrambi”  

OR   (  +  )  indica  “  o  l’uno  o  l’altro”  

NOT   ( )  indica  la  variabile  negata  

Per  valutare  un’espressione  gli  operatori  vanno  in  ordine  di  importanza:  parentesi,  NOT,  AND  e  

infine  OR.  E  solitamente  il  simbolo  della  AND  non  viene  espresso.  

Proprietà:    

Teoremi  di  De  Morgan:  

la  negazione  della  OR  è  uguale  ad  una  AND  dei  singoli  elementi  negati  

la  negazione  della  AND  è  uguale  ad  una  OR  dei  singoli  elementi  negati  

Una  funzione  è  

duale  se  è  possibile  scambiare  AND-­‐OR  e  0-­‐1  e  viceversa.  

Una  funzione  è  

self-­‐dual  se  facendone  il  duale  non  si  ottiene  la  funzione  iniziale.  

Formule  booleane  quantificative  (QBF):    

“per  ogni”:  tutti  i  vertici  con  la  prima  variabile  a  0  AND  

tutti  i  vertici  con  la  prima  variabile  a  1  

“esiste”:  tutti  i  vertici  con  la  prima  variabile  a  0  OR  tutti  i  

vertici  con  la  prima  variabile  a  1  

Teorema  del  consenso:   Se   in   una   funzione   è   presente   una   variabile   e   la   sua  

negata   allora   è   possibile   aggiungere   un   termine   AND   di  

tutte   le   variabili   che   appaiono   insieme   ad   essa.   Idem    

                                             togliere  il  termine  se  esso  è  già  presente.  

  2  

Teoremi  utili  (riassunto):    

  Minimizzazione  

  Assorbimento  

  Semplificazione  

  Consenso  

  De  Morgan  

I   teoremi   sono   utili   quando   una   funzione   contiene   troppe   variabili   che   quindi   fanno   crescere   di  

molto   il   numero   di   combinazioni   possibili.   In   questi   casi,   applicando   i   teoremi   e   facendo   della  

funzione   la   sua   complementare   (scambio   di   AND   con   OR   e   variabili   con   le   rispettive   negate)   è  

possibile   arrivare   ad   avere   una   funzione   meno   complessa   ma   comunque   con   gli   stessi   risultati.  

Esempio:    

Espansione  di  Shannon:  

avendo   una   funzione   con   n   variabili   entranti   è   possibile   spezzarla   in   due   sottofunzioni   dove   una  

variabile  è  fissa  o  a  1  oppure  a  0  ( variabile  di  split):    

La  funzione  di  partenza  si  può  scrivere  ora  come:  

Con  l’espansione  di  Shannon  uno  degli  ipercubi  di  divide  in  due  sottoipercubi  più  piccoli.  Esempio:  

  3  

RAPPRESENTAZIONI  BOOLEANE  E  TABELLE  DELLA  VERITA’  

Innanzitutto  è  sempre  meglio  avere  la  funzione  espressa  in  uno  dei  due  modi:  

somme  di  prodotti  (SOP)    

• cioè  OR  di  AND,  tanti  

mintermini  (variabili  in  AND)  unite  poi  in  OR  

in  questo  caso  vengono  messi  in  risalto  i  vertici  che  hanno  

f(x)  =  1  

prodotti  di  somme  (POS)  

• cioè  AND  di  OR,  tanti  

maxtermini  (variabili  in  OR)  unite  poi  in  AND  

in  questo  caso  vengono  messi  in  risalto  i  vertici  che  hanno  

f(x)  =  0  

VOCABOLARIO  

Mintermine:   termine  composto  da  variabili  in  AND  che  corrisponde  ad  un  1  della  funzione  

• Maxtermine:   termine   composto   da   variabili   in   OR   che   corrisponde   ad   uno   zero   della  

• funzione  

Tabella   della   verità:   tabella   che   rappresenta   tutte   le   possibili   combinazioni   di   variabili  

• d’ingresso  con  la  rispettiva  uscita  

Forma  canonica:  tabella  della  verità  dove  tutte  le   f(x)  =  1  rappresentano  un  singolo  vertice  

• (ovvero  il  mintermine  è  composto  da  tutte  le  variabili)  

NB!   Più  un  termine  contiene  variabili,  più  esso  rappresenta  

una  parte  ristretta  del  cubo  ( cubo:  AND  di  variabili):  

VOCABOLARIO  2  

Implicante:   cubo   della   funzione.   Un   implicante   formato   da   n   variabili   è   un   mintermine   o  

• maxtermine  

Cubo   irridondante:   se   esso   è   indispensabile   per   avere   la   copertura   minima,   cioè   se  

• togliendolo  non  rimangono  termini  scoperti  

Cubo   primo:   se   togliendolo   e   sostituendolo   con   una   singola   variabile   cambia   la   funzione  

• iniziale  (ovvero,  magari,  vengono  coperti  anche  altri  mintermini  che  non  vanno  considerati)  

Cubo  primo  essenziale:   se  un  vertice  è  contenuto  solo  in  quel  cubo  

•      

irridondante   cubo  primo  

  4  

DIAGRAMMI  DI  DECISIONE  BINARIA                                                                          

E’  un  grafico  a  forma  di  albero  che  rappresenta  una  funzione  booleana:  

ogni   nodo  rappresenta  una  variabile    

• da  ogni  nodo  partono  due   rami   che  rappresentano  le  possibili  scelte  (variabile  a  0  o  a  1)  

• si  arriva  alla  fine  ad  ottenere  il  risultato  della  funzione  

•   1. si   parte   dalla   prima   variabile   per  

importanza     (a)   e   si   divide   la   funzione   a  

seconda   se   essa   è   pura   o  

complementata  

2. si   procede   così   per   ogni   variabile   fino  a  

non  avere  più  variabili  legate  al  nodo  

3. si  collega  al  risultato  corrispondente    

IMPLEMENTAZIONE  DELLE  FUNZIONI  LOGICHE    

OR    

AND    

NOT    

Ogni  funzione,  in  realtà,  è  realizzata  mediante  circuiti  elettrici  (CMOS)  in  cui  gli  switch  realizzano  

le   varie   porte.   Essendo   quindi   che   si   tratta   di   circuiti,   è   possibile   che   avvenga   un   ritardo   tra  

l’ingresso  e  l’uscita  della  porta,  questo  è  chiamato  appunto   gate  delay  ed  è  indicato  con  

t  [

ns].  

G

  5  

VOCABOLARIO  

Fanin:   ingressi  di  una  porta     FI(g)  

à

• Fanout:   uscite  della  porta  che  sono  ingressi  di  una  successiva     FO(g)  

à

• Cono:   tutti  i  fanin  per  arrivare  fino  a  quella  porta  (dall’inizio  del  percorso)  

• Supporto:  variabili  principali  che  riguardano  quella  porta  

•

MINTERMINI,  MAXTERMINI  E  FORME  CANONICHE  

Come  già  detto  esistono  due  forme  canoniche  per  rappresentare  una  funzione:  

somme  di  prodotti  formate  da   mintermini  

• prodotti  di  somme  

formati  da   maxtermini  

•

dove:   i   mintermini  impongono  gli  1  della  funzione  mediante  AND  

• i   maxtermini  impongono  gli  0  della  funzione  mediante  OR  

•  

Questo  significa  che  ogni    vertice  di  un  ipercubo  si  può  rappresentare  in  due  modi  a  seconda  di  

come  vengono  scritte  le  variabili.  Ad  esempio,  per  due  variabili  

x   e   y

:  

NB!   Grazie   a   De   Morgan   mintermini   e  

maxtermini  si  possono  scambiare  cio