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

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.

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à

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.

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

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.

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

Il codice Gray è un codice in cui due numeri consecutivi hanno distanza di Hamming $1$: passando dal numero al successivo cambia 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).

Conversione binario $\to$ 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$.

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.