Sistema binario

Sistema binario

∑

=

n

n

an

N 2

a

= 0 , 1 ^{2 → 10 3 → 11 59 → 111011}

A B C S D

1 1 1 1

0 0 1 0 1 1 0

1

1 1 0 1

1 0 1 1

1 0 0 0

0 1 1 1

0 1 0 0

0 0 1 0

0 0 0 0

Tavola dell’addizione

A bit primo addendo B bit secondo addendo

C bit riporto precedente somma S bit somma

D bit riporto

101 11

10 + = 5 3

2 + =

Algebra di Boole

Porte Logiche

A 1 0

0 1

A B

1 0

1 1 1

0 1 0

A B

1 0

1 1 0

0 0 0

A B

1 0

1 0 1

0 1 0

B A +

OR AND

B A

NOT

XOR

A

B A B

A B

A / = +

A B

0 0

0 1 1 1

0 1 0 0

1 0

1 1 0 0

1 0 0

0 0 1

1 1 1

0 1 0

A B A B A B A B + A B

B A B

A + =

B A

AB = +

BC AC

C B

A + ) = + (

A B

B

A + = + BA AB =

A A =

A B

B

A / = /

( )

( ^{NOT A} ) ^Id ( ) ^A

NOT =

( ^{A B} ) ^OR ( ^{B A} )

OR , = ,

( ^{A B} ) ^AND ( ^{B A} )

AND , = ,

( ^{A B} ) ^XOR ( ^{B A} )

XOR , = ,

( ^{B C} ) ( ^{A B} ) ^C

A + + = + +

( ) ( ) ^{BC AB C}

A =

( ^{A B} )( ^{A C} )

C B

A + = + +

B A

B A

B

A / = / = /

Sommatore Logico

( ^{A B} ) ^C

S = / / ^{D =} ( ^{A / B} ) ^{C + AB}

A B AB A/B C (A/B)/C S (A/B)C (A/B)C+AB 1

1 0 0 0 0 0

0

0

0

1 1 1 0 1 0 0 1

0 1 0 0

0 0

D

1 1

1 1 0 1 0 0 0 0

0 1 0 1 1 0 0

0 1 1 1 1 0

1 1 1

0

1 1 0

1 0 0 1 0 1 1

1 0 1

1 0 0

0 1 1

0 1 0

0 0

0 1

0 0 0

Porte Logiche

Realizzazioni fisiche delle porte logiche Circuiti elettro-meccanici

OR

NOT AND

V_ds

V_gs

input

output R

n p n

V_g

MOSFET

drain gate

source

Circuiti elettronici NOT

NAND

V_ds

output

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

R C

A

B

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

AB C =

V_ds

R

B A

C = +

A B

C

Porte Logiche Reversibili

Input Output

AND non è reversibile NOT è reversibile

La formulazione della MQ con Osservabili Autoaggiunte ed Evoluzione Unitaria è REVERSIBILE

i i

f

A B

B = ⊕

A_i B_i A_f B_f

0 0 0

0 1 1

0

0 1 1

1 0 1

1 1 0

CONTROL – NOT (CN)

⎩ ⎨

⎧

=

= =

= 1

0

i i

i i

f i

f

B se A

A se B B

A A

i i

i i i

i

f

A B A B A B

B = + = /

Bit di controllo

Bit target

A_i A_f

B_f

B_i CN

CONTROL - CONTROL – NOT (CCN)

(Toffoli)

C

= A

B

⊗ C

A_i B_i C_i A_f B_f C_f

0 0 1 0

0 1 1 0 1 1

1 0 0 1 0 0

1 0 1 1 0 1

1 1 0 1 1 1

0 0

1

1 0

1 0 0 0

1

0 0 0

1 0 0

0 1

1 1

⎩ ⎨

⎧ = =

=

=

= C altrimenti

B A

se C C

B B

A A

i

i i

i f

i f

i f

1

Bits di controllo

Bit target

A_i A_f

B_f B_i

C_f

C_i CCN

Porta Universale

•A

=B

=1 NOT

•A_i=1

CN

•C_i=0

AND

i

f

C

C =

i i

f

B C

C = ⊗

i i

f

A B

C =

Sommatore Reversibile

( )

( )

( ) ( )

(

) (

)

f

i i i i i

i f

i i

i i

i i i

i i i

C B

A C

B C

B A C B A D

C B D

B A B

A B

B A ,D

,B A D

D

/ /

,

, , / ,

,

/ ,

, 0

1

1 1

1 1

=

=

=

=

=

=

=

=

=

CN

CCN CCN

CN CCN

A B C D

1 1 1

1 1

1 0 1 1

1 0 1 1

0

1 1 1

1 0 1

CCN(A,B,D)

Circuito logico:

1. Porte logiche 2. Fili

addendi resto controllo

B_i C_i D_i

CN(A,B)

A_i A_f

B_f C_f D_f CCN CCN

CN

CN

CCN(B,C,D) CN(B,C)

somma resto

Porta di Fredkin

CONTROL – EXCHANGE (F-gate)

A_i B_i C_i A_f B_f C_f

0 0 1 0

0 1 1 0 1 1

1 0 0 1 0 0

1 0 1 1 1 0

1 1 0 1 0 1

1 0

1

1 0

1 0 0 0

1

0 0 0

1 0 0

0 1

1 1

⎪⎪

⎩

⎪⎪

⎨

⎧

⎭ =

⎬⎫

⎩⎨

⎧

⎭ =

⎬⎫

⎩⎨

⎧

⎭ =

⎬⎫

⎩⎨

= ⎧

1 0

i i

i

i i

i

f f i

f

A B se

C

A C se

B C

A B A

A_i A_f

B_f B_i

C_f C_i

Porta Universale

•C_i=0

AND