05 - Codici correttori d'errore: distanza di Hamming, bound di Hamming e Singleton

Hai sette bit che arrivano da un canale rumoroso e sai che al più uno è sbagliato. Se i sette bit sono una parola scelta bene in un codice di sole 16 parole, puoi ritrovare quale bit è da correggere con tre somme modulo 2. Il numero che decide quanti errori un codice sa correggere è la distanza minima d: un codice con distanza d corregge ogni schema di al più t = ⌊(d-1)/2⌋ errori e ne rivela fino a d-1. Il codice di Hamming (7,4) ha d = 3, corregge un errore e riempie lo spazio dei vettori senza sprechi; i due limiti di questo articolo, quello di Hamming e quello di Singleton, dicono quanto un codice può spingersi oltre. Costruisco il (7,4) da zero, lo provo su tutti i vettori d'errore piccoli e verifico i limiti per enumerazione, perché due dei risultati che si ripetono negli appunti (la matrice di controllo e il rapporto fra sindrome e posizione) si sbagliano facilmente a mano.

La distanza di Hamming e la sua geometria

La distanza di Hamming dH(x, y) fra due stringhe di uguale lunghezza è il numero di posizioni in cui differiscono. Per x = 1011 e y = 1101 differiscono la seconda e la terza posizione, quindi dH = 2. Le tre proprietà che la rendono una distanza vera sono:

• non negatività, con dH(x, y) = 0 se e solo se x = y;
• simmetria, dH(x, y) = dH(y, x);
• disuguaglianza triangolare, dH(x, z) ≤ dH(x, y) + dH(y, z).

Non c'è un ordine fra queste proprietà, e l'unica che serve davvero più avanti è l'ultima: da essa discende tutta la teoria della correzione, perché permette di dire che due sfere di raggio t non si toccano se i centri distano abbastanza. Le altre due ti dicono che puoi parlare di «sfera» senza ambiguità.

Una sfera di Hamming di raggio t attorno a una stringa di lunghezza n contiene tutte le stringhe a distanza al più t. Scegliere esattamente j posizioni da capovolgere si può fare in binom(n, j) modi, quindi il volume è V(n, t) = Σj=0..t binom(n, j). Con n = 10 e t = 2 si ottiene 1 + 10 + 45 = 56, il numero che il listato sui limiti ricalcola più avanti.

Perché t = ⌊(d-1)/2⌋: la disuguaglianza triangolare al lavoro

