Compiti scritti di Architettura degli Elaboratori: A.A. 2000/2001
Lunedi 04 Giugno 2001 (Parte di reti logiche)
------------------------------------------------------------------------
Parte B: reti logiche e aritmetica binaria
------------------------------------------------------------------------
1) Utilizzando il procedimento delle Mappe di Karnaugh, progettare una rete
combinatoria "P" in forma SP che implementi il prodotto binario di valori
espressi su due bit.
________
x1 -->| |--> r3
x0 -->| "P" |--> r2
y1 -->| |--> r1
y0 -->| |--> r0
--------
Dati 4 bit in ingresso rispettivamente x1,x0 e y1,y0 (ovvero due interi
espressi in binario naturale su due bit), la rete P produce i 4 bit
(r3,r2,r1,r0) che esprimono il valore in binario naturale del prodotto.
(es. 3 X 2 = 6 equivale a 11 X 10 = 0110)
Per maggiore chiarezza, questo e' lo schema aritmetico del prodotto richiesto
(dove r1# e' il riporto generato dal calcolo della somma che produce r1,
ed r3 e' il riporto della somma che produce r2):
x1 x2 X
y1 y2 =
-----
(r1#) y2*x1 y2*x2 +
y1*x1 y1*x2 0
------------------
r3 r2 r1 r0
Riportare per intero le tabelle di verita`, le mappe di Karnaugh e le
espressioni finali ottenute in forma SP, ed una traccia scritta del
procedimento seguito.
### Svolgimento:
Tabelle di verita delle 4 funzioni da realizzare (r3, r2, r1, r0)
x1 x0 y1 y0 | r3 r2 r1 r0
-------------------------
0 0 0 0 | 0 0 0 0 (00 x qls. cosa = 0000)
0 0 0 1 | 0 0 0 0
0 0 1 0 | 0 0 0 0
0 0 1 1 | 0 0 0 0
0 1 0 0 | 0 0 0 0
0 1 0 1 | 0 0 0 1 (01 x 01 = 0001)
0 1 1 0 | 0 0 1 0 (01 x 10 = 0010)
0 1 1 1 | 0 0 1 1 ecc.
1 0 0 0 | 0 0 0 0
1 0 0 1 | 0 0 1 0
1 0 1 0 | 0 1 0 0
1 0 1 1 | 0 1 1 0
1 1 0 0 | 0 0 0 0
1 1 0 1 | 0 0 1 1
1 1 1 0 | 0 1 1 0
1 1 1 1 | 1 0 0 1
Mappe di Karnaugh
r3: somma mintermini (15)
\ y1 y0
x1 x0
0 0 0 0
0 0 0 0 = (x1 x0 y1 y0)
0 0 1 0
0 0 0 0
r2: somma mintermini (10, 11, 14)
\ y1 y0
x1 x0
0 0 0 0
0 0 0 0 = (x1 !y0 y1)+(!x0 x1 y1)
0 0 0 1
0 0 1 1
r1: somma mintermini (6, 7, 9, 11, 13, 14)
\ y1 y0
x1 x0
0 0 0 0
0 0 1 1 = (x1 y0 !y1)+(!x0 x1 y0)+(x0 !y0 y1)+(x0 !x1 y1)
0 1 0 1
0 1 1 0
r0: somma mintermini (5, 7, 13, 15)
\ y1 y0
x1 x0
0 0 0 0
0 1 1 0 = (x0 y0)
0 1 1 0
0 0 0 0
2) A quale valore decimale in virgola mobile corrisponde la rappresentazione
IEEE 754 in singola precisione (su 32 bit) con base di polarizzazione per
l'esponente pari a 127 (01111111):
0 10000000 11000000000000000000000
### Svolgimento:
esponente = 10000000 - 01111111 = +1
mantissa = (1).11000000000000000000000
valore decimale = 1.11 x 2^1 = 11.1 x 2^0 = 3.5 in base 10
3) Avendo a disposizione solamente l'architettura di una ALU che esegua
l'operazione di somma tra valori binari interi su 8 bit, e assumendo di
poter ricorrere ad una seconda componente architetturale che permetta di
convertire la rappresentazione dei valori binari in complemento a due,
e' possibile eseguire l'operazione di differenza (45 - 18)? e (18 - 45)?
Giustificare la risposta, eventualmente mostrando il procedimento che
conduce al risultato corretto (usando la rappresentazione binaria).
### Svolgimento:
Si, e' possibile in quanto la somma binaria naturale permette la somma
e la sottrazione di valori espressi in complemento a due.
es. 45 - 18 = (su 8 bit)
45 + 00101101 +
(-18) 11101110
---- ------
+27 1 00011011 (somma di valori discordi non da overflow!
quindi perdo il bit di riporto)
18 - 45 = (su 8 bit)
18 + 00010010
(-45) 10101011
---- ------
-27 10111101
------------------------------------------------------------------------
Lunedi 9 Luglio 2001 (Parte di reti logiche)
------------------------------------------------------------------------
Parte B: reti logiche e aritmetica binaria
------------------------------------------------------------------------
1) Progettare una rete sequenziale "S" che riceva in input una sequenza di
bit (ingresso x(t)) potenzialmente infinita, a partire da un tempo iniziale t0.
L'uscita Z(t) della rete P vale 1 se e solo se la sequenza di bit ricevuta
in ingresso dal tempo t0 fino al tempo t contiene un numero di 1 multiplo
di 3 (e maggiore di zero).
________
| |
x(t)...10100110100 x ->| "P" |--> Z(t) ...00001100000
| |
r ->| |-->
| -------- |
| |
|-------------|
linee di retroazione
Progettare l`automa di Mealy (o di Moore) per la codifica e la minimizzazione
degli stati, la rete combinatoria P in forma SP che genera l`uscita Z e le
linee di retroazione (r) utilizzando i metodi visti a lezione.
Riportare per intero le tabelle, le mappe, i procedimenti e le
espressioni finali ottenute in forma SP, ed una traccia scritta del
procedimento seguito.
### Svolgimento:
Automa di Moore codificato in tabella di flusso:
input 0 1
(stato iniziale) A A,0 B,0
B B,0 C,0
C C,0 D,1
D D,1 B,0
Minimizzazione automa
B bc
C x x
D x x x
A B C
e quindi
B x
C x x
D x x x
A B C
occorrono 4 stati, e quindi due bit per codificare lo stato e quindi
due linee di retroazione (s1' e s0'): siano
s1' s0'
A = 0 0
B = 0 1
C = 1 0
D = 1 1
tabella di verita' delle funzioni Z(t) e Stato successivo (s1',s0' ovvero
le due linee di retroazione)
s1 s0 x | s1' s0' Z(t)
----------------------
0 0 0 | 0 0 0 (se sono in A con input 0 rimango in A, Z=0)
0 0 1 | 0 1 0 (ecc. )
0 1 0 | 0 1 0
0 1 1 | 1 0 0
1 0 0 | 1 0 0
1 0 1 | 1 1 1
1 1 0 | 1 1 1
1 1 1 | 0 1 0
Mappe di Karnaugh
s1': somma mintermini (3,4,5,6)
\ s0 x
s1
0 0 1 0
1 1 0 1 = (!s1 s0 x)+(s1 !s0)+(s1 !x)
s0': somma mintermini (1,2,5,6,7)
\ s0 x
s1
0 1 0 1
0 1 1 1 = (!s0 x)+(s0 !x)+(s1 s0)
Z(t): somma mintermini (5,6)
\ s0 x
s1
0 0 0 0
0 1 0 1 = (s1 !s0 x)+(s1 s0 !x)
2) Assumendo di usare la rappresentazione in virgola mobile IEEE 754
in singola precisione (su 32 bit) con base di polarizzazione per
l`esponente pari a 127 (01111111), tradurre il valore a) in decimale,
ed il valore b da decimale a rappresentazione IEEE 754:
a) 0 10000011 11010000000000000000000 equivale a ...............
svolgimento:
segno +
esponente = 10000011 - 01111111 = 131-127 = +4
mantissa = 1.1101000... x 2^4 = 11101.0000... x 2^0 = 29
b) . ........ ....................... equivale a -7.25
svolgimento:
segno: 1
parte intera: 7 = 111 (alg. della divisione e prendo i resti)
parte frazionaria = 0.25 x2 = 0.50 --> 0
0.50 x2 = 1.00 --> 1
0.00 x2 = 0.00 --> 00000...
mantissa = 111.010000...x2^0
normalizzo = 1.1101000 x2^2
esponente (base polarizz. 127) = 2+127 = 129 = 10000001
e quindi si ottiene: 1 10000001 110100000000000000
In seguito si esprima il valore della somma (a+b) in formato IEEE 754.
a + b = . ........ .......................
a = 1.1101000... x 2^4
b = 1.1101000... x 2^2
porto nello stesso esponente (il minore dei due)
a = 111.01000... x 2^2
b = 1.1101000... x 2^2
faccio la sottrazione in binario delle mantisse allineate
a = 111.01000... x 2^2 +
b = 001.1101000... x 2^2
------------
= 101.01110... x 2^2
normalizzo il risultato
= 1.0101110... x 2^4
per cui segno +, esponente = 4+127 = 131 = 10000011
(a+b) = 0 10000011 0101110000...
3) Quali delle seguenti operazioni eseguite con aritmetica binaria in
complemento a due su 4 bit generano un overflow?
Giustificare le risposte.
a) 0111 + 0111 = .... overflow! 1110 e' negativo (+ + + = -)
b) 1111 + 0111 = .... ok. 0110 (il bit che esce non e' OV)
c) 1000 + 1111 = .... overflow! (- + - = +)
d) 1001 + 0111 = .... ok. 0000 (il bit che esce non e' OV)
e) 1000 + 1000 = .... overflow (- + - = +)
f) 1010 - 0010 = .... ok. 1000 (il bit che esce non e' OV)
g) 1111 - 1000 = .... ok. 0111 (il bit che esce non e' OV)
h) 1000 - 0001 = .... overflow! (- - + = +)
i) 0111 - 1111 = .... overflow! (+ - - = -)
l) 0111 - 0001 = .... ok. 0110 (il bit che esce non e' OV)
m) 1010 - 0011 = .... overflow! (- - + = +)
------------------------------------------------------------------------
Martedi 4 Settembre 2001 (Parte di reti logiche)
------------------------------------------------------------------------
Parte B: reti logiche e aritmetica binaria
------------------------------------------------------------------------
1) Una rete sequenziale "S" riceve in input una sequenza di bit x(t),
potenzialmente infinita, da intendersi come la rappresentazione binaria
in complemento a due di un valore intero.
Assumendo che i bit entranti siano ordinati dal bit meno significativo (LSB)
al piu' significativo (MSB), si vuole realizzare un circuito automatico
sequenziale (bit a bit) per il complemento a due.
Il complemento a due di una rappresentazione binaria si ottiene
complementando tutti i bit e quindi sommando il valore uno al valore ottenuto.
L'uscita Z(t) della rete P restituisce quindi la sequenza di bit, ordinata dal
bit LSB al bit MSB, del valore opposto (in complemento a due) rispetto al
valore ricevuto in ingresso.
(es. il valore 59 = 00111011 diventa -59 = 11000101, e viceversa)
________
MSB LSB | | MSB LSB
x(t)...00111011 x ->| "P" |--> Z(t) ...11000101
| |
r ->| |-->
| -------- |
| |
|-------------|
linee di retroazione
Progettare l`automa di Moore (o di Mealy) per la codifica e la minimizzazione
degli stati, la rete combinatoria P (in forma SP) che genera l`uscita Z e le
linee di retroazione (r) utilizzando i metodi visti a lezione.
Riportare gli automi, le tabelle di flusso e di minimizzazione, le mappe di
Karnaugh, le espressioni finali in forma SP, ed una traccia scritta del
procedimento seguito.
Automa di Moore codificato in tabella di flusso:
input 0 1
(stato iniziale) A B,0 E,1
B B,0 C,1
C C,1 D,0
D C,1 D,0
E E,1 F,0
F E,1 F,0
Minimizzazione automa
B ec
C x x
D x x o
E x x df ce,df
F x x ce,df ce o
A B C D E
e quindi
B o
C x x
D x x o
E x x o o
F x x o o o
A B C D E
occorrono 2 stati (alfa e beta), e quindi due bit per codificare lo
stato e quindi due linee di retroazione s0': siano
s0'
Alfa = (A,B) = 0
Beta = (C,D,E,F) = 1
tabella di verita' delle funzioni Z(t) e Stato successivo (s1',s0' ovvero
le due linee di retroazione)
s0 x | s0' Z(t)
-------------------
0 0 | 0 0 (se sono in Alfa con input 0 rimango in A, Z=0)
0 1 | 1 1 (ecc. )
1 0 | 1 1
1 1 | 1 0
Mappe di Karnaugh
s0': somma mintermini (1,2,3)
\ x
s0
0 1
1 1 = s0 + x
Z(t): somma mintermini (1,2)
\ x
s0
0 1
1 0 = s0!x + !s0x
2) Assumendo di usare la rappresentazione in virgola mobile IEEE 754
in singola precisione (su 32 bit) con base di polarizzazione per
l`esponente pari a 127 (01111111), tradurre il valore a) in decimale,
ed il valore b da decimale a rappresentazione IEEE 754:
a) 1 10000100 10010110000000000000000 equivale a ...............
svolgimento:
segno -
esponente = 10000100 - 01111111 = 132-127 = +5
mantissa = 1.1001011000... x 2^5 = 110010.11000... x 2^0 = -50.75
b) . ........ ....................... equivale a +22.50
svolgimento:
segno: 0
parte intera: 22 = 10110 (alg. della divisione e prendo i resti)
parte frazionaria = 0.50 x2 = 1.00 --> 1
0.00 x2 = 0.00 --> 00000...
mantissa = 10110.10000...x2^0
normalizzo = 1.0110100000... x2^4
esponente (base polarizz. 127) = 4+127 = 131 = 10000011
e quindi si ottiene: 1 10000011 011010000000000000
In seguito si esprima il valore della somma (a+b) in formato IEEE 754.
a + b = . ........ .......................
a = -1.1001011000... x2^5
b = 1.0110100000... x2^4
porto nello stesso esponente (il minore dei due)
a = -11.001011000... x2^4
b = 1.0110100000... x2^4
faccio la sottrazione in binario delle mantisse allineate
N.B. siccome |a| > |b| faccio b-a e poi ricordo di invertire il segno.
11.0010110000 -
1.0110100000
-------------
01.1100010000 x 2^4
risultato gia' normalizzato
per cui segno -, esponente = 4+127 = 131 = 10000011
(a+b) = 1 10000011 1100010000...
3) Quali sono tutte le possibili rappresentazioni dello zero, su 8 bit,
in notazione
a) binario naturale: 00000000
b) binario in complemento a uno: 00000000 e 11111111
c) binario in complemento a due: 00000000
d) binaria polarizzata con base 127 (N.B. non IEEE 754): 01111111
e) binaria polarizzata con base 128 (N.B. non IEEE 754): 10000000
Quale e` il valore negativo (in base 10), con il massimo valore assoluto,
che e` possibile rappresentare, su 8 bit, in notazione
f) binario naturale: nessun valore negativo rappresentabile
g) binario in complemento a uno: -127 (10000000)
h) binario in complemento a due: -128 (10000000)
i) binaria polarizzata con base 127 (N.B. non IEEE 754): -127 (00000000)
l) binaria polarizzata con base 128 (N.B. non IEEE 754): -128 (00000000)
Giustificare le risposte.
------------------------------------------------------------------------
Lunedi 24 Settembre 2001 (Parte di reti logiche)
------------------------------------------------------------------------
Parte B: reti logiche e aritmetica binaria
------------------------------------------------------------------------
1) Progettare una rete sequenziale "S" che riceva in input due sequenze di
bit sincrone (ingresso x1(t) e x2(t)) potenzialmente infinite, a partire
da un tempo iniziale t0.
L'uscita Z(t) della rete P vale 1 se e solo se le due sequenze differiscono
di un numero di bit multiplo di 3 (maggiore di zero), dal tempo t0 fino al
tempo t.
________
| |
x1(t)...00100011100 ->| "P" |--> Z(t) ...01111100000
x2(t)...10100110110 ->| "P" |
| |
r ->| |-->
| -------- |
| |
|-----<-------|
linee di retroazione
Progettare l automa di Mealy (o di Moore) per la codifica e la minimizzazione
degli stati, la rete combinatoria P in forma SP che genera l uscita Z e le
linee di retroazione (r) utilizzando i metodi visti a lezione.
Riportare per intero le tabelle, le mappe, i procedimenti e le
espressioni finali ottenute in forma SP, ed una traccia scritta del
procedimento seguito.
Svolgimento:
Automa di Moore codificato in tabella di flusso:
input 00 01 10 11
(stato iniziale) A A,0 B,0 B,0 A,0
B B,0 C,0 C,0 B,0
C C,0 D,1 D,1 C,0
D D,1 B,0 B,0 D,1
Minimizzazione automa
B bc
C x x
D x x x
A B C
e quindi
B x
C x x
D x x x
A B C
occorrono 4 stati, e quindi due bit (s1 e s0) per codificare lo stato e quindi
ponendo A=00, B=01, C=10, D=11 si ottiene la seguente tabella di verita`.
s1 s0 x2 x1 | s1` s0` Z
-----------------------
0 0 0 0 | 0 0 0 (se sono in A e arriva 00 rimango in A, Z=0)
0 0 0 1 | 0 1 0
0 0 1 0 | 0 1 0
0 0 1 1 | 0 0 0
0 1 0 0 | 0 1 0
0 1 0 1 | 1 0 0
0 1 1 0 | 1 0 0
0 1 1 1 | 0 1 0
1 0 0 0 | 1 0 0
1 0 0 1 | 1 1 1
1 0 1 0 | 1 1 1
1 0 1 1 | 1 0 0
1 1 0 0 | 1 1 1
1 1 0 1 | 0 1 0
1 1 1 0 | 0 1 0
1 1 1 1 | 1 1 1
dalla quale trovo le tre mappe di Karnaugh:
s1`:
x2,x1 00 01 11 10
s1,s0
00 0 0 0 0
01 0 1 0 1
11 1 0 1 0 = s1!s0 + s1!x2!x1 + s1x2x1 + s0!x2x1 + s0x2!x1
10 1 1 1 1
s0`:
x2,x1 00 01 11 10
s1,s0
00 0 1 0 1
01 1 0 1 0
11 1 1 1 1 = s1s0+s1!x2!x1+s0!x2!x1+s1x2x1+s0x2x1+...
10 1 0 1 0 ...+!s1!s0!x2x1+!s1!s0x2!x1
Z:
x2,x1 00 01 11 10
s1,s0
00 0 0 0 0
01 0 0 0 0
11 1 0 1 0 = s1s0!x2!x1+s1!s0!x2x1+s1s0x2x1+s1!s0x2!x1
10 0 1 0 1
2) Assumendo di usare la rappresentazione in virgola mobile IEEE 754
in singola precisione (su 32 bit) con base di polarizzazione per
l`esponente pari a 127 (01111111), tradurre il valore a) in decimale,
ed il valore b da decimale a rappresentazione IEEE 754:
a) 0 10000101 11010101000000000000000 equivale a ...............
Svolgimento:
segno: +
esponente: 10000101 - 01111111 = 133-127 = +6
mantissa: 1.11010101000...x2^6 = 1110101.01 x 2^0 = +117.25
b) . ........ ....................... equivale a 19.5625
Svolgimento:
segno: 0
parte intera: 19 = 10011
parte frazionaria: 0.5625x2 = 1.125 --> 1
0.125 x2 = 0.250 --> 0
0.250 x2 = 0.500 --> 0
0.500 x2 = 1.000 --> 1
0.000 x2 = 0.000 --> 000000...
mantissa: 10011.100100000 x2^0
mantissa normalizzata: 1.00111001000...x2^4
esponente: 127+4 = 131 = 10000011
e quindi: b = 0 10000011 00111001000000000000000
In seguito si esprima il valore della somma (a+b) in formato IEEE 754.
a + b = . ........ .......................
Svolgimento:
porto in forma con stesso esponente (minore)
a 1.11010101000...x2^6 = 111.010101000 x2^4
b 1.00111001000...x2^4
ora sommo le mantisse allineate
a 111.010101000... x2^4
b 1.00111001000...x2^4
------------------------
1000.100011010000 x 2^4
normalizzo il risultato
1.000100011010000 x 2^7
esponente: 7+127 = 134 = 10000110
e quindi (a+b) = 0 10000110 00010001101000000000000
e si esprima il valore della parte intera di (a+b) in esadecimale.
a + b = ......... esadecimale
Svolgimento:
1.000100011010000 x 2^7 = 10001000.110100000 x2^0
quindi la parte intera e'
10001000: raccogliendo da LSB (dx) i bit a 4 a 4 ottengo
1000 1000 che equivalgono alle due cifre 88 hex
3) Quali delle seguenti operazioni eseguite su una rappresentazione IEEE754
su 32 bit, con base di polarizzazione 127 (01111111) generano overflow oppure
underflow? Assumere di usare solo rappresentazioni normalizzate, e di avere
a disposizione tutti i valori rappresentabili dell`esponente su 8 bit.
Giustificare le risposte.
(Gli esponenti rappresentabili vanno quindi da -127 a +128...)
(N.B. la mantissa va sempre normalizzata, il segno del numero non va
confuso col segno dell'esponente, e attenzione all'operazione effettuata)
a) 1*2^127 + 1*2^127 = 2*2^127 = 1*2^128 ok
b) 1*2^128 + 1*2^128 = 2*2^128 = 1*2^129 overflow
c) -1*2^127 - 1*2^127 = -2*2^127 = -1*2^128 ok
d) 1*2^(-127) / 1*2^1 = 1*2^(-127-1) underflow
e) 1*2^64 * 1*2^64 = 1*2^(64+64) ok
f) -1*2^64 * 1*2^65 = -1*2^(64+65) = -1*2^129 overflow
g) 1*2^127 - 1*2^128 = (1-2)x2^127 = -1*2^127 ok
h) 1*2^(-127) * 1*2^128 = 1*2^(-127+128) = 2 ok
i) -1*2^127 + 1*2^127 = 0 ok
l) 1*2^(-127) * 1*2^(-1) = 1*2^(-127-1) = 1*2^(-128) underflow
------------------------------------------------------------------------
Lunedi 3 Giugno 2002 (Parte di reti logiche)
Progettare una rete sequenziale "S" che riceva in input una sequenza di bit di
ingresso x(t) potenzialmente infinita, a partire da un tempo iniziale t0.
Si deve realizzare una rete che assuma output Z(t)=1 se e solo se l'ultima coppia di valori
di input osservati (x(t),x(t-1)) hanno lo stesso valore.
La rete deve produrre output Z(t)=0 durante l'attesa e l'input del primo valore della sequenza.
________
| |
x(t)...01001101001 ->| "P" |--> Z(t) ...00101000100
| |
r ->| |-->
| -------- |
| |
|-----<-------|
linee di retroazione
Progettare l'automa di Moore, effettuare la minimizzazione degli stati ottenendo
l'automa minimo in forma di Mealy, e progettare la rete combinatoria P in forma
SP che genera l'uscita Z e le linee di retroazione (r) utilizzando i metodi visti
a lezione. Riportare per intero le tabelle, le mappe, i procedimenti e le espressioni
finali ottenute in forma SP, ed una traccia scritta del procedimento seguito.
Svolgimento:
Automa di Moore (in forma tabella di flusso)
0 1
A B,0 C,0
B D,1 C,0
C B,0 E,1
D D,1 C,0
E B,0 E,1
Minimizzazione:
B X
C X X
D X O X
E X X O X
A B C D
Automa minimo: 3 stati (due bit per codifica (s1, s0), scelta arbitraria)
{A} = 00
{BD} = 01
{CE} = 10
Tabella di verità:
s1 s0 x(t) | s1' s0' Z(t)
-------------------------
0 0 0 | 0 1 0 se sono in {A} e arriva 0 vado in {BD} e Z=0...
0 0 1 | 1 0 0
0 1 0 | 0 1 1
0 1 1 | 1 0 0
1 0 0 | 0 1 0
1 0 1 | 1 0 1
1 1 0 | X X X lo stato 11 non esiste, quindi le funzioni binarie
1 1 1 | X X X hanno dei gradi di libertà che posso sfruttare nella
copertura degli implicanti.
Mappe di Karnaugh:
s1':
\ s0 x
s1
0 1 1 0 0 1 1 0
0 1 X X = 0 1 1 0 = s1' = x
s0':
\ s0 x
s1
1 0 0 1 1 0 0 1
1 0 X X = 1 0 0 1 = s0' = !x
Z(t):
\ s0 x
s1
0 0 0 1 0 0 0 1
0 1 X X = 0 1 1 1 = Z(t) = s1x + s0!x
Esercizio 2
Assumendo di usare la rappresentazione in virgola mobile IEEE 754 in singola
precisione (su 32 bit) con base di polarizzazione per l'esponente pari a 127
(01111111), tradurre il valore (a) in decimale, ed il valore (b) da decimale
a rappresentazione IEEE 754:
a) 0 10000010 01010100000000000000000 equivale a ____________
segno: +
esponente: 10000010 - 01111111 = 130-127 = +3
mantissa: 1.0101010000 x 2^3 = 1010.1010000 x 2^0
a= + (8+2+1/2+1/8) = +10.625
b) _ ________ _______________________ equivale a -33.125
segno - : bit 1
parte intera: 33:2 = 16 resto 1 (msb)
16:2 = 8 resto 0
8 :2 = 4 resto 0
4 :2 = 2 resto 0
2 :2 = 1 resto 0
1 :2 = 0 resto 1 (lsb)
parte frazionaria:
0.125 x 2 = 0.250 parte intera 0 (msb parte frazionaria)
0.250 x 2 = 0.500 parte intera 0
0.500 x 2 = 1.000 parte intera 1
0.000 x 2 = 0.000 parte intera 0....
mantissa : 100001.0010000... x 2^0, normalizzo: 1.000010010000...x2^5
esponente = 5 = (127+5=132) = 01111111 + 00000101 = 10000100
b) = 1 10000100 00001001000000000000000
Esercizio 3:
Completare la seguente tabella trasformando il valore espresso su ogni riga
nel valore corrispondente alla rappresentazione sulle altre colonne. Valori
binari vanno rappresentati su 8 bit. Denotare con X i valori non
rappresentabili.
Decimale Binario naturale Compl. a Due Polarizzata(b.p.127)
a) ____0____ __00000000___ __00000000__ 01111111
b) ___255___ 11111111 _____X______ ______X_____
c) 100 __01100100___ __01100100__ __11100011__
d) ___-1____ ______X______ 11111111 __01111110__
e) -128 ______X______ __10000000__ ______X_____
f) 127 __01111111___ __01111111__ __11111110__
------------------------------------------------------------------------
Venerdi 5 Luglio 2002 (Parte di reti logiche)
Progettare una rete sequenziale "S" che riceva in input una sequenza di bit
(ingresso x(t)) potenzialmente infinita, a partire da un tempo iniziale t0.
L'uscita Z(t) della rete P vale 1 se e solo gli ultimi tre bit della sequenza
di bit ricevuta in ingresso realizzano una sequenza palindroma. (cioe' la
sequenza degli ultimi tre bit rimane uguale se letta da sx a dx e viceversa).
Assumere lo stato iniziale della rete determinato dalla sequenza fornita dai bit
dell'esercizio precedente (x2,x1,x0).
Progettare l'automa di Moore per la codifica e la minimizzazione degli stati,
l'automa di Mealy minimo, le mappe di Karnaugh, la rete combinatoria P in forma
SP e PS che genera l'uscita Z e le linee di retroazione (r) utilizzando i metodi
visti a lezione.
Riportare per intero gli automi, le tabelle, le mappe, le espressioni finali
ottenute in forma SP e PS, ed una traccia scritta del procedimento seguito (non
si deve disegnare alcuna rete).
Svolgimento: assumiamo (x2,x1,x0) = (001).
L'automa di Moore iniziale ha la seguente tabella di transizione (assumendo gli
stati etichettati con un nome equivalente alla memoria degli ultimi tre bit di
input):
0 1
A=001 B,1 C,0
B=000 B,1 C,0
C=100 E,1 D,0
D=110 G,0 H,1
E=010 A,0 F,1
F=101 E,1 D,0
G=011 A,0 F,1
H=111 G,0 H,1
La tabella di minimizzazione diventa:
B O
C (be),(cd) (be),(cd)
D X X X
E X X X (ga),(hf)
F (be),(cd) (be),(cd) O X X
G X X X (ga),(hf) O X
H X X X X (ga),(hf) X (ga),(hf)
A B C D E F G
per cui risultano indistinguibili gli stati:
Alfa = (A,B)
Beta = (C,F)
Gamma = (D,H)
Delta = (E,G)
essendo 4 stati bastano due bit per la codifica (s1 e s0)
s1 s0
Alfa = 0 0
Beta = 0 1
Gamma = 1 0
Delta = 1 1
L'automa di Mealy minimo diventa:
0 1
Alfa Alfa,1 Beta,0
Beta Delta,1 Gamma,0
Gamma Delta,0 Gamma,1
Delta Alfa,0 Beta,1
La tabella di verita' completa ottenuta diventa:
s1 s0 X | s1' s0' Z
0 0 0 | 0 0 1
0 0 1 | 0 1 0
0 1 0 | 1 1 1
0 1 1 | 1 0 0
1 0 0 | 1 1 0
1 0 1 | 1 0 1
1 1 0 | 0 0 0
1 1 1 | 0 1 1
e quindi le forme SP e PS finali sono:
s1' = s1!s0 + !s1s0 (SP) = (s1+s0)(!s1+!s0) (PS)
s0' = s1!s0!X + !s1!s0X + s1s0X + !s1s0!X (SP) = (s1+s0+X)(!s1+s0+!X)(s1+!s0+!X)(!s1+!s0+X) (PS)
Z = !s1!X + s1X (SP) = (s1+!X)(!s1+X) (PS)
Esercizio 2
Assumendo di usare la rappresentazione in virgola mobile IEEE 754 in singola
precisione (su 32 bit) con base di polarizzazione per l'esponente pari a 127
(01111111), quale e' il minimo valore positivo (b) in notazione IEEE754, che
sarebbe possibile sommare ad (a), per vedere almeno un bit di differenza tra
(a) e la somma (c)=(a)+(b)? Si deve considerare solo il troncamento (e non
l'arrotondamento) della mantissa, e si deve riportare il procedimento svolto
per determinare (b) e (c).
a) 0 10000010 (x2,x1,x0)10000000000000000000 equivale a ____________
Sia (x2,x1,x0)= (001), allora
segno = +
esponente = 10000010 - 01111111 = 3
mantissa = 1.(001)1000.. x 2^3 = 1001.1000..x2^0 = +9.5
c) = a + b = _ ________ _______________________ (in notazione Standard IEEE754)
il valore minimo superiore ad (a) che si possa rappresentare con almeno un bit di
differenza rispetto ad (a) e':
c) = 0 10000010 (001)10000000000000000001
per cui b) = c-a diventa
b) = 0.00000000000000000000001 x 2^3 = 1.00000000000000000000 x2^(-20) =
= 0 01101011 00000000000000000000000
Esercizio 3
La somma di due valori discordi in complemento a due su n bit (A e B) in quali
casi determina overflow? Giustificare l'affermazione.
Mai.
I valori rappresentabili in complemento a due vanno da -2^n fino a +(2^n)-1.
Il valore della somma di due valori discordi genera sempre un valore compreso tra
i due valori iniziali (si dimostra facilmente). Ne risulta che, essendo i due valori
iniziali rappresentabili, anche il valore del risultato e' rappresentabile.
10 Settembre 2002 (Parte di reti logiche)
B/Esercizio 0
Tradurre in binario in complemento a due su 4 bit il valore opposto della penultima
cifra decimale (d1) del numero di matricola (es. Matricola = (dn..d3,d2,d1,d0) = 0..123456,
d1 = 5, tradurre –d1 = –5 in complemento a due su 5 bit).
Svolgimento: (supponiamo d1 = 9)
Penultima cifra decimale (d1) = __9__
-d1 in complemento a due (b4,b3,b2,b1,b0) = -01001 = 10110+1 = 10111
B/Esercizio 1
Siano b2, b1 e b0 i valori ottenuti nell'esercizio precedente. (e quindi 111)
Progettare una rete sequenziale "S" che riceva in input due sequenze di bit di ingresso x(t)
e y(t) potenzialmente infinite, a partire da un tempo iniziale t0.
Si deve realizzare una rete che assuma output Z(t)= 0 se e solo se le due sequenze hanno visto
l'ultimo e il terzultimo bit uguali e il penultimo bit diverso tra loro.
Assumere lo stato iniziale della rete come lo stato nel quale gli ultimi tre bit delle sequenze
erano [uguali=1, diversi=0] b2(t), b1(t-1), b0(t-2). (e quindi [uguali(t),uguali(t-1),uguali(t-2)]).
Progettare l'automa di Moore, effettuare la minimizzazione degli stati ottenendo l'automa minimo
in forma di Mealy, e progettare la rete combinatoria P in forma SP che genera l'uscita Z e le
linee di retroazione (r) utilizzando i metodi visti a lezione.
Svolgimento:
Immaginiamo di associare ad ogni stato la memoria di quello che è accaduto relativamente
all'uguaglianza o meno degli ultimi tre bit visti:
H = 111 (ultimi tre bit diversi tra loro)
G = 110 (ultimo e penultimo bit diverso, terzultimo bit uguale)
F = 101 (ultimo e terzultimo bit diverso, penultimo bit uguale) N.B. unico caso in cui Z(t)=0.
...
A = 000 (ultimi tre bit uguali tra loro)
Sono in tutto 8 possibili combinazioni.
Si assume di partire dallo stato H=111, prevedendo un arco in uscita per ogni possibile
input delle due sequenze al tempo t attuale.
In particolare, i possibili input dell'automa sono dati dalle possibili combinazioni di
input (sincrone) delle due sequenze:
input X(t)=0 e Y(t)=0 ---> 00 (cioè uguali)
input X(t)=0 e Y(t)=1 ---> 01 (cioè diversi)
input X(t)=1 e Y(t)=0 ---> 10 (cioè diversi)
input X(t)=1 e Y(t)=1 ---> 11 (cioè uguali)
Automa in forma tabella di flusso:
input x(t),y(t)
stato 00 01 10 11
A E,1 A,1 A,1 E,1
B E,1 A,1 A,1 E,1
C F,0 B,1 B,1 F,0
D F,0 B,1 B,1 F,0
E G,1 C,1 C,1 G,1
F G,1 C,1 C,1 G,1
G H,1 D,1 D,1 H,1
H H,1 D,1 D,1 H,1
Procediamo alla minimizzazione:
B O
C X X
D X X O
E eg,ac eg,ac X X
F eg,ac eg,ac X X O
G eh,ad eh,ad X X gh,cd gh,cd
H eh,ad eh,ad X X gh,cd gh,cd O
A B C D E F G
Da cui si deduce che
{AB}, {CD}, {EF}, {GH}
e che
{eg,ac} risulta distinguibile
{eh,ad} risulta distinguibile
{gh,cd} risulta indistinguibile, in quanto sia gh che cd sono indistinguibili.
Per cui vale anche {eg},{eh},{fg},{fh}.
Gli stati dell'automa minimo sono quindi tre:
Alfa = {AB}
Beta = {CD}
Gamma = {EFGH}
00 01 10 11
Alfa Gamma,1 Alfa,1 Alfa,1 Gamma,1
Beta Gamma,0 Alfa,1 Alfa,1 Gamma,0
Gamma Gamma,1 Beta,1 Beta,1 Gamma,1
A questo punto si possono denominare arbitrariamente gli stati con una coppia di bit s1,s0
e procedere alla definizione della tabella di verità.
La tabella prevede 16 combinazioni di input (s1,s0,x(t),y(t)) delle quali 4 sono indifferenti
(X) sull'output. Gli output definiti sono 3: s1', s0', Z(t) e quindi si devono scrivere 3
mappe di Karnaugh a 16 celle. Si lascia lo svolgimento relativo per esercizio.
N.B. identificando le coppie 00 e 11 come (uguali), le coppie 01 e 10 come (diverse) si
possono ridurre le celle delle mappe di karnaugh a 8 (es. ponendo uguali=1 e diverse=0),
e sostituendo a x(t),y(t) il solo bit (uguali) o (diverse).
B/Esercizio 2:
Siano d1 e d0 le due cifre decimali meno significative della matricola, e b2,b1,b0 i valori dei bit dell'esercizio 0.
Sia K = 128 + (d1*10) + d0 = ____________
Assumendo di usare la rappresentazione in virgola mobile IEEE 754 in singola precisione (su 32 bit) con base di
polarizzazione per l'esponente pari a 127 (01111111), tradurre il valore (a) in decimale, ed il valore (b) da decimale a
rappresentazione IEEE 754:
a) 0 1000001(b0) (b1,b2)000000000000000000000 equivale a ____________
Svolgimento:
1.(b1,b2)00000000 x 2^(3+b0)
b) _ __________ ___________________________ equivale a -K .4375
Svolgimento:
segno: 1 (negativo)
esponente: 10000110 (+7) in quanto il bit più significativo è sempre relativo a 2^7 (128).
mantissa: K in binario . 0111 (parte decimale 1/4+1/8+1/16)
B/Esercizio 3: 0.2
Giustificare le risposte.
Quale è il massimo valore minore di 1, rappresentabile nello Standard IEEE754 in doppia precisione (64 bit) con base
di polarizzazione 011111111111 =1023 ?
Svolgimento: il valore massimo positivo minore di uno è 1.1111111111111111111111111111111 x 2^-1
pari a 1/2+1/4+1/8+..........+1/(2^-52) . Infatti basta sommare 1 x 2^-52 alla mantissa per
ottenere UNO. Tale valore si rappresenta come
0 01111111110 111111111111111111111111111111111111111111111111111
Quale è il minimo valore maggiore di -1, rappresentabile nello Standard IEEE754 in doppia precisione (64 bit) con base
di polarizzazione 011111111111 =1023 ?
Lo stesso di prima con solo il bit di segno opposto (1).