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).
Formula (bit per codificare $N$ oggetti)
- Con $n$ bit si codificano $2^n$ oggetti distinti; per $N$ oggetti servono $\lceil \log_2 N \rceil$ bit (26 lettere → 5 bit).

Esempio. Per $26$ lettere servono $\lceil\log_2 26\rceil=5$ bit, perché $2^4=16<26\le2^5=32$ .

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}$

Formula (bit di indirizzo di una memoria). 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.

Esempio. $64\ \text{KB}=2^6\cdot2^{10}=2^{16}$ byte: servono $16$ bit di indirizzo.

Codici numerici

Definizione (codice BCD). 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.

Esempio. $47_{10}=0100\,0111_{\text{BCD}}$ , mentre in binario puro è $101111_2$ .

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

Esempio. $b=110$ ( $6$ ): $g=110\oplus011=101$ .

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

Definizione (ASCII, Unicode e UTF-8)

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.

Esempio. La cifra $7$ ha codice ASCII $48+7=55=\mathrm{0x37}$ ; è (U+00E8) in UTF-8 è C3 A8.

Ordine dei byte: little e big endian

Definizione (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

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

Esempio. 0x12345678 in little endian occupa, a partire dall'indirizzo più basso, i byte 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.

Definizione (bit di parità). 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.

Esempio. 1011 0010 ha quattro 1 (parità $0$ ); 1011 0011 ne ha cinque (parità $1$ ).

Formula (bit di controllo del codice di Hamming). 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.

Esempio. Per $m=8$ bit di dati $k=4$ , perché $2^4-1=15\ge8+4=12$ mentre $k=3$ darebbe $7<11$ .

$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$ $C_{8}$ : posizioni 9, 10, 11, 12
  Definizione (sindrome di Hamming)
  1. 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. Con sindrome $C_8C_4C_2C_1=0110$ è sbagliato il bit in posizione $6$ , che va invertito.

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.