Università di Padova
Corso “Circuiti e Sistemi Logici”
prof. Gianfranco Bilardi
prof.ssa Concettina Guerra
prof. Adalberto Zordan
Programma del corso (I)
• Rappresentazione dell’informazione
• Organizzazione di un calcolatore
– Un calcolatore semplificato (SEC)
– Linguaggio macchina
• Algebra di commutazione
• Reti combinatorie
Università di Padova - Circuiti e Sistemi Logici
2
Programma del corso (II)
• Progettazione logica
– Tecniche di minimizzazione
• Reti sequenziali
–
–
–
–
Reti asincrone
Flip-flop
reti sincrone
analisi e sintesi di reti sequenziali
Università di Padova - Circuiti e Sistemi Logici
3
• Libro di testo
– Franco P. Preparata. Introduzione alla
organizzazione e progettazione di un
elaboratore elettronico. Franco Angeli
• Pagina web
– http://www.dei.unipd.it/~guerra/CSL/index.html
Università di Padova - Circuiti e Sistemi Logici
4
Lezione 1
Rappresentazione dell’informazione
Università di Padova - Circuiti e Sistemi Logici
5
Agenda
• Rappresentazione dell’informazione (lettere e
numeri)
• Conversione di base
– Conversione di interi
– Conversione di frazioni proprie
– Programmi
• Aritmetica binaria
– Addizione
– sottrazione
Università di Padova - Circuiti e Sistemi Logici
6
Rappresentare l’informazione significa
assegnare una stringa di simboli a ciascuno
degli oggetti che vogliamo rappresentare
Università di Padova - Circuiti e Sistemi Logici
7
L’informazione si rappresenta usando un numero
finito di simboli che siano affidabili e facilmente
distinguibili
Università di Padova - Circuiti e Sistemi Logici
8
Rappresentazione binaria
• Alfabeto binario costituito dai simboli 0 e 1
• Un oggetto si rappresenta mediante una
stringa o vettore di k componenti o cifre
binarie (bit)
• Le stringhe distinte con k bit sono 2k
Università di Padova - Circuiti e Sistemi Logici
9
Dimostrazione
• Per induzione
• Base dell’induzione
– Con una componente ( k=1) si hanno 2 stringhe
distinte, 0 e 1.
• Passo dell’induzione
– Assumiamo che ci siano 2 k-1 stringhe con k-1
componenti. Aggiungendo ad ciascuna di tali
stringhe una componente a sinistra (0 o 1) si
hanno 2 x 2 k-1 = 2 k stringhe con k componenti
Università di Padova - Circuiti e Sistemi Logici
10
Rappresentazione posizionale
Dato un numero N, la sua rappresentazione in una
base b e’ una stringa di cifre b-arie della forma
N  ( an an1 . . . a0 . a 1a 2 . . . a m ) b
Il valore di N e’ dato dalla formula
n
i
i
i  m
N
a b
Università di Padova - Circuiti e Sistemi Logici
11
Conversione di interi
• Sia N un intero
N  ( a n a n 1 . . . a 0 ) b
N  anb
 a n 1 b
n
N Esempio:
90
N=(1011010)
n 1
 . . . a 0
