Codifiche binarie e informazione non numerica

In questa pagina 6

In questa pagina 3

Una sequenza di bit non ha significato da sola: è la codifica scelta a dire se rappresenta un intero, un reale, un carattere o un'istruzione.

Bit, byte e multipli

1 byte = 8 bit; una parola (word) è la quantità che il processore elabora in un colpo (32 bit in ARM a 32 bit).
Con $n$ bit si codificano $2^n$ oggetti distinti; per $N$ oggetti servono $\lceil \log_2 N \rceil$ bit (26 lettere → 5 bit).

Prefisso binario	Valore	Prefisso SI	Valore
Ki (kibi)	$2^{10} = 1024$	k (kilo)	$10^3$
Mi (mebi)	$2^{20}$	M (mega)	$10^6$
Gi (gibi)	$2^{30}$	G (giga)	$10^9$
Ti (tebi)	$2^{40}$	T (tera)	$10^{12}$

Per memorie e indirizzi si usano le potenze di 2 (spesso scritte K, M, G). Conti tipici: $16\ \text{MB} = 2^4 \cdot 2^{20} = 2^{24}$ byte, quindi servono 24 bit di indirizzo se ogni byte ha il suo indirizzo; $4\ \text{GB} = 2^{32}$ byte → 32 bit.

Codici numerici

BCD (Binary Coded Decimal): ogni cifra decimale su 4 bit. $259 = 0010\,0101\,1001_{\text{BCD}}$ (in binario puro sarebbe $1\,0000\,0011$ ). Spreca 6 configurazioni su 16 ma evita le conversioni: si usa in display e calcolatrici.

Codice Gray: due numeri consecutivi differiscono per un solo bit. Si ottiene da $b$ binario come $g = b \oplus (b \gg 1)$ .

Decimale	0	1	2	3	4	5	6	7
Binario	000	001	010	011	100	101	110	111
Gray	000	001	011	010	110	111	101	100

Si usa negli encoder di posizione (un errore di lettura sposta di una sola posizione) e nell'ordine delle righe e colonne delle mappe di Karnaugh.

Caratteri

ASCII: 7 bit, 128 simboli. '0'–'9' = 48–57 (0x30–0x39), 'A' = 65 (0x41), 'a' = 97 (0x61). Maiuscola e minuscola differiscono solo per il bit 5 (valore 32); la cifra $d$ ha codice $48 + d$ .
Unicode: assegna un numero (code point) a ogni carattere di tutte le scritture, da U+0000 a U+10FFFF.
UTF-8: codifica i code point in 1–4 byte; i caratteri ASCII restano su 1 byte identico. 'è' = U+00E8 → 2 byte C3 A8.

Ordine dei byte: little e big endian

Una parola di 4 byte occupa 4 indirizzi consecutivi. Per 0x12345678 all'indirizzo 100:

