Teoremele lui Shannon

Context

Claude Shannon a publicat în 1948 lucrarea fundamentală „A Mathematical Theory of Communication", punând bazele teoriei informației. Cele două teoreme ale sale stabilesc limitele fundamentale ale compresiei datelor și ale transmisiei fiabile prin canale cu zgomot.

Prima teoremă a lui Shannon (Codarea surselor)

Enunț

Pentru orice sursă omogenă cu entropia H(X) și un alfabet de cod cu D simboluri, există un cod unic decodabil a cărui lungime medie a cuvintelor de cod L satisface:

H(X) / log₂(D) ≤ L < H(X) / log₂(D) + 1

Interpretare

Prima teoremă stabilește limita inferioară a compresiei: nu se poate comprima o sursă de informație sub entropia sa, dar se poate ajunge arbitrar de aproape de această limită.

• Limita inferioară: L_min = H(X) / log₂(D) — lungimea medie minimă teoretică
• Limita superioară: L_min + 1 — întotdeauna se poate construi un cod cu lungimea medie mai mică decât această valoare

Cazul binar (D = 2)

Pentru coduri binare (D = 2), relația devine:

H(X) ≤ L < H(X) + 1

deoarece log₂(2) = 1.

Exemplu numeric

Fie o sursă cu entropia H(X) = 4.0354 biți/caracter codată binar (D = 2):

Lungime medie minimă: L_min = H(X) / log₂(2) = 4.0354
Limita superioară:    L_max = 4.0354 + 1 = 5.0354

Dacă L obținut = 4.0714, verificăm:
  4.0354 ≤ 4.0714 ≤ 5.0354  ✓  (prima teoremă verificată)

Eficiența codului: η = H(X) / L = 4.0354 / 4.0714 = 0.9911 (99.11%)
Redundanța codului: R = 1 - η = 0.0089 (0.89%)

A doua teoremă a lui Shannon (Codarea canalului)

Enunț

Pentru orice canal de transmisie cu capacitatea C, dacă rata de transmisie R este mai mică decât capacitatea (R < C), atunci există un sistem de codare care permite transmisia cu o probabilitate de eroare arbitrar de mică. Dacă R > C, transmisia fără erori nu este posibilă.

Interpretare

A doua teoremă stabilește limita fundamentală a transmisiei fiabile:

• Dacă R ≤ C: Există o metodă de codare prin care probabilitatea de eroare poate fi făcută oricât de mică (dar niciodată zero cu lungime finită de cod)
• Dacă R > C: Nu există nicio metodă de codare care să permită transmisie fiabilă — erorile sunt inevitabile

Relația cu capacitatea

C = max I(X;Y) = max [H(Y) - H(Y|X)]
    P(X)         P(X)

Viteza de transmisie R (în biți/simbol de canal) trebuie să satisfacă R ≤ C pentru ca transmisia să fie fiabilă.

Implicații practice

Din prima teoremă

Din a doua teoremă

Legătura între cele două teoreme

Cele două teoreme lucrează complementar:

1. Prima teoremă (codarea surselor): elimină redundanța naturală a sursei, comprimând mesajul aproape de entropia H(X)
2. A doua teoremă (codarea canalului): adaugă redundanță controlată pentru protecția împotriva erorilor de canal

Sursă  →  Coder de sursă   →  Coder de canal  →  Canal  →  Decoder
          (elimină redundanța)   (adaugă redundanță)         (corectează erori)
              Prima teoremă        A doua teoremă

Eficiența și redundanța codului

Din prima teoremă derivă măsurile de performanță ale codului:

Capacitatea codului: C_cod = log₂(D) (valoarea maximă a entropiei alfabetului de cod)

Eficiența codului:

η = H(X) / (L · log₂(D))

Redundanța codului:

R = 1 - η = 1 - H(X) / (L · log₂(D))

Un cod este absolut optimal dacă η = 1, adică L = H(X) / log₂(D).

Puncte cheie pentru examen

• Prima teoremă (codarea surselor): H(X)/log₂(D) ≤ L < H(X)/log₂(D) + 1
• Stabilește limita inferioară a compresiei — nu putem comprima sub entropie
• A doua teoremă (codarea canalului): transmisie fiabilă dacă și numai dacă R ≤ C
• Capacitatea canalului C este limita superioară a ratei de transmisie fiabilă
• Cele două teoreme sunt complementare: prima elimină redundanța, a doua adaugă redundanță controlată
• Eficiența codului: η = H(X) / (L · log₂(D)); redundanța: R = 1 - η
• Un cod cu η = 1 se numește absolut optimal