Sia d la distanza minima di un codice, cioè la più piccola distanza fra due parole diverse. Prendi t con 2t + 1 ≤ d e supponi che una stringa ricevuta y sia a distanza al più t da due parole c e c'. Allora dH(c, c') ≤ dH(c, y) + dH(y, c') ≤ 2t < d, contro la definizione di d. Quindi y è vicina a una sola parola e la decodifica a distanza minima, cioè «scegli la parola più vicina», restituisce quella giusta. Il massimo t intero con 2t + 1 ≤ d è ⌊(d-1)/2⌋. Guruswami, Rudra e Sudan (proposizione 1.4.2) enunciano l'equivalenza completa: distanza d, correzione di ⌊(d-1)/2⌋ errori e rivelazione di d-1 errori sono la stessa proprietà.

La differenza fra rivelare e correggere è concreta. Con d = 2, come nel bit di parità, riconosci un errore singolo (la parola ricevuta non è nel codice) ma non sai dove sia, perché a distanza 1 ci sono più parole; con d = 3 sai anche correggere. La tabella del listato sul limite di Singleton conferma i parametri: il codice (4,3) con un bit di parità ha d = 2 e t = 0.

Il codice di Hamming (7,4) costruito e provato

Un codice lineare [n, k] è un sottospazio di dimensione k di F2n, con 2k parole. Si codifica con una matrice generatrice G di dimensione k × n, c = mG modulo 2, e si controlla con una matrice di controllo di parità H di dimensione (n-k) × n tale che GHT = 0. In forma sistematica, G = [I | P] ed H = [PT | I]: se sbagli una sola posizione di PT le due matrici smettono di essere compatibili, e per questo il listato comincia calcolando GHT. Poi codifica tutti i 16 messaggi, misura la distanza minima per enumerazione, scrive la sindrome di ogni errore singolo e decodifica ogni vettore d'errore di peso 0, 1 e 2 su ciascuna delle 16 parole.

from itertools import combinations, product

# Matrice generatrice in forma sistematica [I4 | P] e matrice di controllo [P^T | I3]
G = [[1, 0, 0, 0, 1, 1, 0],
     [0, 1, 0, 0, 1, 0, 1],
     [0, 0, 1, 0, 0, 1, 1],
     [0, 0, 0, 1, 1, 1, 1]]
H = [[1, 1, 0, 1, 1, 0, 0],
     [1, 0, 1, 1, 0, 1, 0],
     [0, 1, 1, 1, 0, 0, 1]]


def codifica(m):
    return tuple(sum(m[i] * G[i][j] for i in range(4)) % 2 for j in range(7))


def sindrome(r):
    return tuple(sum(r[j] * H[i][j] for j in range(7)) % 2 for i in range(3))


def dist(x, y):
    return sum(a != b for a, b in zip(x, y))


# 1) G e H sono compatibili: G H^T = 0 modulo 2
GHt = [[sum(G[i][j] * H[k][j] for j in range(7)) % 2 for k in range(3)] for i in range(4)]
print("G H^T =", GHt)

# 2) Le 16 parole e la distanza minima, per enumerazione
parole = {m: codifica(m) for m in product((0, 1), repeat=4)}
dmin = min(dist(a, b) for a in parole.values() for b in parole.values() if a != b)
print("parole:", len(set(parole.values())), " distanza minima:", dmin)
c = parole[(1, 0, 1, 0)]
print("m = 1010  ->  c =", "".join(map(str, c)))

# 3) La sindrome di un errore singolo in posizione j e' la colonna j di H
print("posizione errata -> sindrome")
tabella = {}
for j in range(7):
    e = [0] * 7
    e[j] = 1
    tabella[sindrome(e)] = j
    print(f"  {j + 1} -> {''.join(map(str, sindrome(e)))}")


# 4) Decodifica per sindrome provata su TUTTI i vettori d'errore di peso 0, 1 e 2, per tutte le 16 parole
def decodifica(r):
    s = sindrome(r)
    if s == (0, 0, 0):
        return r
    j = tabella[s]
    return tuple(b ^ (i == j) for i, b in enumerate(r))


risultati = {0: [0, 0], 1: [0, 0], 2: [0, 0]}  # peso -> [corretti, sbagliati]
for cw in parole.values():
    for peso in (0, 1, 2):
        for pos in combinations(range(7), peso):
            r = tuple(b ^ (i in pos) for i, b in enumerate(cw))
            risultati[peso][0 if decodifica(r) == cw else 1] += 1
for peso, (ok, ko) in risultati.items():
    print(f"errori di peso {peso}: {ok} corretti, {ko} sbagliati")

# 5) Con le colonne di H in ordine binario (1..7) la sindrome, letta come numero, e' la posizione
Hc = [[(j >> b) & 1 for j in range(1, 8)] for b in (2, 1, 0)]
for j in range(7):
    e = [0] * 7
    e[j] = 1
    s = [sum(e[k] * Hc[i][k] for k in range(7)) % 2 for i in range(3)]
    assert int("".join(map(str, s)), 2) == j + 1
print("H con colonne 1..7 in binario: sindrome = posizione, verificato per le 7 posizioni")

# Uscita:
# G H^T = [[0, 0, 0], [0, 0, 0], [0, 0, 0], [0, 0, 0]]
# parole: 16  distanza minima: 3
# m = 1010  ->  c = 1010101
# posizione errata -> sindrome
#   1 -> 110
#   2 -> 101
#   3 -> 011
#   4 -> 111
#   5 -> 100
#   6 -> 010
#   7 -> 001
# errori di peso 0: 16 corretti, 0 sbagliati
# errori di peso 1: 112 corretti, 0 sbagliati
# errori di peso 2: 0 corretti, 336 sbagliati
# H con colonne 1..7 in binario: sindrome = posizione, verificato per le 7 posizioni

La prima riga dell'uscita mostra che G e H sono compatibili, la seconda che le 16 parole sono distinte e distano almeno 3: il codice corregge un errore e ne rivela due. Il messaggio 1010 diventa 1010101, somma della prima e della terza riga di G modulo 2. La sindrome di un errore nella posizione j è la colonna j di H: le sette colonne, 110, 101, 011, 111, 100, 010, 001, sono tutti i vettori non nulli di tre bit, una sola volta ciascuno. Per questo ogni errore singolo ha una sindrome diversa e la decodifica si riduce a leggere la tabella.

Nell'ultima parte dell'uscita sta il risultato principale: su 16 · 7 = 112 errori singoli la decodifica è giusta 112 volte; su 16 · 21 = 336 errori doppi è sbagliata 336 volte. Non è sfortuna: ogni vettore dista al più 1 da una sola parola, quindi un errore doppio finisce sempre vicino a un'altra parola e viene «corretto» verso quella sbagliata. È anche la ragione per cui il codice è perfetto. Per leggere la sindrome come numero di posizione serve un'altra disposizione: se ordini le colonne di H secondo i numeri binari da 1 a 7, la sindrome letta in binario è la posizione dell'errore, come verifica l'ultima riga. Le due versioni del codice sono equivalenti a meno di una permutazione delle posizioni, perché hanno le stesse sette colonne in un ordine diverso.

Il limite di Hamming e i codici perfetti

Se le sfere di raggio t attorno alle 2k parole non si sovrappongono, stanno tutte nei 2n punti dello spazio, quindi 2k · V(n, t) ≤ 2n, cioè k ≤ n - log2 V(n, t). È il limite di Hamming (Guruswami, Rudra e Sudan, teorema 1.7.2, che lo enunciano per un alfabeto di q simboli). Un codice che lo raggiunge con l'uguaglianza è perfetto: le sfere riempiono lo spazio senza lasciare punti scoperti. MacKay (§13.3) riformula l'uguaglianza così: il numero di vettori di rumore in una sfera deve essere pari al numero di sindromi possibili, V(n, t) = 2n-k.

Il listato usa solo interi esatti. Controlla che il (7,4) e il codice di Golay (23,12) soddisfino l'uguaglianza, calcola il massimo k consentito per n = 15 e t = 2, cerca per n fino a 100 i casi in cui V(n, t) è una potenza di due, costruisce il codice BCH (15,7) per verificare se il limite sia stretto e, in coda, confronta Hamming e Singleton su un alfabeto di 256 simboli.

import math
from itertools import product


def V(n, t):
    """Numero di punti di una sfera di Hamming di raggio t in {0,1}^n."""
    return sum(math.comb(n, j) for j in range(t + 1))


def k_max_hamming(n, t):
    """Massimo k intero con 2^k * V(n,t) <= 2^n (limite di Hamming), in aritmetica intera esatta."""
    k = 0
    while 2 ** (k + 1) * V(n, t) <= 2**n:
        k += 1
    return k


# 1) Volumi e limite di Hamming per casi noti
print("V(10,2) =", V(10, 2))
print("(7,4), t=1:  2^4 * V(7,1) =", 2**4 * V(7, 1), " 2^7 =", 2**7)
print("Golay (23,12), t=3:  V(23,3) =", V(23, 3), " 2^11 =", 2**11)
print("n=15, t=2:  V =", V(15, 2), " k massimo per il limite di Hamming =", k_max_hamming(15, 2))

# 2) Quali (n, t) soddisfano la condizione numerica V(n,t) = 2^m, per n fino a 100
# (esclusi i codici a ripetizione di lunghezza dispari, che hanno t = (n-1)/2)
print("(n, t) con V(n,t) potenza di due, 1 <= t < (n-1)/2, n <= 100:")
for n in range(3, 101):
    for t in range(1, (n - 1) // 2):
        v = V(n, t)
        if v & (v - 1) == 0:
            print(f"  n={n:3d} t={t:2d}  V = 2^{v.bit_length() - 1}")

# 3) Il codice BCH (15,7) con polinomio generatore g(x) = x^8 + x^7 + x^6 + x^4 + 1: distanza minima per enumerazione
g = 0b111010001  # coefficienti da x^8 a x^0


def moltiplica(a, b):
    """Prodotto di polinomi su F2, con interi come vettori di bit."""
    r = 0
    while b:
        if b & 1:
            r ^= a
        a <<= 1
        b >>= 1
    return r


pesi = [bin(moltiplica(m, g)).count("1") for m in range(1, 2**7)]
print("BCH (15,7): parole non nulle", len(pesi), " peso minimo =", min(pesi))

# 4) Reed-Solomon [255,223] su un alfabeto di 256 simboli: limite di Hamming q-ario (Guruswami-Rudra-Sudan, teorema 1.7.2)
#    contro il limite di Singleton, con t = 16
q, n, t = 256, 255, 16
volume = sum(math.comb(n, i) * (q - 1) ** i for i in range(t + 1))
k_hamming = 0
while q ** (k_hamming + 1) * volume <= q**n:
    k_hamming += 1
print(f"q=256, n=255, t=16:  k massimo per Hamming = {k_hamming},  k massimo per Singleton (d=33) = {n - 33 + 1}")

# Uscita:
# V(10,2) = 56
# (7,4), t=1:  2^4 * V(7,1) = 128  2^7 = 128
# Golay (23,12), t=3:  V(23,3) = 2048  2^11 = 2048
# n=15, t=2:  V = 121  k massimo per il limite di Hamming = 8
# (n, t) con V(n,t) potenza di due, 1 <= t < (n-1)/2, n <= 100:
#   n=  7 t= 1  V = 2^3
#   n= 15 t= 1  V = 2^4
#   n= 23 t= 3  V = 2^11
#   n= 31 t= 1  V = 2^5
#   n= 63 t= 1  V = 2^6
#   n= 90 t= 2  V = 2^12
# BCH (15,7): parole non nulle 127  peso minimo = 5
# q=256, n=255, t=16:  k massimo per Hamming = 228,  k massimo per Singleton (d=33) = 223

Il (7,4) soddisfa 16 · 8 = 128 = 27; il codice di Golay (23,12) soddisfa V(23, 3) = 2048 = 211. Per n = 15 e t = 2 il limite ammette k ≤ 8, ma il codice BCH (15,7), con polinomio generatore x8 + x7 + x6 + x4 + 1, ha distanza 5 e k = 7: il limite è un tetto, non garantisce che un codice con quei parametri esista. La ricerca per n ≤ 100 mostra altre coincidenze numeriche, fra cui n = 90 e t = 2 (V = 4096 = 212). Soddisfare la condizione numerica è dunque necessario ma non sufficiente: MacKay (§13.3) elenca come soli codici binari perfetti non banali i codici di Hamming (t = 1, n = 2m - 1), i codici a ripetizione di lunghezza dispari e il codice di Golay, e conclude che non ce ne sono altri.

Due precisazioni su fatti che si ripetono male: i codici a ripetizione sono perfetti solo per n dispari, perché con n pari ci sono stringhe a metà strada fra due parole, a distanza uguale da entrambe; e il codice di Hamming prende il nome da Richard Hamming, non da Shannon, che nel suo articolo del 1948 lo cita con attribuzione a Hamming (così riferiscono Guruswami, Rudra e Sudan nelle note bibliografiche; non ho letto il passo di Shannon). La rarità dei codici perfetti è un fatto pratico: la maggior parte dei codici usati sacrifica la perfezione, e con essa la facile decodifica per sindrome, in cambio di distanza o di lunghezze a piacere.

Il limite di Singleton e i codici MDS

Il limite di Singleton riguarda la distanza e vale per qualunque alfabeto: un codice (n, k, d)q ha k ≤ n - d + 1, ovvero d ≤ n - k + 1 (Guruswami, Rudra e Sudan, teorema 4.3.1). La dimostrazione è breve: se tronchi ogni parola ai primi n - d + 1 simboli, i prefissi di due parole diverse devono restare diversi, perché altrimenti le due parole coinciderebbero in n - d + 1 posizioni e differirebbero in al più d - 1, contro la distanza minima d. Allora le parole sono al più quanti sono i prefissi possibili, cioè qk ≤ qn-d+1. I codici con d = n - k + 1 si chiamano MDS, dall'inglese maximum distance separable.

Il listato ha due parti. Nella prima prova tutti i codici lineari binari con n ≤ 6 e k ≤ 4: ogni codice ha una base, cioè k vettori indipendenti, quindi basta provare ogni sottoinsieme di k vettori non nulli e prendere la miglior distanza. Nella seconda costruisce il codice di Reed-Solomon [7, 3] sul campo GF(8) come codice di valutazione: la parola associata a un polinomio f di grado minore di 3 è (f(1), f(α), …, f(α6)), con α radice di x3 + x + 1. La distanza minima segue dal fatto che un polinomio non nullo di grado minore di 3 ha al più due radici.

import math
from itertools import combinations, product


def migliore_distanza_lineare(n, k):
    """Massima distanza minima fra TUTTI i codici lineari binari [n,k]: ogni codice ha una base,
    cioe' k vettori non nulli indipendenti, quindi basta provare tutti i sottoinsiemi di k vettori."""
    migliore = 0
    for base in combinations(range(1, 2**n), k):
        pesi = []
        for mask in range(1, 2**k):
            w = 0
            for i in range(k):
                if (mask >> i) & 1:
                    w ^= base[i]
            pesi.append(bin(w).count("1") if w else 0)
        if min(pesi) > 0:  # w = 0 per qualche combinazione: i vettori non sono indipendenti
            migliore = max(migliore, min(pesi))
    return migliore


def hamming_t_max(n, k):
    """Massimo t per cui il limite di Hamming ammette 2^k parole: 2^k * V(n,t) <= 2^n."""
    migliore = 0
    for t in range(0, n + 1):
        v = sum(math.comb(n, j) for j in range(t + 1))
        if 2**k * v <= 2**n:
            migliore = t
    return migliore


print(" n  k  d migliore  Singleton n-k+1  t reale  t max (Hamming)")
for n, ks in ((3, (1, 2)), (4, (1, 2, 3)), (5, (1, 2, 3, 4)), (6, (1, 2, 3, 4))):
    for k in ks:
        d = migliore_distanza_lineare(n, k)
        print(f"{n:2d} {k:2d}  {d:9d}  {n - k + 1:15d}  {(d - 1) // 2:7d}  {hamming_t_max(n, k):14d}")

# Reed-Solomon [7,3] su GF(8): le parole sono (f(a^0), ..., f(a^6)) con f di grado < 3. Campo con x^3 + x + 1.
LOG, EXP = {}, [0] * 14
x = 1
for i in range(7):
    EXP[i] = EXP[i + 7] = x
    LOG[x] = i
    x <<= 1
    if x & 8:
        x ^= 0b1011


def mul(a, b):
    return 0 if a == 0 or b == 0 else EXP[LOG[a] + LOG[b]]


def valuta(coef, punto):
    r = 0
    for c in reversed(coef):  # schema di Horner; la somma nel campo e' lo XOR
        r = mul(r, punto) ^ c
    return r


punti = [EXP[i] for i in range(7)]
parole = [tuple(valuta(f, p) for p in punti) for f in product(range(8), repeat=3)]
dmin = min(sum(a != b for a, b in zip(u, v)) for u, v in combinations(parole, 2))
print()
print(f"RS [7,3] su GF(8): {len(parole)} parole, distanza minima {dmin} = n-k+1 = {7 - 3 + 1}")

# Decodifica a distanza minima di TUTTI i vettori d'errore di peso <= 3 sulla parola nulla
# (per linearita' le altre parole si comportano allo stesso modo)
for peso in (0, 1, 2, 3):
    corretti = sbagliati = 0
    for pos in combinations(range(7), peso):
        for val in product(range(1, 8), repeat=peso):
            r = [0] * 7
            for p_, v_ in zip(pos, val):
                r[p_] = v_
            d_zero = peso
            vicino = min(sum(a != b for a, b in zip(r, w)) for w in parole if any(w))
            # corretto se la parola nulla e' strettamente la piu' vicina
            if d_zero < vicino:
                corretti += 1
            else:
                sbagliati += 1
    print(f"errori di peso {peso}: {corretti} decodificati bene, {sbagliati} no o ambigui")

# Uscita:
#  n  k  d migliore  Singleton n-k+1  t reale  t max (Hamming)
#  3  1          3                3        1               1
#  3  2          2                2        0               0
#  4  1          4                4        1               1
#  4  2          2                3        0               0
#  4  3          2                2        0               0
#  5  1          5                5        2               2
#  5  2          3                4        1               1
#  5  3          2                3        0               0
#  5  4          2                2        0               0
#  6  1          6                6        2               2
#  6  2          4                5        1               1
#  6  3          3                4        1               1
#  6  4          2                3        0               0
#
# RS [7,3] su GF(8): 512 parole, distanza minima 5 = n-k+1 = 5
# errori di peso 0: 1 decodificati bene, 0 no o ambigui
# errori di peso 1: 49 decodificati bene, 0 no o ambigui
# errori di peso 2: 1029 decodificati bene, 0 no o ambigui
# errori di peso 3: 0 decodificati bene, 12005 no o ambigui

La tabella mostra che, fra i codici binari esaminati, solo quelli banali toccano il limite: con k = 1 (ripetizione, d = n) e con k = n - 1 (un bit di parità, d = 2) vale d = n - k + 1, mentre per esempio n = 5, k = 2 arriva al massimo a d = 3 contro un limite di 4. Nella stessa tabella la colonna di Hamming coincide con il t reale in tutti i 13 casi, quindi in questo intervallo il limite di Hamming è stretto, anche se non vale in generale (il caso n = 15, t = 2 sopra). Il codice Reed-Solomon [7, 3] su GF(8) invece è MDS: d = 5 = n - k + 1. Su 1 + 49 + 1029 vettori d'errore di peso al più 2, la decodifica a distanza minima è sempre riuscita, e nessuno dei 12005 vettori di peso 3 viene decodificato in modo univoco.

Lo stesso schema su GF(256) dà il codice Reed-Solomon [255, 223], con d = 255 - 223 + 1 = 33 e quindi t = 16 simboli corretti, dove ogni simbolo è un byte. Questo è un calcolo dal limite, non un'enumerazione: la costruzione è identica a quella del listato, ma 256223 parole non si enumerano. La differenza con i codici binari è l'alfabeto: l'esistenza di codici MDS richiede un alfabeto grande, e nella costruzione del listato la lunghezza è n = q - 1, cioè 7 su GF(8) e 255 su GF(256).

Come si confrontano i due limiti

Il limite di Hamming sfrutta la geometria dello spazio, le sfere che non si sovrappongono, e dà un tetto al numero di parole una volta fissato t. Il limite di Singleton sfrutta la struttura dei prefissi e dà un tetto alla distanza una volta fissati n e k. Nel campione binario del listato Hamming è il più stringente: il codice (4,2) ha d = 2, Singleton ammetterebbe 3, e Hamming ammette t = 0. Su un alfabeto di 256 simboli le parti si invertono: l'ultima riga del secondo listato dice che per n = 255 e t = 16 Hamming ammette k ≤ 228, mentre Singleton ammette k ≤ 223, valore che Reed-Solomon raggiunge. Il codice [255, 223] è dunque MDS ma non perfetto: le sue sfere non riempiono lo spazio, e nessun limite sulle sfere ne decide la qualità.

La scelta del codice è quindi una scelta di alfabeto prima che di limite. Se i dati sono byte e gli errori colpiscono simboli interi, un codice MDS usa nel modo migliore la ridondanza; se i bit sono indipendenti e rari, la sfera di Hamming è l'immagine giusta e il codice di Hamming o un BCH sono i candidati naturali. Non ho misurato prestazioni su canali reali: il confronto è fra i parametri teorici dei codici.

Errori frequenti

• Confondere d con il numero di errori correggibili. Con d = 5 correggi t = 2 errori, non 5; ne riveli 4.
• Credere che il limite di Hamming sia raggiunto: lo è solo dai codici perfetti. Il BCH (15,7) resta a k = 7 contro un tetto di 8.
• Dichiarare perfetto un codice a ripetizione di lunghezza pari. Per n pari non lo è.
• Ordinare male le colonne di H e leggere la sindrome come posizione. Vale solo con le colonne in ordine binario; nella forma sistematica serve la tabella.
• Applicare Singleton come se fosse stretto per i codici binari. Per k intermedio non lo è, come mostra la tabella.

Tre dei cinque errori (il secondo, il terzo e il quinto) hanno la stessa origine: trattare come raggiunto un limite che è soltanto un tetto. Quando una formula ha un «≤», chiediti quale codice la rende uguaglianza e se quel codice esiste. Il quarto è di notazione: la regola «sindrome uguale posizione» dipende da come ordini le colonne.

Che cosa sai fare adesso

Sai definire la distanza di Hamming, dimostrare perché t = ⌊(d-1)/2⌋ e usare la tabella delle sindromi per correggere un errore del codice (7,4), compresi i suoi limiti: l'errore doppio non si corregge, si sbaglia con certezza. Sai calcolare il limite di Hamming con interi esatti e riconoscere che la coincidenza numerica non basta a garantire l'esistenza (n = 90, t = 2). Sai enunciare e dimostrare il limite di Singleton e riconoscere un codice MDS. Il codice di Hamming è un esempio costruttivo di ciò che il teorema di Shannon dell'articolo 4 promette solo in esistenza; e quando i bit non servono più, la compressione con perdita dell'articolo 6 ripete lo stesso schema con un'altra grandezza. Per rivedere il ruolo dell'informazione mutua, che entra nel limite di Shannon, usa l'articolo 2. Tutti gli articoli sono nell'indice della serie.

Domande frequenti

Nella stessa serie trovi anche l'articolo 01 sull'entropia di Shannon e l'articolo 03 sulla codifica di sorgente.