Codici di Hamming e bound di Hamming

Un limite al tasso di un codice a parità di errori corretti (il bound di Hamming) e una famiglia di codici che lo raggiunge con l'uguaglianza (i codici di Hamming) completano la parte sulla codifica di canale. La distanza minima, la sindrome e la matrice di controllo sono quelle di Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetricoPer proteggere i bit dagli errori si può chiedere la ritrasmissione (ARQ, serve il canale di ritorno), aggiungere ridondanza per correggere (FEC) o unire le due cose (HARQ). Un codice a blocco $(n,k)$ trasforma $k$ bit in una parola di $n>k$ bit scelta tra $2^k$ parole su $2^n$ sequenze; modulatore, canale e demodulatore equivalgono a un canale binario simmetrico senza memoria con probabilità d'errore sul bit $P_{bit}$. Per $P_{bit}<\frac12$ il decodificatore ML sceglie la parola a minima distanza di Hamming; con distanza minima $d_{min}$ si correggono sempre $t=\lfloor\frac{d_{min}-1}{2}\rfloor$ errori e se ne rivelano sempre $d_{min}-1$. Il tasso è $R=\frac kn$ e la probabilità d'errore di parola è limitata da $P(\text{più di }t\text{ errori})$. L'ARQ ha efficienza $S_{SW}$, $S_{GBN}$, $S_{SR}$ in funzione di $t_P$, $t_A$, $\tau_P$ e $p$.Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetrico → e di Matrice di controllo di parità, sindrome e cosetLa matrice di controllo di parità $H$ ($\ell\times n$) soddisfa $H\mathbf r=\mathbf 0\iff\mathbf r\in\mathcal C$; per un codice con generatrice $G$ ($n\times k$) vale $HG=0$ con $\operatorname{rango}(H)=n-k$, e se $G=\begin{bmatrix}I_k\A\end{bmatrix}$ allora $H=[A\mid I_{n-k}]$. La distanza minima è il minimo numero di colonne di $H$ linearmente dipendenti. La sindrome $\boldsymbol\sigma=H\boldsymbol\gamma$ della sequenza ricevuta $\boldsymbol\gamma=\mathbf c+\boldsymbol\varepsilon$ vale $H\boldsymbol\varepsilon$: dipende solo dall'errore. Le sequenze con la stessa sindrome formano un coset ($2^{n-k}$ coset di $2^k$ sequenze) e il decodificatore a minima distanza sceglie il coset leader, l'errore di peso minimo del coset: $\hat{\mathbf c}=\boldsymbol\gamma+\boldsymbol\varepsilon_{min}$. La probabilità di decodifica corretta sul BSC è la somma delle probabilità dei coset leader.Matrice di controllo di parità, sindrome e coset →.

Versione per Ing. Elettronica: Codici a blocco lineari - matrice generatrice, controllo di parità, sindrome e codici di HammingUn codice a blocco è lineare se la somma (bit a bit, modulo 2) di due parole di codice è una parola di codice. Si descrive con la matrice generatrice $G$ ($k\times n$, $\mathbf c=\mathbf mG$) e con la matrice di controllo di parità $H$ ($(n-k)\times n$, $G H^T=0$); in forma sistematica $G=[I_k\mid P]$ e $H=[P^T\mid I_{n-k}]$. La distanza minima è il peso minimo delle parole non nulle. La sindrome $\mathbf s=\mathbf rH^T$ dipende solo dall'errore: se è nulla la parola è valida, altrimenti identifica l'errore (un solo errore ha per sindrome la colonna di $H$ corrispondente). I codici di Hamming $(2^m-1,,2^m-1-m)$ hanno $d_{min}=3$.Codici a blocco lineari - matrice generatrice, controllo di parità, sindrome e codici di Hamming →. Per Ing. delle Telecomunicazioni: Codici di Hamming e CRCIl codice di Hamming $(2^h-1,,2^h-h-1)$ ha come matrice di controllo $H$ che ha per colonne tutte le sequenze non nulle di $h$ bit: colonne distinte e non nulle danno $d_{min}=3$, la sindrome di un errore singolo è la colonna corrispondente, quindi corregge 1 errore (o rivela 2) ed è un codice perfetto ($2^{n-k}=1+n$). Per $(7,4)$ e BSC: errore non rivelato $\simeq7P^3(1-P)^4$, parola sbagliata dopo correzione $\simeq\binom72P^2(1-P)^5$. Il CRC è un codice lineare ciclico usato per sola rivelazione: la parola è $m(x)x^r$ più il resto della divisione per il polinomio generatore $g(x)$ di grado $r$ (modulo 2); rivela ogni errore a burst di lunghezza $\le r$.Codici di Hamming e CRC →.

