Esistono 10 tipi di persone al mondo:
Quelli che conoscono il codice binario
&
Quelli che non lo conoscono
Rappresentazione binaria
dei numeri interi senza segno
00110111
37
Conversione Decimale-Binario:
Conversione Binario-Esadecimale:
55 mod 2 =1 = a0
(55 div 2) mod 2 = 27 mod 2 = 1 = a1
((55 div 2) div 2) mod 2= (27 div 2) mod 2=13 mod 2=1= a2
(13 div 2) mod 2= 6 mod 2 = 0 =a3
(6 div 2) mod 2 = 3 mod 2 = 1 =a4
(3 div 2) mod 2 = 1 mod 2 = 1 = a5
Dunque:
5510=1101112
1)
2)
Raggruppo i bit a blocchi di 4:
11 0111
Converto ciascun blocco in base 16
112=316 01112=716
Dunque: 1101112 = 3716
00110111
37
52
82
Conversione Binario-Decimale:
01010010
=0*20+1*21+0*22+0*23+1*24+0*25+1*26+0*27=
=2+16+64=8210
Conversione Binario-Esadecimale:
1)
2)
Raggruppo i bit a blocchi di 4:
0101 0010
Converto ciascun blocco in base 16
01012=516 00102=216
=>5216
00110111
37
52
82
167
62
Conversione Esadecimale-Decimale:
A7
3E
=10*161+7*160=10*16+7=167
= 3*161+E*161=48+14=62
10100111
Conversione Esadecimale-Binario:
1)
2)
Traduco ciascuna cifra esadecimale in un
blocco di 4 bits :
A16 = 1010= 23+21=10102
716 = 710= 22+21+20=01112
Il binario corrispondente si ottiene
sostituendo ciascuna cifra esadecimale
con il relativo blocco di 4 bit:
A716=101001112
Conversioni numeri razionali
Conversione Decimale-Binario frazionaria:
Conversione Binario-Decimale frazionaria:
Parte Intera {(0,1 * 2)} =0 = a-1
Parte Intera {Parte Frazionaria{(0,1 * 2)}} = 0 = a-2
….
….
0,1 * 2 = 0,2 -> 0 = a-1
0,2 * 2 = 0,4 -> 0 = a-2
0,4 * 2 = 0,8 -> 0 = a-3
0,8 * 2 = 1,6 -> 1 = a-4
0,6 * 2 = 1,2 -> 1 = a-5
0,2 * 2 = 0,4 -> 0 = a-6
….
….
Dunque:
0,110=0,000112 (Periodico)
0,1010010=0*20+1*2-1+0*2-2 + 1*2-3 + 0*2-4 + 0*2-5 +
1*2-6 + 0*2-7 = 0,6562510
Somma tra Numeri Binari
Interi Positivi
Regole base:
• 0+0=0
• 0+1=1+0=1
• 1+1=0 con riporto di 1
• 1+1+(1)=1 con rip.1,
dove (1) e’ il riporto
proveniente dallo step
precedente
Un trabocco indica
un overflow
Esempio:
00001110
riporti
00101110+
01000111=
-------------------
01110101
10001110
riporti
10101110+
11000111=
------------------11110101
Sottrazione tra Numeri Binari
Interi Positivi
Regole base:
• 0-0=0
• 0-1=1 con prestito di 1
• 1-0=1
• 1-1=0
Esempio:
01000111
prestiti
1010111001000111=
-------------------
01100111
Un trabocco indica
un underflow.
11011111
prestiti
1010011011000111=
------------------11011111
Moltiplicazione tra Numeri Binari
Interi Positivi
• La moltiplicazione puo’ essere realizzata
banalmente sommando al moltiplicando se
stesso, un numero di volte pari al valore del
moltiplicatore. 5*3=5+5+5=15.
• Assumendo che la somma abbia costo
costante operando su addendi
rappresentabili con un numero di bits noto a
priori, tale algoritmo ha complessità
computazionale pari a O(N), dove N è il
valore del moltiplicatore.
• Se moltiplicando e moltiplicatore sono
rappresentati con k bits, il prodotto può
richiedere fino a un max di 2k bits per la
sua rappresentazione.
00110 x
00101 =
00110
00000
00110
somme
00000
parziali
00000
000011110
Moltiplicazione tra Numeri Binari
Interi Positivi: Potenze di 2
• Nel caso di moltiplicazione
per potenza k-esima di 2 il
risultato è uno shift a
sinistra di k posizioni:
00110 x
10 =
00000
00110
001100
00110 x
100 =
00000
00000
00110
0011000
Divisione tra Numeri Binari
Interi Positivi
10011011
1001
00001011
1001
0010
resto
1001
10001
quoziente
Verifichiamo la correttezza del calcolo:
1001*
10001=
1001
0000
0000
0000
1001
10011001+
0010=
10011011
(resto)
Divisione tra Numeri Binari
Interi Positivi: Potenze di 2
• Nel caso di divisione per potenza k-esima di 2
il risultato è uno shift a destra di k posizioni:
10011011
1000
0001101
1000
1011
1000
11
1000
10011
Rappresentazione binaria
dei numeri interi con segno
101011012 = 1+4+32+128 =16510 (senza segno)
101011012=-1*(1+4+8+32)=-4510 (segno e modulo)
101011012=-1*27+1+4+32=-9110 (complemento a 2)
per verificare:
a) invertiamo 1 con 0 e viceversa: 0101000102,
b) sommiamo 1: 0101000112=91
Proprietà della rappresentazione in complemento a 2:
1) L’operazione di cambiamento di segno è eseguibile complementando alla base
2) La sottrazione si può ricondurre ad una somma (vedi prox slide)
3) E’ possibile rappresentare lo stesso numero con un numero maggiore di bit
semplicemente copiando il bit + significativo:
es: -710=10012 (con 4 bit)=111110012 (con 8 bit)= 11111111111110012
Somma tra Numeri Binari
in Complemento a 2
• Siano a e b due numeri e sia R(a) e R(b) la rappresentazione di a e
b in complemento alla base (ad es. base 2)
• Sommando R(a) ed R(b), e ignorando l’eventuale riporto dalla
posizione più significativa, otteniamo R(a+b).
• A meno che non vi sia discordanza tra il segno del risultato e quello
comune dei due addendi (ovvero a>0,b>0,a+b<0 oppure
a<0,b<0,a+b>0): in tal caso si ha un supero di capacità.
00102+11012=11112
[2 + (-3) = -1]
riporto
0000
In generale per calcolare a – b basta:
0010+
1) Trovare il complemento a 2 di b, cioè -b
1101=
2) Sommare a+(-b)
1111
01102+01112=OVERFLOW [6 + 7 = 13>7!] riporto
0110
0110
0111
1101
Somma tra Numeri Binari
in Complemento a 2
• Siano a e b due numeri e sia R(a) e R(b) la rappresentazione di a e
b in complemento alla base (ad es. base 2)
• Sommando R(a) ed R(b), e ignorando l’eventuale riporto dalla
posizione più significativa, otteniamo R(a+b).
• A meno che non vi sia discordanza tra il segno del risultato e quello
comune dei due addendi (ovvero a>0,b>0,a+b<0 oppure
a<0,b<0,a+b>0): in tal caso si ha un supero di capacità.
11112+10002=OVERFLOW
[-1 + (-8) = -9<-8] riporto 1000
1111+
1000=
0111
01102+11112=0101
[6 + (-1) = 5]
riporto
1110
0110
L’overflow è possibile solo se gli
addendi hanno segno comune!
1111
0101
CORREZIONE ERRORI
CODICI DI HAMMING
• Per “rivelare” errori di trasmissione il sistema che invia dati introduce
ridondanza nelle informazioni trasmesse.
• Codice (n, k) con n> k => codice con parole di lunghezza n di cui k bit di
informazione
• Un codice a distanza minima d e’ capace di rivelare errori di peso <= d-1
• Dato un codice a distanza minima d esso ha una capacita’ di correzione di
errori di peso <= INTINF((d-1)/2)
Bits di informazione ricevuti
Sistema
trasmissione
Generatore di chek bits
(Encoder)
p4 = I5 + I6 + I7
p2 = I3 + I6 + I7
p1 = I3 + I5 + I7
Bits di parità
Controllo dei chek bits
(Decoder)
S4 = p4 + I5 + I6 + I7
S2 =p2 + I3 + I6 + I7
S1 = p1+ I3 + I5 + I7
CORREZIONE ERRORI
CODICI DI HAMMING
INFORMAZIONE DA INVIARE: 0110
Gruppi
I7
I6
I5
p4
I3
p2
p1
7
6
5
4
3
2
1
X
X
X
X
X
X
X
X
X
X
posizione
I7 + I6 + I5 + p4 = 0
I7 + I6 + I3 + p2 = 0
X
I7 + I5 + I3 + p1 = 0
X
Bit di parità
STRINGA DI INVIO: 0110011
CORREZIONE ERRORI
CODICI DI HAMMING
STRINGA RICEVUTA: 0110011
S4 = p4 + I5 + I6 + I7
S2 =p2 + I3 + I6 + I7
S1 = p1+ I3 + I5 + I7
S4 = 0
S2 = 0
S1 = 0
INFORMAZIONE RICEVUTA: 0110 ok!!!!!
STRINGA RCEVUTA: 0111011
S4 = p4 + I5 + I6 + I7
S2 =p2 + I3 + I6 + I7
S1 = p1+ I3 + I5 + I7
S4 = 1
S2 = 0
S1 = 0
INFORMAZIONE RICEVUTA: ERRORE NEL 4 BIT, QUINDI CORREGGO
E AVRO’ 0110011 ED ESTRAENDO L’INFORMAZIONE: 0110 ok!!!!!