Inegalitatea Kraft-McMillan

În teoria codurilor, inegalitatea Kraft-McMillan oferă o condiție necesară și suficientă pentru existența unui cod binar unic decodabil pentru un set de simboluri.

Afirmație

Fiecare cod binar unic decodabil pentru simboluri $\alpha \in A=\alpha _{1},...,\alpha _{N}$ ${\ displaystyle \ alpha \ în A = \ alpha _ {1}, ..., \ alpha _ {N}}$ ${\ displaystyle \ alpha \ în A = \ alpha _ {1}, ..., \ alpha _ {N}}$ trebuie să satisfacă inegalitatea:

\sum _{i=1}^{N}2^{-l\left(\alpha _{i}\right)}\leq 1

{\ displaystyle \ sum _ {i = 1} ^ {N} 2 ^ {- l \ left (\ alpha _ {i} \ right)} \ leq 1}

{\ displaystyle \ sum _ {i = 1} ^ {N} 2 ^ {- l \ left (\ alpha _ {i} \ right)} \ leq 1}

unde este $l\left(\alpha _{i}\right)$ ${\ displaystyle l \ left (\ alpha _ {i} \ right)}$ ${\ displaystyle l \ left (\ alpha _ {i} \ right)}$ este lungimea șirului binar corespunzător $\alpha _{i}$ ${\ displaystyle \ alpha _ {i}}$ ${\ displaystyle \ alpha _ {i}}$ . Având în vedere numerele întregi $l\left(\alpha _{i}\right)$ ${\ displaystyle l \ left (\ alpha _ {i} \ right)}$ ${\ displaystyle l \ left (\ alpha _ {i} \ right)}$ , $i=1,...,N$ ${\ displaystyle i = 1, ..., N}$ ${\ displaystyle i = 1, ..., N}$ satisfacerea inegalității de mai sus, există un cod binar pentru alfabet $LA$ ${\ displaystyle A}$ $LA$ astfel prin care cuvântul $C\left(\alpha _{i}\right)$ ${\ displaystyle C \ left (\ alpha _ {i} \ right)}$ ${\ displaystyle C \ left (\ alpha _ {i} \ right)}$ are lungime $l\left(\alpha _{i}\right)$ ${\ displaystyle l \ left (\ alpha _ {i} \ right)}$ ${\ displaystyle l \ left (\ alpha _ {i} \ right)}$ și nu există un cuvânt egal cu prefixul său.

Demonstrație (pentru coduri de prefix)

Este posibil să se demonstreze într-un mod simplu că teorema este adevărată pentru codurile de prefix . Aceste coduri pot fi scrise prin arbori binari în care fiecare ramură corespunde unui pic o $1$ ${\ displaystyle 1}$ $1$ . Niciun cuvânt de cod nu se termină pe nodurile interne, altfel ar exista cuvinte cu același prefix. Frunzele sunt asociate fiecare cu un cuvânt cod. Se poate presupune că codul constă din $Nu.$ ${\ displaystyle N}$ $Nu.$ cuvinte și că lungimile lor sunt $m_{1},m_{2},...,m_{N}$ ${\ displaystyle m_ {1}, m_ {2}, ..., m_ {N}}$ ${\ displaystyle m_ {1}, m_ {2}, ..., m_ {N}}$ cu $m_{1}\leq m_{2}\leq ...\leq m_{N}$ ${\ displaystyle m_ {1} \ leq m_ {2} \ leq ... \ leq m_ {N}}$ ${\ displaystyle m_ {1} \ leq m_ {2} \ leq ... \ leq m_ {N}}$ , fără pierderea generalității. Deoarece codul este un prefix, este posibil să asociați un cuvânt diferit fiecărei frunze. Arborele are înălțime $m_{N}$ ${\ displaystyle m_ {N}}$ ${\ displaystyle m_ {N}}$ și deci un număr de frunze cel mult egal cu $2^{m_{N}}$ ${\ displaystyle 2 ^ {m_ {N}}}$ ${\ displaystyle 2 ^ {m_ {N}}}$ . Trecând la o atribuire a cuvintelor cod la simbolurile pe care trebuie să le reprezinte, se poate afirma că prin asocierea frunzei de adâncime $j$ ${\ displaystyle j}$ $j$ eliminați toate cuvintele cu același prefix, care sunt $2^{m_{N}-j}$ ${\ displaystyle 2 ^ {m_ {N} -j}}$ ${\ displaystyle 2 ^ {m_ {N} -j}}$ . Condiția care trebuie respectată este aceea odată atribuită $N-1$ ${\ displaystyle N-1}$ $N-1$ cuvinte de cod la cât mai multe simboluri, avem încă cel puțin o frunză pentru a atribui simbolul rămas, deci următoarea inegalitate trebuie să fie adevărată:

