Sistemi di numerazione Numeri negativi e sottrazioni

Sistemi di numerazione
Conversione da base qualsiasi in decimale
Sistema di numerazione binario
Sistema di numerazione esadecimale
Conversione decimale binario
Conversione decimale esadecimale
Conversione binario esadecimale
Numeri negativi e sottrazioni
Rappresentazioe floating point IEEE 754
Comunicazione
L’informazione
Misura dell’informazione
Entropia
La codifica
Definizioni
Costruzione del codice
1° teorema di Shannon
Codifica ottimale di Huffman
Codici
Codici BCD
Codici con 5 o più bit
Codice Gray
Codici alfanumerici (ASCII)
Aritmetica BCD
Codici a controllo d’errore
Parità semplice ed incrociata
Codifica Hamming
Codifica CRC
A.C. Neve – L’informazione digitale
1
Sistemi di numerazione
Conversione da qualsiasi base in decimale
Si definisce sistema di numerazione un insieme finito di simboli e di regole, per mezzo delle quali è
possibile rappresentare delle quantità, facendo uso dei simboli aggregati in stringhe.
Per comprendere il funzionamento di un sistema di numerazione, è opportuno riesaminare il
funzionamento di quello decimale il quale è costituito da dieci simboli
0,1,2,3,4,5,6,7,8,9
Si consideri pertanto il numero Z = 3237,66 costituito da 6 cifre, 4 descrittive della parte intera e 2 della
parte frazionaria.
Posizione
3
Coefficiente
3
Peso
1000
2
2
100
1
3
10
0
7,
1
-1
6
0,1
-2
6
0,01
Questo numero può essere riscritto come:
3 0 0
2 0
3
0
0
0
7
0,
0,
6
0 6
+
+
+
+
+
o, equivalentemente come
Z = 3⋅103 + 2⋅102 + 3⋅101 + 7⋅100 + 6⋅10-1 + 6⋅10-2
Un qualsiasi numero costituito da 4+2 cifre potrà essere scritto nella seguente forma:
Z = C3⋅103 + C2⋅102 + C1⋅101 + C0⋅100 + C-1⋅10-1 + C-2⋅10-2
Dove i coefficienti Ci rappresentano le cifre costituenti la stringa di simboli.
Si noti che gli indici dei coefficienti coincidono con la numerazione delle posizioni nella stringa.
Nell’esempio proposto, la parte intera è costituita da 4 coefficienti aventi posizioni 3,2,1,0, mentre la
parte frazionaria è costituita da 2 coefficienti aventi posizioni –1 e –2.
In termini ancor più generali, un numero costituito da M cifre intere ed N cifre frazionarie, potrà essere
così rappresentato:
Z = CM-1⋅10M-1 + CM-2⋅10M-2 +…..C1⋅101 + C0⋅100 + C-1⋅10-1 + C-2⋅10-2 +…..C-N⋅10-N
Il sistema di numerazione considerato è anche detto a notazione posizionale in quanto, la quantità
rappresentata dipende oltre che dal valore dei singoli coefficienti, anche dalla posizione che questi
assumono all’interno della stringa infatti, i due coefficienti pari a 3 danno ben diverso contributo alla
A.C. Neve – L’informazione digitale
2
quantità totale in quanto, il primo contribuisce con una quantità pari a 3000 ed il secondo pari solo a 30;
lo stesso discorso vale per i due coefficienti pari a 6.
Tutta l’analisi fin ora condotta è stata dedicata al sistema di numerazione in base 10 il quale è costituito
da 10 simboli esattamente come le dita presenti nelle nostre mani.
Riflettendo su questo aspetto, ci si può facilmente rendere conto del fatto che questa scelta oltre ad
averci condizionato per molto tempo, non ha oggi nulla di più o di meno di qualsiasi altro sistema di
numerazione.
E’ pertanto possibile cambiare il sistema di numerazione usato mantenendo inalterate tutte le
considerazioni fin ora esposte e, sostituire al 10 il valore della nuova base B usata.
Un qualsiasi numero Z espresso in qualsiasi sistema di numerazione potrà essere così espresso:
Z = CM-1⋅BM-1 + CM-2⋅BM-2 +…..C1⋅B1 + C0⋅B0 + C-1⋅B-1 + C-2⋅B-2 +…..C-N⋅B-N
o, in forma più compatta come:
Z=
−N
∑C
i = M −1
i
⋅ Bi
Saranno ora esaminati alcuni esempi di sistemi di numerazione.
E’ opportuno evidenziare il che, la scelta del numero di simboli da usare è vincolata solo da due
considerazioni:
1) è obbligatorio definire un simbolo rappresentativo della quantità nulla
2) è obbligatorio definire un simbolo rappresentativo della quantità unitaria.
Da ciò si desume che il più piccolo sistema di numerazione che si può usare è quello chiamato binario il
quale utilizza i simboli 0 e 1.
Sistema di numerazione binario
In questo sistema di numerazione i simboli usati sono 0 e 1
Si consideri ora la seguente stringa di simboli:
Posizione
Coefficiente
Peso
3
1
8
2
1
4
1
0
2
0
1,
1
-1
1
0,5
-2
1
0,25
La quantità rappresentata da questa stringa risulta:
Z = 1⋅23 + 1⋅22 + 0⋅21 + 1⋅20 + 1⋅2-1 + 1⋅2-2 = 8 + 4 + 0 +1 + 0,5 + 0,25 = 13,7510
Come si può notare, la tecnica di conversione è quella introdotta in precedenza con la variante che, in
questo caso, il valore della base B è pari a 2.
A differenza di tutti gli altri sistemi di numerazione, quello binario consente una conversione in
decimale molto più rapida in quanto i coefficienti della stringa possono valere solo 0 o 1 per cui, nello
A.C. Neve – L’informazione digitale
3
sviluppo di potenze, non sarà necessario effettuare i vari prodotti ma basterà sommare solo i pesi relativi
alle cifre di valore 1.
Si consideri questo nuovo esempio:
Posizione
Coefficiente
Peso
4
1
16
3
1
8
2
0
4
1
1
2
0
1,
1
-1
1
0,5
-2
-3
0
1
0,25 0,125
La quantità rappresentata dalla stringa binaria risulterà:
Z = 16 + 8 + 2 + 1 + 0,5 + 0,125 = 27,62510
Vengono così sommati i soli pesi dei bit pari a 1.
Sistema di numerazione esadecimale
Per questo sistema di numerazione sorgono delle difficoltà relative alla scelta dei 16 simboli da usare, si
è quindi deciso di utilizzare i 10 simboli del sistema decimale ed in più le prime 6 lettere dell’alfabeto
ottenendo così:
Esadecimale
Decimale
0
0
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
A
10
B
11
C
12
D
13
E
14
F
15
Si consideri il seguente esempio:
Posizione
Coefficiente
Peso
3
2
4096
2
A
256
1
0
16
0
F,
1
-1
-2
C
3
0,0625 0,00390625
La quantità rappresentata dalla stringa esadecimale risulterà:
Z = 2⋅163 + A⋅162 + 0⋅161 + F⋅160 + C⋅16-1 + 3⋅16-2 =
8192 + 2560 + 0 +15 + 0,75 + 0,01171875 = 10767,7617187510
Anche in questo caso, si riconferma l’unicità della tecnica di conversione.
Considerazioni comuni
Il massimo valore intero rappresentabile con K cifre risulta pari a BK -1
Con 8 cifre binarie, il massimo valore rappresentabile è pari a 28 – 1 = 255
Con 5 cifre decimali, il massimo valore rappresentabile è pari a 105 –1 = 99999
Con 4 cifre esadecimali, il massimo valore rappresentabile è pari a 164-1 = 65535
Come si può notare, più grande è la base del sistema di numerazione, e minore è il numero di cifre
necessarie per rappresentare una stessa quantità e viceversa:
11111111111111112 = 6553510 = FFFF16
A.C. Neve – L’informazione digitale
4
Soprattutto in binario, per le applicazioni elettroniche, è spesso necessario conoscere in anticipo il
numero di bit che servono per rappresentare una certa quantità, per es. quanti bit sono necessari per
contare in binario fino a 1000010.
A questa domanda si risponde determinando il valore di K che soddisfa alla seguente diseguaglianza:
2K ≥ 10000
da cui risulta
K ≥ 14
in quanto 214 = 16384
A tal proposito può essere molto utile la seguente tabella:
K
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2K
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
Conversione da decimale in qualsiasi base
La conversione di un numero decimale in una qualsiasi base avviene attraverso una serie di operazioni
iterative. Considerato un numero decimale costituito da parte intera e parte frazionaria, si deve operare
separatamente prima sulla parte intera e poi sulla parte frazionaria.
La conversione della parte intera avviene operando su di esso una serie di divisioni successive per la
base in cui si vuole pervenire e conservando i resti in ordine inverso a quello di generazione.
Queste operazioni terminano con il raggiungimento del quoziente nullo.
La conversione della parte frazionaria avviene operando su questa una serie di moltiplicazioni
successive (delle sole parti frazionarie di volta in volta ottenute) per la base in cui si vuole pervenire e
conservando poi, le parti intere dei risultati ottenuti nell’ordine di generazione.
Queste operazioni terminano col raggiungimento di un risultato dotato di parte frazionaria nulla.
A.C. Neve – L’informazione digitale
5
Conversione Decimale Binario
Si consideri il numero decimale 48,375.
La conversione avviene convertendo prima il valore 48 e poi il valore 0,375.
48 : 2 = 24
24 : 2 = 12
12 : 2 = 6
6:2= 3
3:2= 1
1:2= 0
con resto
con resto
con resto
con resto
con resto
con resto
0,375 x 2 =
0,750 x 2 =
0,500 x 2 =
0 ,750
1 ,500
1 ,000
0
0
0
0
1
1
si ha quindi che 4810 = 1100002
si ha quindi che 0,37510 = 0,0112
Al termine del processo si ha quindi che:
48,37510 = 110000,0112
Si consideri ora il numero decimale 49,7.
La conversione avviene convertendo prima il valore 49 e poi il valore 0,7.
49 : 2 = 24
24 : 2 = 12
12 : 2 = 6
6:2= 3
3:2= 1
1:2= 0
con resto
con resto
con resto
con resto
con resto
con resto
0,700 x 2 =
0,400 x 2 =
0,800 x 2 =
0,600 x 2 =
0,200 x 2 =
0,400 x 2 =
0,800 x 2 =
1 ,400
0 ,800
1 ,600
1 ,200
0 ,400
0 ,800
1 ,600
1
0
0
0
1
1
si ha quindi che 4910 = 1100012
si ha quindi che 0,710 = 0,1011001……2
Al termine del processo si ha quindi che:
49,710 = 110001,1011001…..2
come si può notare, la conversione della parte frazionaria non risulta completa in quanto, il calcolo delle
moltiplicazioni successive non potrà mai avere termine. La conversione della parte frazionaria non è
pertanto precisa ma è affetta da errore. Riconvertendo in decimale il valore 0,10110012 ora ottenuto, si
trova essere pari a 0,6953125 che è inferiore a 0,7 di una quantità pari a 0,0046875.
L’errore percentuale commesso sulla parte frazionaria, risulta quindi pari al 0,669%.
E’ quindi necessario prolungare il processo di conversione, fino ad ottenere un valore affetto da un
errore sufficientemente piccolo da non influenzare l’applicazione che si sta sviluppando.
A.C. Neve – L’informazione digitale
6
Conversione Decimale Esadecimale
Si consideri il numero decimale 60,87.
La conversione avviene convertendo prima il valore 60 e poi il valore 0,87.
60 : 16 = 3 con resto 12 (C)
3 : 16 = 0 con resto 3
0,87 x 16 =
0,92 x 16 =
0,72 x 16 =
0,52 x 16 =
0,32 x 16 =
0,12 x 16 =
si ha quindi che 6010 = 3C16
13 ,92
14 ,72
11 ,52
8 ,32
5 ,12
1 ,92
si ha quindi che 0,8710 = 0,DEB851…..16
Al termine del processo si ha quindi che:
60,8710 = 3C,DEB851…..16
Anche in questo caso, la conversione è approssimata.
Conversione da Binario in Esadecimale e viceversa
La conversione tra sistemi di numerazione con basi qualsiasi e differenti da quella decimale, avviene
con una doppia conversione: dalla prima base, in quella decimale e, da quella decimale nella seconda
base.
Esiste però la possibilità di effettuare la conversione in modo diretto quando le due basi risultano
entrambe potenza di due come per es. le basi 2,4,8,16.
Si consideri il numero binario 11011000001010012 e lo si converta in esadecimale.
La conversione avviene associando i bit in gruppi da quattro a partire dall’estrema destra e convertendo
singolarmente questi gruppi in esadecimale:
0110 1100 0010 1001
6
C
2
9
Lo stesso metodo viene usato per la conversione opposta:
A
7
B
0
5
1010 0111 1011 0000 0101
A.C. Neve – L’informazione digitale
7
Decimale
Binario
Ottale
Esadecimale
0.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
0
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111
10000
10001
10010
10011
10100
10101
10110
10111
11000
11001
11010
11011
11100
11101
11110
11111
100000
100001
100010
100011
100100
100101
100110
100111
101000
101001
101010
101011
101100
101101
101110
101111
110000
110001
110010
110011
110100
110101
110110
110111
111000
111001
111010
111011
111100
0
1
2
3
4
5
6
7
10
11
12
13
14
15
16
17
20
21
22
23
24
25
26
27
30
31
32
33
34
35
36
37
40
41
42
43
44
45
46
47
50
51
52
53
54
55
56
57
60
61
62
63
64
65
66
67
70
71
72
73
74
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
10
11
12
13
14
15
16
17
18
19
1A
1B
1C
1D
1E
1F
20
21
22
23
24
25
26
27
28
29
2A
2B
2C
2D
2E
2F
30
31
32
33
34
35
36
37
38
39
3A
3B
3C
A.C. Neve – L’informazione digitale
8
Numeri negativi e sottrazioni
Il problema dei numeri negativi sarà inizialmente affrontato, in questa nota, operando su campi fissi da 4
bit e, successivamente, generalizzato a n bit.
0000
1111
1110
0
15
0001
0010
1
14
1101
2
0011
3
13
A
12
1100
4
5
11
1011
0100
10
9
1010
1001
0101
6
7
8
Si consideri un registro a 4 bit, le configurazioni
definibili al suo interno sono:
00002, 00012, 00102, 00112,………..11102, 11112, alle
quali è possibile associare i valori decimali 0,+1,+2,+3,
…………….+14,+15, come visibile nel registro
circolare A.
Come si può notare, con questa tecnica è possibile
rappresentare solo numeri positivi.
0110
0111
1000
Si ipotizzi ora di voler rappresentare numeri positivi e negativi.
Non avendo il registro alcuna possibilità di discriminare tra numeri positivi e negativi, è evidente la
necessità di dover sacrificare uno dei bit del registro per la definizione del segno.
Rappresentazione modulo e segno
Con questa tecnica, si assegna al bit più significativo il compito di rappresentare il segno:
0 per i numeri positivi e 1 per i numeri negativi come esposto nel registro B.
0000
1111
1110
-7
0
0001
-6
1101
0010
1
2
B
-4
1100
0100
4
5
-3
1011
0011
3
-5
-2
6
-1
1010
1001
0
1000
7
0101
0110
0111
Si ha quindi che: 00112 = +310 e poi 10112 = -310
In questo caso si hanno 7 configurazioni per i numeri
positivi ed altrettante per quelli negativi con la presenza
di due configurazioni per lo zero:
00002 = 10002 = 010
E’ pertanto possibile contare da –710 a +710 o, più in
generale, da –(2n-1 –1) fino a +(2n-1-1).
Questa tecnica di rappresentazione è però poco usata sia
per la presenza di due configurazioni associate allo zero,
come pure per le difficoltà che si incontrano
nell’effettuare le sottrazioni.
Rappresentazione complemento a due
Per analogia a quanto avviene nel sistema di numerazione decimale (complemento a 10), si definisce il
complemento a 2 di un numero binario ad n bit la quantità:
Complemento a 2 di N = 2n - N
Come si può notare la somma di un numero ad n bit più il suo complemento a 2 è sempre pari a 2n.
A.C. Neve – L’informazione digitale
9
0000
1111
1110
0
-1
0010
1
-2
1101
2
0011
3
-3
C
-4
1100
4
0100
Si ha quindi che:
+310 = 00112
5
-5
1011
Con questa tecnica, i numero positivi sono rappresentati
un binario puro mentre quelli negativi sono rappresentati
in complemento a 2.
0001
-6
-8 7
-7
1010
0101
6
1001
-310 = Complemento a 2 di +310 = 11012
0110
0111
1000
Un metodo pratico per ottenere il complemento a 2 di un numero è il seguente:
si complementa il numero e poi si somma 1. Analogamente per il processo inverso.
si consideri il +310 che in binario è pari a 00112, il suo complemento è uguale a 11002, dopo avergli
sommato 1 si ottiene 11012.
Come si può osservare dal registro C, con questa rappresentazione esiste una sola configurazione
associata allo zero e l’insieme dei numeri positivi è di una unità inferiore a quello dei numeri negativi.
E’ pertanto possibile contare da –810 fino a +710 o, più in generale da –2n-1 fino a +2n-1-1.
Si noti anche che tutti i numeri positivi hanno il bit più significativo pari a zero mentre tutti i numeri
negativi hanno il bit più significativo pari ad uno.
Sottrazioni
0000
1111
1110
-1
0
0001
0010
1
-2
1101
2
-4
2 – 5 = -3
4
0100
5
-5
1011
Si ipotizzi di dover effettuare la differenza:
0011
3
-3
1100
E’ evidente che, in un registro a 4 bit, il risultato di una
sottrazione non potrà essere più grande di +7 ne inferiore
a –8.
-6
-7
1010
1001
0101
6
-8 7
1000
0110
0111
In prima ipotesi è possibile, partendo da zero, portare
avanti l’indice del registro di due posizioni e poi indietro
di cinque ottenendo il risultato corretto.
Si può però ottenere lo stesso risultato facendo prima
avanzare l’indice di due posizioni, e poi facendo di
nuovo avanzare l’indice di (16 – 5) posizioni e cioè di
(2n-5) che è il corrispondente complemento a 2.
In termini più rigorosi si ha che:
S = A – B = A + (-B) = A + (2n – B) = A + complemento a 2 di B
Si è quindi trasformata la differenza in una somma.
A.C. Neve – L’informazione digitale
10
Esempi:
Si considerino i seguenti numeri:
+2 = 0010
+5 = 0101
-2 = 1110
-5 = 1011
si effettuino ora le seguenti operazioni:
+2
+5
+7
0010
0101
0111 = +7
-2
+5
+3
1110
0101
1 0011 = +3
+2
-5
-3
0010
1011
1101 = -3
-2
-5
-7
1110
1011
1 1001 = -7
Nei sistemi digitali si opera generalmente con campi di dimensioni fisse e pari a 8,16 o 32 bit.
Con un campo di 8 bit si potrà contare da –128 fino a +127, ottenendo:
-128
+127
+1
0
-1
10000000
01111111
00000001
00000000
11111111
Con un campo di 16 bit si potrà contare da –32768 fino a + 32767
Con un campo di 32 bit si potrà contare da –2147483648 fin a + 2147483647.
Esempi:
+100
-25
+75
01100100
11100111
1 01001011
+99
-100
-1
01100011
10011100
11111111
A.C. Neve – L’informazione digitale
11
Rappresentazione floating point
standard IEEE 754 - 1985
All’interno di un elaboratore, la rappresentazione dei numeri reali in precisione semplice viene
realizzata per mezzo della notazione floating point standard IEEE 754 - 1985 la quale utilizza un campo
di 32 bit così organizzato:
- 1 bit per il segno
- 8 bit di esponente “BIASED 127”
- 23 bit di parte frazionaria (mantissa)
31 30...............…23 22.........................................................0
S
esponente E
mantissa F
il valore decimale associato alla stringa è dato dalla seguente relazione:
N = ( − 1) S ⋅ ( 2 E −127 ) ) ⋅ (1, F )
Il bit 31 rappresenta il segno del numero: 0 se positivo, 1 se negativo.
L’esponente E è rappresentato da otto bit senza segno con un bias pari a 28-1-1 = 127, pertanto un
numero pari a 2A avrà, nella stringa, un esponete E = A +127.
Il valore di E sembrerebbe quindi poter variare tra 0 e 255 quando l’esponente A del numero varia tra
-127 e +128, in pratica però lo standard prevede che l’esponete A possa variare solo tra –126 e +127.
L’esponente 12810 = 111111112 viene usato per rappresentare una situazione di underflow o di
overflow oppure un NaN (Not a Number) quando l’esponente richiesto è più grande del massimo
consentito.
Se la mantissa è zero, l’esponente 000000002 è usato per indicare lo zero (questo è un caso speciale in
quanto il primo uno è normalmente sempre implicito).
In decimale, i numeri rappresentabili avranno un range dinamico compreso tra 10+38 e 10-38
consentendo così la rappresentazione di valori sia estremamente grandi che estremamente piccoli.
La parte frazionaria (mantissa) è costituita da 23 bit senza segno, il bit meno significativo risulta avere
un peso pari a 2-23 il che consente una precisione di una parte su 2+23 equivalente a sette cifre
significative decimali.
La notazione floating point ha la caratteristica di garantire lo stesso numero di cifre significative, e
quindi la stessa precisione di rappresentazione, per tutti i numeri compresi tra 10+38 e 10-38.
Nella rappresentazione in doppia precisione si usa un campo di 64 bit così costituito:
- 1 bit per il segno
- 11 bit di esponente “BIASED 1023”
- 52 bit di parte frazionaria (mantissa)
In questo caso, la precisione è di quindici cifre significative ed il range tra 10-308 e 10+308.
A.C. Neve – L’informazione digitale
12
Esempi:
1) Si consideri il numero decimale -11,375:
(-11,375)10 = (-1011,011)2 2+0 = (-1,011011)2 2+3
come si può notare il numero è stato portato nella forma (1,F) 2A
si ha quindi che:
S=1
E = (3)10 +(127)10 = (130)10 = (10000010)2
F = (0110 1100 0000 0000 0000 000)2
La stringa risulta quindi:
1100 0001 0011 0110 0000 0000 0000 0000
C
1
3
6
0
0
0
0
2) Si consideri il numero decimale +625,00137
(+625,00137)10 = (+1001110001,00000000010110)2 2+0 = (1,00111000100000000010110)2 2+9
come si può notare il numero è stato portato nella forma (1,F) 2A
si ha quindi che:
S=0
E = (9)10 + (127)10 = (136)10 = (10001000)2
F = (0011 1000 1000 0000 0010 110)2
La stringa risulta quindi:
0100 0100 0001 1100 0100 0000 0001 0110
4
4
1
C
4
0
1
6
3) Si consideri il numero decimale -0,005:
(-0,005)10 = (-0,0000000101000111101011100001010)2 2+0 = (1,01000111101011100001010)2 2-8
come si può notare il numero è stato portato nella forma (1,F) 2A
si ha quindi che:
S=1
E = (-8)10 + (127)10 = (119)10 = (01110111)2
F = (0100 0111 1010 1110 0001 010)2
La stringa risulta quindi:
1011 1011 1010 0011 1101 0111 0000 1010
B
B A 3
D 7
0
A
A.C. Neve – L’informazione digitale
13
Comunicazione
TX
Sorgente
Codificatore
Controllore di
canale
RX
Mezzo trasmissivo
Riconoscitore
stato di canale
Gestore del protocollo
Destinatario
Gestore del protocollo
Codificatore: Trasforma l’informazione nella forma più idonea Mezzo trasmissivo: E’ il supporto fisico sul
quale viaggia l’informazione sotto forma di
ad essere trasmessa. Genera quindi il messaggio
segnale.
Controllore di canale: Elabora l’informazione codificata in E’ la parte più critica e più soggetta ad errori.
modo che possa viaggiare nel mezzo trasmissivo. Viene così La principale caratteristica è la Banda
Passante (Larghezza di canale) che limita la
generato il segnale.
velocità di trasferimento.
Gestore del protocollo: Supervisiona il processo di trasmissione
rispettando un insieme di regole che permettono il corretto
avvio, trasferimento e chiusura del processo di trasmissione.
Riconoscitore dello stato di canale: Estrae l’informazione
codificata dalla grandezza fisica usata per il suo trasporto lungo il
mezzo trasmissivo.
Decodificatore: Riconosce l’informazione codificata e ne valuta la
sua correttezza.
Gestore del protocollo: Supervisiona il processo di trasmissione
rispettando un insieme di regole che permettono il corretto avvio,
trasferimento e chiusura del processo di trasmissione.
Disturbi e rumori sono le principali cause di errore. Non sono prevedibili nel tempo e nei valori.
I disturbi provengono dall’esterno infiltrandosi e propagandosi lungo il sistema di comunicazione (impulsi elettromagnetici).
Il rumore viene generalmente generato all’interno del sistema stesso dai vari componenti o dal loro funzionamento.
A.C. Neve – L’informazione digitale
Decodificatore
14
L’informazione
Le basi dell’attuale teoria dell’informazione sono state sviluppate da Shannon e Weaver in “The
mathematical theory of communication” Univ. of Illinois Press – 1964 (tradotto da ETAS).
Nell’ambito della comunicazione, l’aspetto che più rende interessante un messaggio è il suo carattere
di eccezionalità nel senso che, meno prevedibile è la notizia e maggiore è la sensazione di aver
aumentato la conoscenza o equivalentemente, di aver diminuito il grado di incertezza.
Particolarmente apprezzata è anche la variazione dell’informazione ricevuta.
Una stessa informazione viene poi apprezzata in modo differente da due destinatari che dispongono di
un differente livello di conoscenze.
Da queste considerazioni preliminari appare evidente che nel seguito sarà necessario ricorrere all’uso
di concetti e strumenti di tipo probabilistico. E’ infatti evidente che, se il ricevitore è in grado di
conoscere con assoluta certezza il contenuto di un messaggio, quest’ultimo non trasporterà alcuna
informazione ne sarà in grado di rimuovere incertezza.
Una sorgente di informazione è caratterizzata da:
1) Un numero N ≥ 2 di simboli che costituiscono l’alfabeto
2) I simboli stessi x1,x2, … xN
3) La probabilità di ricorrenza di ciascun simbolo p(x1), p(x2), … p(xN)
con
N
∑ p( x ) = 1
i =1
i
Una sorgente di questo tipo è chiamata Sorgente Discreta Senza Memoria.
Per una sorgente di dati binari si avrà che:
N=2
x1=0, x2=1
p(x1)=0.5, p(x2)=0.5
Per una sorgente alfabetica si avrà che:
N = 27
x1=a, x2=b, x3=c ….. x26=z x27=spazio
p(x1)=1/27, p(x2)=1/27 ….. p(x27)=1/27
Come affermato da Shannon, in una lingua esistono delle correlazioni sintattiche tra le varie lettere
dell’alfabeto (parole con tre consonanti di seguito sono rare, con quattro nessuna) per cui è necessario
associare alla sorgente anche le probabilità condizionali dei vari simboli oltre a quelle delle loro
ricorrenze. Divenendo così i simboli statisticamente dipendenti, la sorgente avrà bisogno di una
memoria e sarà detta Sorgente Discreta Con Memoria.
A.C. Neve – L’informazione digitale
15
MISURA DELL’INFORMAZIONE
L’idea fondamentale dalla quale nasce la misura dell’informazione si basa sull’ipotesi di esistenza di
incertezza in chi deve ricevere l’informazione e che parte di questa incertezza venga rimossa
dall’informazione ricevuta.
Si considerino due sorgenti di informazione binaria cioè con N = 2 e tali che:
per la prima
p(x1) = 0.5 e p(x2) = 0.5
per la seconda p(x1) = 0.9 e p(x2) = 0.1
E’ evidente che, nella prima sorgente entrambi i simboli sono in grado di rimuovere la stessa quantità
di incertezza poiché sono equiprobabili, mentre nel secondo caso solo il simbolo x2 è in grado di
rimuovere una grande quantità di incertezza in quanto la ricezione del primo simbolo è quasi scontata a
causa della sua elevata probabilità.
La situazione peggiore si ha nel caso in cui p(x1) = 1 e p(x2) = 0 in quanto la certezza di ricevere
sempre il simbolo x1 non sarà in grado di fornire alcuna informazione ne di rimuovere incertezza.
Si intuisce anche che la situazione ottimale sarà quella con p(x1) = p(x2) = 0.5.
Indicando con I(xi) la quantità di informazione associata al simbolo xi si dovrà avere che:
1) Se
2) Se
3) Se
p(xi) = p(xj) ⇒ I(xi) = I(xj)
p(xi) < p(xj) ⇒ I(xi) > I(xj)
p(xi) = 1
⇒ I(xi) = 0
E’ necessario a questo punto introdurre una ulteriore considerazione:
la misura dell’informazione dovrebbe risultare additiva nel senso che l’informazione associata ad un
messaggio dovrebbe essere uguale alla somma delle informazioni associate ai simboli che la
costituiscono (dal punto di vista delle probabilità si tratta del prodotto delle probabilità)
I(xi,xj) = I(xi) + I(xj)
La funzione matematica che meglio soddisfa le considerazioni fin ora esaminate è il logaritmo infatti:
è una funzione crescente
vale zero quando l’argomento è pari ad 1
il logaritmo del prodotto è pari alla somma dei logaritmi
si ha quindi che l’informazione associata ad un simbolo xi avente una probabilità pari a p(xi) è:
1
) = − log 2 ( p ( xi ))
p ( xi )
La scelta della base del logaritmo non è un problema in quanto il passaggio da una base ad un’altra
implica solo il prodotto per una costante infatti è ben noto che:
I ( xi ) = log 2 (
loga(p) = K·logb(p) con K= 1/logb(a)
dato che la base di calcolo più diffusa è quella in base 10, si ha che:
log 2 N =
A.C. Neve – L’informazione digitale
1
⋅ log10 N = 3.321928 ⋅ log10 N
log10 2
16
tutto ciò sarebbe solo equivalente ad una variazione dell’unità di misura.
La scelta del logaritmo in base 2 implica una misura dell’informazione espressa in BIT.
Questo tipo di misura dell’informazione è utile quando tutti i simboli della sorgente sono
equiprobabili.
Si può però verificare che, due sorgenti con lo stesso valore di N ma con differenti probabilità dei vari
simboli possono, a parità di lunghezza di messaggio, trasportare differenti quantità di informazione.
In questo caso si utilizza il valore medio delle informazioni associate ai simboli della sorgente e cioè:
N
N
i =1
i =1
H ( x) = ∑ p( xi ) ⋅ I ( xi ) = ∑ p ( xi ) ⋅ log 2
1
p ( xi )
La quantità H(x) è detta entropia ed è misurata in bit/simbolo.
Si può dimostrare che per l’entropia risulta valida la relazione:
H ( x) ≤ log 2 N
la cui interpretazione ci induce ad affermare che l’entropia assume il valore massimo log2N quando
tutti i simboli della sorgente hanno la stessa probabilità pari ad 1/N, sotto queste condizioni si ha infatti
che:
N
 1 
 1 
H ( x) = ∑ p ( xi ) ⋅ log 2 
 = N ⋅ p ( xi ) ⋅ log 2 

i =1
 p ( xi ) 
 p ( xi ) 
risultando però che p(xi) =1/N si ha che:
H ( x) = N ⋅
1
⋅ log 2 N = log 2 N
N
L’entropia di una sorgente binaria varia, in funzione della probabilità associata ai suoi due simboli,
secondo il seguente andamento:
0.993
1
0.8
Sia
p(x1) = x e p(x2) = (1-x)
0.6
con
p(x1) + p(x2) = 1 e 0<x<1
H ( x)
si ha quindi che:
0.4
 1 
 1 
H ( x) = x ⋅ log 2   + (1 − x) ⋅ log 2 

 ( x) 
 (1 − x) 
0.2
0.08
0
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 1.1 1.2 1.3 1.4 1.5
0.01
x
A.C. Neve – L’informazione digitale
1.5
17
Esempio:
Si consideri una sorgente di informazione capace di emettere tre simboli tali che:
p(x1) = 0.5 p(x2) = 0.25 e p(x3) = 0.25
l’informazione associata ai tre simboli risulterà:
I(x1) = log2(1/0.5) = log2(2) = 1 bit
I(x2) = log2(1/0.25) = log2(4) = 2 bit
I(x3) = log2(1/0.25) = log2(4) = 2 bit
Esempio:
Si considerino due differenti sorgenti di informazione in grado di emettere quattro simboli tali che:
Sorgente S1 ⇒ p(x1) = 0,5 p(x2) = 0.25 p(x3) = 0.125 p(x4) = 0.125
Sorgente S2 ⇒ p(x1) = 0,25 p(x2) = 0.25 p(x3) = 0.25 p(x4) = 0.25
Determinare la quantità di informazione associata al messaggio (x1 x3 x2 x1).
La quantità di informazione associata al messaggio è data da:
 1
 1 
 1 
 1 
 1 
1
1
1 
I T = log 2 
⋅
⋅
⋅
 = log 2 
 + log 2 
 + log 2 
 + log 2 
=
 p( x1 ) 
 p( x2 ) 
 p( x1 ) 
 p ( x1 ) p( x3 ) p( x 2 ) p( x1 ) 
 p ( x3 ) 
= I ( x1 ) + I ( x3 ) + I ( x 2 ) + I ( x1 )
Si ha quindi che:
Per la sorgente S1 ⇒ IT = 1 + 2 + 3 + 3 = 9 bit
Per la sorgente S2 ⇒ IT = 2 + 2 + 2 + 2 = 8 bit
Come si può notare, la quantità di informazione relativa a messaggi della stessa lunghezza, può
differire a secondo del tipo di sorgente utilizzata.
Esempio:
Calcolare l’entropia degli esempi precedenti.
N
H ( x) = ∑ p ( xi ) ⋅ I ( xi )
i =0
1° caso: H(x) = (1/2)*1 + (1/4)*2 + (1/4)*2 = 1.5 bit/simbolo
2° caso: H(x) = (1/2)*1 + (1/4)*2 + (1/8)*3 + (1/8)*3 = 1.75 bit/simbolo
3° caso: H(x) = (1/4)*2 + (1/4)*2 + (1/4)*2 + (1/4)*2 = 2.0 bit/simbolo
Come si può notare, la sorgente del terzo caso presenta il più alto valore di entropia che è determinato
dal fatto che tutti i simboli sono equiprobabili.
A.C. Neve – L’informazione digitale
18
LA CODIFICA
L’operazione di codifica serve a trasformare gli N simboli, generati da una sorgente informativa, in
una sequenza di bit che dovranno poi essere canalizzati in un mezzo trasmissivo per poter inviare
l’informazione da una sorgente ad un destinatario in modo sicuro e veloce.
Un codice è caratterizzato da:
i simboli usati i quali, aggregati in stringhe, secondo opportune regole, definiscono le parole del
codice.
L’operazione di generazione di queste parole è detta codifica.
-
Un codice si dice distinto se tutte le sue parole sono tra loro distinguibili
Un codice distinto si dice univocamente decodificabile se tutte le sue parole sono identificabili
quando siano inserite in una qualsiasi sequenza di parole in codice.
Un codice univocamente decodificabile si dice istantaneamente decodificabile se tutte le sue
parole sono identificabili non appena ricevuto l’ultimo bit.
Un codice si dice efficiente se usa il minimo numero di bit necessari
Un codice si dice ridondante se usa un numero di bit superiore a quello strettamente necessario.
Per poter ricostruire il messaggio originale, è necessario che il codice risulti distinto ed univocamente
decodificabile. Non è necessario che il codice sia istantaneamente decodificabile a meno che non ci
siano problemi di velocità o si usino sistemi che operino in tempo reale.
Dal punto di vista dell’efficienza del trasporto dell’informazione, il miglior codice è quello che,
mediamente, richiede la trasmissione del minor numero di bit (a parità di informazione).
A tal proposito si evidenzia la possibilità di poter far uso di codici a lunghezza fissa o variabile.
Nel primo caso, le parole del codice sono tutte costituite dallo stesso numero di bit mentre nel secondo
caso le parole sono costituite da un numero differente di bit.
-
Si dice lunghezza della parola li il numero di bit usati per definire quella parola del codice.
Si dice lunghezza media di un codice la quantità:
N
L = ∑ p ( xi ) ⋅ li
bit/parola
i =1
Per un codice efficiente a lunghezza fissa si ha che:
L = 1 + INT [log 2 ( N − 1)]
In un codice numerico, nel quale i simboli sono le dieci cifre decimali, si ha che:
N = 10 ed L = 4 bit/parola - Ogni parola sarà quindi costituita da quattro bit.
Il problema della lunghezza fissa o variabile è fondamentalmente legato alla probabilità di ricorrenza
degli N simboli generati dalla sorgente di informazione. Infatti, se la sorgente emette simboli non
equiprobabili sarebbe più conveniente associare ai simboli più probabili delle parole con lunghezza
inferiore riducendo così la lunghezza media delle stringhe da trasmettere ed il relativo tempo di
trasmissione.
Vale quindi il seguente criterio:
-
Per sorgenti equiprobabili, è più conveniente l’uso di codici a lunghezze fissa mentre per
sorgenti non equiprobabili è più opportuno l’uso di codici a lunghezza variabile.
A.C. Neve – L’informazione digitale
19
Al fine di poter valutare numericamente la convenienza di una codifica a lunghezza variabile si
definisce il coefficiente di efficienza η come:
N
η=
H ( x)
=
L
∑ p( x ) ⋅ log
i =1
i
2
 1 


 p ( xi ) 
N
∑ p( x ) ⋅ l
i =1
i
con valori compresi tra 0 ed 1
i
Nell’analisi fin ora condotta non si è ancora affrontato il problema della costruzione di un codice per
una sorgente non equiprobabile. Proviamo quindi a costruire un codice binario per una sorgente di
informazione in grado di emettere quattro diversi simboli x1 ,x2, x3, x4 aventi le seguenti probabilità:
p(x1) = 0,5 p(x2) = 0.25 p(x3) = 0.125 p(x4) = 0.125
si considerino ora i seguenti possibili codici:
Simbolo
x1
x2
x3
x4
Codice 1
Codice 2
Codice 3
Codice 4
Codice 5
Codice 6
p(xi)
0.5
0.25
0.125
0.125
Codice 1 Codice 2 Codice 3 Codice 4 Codice 5 Codice 6
0
0
00
0
0
0
0
1
01
01
10
10
1
00
11
011
110
110
11
11
10
0111
1110
111
L=1.125 L=1.25
L=2
L=1.875 L=1.875 L=1.75
Non è un codice distinto in quanto i simboli x1 e x2 vengono entrambi codificati con 0 per
cui in ricezione la decodifica risulterebbe ambigua.
La lunghezza del codice è pari a 1.125 bit/parola.
E’ un codice distinto ma non univocamente decodificabile infatti:
la sequenza di simboli (x3 x4) viene codificata con la stringa 0011, in ricezione però questa
stringa può essere decodificata come se fosse la sequenza (x3 x4) o (x1 x1 x4) o (x3 x2 x2) o
ancora (x1 x1 x2 x2).
La lunghezza del codice è pari a 1.125 bit/parola.
E’ un codice istantaneamente decodificabile ed a lunghezza fissa.
Dato che ogni parola ha lunghezza 2, ciascuna coppia di bit può essere immediatamente
decodificabile alla sua ricezione.
La lunghezza del codice è pari a 2 bit/parola.
E’ un codice univocamente decodificabile dato che la ricezione di uno 0 indica sempre
l’inizio di una nuova parola.
Questo codice non è però istantaneamente decodificabile perché la fine di una parola non
può essere rilevata se non aspettando l’inizio della successiva.
La lunghezza del codice è pari a 1.875 bit/parola.
Questo codice è istantaneamente decodificabile dato che la ricezione di uno 0 indica
sempre la fine di una parola.
La lunghezza del codice è pari a 1.875 bit/parola.
Anche questo codice è istantaneamente decodificabile ma la sua lunghezza è di 1.75
bit/parola
A.C. Neve – L’informazione digitale
20
Si noti che l’entropia della sorgente usata è pari a:
H(x)=(1/2)*log2(1/0.5)+(1/4)*log2(1/0.25)+(1/8)*log2(1/0.125)+(1/8)*log2(1/0.125) = 1.75 bit/simbolo
e che nessun codice univocamente decodificabile presente in tabella ha una lunghezza minore di 1.75
bit/simbolo.
Questo risultato non è casuale ed è dimostrato dal 1° Teorema di Shannon il quale afferma che gli N
simboli di una sorgente discreta senza memoria non possono essere rappresentati da un codice
istantaneamente decodificabile di lunghezza inferiore all’entropia della sorgente stessa e cioè:
H ( x) ≤ L
da questa relazione si ribadisce che il rapporto H(x)/L (cioè il coefficiente di efficienza) non potrà
essere maggiore di 1 e pertanto il Codice 6 ha la massima efficienza.
Con riferimento alla tabella proposta ed a quanto sostenuto dal teorema di Shannon , si può affermare
che non potrà esistere nessun codice istantaneo più corto del Codice 6 e pertanto è inutile prolungare la
ricerca di un codice più corto.
Si dice prefisso di una parola in codice, una sequenza binaria ottenuta troncando la parola stessa.
Per esempio, i prefissi della parola 0101 sono 0, 01, 010 e 0101.
Un codice univocamente decodificabile è anche istantaneamente decodificabile se nessuna parola del
codice è prefisso di un’altra e cioè se nessuna parola può essere ottenuta aggiungendo cifre binarie ad
un’altra parola. Infatti, si consideri il caso in cui sia stato ricevuto il bit finale di una parola di un
codice univocamente decodificabile. Se questa parola non può essere riconosciuta senza ambiguità è
solo perché questa parola costituisce anche la prima parte di un’altra parola del codice.
E’ infine opportuno citare la diseguaglianza di Kraft per la quale:
Condizione necessaria e sufficiente per l’esistenza di un codice istantaneo relativo ad una sorgente di
N simboli con parole di lunghezza l1, l2, l3, .....lN è che risulti:
N
∑2
− li
≤1
i =1
Si noti che la diseguaglianza di Kraft consente di stabilire se, dato un insieme di parole di una certa
lunghezza, esiste un codice istantaneamente decodificabile con parole di tale lunghezza.
Non fornisce però alcuna informazione sulle sequenze binarie che costituiscono le parole stesse.
Le considerazioni fino ad ora sviluppate hanno fornito le conoscenze teoriche e pratiche riguardanti la
lunghezza del codice istantaneo più breve ma, resta ancore irrisolto il problema della effettiva
costruzione del codice ottimale.
Esiste a tal proposito l’algoritmo di Huffman il quale propone un metodo iterativo per la
determinazione del codice ottimale per una sorgente non equiprobabile.
Si inizia con il suddividere i simboli della sorgente in due gruppi caratterizzati dall’avere somme di
probabilità all’incirca uguali. Si assegna poi il bit 0 al primo gruppo ed il bit 1 al secondo gruppo.
I gruppi ottenuti vengono di nuovo suddivisi in due sottogruppi aventi ancora la somma delle
probabilità all’incirca uguali. Anche ora si assegna il bit zero al primo gruppo ed il bit 1 al secondo
gruppo.
Si procede in questo modo fino all’esaurimento di tutti i simboli.
A.C. Neve – L’informazione digitale
21
Si viene così a determinare un albero la cui percorrenza, attraverso i vari rami, fornisce le parole del
codice associate ai vari simboli.
Si consideri come esempio la seguente sorgente di simboli non equiprobabili:
Simbolo
Probabilità
A
B
C
D
E
F
G
H
0.512 0.128 0.128 0.032 0.128 0.032 0.032 0.008
Con il metodo ora descritto si realizza il seguente albero:
A (0.512)
A
B
C
D
E
F
G
H
0
B (0.128)
0
100
0
BC (0.256)
1
1
0
BCDEFGH (0.488)
C (0.128)
101
E (0.128)
110
0
1 DEFGH (0.232)
D (0.032)
0
11100
DF (0.064)
1
0
1 F (0.032)
DFGH (0.104)
G (0.032)
0
1
11101
11110
GH (0.040)
1
H (0.008)
11111
ottenendo il seguente codice ottimale:
Simbolo
Codice
A
0
B
100
C
101
D
11100
E
110
F
G
H
11101 11110 11111
Si noti che, questo codice non è unico ed una diversa articolazione dell’albero (assegnazione di 0 e 1
oppure di 1 e 0) avrebbe fornito codici differenti ma tutti ottimali.
La lunghezza media di questo codice risulta pari a:
H
L = ∑ p( xi ) ⋅ li = 0.512 ⋅ 1 + 3 ⋅ (0.128 ⋅ 3) + 3 ⋅ (0.032 ⋅ 5) + 0.008 ⋅ 5 = 2.184 bit/parola
i= A
Lo stesso codice, realizzato a lunghezza fissa, avrebbe richiesto tre bit per simbolo con una lunghezza
media pari a 3 bit/parola che è certamente superiore al precedente.
L’entropia associata a questa sorgente risulta pari a:
H
 1  H
 1 
H ( x) = ∑ p ( xi ) ⋅ log 2 
 = ∑ p ( xi ) ⋅ 3.321 ⋅ log10 
 = 2.165 bit/simbolo
i= A
 p ( xi )  i = A
 p ( xi ) 
A.C. Neve – L’informazione digitale
22
Il coefficiente di efficienza risulta infine pari a:
η = H(x)/L = 2.165/2.184 = 99.1%
che è un valore sicuramente buono essendo molto prossimo ad 1.
Per un codice a lunghezza fissa di tre bit si sarebbe invece avuto η = 2.165/3 = 72.1%.
Esempio:
Delle sorgenti proposte, si determini il valore dell’entropia ed un codice ottimizzato.
Sorgente S1 ⇒ N = 5
p(x1) = 0.5 p(x2) = 0.25 p(x3) = 0.125 p(x4) = 0.0625 p(x5) = 0.0625
Sorgente S2 ⇒ N = 4
p(x1) = 0.5 p(x2) = 0.25 p(x3) = 0.1875 p(x4) = 0.0625
Per la prima sorgente S1 si ha che:
5
 1 
H ( x) = ∑ p ( xi ) ⋅ log 2 
 = 1.875 bit/simbolo
i =1
 p ( xi ) 
Un codice ottimale determinato con il metodo di Huffman è il seguente:
x1 (0.5)
x1
x2
x3
x4
x5
0
0
x2 (0.25)
10
0
x3 (0.125)
110
1
0
x2x3x4x5 (0.5)
1 x3x4x5 (0.25)
x4 (0.0625)
0
1110
1
x4x5 (0.125)
1
x5 (0.0625)
1111
La lunghezza media di questo codice è pari a:
5
L = ∑ p ( xi ) ⋅ li = 1.875 bit/parola
i =1
L’efficienza di questo codice è pari a:
η = H(x)/L = 1.875/1.875 = 100%
Codificando questa sorgente con un codice a lunghezza fissa sarebbero stati necessari tre bit per parola
e la lunghezza media del codice sarebbe risultata pari a:
5
L = ∑ p ( xi ) ⋅ li = 3.0 bit/parola
i =1
A.C. Neve – L’informazione digitale
23
con una efficienza del codice pari a:
η = H(x)/L = 1.875/3.0 = 62.5%
Per la seconda sorgente S2 si ha che:
5
 1 
H ( x) = ∑ p ( xi ) ⋅ log 2 
 = 1.702 bit/simbolo
i =1
 p ( xi ) 
Un codice ottimale determinato con il metodo di Huffman è il seguente:
x1 (0.5)
0
0
x1
x2
x3
x4
x2 (0.25)
1
10
0
x3 (0.1875)
x2x3x4 (0.5)
0
110
1 x3x4 (0.25)
1
x4 (0.0625)
111
La lunghezza media di questo codice è pari a:
5
L = ∑ p ( xi ) ⋅ l i = 1.75 bit/parola
i =1
L’efficienza di questo codice è pari a:
η = H(x)/L = 1.702/1.75 = 97.25%
Codificando questa sorgente con un codice a lunghezza fissa sarebbero stati necessari due bit per
parola e la lunghezza media del codice sarebbe risultata pari a:
5
L = ∑ p( xi ) ⋅ l i = 2.0 bit/parola
i =1
con una efficienza del codice pari a:
η = H(x)/L = 1.702/2.0 = 85.1%
Nel caso di sorgenti equiprobabili si ha che:
η=
log 2 N
H ( x)
=
L
1 + INT [log 2 ( N − 1)]
per cui η potrà essere uguale ad 1 solo nel caso in cui il numero N di simboli generati dalla sorgente
risulti pari ad una potenza di 2.
A.C. Neve – L’informazione digitale
24
CODICI
Come si è già detto, si intende per codice un sistema di simboli utilizzati per rappresentare gli elementi
di un insieme.
I codici sono caratterizzati dai simboli utilizzati i quali, aggregati in maniera opportuna, danno origine
alle cosiddette parole del codice.
L’operazione di generazione di queste parole è detta codifica, quella inversa è detta decodifica.
La necessità di poter disporre di un codice deriva dall’esigenza di dover trasmettere, in modo sicuro e
veloce, una certa quantità di informazione da un utilizzatore ad un altro attraverso un supporto fisico
detto mezzo di trasmissione.
Una volta definiti i simboli utilizzati dal codice e gli elementi dell’insieme che si vogliono
rappresentare, è necessario determinare il numero dei simboli che è necessario aggregare tra loro per
poter rappresentare univocamente tutti gli elementi dell’insieme considerato.
Indicando con K il numero dei simboli usati, con N il numero degli elementi dell’insieme da
rappresentare ed n il numero di simboli da aggregare tra loro, si ha che:
se Kn < N il codice è ambiguo
se Kn = N il codice è efficiente
se Kn > N il codice è ridondante
Nell’utilizzo pratico, un codice deve sempre risultare non ambiguo.
Volendo rappresentare 100 diversi oggetti facendo uso di 3 simboli, sarà necessario aggregare i
simboli in stringhe di lunghezza pari almeno a 5.
Volendo rappresentare 64 diversi oggetti facendo uso di 2 simboli, sarà necessario aggregare i simboli
in stringhe di lunghezza pari almeno a 6.
Nel seguito saranno considerati solo codici con K=2 e cioè codici binari e del tipo a lunghezza fissa.
La tecnica di codifica più diffusa è quella per carattere, per ogni simbolo esiste una parola del codice
per cui un messaggio viene codificato convertendo ogni simbolo del messaggio stesso nella
corrispondente parola del codice usato.
Codici numerici
Questi codici sono esclusivamente usati per la rappresentazione di informazioni numeriche.
Affinché un codice numerico possa risultare non ambiguo deve far uso di parole costituite da quattro
bit in quanto 24 > 10, questi codici sono detti BCD (Binary Coded Decimal).
Ricordando che con 4 bit si possono generare 16 diverse configurazioni, un codice BCD potrà essere
ottenuto scegliendo 10 di queste possibili configurazioni ed associandole alle 10 cifre decimali
secondo un ordine ritenuto più conveniente.
Operando in questi termini si ha la possibilità di generare 16!/(16-10)! = 16!/6! = 29059430000
differenti codici.
A.C. Neve – L’informazione digitale
25
Cifra decimale BCD 8421
0
0000
1
0001
2
0010
3
0011
4
0100
5
0101
6
0110
7
0111
8
1000
9
1001
BCD 8421
BCD 2421 Aiken
BCD +7+4-2-1
BCD Eccesso-3
BCD 2421 Aiken
0000
0001
0010
0011
0100
1011
1100
1101
1110
1111
BCD +7+4-2-1 BCD Eccesso-3
0000
0011
0111
0100
0110
0101
0101
0110
0100
0111
1010
1000
1001
1001
1000
1010
1111
1011
1110
1100
Questo codice è il più semplice, immediato ed il più diffuso.
E’ un codice pesato con pesi 8421 per cui coincide con le prime dieci
configurazioni consecutive ottenibili, in binario, con 4 bit.
Esistono ben 64 codici con peso 2421 uno dei quali è quello Aiken. Questo
codice, oltre che essere pesato è anche autocomplementante.
Si dice autocomplementante un codice nel quale il complemento di una
qualsiasi parola genera una configurazione di bit ancora appartenente allo
stesso codice.
Questo è un esempio di codice pesato con pesi positivi e negativi.
Per es., la cifra 5 si ottiene dalla somma +7-2, quella 3 da +4-1 ecc.
Questo è un codice non pesato. Si genera facendo corrispondere alle cifre
decimali, la loro rappresentazione in binario a 4 bit incrementata di 0011 (3).
Questo codice non contiene la configurazione 0000 ed è autocomplementante.
Parametri caratteristici e definizioni
Si dice peso di una configurazione, il numero di bit pari ad 1 presenti in una configurazione.
Si dice distanza tra due configurazioni, il numero di bit per i quali le due configurazioni differiscono o,
equivalentemente, il numero di bit da invertire per passare da una configurazione all’altra.
Si dice distanza di Hamming, la minima distanza tra due qualsiasi configurazioni di un codice.
Tutti i codici BCD hanno distanza di Hamming pari ad 1. Più grande è il valore di questo parametro e
più sicuro risulterà il codice nei confronti di possibili errori.
Si parla di configurazione errata quando, per effetto di una casuale inversione di bit, si verifica che la
parola originaria di un codice si trasforma in una parola non appartenente al codice.
Si intende per molteplicità di errore, la distanza tra la configurazione originaria e quella errata.
Nella pratica coincide con il numero di bit invertiti a causa di un errore.
Si può definire la ridondanza di un codice considerando ridondante un codice che utilizza un numero
di bit (e non di configurazioni) M = N + k superiore a quello strettamente necessario per rappresentare,
in modo non ambiguo, tutti gli N elementi dell’insieme considerato.
Alla luce di queste considerazioni, tutti i codici BCD risultano efficienti.
I k bit in più sono detti bit di controllo.
Si può quindi definire il grado di ridondanza di un codice come il rapporto M/N.
A.C. Neve – L’informazione digitale
26
Codici con 5 o più di 5 bit
Cifra decimale
0
1
2
3
4
5
6
7
8
9
2 su 5
51111
Shift counter
(Johnson)
Biquinario
Ring counter
2 su 5
00110
00011
00101
01001
01010
01100
10001
10010
10100
11000
51111
00000
00001
00011
00111
01111
10000
11000
11100
11110
11111
Shift counter
00000
00001
00011
00111
01111
11111
11110
11100
11000
10000
Biquinario
01 00001
01 00010
01 00100
01 01000
01 10000
10 00001
10 00010
10 00100
10 01000
10 10000
Ring counter
0000000001
0000000010
0000000100
0000001000
0000010000
0000100000
0001000000
0010000000
0100000000
1000000000
Questo è un codice a 5 bit le cui configurazioni hanno peso costante e pari a 2
infatti, in ogni parola sono presenti sempre e soltanto due bit pari ad 1.
Questa tecnica rende più semplice la rilevazione di eventuali errori.
Questo codice ha distanza di Hamming pari a 2. Non è un codice pesato.
Questo è un codice a 5 bit pesato con pesi pari a 5 1 1 1 1.
Risulta autocomplementante e con distanza di Hamming pari ad 1.
Questo è un codice a 5 bit non pesato con distanza di Hamming pari ad 1.
Si noti che le varie configurazioni vengono generate dallo scorrimento da destra a
sinistra di cinque bit pari ad 1 (tipico del contatore Johnson).
Questo è un codice pesato a 7 bit nel quale tutte le parole hanno peso costante pari a
2, questa caratteristica consente una più facile individuazione di eventuali errori.
I 7 bit di questo codice possono essere considerati appartenenti a due gruppi
separati, il primo da 2 bit con pesi 5 e 0 ed il secondo da cinque bit con pesi 43210.
In ciascuno di questi due gruppi vi è sempre e soltanto un solo bit pari ad 1.
La distanza di Hamming è pari a 2.
Questo è un codice pesato a 10 bit con pesi 9876543210.
La distanza di Hamming è pari a 2 e le sue parole hanno peso costante pari ad 1.
Nonostante questo codice risulti fortemente ridondante, esso è particolarmente
sicuro nei confronti di possibili errori.
Esempi:
3740 in base 10 equivale a:
0011 0111 0100 0000
0011 1101 0100 0000
0110 1010 0111 0011
01001 10010 01010 00110
0101000 1000100 0110000 0100001
A.C. Neve – L’informazione digitale
in codice BCD 8421
in codice BCD 2421 Aiken
in codice Eccesso-3
in codice 2 su 5
in codice Biquinario
27
Codice Gray
Cifra decimale G3 G2 G1 G0
0
0
0
0
0
1
0
0
0
1
2
0
0
1
1
3
0
0
1
0
4
0
1
1
0
5
0
1
1
1
6
0
1
0
1
7
0
1
0
0
8
1
1
0
0
9
1
1
0
1
10
1
1
1
1
11
1
1
1
0
12
1
0
1
0
13
1
0
1
1
14
1
0
0
1
15
1
0
0
0
Il codice di Gray è un codice non pesato e, fondamentalmente,
non è un codice BCD per cui non usa la codifica per carattere.
Ogni configurazione è pertanto individualizzata come accade
nella rappresentazione dei numeri in binario puro.
In un codice Gray, l’ordine delle varie configurazioni è tale che
la generica configurazione ha distanza 1 dalla successiva e dalla
precedente come pure l’ultima ha distanza 1 dalla prima. Per tali
proprietà questo codice è detto monoprogressivo e ciclico.
Nella figura sono circoscritti i codici di Gray a 1, 2, 3 e 4 bit.
Un codice di Gray ad n bit può essere costruito da quello ad n-1
bit semplicemente ribaltando specularmente il codice ad n-1 bit
e premettendo uno 0 alle prime 2n-1 configurazioni ed un 1 alle
successive 2n-1. Per questa caratteristica il codice di Gray è
anche detto riflessivo.
Il codice di Gray è molto utilizzato nei circuiti combinatori che non possono tollerare la commutazione
contemporanea di due o più bit. La commutazione contemporanea di più bit non può mai essere
ottenuta nei circuiti reali in quanto, vi sarà sempre un bit che commuta prima di tutti gli altri ed un
altro che commuterà per ultimo. Il caso più semplice è quello di una porta OR i cui ingressi devono
commutare dalla configurazione 01 a quella 10 lasciando l’uscita inalterata al valore 1. Non risultando
la commutazione istantanea, si ha che gli ingressi potranno avere le seguenti evoluzioni: 01 Î 11 Î
10 oppure 01 Î 00 Î 10 a secondo che sia più veloce a commutare il primo bit o il secondo.
Nel primo caso non ci sono problemi in quanto l’uscita resta fissa sul valore 1, nel secondo caso invece
l’uscita va a 0 per un brevissimo intervallo di tempo per poi ritornare subito ad 1, viene così a
generarsi un piccolo impulso la cui durata è pari alla differenza tra i due tempi di commutazione che
può risultare estremamente pericoloso e di difficilissima rilevazione a causa della breve durata.
Questi tipi di impulsi sono detti alee statiche. Il loro modo di verificarsi è imprevedibile in quanto
dipendente sia dalla temperatura che dalle tolleranze di produzione.
La conversione da Gray in Binario puro si effettua nel seguente modo:
si inizia dal bit all’estrema sinistra, i bit del numero binario saranno gli stessi del codice
Gray fino al primo 1 compreso, per le altre cifre si ha che:
se il bit Gray è pari ad 1, la corrispondente cifra binaria si ottiene complementando la
precedente, se invece è pari a 0, coincide con la precedente.
0 1 0 1 Gray
0 1 1 0 Binario puro
1 0 1 0 1 1 0 0 1 1 1 Gray
1 1 0 0 1 0 0 0 1 0 1 Binario puro
A.C. Neve – L’informazione digitale
28
La conversione da Binario puro in Gray si effettua invece nel seguente modo:
a partire dal bit all’estrema sinistra, si confrontano i bit a coppie successive, se tali bit
sono uguali, il bit in Gray sarà pari a 0, se invece sono differenti il bit Gray sarà pari ad
1. Il confronto del primo bit avverrà sempre con lo 0.
0 1 1 1 Binario puro
0 1 0 0 Gray
1 1 0 1 0 0 1 Binario puro
1 0 1 1 1 0 1 Gray
Cifra decimale
0
1
2
3
4
5
6
7
8
9
Gray BCD
0000
0001
0011
0010
0110
1110
1010
1011
1001
1000
E’ anche possibile realizzare un codice Gray di tipo BCD che
consenta la codifica per carattere.
Questo codice, oltre a disporre di solo dieci configurazioni, dovrà
rispettare le tipiche caratteristiche del vero codice Gray, dovrà
pertanto risultare monoprogressivo, ciclico e riflessivo.
Un esempio può essere quello proposto nella tabella seguente.
Codici alfanumerici
I codici fin ora esaminati vengono utilizzati per la gestione di informazioni puramente numeriche.
Nella maggior parte delle applicazioni vi è invece la necessità di dover gestire informazioni nel senso
più generale del termine e cioè informazione caratterizzata oltre che da simboli numerici, anche da
lettere dell’alfabeto maiuscole e minuscole, vari segni di interpunzione e, soprattutto, caratteri per il
controllo della comunicazione.
Il codice più diffuso per il trattamento dell’informazione alfanumerica è il codice ASCII (American
Standard Code for Information Interchange), questo è un codice a 7 bit che consente la
rappresentazione di 128 simboli. Nei sistemi di elaborazione digitali, l’informazione è impacchettata in
blocchi elementari da 8 bit (byte) per cui l’ottavo bit resta disponibile per l’utilizzo come bit di parità o
per l’ampliamento del codice a 256 simboli (ASCII esteso).
Un altro codice molto diffuso è il codice EBCDIC (Extended Binary Coded Decimal Interchange
Code), questo è un codice ad 8 bit che consente la rappresentazione di 256 simboli.
A.C. Neve – L’informazione digitale
29
ACK
BEL
BS
CAN
CR
DC1
DC2
DC3
DC4
DEL
DLE
EM
ESC
ENQ
EOT
ETB
ETX
FF
FS
GS
HT
LF
NAK
NUL
RS
SI
SO
SOH
SP
STX
SUB
SYN
US
VT
Acknowledge
Bell
Backspace
Cancel
Carriage return
Device control 1
Device control 2
Device control 3
Device control 4
Delete
Data link espace
End of medium
Escape
Enquiry
End of trasmission
End of trasmission block
End of text
Formed feed
File separator
Group separator
Horizontal tabulation
Line feed
Negative acknowledge
Null
Record separator
Shift in
Shift out
Start of heading
Space
Start of text
Substitute
Synchronous
Unit separator
Vertical tabulation
000
0000 NUL
0001 SOH
0010 STX
0011 ETX
0100 EOT
0101 ENQ
0110 ACK
0111 BEL
1000 BS
1001 HT
1010 LF
1011 VT
1100 FF
1101 CR
1110 SO
SI
1111
001
010
011
100
101
DLE
DC1
DC2
DC3
DC4
NAK
SYN
ETB
CAN
EM
SUB
ESC
FS
GS
RS
US
SP
!
“
#
$
%
&
‘
(
)
*
+
,
.
/
0
1
2
3
4
5
6
7
8
9
:
;
<
=
>
?
@
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
[
\
]
^
_
110
111
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
r
s
t
u
v
w
x
y
z
{
|
}
~
DEL
Codice ASCII
I tre bit delle colonne sono i più
significativi (b6b5b4).
I quattro bit delle righe sono i meno
significativi (b3b2b1b0)
I caratteri del codice che iniziano con 00 (cioè quelli delle prime due colonne) sono detti caratteri di
controllo e sono di ausilio alle apparecchiature che utilizzano il codice ASCII.
Questi caratteri si possono dividere in quattro tipologie:
1) Controllo di trasmissione: questi caratteri servono per definire la struttura del messaggio e sono
in parte correlati al gestore del protocollo.
2) Controllo di stampa: questi caratteri servono a posizionare correttamente il testo sul sistema di
visualizzazione (ritorno carrello CR, salto linea LF ecc.).
3) Controllo blocco dati: vengono usati per la gestione di grandi quantità di dati organizzati in file
o record.
4) Controllo dei dispositivi: sono utilizzati per il controllo e gestione di dispositivi o di loro
particolari funzionalità.
Struttura del messaggio:
0000001 intestazione 0000010
SOH
STX
Testo del messaggio
0000011
ETX
L’espressione - Oggi 12 marzo 2000 - viene così codificata:
O g g
i
1 2
m a r
z o
2 0 0 0
4F 67 67 6C 20 31 32 20 6D 61 72 7A 6F 20 32 30 30 30
La sequenza di caratteri è stata rappresentata in esadecimale solo per comodità.
A.C. Neve – L’informazione digitale
30
Aritmetica BCD 8421
In alcune applicazioni è spesso necessario eseguire delle operazioni aritmetiche tra numeri espressi in
codice BCD 8421. E’ opportuno tener presente che, in questo codice, risultano assenti le ultime 6
configurazioni binarie (1010, 1011, 1100, 1101, 1110 e 1111).
Effettuando la somma tra numeri BCD, se il risultato ricade in una di queste ultime configurazioni si
dovrà apportare, a queste configurazioni, una correzione che consiste nell’aggiungere un valore pari a
6 = 0110 al valore ottenuto e, facendo propagare il riporto nel modo opportuno.
525 + 311 = 836
0101 0010 0101 +
0011 0001 0001 =
1000 0011 0110
che risulta corretto
649 + 853 = 1502
0110 0100 1001 +
1000 0101 0011 =
1110 1001 1100 +
0110
0110 =
0001 0100 1010 0010 +
0110
=
0001 0101 0000 0010
che risulta errato nella prima ed ultima cifra
che risulta nuovamente errato nella terza cifra
Si consideri ora questo nuovo esempio:
94 + 94 = 188
1001 0100 +
1001 0100 =
0001 0010 1000 +
0110
=
0001 1000 1000
che sembrerebbe essere corretto in quanto composto tutto da parole BCD8421
si nota però che il risultato,128, è certamente errato nella seconda cifra.
Anche in questo caso è necessario operare un aggiustamento.
Si renderà pertanto necessario l’aggiustamento quando:
1) la somma delle due cifre risulta maggiore di 9 e minore di F
2) vi è un riporto cioè quando la somma delle due cifre è maggiore di F
Si fa notare che i due casi si verificano quando vi è il classico riporto decimale.
A.C. Neve – L’informazione digitale
31
Considerazioni applicative
Il massimo valore esprimibile con 4 cifre BCD 8421 risulta pari a:
1001 1001 1001 1001 = 999910
come si può osservare sono stati utilizzati 16 bit per contare fino a 999910
Si fa notare che, nel sistema di numerazione binario puro, con 16 bit si sarebbe ottenuto il seguente
valore:
11111111111111112 = 6553510
Si può così constatare una elevata mancanza di efficienza nell’uso del codice BCD rispetto al classico
sistema di numerazione, che però è ampiamente compensata dalla semplificazione ed invariabilità
dell’hardware usato per i collegamenti.
Convertitori di codice
I convertitori di codice sono dei circuiti combinatori che accettano in ingresso una configurazione di
bit appartenente ad un certo codice e, forniscono in uscita la corrispondente configurazione espressa in
un altro codice.
A.C. Neve – L’informazione digitale
32
Codici a controllo d’errore
Durante lo scambio di informazioni tra due unità, fenomeni di disturbo, possono determinare il
verificarsi di errori nelle stringhe di bit utilizzate per rappresentare l’informazione stessa, è pertanto
evidente la necessita di strumenti e tecniche che consentano la rivelazione ed eventualmente anche la
correzione di questi errori.
Sorgente
Codificatore
TX
RX
Mezzo di trasmissione
Decodificatore
Utente
La tecnica più elementare per il controllo degli errori è la parità semplice, questa consiste
nell’aggiungere alla parola del codice un bit in modo tale da rendere pari (o dispari ) il numero
complessivo di 1 presenti nella configurazione, si definisce così la parità pari ( o parità dispari ).
Il trasmettitore ha pertanto il compito di assemblare la stringa unendo al carattere la relativa parità e
trasmettere il tutto.
Il ricevitore ha invece il compito di prelevare la stringa di bit, esaminare il carattere, determinare il
valore della parità e confrontarla con quella ricevuta, se coincidono la trasmissione è stata corretta
altrimenti è evidente che si è verificato un errore.
Considerato il carattere ASCII corrispondente alla vocale E, si ha che:
P
1
0
0
0
1
0
1
essendo presenti nel carattere 3 bit pari ad 1, il valore del bit di parità dovrà essere uguale ad 1 se si
usa la parità pari ( altrimenti 0 se si usa la parità dispari).
Si supponga ora che al ricevitore pervenga la stringa seguente:
1
1
0
1 0 1 0 1
essendo presenti nei primi sette bit quattro uno ci si aspetta un bit di parità pari uguale a 0, risultando
invece il bit di parità uguale ad 1 è evidente la presenza di un errore che non può essere però
individuato e corretto.
La parità semplice consente quindi il solo rilevamento di errori di molteplicità dispari e non la
correzione.
Si fa notare che in caso di errore doppio, cioè di molteplicità due, il controllo di parità non rileva
errori.
Questa tecnica di controllo è valida quando il canale di trasmissione ha un tasso di errore contenuto,
nel caso di trasmissione che utilizzi il codice ASCII la probabilità di errore tollerabile è di 1/8 = 0.125.
A.C. Neve – L’informazione digitale
33
Un salto di qualità può essere ottenuto facendo uso della parità incrociata, organizzando i caratteri da
trasmettere in gruppi di dimensione fissa ordinati secondo una matrice e inserendo la parità sia per
righe che per colonne. Nell’esempio seguente si utilizzano otto caratteri del codice BCD 8421.
Trasmesso
1 1 0
0 0 0
1 0 1
1 0 1
0 1 0
0 0 1
0 0 0
0 0 0
1 0 1
Ricevuto
1 1 0
0 0 0
1 0 1
1 0 1
0 1 0
0 0 1
0 0 0
0 0 0
1 0 1
0
1
1
0
0
1
0
1
0
0
1
1
0
1
0
0
1
0
0
1
1
0
1
1
0
1
0
0
1
0
1
0
1
0
1
0
Come si può osservare dalla tabella di trasmissione, verranno trasmessi N+1
caratteri comprensivi della propria parità.
Si ipotizzi ora che durante la trasmissione si verifichi un errore relativo all’1 in
grassetto, in questo caso si noterà un errore di parità nella quarta riga ed uno
nella seconda colonna, l’incrocio della riga e colonna interessati individuano il
bit errato che potrà così essere corretto.
Questa tecnica consente anche la rilevazione, ma non la correzione, di errori di
molteplicità due
1
0
1
1
0
0
0
0
1
1
0
0
0
1
0
0
0
0
0
0
1
1
0
1
1
1
1 0
1
0
0
1
1
0
1
0
In questa figura si può notare un errore doppio, la
parità risulta quindi errata sia sulla quarta e
quinta riga che sulla seconda e terza colonna, non
è quindi possibile effettuare la correzione
dell’errore ma solo la sua rilevazione.
0
1
1
0
1
0
0
1
0
Un altro metodo per il controllo degli errori è la codifica Hamming.
Questo codice viene implementato aggiungendo, agli n bit di un qualsiasi codice efficiente, K bit di
controllo ognuno dei quali verifica la parità di un gruppo degli M = n + K bit complessivi.
Il primo passo consiste nel determinare il numero K di bit che dovranno essere aggiunti a quelli del
codice. Dovrà risultare che :
⇒
2K -1 ≥ M = n + K
2K -1 -K ≥ n
si noti che con questo valore di K è possibile l’identificazione di tutti gli M bit della nuova parola.
Per codici aventi n = 2,3,4 si ottiene K = 3
Per codici aventi n = 5,6,7,8,9,10,11 si ottiene K = 4
Nella stringa binaria complessiva i bit Ki vengono inseriti nelle posizioni 1,2,4 per codici con n fino a
4 mentre vengono inseriti nelle posizioni 1,2,4,8, per codici con n fino a 11.
Regola generale:
Per rilevare N errori è necessario un codice con distanza di Hamming pari a N+1
Per correggere N errori è necessario un codice con distanza di Hamming pari a 2N+1
A.C. Neve – L’informazione digitale
34
Per codici con n = 4 la stringa di bit risulta la seguente:
7
n3
6
n2
5
4
n1 K3
3
2
n0 K2
1
k1
K1 rappresenta la parità per i bit (1,3,5,7,)
K2 rappresenta la parità per i bit (2,3,6,7,)
K3 rappresenta la parità per i bit (4,5,6,7,)
Per codici con n = 5 ..... 11 la stringa di bit risulta la seguente:
15
n10
14
n9
13
n8
12
n7
11
n6
10
n5
9
8
n4 K4
7
n3
6
n2
5
4
n1 K3
3
2
n0 K2
1
K1
K1 rappresenta la parità per i bit (1,3,5,7,9,11,13,15,)
K2 rappresenta la parità per i bit (2,3,6,7,10,11,14,15)
K3 rappresenta la parità per i bit (4,5,6,7,12,13,14,15,)
K4 rappresenta la parità per i bit (8,9,10,11,12,13,14,15)
In fase di ricezione si rigenerano i valori dei bit Ki relativi alla stringa ricevuta.
Se tutti i bit Ki risultano nulli, la trasmissione è stata corretta, altrimenti il valore ottenuto dalla stringa
dei vari Ki ordinati per indice decrescente, rappresenta in binario l’indice del bit nel quale si è
verificato l’errore.
Esempio:
TX
7
1
6
0
5
0
4
3
1
2
1
K3 = 1 K2 = 0 K1 = 0
Ipotizzando un errore sul bit 6, la stringa ricevuta risulta la seguente:
RX
7
1
6
1
5
0
4
1
3
1
2
0
1
0
In questo caso si ottiene:
K3 = 1 K2 = 1 K1 = 0
da cui K3,K2,K1 = 1102 = 610
individuando così l’errore sul bit numero 6.
A.C. Neve – L’informazione digitale
35
I codici autocorretivi tipo Hamming sono in grado di rilevare un alto tasso di errori solo se i bit errati
sono distribuiti in modo casuale lungo tutto il messaggio per cui, il loro uso è limitato ad applicazioni
su brevissime distanze come nel caso di scambio dati tra microprocessore e memorie.
Nelle trasmissioni su distanze maggiori, i disturbi hanno, generalmente, una durata molto superiore a
quella del singolo bit per cui uno di questi disturbi è in grado di distruggere diversi bit contigui, questo
fenomeno è detto errore a raffica (burst error).
In questi casi i codici autocorrettivi sono del tutto inadeguati.
La tecnica più utilizzata in queste situazioni fa uso dei codici polinomiali o ciclici (CRC Cyclic
Redundant Check). Questa tecnica consiste nell’aggiungere, in coda ai bit costituenti il messaggio, una
serie di bit opportunamente calcolati.
Un messaggio M(x) di N bit viene considerato come un polinomio di grado N+1 i cui coefficienti sono
i bit del messaggio stesso.
Su questo polinomio saranno poi effettuate delle operazioni in aritmetica modulo-2.
Sia il trasmettitore che il ricevitore utilizzano uno stesso polinomio G(x) di grado r, il trasmettitore per
calcolare ed aggiungere al messaggio i bit di controllo, il ricevitore per verificare la correttezza del
messaggio. Nel caso in cui il messaggio risultasse errato, il ricevitore invierà poi una richiesta di
ritrasmissione del messaggio stesso.
Il polinomio G(x) dovrà sempre avere il termine di grado 0 cioè l’ultimo bit dovrà essere pari ad 1.
La tecnica del CRC consiste nell’aggiungere al messaggio M(x), formato da N bit, un messaggio di
controllo R(x) formato da r bit (con r < N) in modo da ottenere un nuovo messaggio T(x) formato da
N+r bit che risulti divisibile per G(x).
I più diffusi polinomi generatore G(x) sono:
CRC-16
= x16 + x15 + x2 + 1 = 1 1000 0000 0000 0101
CRC-CCITT = x16 + x12 + x5 + 1 = 1 0001 0000 0010 0001
Questi codici sono in grado di rilevare:
-
tutti gli errori singoli e doppi
tutti gli errori di molteplicità dispari
tutti gli errori burst di lunghezza massima 16
il 99,997% degli errori burst di lunghezza 17
il 99,998% degli errori burst di lunghezza 18
Nel campo delle applicazioni dove è richiesta una precisione quasi assoluta (99,99999998%), si usano
polinomi generatori a 32 bit del tipo:
CRC-32 = x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x1 +1
A.C. Neve – L’informazione digitale
36
L’algoritmo per il calcolo del messaggio composto T(x) è il seguente:
1) Se r è il grado del polinomio G(x), si aggiungono r bit pari a 0 nelle posizioni meno
significative di M(x) ottenendo un nuovo polinomio M’(x) di grado N+r. Tutto ciò equivale a
moltiplicare M(x) per xr.
2) Si divide il polinomio M’(x) per il polinomio G(x) usando l’aritmetica modulo-2.
(Nell’aritmetica modulo-2 l’addizione o sottrazione tra bit omologhi si può interpretare come
una operazione di XOR)
3) Il resto R(x) della divisione sarà poi sommato al polinomio M’(x) per ottenere il blocco T(x).
Il controllo in ricezione si effettua dividendo il polinomio T(x) ricevuto per il polinomio generatore
G(x), se il resto è nullo la trasmissione è stata corretta, in caso contrario vi sono stati degli errori e si
dovrà chiedere la ritrasmissione del messaggio.
Esempio:
Si consideri il messaggio M(x) = 1100101101101
ed il polinomio generatore G(x) = x4 + x1 + 1 = 10011.
Determinare il polinomio T(x).
M’(x)
=
1 1 0 0 1 0 1 1 0 1 1 0 1 0 0 0 0
1 1 0 0
1 0 0 1
- 1 0 1
1 0 0
- - 1
1
-
1
1
0
1
1
0
1
1
-
0 1 1 0 1 1 0 1 0 0 0 0 : 1 0 0 1 1
x x x x x
0
1
1 1 1
0 1 1
1 0 0 0
0 0 1 1
1 0 1 1 1
1 0 0 1 1
- - 1 0 0 1 0
1 0 0 1 1
- - - - 1 1 0 0 0
1 0 0 1 1
- 1 0 1 1 0
1 0 0 1 1
- - 1 0 1
R e s t o
Dove xxxxx è il quoziente che però non interessa
il polinomio T(x) risulterà quindi:
T(x)
=
1 1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1
A.C. Neve – L’informazione digitale
37
In fase di ricezione si effettuerà la divisione di T(x) sempre per il polinomio generatore G(x):
1 1 0 0
1 0 0 1
- 1 0 1
1 0 0
- - 1
1
-
1
1
0
1
1
0
1
1
-
0 1 1 0 1 1 0 1 0 1 0 1 : 1 0 0 1 1
x x x x x
0
1
1 1 1
0 1 1
1 0 0 0
0 0 1 1
1 0 1 1 1
1 0 0 1 1
- - 1 0 0 1 0
1 0 0 1 1
- - - - 1 1 0 1 0
1 0 0 1 1
- 1 0 0 1 1
1 0 0 1 1
R e s t o
0 0 0 0 0
Come si può notare, essendo il resto nullo, la trasmissione è corretta.
A.C. Neve – L’informazione digitale
38