Esercizio - Codice di controllo per numeri di registro

Questa pagina non ha ancora la versione ripasso: qui sotto c'è il testo completo.

Testo (scheda "Channel coding"). Un addetto vuole assegnare un numero di registro decimale univoco a tutti i pacchi gestiti, in modo da identificare fino a 100 miliardi di pacchi, e in modo che, se una sola cifra di un numero è trascritta male nel registro, l'errore venga sempre rivelato. Quante cifre servono nel numero di registro? Scrivere un possibile algoritmo per crearlo.

Teoria usata: Codici a blocco - distanza minima, rivelazione e correzioneLa codifica di canale aggiunge ridondanza in modo mirato: $k$ bit di informazione diventano una parola di codice di $n>k$ bit scelta tra $2^k$ parole ammesse. Se la parola ricevuta non è una parola di codice l'errore è rivelato (e si può chiedere la ritrasmissione, ARQ) oppure corretto (FEC). La qualità dipende dalla distanza minima di Hamming $d_{min}$: si rivelano fino a $d_{min}-1$ errori e se ne correggono $t<d_{min}/2$, ma non contemporaneamente. Per un BSC con $P_{bit}<1/2$ la decisione ottima ML coincide con quella a distanza minima. Limite di Hamming: $k/n\le1-\frac1n\log_2\sum_{r=0}^t\binom nr$.Codici a blocco - distanza minima, rivelazione e correzione → (rivelazione con $d_{min}=2$, codice a bit di parità), Codici a blocco lineari e sindromeUn codice a blocco è lineare se la somma (XOR) di due parole di codice è una parola di codice: allora le parole formano un sottospazio di $\mathbb Z_2^n$. Si descrive con la matrice generatrice $G$ ($n\times k$, $\mathbf c=G\mathbf b$; in forma sistematica $G=\binom{I_k}{A}$) e con la matrice di controllo $H$ ($(n-k)\times n$, $H\mathbf c=\mathbf 0$ se e solo se $\mathbf c\in\mathcal C$; per $G$ sistematica $H=[A\mid I_{n-k}]$). La distanza minima è il peso minimo delle parole non nulle e vale $d_{min}\le n-k+1$ (Singleton). La sindrome $\boldsymbol\sigma=H\tilde{\mathbf c}$ dipende solo dall'errore; la decodifica a distanza minima è $\hat{\mathbf c}=\tilde{\mathbf c}-\varepsilon(\boldsymbol\sigma)$, dove $\varepsilon(\boldsymbol\sigma)$ è il coset leader (vettore di peso minimo con quella sindrome).Codici a blocco lineari e sindrome → (limite di Singleton).

1. Cambiare alfabeto

Il corso ha sempre lavorato con bit, ma il testo parla di cifre decimali: l'alfabeto è $\mathbb Z_{10}=\{0,1,\dots,9\}$ invece di $\mathbb Z_2$. La distanza di Hamming resta la stessa idea: $d_H(\mathbf a,\mathbf b)=$ numero di cifre diverse. Tutti i ragionamenti sulla distanza minima valgono ancora (non serve la linearità).

2. Quante cifre di informazione

Servono $10^{11}$ identificatori diversi ($100$ miliardi). Con $k$ cifre decimali se ne hanno $10^k$: $k=11$ cifre danno esattamente $10^{11}$ numeri ($00000000000,\dots,99999999999$). Quindi $k=11$ per identificare, ma non basta per rivelare errori: con $11$ cifre ogni sequenza è un numero valido, e se si sbaglia una cifra si ottiene un altro numero valido (distanza $1$ tra parole valide: $d_{min}=1$, nessun errore rivelabile).

3. Quante cifre in tutto

Per rivelare ogni errore su una sola cifra serve $d_{min}\ge2$ (un codice con $d_{min}$ rivela $d_{min}-1$ errori): due numeri validi devono differire in almeno $2$ cifre. Il limite di Singleton $d_{min}\le n-k+1$ dà $2\le n-11+1$, cioè $n\ge12$: servono almeno $12$ cifre (le $11$ di informazione più una cifra di controllo). E $12$ bastano, con l'idea del bit di parità portata in $\mathbb Z_{10}$. Il codice è un blocco $(n,k)=(12,11)$ sistematico.

4. L'algoritmo

Si prende il numero di $11$ cifre $b_1b_2\dots b_{11}$ e si copia: $c_j=b_j$ per $j=1,\dots,11$. La cifra di controllo $c_{12}$ è scelta in modo che la somma di tutte le cifre, compresa lei, sia congruente a $0$ modulo $10$: $$\sum_{j=1}^{12}c_j\equiv0\pmod{10},\qquad c_{12}=\Big(-\sum_{j=1}^{11}b_j\Big)\bmod 10.$$ Esempio. $\mathbf b=12347891234$: somma delle cifre $1+2+3+4+7+8+9+1+2+3+4=44$, $44\bmod10=4$, quindi $c_{12}=(10-4)=6$ e il numero di registro è $\mathbf c=123478912346$ (somma $50\equiv0$, verificato al calcolatore).

Controllo alla trascrizione. Si ricalcola la somma delle $12$ cifre modulo $10$: se non è $0$, c'è un errore.

5. Perché rivela ogni errore su una cifra

Se la cifra in posizione $j$ passa da $c_j$ a $c_j'\ne c_j$, la somma cambia di $c_j'-c_j$, che è un numero tra $-9$ e $9$ diverso da $0$ e quindi non multiplo di $10$: la somma modulo $10$ non è più $0$. Quindi due numeri validi differiscono in almeno $2$ cifre: $d_{min}=2$. Controllo numerico: tutti i $12\cdot9=108$ errori su una cifra di $123478912346$ danno somma $\not\equiv0$ (nessuno sfugge).

6. Limiti e miglioramenti

Come il bit di parità, questo codice rivela ma non corregge (non si sa quale cifra è sbagliata) e non rivela due errori che si compensano (per esempio $+3$ su una cifra e $-3$ su un'altra) né lo scambio di due cifre adiacenti: $123478912346$ diventa $123748912346$ ed è ancora valido. Per questo i codici reali (ISBN, carte di credito, codice fiscale) usano pesi diversi per le cifre (ISBN-10: somma pesata modulo $11$; carte di credito: algoritmo di Luhn, che raddoppia una cifra su due): aumentano la capacità di rivelare gli errori più frequenti nelle trascrizioni.