En la 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 relación límite entre el logaritmo negativo de la probabilidad de error y la longitud de bloque del código para longitudes de bloque grandes. Por ejemplo, si la probabilidad de errorde un decodificador cae como, dónde es la longitud del bloque, el exponente de error es . En este ejemplo, enfoques para grande . Muchos de los teoremas de la teoría de la información son de naturaleza asintótica, por ejemplo, el teorema de la codificación del canal establece que para cualquier tasa menor que la capacidad del canal, la probabilidad de error del código del canal puede llegar a cero como la longitud del bloque. va al infinito. En situaciones prácticas, existen limitaciones para el 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 llega al infinito.
Para DMC invariantes en el tiempo
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 puede usarse para asegurar que la probabilidad de error de bloque sea menor que ε> 0 para mensajes suficientemente largos. bloque X . Además, para cualquier tasa mayor que la capacidad del canal, la probabilidad de error de bloque en el receptor aumenta a uno cuando la longitud del bloque llega al infinito.
Suponiendo una configuración de codificación de canal de la siguiente manera: el canal puede transmitir cualquiera de mensajes, transmitiendo la palabra de código correspondiente (que es de longitud n ). Cada componente en el libro de códigos se dibuja iid de acuerdo con alguna distribución de probabilidad con la función de masa de probabilidad Q . En el extremo de la decodificación, se realiza la decodificación de máxima probabilidad.
Dejar ser el la palabra de código aleatoria en el libro de códigos, donde viene de a . Suponga que se selecciona el primer mensaje, por lo que la palabra clavees transmitida. Dado que se recibe, la probabilidad de que la palabra de código se detecte incorrectamente como es:
La función tiene límite superior
por Por lo tanto,
Dado que hay un total de M mensajes y las entradas en el libro de códigos son iid, la probabilidad de que se confunde con cualquier otro mensaje veces la expresión anterior. Usando el límite de unión, la probabilidad de confundir con cualquier mensaje está delimitado por:
para cualquier . Promedio de todas las combinaciones de:
Elegir y combinando las dos sumas sobre en la fórmula anterior:
Utilizando la naturaleza de independencia de los elementos de la palabra de código y la naturaleza discreta sin memoria del canal:
Usando el hecho de que cada elemento de la palabra de código está distribuido de manera idéntica y, por lo tanto, estacionario:
Reemplazando M por 2 nR y definiendo
la probabilidad de error se convierte en
Q ydebe elegirse de modo que el límite sea más estrecho. Por tanto, el exponente de error se puede definir como
Para fuentes discretas sin memoria invariantes en el tiempo
El teorema de la codificación de fuente establece que para cualquier y cualquier fuente iid de tiempo discreto como y para cualquier tasa menor que la entropía de la fuente, hay suficiente y un codificador que lleva iid repetición de la fuente, y lo asigna a bits binarios de modo que los símbolos fuente son recuperables de los bits binarios con probabilidad al menos .
Dejar 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 correspondienteluego 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á a la secuencia fuente que maximiza , dónde denota el evento ese mensaje fue transmitido. Esta regla es equivalente a encontrar la secuencia fuente entre el conjunto de secuencias de origen que se asignan al mensaje que maximiza . Esta reducción se deriva del hecho de que los mensajes se asignaron al azar e independientemente de todo lo demás.
Por lo tanto, como ejemplo de cuando ocurre un error, supongamos que la secuencia fuente fue asignado al mensaje como era la secuencia fuente . Si se generó en la fuente, pero entonces ocurre un error.
Dejar denotar el evento 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 puede centrarse en encontrar un límite superior al .
Dejar denotar el evento que la secuencia fuente se asignó al mismo mensaje que la secuencia de origen y eso . Por lo tanto, dejando denotar el evento de que las dos secuencias fuente y mapear al mismo mensaje, tenemos que
y usando el hecho de que y es independiente de todo lo demás tiene eso
Un límite superior simple para el término de la izquierda se puede establecer como
para algún número real arbitrario Este límite superior se puede verificar observando que cualquiera es igual o porque las probabilidades de una secuencia de entrada dada son completamente deterministas. Por tanto, si luego de modo que la desigualdad se mantenga en ese caso. La desigualdad se mantiene también en el otro caso porque
para todas las cadenas fuente posibles. Así, combinando todo e introduciendo algunos, tengo eso
Donde las desigualdades se derivan de una variación del límite de la Unión. Finalmente, aplicando este límite superior a la suma de tengo eso:
Donde la suma ahora puede hacerse cargo de todos porque eso solo aumentará el límite. En última instancia, cediendo eso
Ahora, por simplicidad, deja así que eso Sustituyendo este nuevo valor de en el límite anterior sobre la probabilidad de error y utilizando el hecho de que es solo una variable ficticia en la suma da lo siguiente como un límite superior en la probabilidad de error:
- y cada uno de los componentes de son independientes. Por lo tanto, simplificar la ecuación anterior produce
El término en el exponente debe maximizarse sobre para alcanzar el límite superior más alto de la probabilidad de error.
Dejando ver que el exponente de error para el caso de codificación fuente es:
R. Gallager, Teoría de la información y comunicación confiable , Wiley 1968