Codici ridondanti e controllo dell’errore

1

Codici ridondanti e controllo dell’errore

Codici binari ridondanti sono utilizzati per la

individuazione di malfunzionamenti (guasto dei circuiti, difetti di trasmissione) che conducano a parole errate

In un codice ridondante, solo n delle parole disponibili sono lecite (dove n ≤ ) per cui

– se S non è una parola lecita, allora è certamente errata – se S è una parola lecita, allora è probabilmente corretta

K^m

… maggiore è la ridondanza maggiore è la probabilità di scoprire un errore … nessuna certezza che una parola codice lecita non sia errata ...

K^m-1

2

Un esempio: il controllo di parità

Utilizzato per il controllo dell’errore nella trasmissione di parole di codici binari completi (K = 2, n = 2^m )

Dal codice completo si ottiene un codice ridondante aggiungendo un bit con la seguente regola:

– 1 se gli m bit hanno un numero dispari di 1 – 0 se gli m bit hanno un numero pari di 1

le parole lecite del nuovo codice avranno un numero pari di 1 ...

aggiunta bit di parità parola

(m bit)

trasmissione parola

(m+1 bit)

Parola ricevuta (m+1 bit)

controllo di parità

Parola lecita (m bit)

segnalazione esito

trasmissione

… possibile scoprire un solo errore ...

3

Codifica in Bit Diretta ed Indiretta

Un codice binario associa ad ogni valore una parola codice in bit Una codifica in bit può anche essere ottenuta attraverso un codice

intermedio

T=(x1,x2,...,xn) J=(s1,s2,....,sk) E=(0,1)

• un codice intermedio associa ad ogni xi una stringa di sj

• un codice binario associa ad sj una stringa di bit

• sostituendo i simboli sj di ciascuna parola codice xi con la corrispondente parola in bit...

… diremo Indiretta un tale tipo di codifica ...

Esempio:

T= (x1,x2,...x10) J= (a,b,c) codice:

x1 aaa x6 abc x2 aab x7 aca x3 aac x8 acb x4 aba x9 acc x5 abb x10 baa codice binario per J:

a 00 b 01 c 11

X1 000000 X2 000001 X3 000011 X4 000100 X5 000101 X6 000111 X7 001100 X8 001101 X9 001111 X10 010000

Codifica Binaria Indiretta

5

SISTEMI DI NUMERAZIONE POSIZIONALI

La rappresentazione dei numeri richiede:

una codifica, ovvero la definizione di un alfabeto in codice e di un codice

la definizione di operazioni ed algoritmi che consentano di realizzare sulle rappresentazioni dei numeri le operazioni caratteristiche del tipo di numero codificato

6

un sistema di numerazione è quindi definito da:

• alfabeto in codice: ovvero l’insieme dei simboli base, che nel caso specifico vengono detti CIFRE

• un codice: e più in particolare un insieme di regole che permettono di definire la rappresentazione di un numero mediante una stringa di cifre

• un insieme di operazioni che realizzano sulla

rappresentazione dei numeri le operazioni previste per i numeri stessi

7

le persone usano il sistema di numerazione decimale:

• l’alfabeto in codice è costituito da dieci cifre

• la prima regola del codice è che una parola codice rappresenta un numero dato dalla somma dei numeri rappresentati dalle singole cifre che lo compongono

• la seconda regola è che il numero rappresentato da una cifra dipende dalla cifra stessa e dalla posizione

occupata dalla cifra nella stringa in cui si trova

più precisamente:

• alle cifre (0,1,2,3,4,5,6,7,8,9) vengono associati nell’ordine i primi 10 numeri naturali

• detto i il posto occupato dalla cifra c_iin una stringa (il posto 0 è il primo a partire da destra...), il numero rappresentato da tale cifra è: c_i*10ⁱ

esempio: la stringa 3543 rappresenta il numero:

3*10⁰ + 4*10¹ +5*10²+3*10³

• il sistema viene detto POSIZIONALE e PESATO

• 10 è detta la BASE del sistema

9

cambiando l’alfabeto in codice e la base, si possono costruire sistemi posizionali e pesati diversi da quello decimale

un numero X >0 si rappresenta mediante la stringa di cifre:

