Esistono 10 tipi di persone al mondo: Quelli che conoscono il codice binario & Quelli che non lo conoscono

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

Conversione Decimale-Binario:

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:

55₁₀=110111₂

Conversione Binario-Esadecimale:

1) Raggruppo i bit a blocchi di 4:

11 0111

2) Converto ciascun blocco in base 16 11₂=3₁₆ 0111₂=7₁₆

Dunque: 110111₂ = 37₁₆

00110111 37

Conversione Binario-Decimale:

01010010 =0*2⁰+1*2¹+0*2²+0*2³+1*2⁴+0*2⁵+1*2⁶+0*2⁷=

=2+16+64=82₁₀

Conversione Binario-Esadecimale:

1) Raggruppo i bit a blocchi di 4:

0101 0010

2) Converto ciascun blocco in base 16 0101₂=5₁₆ 0010₂=2₁₆

=>52₁₆

82 52

00110111 37

Conversione Esadecimale-Decimale:

A7 =10*16¹+7*16⁰=10*16+7=167 3E = 3*16¹+E*16¹=48+14=62

Conversione Esadecimale-Binario:

1) Traduco ciascuna cifra esadecimale in un blocco di 4 bits :

A₁₆ = 10₁₀= 2³+2¹=1010₂ 7₁₆ = 7₁₀= 2²+2¹+2⁰=0111₂ 2) Il binario corrispondente si ottiene

sostituendo ciascuna cifra esadecimale con il relativo blocco di 4 bit:

A7₁₆=10100111₂

167

52

00110111 37

82

62

10100111

Conversione Decimale-Binario 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,1₁₀=0,00011₂ (Periodico)

Conversioni numeri razionali

Conversione Binario-Decimale frazionaria:

0,1010010=0*2⁰+1*2^-1+0*2^-2 + 1*2^-3 + 0*2^-4 + 0*2^-5 + 1*2^-6 + 0*2^-7 = 0,65625₁₀

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

Esempio:

0 0 0 0 1 1 1 0 riporti 0 0 1 0 1 1 1 0 +

0 1 0 0 0 1 1 1 = --- 0 1 1 1 0 1 0 1

1 0 0 0 1 1 1 0 riporti 1 0 1 0 1 1 1 0 +

1 1 0 0 0 1 1 1 = --- 1 1 1 1 0 1 0 1 Un trabocco indica

un overflow

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:

0 1 0 0 0 1 1 1 prestiti 1 0 1 0 1 1 1 0 -

0 1 0 0 0 1 1 1 = --- 0 1 1 0 0 1 1 1

1 1 0 1 1 1 1 1 prestiti 1 0 1 0 0 1 1 0 -

1 1 0 0 0 1 1 1 = --- 1 1 0 1 1 1 1 1 Un trabocco indica

un underflow.

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 00000 00000

000011110

somme

parziali

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 1001 10001

00001011 1001 0010

Verifichiamo la correttezza del calcolo:

1001*

10001=

1001 0000 0000 0000 1001

10011001+

0010=

10011011

resto

quoziente

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 1000 10011

0001101

1000

1011

1000

11

Rappresentazione binaria

dei numeri interi con segno

10101101₂ = 1+4+32+128 =165₁₀ (senza segno) 10101101₂=-1*(1+4+8+32)=-45₁₀ (segno e modulo) 10101101₂=-1*2⁷+1+4+32=-91₁₀ (complemento a 2)

per verificare: a) invertiamo 1 con 0 e viceversa: 010100010₂, b) sommiamo 1: 010100011₂=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: -7₁₀=1001₂ (con 4 bit)=11111001₂ (con 8 bit)= 1111111111111001₂

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à.

0010₂+1101₂=1111₂ [2 + (-3) = -1] riporto 0000 0010+

1101=

1111 0110₂+0111₂=OVERFLOW[6 + 7 = 13>7!] riporto 0110

0110 0111 1101

In generale per calcolare a – b basta:

1) Trovare il complemento a 2 di b, cioè -b 2) Sommare a+(-b)

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à.

1111₂+1000₂=OVERFLOW [-1 + (-8) = -9<-8] riporto 1000 1111+

1000=

0111 0110₂+1111₂=0101 [6 + (-1) = 5] riporto 1110

0110 1111 0101 L’overflow è possibile solo se gli

addendi hanno segno comune!

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 parità

Sistema trasmissione

Bits di informazione ricevuti

p4 = I5 + I6 + I7 p2 = I3 + I6 + I7

p1 = I3 + I5 + I7 S4 = p4 + I5 + I6 + I7

S2 =p2 + I3 + I6 + I7 S1 = p1+ I3 + I5 + I7 Generatore di chek bits

(Encoder) Controllo dei chek bits

(Decoder)

CORREZIONE ERRORI CODICI DI HAMMING

INFORMAZIONE DA INVIARE: 0110

STRINGA DI INVIO: 0110011

7 6 5 4 3 2 1 posizione

X X X X

X X X X

X X X X

Gruppi

I₇ + I₆ + I₃ + p₂ = 0 I₇ + I₅ + I₃ + p₁ = 0 Bit di parità

I₇ I₆ I₅ p₄ I₃ p₂ p₁

CORREZIONE ERRORI CODICI DI HAMMING

STRINGA RICEVUTA: 0110011

INFORMAZIONE RICEVUTA: 0110 ok!!!!!

STRINGA RCEVUTA: 0111011

INFORMAZIONE RICEVUTA: ERRORE NEL 4 BIT, QUINDI CORREGGO E AVRO’ 0110011 ED ESTRAENDO L’INFORMAZIONE: 0110 ok!!!!!

S4 = p4 + I5 + I6 + I7 S2 =p2 + I3 + I6 + I7

S1 = p1+ I3 + I5 + I7

S4 = 0 S2 = 0 S1 = 0

S4 = p4 + I5 + I6 + I7 S2 =p2 + I3 + I6 + I7

S1 = p1+ I3 + I5 + I7

S4 = 1 S2 = 0 S1 = 0