Esercizio 29codice di Hamming su 16 bit di dati

Quanti bit di controllo

Per $M$ bit di dati servono $K$ bit di controllo con

$$2^K - 1 \ge M + K.$$

Per $M = 16$: con $K = 4$ è $15 \ge 20$ falso; con $K = 5$ è $31 \ge 21$ vero. Quindi $K = 5$ e la parola è di $M + K = 21$ bit.

Disposizione dei bit

• Le posizioni sono numerate da 1 (la meno significativa, a destra) a 21 (a sinistra).
• I bit di controllo stanno nelle posizioni potenza di 2: 1, 2, 4, 8, 16.
• I 16 bit di dati occupano le altre 16 posizioni (3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, 17, 18, 19, 20, 21), con il primo bit del dato (a sinistra) nella posizione più alta, 21 (è la disposizione per cui i risultati coincidono con le opzioni dei temi).
• Il bit di controllo in posizione $2^i$ è lo XOR (parità pari) dei bit di dati le cui posizioni, scritte in binario, hanno il bit $i$ uguale a 1.

A. Dati 0100111000101011

Posizioni da 21 a 1 (le caselle $C_j$ sono i bit di controllo, da calcolare):

Ogni bit di controllo copre le posizioni con quel bit a 1 nel numero di posizione:

Parola memorizzata (posizione 21 a sinistra):

$$\texttt{010010110001011011111} \quad \Rightarrow \text{risposta d.}$$

B. Dati 0101101011101010

Con lo stesso procedimento i dati occupano le posizioni 21...3 saltando le potenze di 2; i bit di controllo risultano $C_1 = 0$, $C_2 = 1$, $C_4 = 1$, $C_8 = 0$, $C_{16} = 1$ (rispettivamente: parità dei bit 0,1,1,0,1,0,0,1,0,0, 0,0,1,1,1,1,0,1,0, 1,0,1,1,0,1,0,1,0, 0,1,1,1,0,1,0, 1,1,0,1,0). Parola memorizzata:

$$\texttt{010111010111001011010} \quad \Rightarrow \text{risposta d.}$$

C. Errore in lettura

Se si legge la parola A con il bit 13 invertito, si ricalcolano le cinque parità sulla parola ricevuta (ogni parità comprende il bit di controllo stesso): ciascun gruppo $i$ dà $0$ se è giusto e $1$ se contiene l'errore. Il numero binario formato dai cinque risultati è la sindrome:

$$13 = 01101_2 \;\Rightarrow\; \text{gruppi } 1, 4 \text{ e } 8 \text{ errati} \;\Rightarrow\; \text{sindrome} = 8 + 4 + 1 = 13.$$

La sindrome è la posizione del bit sbagliato: basta invertire il bit 13 per correggerlo. Se l'errore fosse in un bit di controllo (per esempio la posizione 8), la sindrome sarebbe 8 e si invertirebbe il bit di controllo; sindrome $0$ significa nessun errore (con un solo errore alla volta).

Verifica con un programma

def hamming(dati):
    """Codice SEC: dati MSB per primo, posizioni 1..n con il bit 1 a destra, check bit nelle potenze di 2."""
    m = len(dati)
    k = 0
    while 2 ** k < m + k + 1:
        k += 1
    n = m + k
    pos_dati = [p for p in range(n, 0, -1) if p & (p - 1)]       # posizioni non potenza di 2, dall'alto
    parola = {p: int(b) for p, b in zip(pos_dati, dati)}
    for i in range(k):
        p = 2 ** i
        parola[p] = sum(v for q, v in parola.items() if q & p and q != p and q & (q - 1)) % 2
    return parola, n

def stringa(parola, n):
    return "".join(str(parola[p]) for p in range(n, 0, -1))

def sindrome(parola, n):
    s, i = 0, 0
    while 2 ** i <= n:
        s |= (sum(v for q, v in parola.items() if q & 2 ** i) % 2) << i
        i += 1
    return s

pa, n = hamming("0100111000101011")
print(stringa(pa, n))                    # 010010110001011011111
pb, _ = hamming("0101101011101010")
print(stringa(pb, n))                    # 010111010111001011010

print(sindrome(pa, n))                   # 0: parola corretta
pa[13] ^= 1                              # errore nel bit 13
print(sindrome(pa, n))                   # 13: posizione del bit errato
pa[13] ^= 1
pa[8] ^= 1                               # errore in un bit di controllo
print(sindrome(pa, n))                   # 8

Errori comuni

• Sbagliare il numero di bit di controllo: la condizione è $2^K - 1 \ge M + K$ (con $K = 4$ si avrebbe $15 \ge 20$, falso): per 16 bit di dati sono 5, non 4.
• Mettere i bit di controllo in fondo o in testa invece che nelle posizioni potenza di 2.
• Numerare le posizioni da sinistra: le posizioni (e i gruppi di parità) si contano da 1 a destra; in una stringa scritta con la posizione 21 a sinistra il bit $C_1$ è l'ultimo a destra.
• Usare parità dispari invece di pari (le opzioni sono tutte a parità pari).
• Dimenticare che ogni bit di controllo copre solo le posizioni con il proprio bit a 1.