C_n-1C_n-2 ...C₁ C₀ . C_-1 C_-2... C_-m

se ⁱ

n

m i

i b

C X =

∑

−

= 1

… ovviamente nelle operazioni aritmetiche bisogna tener presente la base b della numerazione ...

…in generale ...

10

Il sistema decimale

• Cifre: (0,1,2,3,4,5,6,7,8,9)

• Base: b = 10

• Pesi: ... 10000 1000 100 10 1

11

Il sistema ottale

• Cifre: (0,1,2,3,4,5,6,7)

• Base: b = 8

• Pesi: ... 4096 512 64 8 1

10₈ = 8₁₀ 11₈ = 9₁₀ 12₈ = 10₁₀ 13₈=... .… = 19₁₀ 77₈ = 63₁₀ 100₈ = 64₁₀ 777₈= …. 1000₈ = ….

0.1₈ = 1/8₁₀ 0.01₈ = 1/64₁₀ 0.001₈ 0.77₈

Il sistema esadecimale

• Cifre: (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F)

• Base = 16

• Pesi: … 4096 256 16 1

10₁₆ = 16₁₀ 16C₁₆ = 364₁₀ 0.1 0.01

13

Il sistema binario

• Cifre: (0,1)

• Base = 2

• Pesi: ...2048 1024 512 256 128 64 32 16 8 4 2 1

10₂ = 2₁₀ 100₂ = 4₁₀ 111010₂ = 58₁₀ 0.1₂ = 1/2₁₀ 0.01₂ = 1/4₁₀ 0.11₂ = 3/4₁₀

14

Tabella riassuntiva

F 17

1111 15

E 16

1110 14

D 15

1101 13

C 14

1100 12

B 13

1011 11

A 12

1010 10

9 11

1001 9

8 10

1000 8

7 07

0111 7

6 06

0110 6

5 05

0101 5

4 04

0100 4

3 03

0011 3

2 02

0010 2

1 01

0001 1

0 00

0000 0

Esadecimale Ottale

Binario Decimale

15

… una caratteristica dei sistemi a base 2

se adottiamo per ciascuna cifra dell’alfabeto codice una codifica in numerazione binaria

– ad esempio ottale: (0,1,2,3,4,5,6,7) 000, 001, 010, 011, 100, 101, 110, 111

si ha che la codifica binaria indiretta coincide con quella diretta

– ad esempio: 77₈ = 111 111₂ 34₈= 011 100₂

idem se codice esadecimale: (0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F)

– (0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111)

– A9₁₆ = 1010 1001₂ FF₁₆= 1111 1111₂

i numeri periodici:

• il concetto di numero periodico è del tutto dipendente dalla base di numerazione

• un numero periodico in una determinata base può non esserlo in un’altra

• esempio: 1/3 è periodico nella base decimale

ma nella base 3 è esattamente rappresentato da 0.1;

0.1₁₀ è periodico in binario

17

CONVERSIONE DI BASE

Dato N>0 intero, in base decimale, convertirlo in base b

• dividiamo N per b, otteniamo un quoto Q₀ed un resto R₀

• dividiamo Q₀ per b, otteniamo un quoto Q₁ ed un resto R₁

• ripetiamo finché Q_n < b

N=Q₀b+R₀ Q₀=Q₁b+R₁ Q₁=Q₂b+R₂

...

Q_n-1=Q_nb+R_n

sostituendo avremo:

N = Q_nbⁿ⁺¹ + R_nbⁿ + R_n-1b^n-1 + … + R₁b +R₀b⁰ e quindi N nella base b è:

Q_nR_nR_n-1 ...R₁R₀

18

Esempio:

conversione di 10268 decimale in base ottale

10268 : 8 1283 resto 4 1283 : 8 160 resto 3 160 : 8 20 resto 0 20 : 8 2 resto 4 10268₁₀ = 24034₈

cifra meno significativa cifra più significativa

19

conversione in base binaria di 123 decimale 123 : 2 61 resto 1

61 : 2 30 resto 1 30 : 2 15 resto 0 15 : 2 7 resto 1 7 : 2 3 resto 1 3 : 2 1 resto 1 123₁₀ = 1111011₂

123 : 2 61 : 2

30 : 2 15 : 2

