I codici

Codice (C): insieme di simboli (alfabeto) e di regole per generare parole che rappresentano gli elementi di un altro insieme di entità (C’).

Esempi

Simboli di C	Parole di C	Entità di C’	
Cifre decimali
(0, 1, 2, …,9)	Numeri naturali
(p.e.: 12)	I  I  I  I  I  I  I
I  I  I  I  I  I  I	
Bit
(0,1)	Stringhe di 4 bit
(p.e.: 1100)	Numero intero
compreso tra 0 e 15
(p.e.: “12”)	
Lettere 
dell’alfabeto 
italiano
(a,b, …, z)	Parole italiane
(p.e.: dodici)	I  I  I  I  I  I  I
I  I  I  I  I  I  I	

Codifica: operazione per cui una parola di C viene associato un elemento di C’.

Decodifica: operazione per cui un elemento di C’ corrisponde ad una parola di C. 

Codice non ambiguo: codice in cui la corrispondenza tra le parole di C e gli elementi di C' è univoca.

Se si indica con

b: il numero di simboli differenti usati per identificare le parole di C (nel caso di uso di un sistema di numerazione, b identifica la sua base);

n: la lunghezza (costante) delle parole di C;

m: il minimo valore di n che rende non ambiguo il codice C per codificare gli elementi di C’;

N = |C’|

allora 				bm   = N

Un codice si dice:

irridondante se 			n = m

ridondante se 				n > m

ambiguo se 				n < m

DISTANZA DI HAMMING

Si definisce distanza di Hamming h di un codice il numero minimo di bit di cui differiscono due qualsiasi parole del codice

codici irridondanti			h = 1

codici ridondanti			h = 1

codici ambigui				h = 0

Esempi di codifiche

Parole di 
C 	Prima 
codifica	Seconda
codifica	Terza
codifica	Quarta
codifica	Quinta
codifica	
alfa	000	0000	00	0000	110000	
beta	001	0001	01	0011	100011	
gamma	010	0010	11	0101	001101	
delta	011	0011	10	0110	010110	
mu	100	0100	00	1001	011011	

  		Non 		Non		    Ambiguo	Non		Non
ambiguo	ambiguo				ambiguo	ambiguo

		Irridondante	Ridondante				Ridondante	Ridondante

Distanza
di 		1		1			0		2		3
Hamming
                                                                                                  Si può	         Si può
                                                                                                  rivelare              rivelare
                                                                                                  un errore            e
										          correggere
										           un errore

Codice BCD (Binary Coded Decimal)

CIFRA	BCD	
0
1
2
3
4
5
6
7
8
9	0000
0001
0010
0011
0100
0101
0110
0111
1000
1001	

Esempio

(325)10      =     (0011   0010   0101)BCD

Codice ASCII

Inserire tabella

Codici a rivelazione e a correzione di errore

Qui mettere figura

Codici di parita’/disparita’

Data una parola del codice di partenza, che utilizza il sistema di numerazione binario, si aggiunge un 1 per avere un numero di bit pari/dispari.

Esempio

		codice				codice		codice
		irridondante			parita’		disparita’

A		000					0000			0001
B		001					0011			0010
C		010					0101			0100
D		011					0110			0111
E		100					1001			1000
F		101					1010			1011
G		110					1100			1101
H		111					1111			1110

Distanza
di Hamming
		h = 1					h = 2			h = 2

Codici di Hamming
Sono codici con h>2, il più usato è quello con 

h =3  R=2 oppure R=1 e C=1

Esempio: si abbia un codice irridondante con 4 bit
allora codice di Hamming con h =3 è uguale a:

P1 P2 X3 P4 X5 X6 X7

Dove:
I.	X3, X5, X6, X7 rappresentano i 4 bit del codice irridondante
II.	P1 controlla bit di parità dei bit in posizione 3, 5, 7
III.	P2 controlla bit di parità dei bit in posizione 3, 6, 7
IV.	P3 controlla bit di parità dei bit in posizione 5, 6, 7

Notare che 

I.	P1 controlla la parità dei bit la cui posizione, codificata in binario, presenta un 1 nel bit di posizione 1 (20)

II.	P2 controlla la parità dei bit la cui posizione, codificata in binario, presenta un 1 nel bit di posizione 2 (21)

III.	P4 controlla la parità dei bit la cui posizione, codificata in binario, presenta un 1 nel bit di posizione 4 (22)

Esempio di codifica di 1011

X3=1  X5=0  X6=1  X7=1

Codice di Hamming 

P1=0  P2=1  X3=1  P4=0  X5=0  X6=1  X7=1

I codici di Hamming vengono  utilizzati per la  memorizzazione o trasmissione dei dati.

Esempi di errore della trasmissione della codifica

0  1  1  0  0  1  1

in ricezione si generano i bit:

C1 = 0 se i bit di parità dei bit P1, X3, X5, X7 sono in numero pari
C2 = 0 se i bit di parità dei bit P2, X3, X6, X7 sono in numero pari
C4 = 0 se i bit di parità dei bit P4, X5, X6, X7 sono in numero pari

Un errore sul primo bit:
1  1  1  0  0  1  1
allora
C1 = 1 
C2 = 0 
C4 = 0 

Un errore sul terzo bit:
0  1  0  0  0  1  1
allora
C1 = 1 
C2 = 1 
C4 = 0 

Un errore sul  sesto bit

0  1  1  0  0  0  1
allora
C1 = 0 
C2 = 1 
C4 = 1 

Notare che leggendo la codifica C4C2C1 in binario essa indica la posizione del bit errato (e quindi da invertire)