Architettura dei calcolatori Argomenti del corso · Codifica dei numeri naturali moltiplicazione...

1

Architettura dei calcolatori

Breve presentazione del corso

� Docenti: Davide Ancona (titolare) Giuseppe Ciaccio (esercitatore)

� CFU: 12, circa 96 h ripartite su 48 lezioni

� Esame: uno scritto finale, orale opzionale in casi eccezionali (modifica voto + o � 3 punti)

2

Argomenti del corso� Codici binari (16 h circa)� Circuiti (16 h circa)� Componenti HW (8 h circa)� Macchine CISC (8 h circa)� Microprogrammazione (10 h circa)� Macchine RISC (10 h circa)� Aspetti più avanzati (10 h circa)� Miglioramento prestazioni (10 h circa)� Linguaggi ad alto livello (8 h circa)

3

Livelli di astrazione

Linguaggi ad alto livello

Macchine RISC, CISC, aspetti avanzati

Microprogrammazione, miglioramento delle prestazioni

Circuiti, componenti HW

Codici binari

4

Strumenti e materiale

� aula web: 2 forum, registro lezioni, quiz, altro materiale

� pagina web: testi esami scritti, risposte e soluzioni, appunti, altre info

� dispense: bastano per l'esame� libri: solo per approfondire� spiegazioni: meglio prima che finiscano

le lezioni ...

5

Integrazione con altri insegnamenti

� Programmazione e algoritmi e strutture dati: � una visione più a basso livello aiuta a capire

meglio certi meccanismi� legame tra C e linguaggi macchina

� Sistemi operativi: soprattutto per gli aspetti avanzati

6

Codici binari

Insieme di tutte le codifiche binarie

succ({0,1}) = tutte le successioni di bit finite e infinite (numerabili)

Def. più formale: insieme di tutte le funzioni parziali c:N {0,1} tali che per �ogni n,m�N se c(n) definito e m<n, allora c(m) definito

7

Un po' di notazioneUna conveniente rappresentazione (specialmente nel caso finito)

c = bN-1

bN-2

... b0

c(i)=bi per i=0..N-1, c(i) indefinito per i>N-1

� l'ultimo bit a destra ha pedice 0 (e non 1) e viene detto bit meno significativo

� l'ultimo bit a sinistra ha pedice N-1 (se ci sono N bit) e viene detto bit più significativo

8

Lunghezza di una codifica

Sia indef(c)={i|cod(i) indefinito}

|c| = min(indef(c)) se indef(c)��|c| = + se indef(c)=� �

Esempi:|1001| = 4, |b

N-1b

N-2 ... b

0| = N

| | = 0, |...1...1010| = +�

9

Codici binari

� ogni elemento in X deve avere (almeno) una codifica

� ogni successione in succ({0,1}) deve codificare (al più) un elemento in X

X

succ({0,1})

��

�

0 101

�

....

....

cod

decod

10

Codici binari (formalizzazione)� Negli esempi X = {�, , �, �, �, �}