1. Il bound di Hamming

Un codice $(n,k)$ che corregge sempre $t$ errori ha $d_{min}\ge2t+1$: le sfere di Hamming di raggio $t$ attorno alle $2^k$ parole sono disgiunte (Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetricoPer proteggere i bit dagli errori si può chiedere la ritrasmissione (ARQ, serve il canale di ritorno), aggiungere ridondanza per correggere (FEC) o unire le due cose (HARQ). Un codice a blocco $(n,k)$ trasforma $k$ bit in una parola di $n>k$ bit scelta tra $2^k$ parole su $2^n$ sequenze; modulatore, canale e demodulatore equivalgono a un canale binario simmetrico senza memoria con probabilità d'errore sul bit $P_{bit}$. Per $P_{bit}<\frac12$ il decodificatore ML sceglie la parola a minima distanza di Hamming; con distanza minima $d_{min}$ si correggono sempre $t=\lfloor\frac{d_{min}-1}{2}\rfloor$ errori e se ne rivelano sempre $d_{min}-1$. Il tasso è $R=\frac kn$ e la probabilità d'errore di parola è limitata da $P(\text{più di }t\text{ errori})$. L'ARQ ha efficienza $S_{SW}$, $S_{GBN}$, $S_{SR}$ in funzione di $t_P$, $t_A$, $\tau_P$ e $p$.Controllo d'errore - ARQ, FEC e codici a blocco sul canale binario simmetrico →). Quante sequenze contiene una sfera?

• Le sequenze a distanza esattamente $r$ da una sequenza data di $n$ bit si ottengono cambiando $r$ bit su $n$: sono $\binom nr$ (si scelgono le posizioni da cambiare).
• Quindi la sfera di raggio $t$ contiene $\sum_{r=0}^t\binom nr$ sequenze (la prima, per $r=0$, è la parola stessa).

Le $2^k$ sfere, tutte diverse, stanno nello spazio delle $2^n$ sequenze:

$$\boxed{2^k\sum_{r=0}^t\binom nr\le2^n}$$

Prendendo $\log_2$ e dividendo per $n$:

$$n\ge k+\log_2\sum_{r=0}^t\binom nr\quad\Longrightarrow\quad\boxed{\frac kn\le1-\frac1n\log_2\sum_{r=0}^t\binom nr}.$$

È un limite superiore al tasso $R=\frac kn$ in funzione di $t$: più errori si vogliono correggere, meno alto può essere il tasso. È una condizione necessaria: se è violata il codice non esiste; se è rispettata non è detto che esista.

Esempio ($t=1$, $n=7$). $\sum_{r=0}^1\binom7r=1+7=8$, quindi $2^k\cdot8\le2^7$, cioè $k\le4$: il tasso massimo di un codice a $7$ bit che corregge $1$ errore è $\frac47$. Con $k=4$ vale l'uguaglianza: $2^4\cdot8=2^7$.

Esempio (un codice che non esiste). Si può costruire un codice con $n=64$ e $k=57$ che corregge $2$ errori? Con $t=2$: $\sum=1+64+\binom{64}2=1+64+2016=2081$ e $\frac{57}{64}=0{,}8906$, mentre $$1-\frac1{64}\log_2(2081)=1-\frac{11{,}02}{64}=0{,}8278.$$ $0{,}8906>0{,}8278$: il bound è violato, il codice non esiste (con sole $7$ righe di parità non si distinguono i $2081$ errori da correggere: $2^7=128<2081$).

