Sistemi  di  numerazione    

Sistema  binario,  o1ale,  esadecimale  Rappresentazione  delle  informazioni  

Informazioni  u8li  

Docente:  Carlo  Robino    

Conta1o:  carlo.robino@gmail.com    

Orari  ricevimento:  da  concordarsi  

Cominciamo  dall’abc  (senza  snobbarlo  …)  •  …  rappresentazione  (ed  elaborazione)  rigorosa  (ossia  

meccanizzabile)  dell’informazione:  •  Il  primo  8po  di  informazione  che  si  presta  ad  essere  

rigorosamente  rappresentato  è  l’informazione  numerica  •  Numeri  rappresenta8  mediante:  

–  aste,  fagioli,  …  –  cifre  greco-­‐romane  –  cifre  decimali  (o  in  altra  base)  

•  Una  prima  fondamentale  differenza  quan8ta8va  tra  le  diverse  tecniche  di  rappresentazione:  –  n  aste  per  rappresentare  il  numero  n  (numerazione  unaria)  –  ⎣logk(n)  ⎦  +  1  cifre  per  rappresentare  il  numero  n  in  base  k  –  dove  ⎣  x  ⎦  indica  il  più  piccolo  numero  intero  minore  o  uguale  a  x.  

La  rappresentazione  dell’informazione  non  numerica  

(Osservazioni  preliminari)  •  Informazione  testuale  (cara1eri)  •  Informazione  grafica  (pixel,  ma  anche  forme  più  …  

astra1e)  •  Informazione  musicale  (digitalizzata  o  no)  •  ….  Mul8medialità  …  

•  NB:  Fondamentale  dis8nguere  tra  rappresentazione  dell’informazione  in  forma  analogica  e  digitale:  L’ele1ronica  -­‐  e  l’informa8ca-­‐  moderne  sono  ormai  assestate  sulle  tecniche  digitali  

La  “macchina”  da  calcolo  -­‐in  senso  lato  e  astra1o-­‐  

(cominciando  dal  basso)  •  L’essenza  dell’informa8ca  sta  nello  scomporre  l’informazione  

in  “pezzi”  elementari  e  la  sua  elaborazione  in  operazioni  elementari:  

•  Che  cosa  più  elementare  del  bit,  ossia  di  due  possibili  valori  dell’informazione:  {0,1}  o  {Vero,  Falso},  …?  

•  Tu1a  l’informazione  -­‐discreta-­‐  può  essere  scomposta  -­‐  ossia  rappresentata  come  una  opportuna  sequenza  di  0  e  1  (e  quella  con8nua  può  essere  approssimata  in  questa  maniera)  

•  Una  par8colare  algebra  (  Boole  )  perme1e  una  facile  manipolazione  dei  simboli  

Primi  esempi  di  rappresentazione  di  informazioni  componendo  bit  

•  Byte:  sequenza  di  8  bit:  (00000000, 00000001, 00000010, …, 11111111).  •  Un  byte  può  rappresentare i numeri naturali da 0 a 255 (= 28 –1):���

zero = 00000000; 8 = 00001000; …; 255 = 11111111. •  … e i numeri interi compresi fra –127 e 127, ossia fra –(2(8–1) - 1) e (2(8–1) - 1)

