Appunti Fondamenri di Informartica teoria - sistemi di codifica

Sistemi di codifica

Rappresentazione di dati numerici

Codifica binaria

Utilizza sequenze di bit per rappresentare i numeri in base 2.

Limiti della rappresentazione binaria di numeri

• Overflow: si verifica quando un valore rappresentato in complemento a 2 è troppo grande per essere rappresentato con il numero di bit disponibile.
• Troncamento: si verifica quando un valore non può essere rappresentato accuratamente (numero di cifre dedicate alla mantissa).

Codice binario

• Programmazione: con "codice binario" si intende come "codice eseguibile da un processore", ovvero si riferisce a un programma scritto in linguaggio macchina.
• Rappresentazione dei dati numerici: "codice binario" si può riferire a un modo di rappresentazione di numeri interi corrispondente al sistema numerico binario o a un sistema derivato (per esempio la rappresentazione in complemento a 2).
• Rappresentazione di informazioni non numeriche: "codice binario" che utilizza stringhe di un alfabeto composto da due soli simboli (zero e uno) per rappresentare qualunque informazione (caratteri, segnali, immagini, ecc.).

Codifica di dati non numerici: definizioni

I calcolatori lavorano soltanto con i numeri, ma devono poter trattare anche altre entità, per questa ragione sono stati inventati i codici.

• Alfabeto: insieme finito di simboli (caratteri) distinti.
• Parola o stringa: sequenza finita di simboli.

Esempi

Alfabeti usati dall'uomo

• {A, B, C, D, …, Z}
• {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
• { ; , . ! ? : ( ) ‘ “... }
• {Caratteri giapponesi}
• {Caratteri arabi}

È necessario stabilire delle regole di corrispondenza tra simboli di un alfabeto e stringhe di simboli di un altro, dette codifiche. La codifica metterà in corrispondenza biunivoca ogni simbolo appartenente all’alfabeto più ricco con una stringa di simboli appartenenti all’alfabeto più ridotto.

Codifica: definizione

Dato un insieme di elementi (alfabeto da codificare), si dice codifica degli elementi mediante parole (o stringhe) di un alfabeto un procedimento che permette di stabilire una corrispondenza biunivoca tra gli elementi e un sottoinsieme dell’insieme delle parole (o stringhe).

Codifica: esempio

Alfabeto da codificare: lettere alfabeto ‘A’, ‘B’, …, ‘Z’.

• Alfabeto utilizzato per la codifica: cifre decimali 0, 1, …, 9 = {‘A’, ‘B’, ‘C’, …, ‘Z’} = {0, 1, 2, …, 9}, = {01, 02,…, 26}

Possibile codifica di lettere dell’alfabeto tramite parole o stringhe composte da cifre decimali

• ‘A’ > 01
• ‘B’ > 02
• ‘C’ > 03
• ‘D’ > 04 …
• ‘Z’ > 26

Codice binario

Un codice binario è la codifica dei simboli di un alfabeto mediante stringhe di bit. Si utilizza per rappresentare in forma digitale (tramite numeri) informazioni non numeriche. L’alfabeto utilizzato è binario costituito dai simboli ‘0’ e ‘1’.

Codici binari: definizione

Se C è la cardinalità (n. di elementi), il numero n di bit da utilizzare per codificare tutti i simboli deve essere tale che:

• Se n = M, il codice è non ridondante (usa il minimo numero di bit per codificare tutti i simboli).
• Se n > M, il codice è ridondante (usa più bit del necessario per codificare tutti i simboli).

Codici binari esempi: distanza di Hamming tra due stringhe

Date due parole della stessa lunghezza, si definisce distanza di Hamming (H) il numero di bit differenti che compaiono nelle due parole in posizioni corrispondenti.

Esempio:

• S1 = 0000000000
• S2 = 0000011111
• H = 5

Distanza di Hamming

Si definisce distanza di Hamming (H) di un codice: il minimo numero di bit di cui differiscono due parole qualsiasi del codice.

Esempi

Non è vero che se n > M allora H > 1.

• Alfabeto = {A, B, C}. Quanto vale M?
• Codice con n > M e H = 1 (ridondante):
  – 000 A
  – 001 B
  – 010 C
• Codice con n > M e H = 2 (ridondante):
  – 000 A
  – 011 B
  – 101 C
• Codice con n = M e H = 1 (ridondante):
  – 00 A
  – 01 B
  – 10 C

Se due parole di codice hanno una distanza di Hamming uguale a H, ci vogliono esattamente H errori su singoli bit per trasformare l’una nell’altra.

Esempio: la distanza di Hamming tra s1=1000 1001 e s2=1011 0001 è H = 3, ossia per trasformare s1 in s2 devono cambiare tre bit.

Trasmissione di informazioni

Un sistema di telecomunicazione reale è soggetto ad errori di trasmissione dovuti alla presenza di rumore sul canale. La probabilità di errore sul bit inviato sul canale è legata a diversi fattori: potenza media del segnale in ricezione, tipo di canale, ecc.

• È possibile rendere arbitrariamente piccola la probabilità d’errore sui bit di informazione utilizzando opportune tecniche di codifica di canale.
• Il processo di codifica di canale consiste nell’aggiungere bit di ridondanza al messaggio che si vuole trasmettere.
• In fase di ricezione, la presenza di tali bit aggiuntivi consente di rilevare o correggere eventuali errori introdotti nel messaggio dal rumore presente sul canale.

Codifica di canale

Lo svantaggio della codifica di canale è che si devono trasmettere più bit di quanti ne siano effettivamente necessari per rappresentare il messaggio; a parità di altre condizioni, cresce il tempo richiesto per la trasmissione.

• La codifica di canale, a parità di condizioni, non cambia la probabilità d’errore dei bit che viaggiano “fisicamente” sul canale.
• L’impiego della codifica di canale riduce la probabilità d’errore dei bit di informazione (ovvero dei bit del messaggio).

Codice a rivelazione/correzione degli errori

In un sistema di telecomunicazione reale il segnale trasmesso può essere affetto da errori. Ci sono due approcci al trattamento degli errori:

• Includere abbastanza informazione aggiuntiva in modo da poter ricostruire il messaggio originario (correzione dell’errore).
• Includere meno informazione aggiuntiva, in modo da accorgersi che c’è stato un errore, senza per questo essere in grado di correggerlo (rilevazione dell’errore).

Normalmente, il segnale consiste di: n = m + r bit, dove:

• m bit costituiscono il messaggio vero e proprio;
• r bit sono ridondanti, e sono detti redundant bit (o check bit).

Codici ridondanti a rivelazione di errore: parità

Il bit di parità è un codice di controllo utilizzato nei calcolatori per rilevare errori nella trasmissione o nella memorizzazione dei dati.

Parità:

• È un codice con H = 2;
• Si ottiene dal codice non ridondante aggiungendo 1 bit in modo che il numero complessivo di bit uguali a “1” sia pari (parità pari) o dispari (parità dispari);
• Avendo H = 2 può solo rilevare gli errori, e solo se questi accadono singolarmente o in un numero dispari nella stessa parola di codice.

Se un numero dispari di bit (incluso il bit di parità) è cambiato durante la trasmissione di un insieme di bit allora il bit di parità non sarà corretto e indicherà che è avvenuto un errore durante la trasmissione.

Esempio: parità pari

Codice parità pari:

101000011110

Possibili errori singoli che rendono la parola a... (continua)