Indirizzo	100	101	102	103
Big endian (byte più significativo all'indirizzo minore)	12	34	56	78
Little endian (byte meno significativo all'indirizzo minore)	78	56	34	12

x86 è little endian; ARM può lavorare in entrambi i modi ma si usa quasi sempre little endian. Le reti trasmettono in big endian.

Rilevazione e correzione degli errori

Le memorie possono subire errori: guasti permanenti (hardware) e errori soft, casuali e non distruttivi (per esempio una particella che cambia lo stato di una cella). Si aggiungono $k$ bit di controllo agli $m$ bit di dati.

Bit di parità ( $k = 1$ ): si sceglie il bit in modo che il numero totale di 1 sia pari. Rileva un numero dispari di errori, non li corregge. Dati $1011\,0010$ (quattro 1) → parità 0.

Codice di Hamming (correzione di un errore singolo, SEC). Servono $k$ bit di controllo con

$2^k - 1 \ge m + k$

perché la sindrome di $k$ bit deve distinguere "nessun errore" e ciascuna delle $m + k$ posizioni.

$m$ (dati)	$k$ (controllo)	Aggiunta
8	4	50%
16	5	31%
32	6	19%
64	7	11%

Costruzione:

Si numerano le posizioni da 1 a $m + k$ . I bit di controllo $C_1, C_2, C_4, C_8, \dots$ stanno nelle posizioni potenze di 2, i dati nelle altre.
$C_{2^j}$ $C_{2^{j}}$ è lo XOR dei dati nelle posizioni il cui numero binario ha il bit $j$ $j$ a 1. Con $m = 8$ $m = 8$ (posizioni 1–12):
- $C_1$ : posizioni 3, 5, 7, 9, 11
- $C_2$ : posizioni 3, 6, 7, 10, 11
- $C_4$ : posizioni 5, 6, 7, 12
- $C_8$ : posizioni 9, 10, 11, 12
In lettura si ricalcolano i bit di controllo dai dati letti e si fa lo XOR con quelli memorizzati: la sindrome. Se è $0$ non ci sono errori; altrimenti il suo valore è la posizione del bit sbagliato, che si inverte.

Esempio di correzione: se la sindrome vale $C_8C_4C_2C_1 = 0110$ , è sbagliato il bit in posizione 6 (il dato $D_3$ ). Un errore su un bit di controllo dà una sindrome con un solo 1 (posizione potenza di 2).

SEC-DED: aggiungendo un bit di parità su tutta la parola si rileva anche un errore doppio (sindrome $\neq 0$ ma parità globale corretta), senza poterlo correggere.

Esercizi svolti in aula: Esercizio 3 · bit di controllo di Hamming per un byte, Esercizio 4 · parola letta dalla memoria con la sindrome di Hamming, Esercizio 5 · bit di controllo per una parola di 1024 bit, Esercizio 6 · codice SEC per una parola di 16 bit.

Errori tipici

Usare $2^k \ge m$ invece di $2^k - 1 \ge m + k$ : anche i bit di controllo possono sbagliare.
Confondere KB ( $2^{10}$ byte per le memorie) con kb (kilobit).
Leggere un dump di memoria little endian da sinistra a destra come se fosse il numero.

Versione ripasso

Bit e multipli

Con $n$ bit si codificano $2^n$ oggetti ( $\lceil \log_2 N \rceil$ bit per $N$ ). Ki $= 2^{10}$ , Mi $= 2^{20}$ , Gi $= 2^{30}$ ; k, M, G $= 10^3, 10^6, 10^9$ . $16\ \text{MB} = 2^{24}$ byte $\to$ 24 bit di indirizzo; $4\ \text{GB} \to$ 32 bit.

Codici

BCD: una cifra decimale su 4 bit ( $259 = 0010\,0101\,1001$ ). Gray: consecutivi differiscono per un bit, $g = b \oplus (b \gg 1)$ : 000, 001, 011, 010, 110, 111, 101, 100 (mappe di Karnaugh).
ASCII: 7 bit; '0' = 48, 'A' = 65, 'a' = 97 (differiscono per il bit 5). Unicode: code point U+0000...U+10FFFF; UTF-8: 1-4 byte, ASCII invariato; 'è' $\to$ C3 A8.
Endian: 0x12345678 all'indirizzo 100, big endian 12 34 56 78, little endian 78 56 34 12 (x86 e quasi sempre ARM).

Errori: parità e Hamming

Parità ( $k = 1$ ): numero di 1 pari, rileva un numero dispari di errori.
Hamming SEC con $m$ $m$ dati e $k$ $k$ controlli: $2^k - 1 \ge m + k$ $2^{k} - 1 \geq m + k$ (la sindrome distingue "nessun errore" e le $m + k$ $m + k$ posizioni); $m = 8, 16, 32, 64 \to k = 4, 5, 6, 7$ $m = 8, 16, 32, 64 \to k = 4, 5, 6, 7$ .
1. Posizioni da 1 a $m + k$ ; controlli $C_1, C_2, C_4, C_8, \dots$ nelle potenze di 2.
2. $C_{2^j}$ = XOR dei dati nelle posizioni con il bit $j$ a 1 ( $m = 8$ : $C_1$ : 3, 5, 7, 9, 11; $C_2$ : 3, 6, 7, 10, 11; $C_4$ : 5, 6, 7, 12; $C_8$ : 9, 10, 11, 12).
3. In lettura, sindrome $= 0$ nessun errore, altrimenti è la posizione da invertire ( $0110 \to 6$ ).
SEC-DED: parità globale in più, rileva l'errore doppio.
Esercizi: Esercizio 3 · bit di controllo di Hamming per un byte, Esercizio 4 · parola letta dalla memoria con la sindrome di Hamming, Esercizio 5 · bit di controllo per una parola di 1024 bit, Esercizio 6 · codice SEC per una parola di 16 bit.

Errori tipici: $2^k \ge m$ invece di $2^k - 1 \ge m + k$ ; KB e kb; dump little endian letto come numero.