Coduri bloc și proprietăți

Definiții fundamentale

Codificarea

Codificarea este trecerea de la un sistem de semnale primare (alfabetul sursei A = {a₁, a₂, ..., aₘ}) la un sistem de semnale secundare (alfabetul codului X = {x₁, x₂, ..., xD}). Combinațiile de semnale secundare se numesc cuvinte de cod, iar totalitatea lor formează un cod C = {c₁, c₂, ..., cₘ}.

Cod bloc

Un cod bloc atribuie fiecărui simbol al sursei un cuvânt de cod de lungime fixă sau variabilă, independent de contextul în care apare acel simbol. Codurile bloc pot fi:

• Coduri uniforme — toate cuvintele de cod au aceeași lungime
• Coduri neuniforme — cuvintele de cod au lungimi diferite (lungimea medie mai mică decât a codurilor uniforme)

Tipuri de coduri

Cod singular vs. nesingular (regulat)

• Cod singular: cel puțin două semnale primare distincte au același cuvânt de cod — decodarea nu este posibilă
• Cod nesingular (regulat): toate cuvintele de cod sunt distincte — condiție necesară dar nu suficientă pentru decodare unică

Cod unic decodabil

Un cod C se numește unic decodabil dacă succesiunile de cuvinte de cod, corespunzătoare diferitelor succesiuni de lungime finită ale sursei, sunt distincte.

Altfel spus, orice secvență de simboluri de cod poate fi descompusă într-un singur mod în cuvinte de cod.

Cod prefix (instantaneu decodabil)

Un cod în care niciun cuvânt de cod nu este prefixul altui cuvânt de cod se numește cod cu proprietate de prefix (cod prefix, cod instantaneu sau cod ireductibil).

Proprietăți ale codului prefix:

• Se poate decodifica fiecare cuvânt imediat la recepționare, fără a aștepta cuvintele următoare
• Orice cod prefix este unic decodabil (dar reciproca nu este întotdeauna adevărată)

Exemplu: cod prefix vs. cod non-prefix

Fie sursa S = {s₁, s₂, s₃, s₄}:

Codul A este prefix: niciun cuvânt nu este prefixul altui cuvânt. Secvența 010110 se decodifică imediat: 0|10|110 → s₁ s₂ s₃.

Codul B nu este prefix: 0 este prefix al lui 01, care este prefix al lui 011, care este prefix al lui 0111. Secvența 0011 este ambiguă: ar putea fi 0|011 → s₁ s₃ sau 0|01|1 (invalid) — decodificarea necesită context suplimentar.

Inegalitatea Kraft

Teorema (Kraft): Condiția necesară și suficientă pentru existența unui cod prefix C = {c₁, c₂, ..., cₘ} cu un alfabet de cod de D simboluri și cu lungimile cuvintelor de cod l₁, l₂, ..., lₘ este:

Σ D^(-lᵢ) ≤ 1     (pentru i = 1, 2, ..., M)

Interpretare

Inegalitatea Kraft stabilește o condiție pe care lungimile cuvintelor de cod trebuie să o satisfacă pentru ca un cod prefix să poată exista. Nu garantează construcția codului, ci doar posibilitatea existenței sale.

Exemplu

Fie un cod binar (D = 2) cu lungimile l₁ = 1, l₂ = 2, l₃ = 3, l₄ = 3:

Σ 2^(-lᵢ) = 2⁻¹ + 2⁻² + 2⁻³ + 2⁻³
           = 0.5 + 0.25 + 0.125 + 0.125
           = 1.0 ≤ 1  ✓

Inegalitatea este satisfăcută, deci un cod prefix cu aceste lungimi poate exista.

Inegalitatea McMillan

Teorema (McMillan): Un cod este unic decodabil dacă și numai dacă lungimile cuvintelor de cod satisfac inegalitatea Kraft:

Σ D^(-lᵢ) ≤ 1

Semnificație

Inegalitatea McMillan extinde rezultatul lui Kraft: clasa codurilor unic decodabile satisface aceeași inegalitate ca și clasa codurilor prefix. Aceasta înseamnă că nu există niciun avantaj (în termeni de lungimi ale cuvintelor) în a folosi coduri unic decodabile non-prefix față de coduri prefix.

Arbori de cod

Codurile prefix au o reprezentare geometrică intuitivă prin grafuri arborescente:

• Rădăcina reprezintă începutul decodificării
• Din fiecare nod intern pornesc D arce (câte unul pentru fiecare simbol al alfabetului de cod)
• Nodurile frunză (terminale) corespund cuvintelor de cod
• Drumul de la rădăcină la fiecare frunză definește cuvântul de cod corespunzător

Pentru un cod binar prefix:

        (rădăcină)
       /          \
      0            1
     / \          / \
    00  01       10  11
              (s₂)  / \
                  110  111
                (s₃)  (s₄)

Cuvintele de cod corespund frunzelor: s₁ = 00, s₂ = 10, s₃ = 110, s₄ = 111 etc.

Proprietate importantă: într-un cod prefix, cuvintele de cod corespund numai nodurilor terminale (frunze), niciodată nodurilor intermediare. Dacă un cuvânt de cod ar corespunde unui nod intermediar, atunci el ar fi prefix al altui cuvânt — contradicție.

Lungimea medie a codului

Lungimea medie a cuvintelor de cod este:

L = Σ P(aₖ) · lₖ     (pentru k = 1, 2, ..., M)

Din prima teoremă a lui Shannon:

H(X) / log₂(D) ≤ L

Se caută codul cu L minim (cod compact sau cvasioptimal).

Puncte cheie pentru examen

• Cod prefix (instantaneu): niciun cuvânt nu este prefix al altuia — decodare imediată
• Orice cod prefix este unic decodabil, dar nu orice cod unic decodabil este prefix
• Inegalitatea Kraft: Σ D^(-lᵢ) ≤ 1 — condiție necesară și suficientă pentru existența codului prefix
• Inegalitatea McMillan: aceeași inegalitate se aplică și codurilor unic decodabile
• Nu există avantaj de lungime în a folosi coduri unic decodabile non-prefix
• Arborele de cod: codurile prefix corespund nodurilor frunză ale arborelui
• Lungimea medie: L = Σ P(aₖ) · lₖ, limitată inferior de H(X) / log₂(D)