2
N  1 2  0 2 1 2 1 2  0 2 1 2  0 2
6
5
4
3
Università di Padova - Circuiti e Sistemi Logici
2
1
0
12
Conversione di interi
• Sia N un intero
N  a 0  2 ( a1  2 a 2  2 a 3 . . .2
2
n1
an )
N  a 0  2 ( a1  2 ( a 2  . . . .2 ( a n1  2 a n )
Università di Padova - Circuiti e Sistemi Logici
13
S0  N
S i  a i  2  S i 1
.....
Sn  an ;
S n 1  a n 1  2  S n
N  a 0  2 ( a 1  2 ( a 2  . . . .2 ( a n 1  2 a n )
Università di Padova - Circuiti e Sistemi Logici
14
Procedure di Conversione (interi)
• Da binario a decimale
– Porre
Sn  an
S  a  2  S i 1
– Per i= n-1, n-2, i…0 calcolare
i
– Porre
N=S0
Università di Padova - Circuiti e Sistemi Logici
15
Esempio
• Trovare il valore di 1101001 (n=6)
S 6  1;
S5  1  2  1  3
S 4  0  2  3  6;
S 2  0  2  13  26;
S 3  1  2  6  13
S 1  0  2  26  52
S 0  1  2  52  105
Università di Padova - Circuiti e Sistemi Logici
16
Procedure di Conversione (interi)
• Da decimale a binario
– Porre
S0  N
– Per i= 0, 1, …n calcolare ai e Si-1 come resto e
quoziente della divisione di Si per 2.
Università di Padova - Circuiti e Sistemi Logici
17
Esempio
• Trovare la rappresentazione binaria di 105
S 0  105  2  52  1;
S 2  26  2  13  0;
S 4  6  2  3  0;
S1  52  2  26  0;
S 3  13  2  6  1;
S 5  3  2  1  1;
S 6  1  2  0  1;
Università di Padova - Circuiti e Sistemi Logici
18
Conversione di frazioni
• F <1 frazione
F  a 1  2
1
 a 2  2
2 F  a 1  ( a 2  2
1
2
 a 3  2
 a 3  2
Università di Padova - Circuiti e Sistemi Logici
2
3
. . .
. . . )
19
2  F i  a  ( 1 1)  F ( i  1)
.....
F  F0 ;
2  F0  a 1  F1
2  F  a 1  ( a  2  2
1
Università di Padova - Circuiti e Sistemi Logici
 a 3  2
2
. . . . )
20
Precisione
Quante cifre deve avere la rappresentazione
binaria di F per avere una precisione
confrontabile con quella decimale?
Università di Padova - Circuiti e Sistemi Logici
21
• Se n’ è il numero di cifre della
rappresentazione binaria si ha:
n'
n
2  10
 n'  n log 2 10
log 2 10  3.322
n'  n  3.32
Università di Padova - Circuiti e Sistemi Logici
22
• La rappresentazione binaria di una frazione
dovrebbe essere espressa con circa 3 volte il
numero di cifre di quella decimale
Università di Padova - Circuiti e Sistemi Logici
23
Procedura di conversione (frazioni)
• Da decimale a binario (con s bit)
– Porre F0= F;
– per i=1,2, …, s calcolare a-i e F-i come parti
intere e frazionarie del prodotto 2xF-(i-1)
Università di Padova - Circuiti e Sistemi Logici
24
Esempio:0.67578125
F0  0.67578125
2 F0  2  0.67578125  1  0.3515625
2 F1  2  0.3515625  0  0.703125
2 F2  2  0.703125  1  0.40625
2 F3  2  0.40625  0  08125
.
Università di Padova - Circuiti e Sistemi Logici
25
2 F4  2  08125
.
 1  0.625
2 F5  2  0.625  1  0.25
2 F6  2  0.25  0  05
.
2 F7  2  05
.  1 0
Università di Padova - Circuiti e Sistemi Logici
26
Procedura di conversione (frazioni)
• Da binario a decimale
Data la sequenza a-1 a-2 ...a-s
– Porre F-(s-1) = a-s /2;
– per i=s-2, s-3, …,0 calcolare
F-i = (a-(i+1) + F-(i+1)) /2
– Porre F = F0
Università di Padova - Circuiti e Sistemi Logici
27
Esempio:010101101
.
F 7
F 6
F5
F 4
F 3
F 2
 1 / 2  0.5
 (0  0.5) / 2  0.25
 (1  0.25) / 2  0.625
 (1  0.625) / 2  0.8125
 (0  0.8125) / 2  0.40625
 (1  0.4062) / 2  0.703125
Università di Padova - Circuiti e Sistemi Logici
28
F1  (0  0.703125) / 2  0.3515625
F0  (1  0.3515625) / 2  0.67578125
Università di Padova - Circuiti e Sistemi Logici
29
Riassumendo
•
*
*
•
*
*
Da Binario a decimale:
Parte intera - Metodo delle Moltiplicazioni
Parte frazionaria - Metodo delle divisioni
Da decimale a Binario:
Parte intera - Metodo delle divisioni
Parte frazionaria - Metodo delle
moltiplicazioni
Università di Padova - Circuiti e Sistemi Logici
30
Aritmetica binaria
•
•
•
•
•
Addizione
0+0=0
0+1=1
1+0=1
1+1=10
Università di Padova - Circuiti e Sistemi Logici
31
Aritmetica binaria
•
•
•
•
•
Sottrazione
0-0=0
0-1=-1
1-0=1
1-1=0
Università di Padova - Circuiti e Sistemi Logici
32
Aritmetica binaria
Università di Padova - Circuiti e Sistemi Logici
33