Esempio (confronto con Singleton). Per $n=10$ e $t=2$: $1+10+45=56$ e $2^{n-k}\ge56$ dà $n-k\ge6$, cioè $k\le4$. Il bound di Singleton (Codici a blocco lineari - matrice generatrice, forma sistematica e bound di SingletonUn codice a blocco è lineare se le sue $2^k$ parole formano un sottospazio dello spazio delle sequenze binarie di $n$ bit, con la somma modulo 2 (XOR) senza riporto: contiene la parola nulla ed è chiuso rispetto alla somma. Si descrive con la matrice generatrice $G$ ($n\times k$, rango $k$, $\mathbf c=G\mathbf b$, le colonne sono parole di codice); le operazioni sulle colonne non cambiano il codice, le permutazioni delle righe permutano i bit e non cambiano le prestazioni sul canale senza memoria. In forma sistematica $G=\begin{bmatrix}I_k\A\end{bmatrix}$ e $\mathbf c=[\mathbf b;A\mathbf b]$. Per i codici lineari la distanza minima è il peso di Hamming minimo delle parole non nulle e vale il bound di Singleton $d_{min}\le n-k+1$.Codici a blocco lineari - matrice generatrice, forma sistematica e bound di Singleton →) con $d_{min}\ge5$ darebbe solo $k\le n-d_{min}+1=6$: quello di Hamming è più stringente.

2. Il codice di Hamming

Definizione. Un codice di Hamming è un codice lineare la cui matrice di controllo di parità $H$ ha per colonne tutte le sequenze binarie non nulle lunghe $n-k$, ciascuna presa una sola volta. L'ordine delle colonne non conta.

Con $m=n-k$ righe le sequenze non nulle sono $2^m-1$, quindi

$$n=2^{n-k}-1,\qquad n=2^m-1,\quad k=2^m-1-m.$$

(il codice $(3,1)$ è il codice a ripetizione.) Quindi esiste un codice di Hamming con parametri $(n,k)$ se e solo se $n=2^{n-k}-1$: per $(63,57)$ vale $2^6-1=63$, sì; per $(15,11)$ vale $2^4-1=15$, sì; per $(9,4)$ no ($2^5-1=31\ne9$); per $(6,3)$ no ($2^3-1=7\ne6$).

