Codici binari - BCD, ASCII, Unicode, parità e Gray

Una codifica associa a ogni elemento di un insieme discreto una configurazione di bit, per facilitare elaborazione, memorizzazione e trasmissione. Un codice a $n$ bit ha $2^n$ configurazioni: 4 elementi si codificano con 2 bit (00, 01, 10, 11), 8 elementi con 3 bit, 16 con 4 bit. Se gli elementi sono meno delle configurazioni, alcune configurazioni restano non utilizzate.

Codice BCD

Definizione (codice BCD). Il BCD (Binary-Coded Decimal) codifica ogni cifra decimale con il suo valore binario su 4 bit. Per scrivere un numero si codifica cifra per cifra:

Esempio. $185_{10}=0001\;1000\;0101_{BCD}$, mentre in binario puro è $10111001_2$: le due rappresentazioni sono diverse. Invece $3_{10}=0011_{BCD}=11_2$ coincidono solo perché il numero ha una cifra.

Le sei configurazioni $1010,1011,1100,1101,1110,1111$ (valori $10$–$15$) non sono cifre BCD: sono un esempio di configurazioni non utilizzate, che nelle mappe di Karnaugh diventano condizioni di indifferenza (Mappe di Karnaugh - POS, condizioni di don't care e paritàPer la POS minima si raggruppano gli 0 della mappa, si ottiene la SOP minima di $\overline F$ e si scrive $F$ come prodotto di somme (variabile diretta se vale 0 nel gruppo, negata se vale 1). Le condizioni di don't care (X) sono combinazioni di ingresso che non si presentano o la cui uscita è indifferente: si usano come 1 o come 0 a seconda di quel che allarga i gruppi (mai raggruppamenti fatti solo di X). Le funzioni XOR a più variabili (disparità) e XNOR (parità) hanno mappa a scacchiera: non si semplificano con i gruppi.Mappe di Karnaugh - POS, condizioni di don't care e parità →).

Lo spreco di bit (4 bit per 10 valori) è il prezzo della comodità quando ingressi e uscite sono numeri decimali (display, calcolatrici). Per rappresentare il numero $10$ in BCD servono 8 bit ($0001\,0000$), non 4: la cifra $10$ non esiste.

Attenzione ai quiz. $0001\,0101\,1001_{BCD}$ è $159$ (non $1519$): si legge a gruppi di 4. $00101000_{BCD}$ vale $28$, non $40$ (che sarebbe la lettura binaria $2^5+2^3$). Il BCD $00010010$ è $12_{10}$, cioè $C_{16}$.

ASCII

L'ASCII (American Standard Code for Information Interchange) usa 7 bit per $128$ caratteri: lettere maiuscole e minuscole, cifre, segni di punteggiatura e $32$ caratteri di controllo non stampabili. Di solito si memorizza in un byte, con il bit più significativo a $0$ o usato per caratteri aggiuntivi.

Esempi: A $=1000001_2=65$; a $=1100001_2=97$ (le minuscole differiscono dalle maiuscole per un bit); la cifra 0 $=0110000_2=48$, la cifra 5 $=0110101_2=53$.

Relazione con il BCD: il codice ASCII di una cifra decimale si ottiene aggiungendo 011 a sinistra del suo BCD: 5 $=011\,0101$ ($0101$ è il BCD di 5).

Unicode e UTF-8

L'ASCII non basta per le lingue del mondo. Unicode assegna a ogni carattere un numero univoco, il code point, indipendente da lingua, piattaforma e programma; si scrive U+ seguito dalle cifre esadecimali (T = U+0054, ± = U+00B1, € = U+20AC). La codifica più usata è UTF-8, che usa da 1 a 4 byte per code point ed è compatibile con l'ASCII: i primi $128$ code point hanno la stessa codifica a un byte.

Definizione (codifica UTF-8)

intervallo del code point	byte	schema dei bit
U+0000 – U+007F	1	0xxxxxxx
U+0080 – U+07FF	2	110xxxxx 10xxxxxx
U+0800 – U+FFFF	3	1110xxxx 10xxxxxx 10xxxxxx
U+10000 – U+10FFFF	4	11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

I bit x sono quelli del code point, scritti in binario e distribuiti da sinistra a destra.

Esempio ±: $B1_{16}=1011\,0001_2$ sta in $2$ byte. Gli $11$ bit di payload sono $000\,1011\,0001$: i primi $5$ ($00010$) vanno nel primo byte, gli ultimi $6$ ($110001$) nel secondo: $11000010\;10110001$. Esempio €: $20AC_{16}=0010\,0000\,1010\,1100_2$, $16$ bit, quindi $3$ byte: $11100010\;10000010\;10101100$.

UTF-8 non usa un solo byte per tutti i caratteri, né due byte per tutti quelli alfanumerici: lunghezza variabile.

Bit di parità

Definizione (bit di parità). Per rilevare errori (non correggerli) si aggiunge un bit scelto in modo che il numero totale di 1 sia pari (parità pari, la più usata) oppure dispari.

Esempio. 1011001 ha quattro 1: con parità pari il bit è $0$ (01011001), con parità dispari è $1$ (11011001).

Esempi. 1000001 ha due 1: con parità pari il bit è $0$ ($01000001$), con parità dispari è $1$ ($11000001$). 1010100 ha tre 1: parità pari $\to$ bit $1$ ($11010100$); parità dispari $\to$ bit $0$ ($01010100$).

Il ricevitore conta gli 1. Se in un sistema a parità pari arriva una parola con un numero dispari di 1, almeno un bit è stato corrotto (può rispondere con un NAK, negative acknowledge, e farsi ritrasmettere il dato). Se il numero è pari non c'è stato errore su un singolo bit, ma sono possibili due errori che si compensano: la parità rivela errori su un numero dispari di bit. Esempi con parità pari: 00100010 (due 1) e 11111111 (otto 1) sono parole accettabili, 00100011 segnalerebbe un errore. Per correggere servono più bit di controllo.

Distanza di Hamming

Definizione (distanza di Hamming). La distanza di Hamming tra due configurazioni è il numero di bit in cui differiscono. Esempi: $8=1000$ e $11=1011$ differiscono nei due bit meno significativi, distanza $2$; $8=1000$ e $4=0100$ differiscono in due posizioni, distanza $2$; $0=000$ e $7=111$, distanza $3$. Non è la differenza algebrica dei numeri.

Esempio. $d(0110,1101)=3$: i due codici differiscono in $3$ bit su $4$ ($0110\oplus1101=1011$).

Geometricamente, le configurazioni di $n$ bit sono i vertici di un ipercubo ($n=1$ segmento, $n=2$ quadrato, $n=3$ cubo): due configurazioni a distanza $1$ sono unite da uno spigolo. Servirà nelle mappe di Karnaugh (Mappe di Karnaugh - implicanti e copertura minimaLa mappa di Karnaugh è la tabella di verità disposta in una griglia con righe e colonne in codice Gray, così che celle adiacenti (anche tra bordi opposti) differiscano in una sola variabile. Si raggruppano gli 1 in rettangoli di $2^k$ celle: ogni gruppo elimina $k$ variabili e dà un prodotto. Implicante primo = gruppo massimo; essenziale = unico a coprire un mintermine; la copertura minima contiene tutti gli essenziali più il minimo di altri primi (può non essere unica). Efficace fino a 4 variabili.Mappe di Karnaugh - implicanti e copertura minima →).

Codice Gray

Definizione (codice Gray). Il codice Gray è un codice in cui due numeri consecutivi hanno distanza di Hamming $1$: passando dal numero al successivo cambia un solo bit.

Esempio. A $4$ bit $5\to0111$ e $6\to0101$ differiscono in un solo bit.

Perché serve. Un dispositivo che segnala la propria posizione con $3$ interruttori $B_2B_1B_0$ in codice binario passa da $011$ (posizione 3) a $100$ (posizione 4) cambiando tutti e tre i bit. Nella realtà i sensori non cambiano nello stesso istante: durante la transizione si può leggere $011\to001\to101\to100$, e $101$ è la posizione $5$, un grosso errore. Con il Gray la transizione fra posizioni adiacenti cambia un solo sensore: per un encoder ottico a $3$ bit i sensori sul confine fra le posizioni $010$ e $110$ possono leggere solo $010$ o $110$, entrambe corrette entro la tolleranza. (Da qui l'uso nei sensori di posizione; nel corso lo si usa anche per ordinare le mappe di Karnaugh e per codificare gli stati.)

Costruzione per riflessione. Si parte dal codice a $n-1$ bit, lo si riscrive in ordine inverso (specchiato) sotto se stesso, si antepone $0$ alla prima metà e $1$ alla seconda. Con $3$ bit: $000,001,011,010,110,111,101,100$. Il primo e l'ultimo valore hanno distanza $1$: il codice è chiuso (ciclico).

Formula (conversione binario-Gray). Il bit più significativo si copia; ogni altro bit è lo XOR del bit binario corrispondente con quello alla sua sinistra: $g_i=b_i\oplus b_{i+1}$. Esempio: $b=1011$: $g_3=1$; $g_2=0\oplus1=1$; $g_1=1\oplus0=1$; $g_0=1\oplus1=0$, quindi $g=1110$. La conversione inversa è $b_i=b_{i+1}\oplus g_i$.

Esempio. $b=0110$ ($6$): $g_3=0$, $g_2=0\oplus1=1$, $g_1=1\oplus1=0$, $g_0=1\oplus0=1$, quindi $g=0101$.

Codice Gray con un numero di parole non potenza di 2. Per $n$ parole pari (esempio $10$) si calcola il Gray delle prime $n/2=5$ parole ($0000,0001,0011,0010,0110$) e si aggiunge la loro immagine speculare con il bit più significativo a $1$: $1110,1010,1011,1001,1000$. Risultato: $0000,0001,0011,0010,0110,1110,1010,1011,1001,1000$, ancora chiuso ($0000$ e $1000$ distano $1$). Per $2^n-1$ parole (esempio $7$) basta prendere le prime $7$ del Gray normale: $000,001,011,010,110,111,101$.

Errori comuni

• Leggere un BCD come binario ($00101000$ non è $40$) o dimenticare che servono 4 bit per cifra.
• Dire che la parità corregge gli errori: li rileva, e solo se sono in numero dispari.
• Calcolare la distanza di Hamming come differenza dei numeri.
• Confondere ASCII a 7 bit con un codice a 8 bit.
• Pensare che UTF-8 usi sempre lo stesso numero di byte.