7 : 2 1 1 1 0 1 1

3 : 2 1

Esempio:

• nei calcolatori la rappresentazione interna di un numero è finalizzata a rendere efficienti gli algoritmi per le operazioni

• in genere è usata codifica a lunghezza fissa

– l’insieme di numeri rappresentati è finito

• sono usati sistemi posizionali

RAPPRESENTAZIONE DEI NUMERI

ad eccezione dei numeri interi positivi (caso banale), è effettuata una trasformazione del numero da

rappresentare in un altro numero “rappresentabile” ...

21

• insieme X dei numeri da rappresentare

– X è un intervallo di numeri interi o reali

• insieme Y dei numeri rappresentati

– Y è un intervallo finito

• trasformazione di un numero x∈X in un numero y∈Y – regola di trasformazione: y = R(x)

• rappresentazione in cifre (sistema posizionale) di y

• codifica in bit delle cifre

Trasformazione e codifica

22

Overflow e underflow

• overflow: tentativo di rappresentare un numero esterno all’intervallo

– se X è un intervallo di numeri interi allora Y deve avere almeno la stessa cardinalità

• underflow: un numero reale x≠0 viene rappresentato da y = 0 – X è un intervallo di numeri reali, rappresentati da Y

(intervallo finito) con un’approssimazione

ε

23

Parametri di un sistema di rappresentazione

• intervallo numerico e tipo del numero x da rappresentare

• regola di trasformazione y = R(x)

• condizione di overflow

• approssimazione

ε

(solo per i reali)

NB: se la base della numerazione della

trasformazione non è binaria, la codifica del numero in binario è indiretta ...

• base di numerazione

• codifica delle cifre in binario

(se la base della numerazione è diversa da 2)

• Y ed X coincidono,

• Numeri rappresentabili: 0 ≤y < M

• M = bⁿ

• b è la base di numerazione

– in pratica 2, 8, 16 … ma anche 10

• rappresentazione ad n cifre :

– C_n-1C_n-2 ....C₀ , dove 0 ≤≤C_i < b

• condizione di overflow: x ≥M

I numeri naturali

25

Aritmetica dei numeri naturali

• Algoritmi classici per la realizzazione delle operazioni aritmetiche (noti dalle elementari)

• le regole sono le stesse per tutti i sistemi di numerazione posizionali (non solo quello decimale):

– per addizione e sottrazione numeri in colonna e riporto …, – per moltiplicazione e divisione uso di tavole pitagoriche per

le singole cifre …

– un esempio … in decimale ... _{1 1 0 0}

4987 + 3232 8219

riporti

26

Aritmetica binaria

• Un numero viene rappresentato da una stringa di n bit

• L’intervallo rappresentato è: 0 ≤y < 2ⁿ

ad esempio se n = 16 l'intervallo è [0, 65536)

la stringa 1000 0000 0001 1010 rappresenta il numero 32794 infatti la stringa è pari a 801A esadecimale che vale 8*4096 + 1*16 + 10 = 32794

1 1 0 0

0110 + 0111 1101

riporti 110 ×

101 110−−110 11110

Somma Binaria

Prodotto Binario

27

Aritmetica binaria: tavole

r a b s r'

0 0 0 0 0

0 0 1 1 0

0 1 0 1 0

0 1 1 0 1

1 0 0 1 0

1 0 1 0 1

1 1 0 0 1

1 1 1 1 1

x ^{0 1}

0 0 0

1 0 1

Prodotto

Somma

r: riporto a,b: addendi s: somma r’: nuovo riporto

Rappresentazione con Aritmetica decimale

• Un numero viene rappresentato da d cifre decimali

• L’intervallo rappresentato è: 0 ≤y < 10^d

• per ogni cifra decimale si adotta una rappresentazione con k bit per cifra: il numero è rappresentato da k ×d bit

– ad esempio, per d = 4, l’intervallo è [0, 10000);

– adottando un sistema 8-4-2-1 (k = 4) un numero è rappresentato da 16 bit

– la stringa 1000 0000 0001 0010 rappresenta il numero 8012 (codifica indiretta di un numero in binario: l’alfabeto codice intermedio è costituito dalle cifre decimali)

29