Esempio ($n=7$, $k=4$, $m=3$). La matrice di controllo della lezione ha per colonna $j$ il numero $j$ scritto in binario (bit meno significativo in alto): $$H=\begin{bmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\end{bmatrix}.$$ Con questa scelta la sindrome di un errore singolo, letta come numero binario, è proprio la posizione dell'errore.

Forma sistematica. Si scelgono le $n-k=m$ colonne dell'identità e si scrivono a destra, le altre $k$ colonne a sinistra (in qualunque ordine): $H=[A\mid I_m]$ e $G=\begin{bmatrix}I_k\\A\end{bmatrix}$. Per $(7,4)$ si ottiene (permutando le colonne di $H$ come $3,5,6,7,1,2,4$) $$H=\begin{bmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\end{bmatrix},\qquad G=\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\1&1&0&1\\1&0&1&1\\0&1&1&1\end{bmatrix}.$$ (le colonne di $A$ sono le sequenze di peso $\ge2$; $HG=0$ verificato con Python). Per $(15,11)$ le $11$ colonne di $A$ sono tutte le sequenze di $4$ bit di peso $\ge2$.

3. La distanza minima vale 3

Teorema. Ogni codice di Hamming ha $d_{min}=3$.

Dimostrazione. Per il teorema della sezione 2 di Matrice di controllo di parità, sindrome e cosetLa matrice di controllo di parità $H$ ($\ell\times n$) soddisfa $H\mathbf r=\mathbf 0\iff\mathbf r\in\mathcal C$; per un codice con generatrice $G$ ($n\times k$) vale $HG=0$ con $\operatorname{rango}(H)=n-k$, e se $G=\begin{bmatrix}I_k\A\end{bmatrix}$ allora $H=[A\mid I_{n-k}]$. La distanza minima è il minimo numero di colonne di $H$ linearmente dipendenti. La sindrome $\boldsymbol\sigma=H\boldsymbol\gamma$ della sequenza ricevuta $\boldsymbol\gamma=\mathbf c+\boldsymbol\varepsilon$ vale $H\boldsymbol\varepsilon$: dipende solo dall'errore. Le sequenze con la stessa sindrome formano un coset ($2^{n-k}$ coset di $2^k$ sequenze) e il decodificatore a minima distanza sceglie il coset leader, l'errore di peso minimo del coset: $\hat{\mathbf c}=\boldsymbol\gamma+\boldsymbol\varepsilon_{min}$. La probabilità di decodifica corretta sul BSC è la somma delle probabilità dei coset leader.Matrice di controllo di parità, sindrome e coset →, $d_{min}$ è il minimo numero di colonne di $H$ che sommano a $\mathbf 0$.

1. Nessuna parola di peso 1. Una parola di peso $1$ con l'$1$ in posizione $i$ darebbe $H\mathbf c=\mathbf h_i$, la colonna $i$: ma per costruzione in $H$ non ci sono colonne nulle.
2. Nessuna parola di peso 2. Con due $1$ in posizioni $i\ne j$ si avrebbe $H\mathbf c=\mathbf h_i+\mathbf h_j$, la somma di due colonne diverse: non può essere $\mathbf 0$ perché in $H$ non ci sono colonne ripetute.
3. Esiste una parola di peso 3. Si scelgono $i\ne j$. La somma $\mathbf h_i+\mathbf h_j$ non è nulla (le colonne sono diverse) e diversa da $\mathbf h_i$ e da $\mathbf h_j$ (perché né $\mathbf h_j$ né $\mathbf h_i$ sono nulle); quindi è una sequenza non nulla di $n-k$ bit diversa da $\mathbf h_i$ e $\mathbf h_j$, e siccome $H$ contiene tutte le sequenze non nulle, è una terza colonna $\mathbf h_k$ con $k\ne i,j$. Allora $\mathbf h_i+\mathbf h_j+\mathbf h_k=\mathbf 0$: la sequenza con tre $1$ in $i,j,k$ è una parola di codice. $\square$

Quindi corregge sempre $t=1$ errore (un errore nella posizione $j$ ha per sindrome la colonna $j$, e le colonne sono tutte diverse: si capisce dove è) e rivela sempre $2$ errori ($d_{min}-1$): con due errori in $i$ e $j$ la sindrome $\mathbf h_i+\mathbf h_j\ne\mathbf0$ segnala l'errore, ma il decodificatore, che interpreta la sindrome come un errore singolo in una terza posizione $k$, produce una parola sbagliata (rivelazione sì, correzione no). Il numero di parole di peso $3$ di $(7,4)$ è $7$: lo spettro dei pesi è $1,\,7,\,7,\,1$ per i pesi $0,3,4,7$ (verificato).

4. È un codice perfetto

Per un codice di Hamming $t=1$ e $n=2^{n-k}-1$, quindi $1+n=2^{n-k}$. Il bound di Hamming vale con l'uguaglianza: $$1-\frac1n\log_2\sum_{r=0}^1\binom nr=1-\frac1n\log_2(1+n)=1-\frac1n\log_2\!\left(2^{n-k}\right)=1-\frac{n-k}{n}=\frac kn.$$

Definizione. Un codice per cui le sfere di raggio $t$ attorno alle parole riempiono tutto lo spazio senza sovrapporsi (il bound di Hamming vale con l'uguaglianza) è un codice perfetto.

Significa che ogni sequenza di $n$ bit è a distanza $\le1$ da una (e una sola) parola: nella tabella dei coset (Matrice di controllo di parità, sindrome e cosetLa matrice di controllo di parità $H$ ($\ell\times n$) soddisfa $H\mathbf r=\mathbf 0\iff\mathbf r\in\mathcal C$; per un codice con generatrice $G$ ($n\times k$) vale $HG=0$ con $\operatorname{rango}(H)=n-k$, e se $G=\begin{bmatrix}I_k\A\end{bmatrix}$ allora $H=[A\mid I_{n-k}]$. La distanza minima è il minimo numero di colonne di $H$ linearmente dipendenti. La sindrome $\boldsymbol\sigma=H\boldsymbol\gamma$ della sequenza ricevuta $\boldsymbol\gamma=\mathbf c+\boldsymbol\varepsilon$ vale $H\boldsymbol\varepsilon$: dipende solo dall'errore. Le sequenze con la stessa sindrome formano un coset ($2^{n-k}$ coset di $2^k$ sequenze) e il decodificatore a minima distanza sceglie il coset leader, l'errore di peso minimo del coset: $\hat{\mathbf c}=\boldsymbol\gamma+\boldsymbol\varepsilon_{min}$. La probabilità di decodifica corretta sul BSC è la somma delle probabilità dei coset leader.Matrice di controllo di parità, sindrome e coset →) tutte le $2^{n-k}=n+1$ sindromi sono occupate, una dal caso senza errore e $n$ dagli errori singoli. Non ci sono coset leader di peso $2$.

Decodifica. Si calcola la sindrome $\boldsymbol\sigma=H\boldsymbol\gamma$; se è nulla la parola è valida; altrimenti $\boldsymbol\sigma$ coincide con una colonna $\mathbf h_j$ e si inverte il bit $j$.

Esempio ($(7,4)$ sistematico). $\mathbf b=[1,0,1,1]^T$: i primi quattro bit sono $1,0,1,1$ e le tre parità (righe $5,6,7$ di $G$) sono $b_1\oplus b_2\oplus b_4=1\oplus0\oplus1=0$, $b_1\oplus b_3\oplus b_4=1\oplus1\oplus1=1$, $b_2\oplus b_3\oplus b_4=0\oplus1\oplus1=0$, quindi $\mathbf c=G\mathbf b=[1,0,1,1,0,1,0]^T$. Se il canale sbaglia il bit $2$ si riceve $\boldsymbol\gamma=[1,1,1,1,0,1,0]^T$: $\boldsymbol\sigma=H\boldsymbol\gamma=[1,0,1]^T$, che è la colonna $2$ di $H$. Si inverte il bit $2$ e si ottiene $\hat{\mathbf c}=\mathbf c$, quindi $\hat{\mathbf b}=[1,0,1,1]^T$ (controllato con Python su tutti i $16\cdot7=112$ errori singoli).

5. Probabilità d'errore di parola

Il codice corregge tutti gli errori singoli, e con $\ge2$ errori la sequenza ricevuta cade nella sfera di un'altra parola (tutto lo spazio è coperto): la decisione è sempre sbagliata. Quindi, sul BSC, la probabilità d'errore di parola è esattamente $$P(E)=P(\text{almeno 2 errori su }n)=1-(1-P_{bit})^n-nP_{bit}(1-P_{bit})^{n-1}.$$

(valori calcolati con Python). Il tasso sale con $m$ ma la probabilità di avere due errori in una parola più lunga sale anch'essa: come $\binom n2P_{bit}^2$. Per $P_{bit}=10^{-2}$ il $(255,247)$ non protegge quasi più.

6. Modificare un codice di Hamming

• Aggiungere un bit di parità totale (codice di Hamming esteso): $c_{n+1}=c_1\oplus\dots\oplus c_n$. Tutte le parole hanno peso pari, le $7$ parole di peso $3$ di $(7,4)$ diventano di peso $4$ e il codice $(8,4)$ ha $d_{min}=4$ (spettro dei pesi $1,14,1$ per $0,4,8$): corregge $1$ errore e ne rivela $3$ (verificato con Python). La matrice di controllo ha una riga di tutti $1$ in più e una colonna nulla in più nelle righe precedenti: $H_{est}=\begin{bmatrix}H&\mathbf 0\\1\ \cdots\ 1&1\end{bmatrix}$.
• Aggiungere un bit che somma solo i bit di informazione, $c_{n+1}=\sum_{i=1}^kb_i$: non basta per salire a $d_{min}=4$. Per $(63,57)$ si prendono due colonne della parte di informazione, per esempio $\mathbf h_i=[1,1,0,0,0,0]^T$ e $\mathbf h_j=[1,1,1,0,0,0]^T$ (entrambe di peso $\ge2$): la loro somma è $[0,0,1,0,0,0]^T$, una colonna dell'identità, quindi esiste una parola di peso $3$ con due $1$ nella parte di informazione e uno in quella di parità; il nuovo bit, somma di due bit di informazione, vale $0$ e il peso resta $3$. Il codice $(64,57)$ ottenuto ha $d_{min}=3<5$, coerente con il bound di Hamming della sezione 1.
• Togliere colonne (codice accorciato): tolta, per esempio, la colonna $[1,1,1]^T$ da $(7,4)$ resta una $H$ $3\times6$ con colonne non nulle e distinte: $d_{min}=3$ (corregge sempre $1$ errore), ma non è di Hamming ($n=6\ne2^3-1$) e non è perfetto (la sindrome $111$ non è usata dai singoli errori).
• Duplicare una colonna (per esempio sostituire una colonna con un'altra già presente): due colonne uguali fanno scendere a $d_{min}=2$, e il codice rivela $1$ errore, non ne corregge nessuno (verificato).

Errori comuni

• Dire che esiste un codice di Hamming per ogni coppia $(n,k)$: serve $n=2^{n-k}-1$.
• Dire che il bound di Hamming garantisce l'esistenza: è solo una condizione necessaria.
• Contare nella sfera di raggio $t$ solo $\binom nt$ sequenze invece di $\sum_{r=0}^t\binom nr$ (sono le sequenze a distanza $\le t$).
• Per un codice di Hamming prendere $P(E)=P(\text{esattamente 2 errori})$: sono gli errori di almeno $2$ (anche $3,4,\dots$).
• Dimenticare che l'identità nella forma sistematica di $H$ sta a destra.

Domande d'esame

1. Mostrare che esiste un codice di Hamming $(63,57)$ e dire quanti errori corregge e rivela. $n-k=6$ e $2^6-1=63=n$: esiste. $d_{min}=3$: corregge $1$ errore, ne rivela $2$.
2. Dimostrare che $d_{min}=3$ per un codice di Hamming. Nessuna colonna nulla (niente peso $1$), nessuna colonna ripetuta (niente peso $2$), tre colonne sommano a zero perché la somma di due è un'altra colonna (peso $3$ esiste).
3. Verificare che il codice di Hamming raggiunge il bound di Hamming con l'uguaglianza. Con $t=1$: $1-\frac1n\log_2(1+n)$ e $1+n=2^{n-k}$ danno $\frac{k}{n}$.

Esercizi svolti

• Esercizio - porta parallela a 8 pin, Hamming (7,4), coset e canale con pin guasto (esame del 15 febbraio 2023, es. 157): porta parallela a 8 pin: Hamming (7,4), coset e canale con un pin guasto.
• Esercizio - codice (6,3) accorciato di Hamming, sindrome e peso minimo (esame del 6 settembre 2022, es. 146): codice (6,3) accorciato dal (7,4): non è di Hamming, ma ha $d_{min}=3$.
• Esercizio - codice di Hamming (63,57), bound di Hamming e bit di parità aggiunto (secondo compitino dell'11 gennaio 2022, es. 132): Hamming (63,57), matrice sistematica a pesi decrescenti e bound di Hamming con un bit aggiunto.