reti combinatorie. - unirc.it · reti logiche combinatorie 13 una porta logica è un circuito usato...
TRANSCRIPT
![Page 1: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/1.jpg)
RETI COMBINATORIE.
Algebra booleana: logica binaria (a due stati)
A è una variabile booleana: A=1 oppure A=0
Funzioni logiche elementari per l’algebra Booleana: AND, OR, NOT
1
![Page 2: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/2.jpg)
2
Logica positiva: livello di tensione + elevatocorrisponde all’1 logico;livello di tensione + bassocorrisponde allo 0 logico;
Logica negativa: livello di tensione + elevatocorrisponde allo 0 logico;livello di tensione + bassocorrisponde all’1 logico.
![Page 3: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/3.jpg)
PORTE LOGICHE 3
La porta NOT.
Out = NOT In1 = In1
In1 Out
01
10
OutIn1
![Page 4: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/4.jpg)
PORTE LOGICHE 4
La porta AND.In1
In2
Out
11 1 01 000 1 00 0
OutIn1 In2
Out = In1 AND In2 = In1 • In2
![Page 5: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/5.jpg)
PORTE LOGICHE
La porta OR.
11 1 11 010 1 00 0
OutIn1 In2
Out = In1 OR In2 = In1 + In2
OutIn1
In2
5
![Page 6: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/6.jpg)
PROPRIETA’ FONDAMENTALI
6
A+0=AA+1=1A+A=AA+A=1
A • 0=0A • 1=AA • A=AA • A=0
A + A=1A • A=0
A=A
NOT AND OR
![Page 7: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/7.jpg)
LEGGI DI DE MORGAN7
⋅⋅⋅+++=⋅⋅⋅⋅⋅ CBACBA
⋅⋅⋅⋅⋅=⋅⋅⋅+++ CBACBA
![Page 8: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/8.jpg)
PORTE LOGICHE 8
La porta NAND.
01 1 11 010 1 10 0
OutIn1 In2
In1
In2Out
Out = In1 NAND In2 = In1 • In2
![Page 9: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/9.jpg)
PORTE LOGICHE
La porta NOR.
01 1 01 000 1 10 0
OutIn1 In2
OutIn1
In2
Out = In1 NOR In2 = In1 + In2
9
![Page 10: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/10.jpg)
PORTE LOGICHE10
La porta XOR.
01 1 11 010 1 00 0
OutIn1 In2
OutIn1
In2
Out=In1 XOR In2=In1·In2+ In1·In2=In1⊕In2
![Page 11: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/11.jpg)
PORTE LOGICHE11
La porta XNOR.
11 1 01 000 1 10 0
OutIn1 In2
OutIn1
In2
Out=In1 XNOR In2=In1·In2+ In1·In2=In1⊕In2
![Page 12: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/12.jpg)
PORTE LOGICHE12
La porta XNOR. OutIn1
In2
Dimostrare che:
In1 XNOR In2 = NOT (In1 XOR In2)
![Page 13: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/13.jpg)
RETI LOGICHE COMBINATORIE
13
Una porta logica è un circuito usato per realizzare in hardware una funzione logica
elementare
L’insieme di più porte logiche è unarete logica combinatoria e consente
di realizzare in hardware una funzione logica complessa
![Page 14: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/14.jpg)
14
Esempio di rete logica combinatoria
A
B
COut
CACBBAOut ⋅+⋅+⋅=
![Page 15: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/15.jpg)
CIRCUITI COMBINATORI 15
Un MULTIPLEXER è un circuito logicoche consente di selezionare 1 tra 2n ingressiin base allo stato di n segnali di controllo
S0 S1…Sn-1
01..2n-1
I0
I1
I2n-1
Out
Out = Ikse la parola binaria
S0 S1 …Sn-1rappresenta il numero
Decimale k
![Page 16: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/16.jpg)
CIRCUITI COMBINATORI 16
S0
01
I0
I1
Out
Multiplexer 2:1
11110011110100011110101001000000
OutI1I0S0
0100 SISIOut ⋅+⋅=
![Page 17: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/17.jpg)
CIRCUITI COMBINATORI
S1 S0
0123
I0
I1I2
Out
I3
Multiplexer 4:1
I311I201
I110I000
OutS0S1
17
![Page 18: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/18.jpg)
CIRCUITI COMBINATORI
18
Un DEMULTIPLEXER è un circuito logicoche consente di instradare 1 ingresso su una
tra 2n linee di uscita in base allo stato di n segnali di controllo
![Page 19: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/19.jpg)
Proprietà dell’algebra di Boole
X1 + X2 = X2 + X1 Pr. Commutativa(X1 + X2) + X3 = X1 + (X2 + X3) Pr. Associativa(X1·X2) + (X1 ·X3) = X1 ·(X2 + X3) Pr. Distributiva
X1 + X1·X2 = X1
X12XX1··X21 =+X
Priorità degli operatori: Not, And, Or
![Page 20: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/20.jpg)
Principio di dualità
Nota una proprietà dell’algebra booleanasi può ottenere la sua duale scambiando gli operatori e i simboli nel modo seguente:
“+” � “·”“1” � “0”
![Page 21: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/21.jpg)
Proprietà dell’algebra di Boole
X1·X2 = X2·X1 Pr. Commutativa(X1·X2) ·X3 = X1· (X2·X3) Pr. Associativa(X1+X2)·(X1+X3) = X1 + (X2·X3) Non valida in
algebra ordinaria
X1·(X1+X2) = X1 Dimostrare
X12)XX2)·(X11( =++X
![Page 22: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/22.jpg)
MintermineUn mintermine pi è una funzione che vale 1 in
corrispondenza della sola configurazione i dei valori delle variabili di ingresso.
Ogni mintermine pi ammette un’espressione algebrica consistente nell’AND di tutte le variabili, dove ogni variabile compare diretta (cioè non negata) se vale 1 nella configurazione i, compare negata se invece vale 0.
cbap ⋅⋅=0
![Page 23: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/23.jpg)
MaxtermineUn maxtermine si è una funzione che vale 0 in
corrispondenza della sola configurazione i dei valori delle variabili di ingresso.
Ogni maxtermine si ammette un’espressione algebrica consistente nell’OR di tutte le variabili, dove ogni variabile compare diretta (cioè non negata) se vale 0 nella configurazione i, compare negata se invece vale 1.
cbas ++=0
![Page 24: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/24.jpg)
La Prima Forma Canonica (SP)La prima forma canonica di una funzione f è la OR
di tutti i mintermini pi, per le configurazioni i per le quali f = 1
�
�
=++=
=∀=
3)4,2,0(
420
ingresso di ioneconfiguraz della
enzacorrispondin 1 che tale
f
pppf
i
fipfi
i
![Page 25: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/25.jpg)
La Seconda Forma Canonica (PS)La seconda forma canonica di una funzione f è la
AND di tutti i maxtermini si, per le configurazioni i per le quali f = 0
)4,2,0(420
ingresso di ioneconfiguraz della
enzacorrispondin 0 che tale
3∏=⋅⋅=
=∀= ∏
f
sssf
i
fisf ii
![Page 26: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/26.jpg)
Completezza funzionale
Insiemi funzionalmente completi:{AND, OR, NOT} (Le forme canoniche ne sono una prova)
{AND, NOT}
{OR, NOT}
![Page 27: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/27.jpg)
Completezza funzionale
Insiemi funzionalmente completi:
{NAND} NOT X = X NAND X
{NOR} NOT X = X NOR X
![Page 28: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/28.jpg)
Esercizio
Passare dalla prima forma canonica (SP) alla rappresentazione in termini di porte NAND
![Page 29: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/29.jpg)
Enumerazione di funzioni
in variabil di distinte funzioni 2 Esistono )(2n
Es.: Enumerare tutte le funzioni a 2 ingressi
![Page 30: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/30.jpg)
Semplificazione delle forme canoniche
bac
cabaca
cabcbabaca
cabcbacbacbaca
cabcbacbaca
cabcbacbacbacbaz
+==++=
=+++==++++=
=+++==++++=
![Page 31: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/31.jpg)
MAPPE DI KARNOUGH
31
2 Ingressi – 1 Uscita
11 101 000 100 0
OutA B
Tabella di verità
1
A
B
0 1
0
1
Mappa di K.
BAOut ⋅=Formula logica
![Page 32: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/32.jpg)
3 Ingressi – 1 Uscita
01 0 101 0 000 1 1
01 1 011 1 1
00 1 000 0 100 0 0
OutA B C
A
BC
00 01 11 10
0
1 1
?
Regola:Una mappa di K. è costruitaassicurando che le sue celle
siano ADIACENTI
32
![Page 33: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/33.jpg)
4 Ingressi – 1 UscitaCD
AB 00 01 11 10
00
01
11
10
Sono celle adiacentiNON sono celle adiacentiSono celle adiacentiNON sono celle adiacenti
Sono celle tutte adiacenti tra loro
?
Due celle sono adiacenti se,spostandosi da una all’altracambia uno solo dei bit da cui sono intercettate nella
Mappa di K.
33
![Page 34: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/34.jpg)
Funzione prodotto
Una funzione prodotto p di k variabili èrappresentata sulla mappa da un sottocubo di 2n-k caselle adiacenti contenenti 1
![Page 35: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/35.jpg)
Implicanti e Implicati
Una funzione prodotto p si dice implicantedi una funzione f, se f=1 almeno in tutti i vertici del sottocubo relativo a p (p � f).
Una funzione può essere espressa come OR dei suoi implicanti
f = p1 + p2 + … + pn
![Page 36: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/36.jpg)
Implicante primo
Un implicante p � f si dice implicante primo di f, se non esiste alcun altro implicante p’ di f (p’� f ) tale che
p � p’(Un implicante primo rappresenta il massimo
sottocubo)
Una funzione f può essere espressa come somma dei suoi implicanti primi
![Page 37: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/37.jpg)
Implicante primo essenziale
Un implicante p � f si dice implicante primo essenziale di f, se esiste almeno un vertice del sottocubo relativo a p, che non appartiene al sottocubo di alcun altro implicante primo di f.
Un implicante primo è cioè essenziale se èl’unico a coprire un dato 1 della f.
![Page 38: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/38.jpg)
Sintesi ottima di reti a due livelli
Ogni forma SP minima di una funzione f èuna forma SP prima irridondante per f.
![Page 39: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/39.jpg)
Forma SP minima
1. Determinare tutti gli implicanti primi di f2. Selezionare un insieme irridondante di
implicanti primi la cui somma copra la f, e il cui costo complessivo sia minimo
OVVERO2A) Selezionare dapprima gli implicanti primi
essenziali2B) Selezionare gli implicanti primi non essenziali
che ricoprono gli 1 della mappa non ricoperti dagli implicanti primi essenziali
![Page 40: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/40.jpg)
Sintesi di reti combinatorie
40
1. Stabilire in quali condizioni l’uscita dellarete combinatoria deve assumere 1
2. Costruire la tabella di verità
3. Estrarre una formula logica minimizzata
4. Disegnare la rete combinatoria
![Page 41: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/41.jpg)
Minimizzazione 41
Individuare nella mappa i gruppi “piùgrandi possibili” di celle adiacenti.
Ogni gruppo contiene 2k celleLa presenza dei gruppi 2 e 4 introduce ridondanza
Tutti gli 1 devono essere “coperti”; no ridondanze
1111111
111
CDAB 00 01 11 10
00
01
11
10
Gruppo 1
Gruppo 2
Gruppo 3
Gruppo 4
![Page 42: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/42.jpg)
Dalla mappa alla formula logica 42
1111111
111 Gruppo 1
Gruppo 2
Gruppo 3
CDAB 00 01 11 10
00
01
11
10
Gruppo 1 B · D Gruppo 2 C · D
Gruppo 3 B · D
DBDCDBOut ⋅+⋅+⋅=
![Page 43: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/43.jpg)
Esercizio di riepilogo
• Individuare i mintermini• I forma canonica (SP)• Rappresentazione a NAND• Mappa di K• Implicanti• Implicanti primi• Implicanti primi essenziali• Sintesi ottima a 2 livelli
![Page 44: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/44.jpg)
Esercizio di riepilogo
111010110
10100010
1110001001000
10000ZX0X1X2X3
1111110111
101110011
11010101
110010001
ZX0X1X2X3
![Page 45: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/45.jpg)
Esercizio
Realizzare un circuito capace di confrontare 2 numeri interi N1 e N2 senza segno a 2 bit, tale circuito fornisce in uscita il valore 1 se N1�N2, e 0 altrimenti.
Z = 1 se N1�N2Z = 0 se N1<N2
![Page 46: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/46.jpg)
Funzioni non completamente specificate
Una funzione si dice non completamentespecificata quando esistono delle condizioni di indifferenza, ovvero delle configurazioni di ingresso per le quali la funzione non è specificata.
N.B.: Esistono funzioni non completamente specificate ma non esistono reti non completamente specificate!!!
![Page 47: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/47.jpg)
Funzioni non completamente specificate
Se ci sono h condizioni di indifferenza per f vi sono 2h modi per assegnare ‘0’ o ‘1’ a tali condizioni, esistono quindi 2h funzioni complete distinte che coincidono con la f ovunque questa è specificata, e altrettante reti per f.
Fra tutte le reti si cerca la rete minima (a due livelli) assegnando alle condizioni di indifferenza i valori 0 o 1 più opportuni.
![Page 48: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/48.jpg)
Forma SP minima per funzioni non completamente specificate
1. Si assegna provvisoriamente il valore 1 a tutte le condizioni di indifferenza ottenendo la funzione f’
2. Si determinano gli implicanti primi della funzione f’
3. Si scartano gli implicanti primi che coprono solo gli 1 corrispondenti alla condizioni di indifferenza
4. Si procede per la sintesi ottima considerando che solo gli 1 della funzione f devono essere necessariamente coperti
![Page 49: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/49.jpg)
Esempio
xx110
xxxx11
101
1100
10110100x3x2
x1x0
![Page 50: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/50.jpg)
Esercizio
![Page 51: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/51.jpg)
Importanza dei circuiti aritmeticiIn qualsiasi microprocessore è presente
un’unità Logica-Aritmetica (ALU)
51
Ingresso1
Ingresso2
Uscita
Controllo
ALU
Esempio:Ingresso1+Ingresso2Ingresso1-Ingresso2Ingresso1×Ingresso2
(Ingresso1)2
.
.
.
2Ingresso
La somma binaria è l’operazione di base
![Page 52: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/52.jpg)
0 1 0 0 0 0 1 0 0 +
0 1 1 0 0 0 1 0 1 =
0 1 0 1 0 0 1 0 0 1
00100001
Risultato: OutBIN=0101001001
52
![Page 53: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/53.jpg)
Circuiti Sommatori 53
Il modulo di base èil full-adder (FA) CiCo
S
A B
FA
TIPI DI CIRCUITI SOMMATORIRipple CarryCarry-Select
Carry Look-AheadSommatori ad albero (Kogge Stone)
![Page 54: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/54.jpg)
Half adder 54
Funzione da realizzare: somma binaria tra 2 bit• Costruzione della tabella di verità di una rete
logica a due ingressi (A e B) e due uscite (Co e S)
1 01 10 11 00 10 10 00 0Co SA B BACo ⋅= BAS ⊕=
A
B
Co
SHALF-ADDER
![Page 55: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/55.jpg)
55Full-AdderRete logica con 3 ingressi (A, B, Ci) e due
uscite (Co ed S)
1 00 1 10 11 0 01 01 0 11 01 1 01 11 1 1
0 10 1 0 0 10 0 1
0 00 0 0Co SA B Ci
ABCi
00 01 11 10
0
1 1111
ABCi
00 01 11 10
0
1 1111
Co
S
![Page 56: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/56.jpg)
ABCi
00 01 11 10
0
1 1111
ABCi
00 01 11 10
0
1 1111
Mappa per Co Mappa per S
BACiACiBCo ⋅+⋅+⋅=
=⋅⋅+⋅⋅+⋅⋅+⋅⋅= CiBACiBACiBACiBAS=⋅+⋅⋅+⋅+⋅⋅= )()( CiBCiBACiBCiBA
)()( CiBACiBA ⊕⋅+⊕⋅=
Ponendo CiBY ⊕=
CiBAYAYAS ⊕⊕=⋅+⋅=56
![Page 57: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/57.jpg)
Circuito logico di un full-adder
BACiACiBCo ⋅+⋅+⋅= CiBAYAYAS ⊕⊕=⋅+⋅=
A
B
Ci
S
Co
57
![Page 58: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/58.jpg)
Circuito alternativo
CiBAYAYAS ⊕⊕=⋅+⋅=
BACiACiB
BACiACiBBACiACiBCo
⋅⋅⋅⋅⋅=
=⋅+⋅+⋅=⋅+⋅+⋅=
ABCi
S
Co
58
![Page 59: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/59.jpg)
Circuito Alternativo 59
ABCi
S
Co
CiBAYAYAS ⊕⊕=⋅+⋅=
BACiBACo ⋅⋅⋅⊕= )(
![Page 60: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/60.jpg)
Circuiti Integrati a Porte Discrete60
1 2 3 4 5 6 7
891011121314VCC
GND
DM74ALS08
![Page 61: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/61.jpg)
Il Ripple-Carry Adder 61
Esegue l’operazione di somma tra due numeri ad n-bit secondo il metodo carta e penna
CiCoS
A B
FACiCoS
A B
FA CiCoS
A B
FA
an-1 bn-1 an-2 bn-2 a0 b0
sn-1 sn-2 s0
c0c1cn-2cn-1cn
Operandi: A=an-1 an-2 … a1 a0 e B=bn-1 bn-2 … b1 b0Risultato ad n+1 bit: cn sn-1 sn-2 … s1 s0
![Page 62: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/62.jpg)
Il Ripple-Carry Adder62
E’ il sommatore più semplice e meno costoso:richiede meno porte logiche di qualsiasi altro
tipo di sommatore
Sommatore più lento.Problema legato alla propagazione del riporto:
l’i-esimo FA può generare il risultato corretto solo dopo avere ricevuto in ingresso il riporto generato
dal precedente FA
![Page 63: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/63.jpg)
CiCoS
A B
FACiCoS
A B
FA CiCoS
A B
FA
an-1 bn-1 an-2 bn-2 a0 b0
sn-1 sn-2 s0
c0c1cn-2cn-1cn
cn
a0b0an-1bn-1 an-2bn-2
sn-1sn-2 s0
c0c1
cn-2cn-1
63
![Page 64: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/64.jpg)
an-1bn-1 an-2bn-2
sn-1sn-2 s0
c0c1
cn-2cn-1
a0b064
Path per sk = 1 XOR+2·k NAND+1 XORPath per ck= 1 XOR+2·k NAND
Path critici:per sn-1 : 1 XOR+2·(n-1) NAND+1 XOR
per cn : 1 XOR+2·n NAND
![Page 65: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/65.jpg)
Il Carry-Select Adder 65
Ripple-carrya 4-bit
RC
Ripple-carrya 4-bitRC-Z
Ripple-carrya 4-bitRC-U
0
1
a[7:4] b[7:4]
a[7:4] b[7:4]
Sz[7:4]
Su[7:4]
a[3:0] b[3:0]
c0c4c4
01
S[3:0]S[7:4]
01
cz8
cu8
cz8
cu8c8
I blocchi RC, RC-Ze RC-U lavorano
in parallelo
![Page 66: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/66.jpg)
Il Carry-Select Adder66
Nel caso esaminato (operandi a 8-bit) si ha:Path critici:
per s7 : 1 XOR+8 NAND+1 MUXper c8 : 1 XOR+8 NAND+1 MUX
In un Ripple-Carry a 8-bit si avrebbe:Path critici:
per s7 : 1 XOR+14 NAND+1 XORper c8 : 1 XOR+16 NAND
![Page 67: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/67.jpg)
Esempio
Disegnare un Carry Select Adder a 12 bit che utilizza RCA a 4 bit.
Ricavare una formula generale per esprimere i ritardi massimi
![Page 68: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/68.jpg)
Il Carry-Select Adder68
In un Carry-Select ad n-bit realizzato usandoBlocchi Ripple-Carry a 4-bit sono necessari
stadi di multiplexer14
−n
Path critici:
per sn-1 : 1 XOR+8 NAND+ MUX
per cn : si individua lo stesso path
Il Carry-Select è più veloce, ma più costoso
)14
( −n
![Page 69: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/69.jpg)
Il Carry Look-Ahead 69
iiii cbaS ⊕⊕=
iiiiii bacbac ⋅⋅⋅⊕=+ )(1
Applicando le leggi di De Morgan
iiiiii bacbac ⋅+⋅⊕=+ )(1
Si definiscono i segnali di propagate pie di generate gi
iii bap ⊕= iii bag ⋅=
![Page 70: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/70.jpg)
iii cpS ⊕=
iiii gcpc +⋅=+1
c1=g0+ p0 c0
c2=g1+ p1 c1 = g1+ p1 (g0+ p0 c0)= g1+ p1 g0 + p1 p0 c0
c3=g2+ p2 c2 = g2+ p2 (g1+ p1 g0 + p1 p0 c0)=g2+p2g1+p2p1g0+p2p1p0c0..ck+1=gk+ gk-1 pk+ gk-2 pk-1+...+ g0 p1 p2 ... pk+ p0 p1 ... pk c0. .cn=gn-1+gn-2pn-1+...+p0p1...pn-1c0
70
![Page 71: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/71.jpg)
4-bit Carry Look-Ahead Adder71
a3 b3 a2 b2 a1 b1 a0 b0
c0c1
c2c3
c4
s0s1s2s3
![Page 72: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/72.jpg)
Path critici:
per si : 1 XOR+1 AND+1 OR +1 XORper ci+1 : 1 XOR+1 AND+1 OR
Da i dipende il numero di ingressi delle porteAND ed OR incluse nei path critici
PROBLEMA
Un Carry Look-Ahead ad n-bit richiede porteAND ed OR fino ad n+1 ingressi !!
72
![Page 73: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/73.jpg)
Esercizio
Realizzare un modulo aritmetico capace di eseguire la somma e la differenza di due numeri interi in complemento a 2.
f = A + B quando sel = 0 f = A – B quando sel = 1
AB
sel
fAdder/Subtracter
![Page 74: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/74.jpg)
Esercizio
Bit di paritàPer una stringa di n bit, il bit di parità è un bit
aggiuntivo che vale 1 se il numero di 1 della stringa è dispari, vale 0 se il numero di 1 della stringa è pari.
Realizzare una rete per la generazione del bit di parità per stringhe di cinque bit.
![Page 75: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/75.jpg)
Esercizio
Radice quadrata
Realizzare una rete combinatoria a cinque ingressi x4, x3, x2, x1, x0, che esegue la radice quadrata approssimata per difetto del numero binario x4x3x2x1x0
![Page 76: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/76.jpg)
Tree AddersFor high speed adders it is necessary to use tree structures.Parallel prefix-tree algorithms organize carry propagation and generation into recursive trees, in this way it is possible to compute the output carry of an N-bit adder in a logarithmic time.
Parallel prefix-tree algorithms compute the addition in three stage:First stage -> computation of carry generate and carry propagate for each bitgi = ai·bipi = ai⊕bi
Second stage -> computation of the carries for each bit position by iteratively combining the generate and propagate terms of the first stageci+1 = gi + gi-1·pi
Third stage -> computation of the sum bits si = ai ⊕ bi ⊕ ci = pi⊕ ci
The second stage is the most computational expensive one, in fact it represents the carry propagation chain.
![Page 77: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/77.jpg)
Tree AddersTree algorithms exploit the properties of dot operator to calculate the carries.
Definition:
Gi:j = gi + gi-1·pi + … + gj·pi·pi-1· … ·pj+1
Pi:j = pi·pi-1· … ·pj
Gi:i = gi
Pi:i = pi
ci+1 = Gi:0
![Page 78: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/78.jpg)
Tree AddersDefinition of dot operator “•” :(Gi:j, Pi:j) • (Gj-1:k, Pj-1:k) = (Gi:j + Pi:j · Gj-1:k , Pi:j· Pj-1:k) = (Gi:k, Pi:k)
Properties:1) Associativity
(Gi:j, Pi:j) • (Gj-1:k, Pj-1:k) = (Gi:k, Pi:k)
2) Non-commutativity
3) Idempotency(Gi:j, Pi:j) • (Gi:j, Pi:j) = (Gi:j, Pi:j)
Proof: A + B·A = AA·A = A
![Page 79: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/79.jpg)
Tree Adders
16-bit radix-2 Kogge-Stone tree
(A0,
B0)
(A1,
B1)
(A2,
B2)
(A3,
B3)
(A4,
B4)
(A5,
B5)
(A6,
B6)
(A7,
B7)
(A8,
B8)
(A9,
B9)
(A10
, B10
)
(A11
, B11
)
(A12
, B12
)
(A13
, B13
)
(A14
, B14
)
(A15
, B15
)
S0
S1
S2
S3
S4
S5
S6
S7
S8
S9
S10
S11
S12
S13
S14
S15
Calculates pi and gi
‘dot’ operator
sum
![Page 80: RETI COMBINATORIE. - unirc.it · RETI LOGICHE COMBINATORIE 13 Una porta logica è un circuito usato per realizzare in hardware una funzione logica elementare L’insieme di più porte](https://reader030.vdocumenti.com/reader030/viewer/2022040222/5e45a649271fb61c863578e2/html5/thumbnails/80.jpg)
Tree Adders(A
0, B
0)
(A1,
B1)
(A2,
B2)
(A3,
B3)
(A4,
B4)
(A5,
B5)
(A6,
B6)
(A7,
B7)
(A8,
B8)
(A9,
B9)
(A10
, B10
)
(A11
, B11
)
(A12
, B12
)
(A13
, B13
)
(A14
, B14
)
(A15
, B15
)
S0
S1
S2
S3
S4
S5
S6
S7
S8
S9
S10
S11
S12
S13
S14
S15
Brent-Kung Tree