• poiché si adotta la codifica a lunghezza fissa ad n cifre (k bit),

– rappresentazioni estese a sinistra – esempi: n=5, b=10 254 ==> 00254

n=5, b=2 4₁₀==> 00100

il tentativo di rappresentare 32 … :

0 0 1 0 0

1 0 0 0 0 0

… overflow

30

• il numero x = b^kè rappresentato da: C_k = 1 e da C_i= 0, per i ≠k

– esempi: n=5, b=10 100 ==> 00100 n=5, b=2 8 ==> 01000

• il prodotto (quoto) di un numero x per una potenza della base b^k si ottiene aggiungendo k cifre 0 alla destra del numero

(sopprimendo k cifre alla destra del numero)

– esempi: 252 * 100 = 25200 252 / 100 = 2 101 * 10 = 1010 101 / 10 = 10

Potenze alla base

… in decimale

31

0 0 1 0 0 * 10

… nei registri ...

• shift left

0 1 0 0 0

0 1 0 0 0 * 100 0 0 0 0 0

0 0 0 1 0 / 10

• shift right

0 0 0 0 1

0 0 0 1 0 / 100 0 0 0 0 0

Interi relativi: rappresentazione in segno e modulo ...

• Intervallo: x∈(-M , M)

• rappresentazione (tradizionale) in segno e modulo: s, y

– s = sign(x) --- y = |x|

• condizione di overflow: |x| ≥M

• n cifre per rappresentare il suo modulo e una cifra che precede le altre per rappresentare il segno

- in aritmetica binaria s = sign(x) è rappresentata da un bit:

s = 1 se x < 0; s = 0 se x≥≥ 0

s y

15 14 0

x∈(-2¹⁵, 2¹⁵) ^intervallo

aperto

33

... vantaggi e svantaggi

• vantaggio: coincide con la nostra usuale rappresentazione

• svantaggio: richiede il trattamento separato di segno e modulo: algoritmi aritmetici più pesanti ...

... nei calcolatori, per ovviare agli svantaggi dell’aritmetica della rappresentazione in segno e modulo, si adottano altre rappresentazioni ...

34

Rappresentazioni in complementi

• Intervallo: x∈[-M/2 , M/2)

– oppure x∈∈(-M/2 , M/2)

• trasformazione nell’intervallo y∈[0 , M) secondo la regola:

– x ≥≥ 0 →→ y = x – x < 0 →→ y = M - |x|

» si dice che y è il complemento ad M del modulo di x

• se M = bⁿ →→ rappresentazione in complementi alla base

- intervallo di x chiuso a sinistra

• se M = bⁿ-1 →→ complementi diminuiti

- intervallo di x aperto a sinistra

35

Rappresentazione di reali:

virgola fissa

• virgola fissa (fixed point): rappresentazione di numeri con n cifre, nella quale la posizione della virgola (o punto decimale) che separa la parte intera da quella frazionaria è predeterminata:

Es.: n cifre intere + m decimali

C_n-1C_n-2 ...C₁ C₀ . C_-1 C_-2... C_-m

• nella rappresentazione dei numeri frazionari (|x| < 1) la virgola è in prima posizione: .078900

- se la virgola occupa una posizione fissa, non necessita di essere rappresentata esplicitamente ...

Rappresentazione di reali: virgola mobile

• virgola mobile (floating point): un numero reale x è rappresentato mediante la coppia (M, E), dove:

- x = M · b^E ±± εε

- M è un numero frazionario o intero detto mantissa - E è un numero intero detto esponente o caratteristica - b è la base della numerazione (binaria nei calcolatori) - εε è l’approssimazione della rappresentazione

…. più ‘coppie’ Mantissa, Esponente Es.: dato il reale 13,78 (virgola fissa)

• 1,378·10¹

• 137,8 · 10^-1

• 0,001378 · ¹⁰⁴ (normalizzata)

37

... virgola mobile

• M∈[M_min, M_max]

• E∈[E_min, E_max]

• |M|∈[A_min, M_max]

}

• condizione di underflow: |x| < A_min b^Emin

• M è in virgola fissa, E rappresenta l’effettivo ordine di grandezza del numero x da rappresentare e quindi la posizione ideale della virgola

condizione di overflow