exponente de error

En teoría de la información , el exponente de error de un código de canal o código fuente sobre la longitud del bloque del código es la tasa a la que la probabilidad de error decae exponencialmente con la longitud del bloque del código. Formalmente, se define como la razón límite del logaritmo negativo de la probabilidad de error a la longitud del bloque del código para longitudes de bloque grandes. Por ejemplo, si la probabilidad de error de un decodificador cae como , donde es la longitud del bloque, el exponente de error es . En este ejemplo, se aproxima para grandes . Muchos de los teoremas de la teoría de la información son de naturaleza asintótica, por ejemplo, el teorema de codificación de canal establece que para cualquier tasa menor que la capacidad del canal, la probabilidad del error del código de canal puede hacerse que vaya a cero a medida que la longitud del bloque tiende al infinito. En situaciones prácticas, existen limitaciones al retraso de la comunicación y la longitud del bloque debe ser finita. Por lo tanto, es importante estudiar cómo cae la probabilidad de error a medida que la longitud del bloque tiende al infinito. ${\displaystyle P_{\mathrm {error} }}$${\displaystyle e^{-n\alpha}}$${\estilo de visualización n}$${\estilo de visualización \alpha}$${\displaystyle {\frac {-\ln P_{\mathrm {error} }}{n}}}$${\estilo de visualización \alpha}$${\estilo de visualización n}$

El teorema de codificación de canal establece que para cualquier ε > 0 y para cualquier tasa menor que la capacidad del canal, existe un esquema de codificación y decodificación que se puede utilizar para garantizar que la probabilidad de error de bloque sea menor que ε > 0 para un bloque de mensaje X suficientemente largo . Además, para cualquier tasa mayor que la capacidad del canal, la probabilidad de error de bloque en el receptor tiende a uno a medida que la longitud del bloque tiende a infinito.

Suponiendo una configuración de codificación de canal como la siguiente: el canal puede transmitir cualquiera de los mensajes, transmitiendo la palabra de código correspondiente (que tiene una longitud n ). Cada componente del libro de códigos se extrae iid de acuerdo con una distribución de probabilidad con una función de masa de probabilidad Q. En el extremo de la decodificación, se realiza una decodificación de máxima verosimilitud. ${\displaystyle M=2^{nR}\;}$

Sea la palabra clave aleatoria n.° en el libro de códigos, donde va de a . Supongamos que se selecciona el primer mensaje, por lo que se transmite la palabra clave. Dado que se recibe , la probabilidad de que la palabra clave se detecte incorrectamente es: ${\displaystyle X_{i}^{n}}$${\displaystyle i}$${\displaystyle i}$${\displaystyle 1}$${\displaystyle M}$${\displaystyle X_{1}^{n}}$${\displaystyle y_{1}^{n}}$${\displaystyle X_{2}^{n}}$

${\displaystyle P_{\mathrm {error} \ 1\to 2}=\sum _{x_{2}^{n}}Q(x_{2}^{n})1(p(y_{1}^{n}\mid x_{2}^{n})>p(y_{1}^{n}\mid x_{1}^{n})).}$

La función tiene límite superior ${\displaystyle 1(p(y_{1}^{n}\mid x_{2}^{n})>p(y_{1}^{n}\mid x_{1}^{n}))}$

