Desigualdad de Kraft

En la teoría de códigos, '''la desigualdad de Kraft''', nombrada así debido a Leon Kraft, expresa las condiciones suficientes para la existencia de un código prefijo^[1]​ y, las condiciones necesarias para la existencia de un código unívocamente decodificable para un grupo dado de longitudes de palabra. Sus aplicaciones a los códigos y árboles prefijos son usualmente empleadas en ciencias de la computación y teoría de la información.

Más específicamente, la desigualdad de Kraft, limita la longitud de las palabras en un código prefijo: si se toma la exponencial de la longitud de cada palabra válida, el grupo resultante de valores debe seguir una función de probabilidad, es decir, su medida total debe ser menor o igual a uno (1). La desigualdad de Kraft puede ser entendida en términos de un presupuesto limitado de palabras a ser empleado, siendo las palabras más cortas, las más caras.

• Si la desigualdad de Kraft se cumple de manera estrictamente desigual (menor a 1), el código tiene alguna redundancia.
• Si la desigualdad de Kraft se cumple de manera que el resultado es exactamente igual a 1, el código en cuestión es un código completo.
• Si la desigualdad de Kraft no se cumple, el código no es unívocamente descodificable.

Dada una fuente de ${\displaystyle n}$ símbolos a codificar con un alfabeto de ${\displaystyle r}$ símbolos utilizando un conjunto de ${\displaystyle n}$ palabras de longitudes ${\displaystyle l_{1}}$ a ${\displaystyle l_{n}}$, la desigualdad de Kraft corresponde a:

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

Hay que tener en cuenta que:

• Es condición necesaria para que un código sea uno de los códigos prefijo (o códigos instantáneos).
• Es condición suficiente para que exista algún código prefijo (o código instantáneo) con la secuencia de longitudes: ${\displaystyle l_{1}}$... ${\displaystyle l_{n}}$.
• Dado un código conocido ${\displaystyle C}$, con longitudes ${\displaystyle l_{1}}$ a ${\displaystyle l_{n}}$, que cumple la desigualdad de Kraft, NO podemos afirmar que ${\displaystyle C}$ es instantáneo (pues ${\displaystyle C}$ no tiene por qué cumplir la regla del prefijo). Sin embargo, sabemos que existe algún código instantáneo con longitudes ${\displaystyle l_{1}}$... ${\displaystyle l_{n}}$, puesto que se verifica la desigualdad de Kraft con dicha secuencia de longitudes.
• Obsérvese que todo código unívocamente decodificable cumple la desigualdad de Kraft (Th. de McMillan).

• Kraft, Leon G. (1949), A device for quantizing, grouping, and coding amplitude modulated pulses, Cambridge, MA: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology ..

• McMillan, Brockway (1956), «Two inequalities implied by unique decipherability», IEEE Trans. Information Theory 2 (4): 115-116, doi:10.1109/TIT.1956.1056818 ..

• Kraft's inequality (NIST)