6.3: Teorema de Codificación Fuente

Última actualización
Guardar como PDF

Page ID: 82013

Paul Penfield, Jr.
Massachusetts Institute of Technology via MIT OpenCourseWare

\( \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}}\)

Ahora volviendo al modelo fuente, tenga en cuenta que las palabras clave tienen una longitud promedio, en bits por símbolo,

\(L = \displaystyle \sum_{i} p(A_i)L_i \tag{6.11}\)

Para la velocidad máxima se necesita la longitud promedio de palabra de código más baja posible. La asignación de símbolos de alta probabilidad a las palabras de código cortas puede ayudar a hacer\(L\) pequeñas. Los códigos Huffman son códigos óptimos para este propósito. Sin embargo, hay un límite en cuanto a cuán corta puede ser la palabra de código promedio. Específicamente, el Teorema de Codificación Fuente establece que la información promedio por símbolo siempre es menor o igual a la longitud promedio de una palabra clave:

\(H \leq L \tag{6.12}\)

Esta desigualdad es fácil de probar utilizando las desigualdades de Gibbs y Kraft. Utilizar la desigualdad Gibbs con\(p'(A_i) = 1/2^{L_i}\) (la desigualdad Kraft asegura que el\(p'(A_i)\), además de ser positivo, suman no más de 1). Así

Screen Shot 2021-05-05 a las 10.59.09 PM.png — Figura 6.3: Canal binario

\[\begin{align*} H \quad &= \quad \displaystyle \sum_{i} p(A_i)\log_2\Big(\dfrac{1}{p(A_i)}\Big) \\ &\leq \quad\displaystyle \sum_{i} p(A_i)\log_2\Big(\dfrac{1}{p'(A_i)}\Big) \\ &= \quad \displaystyle \sum_{i} p(A_i)\log_2 2^{L_i} \\ &= \quad\sum_{i} p(A_i)L_i \\ &= \quad L \tag{6.13} \end{align*} \]

El Teorema de Codificación de Origen también se puede expresar en términos de velocidades de transmisión en bits por segundo multiplicando la Ecuación 6.12 por los símbolos por segundo\(R\):

\(H \ R \leq L \ R \tag{6.14}\)