${\displaystyle \left({\frac {p(y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}}$

Por lo tanto, ${\displaystyle s>0\;}$

${\displaystyle P_{\mathrm {error} \ 1\to 2}\leq \sum _{x_{2}^{n}}Q(x_{2}^{n})\left({\frac {p(y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}.}$

Dado que hay un total de M mensajes y las entradas en el libro de códigos son iid, la probabilidad de que se confunda con cualquier otro mensaje es multiplicada por la expresión anterior. Si se utiliza el límite de unión, la probabilidad de que se confunda con cualquier mensaje está limitada por: ${\displaystyle X_{1}^{n}}$${\displaystyle M}$${\displaystyle X_{1}^{n}}$

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\left(\sum _{x_{2}^{n}}Q(x_{2}^{n})\left({\frac {p(y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}\right)^{\rho }}$

para cualquier . Promediando todas las combinaciones de : ${\displaystyle 0<\rho <1}$${\displaystyle x_{1}^{n},y_{1}^{n}}$

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\sum _{y_{1}^{n}}\left(\sum _{x_{1}^{n}}Q(x_{1}^{n})[p(y_{1}^{n}\mid x_{1}^{n})]^{1-s\rho }\right)\left(\sum _{x_{2}^{n}}Q(x_{2}^{n})[p(y_{1}^{n}\mid x_{2}^{n})]^{s}\right)^{\rho }.}$

Eligiendo y combinando las dos sumas en la fórmula anterior: ${\displaystyle s=1-s\rho }$${\displaystyle x_{1}^{n}}$

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\sum _{y_{1}^{n}}\left(\sum _{x_{1}^{n}}Q(x_{1}^{n})[p(y_{1}^{n}\mid x_{1}^{n})]^{\frac {1}{1+\rho }}\right)^{1+\rho }.}$

Utilizando la naturaleza independiente de los elementos de la palabra clave y la naturaleza discreta y sin memoria del canal:

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\prod _{i=1}^{n}\sum _{y_{i}}\left(\sum _{x_{i}}Q_{i}(x_{i})[p_{i}(y_{i}\mid x_{i})]^{\frac {1}{1+\rho }}\right)^{1+\rho }}$

Utilizando el hecho de que cada elemento de la palabra clave está distribuido de forma idéntica y, por tanto, es estacionario:

${\displaystyle P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\left(\sum _{y}\left(\sum _{x}Q(x)[p(y\mid x)]^{\frac {1}{1+\rho }}\right)^{1+\rho }\right)^{n}.}$

Reemplazando M por 2 ^nR y definiendo

${\displaystyle E_{o}(\rho ,Q)=-\ln \left(\sum _{y}\left(\sum _{x}Q(x)[p(y\mid x)]^{1/(1+\rho )}\right)^{1+\rho }\right),}$

La probabilidad de error se convierte en

${\displaystyle P_{\mathrm {error} }\leq \exp(-n(E_{o}(\rho ,Q)-\rho R)).}$

Q y debe elegirse de manera que el límite sea lo más ajustado posible. Por lo tanto, el exponente de error puede definirse como ${\displaystyle \rho }$

${\displaystyle E_{r}(R)=\max _{Q}\max _{\rho \in [0,1]}E_{o}(\rho ,Q)-\rho R.\;}$

El teorema de codificación de fuente establece que para cualquier fuente iid de tiempo discreto como y para cualquier tasa menor que la entropía de la fuente, existe un codificador suficientemente grande que toma la repetición iid de la fuente, , y la asigna a bits binarios de modo que los símbolos de la fuente se puedan recuperar de los bits binarios con una probabilidad de al menos . ${\displaystyle \varepsilon >0}$${\displaystyle X}$${\displaystyle n}$${\displaystyle n}$${\displaystyle X^{1:n}}$${\displaystyle n.(H(X)+\varepsilon )}$${\displaystyle X^{1:n}}$${\displaystyle 1-\varepsilon }$

Sea el número total de mensajes posibles. A continuación, asigne cada una de las posibles secuencias de salida de origen a uno de los mensajes de forma aleatoria utilizando una distribución uniforme e independientemente de todo lo demás. Cuando se genera una fuente, el mensaje correspondiente se transmite al destino. El mensaje se decodifica en una de las posibles cadenas de origen. Para minimizar la probabilidad de error, el decodificador decodificará en la secuencia de origen que maximice , donde denota el evento de que se transmitió el mensaje. Esta regla es equivalente a encontrar la secuencia de origen entre el conjunto de secuencias de origen que se asignan al mensaje que maximiza . Esta reducción se desprende del hecho de que los mensajes se asignaron de forma aleatoria e independientemente de todo lo demás. ${\displaystyle M=e^{nR}\,\!}$${\displaystyle M=m\,}$${\displaystyle X_{1}^{n}}$${\displaystyle P(X_{1}^{n}\mid A_{m})}$${\displaystyle A_{m}\,}$${\displaystyle m}$${\displaystyle X_{1}^{n}}$${\displaystyle m}$${\displaystyle P(X_{1}^{n})}$

Por lo tanto, como ejemplo de cuándo ocurre un error, supongamos que la secuencia de origen se asignó a mensaje , ya que la secuencia de origen se generó en la fuente, pero luego ocurre un error. ${\displaystyle X_{1}^{n}(1)}$${\displaystyle 1}$${\displaystyle X_{1}^{n}(2)}$${\displaystyle X_{1}^{n}(1)\,}$${\displaystyle P(X_{1}^{n}(2))>P(X_{1}^{n}(1))}$

Sea el evento de que la secuencia fuente se generó en la fuente, de modo que Entonces la probabilidad de error se puede descomponer como Por lo tanto, la atención se puede centrar en encontrar un límite superior para . ${\displaystyle S_{i}\,}$${\displaystyle X_{1}^{n}(i)}$${\displaystyle P(S_{i})=P(X_{1}^{n}(i))\,.}$${\displaystyle P(E)=\sum _{i}P(E\mid S_{i})P(S_{i})\,.}$${\displaystyle P(E\mid S_{i})\,}$

Sea el evento en el que la secuencia fuente se asignó al mismo mensaje que la secuencia fuente y que . Por lo tanto, sea el evento en el que las dos secuencias fuente y se asignan al mismo mensaje, tenemos que ${\displaystyle A_{i'}\,}$${\displaystyle X_{1}^{n}(i')}$${\displaystyle X_{1}^{n}(i)}$${\displaystyle P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i))}$${\displaystyle X_{i,i'}\,}$${\displaystyle i\,}$${\displaystyle i'\,}$

${\displaystyle P(A_{i'})=P\left(X_{i,i'}\bigcap P(X_{1}^{n}(i')\right)\geq P(X_{1}^{n}(i)))\,}$

y usando el hecho de que y es independiente de todo lo demás tenemos que ${\displaystyle P(X_{i,i'})={\frac {1}{M}}\,}$

${\displaystyle P(A_{i'})={\frac {1}{M}}P(P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i)))\,.}$

Se puede establecer un límite superior simple para el término de la izquierda como

${\displaystyle \left[P(P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i)))\right]\leq \left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\,}$

Para un número real arbitrario, este límite superior se puede verificar observando que o bien es igual a o bien porque las probabilidades de una secuencia de entrada dada son completamente deterministas. Por lo tanto, si entonces de modo que la desigualdad se cumple en ese caso. La desigualdad se cumple también en el otro caso porque ${\displaystyle s>0\,.}$${\displaystyle P(P(X_{1}^{n}(i'))>P(X_{1}^{n}(i)))\,}$${\displaystyle 1\,}$${\displaystyle 0\,}$${\displaystyle P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i))\,,}$${\displaystyle {\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\geq 1\,}$

${\displaystyle \left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\geq 0\,}$

para todas las cadenas de origen posibles. Por lo tanto, combinando todo e introduciendo algunos , tenemos que ${\displaystyle \rho \in [0,1]\,}$

${\displaystyle P(E\mid S_{i})\leq P(\bigcup _{i\neq i'}A_{i'})\leq \left(\sum _{i\neq i'}P(A_{i'})\right)^{\rho }\leq \left({\frac {1}{M}}\sum _{i\neq i'}\left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\right)^{\rho }\,.}$

Donde las desigualdades se derivan de una variación del límite de unión. Finalmente, al aplicar este límite superior a la suma para tenemos que: ${\displaystyle P(E)\,}$

${\displaystyle P(E)=\sum _{i}P(E\mid S_{i})P(S_{i})\leq \sum _{i}P(X_{1}^{n}(i))\left({\frac {1}{M}}\sum _{i'}\left({\frac {P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\right)^{\rho }\,.}$

Donde ahora se puede asumir la suma total porque eso solo aumentará el límite. En última instancia, obtenemos que ${\displaystyle i'\,}$

${\displaystyle P(E)\leq {\frac {1}{M^{\rho }}}\sum _{i}P(X_{1}^{n}(i))^{1-s\rho }\left(\sum _{i'}P(X_{1}^{n}(i'))^{s}\right)^{\rho }\,.}$

Ahora, para simplificar, supongamos que al sustituir este nuevo valor de en el límite anterior de probabilidad de error y usar el hecho de que es solo una variable ficticia en la suma, obtenemos lo siguiente como límite superior de probabilidad de error: ${\displaystyle 1-s\rho =s\,}$${\displaystyle s={\frac {1}{1+\rho }}\,.}$${\displaystyle s\,}$${\displaystyle i'\,}$

${\displaystyle P(E)\leq {\frac {1}{M^{\rho }}}\left(\sum _{i}P(X_{1}^{n}(i))^{\frac {1}{1+\rho }}\right)^{1+\rho }\,.}$

${\displaystyle M=e^{nR}\,\!}$y cada uno de los componentes de son independientes. Por lo tanto, simplificando la ecuación anterior se obtiene${\displaystyle X_{1}^{n}(i)\,}$

${\displaystyle P(E)\leq \exp \left(-n\left[\rho R-\ln \left(\sum _{x_{i}}P(x_{i})^{\frac {1}{1+\rho }}\right)(1+\rho )\right]\right).}$

El término en el exponente debe maximizarse para lograr el límite superior más alto en la probabilidad de error. ${\displaystyle \rho \,}$

Veamos que el exponente de error para el caso de codificación fuente es: ${\displaystyle E_{0}(\rho )=\ln \left(\sum _{x_{i}}P(x_{i})^{\frac {1}{1+\rho }}\right)(1+\rho )\,,}$

${\displaystyle E_{r}(R)=\max _{\rho \in [0,1]}\left[\rho R-E_{0}(\rho )\right].\,}$

• Codificación fuente
• Codificación de canales

R. Gallager, Teoría de la información y comunicación fiable , Wiley 1968