� cod:X parti(succ({0,1})-{� �} funzione totaleEs.: cod( )={10,010}

� spesso per praticità è una funzione da X in succ({0,1})

Es.: cod( )=10

10, 010 vengono dette codifiche o configurazioni

11

Codici binari (formalizzazione)Negli esempi X = {�, , �, �, �, }�

� decod:succ({0,1}) X� funzione parzialeEs.: decod(110)= �

decod(111) indefinito

� codifica senza perdita di informazione (lossless)

�x X, c cod(x) decod(c)=x� � �

se tale proprietà non è verificata la codifica è lossy (con perdita di informazione) 12

Codifiche valide/non valide

� codifiche valide insieme V = { c | decod(c) definito}

� codifiche non valide: NV = { c | decod(c) indefinito}

quindi V NV = succ({0,1}) e V NV = � � �

13

Lunghezza fissa o variabile?� Presupposto: ci limitiamo a succesioni di bit di lunghezza finita e non nulla.

� lunghezza fissa: c V� � , |c|=N N costante detta lunghezza del codice

� lunghezza variabile: �c1, c2�V tali che |c1|�|c2|

� Scelta più pratica: lunghezza fissa. � Le celle di memoria hanno tutte la stessa dimensione! 14

Codici binari a lunghezza fissa

� se N è la lunghezza, sono codificabili al più 2N elementi

� proprietà di base:� 20 = 1

� 21 = 2 � 2x * 2y = 2x+y

� 2x / 2y = 2x-y, quindi 2-x = 1 / 2x

� 2x+1 � 2x = 2x

� �i=h..k

=2h + 2h+1 + ... + 2k = 2k+1 - 2h

15

Codifica dei numeri

� tutte le codifiche sono a lunghezza fissa

� codificabili solo degli intervalli finiti

� realizzazione delle operazioni� addizione (algebrica), moltiplicazione e

divisione� confronto (=, �, <, , >, )� �

� conversioni� stessa codifica, ma lunghezza diversa� codifiche diverse 16

Codifica dei numeri naturali

� N = {0,1,2,...}� Si usa un unico tipo di codifica

� decod(bN-1

bN-2

... b0) = �

i=0..N-1 2i*b

i

Es.: decod(01101) =

1*20 + 0*21 + 1*22 + 1*23 + 0*24 =

1 + 4 + 8 = 13

17


� cod(n) =

for i = 0..N-1

bi = n % 2

n = n / 2

return bN-1bN-2 ... b

0

n deve appartenere all'intervallo [0..2N-1]

18


� addizione (2 addendi):

si usa la seguente tabella:

addendo 1 addendo 2 riporto precedente riporto risultato0 0 0 0 00 0 1 0 10 1 0 1 00 1 1 1 01 0 0 0 11 0 1 1 01 1 0 1 01 1 1 1 1

19


� Esempio di addizione

01101 + (addendo 1)

00111 = (addendo 2)

011110 (riporti)

10100 (risultato) il primo riporto è sempre 0

l'ultimo riporto serve per l'overflow0 � ok1 overflow�

il calcolo parte dalla cifra meno significativa

20


� overflow nell'addizione:

dovuto alla lunghezza fissa del codice

il risultato può cadere fuori dall'intervallo di rappresentabilità

� sottrazione: meno interessante, visto che poi si codificano gli interi

21


� moltiplicazione e divisione

Vediamo solo un caso facile:

moltiplicazione e divisione per potenze di 2

Es.:

001011 * 000100 = 101100

tutte le codifiche con un solo bit a 1 sono potenze di 2

aggiungo 2 zeri a destra e perdo i 2 più significativi

22


� moltiplicazione per 2k:

shift aritmetico a sinistra di k posizioni

Es.: 00010110 (con k=3)

10110000 sposto tutti i bit a sinistra di 3 posizioni

le 3 posizioni rimaste liberevengono completate con bit a 0

i 3 bit più significativi vengono persi. Se uno dei bit è 1 overflow

23

�


� divisione intera per 2k:

shift aritmetico a destra di k posizioni

Es.: 01010110 (con k=3)

00001010 sposto tutti i bit a destra di 3 posizioni

le 3 posizioni rimaste liberevengono completate con bit a 0

i 3 bit meno significativi che vengono persi corrispondono al resto della divisione

24


� confronto

aN-1

...a0 < b

N-1...b

0:

for i = N-1..0

if ai != b

i return a

i < b

i

return false

25


� � modifica della lunghezza

espansione: aggiungo 0 a sinistra

Es.: 10011 � 00010011 da 5 a 8 bit

aggiunti

compressione: levo 0 a sinistra Es.: 00011011 posso scendere fino a 5 bit�

eliminabili 26

Codifica dei numeri interi

� Z={0,1,-1,2,-2,...}� Esistono diversi codici

� modulo e segno� complemento a 1� complemento a 2� eccesso 2N-1

� Intervalli� [-(2N-1-1),2N-1-1] simmetrico, 2 zeri� [-2N-1,2N-1-1] antisimmetrico, 1 zero

27

Modulo e segno

� Si aggiunge il segno a sinistra

Es. codZ(+7)=+111, cod

Z(-7)=-111

� Problema: solo 2 simboli: 0 e 1

Soluzione: + � 0, - � 1

Es. codZ(+7)=0111, cod

Z(-7)=1111

decodZ(0101)=+decod

N(101)=+5

decodZ(1110)=-decod

N(110)=-6

28

Modulo e segno

Intervallo di rappresentabilità

bN-1

bN-2

... b0

bit di segno

modulo

Il modulo codifica un naturale su N-1 bitQuindi max del modulo = 2N-1-1e intervallo = [-(2N-1-1),2N-1-1]Notare che cod(0) = {10...0,00...0}

29

Modulo e segno

� addizione algebrica complicata

segno concorde addizione dei moduli

Es.: 10110 + 10011 = 11001

segno discorde � confronto tra i moduli� sottrazione dei moduli: max - min� il segno è quello del modulo maggiore

Es.: 10100 + 00011 = 10001

30

Modulo e segno

� moltiplicazione e divisione più semplici� segno: vedi la tabella� i moduli si moltiplicano/dividono

* 0 10 0 11 1 0

Regola del segno

31

Modulo e segno

� cambio di segno ovvio� confronto

� prima confronto i bit di segno: 0 > 1� se sono concordi

� 0: come per i naturali� 1: il maggiore è quello col modulo minore

32

Modulo e segno

� modifica della lunghezza

espansione: aggiungo 0 a sinistra del modulo

Es.: 10011 � 10000011 da 5 a 8 bit

aggiunti

compressione: levo 0 a sinistra del moduloEs.: 10000011 posso scendere fino a 3 bit�

eliminabili

33

Complemento a 1

� comp(0) = 1, comp(1) = 0� positivi

come la codifica dei naturali

� negativi (complementazione bit a bit)

codZ(-n) = comp(cod

N(n))

Es.: codZ(3) = comp(cod

N(3))=comp(011)=100

� zero: codZ(0) = {0...0,1...1}

� bit di segno: 1 � -, 0 +� (zero a parte) 34

Complemento a 1

� decodZ(0b

N-2...b

0) = decod

N(b

N-2...b

0)

� decodZ(1b

N-2...b

0) =

- decodN(comp(b

N-1...b

0))

Es.: decodZ(1110) = - decod

N(0001) = -1

� intervallo di rappresentabilità

� max = decodZ(01...1) = 2N-1 � 1

� min = decodZ(10...0) = - (2N-1 � 1)

35

Complemento a 1

� operazioni aritmetiche

realizzazione diretta non semplice (a parte i non negativi)

� cambio di segno: complementazione� confronto:

� prima confronto i bit di segno: 0 > 1� se concordi, confronto come naturali

36

Complemento a 1

� modifica della lunghezza� espansione/compressione per i positivi:

come per i naturali � espansione/compressione per i negativi:

inserisco/cancello 1

Es.: 1001 � 111001 da 4 a 6 bit

Es.: 11110101 � 10101 da 8 a 5 bit

eliminabili

37

Complemento a 2

� positivi

come la codifica dei naturali

� negativi (complementazione più 1)

codZ(-n) = comp(cod

N(n)) + 0...01 (n naturale)

Es.: codZ(-3) = comp(cod

N(3)) + 001 =

= comp(011) + 001 = 101

� zero: codZ(0) = 0...0

� bit di segno: 1 � -, 0 +� 38

Complemento a 2

� decodZ(0b

N-2...b

0) = decod

N(b

N-2...b

0)

� decodZ(1b

N-2...b

0) =

- decodN(comp(b

N-1...b

0) + 0..01)

Es.: decodZ(1110) = - decod

N(0010) = -2


� max = decodZ(01...1) = 2N-1 � 1

� min = decodZ(10...0) = - 2N-1

39

Complemento a 2

� addizione: come per i naturali (escludendo il possibile riporto)

� calcolo dell'overflow� se segni discordi: mai overflow� se segni concordi:

segno risultato concorde ok

segno risultato discorde overflow

40

Complemento a 2

1001 + 1110 +

1000 = 1111 =

0001 1101

segno discordeoverflow

segno concordeok

41

Complemento a 2

� moltiplicazione e divisione

realizzazione diretta non semplice (a parte i non negativi)

� cambio di segno: complementazione + 1

(attenzione all'overflow per 10...0)� confronto:

� prima confronto i bit di segno: 0 > 1� se concordi, confronto come naturali

42

Complemento a 2

� modifica della lunghezza� espansione/compressione per i positivi:

come per i naturali � espansione/compressione per i negativi:

inserisco/cancello 1

Es.: 1001 � 111001 da 4 a 6 bit

Es.: 11110101 � 10101 da 8 a 5 bit

eliminabili

43

Eccesso 2N-1

� codZ(n) = cod

N(n + 2N-1)

� decodZ(c) = decod

N(c) � 2N-1


min = decodZ(0...0) = � 2N-1

max = decodZ(1...1) = 2N - 1 � 2N-1 = 2N-1 � 1

� 1 � +, 0 - (al contrario degli altri)�

44

Eccesso 2N-1

� addizione, moltiplicazione e divisione

realizzazione diretta non semplice

� cambio di segno: complementazione + 1

(attenzione all'overflow per 00...0)� confronto: come il codice per i naturali� modifica della lunghezza: meglio

convertire in complemento a 2, modificare la lunghezza e poi riconvertire

45

Conversioni

� complemento a 2 � eccesso 2N-1

aN-1

aN-2

...a0 comp(a�

N-1)a

N-2...a

0

� complemento a 2 � complemento a 1

0aN-2

...a0 � 0a

N-2...a

0

1aN-2

...a0

� 1aN-2

...a0-1

con l'eccezione 10...0 101...1�

N bit N+1 bit 46

Conversioni

� modulo e segno complemento a 1�

0aN-2

...a0 � 0a

N-2...a

1aN-2

...a0

1comp(� aN-2

...a0)

47

Codifica dei razionali/reali

� Q={ p/q | p�Z, q�N+}

� R={ limn +� �

s | s succ. di Cauchy in Q}

� Problema:

in un intervallo finito esistono infiniti razionali e reali:

Es.: 1/n [0..1] per ogni n � � N+

48

Codifica dei razionali/reali

� I codici hanno lunghezza fissa

X = intervallo limitato

codici con perdita di informazione!

Codifica approssimata:

Es.: decod(cod(0.2)) � 0.2

49

Codici in virgola fissa

� Sistema decimale usuale:

Es.:936.3729

� Passando alla base 2:

Es.: 101.1001

10210-1 10-4

100

22 20 2-1 2-4

decod(101.1001) = 22 + 20 + 2-1 + 2-4 = 5.5625 50


� Problema: come rappresento la virgola?

Soluzione (semplice):

posizione fissata a priori

Posizione specificabile in vari modi.

La virgola separa la posizione 20 dalla

posizione 2-1.

Per ora tralasciamo i valori negativi.

51


� Fissiamo N = 7 e c = 1011001� 2 cifre intere: 10.11001� 2 cifre frazionarie: 10110.01

� cifra più significativa corrisponde a 23:

1011.001

� cifra più significativa corrisponde a 2-4:

101.1001

52


� decodifica:

decod(bk+N-1

...bk) = �

i=k..k+N-1 2i * b

i

k = esponente bit meno significativo

Es.: N = 5, k = -3

decod(10110) = 21 + 2-1 + 2-2 =

= 2 + ½ + ¼ = 2.75

53


� codifica:

N = I+F, I parte intera, F frazionaria

codR(I,F)

(n)=codN(I)

(�n�) codR(F)

(n-�n�)

codifica parte intera su I bitcodifica parte frazionaria su F bit

54

Codifica parte frazionaria

� codR(F)

(n) =

for i = -1..-F

n = n * 2;

bi = if n < 1 then 0 else 1

n = if n < 1 then n else n - 1

return b-1b-2 ... b

-F

55

Codifica in virgola fissa

Es.:

codR(3,4)

(5.75) = 1011100

decodR(3,4)

(1011100) = 22+20+2-1+2-2=

= 4+1+1/2+1/4 = 5.75

codR(1,3)

(0.1) = 0000

decodR(1,3)

(0000) = 0

56

Errore di approssimazione

= | � n � decodR(I,F)

(codR(I,F)

(n)) |

� codR(3,4)

(5.75) = 1011100

= | 5.75 � 5.75 | = 0 (esatta)�

� codR(1,3)

(0.1) = 0000

= | 0.1 � 0 | = 0.1 (per difetto)�

� codR(1,3)

(0.1) = 0001

= | 0.1 � 0.125 | = 0.025 (per eccesso)�

57

Approssimo per difetto o per eccesso?

Codifica di 0.1, 1 bit intero, 3 frazionari

0000 approssimo per difetto = � 0.1

0001 approssimo per eccesso =� 0.025

Approssimazione migliore:

quella con errore � minore

Basta guardare un bit �in avanti� nel procedimento di codifica

58

Approssimazione

b-1...b

-Fb

-F-1 (codifica parte frazionaria)

b-F-1

=0 b-1...b

-F (approssimo per difetto)

�max

� �i=-F-2..-F-N-1

2i = 2-F-1-2-F-N-1 N� �N+

quindi �max

< 2-F-1

bit �in avanti� serve solo per approssimarebit meno significativo

59

Approssimazione

b-F-1

=1 b-1...b

-F +0..01 (approssimo per

eccesso)

�max

decod�R(F)

(b-1...b

-F +0..01)-decod

R(F+1)(b

-

1...b

-F1) = 2-F-2-F-1=2-F-1

Attenzione: in b-1...b

-F +0..01 il riporto

potrebbe propagarsi alla parte intera

F bit

60

Approssimazione

� Una visione grafica

d = decodR(F)

(b-1...b

-F)

d d+2-F-1 d+2-F

2-F

2-F-1

n1 n

2n

3

approssimatoper difetto approssimato

per eccesso

approssimato per difetto o per eccesso

61

Codifiche infinite

� �2 ovvio ...� 1/3 = 0.333...333... ovvio anche questo� 0.2 meno ovvio:0.2 * 2 = 0.4

0.4 * 2 = 0.8

0.8 * 2 = 1.6

0.6 * 2 = 1.2

0.2 * 2 = 0.4

..... 62

Overflow e underflow

� I=3, F=4

val max rappresentabile con =0�

decodR(3,4)

(1111111) = 23-2-4

val min positivo rappresentabile con =0�

decodR(3,4)

(0000001) = 2-4

1111111 + 0000001 = overflow

0000001 * 0001000 = underflow

63

Codifiche in virgola mobile

� Es.: I=1, F=3

1.812 m

1812 m = 1.812 Km = 1.812 * 103 m

0.01812 m = 1.812 cm = 1.812 * 10-2 m

181.2 m = 1.812 hm = 1.812 * 102 m

0.001812 m = 1.812 mm = 1.812 * 10-3 m

64

Codifiche in virgola mobile

base 10: 1.812 * 10-3

base 2: 1.011 * 2-3

-3 1011

11101 1011

virgola fissa in base 10potenza di 10

potenza di 2virgola fissa in base 2

base fissata, riporto solo l'esponente

virgola fissa, I=1, F=3

esponente in complemento a 2 con N=5

65

Normalizzazione

Es. di formato:

111001 1100esponente in complemento a 2 con N=6

e = decodZ(111001) = -7

m = decodR(1,3)

(1100) = 1.5

decod(111001 1100)=2e *m=2-7*1.5

decod(111010 0110)=2-6*1.5/2=2-7*1.5

decod(111011 0011)=2-5*1.5/4=2-7*1.5

mantissa con I=1, F=3

66

Normalizzazione

Quindi:

cod(2-7*1.5)={111001 1100, 111010 0110, 111011 0011}

Meglio se cod è una funzione.

Basta imporre che m sia normalizzata

Tipicamente: 20 � m < 21

Più in generale:

2k � m < 2k+1 per un certo k fissato

67

Normalizzazione

Se 1 � m < 2

cod(2-7*1.5)=111001 1100

Ottimizzazione: visto che 1 � m < 2,

la codifica di m sarà sempre della forma

1b-1..b

-F

questo bit è superfluo e viene quindi omesso

68

Calcolo della codifica

Con normalizzazione 1 � m < 2

cod(n)=codZ(e) cod

R(F)(-1+n/2e)

dove e = log�2(n) infatti�

n=2e*m m=n/2e 1 � n/2e < 2

0 � log2(n)-e < 1 e = log�

2(n)�

� codZ dipende dalla codifica scelta per e

� F = lunghezza della mantissa

esclusione del primo bit

69

Calcolo della decodifica

Con normalizzazione 1 � m < 2

decod(bN-1

..b0b

-1..b

-F)=2e*m

dove e=decodZ(b

N-1..b

0)

m=decodR(F)

(b-1..b

-F)+1

70

Codifica dello zero

2e*m=0 non ha soluzioni per 1 � m < 2

Eccezione:

cod(0)=0..00..0

configurazione 0..0 inutilizzata per e

codice eccesso 2N-1 evita �buchi�

71

Numeri negativi

Codifica più utilizzata: modulo e segno

b bN-1

..b0 b

-1..b

-F

bit di segnocodifica di e

codifica di m

72

Codifica dei caratteri

� Cosa sono i caratteri:

insieme di simboli, interpretazione puramente sintattica (a parte i caratteri di controllo)

Es. caratteri stampabili: 'a' 'A' '7' '@' '#'

Es. caratteri di controllo: '\n' (new line)

'\t' (tab) � Codifica meno problematica rispetto ai

numeri: meno operazioni e più semplici

73

Codifica dei caratteri

� Esistono vari codici:

ASCII, unicode, EBCDIC,...� Esempio: ASCII

American Standard Code for Information Interchange

Lunghezza fissa: 7 bit

74

Codice ASCII

Codifica delle lettere: immersione in un intervallo di N, ordine preservato (sia per le

minuscole che per le maiuscole)

cod('a')<cod('b')<...<cod('z')

cod('A')<cod('B')<...<cod('Z')

cod('b')-cod('a')=0000001, ...

cod('B')-cod('A')=0000001, ...

cod('a')-cod('A')=cod('b')-cod('B')=...

75

Codice ASCII

Codifica delle cifre: immersione in un intervallo di N, ordine preservato

cod('0')<cod('1')<...<cod('9')

cod('1')-cod('0')=0000001

...

cod('9')-cod('8')=0000001

76

Cifre: caratteri o numeri?

Attenzione: '0'�0, '1' 1,...,'9' 9� �

'5' carattere (simbolo stampabile)

5 numero

Si usa codifica diversa:

cod('5')=0110101 (7 bit)

cod(5)=0000000000000101 (16 bit)

77

Stampa di un numero

1.Conversione da base 2 a base 10

2.Conversione da cifra-numero a cifra-carattere

3.Stampa del carattere

78

Base 2 base 10

Per semplicità solo caso n>0 (N=8)

conv2to10(n)=

i=0

while (n>00000000)

ci = n % 00001010 /* resto */

n = n / 00001010 /* quoziente */

i = i + 1

return ci-1...c

0

79

Cifra-numero cifra-carattere

Cifra-numero su 8 bit, cifra-carattere su 7

convChar(b7...b

0)=

return b6...b

0 + cod('0')

Assumendo codice ASCII:

convChar(b7...b

0)=

return b6...b

0 + 0110000

80

Rilevazione di errori

Consideriamo un codice a lunghezza fissa

Problema: leggo/ricevo configurazione c

voglio capire se si sono verificati errori.

numero errori = numero bit alterati

Es.: una cella contiene 0011

lettura n.1: ottengo 0011 (0 errori)

lettura n.2: ottengo 1010 (2 errori)

lettura n.3: ottengo 0001 (1 errore)

81

Distanza di Hamming

Numero di bit diversi a parità di posizione

H(b1...b

N,b'

1...b'

N)=�

i=1..N|b

i-b'

i|

bi=b'

i |b

i-b'

i|=0

bi

b'�i |b

i-b'

i|=1

quindi 0�H(b1...b

N,b'

1...b'

N) N�

Es.: H(01010,01010)=0, H(11100,01001)=3, H(10010,01101)=5

82

Rilevazione di al più k errori

Cella contiene c V� , viene letto c'

Numero errori commessi = H(c,c')

Codice a rilevazione di al più k errori:

se 1 H(c,c') k allora c' NV � � �

Condizione necessaria, ma non sufficiente:

il codice deve avere una certa ridondanza

83

Ridondanza

controllo di c': mi accorgo di errori solo se

c'�NV (assumendo che c V)�

NV = { c {0,1}� N | decod(c) indefinito}

V = { c {0,1}� N | decod(c) definito}

V NV = {0,1}� N e V NV = � �

Ridondanza di un codice

R =(|V|+|NV|)/|V|=2N/|V|

tutte le configurazioni numero configurazioni valide 84

Codici ridondanti

in ogni caso R � 1 � R = 1 tutte le configurazioni di

lunghezza N sono valide� R � 2 codice ridondante: le

configurazioni non valide di lunghezza N sono almeno tante quante quelle valide

Ricorda: |V|+|NV| = 2N

R�2 2! N/|V|�2 (|V|+! |NV|)/|V|�2 !

|NV| |V|�

85

Ridondanza necessariaTeorema: se riesco a rilevare al più un

errore, allora R�2

Sia V={c1,...,c

v}, H1(c

i)={c | H(c,c

i)=1}

H1(ci)�V=� quindi S=�

i=1..vH1(c

i)"NV

per ogni c in S, nc=card{c

i | H(c,c

i)=1}

Fatti: |H1(ci)|=N, n

cN�

|V|*N=#i=1..v

|H1(ci)|=#

c�Sn

c�#

c�SN=|S|*N

quindi V S NV" " 86

Ridondanza non sufficiente

Ridondanza non sufficiente per rilevazione errori

Es.: N=3, V={000,001,010,011}

R=23/|V|=8/4=2

codice ridondante,

ma se, per esempio, c=000 e c'=001

non mi accorgo dell'errore

non riesco a rilevare neanche un errore!

87

Condizione suff. e necessaria

Teorema: rilevo al più k errori !

�c,c' V c c' H(c,c')>k� �

( ) se per assurdo c,c' V c c' e H(c,c') k � � � allora non riesco a rilevare al più k errori

( ) sia c V, c c' e H(c,c') k, allora $ � � �necessariamente c' NV, quindi riesco a �rilevare l'errore

88

Condizione equivalente

�c,c' V c c' H(c,c')>k � � !

�c V 0<H(c,c') k c' NV� � �

k

c

c'

tutte configurazioni non valide

89

Disuguaglianza triangolare

H(c1,c3)�H(c1,c2)+H(c2,c3)

Infatti, per ogni posizione i tale che c1i

c3�i

c2i=c1i c2!

ic3�

i

quindi |c1i-c3i|=1=|c2i-c1i|+|c2

i-c3

i|

e per ogni i tale che c1i=c3

i

|c1i-c3i|=0 |c2� i-c1i|+|c2

i-c3

i| 90

Disuguaglianza triangolare

Vale anche

H(c1,c2)+H(c2,c3)� 2N-H(c1,c3)

Infatti, per ogni posizione i tale che c1i=c3

i

c2i=c1i c2!

i=c3

i

quindi |c2i-c1i|+|c2i-c3

i|=0 oppure 2

H(c1,c2)+H(c2,c3)�

H(c1,c3)+2(N-H(c1,c3))=2N-H(c1,c3)

91

Codici di Hamming

Problema: codice con R=1, voglio poter rilevare al più 1 errore

Basta aggiungere 1 bit:

2N/|V|=1 2N+1/|V|=2

Ma la ridondanza non è sufficiente...

Bisogna trovare una tecnica per cui

1. H(c1,c2)>1 per ogni c1,c2�V, c1 c2�

2. c N� V verificabile semplicemente 92

Codici di Hamming

Tecnica del bit di parità

Es.: c=100110 1

Controllo: se il numero totale di bit a 1 è pari, allora c�V, altrimenti c�NV

Facilmente realizzabile tramite logica circuitale, usando porte XOR (vedi parte su circuiti combinatori)

bit di parità determinato dai bit di datobit di dato

93

Codici di Hamming

1 bit di parità rilevabile 1 errore

Infatti

H(000000 0,000001 1)=2

�c1,c2 V c1 c2 � � H(c1,c2)>1

c1 V c1 contiene numero pari di bit a 1�

H(c1,c2)=1 c2 contiene numero dispari di bit a 1 c2 NV�

94

Codici di Hamming

Rilevazione di al più 2 errori

�c1,c2 V c1 c2 � � H(c1,c2)>2

1 bit di parità non basta

Attenzione: numero bit di parità necessari cresce con la lunghezza N del codice a differenza dei codici di Hamming a 1 bit

95

Rilevazione errori e ridondanza

Sia C codice non ridondante (1�R<2) di lunghezza N, se aggiungo 1 bit di parità ottengo C' con R'=2N+1/|V'|=2R<4

Nota bene: R=2N/|V| e |V|=|V'|

Quindi la ridondanza di C' è limitata indipendentemente dal valore di N

Ciò non vale per C' che rileva al più 2 errori

96

Rilevazione errori e ridondanza

Sia C tale che rileva al più 2 errori, sia

V={c1,...,c

v}, S=�

i=1..vH1(c

i) NV"

i�j implica H1(ci)�H1(c

j)= infatti se �

c H1(� ci), H(c

i,c

j)�H(c,c

i)+H(c,c

j)

H(c,cj)�H(c

i,c

j)-1 2 c H1(� % c

j), quindi

|NV| N*|V| R (N*|V|+|V|)/|V|=N+1� �

97

Codici di Hamming a più bit

Abbiamo visto che 1 bit di parità non basta per rilevare 2 errori

Assumiamo quindi di avere P bit di parità

di posizione p1,...,p

P e D bit di dato di

posizione d1,..,d

D

98


Sia D(p) l'insieme delle posizioni di tutti i bit di dato che determinano il bit di parità di posizione p

Sia P(d) l'insieme delle posizioni di tutti i bit di parità che dipendono dal bit di dato di posizione d

D(p)={d | p�P(d)} P(d)={p | d�D(p)} ossia D e P sono relazioni inverse l'una dell'altra

99


c�V ! in c le posizioni in {p

1}�D(p

1) hanno n. pari di bit a 1

&&in c le posizioni in {p

2}�D(p

2) hanno n. pari di bit a 1

&&...&&

in c le posizioni in {pP}�D(p

P) hanno n. pari di bit a 1

100


Dato P, troviamo un modo per determinare� il numero massimo D di bit dato che

possono essere gestiti da P bit di parità � gli insiemi D(p) per ogni posizione di bit

di parità

101


Osservazione: se c�V e H(c,c')=2 allora deve essere c' N� V

3 casi a seconda dei 2 bit alterati

1) 2 bit di parità

2) 1 bit parità, 1 bit di dato

3) 2 bit di dato

102


caso 1)

c' ottenuto da c�V alterando 2 bit di parità

di posizione pi e p

j (i�j)

Se {pi}�D(p

i) e {p

j}�D(p

j) verificano il

controllo di parità in c allora non lo

verificano in c' (in entrambi gli insiemi si modifica solo il bit di parità)

Quindi c'�NV come richiesto

103

Codici di Hamming a più bitcaso 2)

c' ottenuto da c�V alterando 1 bit di parità di posizione p e 1 bit di dato di posizione d

Se p�P(d) allora se {p}�D(p) verificano il controllo di parità in c lo verificano anche in c' (2 bit modificati)

Ma se esiste p'�p t.c. p'�P(d), allora se {p'}�D(p') verificano il controllo di parità in c non lo verificano in c' (1 bit modificato)

Quindi deve essere |P(d)|>1 affinché c' NV� 104

Codici di Hamming a più bitcaso 3)

c' ottenuto da c�V alterando 2 bit di dato di posizioni d

i e d

j (i�j)

se P(di)=P(d

j) allora per ogni p�P(d

i) se

{p}�D(p) verificano il controllo di parità in c lo verificano anche in c' (2 bit modificati)

Ma se P(di)�P(d

j) allora esiste almeno p t.c. se

{p}�D(p) verificano il controllo di parità in c non lo verificano in c' (1 bit modificato) Quindi deve essere P(d

i)�P(d

j) affinché c' NV�

105

Codici di Hamming a più bitMax numero di bit di dato D gestibile con P

bit di parità� |P(d)|>1 per ogni posizione d di bit dato

� i j � P(di)�P(d

j) per ogni posizione d

i, d

j di

bit di dato

D = max numero insiemi su P elementi di cardinalità maggiore di 1

D = 2P-P-1

tutti i possibili insiemi tutti gli insiemi con 1 elemento

l'insieme vuoto

106

Codici di Hamming a più bitCome determinare P(d)?

Ogni S�Parti({p1,...,p

P}) rappresentabile

con configurazione bP...b

1 di bit

S

&(isomorfismo)

funzione caratteristica o indicatrice '

S:Parti({p

1,...,p

P}) � {0,1}

&(isomorfismo)

configurazione di P bit

107


Quindi P(d)� bP...b

1 con almeno 2 bit a 1

(cardinalità deve essere maggiore di 1)

Idea: P(d) cod(d) (codifica dei naturali �con P bit)

Quindi basta scegliere per i bit di dato posizioni diverse da 0 e potenze di 2

Le potenze di 2 sono per le posizioni dei bit di parità, la posizione 0 non si usa (si parte da 1) 108

Codici di Hamming a più bitConvenzioni sul formato:

P bit parità lunghezza max=P+D=2P-1

Calcolo posizioni bit di parità p1,...,p

P:

p1=20, p

2=21,...,p

P=2(P-1)

Calcolo posizioni bit di parità d1,...,d

D:

d1=3, d

2=5,...,d

P=2P-1

Nota bene: le posizioni partono da 1

109


Grazie a questa convenzione

{pi}�D(p

i)={n | n=decod(b

P+D...b

i+11b

i-1...b

1)}

dove decod è la solita decodifica binaria dei naturali su P+D bit

P(k)=cod(k) su P+D bit

Nota bene: funziona anche quando k corrisponde a un bit di parità

P(p)={p} 110


Esempio con P=3 (3 bit parità)

DMAX

=23-3-1= 4 (4 bit di dato)

Codice a 7 bit col seguente formato:

d4d

3d

2p

3d

1p

2p

1 (posizioni bit parità: 1,2 e 4)

7 6 5 4 3 2 1

P(3)={2,1},P(5)={4,1},P(6)={4,2},P(7)={4,2,1}

D(1)={7,5,3},D(2)={7,6,3},D(4)={7,6,5}

111

Codici di Hamming a più bitConversione da codice non ridondante (R<2) di

lunghezza D a codice di Hamming per la rilevazione di al più 2 errori.

Il numero minimo P di bit di parità deve essere t.c. 2P-1-P<D 2� P-P-1

Per ogni bD...b

1 valida

bD...b

1 � b

D...b

2b'

3b

1b'

2b'

1 con {b'

1,...,b'

P} tali

che

le posizioni in {2i-1}�D(2i-1) abbiano numero pari di bit a 1 per ogni i=1..P

112


Per rilevare al più 3 errori ci vogliono più bit e codici ancora più complessi

Esempio con P=3, D=4

1001100�V

0101101�V

H(1001100,0101101)=3 codice non può rilevare 3 errori

113

Correzione di al più k errori (k>0)

Def.: per ogni c,c' se c�V e 1 H(c,c') k � �allora non esiste c''�V tale che c''�c e H(c'',c') k �

Quindi:� c' NV: � 1 H(c,c') � c�c'. Se per assurdo

c'�V allora c'�c e H(c',c')=0<k (imposs.)� l'unica correzione possibile è c' c�

114

Condizione suff. e necessariaTeorema: correggo al più k errori (k>0)!

�c,c'' V c c'' H(c,c'')>2k� �

( ) Per Teo. su rilevazione

�c,c'' V c c'' H(c,c'')>k� �

Per assurdo siano c,c'' V tali che �k<H(c,c'') 2k. �

È sempre possibile passare da c a c'' modificando prima k bit, ottenendo c', e poi i rimanenti H(c,c'')-k bit diversi

115

Condizione suff. e necessariaQuindi H(c,c')=k e H(c',c'')=H(c,c'')-k 2k-�

k=k, per cui

1 H(c,c') k, ma c c'', c'' V e H(c',c'') k� � � � �

contro l'ipotesi

( ) Supponiamo esistano$ c,c''�V e c' t.c. 1 H(c,c') k, � � c'' c e H(c'',c') k� �

Per disuguaglianza triangolare

H(c,c'') H(c,c')+H(c'',c') 2k, contro � �l'ipotesi 116

Codici a correzione di 1 erroreConsidero codice a rilevazione di al più 2 errori

Poiché �c,c'�V c�c' H(c,c')>2=2*1

Allora è anche codice a correzione di 1 errore

Bit da correggere:

S = {posizioni dei bit di parità �sbagliati�}

devo modificare posizione k t.c.

k�{p}�D(p) per ogni p�S

k%{p}�D(p) per ogni p%S

Quindi k=�p�S

p

117

Codici a correzione di al più 1 errore

Esempio con P=3, D=4

Si vuole correggere 1001000

In {1}�D(1)={1,3,5,7} n. bit a 1 è dispari NO

In {2}�D(2)={2,3,6,7} n. bit a 1 è dispari NO

In {4}�D(4)={4,5,6,7} n. bit a 1 è pari OK

Quindi S={1,2} e il bit da correggere è in posizione k=1+2=3

118

Codici a lunghezza variabile

Confronto con lunghezza fissa:� codici a lunghezza fissa più semplici,

scelta naturale che riflette l'organizzazione fisica della memoria (celle di lunghezza fissa)

� codici a lunghezza variabile permettono di �risparmiare� bit a fronte di una maggiore complessità

119

Codici a lunghezza variabile

Due esempi di applicazione:� codifica delle istruzioni macchina� compressione dei dati

120

Codifica delle istruzioniUn semplice esempio:� codifica istruzioni: a lunghezza fissa (16

bit)� 4 formati di istruzioni: a 0, 1, 2 o 3

operandi� codifica di un operando: a lunghezza

fissa (4 bit)

121

Codifica delle istruzioni

La codifica di un'istruzione è formata da due parti.

operandicodice operativo

16 bit

codifica del tipo di istruzione

122

Codifica delle istruzioniUna soluzione semplice: codice operativo a

lunghezza fissa

Alcuni tipi di istruzione usano 3 operandi, ogni operando è codificato con 4 bit

codifica operandi almeno 4*3=12 bit

codice operativo al più 16-12=4 bit

operandicodice operativo

16 bit

4 bit 12 bit

123


codice operativo lunghezza fissa 4 bit

posso codificare al più 24=16 tipi diversi di istruzione

Problema: �spreco� dei bit

4 bit per ogni istruzione a 2 operandi

8 bit per ogni istruzione a 1 operando

12 bit per ogni istruzione a 0 operandi

124


Una soluzione che non �spreca� bit: codice operativo a lunghezza variabile

La lunghezza dipende dal numero di operandi richiesto dal tipo di istruzione

Numero operandi 0 1 2 3Lunghezza codice operativo 16 12 8 4

Domanda: quanti tipi di istruzioni a 3 operandiriesco a codificare? Devono essere meno di 24

125


Problema dell'ambiguità

0000110011110101

Istruzione a 3 operandi con codice operativo 0000?

Istruzione a 2 operandi con codice operativo 00001100? etc.

Devo trovare un modo per evitare questa ambiguità

126

Codifica delle istruzioniUna possibile soluzione all'ambiguità

codice op. a 4 bit:

b3b

2b

1b

0 con b

3b

2b

1b

0 �1111

codice op. a 8 bit:

1111b3b

2b

1b

0 con b

3b

2b

1b

0 �1111

codice op. a 12 bit:

11111111b3b

2b

1b

0 con b

3b

2b

1b

0 �1111

codice op. a 16 bit:

111111111111b3b

2b

1b

0 (b

3b

2b

1b

0 qualsiasi)

127


Totale tipi di istruzioni codificabili:

24-1 con 3 operandi

24-1 con 2 operandi

24-1 con 1 operando

24 con 0 operandi

26-3=61 in totale rispetto alle 16 rappresentabili con codici operativo di lunghezza fissa 4

128

Compressione dei dati

Un semplice esempio:

considero file che contiene solo i simboli

A,E,I,O,U

Uso codice a lunghezza fissa non ridondante per codificare A,E,I,O,U

N=3 (22<5<=23)

Quindi se file �contiene� L caratteri la sua dimensione è 3L bit

129


Se la frequenza di ogni simbolo è diversa

posso comprimere il file se passo a lunghezza variabile

Esempio frequenze:

f(A)=0.35,f(E)=0.25,f(O)=0.21,f(I)=0.15,

f(U)=0.04

Assegno configurazioni di lunghezza minore a simboli di frequenza maggiore

130


Una possibile soluzione (anche se non ottimale...)

A 0, E 10, O 110, U 1110, U 1111� � � � �

Non c'è ambiguità ogni codifica non è prefisso di altre codifiche

131

Compressione dei datiLunghezza del file compresso:

(�s S�

l(s) * f(s))*L dove

L=numero simboli codificati nel file

S=insieme dei simboli

l(s) lunghezza del codice che codifica s

f(s) frequenza di s nel file

Nel nostro caso:

(1*0.35+2*0.25+3*0.21+4*0.15+4*0.04)*L=

2.24*L<3*L 132

Rapporto di compressione

In realtà L non serve perché il dato interessante è il rapporto di compressione

(3*L/2.24*L) 1� .34

Oppure la percentuale di spazio risparmiato:

(3*L-2.24*L)/(3*L)=0.76/3�0.253, quindi abbiamo salvato circa il 25.3% dello spazio

133

Soluzione generale

Quale semplice proprietà assicura assenza di ambiguità nel caso di codifiche a lunghezza variabile?

Ogni prefisso (proprio) di una codifica valida è non valido

Esempio: i prefissi di 1001 sono la successione vuota �, 1, 10 e 100.

Se decod(1001) è definito allora decod(�), decod(1), decod(10) e decod(100) sono indefiniti

134

Definizioni formali

Def.: c è prefisso (proprio) di c, prefix(c,c'), se e solo se |c|<|c'| e per ogni i < |c| c(i)=c'(i+|c'|-|c|)

Def.: codice a lunghezza variabile non ambiguo rispetto ai prefissi: per ogni c, c' se prefix(c,c') e decod(c') è definito, allora decod(c) è indefinito

135

Codici e alberi binari

Idea: un codice non ambiguo rispetto ai prefissi si può rappresentare con un

albero binario posizionale (al posto di posizionale spesso si usa impropriamente

anche il termine ordinato)

136

Definizione intuitiva di alberoN.B.: per definizioni più formali vedere il

corso di ASD

Un albero è formato da un insieme non vuoto di nodi e un insieme di archi.

Ogni arco connette due nodi e ha una direzione.

Non possono esistere due archi diversi che vanno da un nodo a un altro, ossia l'insieme degli archi è una relazione binaria tra i nodi dell'albero.

137

Rappresentazione e terminologia

Esempio: l'arco e va n1 a n2.

n1 n2e

e è arco uscente da n1 ed entrante in n2n2 è figlio (child) di n1, n1 parent di n2Un cammino è una successione non vuota di nodi n

1...n

k tale che esiste l'arco da n

i a n

i+1

per ogni i=1..k-1

n1

n2

n1

nk-1

nk

138

Definizione di albero

� I nodi sono in numero finito� Esiste un unico nodo detto radice che

non ha alcun arco entrante� A parte la radice, tutti gli altri nodi hanno

un solo arco entrante� Non esistono cammini ciclici, ossia del

tipo n1, n2,...,n1

Altezza albero: numero archi di un cammino massimo (radice - foglia)

139

Alberi binari posizionali

Tutti i nodi hanno al più 2 archi uscenti e ogni arco può essere destro o sinistro;

quindi ogni nodo può avere:� 0 archi uscenti (viene detto foglia)

� 1 arco destro uscente� 1 arco sinistro uscente

� 2 archi uscenti, uno destro e l'altro sinistro

140

Esempio di albero binario posizionale

radice

foglia foglia

foglia

arcodestro

arcosinistro

figlio sinistro figlio destro

141

Archi etichettati

Seguiamo la seguente convenzione: archi sinistri etichettati con 0, archi destri etichettati con 1

A ogni foglia n possiamo associare la configurazione di bit corrispondenti alle etichette degli archi che compongono il cammino dalla radice alla foglia n

142

Archi etichettati

Esempio:

n1 010 �

n2 011�

n3 10�

foglia n1 foglia n2

foglia n3

radice

0

0

0

1

1

1

143

Codice e alberi

Ogni codice (finito, a lunghezza fissa o variabile) non ambiguo rispetto ai prefissi può essere rappresentato da un albero binario posizionale, dove le foglie corrispondono agli elementi codificati.

Viceversa, ogni albero binario posizionale rappresenta un codice non ambiguo rispetto ai prefissi dove gli elementi codificati corrispondono alle foglie.

144

Codici e alberiEsempio: il codice tale che cod(A)={01},

cod(E)={100}, cod(I)={101}, cod(O)={110}, cod(U)={111} corrisponde al seguente albero

E

0

0

0

1

1

1

A

I

0 1

O U

1

145

Codici a espansione

Utili schemi per rappresentare istruzioni con codici operativi a lunghezza variabile.

� formati multipli predefiniti� con cifra di espansione� con configurazione di espansione

Sono schemi che garantiscono codici non ambigui rispetto ai prefissi, quindi tutti rappresentabili con alberi binari posizionali

146

Formati multipli predefiniti

Esempio:

� formato 1 a 4 bit: 00b1b

0 (22 config.)


2b

1b

0 (24 config.)

� formato 3 a 9 bit: 10b6...b

0 (27 config.)

�

formato 4 a 13 bit: 11b

10...b

0 (211 config.)

147

Formati multipli predefiniti

Rappresentazione ad albero

0

0

1

110

24

711

formato 1formato 2

formato 3

formato 4

n = albero completo di altezza n (2n foglie)

148

Cifra di espansione

Esempio:


1b

0 (23 config.)


2b

1b

0 (24 config.)

� formato 3 a 9 bit: 110b5...b

0 (26 config.)

�

formato 4 a 13 bit: 111b

9...b

0 (210 config.)

149

Rappresentazione ad albero

Cifra di espansione

0

0

1

13

4

610

formato 1

formato 2

formato 3formato 4

0 1

150

Configurazione di espansione

Esempio: formato 1 a 4 bit: b

3b

2b

1b

0

(escluso 1..1, 24-1 config.)� formato 2 a 6 bit: 1111b

1b

0

(escluso 1..1, 22-1 config.)� formato 3 a 9 bit: 111111b

2b

1b

0

(escluso 1..1, 23-1 config.)�

formato 4 a 13 bit: 1..1b

3b

2b

1b

0 (24 config.)

151

Configurazione di espansione

Rappresentazione ad albero10

3

formato 1

0

2

1

0

1

1

0 1

0

1

1

0

formato 2

1

0

2

1

0

1

1

0

formato 3

152

Codifica di HuffmanPermette la generazione di un codice

ottimale (che minimizza il numero di bit necessari per la codifica) basata sull'analisi della frequenza dei simboli

Idea: l'albero binario posizionale che rappresenta il codice viene generato a partire dalle foglie (approccio bottom-up)

153

Generazione codice ottimaleAlgoritmo di costruzione dell'albero:

I nodi vengono inseriti in una coda di priorità; nodi con frequenza più bassa hanno priorità più alta.

Si estraggono due nodi dalla coda (ossia, quelli con le frequenze minori f1 e f2), si crea un nuovo nodo genitore n con frequenza f1+f2, si inserisce n nella coda.

L'algoritmo termina quando nella coda rimane un solo nodo (la radice) 154

Generazione codice ottimale

Esempio f(A)=0.35,f(E)=0.25,f(O)=0.21,f(I)=0.15,

f(U)=0.04

Fase iniziale: coda di foglie

A 0.35 E 0.25 O 0.21 I 0.15 U 0.04

155


A 0.35 E 0.25 O 0.21

I 0.15 U 0.04

0.19

Creazione di un nodo non foglia

156


I restanti passi:

A 0.35 E 0.25

O 0.21

I 0.15 U 0.04

0.19

0.4

157


A 0.35 E 0.25 O 0.21

I 0.15 U 0.04

0.19

0.40.6

158


A 0.35 E 0.25 O 0.21

I 0.15 U 0.04

0.19

0.40.6

1

Albero finale:

159


A E O

I U

0

0

0 1

0 1 1

1

A � 00, E � 01, O � 10, I � 110, U � 111Spazio risparmiato rispetto a lunghezza fissa 3(3- (0.81*2+0.19*3))/3=0.27

Codice generato:NOTA BENE: è un albero full,ossia ogni nodo può avere 0 o2 figli (ma non 1).

Architettura dei calcolatori Argomenti del corso · Codifica dei numeri naturali moltiplicazione...

Documents

Transcript of Architettura dei calcolatori Argomenti del corso · Codifica dei numeri naturali moltiplicazione...