Saltar al contenido principal
LibreTexts Español

6.1.1: Desigualdad Kraft

  • Page ID
    82072
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Dado que el número de códigos distintos de longitud corta es limitado, no todos los códigos pueden ser cortos. Algunos deben ser más largos, pero luego la condición de prefijo limita aún más los códigos cortos disponibles. Una importante limitación en la distribución de longitudes de código\(L_i\) fue dada por L. G. Kraft, estudiante del MIT, en su tesis de maestría de 1949. Se le conoce como la desigualdad Kraft:

    \(\displaystyle \sum_{i} \dfrac{1}{2^{L_i}} \leq 1 \tag{6.1}\)

    Cualquier conjunto válido de palabras clave distintas obedece a esta desigualdad, y a la inversa para cualquier propuesta\(L_i\) que la obedezca, se puede encontrar un código.

    Por ejemplo, supongamos que un código consiste en las cuatro palabras de código distintas de dos bits 00, 01, 10 y 11. Entonces cada uno\(L_i\) = 2 y cada término en la suma en la Ecuación 6.1 es 1/2\(^2\) = 1/4. En este caso la ecuación se evalúa a una igualdad, y hay muchas formas diferentes de asignar las cuatro palabras clave a cuatro símbolos diferentes. Como otro ejemplo, supongamos que sólo hay tres símbolos, y las palabras clave propuestas son 00 01, y 11. En este caso la desigualdad Kraft es una desigualdad. Sin embargo, debido a que la suma es menor que 1, el código puede hacerse más eficiente reemplazando una de las palabras clave por una más corta. En particular, si el símbolo representado por 11 ahora está representado por 1 el resultado sigue siendo un código de condición de prefijo pero la suma sería (1/2\(^2\)) + (1/2\(^2\)) + (1/2) = 1.

    La desigualdad Kraft se puede probar fácilmente. Let\(L_{max}\) Ser la longitud de la palabra de código más larga de un código de prefixcondition. Hay exactamente\(2^{L_{max}}\) diferentes patrones de 0 y 1 de esta longitud. Así

    \(\displaystyle \sum_{i} \dfrac{1}{2^{L_{max}}} = 1 \tag{6.2}\)

    donde esta suma está por encima de estos patrones (esta es una ecuación inusual porque la cantidad que se suma no depende de ella\(i\)). Al menos uno de estos patrones es una de las palabras de código, pero a menos que este sea un código de longitud fija, hay otras palabras de código más cortas. Por cada palabra de código más corta de length\(k\) (\(k < L_{max}\)) hay exactamente\(2^{L_{max−k}}\) patrones que comienzan con esta palabra de código, y ninguna de ellas es una palabra de código válida (porque este código es un código de condición de prefijo). En la suma de la Ecuación 6.2 reemplazar los términos correspondientes a esos patrones por un solo término igual a 1/2\(^k\). La suma no ha cambiado. Continuar este proceso con otras palabras de código cortas. Cuando está completo, hay términos en la suma correspondiente a cada palabra clave, y la suma sigue siendo igual a 1. Puede haber otros términos correspondientes a patrones que no sean palabras de código; si es así, eliminarlos de la suma en la Ecuación 6.2. El resultado es exactamente la suma en la Ecuación 6.1 y es menor o igual a 1. La prueba está completa.


    This page titled 6.1.1: Desigualdad Kraft is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Paul Penfield, Jr. (MIT OpenCourseWare) via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.