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

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.

PORTE LOGICHE 3

La porta NOT.

Out = NOT In1 = In1

In1 Out

01

10

OutIn1

PORTE LOGICHE 4

La porta AND.In1

In2

Out

11 1 01 000 1 00 0

OutIn1 In2

Out = In1 AND In2 = In1 • In2

PORTE LOGICHE

La porta OR.

11 1 11 010 1 00 0

OutIn1 In2

Out = In1 OR In2 = In1 + In2

OutIn1

In2

5

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

LEGGI DI DE MORGAN7

⋅⋅⋅+++=⋅⋅⋅⋅⋅ CBACBA

⋅⋅⋅⋅⋅=⋅⋅⋅+++ CBACBA

PORTE LOGICHE 8

La porta NAND.

01 1 11 010 1 10 0

OutIn1 In2

In1

In2Out

Out = In1 NAND In2 = In1 • In2

PORTE LOGICHE

La porta NOR.

01 1 01 000 1 10 0

OutIn1 In2

OutIn1

In2

Out = In1 NOR In2 = In1 + In2

9

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

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

PORTE LOGICHE12

La porta XNOR. OutIn1

In2

Dimostrare che:

In1 XNOR In2 = NOT (In1 XOR In2)

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

14

Esempio di rete logica combinatoria

A

B

COut

CACBBAOut ⋅+⋅+⋅=

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

CIRCUITI COMBINATORI 16

S0

01

I0

I1

Out

Multiplexer 2:1

11110011110100011110101001000000

OutI1I0S0

0100 SISIOut ⋅+⋅=

CIRCUITI COMBINATORI

S1 S0

0123

I0

I1I2

Out

I3

Multiplexer 4:1

I311I201

I110I000

OutS0S1

17

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

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

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”

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

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

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

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

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

Completezza funzionale

Insiemi funzionalmente completi:{AND, OR, NOT} (Le forme canoniche ne sono una prova)

{AND, NOT}

{OR, NOT}

Completezza funzionale

Insiemi funzionalmente completi:

{NAND} NOT X = X NAND X

{NOR} NOT X = X NOR X

Esercizio

Passare dalla prima forma canonica (SP) alla rappresentazione in termini di porte NAND

Enumerazione di funzioni

in variabil di distinte funzioni 2 Esistono )(2n

Es.: Enumerare tutte le funzioni a 2 ingressi

Semplificazione delle forme canoniche

bac

cabaca

cabcbabaca

cabcbacbacbaca

cabcbacbaca

cabcbacbacbacbaz

+==++=

=+++==++++=

=+++==++++=

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

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

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

Funzione prodotto

Una funzione prodotto p di k variabili èrappresentata sulla mappa da un sottocubo di 2n-k caselle adiacenti contenenti 1

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

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

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.

Sintesi ottima di reti a due livelli

Ogni forma SP minima di una funzione f èuna forma SP prima irridondante per f.

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

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

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

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 ⋅+⋅+⋅=

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

Esercizio di riepilogo

111010110

10100010

1110001001000

10000ZX0X1X2X3

1111110111

101110011

11010101

110010001

ZX0X1X2X3

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

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!!!

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.

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

Esempio

xx110

xxxx11

101

1100

10110100x3x2

x1x0

Esercizio

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

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

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)

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

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

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

Circuito logico di un full-adder

BACiACiBCo ⋅+⋅+⋅= CiBAYAYAS ⊕⊕=⋅+⋅=

A

B

Ci

S

Co

57

Circuito alternativo

CiBAYAYAS ⊕⊕=⋅+⋅=

BACiACiB

BACiACiBBACiACiBCo

⋅⋅⋅⋅⋅=

=⋅+⋅+⋅=⋅+⋅+⋅=

ABCi

S

Co

58

Circuito Alternativo 59

ABCi

S

Co

CiBAYAYAS ⊕⊕=⋅+⋅=

BACiBACo ⋅⋅⋅⊕= )(

Circuiti Integrati a Porte Discrete60

1 2 3 4 5 6 7

891011121314VCC

GND

DM74ALS08

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

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

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

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

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

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

Esempio

Disegnare un Carry Select Adder a 12 bit che utilizza RCA a 4 bit.

Ricavare una formula generale per esprimere i ritardi massimi

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

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 ⋅=

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

4-bit Carry Look-Ahead Adder71

a3 b3 a2 b2 a1 b1 a0 b0

c0c1

c2c3

c4

s0s1s2s3

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

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

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.

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

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.

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

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

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

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