(primo bit = 0: numero positivo, primo bit = 1: numero negativo; 0 = 00000000 e 0 = 10000000

•  (nel seguito vedremo una rappresentazione più efficace) •  I numeri reali: numeri razionali contenenti una parte intera e una frazionaria

che approssimano il numero reale con precisione arbitraria. Notazione in virgola fissa: si codificano separatamente la parte intera e la parte frazionaria: ad esempio: ��� 8.345 ( in base due):

–  primo byte (rappresentazione dell’intero 8) = 00001000 –  secondo byte (rappresentazione della parte frazionaria 0.345) = 01011000

(anche qui vedremo ulteriori rappresentazioni in seguito)

Codifica  ASCII  •  I caratteri ASCII (American Standard Code for Information

Interchange): –  sette bit usati per rappresentare 128 caratteri (ottavo per controllo). –  a ogni lettera (le maiuscole da A a Z, le minuscole da a a z), cifra (da 0 a 9) o

separatore (usato per la punteggiatura o come operatore aritmetico) viene assegnato un numero naturale rappresentabile in forma binaria.

•  Ad esempio “A” viene codificata in ASCII come numero 65 e la sua forma binaria è 01000001; il separatore “;” viene codificato come 59 e la sua forma binaria è 00111011.

•  NB: la stessa stringa di bit ha diversi significati, a seconda del tipo di informazione rappresentata!

Sistemi  di  numerazione  

•  Numerazione decimale: base=10

•  Conteggio:  0,  1,  2,  3,  4,  5,  6,  7,  8,  9  à  0  con  riporto

Rappresentazione  di  numeri  interi  •  Si  sceglie  una  base  b.  •  Si  scelgono  b  simboli  che  rappresentano  i  numeri  da  0  a  b-­‐1  

(cifre).  •  I  numeri  sono  rappresenta8  dai  coefficien8  del  polinomio  

per  le  potenze  della  base  •  Indichiamo  la  base  del  sistema  di  numerazione  con  il  pedice  

Nb  =  As  As-­‐1  …  A1  A0  0  ≤  Ai  ≤  b  -­‐  1  Valore  Nb  =  As  bs  +  As-­‐1  bs-­‐1  +  …  +  A1  b1  +  A0  b0  

•  La  rappresentazione  è  posizionale  poiché  il  peso  associato  alla  generica  cifra  Ai  dipende  dalla  posizione  di  Ai  

Sistemi  di  numerazione  

•  Numerazione  binaria:  base=2  

•  Conteggio:    0,  1  à  0  riporto  10,  11  à  0  riporto  100,  …  

•  Corrispondenza  binario-­‐decimale  

Sistemi  di  numerazione  

10101110102  •  Numerazione  binaria:  base  2.  Simboli  usa8:  0,  1  

         

1·∙  29  +  0·∙  28  +  1·∙  27  +  0·∙  26  +  1·∙  25  +  1·∙  24  +  1·∙  23  +  0·∙  22  +  1·∙  21  +  0·∙  20  =  

=  512+128+32+16+8+2=698  10  

Sistemi  di  numerazione:  o1ale  

•  Numerazione  o1ale:  base  8  •  Simboli  usa8:  0,  1,  2,  3,  4,  5,  6,  7  •  Esempio:  

3  7  1  58  3·∙  83  +  7·∙  82  +  1·∙  81  +  5·∙  80  =  =  3·∙512  +  7·∙64  +  8  +  5  =  

=  1536+448+8+5  =  1997  10  

Sistemi  di  numerazione:  esadecimale  

•  La  base  16  è  molto  usata  in  campo  informa8co  Cifre:  0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F  

•  La  corrispondenza  in  decimale  delle  cifre  oltre  il  9  è  

•  Esempio:  (3A2F)16  =  3X163  +  10X162  +  2X161  +  15X160  =  3X4096  +  10X256  +  2X16  +  15  =  (14895)10  

Sistemi  di  numerazione:  esempi  

•  Base  2  

•  Base  8  

Sistemi  di  numerazione:  esempi  

•  Base  16  

Sistemi  di  numerazione:  esempi  •  b  =  10,  N  =  14320  10  

N  =  1·∙  104  +  4·∙  103  +  3·∙  102  +  2·∙  10  +  0·∙  1  

•  b  =  2,  N  =  110100  2  N  =  1·∙  25  +  1·∙  24  +  0·∙  23  +  1·∙  22  +  0·∙  2  +  0·∙  1  =  32  +  16  +  4  =  52  10  

•  b  =  8,  N  =  3216  8  N  =  3·∙  83  +  2·∙  82  +  1·∙  8  +  6  =  1536  +  128  +  8  +  6  =  1678  10  

•  b  =  16,  N  =  AB9E  16  N  =  10·∙  163  +  11·∙  162  +  9·∙  16  +  15  =  40960  +  2816  +  144  +  15  =  43935  10  

Esercizi    

•  111010102=  •  4568=  •  F5216=  

Esercizi    

•  111010102=  1  ·∙  27+1  ·∙  26+1  ·∙  25+0  ·∙  24+1  ·∙  23+0  ·∙  22+1  ·∙  21+0  ·∙  20=  128+64+32+8+2=23410  

•  4568=  •  F5216=  

Esercizi    

•  111010102=  1  ·∙  27+1  ·∙  26+1  ·∙  25+0  ·∙  24+1  ·∙  23+0  ·∙  22+1  ·∙  21+0  ·∙  20=  128+64+32+8+2=23410  

•  4568=  4  ·∙  82+5  ·∙  81+6  ·∙  80=  4  ·∙  64+  40+6=  30210  •  F5216=  

Esercizi    

•  111010102=  1  ·∙  27+1  ·∙  26+1  ·∙  25+0  ·∙  24+1  ·∙  23+0  ·∙  22+1  ·∙  21+0  ·∙  20=  128+64+32+8+2=23410  

•  4568=  4  ·∙  82+5  ·∙  81+6  ·∙  80=  4  ·∙  64+  40+6=  30210  •  F5216=  15  ·∙  162+5  ·∙161+2  ·∙160=392210  

Conversione  di  base  •  Per  la  parte  intera:  •  Dato  un  numero  in  una  base  A,  si  vuole  rappresentarlo  in  base  B,  

cioè:  N  A  =  N  B  =  x0  +  B  (x1  +  B  (…B  xs)…)  

•  Se  dividiamo  N  A  per  la  nuova  base  B,  o1eniamo  un  quoziente  N1  ed  un  resto  R.  Uguagliando:  

N  A  =  R  +  B  N1  =  x0  +  B  (x1  +  B  (x2  +  …  )  )  •  da  cui:  

x0  =  R  (x1  +  B  (x2  +  …  )  )  =  N1  

•  Iterando  il  procedimento  con  N1  al  posto  di  N  A,  si  o1engono  tur  i  coefficien8  del  polinomio  nelle  potenze  di  B,  cioè  la  codifica  di  N  A  nella  nuova  base,  e  quindi  N  B  

Conversione  di  base:  numeri  frazionari  

Nb    =  0  ,  A-­‐1  A-­‐2  A-­‐3  A-­‐4  A-­‐5  Valore  Nb  =  A-­‐1  b-­‐1  +  A-­‐2  b-­‐2  +  A-­‐3  b-­‐3  +  A-­‐4  b-­‐4  +  A-­‐5  b-­‐5  

•  In  generale:  Qb    =  As  As-­‐1  …  A1  A0  ,  A-­‐1  A-­‐2  A-­‐3  …  A-­‐R  0  ≤  Ai  ≤  b  -­‐  1  Valore  Q  b  =  As  bs  +  As-­‐1  bs-­‐1  +  …  +  A1  b1  +  A0  b0  +  

+  A-­‐1  b-­‐1  +  A-­‐2  b-­‐2  +  A-­‐3  b-­‐3  +  …  +  A-­‐R  b-­‐R  •  Esempi:    

b  =  10,  N  =  325,23  10  N  =  3·∙  102  +  2·∙  101  +  5  +  2·∙  10-­‐1  +  3·∙  10-­‐2  

b  =  2,  N  =  101,01  2  N  =  1·∙  22  +  1  +  1·∙  2-­‐2  =  4  +  1  +  0,25  =  5,25  10  

Conversione  di  base  •  Per  la  parte  frazionaria:  •  Dato  un  numero  in  una  base  A,  si  vuole  rappresentarlo  in  base  B,  cioè:  

FA  =  FB  =  B-­‐1(x-­‐1  +  B-­‐1(x-­‐2  +  B-­‐1(…B-­‐1x-­‐r)…))  •  Se  mol8plichiamo  F  A  per  la  nuova  base  B,  o1eniamo  una  parte  intera  

I  ed  una  parte  frazionaria  F1.  Uguagliando:  FA  ·∙  B  =  I  +  F1  

•  da  cui:  x-­‐1  =  I  B-­‐1(x-­‐2  +  B-­‐1(…B-­‐1x-­‐r)…)  =  F1  

•  Iterando  il  procedimento  con  F1  al  posto  di  FA,  si  o1engono  i  coefficien8  del  polinomio  nelle  potenze  di  B,  cioè  la  codifica  di  FA  nella  nuova  base,  e  quindi  FB.  Il  procedimento  termina  quando  Fl  =  0,  oppure  quando  si  è  raggiunta  la  precisione  desiderata  (errore  <  B-­‐r  se  ci  si  ferma  al  termine  x-­‐r)  

In  modo  più  semplice  

•  Il  metodo  si  applica  qualsiasi  sia  base  nella  quale  si  intende  rappresentare  il  numero.  – Per  la  parte  intera  del  numero  si  applica  una  serie  di  divisioni  successive  

– Per  la  parte  frazionaria  di  si  applica  una  serie  di  mol8plicazioni  successive:  

Da  decimale  a  binario:  numeri  interi  

•  Si  divide  ripetutamente  il  numero  intero  decimale  per  2  fino  ad  o1enere  un  quoziente  nullo;  le  cifre  del  numero  binario  sono  i  res8  delle  divisioni;  la  cifra  più  significa8va  è  l’ul8mo  resto  

Da  decimale  a  binario:  numeri  razionali  

•  Si  mol8plica  ripetutamente  il  numero  frazionario  decimale  per  2,  fino  ad  o1enere  una  parte  decimale  nulla  o,  dato  che  la  condizione  potrebbe  non  verificarsi  mai,  per  un  numero  prefissato  di  volte;  le  cifre  del  numero  binario  sono  le  par8  intere  dei  prodor  successivi;  la  cifra  più  significa8va  è  la  parte  intera  del  risultato  della  prima  mol8plicazione  

Conversione  di  base:  numeri  interi  

Conversione  di  base:  numeri  frazionari