2^{m_{N}}-\sum _{i=1}^{N-1}2^{m_{N}-m_{i}}\geq 1

{\ displaystyle 2 ^ {m_ {N}} - \ sum _ {i = 1} ^ {N-1} 2 ^ {m_ {N} -m_ {i}} \ geq 1}

{\ displaystyle 2 ^ {m_ {N}} - \ sum _ {i = 1} ^ {N-1} 2 ^ {m_ {N} -m_ {i}} \ geq 1}

Aceasta înseamnă că:

2^{m_{N}}-\sum _{i=1}^{N-1}2^{m_{N}}\cdot {\frac {1}{2^{m_{i}}}}=2^{m_{N}}\cdot \left(1-\sum _{i=1}^{N-1}{\frac {1}{2^{m_{i}}}}\right)\geq 1

{\ displaystyle 2 ^ {m_ {N}} - \ sum _ {i = 1} ^ {N-1} 2 ^ {m_ {N}} \ cdot {\ frac {1} {2 ^ {m_ {i} }}} = 2 ^ {m_ {N}} \ cdot \ left (1- \ sum _ {i = 1} ^ {N-1} {\ frac {1} {2 ^ {m_ {i}}}} \ dreapta) \ geq 1}

{\ displaystyle 2 ^ {m_ {N}} - \ sum _ {i = 1} ^ {N-1} 2 ^ {m_ {N}} \ cdot {\ frac {1} {2 ^ {m_ {i} }}} = 2 ^ {m_ {N}} \ cdot \ left (1- \ sum _ {i = 1} ^ {N-1} {\ frac {1} {2 ^ {m_ {i}}}} \ dreapta) \ geq 1}

sau:

1-\sum _{i=1}^{N-1}2^{-m_{i}}\geq 2^{-m_{N}}

{\ displaystyle 1- \ sum _ {i = 1} ^ {N-1} 2 ^ {- m_ {i}} \ geq 2 ^ {- m_ {N}}}

{\ displaystyle 1- \ sum _ {i = 1} ^ {N-1} 2 ^ {- m_ {i}} \ geq 2 ^ {- m_ {N}}}

care poate fi rescris ca:

\sum _{i=1}^{N}2^{-m_{i}}\leq 1

{\ displaystyle \ sum _ {i = 1} ^ {N} 2 ^ {- m_ {i}} \ leq 1}

{\ displaystyle \ sum _ {i = 1} ^ {N} 2 ^ {- m_ {i}} \ leq 1}

care este tocmai inegalitatea Kraft-McMillan.
Într-un mod similar se poate arăta că dat un cod cu cuvinte de lungime $m_{1}\leq m_{2}\leq ...\leq m_{N}$ ${\ displaystyle m_ {1} \ leq m_ {2} \ leq ... \ leq m_ {N}}$ ${\ displaystyle m_ {1} \ leq m_ {2} \ leq ... \ leq m_ {N}}$ care verifică inegalitatea Kraft-McMillan, este posibil să le plasezi într-o corespondență unu-la-unu cu cuvintele unui cod binar prefixat unde lungimea $m_{i}$ ${\ displaystyle m_ {i}}$ $pe mine}}$ este asociat cu frunza la adâncime $m_{i}$ ${\ displaystyle m_ {i}}$ $pe mine}}$ în arborele binar.

Bibliografie

Leon G. Kraft, Un dispozitiv pentru cuantificarea, gruparea și codificarea impulsurilor modulate în amplitudine , Cambridge, MA, Teză MS, Departamentul de inginerie electrică, Massachusetts Institute of Technology , 1949.

Brockway McMillan, Două inegalități implicate de descifrabilitate unică , în IEEE Trans. Teoria informației , vol. 2, nr. 4, 1956, pp. 115–116, DOI : 10.1109 / TIT.1956.1056818 .

Portal IT : accesați intrările Wikipedia care se ocupă cu IT