Inegalitatea Kraft

În teoria codurilor , inegalitatea Kraft oferă, având în vedere un set de lungimi de cuvinte cod, o condiție necesară și suficientă pentru existența unui cod prefix și a unui cod unic decodabil . Inegalitatea lui Kraft poartă numele lui Leon Kraft . A fost publicat de Kraft în 1949. Cu toate acestea, articolul Kraft se ocupă doar de coduri de prefix și atribuie Raymond Redheffer analiza care duce la inegalitate .

Definiție formală

Este un alfabet și un cod unic decodabil peste o dimensiune a alfabetului , notând lungimile cuvintelor cod , apoi ${\ displaystyle {\ mathcal {S}} = \ {s_ {0}, s_ {1}, \ dots s_ {n-1} \}}$ $\ mathcal {C}$ ${\ mathcal {S}}$ ${\ mathcal {T}}$ $r$ ${\ displaystyle \ ell _ {i} = | {\ mathcal {C}} (s_ {i}) |}$

${\ displaystyle \ sum _ {i = 0} ^ {n-1} r ^ {- \ ell _ {i}} \ leqslant 1.}$

În schimb, să se satisfacă inegalitatea lui Kraft, apoi există un cod de prefix de dimensiune pe un alfabet de dimensiune cu aceste lungimi de cod. ${\ displaystyle \ ell _ {0}, \ ell _ {1}, \ dots \ ell _ {n-1}}$ $nu$ $r$

Cazul codurilor de prefix

Prin ne limităm la codurile de prefix, vom găsi o simplă demonstrație a sensului înainte bazată pe bijectie între -ary copaci și coduri prefix $r$

Inegalitatea Kraft devine atunci:

Pentru orice copac- aer, cu toate frunzele sale și adâncimea frunzei : ${\ mathcal {A}}$ $r$ ${\ displaystyle {\ mathcal {L}} ({\ mathcal {A}})}$ ${\ displaystyle d (\ ell)}$ $\ Ell$

∑ℓ∈L(LA)r-d(ℓ)⩽1{\ displaystyle \ sum _ {\ ell \ in {\ mathcal {L}} ({\ mathcal {A}})} r ^ {- d (\ ell)} \ leqslant 1}

{\ displaystyle \ sum _ {\ ell \ in {\ mathcal {L}} ({\ mathcal {A}})} r ^ {- d (\ ell)} \ leqslant 1}

Demonstrație

Prin inducție structurală pe copac: evident dacă este o frunză sau goală. ${\ mathcal {A}}$

