Desigualtat de Kraft

En la teoria de còdics, '''la desigualtat de Kraft''', nomenada aixina per Leon Kraft, expressa les condicions suficients per a l'existència d'un còdic prefixe i, les condicions necessàries per a l'existència d'un còdic unívocamente decodificable per a un grup donat de llongituts de paraula. Les seues aplicacions als còdics i arbres prefixos són usualment amprades en ciències de la computació i teoria de l'informació.

Més específicament, la desigualtat de Kraft, llimita la llongitut de les paraules en un còdic prefixe: si es pren l'exponencial de la llongitut de cada paraula vàlida, el grup resultant de valors deu seguir una funció de provabilitat, és dir, la seua mida total deu ser menor o igual a un (1). La desigualtat de Kraft pot ser entesa en térmens d'un presupost llimitat de paraules a ser amprat, sent les paraules més curtes, les més cares.

• Si la desigualtat de Kraft es complix de manera estrictament desigual (menor a 1), el còdic té alguna redundància.
• Si la desigualtat de Kraft es complix de manera que el resultat és exactament igual a 1, el còdic en qüestió és un còdic complet.
• Si la desigualtat de Kraft no es complix, el còdic no és unívocamente descodificable.

Definició

Donada una font de $n$ símbols a codificar en un alfabet de $r$ símbols utilisant un conjunt de $n$ paraules de llongituts $l_1$ a $l_n$, la desigualtat de Kraft correspon a:

$\sum _{i=1}^n{\left(\frac{1}{r}\right)}^{{\ell }_i}\le 1.$

Cal tindre en conte que:

• És condició necessària per a que un còdic siga un dels còdics prefixe (o còdics instantàneus).
• És condició suficient per a que existixca algun còdic prefixe (o còdic instantàneu) en la seqüència de llongituts: $l_1$... $l_n$.
• Donat un còdic conegut $C$, en llongituts $l_1$ a $l_n$, que complix la desigualtat de Kraft, NO podem afirmar que $C$ és instantàneu (puix $C$ no té per qué complir la regla del prefix). No obstant, sabem que existix algun còdic instantàneu en llongituts $l_1$... $l_n$, ya que es verifica la desigualtat de Kraft en dita seqüència de llongituts.
• Observe's que tot còdic unívocamente decodificable complix la desigualtat de Kraft (Th. de McMillan).

Referències

• .

• .