Dacă , deoarece inegalitatea lui Kraft este valabilă pentru toate , observați adâncimea frunzei din subarborele căruia îi aparține. Apoi avem: ${\ displaystyle {\ mathcal {A}} = {\ mathcal {N}} ({\ mathcal {A}} _ {0}, {\ mathcal {A}} _ {1}, \ dots, {\ mathcal { A}} _ {r-1})}$ ${\ displaystyle {\ mathcal {A}} _ {i}}$ $eu$ ${\ displaystyle d '(\ ell)}$ ${\ displaystyle \ ell}$ ${\ mathcal {A}}$

${\ displaystyle \ sum _ {\ ell \ in {\ mathcal {L}} ({\ mathcal {A}})} r ^ {- d (\ ell)} = \ sum _ {i = 0} ^ {r -1} \ sum _ {\ ell \ in {\ mathcal {L}} ({\ mathcal {A}} _ {i})} r ^ {- d (\ ell)} = \ sum _ {i = 0 } ^ {r-1} \ sum _ {\ ell \ in {\ mathcal {L}} ({\ mathcal {A}} _ {i})} r ^ {- d '(\ ell) -1} = r ^ {- 1} \ sum _ {i = 0} ^ {r-1} \ sum _ {\ ell \ in {\ mathcal {L}} ({\ mathcal {A}} _ {i})} r ^ {- d '(\ ell)}}$

Prin aplicarea ipotezei de inducție, avem ${\ displaystyle \ sum _ {\ ell \ in {\ mathcal {L}} ({\ mathcal {A}})} r ^ {- d (\ ell)} \ leqslant r ^ {- 1} \ sum _ { i = 0} ^ {r-1} 1 = 1}$

În schimb, este suficient să arătăm că, din satisfacerea inegalității lui Kraft, putem construi un arbore -ary cu frunze satisfăcătoare . ${\ displaystyle \ ell _ {0}, \ ell _ {1}, \ dots \ ell _ {n-1}}$ $r$ $nu$ ${\ displaystyle f_ {0}, \ dots f_ {n-1}}$ ${\ displaystyle \ forall i, ~ f_ {i} = \ ell _ {i}}$

Demonstrație

Fără pierderea generalității, să presupunem că propunem să construim acest arbore cu următorul algoritm: ${\ displaystyle \ ell _ {0} \ leqslant \ ell _ {1} \ leqslant \ dots \ ell _ {n-1}}$

programme arbre(n, r, [l_0, l_1, ... l_{n-1}]) A <- Arbre r-aire complet de profondeur l_{n-1} pour i de 0 à n-1 choisir un noeud n de A non-marqué de profondeur l_i en faire une feuille i.e. supprimer tous ses descendants le marquer retourner A

Pentru a justifica corectarea algoritmului, avem nevoie de două elemente:

Nu se elimină niciodată un nod marcat de algoritm: atunci când se construiește o foaie de adâncime , se elimină doar noduri de adâncime strict mai mari decât . Cu toate acestea, din moment ce adâncimile sunt sortate în ordine crescătoare, toate foile marcate au o adâncime maximă . ${\ displaystyle \ ell _ {i}}$ ${\ displaystyle \ ell _ {i}}$ ${\ displaystyle \ ell _ {i}}$
În pas , există un nod de adâncime care nu a fost marcat: este suficient să observăm că în pas algoritmul elimină sau marchează nodul (ele) de adâncime . Prin urmare, înainte de pas, am șters sau marcat , prin inegalitatea Kraft. Deci, există un nod de adâncime care nu a fost nici marcat, nici șters, să luăm strămoșul său de adâncime , acest nod nu a fost încă marcat, ceea ce încheie dovada algoritmului. $eu$ $\ ell _ {i}$ $j$ ${\ displaystyle r ^ {\ ell _ {n-1} - \ ell _ {j}}}$ ${\ displaystyle \ ell _ {n-1}}$ $eu$ ${\ displaystyle \ sum _ {j = 0} ^ {i-1} r ^ {\ ell _ {n-1} - \ ell _ {j}} \ leqslant r ^ {\ ell _ {n-1}} \ sum _ {j = 0} ^ {n-1} r ^ {- \ ell _ {j}} \ leqslant r ^ {\ ell _ {n-1}}}$ ${\ displaystyle \ ell _ {n-1}}$ ${\ displaystyle \ ell _ {i}}$

Caz general

Cazul general are un corolar interesant: întrucât orice cod unic decodabil respectă inegalitatea Kraft și, din această inegalitate, putem construi un cod prefix, pentru orice cod unic decodabil, există un cod prefix ale cărui cuvinte cod sunt de aceeași dimensiune. Cu alte cuvinte, codurile unic decodabile nu sunt mai compacte decât codurile prefix.

Rețineți că conversația a fost deja tratată în cazul codurilor de prefix, orice cod de prefix fiind un cod unic decodabil.

Demonstrație

Notă lungimea de cod al unui cuvânt pe și , și ia în considerare numărul de cuvinte de dimensiuni , cu dimensiuni de cod : . așa cum este doar decodabil, avem . ${\ displaystyle \ ell (a)}$ $la$ ${\ displaystyle {\ mathcal {S}}}$ ${\ displaystyle \ ell _ {M} = \ max \ {\ ell (s), s \ in {\ mathcal {S}} \}}$ ${\ displaystyle N_ {m, p}}$ $m$ $p$ ${\ displaystyle N_ {m, p} = | \ {a \ in {\ mathcal {S}} ^ {m}, \ ell (a) = p \} |}$ $\ mathcal {C}$ ${\ displaystyle N_ {m, p} \ leqslant | {\ mathcal {T}} ^ {p} | = r ^ {p}}$

Atunci avem

${\ displaystyle \ sum _ {a \ in {\ mathcal {S}} ^ {m}} r ^ {- \ ell (a)} = \ sum _ {p = 1} ^ {m \ ell _ {M} } \ sum _ {a \ in {\ mathcal {S}} ^ {m}, \ ell (a) = p} r ^ {- \ ell (a)} = \ sum _ {p = 1} ^ {m \ ell _ {M}} N_ {m, p} r ^ {- p} \ leqslant \ sum _ {p = 1} ^ {m \ ell _ {M}} r ^ {p} r ^ {- p} = m \ ell _ {M}}$

Dar o dezvoltare simplă ne oferă:, ceea ce ne aduce la . Acest lucru fiind adevărat pentru orice , deoarece găsim inegalitatea dorită. ${\ displaystyle \ left (\ sum _ {s \ in {\ mathcal {S}}} r ^ {- \ ell (s)} \ right) ^ {m} = \ sum _ {a \ in {\ mathcal { S}} ^ {m}} r ^ {- \ ell (a)}}$ ${\ displaystyle \ sum _ {s \ in {\ mathcal {S}}} r ^ {- \ ell (s)} \ leqslant (m \ ell _ {M}) ^ {1 / m}}$ $m$ ${\ displaystyle (m \ ell _ {M}) ^ {1 / m} \ longrightarrow 1}$

Note și referințe

(în) Leon Gordon Kraft , „ Un dispozitiv de cuantificare, grupare și codificare a impulsurilor modulate în amplitudine ” , Massachusetts Institute of Technology (PhD) ,1949( citiți online , consultat la 18 iulie 2019 )