Un canal de variación arbitraria ( AVC ) es un modelo de canal de comunicación utilizado en la teoría de la codificación , y fue introducido por primera vez por Blackwell, Breiman y Thomasian. Este canal en particular tiene parámetros desconocidos que pueden cambiar con el tiempo y estos cambios pueden no tener un patrón uniforme durante la transmisión de una palabra de código .Los usos de este canal se pueden describir utilizando una matriz estocástica. , dónde es el alfabeto de entrada, es el alfabeto de salida, y es la probabilidad sobre un conjunto dado de estados , que la entrada transmitida conduce a la salida recibida . El estado en conjunto puede variar arbitrariamente en cada unidad de tiempo . Este canal fue desarrollado como una alternativa al Canal Simétrico Binario (BSC) de Shannon , donde se conoce la naturaleza completa del canal , para ser más realista a las situaciones reales del canal de la red .
Capacidad de los AVC deterministas
La capacidad de un AVC puede variar según determinados parámetros.
es una tasa alcanzable para un código AVC determinista si es mayor que, y si por cada positivo y y muy grande , largo- Existen códigos de bloque que satisfacen las siguientes ecuaciones: y , dónde es el valor más alto en y donde es la probabilidad promedio de error para una secuencia de estados . La tasa más grande representa la capacidad del AVC, denotado por.
Como puede ver, las únicas situaciones útiles son cuando la capacidad del AVC es mayor que, porque entonces el canal puede transmitir una cantidad garantizada de datossin errores. Entonces comenzamos con un teorema que muestra cuándoes positivo en un AVC y los teoremas discutidos después reducirán el rango de por diferentes circunstancias.
Antes de enunciar el teorema 1, es necesario abordar algunas definiciones:
- Un AVC es simétrico si para cada , dónde , , y es una función de canal .
- , , y son todas las variables aleatorias en conjuntos, , y respectivamente.
- es igual a la probabilidad de que la variable aleatoria es igual a .
- es igual a la probabilidad de que la variable aleatoria es igual a .
- es la función de masa de probabilidad combinada (pmf) de, , y . se define formalmente como .
- es la entropía de.
- es igual a la probabilidad media de que será un cierto valor basado en todos los valores posiblemente podría ser igual a.
- es la información mutua de y , y es igual a .
- , donde el mínimo está sobre todas las variables aleatorias tal que , , y se distribuyen en forma de .
Teorema 1: si y solo si el AVC no es simétrico. Si, luego .
Prueba de la primera parte para la simetría: si podemos probar que es positivo cuando el AVC no es simétrico, y luego demuestre que , podremos demostrar el Teorema 1. Suponga eran iguales a . De la definición de, esto haría y variables aleatorias independientes , para algunos, porque esto significaría que la entropía de ninguna variable aleatoria dependería del valor de la otra variable aleatoria . Usando la ecuación, (y recordando ,) podemos obtener,
- desde y son variables aleatorias independientes , para algunos
- porque solo depende de ahora
- porque
Entonces ahora tenemos una distribución de probabilidad enque es independiente de. Entonces, ahora la definición de un AVC simétrico se puede reescribir de la siguiente manera: desde y son ambas funciones basadas en , han sido reemplazados por funciones basadas en y solo. Como puede ver, ambos lados ahora son iguales al calculamos antes, por lo que el AVC es simétrico cuando es igual a . Por lo tanto, solo puede ser positivo si el AVC no es simétrico.
Prueba de la capacidad de la segunda parte : consulte el documento "La capacidad del canal que varía arbitrariamente revisada: positividad, restricciones", que se hace referencia a continuación para obtener una prueba completa.
Capacidad de AVC con restricciones de entrada y estado
El siguiente teorema se ocupará de la capacidad de los AVC con restricciones de entrada y / o estado. Estas restricciones ayudan a disminuir la amplia gama de posibilidades de transmisión y error en un AVC, lo que hace que sea un poco más fácil ver cómo se comporta el AVC.
Antes de pasar al Teorema 2, necesitamos definir algunas definiciones y lemas :
Para tales AVC, existe:
- - Una restricción de entrada basado en la ecuación , dónde y .
- - Una restricción estatal , basado en la ecuación , dónde y .
- -
- - es muy similar a ecuación mencionada anteriormente, , pero ahora cualquier estado o en la ecuación debe seguir el restricción estatal.
Asumir es una función dada de valor no negativo en y es una función dada de valor no negativo en y que los valores mínimos para ambos son . En la literatura que he leído sobre este tema, las definiciones exactas de ambos y (para una variable ,) nunca se describe formalmente. La utilidad de la restricción de entrada y la restricción del estado se basará en estas ecuaciones.
Para AVC con restricciones de entrada y / o estado, la tasa ahora está limitado a palabras en código de formato que satisfacen , y ahora el estado se limita a todos los estados que satisfacen . La tasa más alta todavía se considera la capacidad del AVC, y ahora se denota como.
Lema 1: Cualquier código donde es mayor que no pueden considerarse códigos "buenos" , porque esos tipos de códigos tienen una probabilidad media máxima de error mayor o igual a, dónde es el valor máximo de . Esta no es una buena probabilidad de error promedio máxima porque es bastante grande, esta cerca de , y la otra parte de la ecuación será muy pequeña ya que el el valor se eleva al cuadrado y está configurado para ser más grande que . Por lo tanto, es muy poco probable que reciba una palabra clave sin errores. Es por eso que el condición está presente en el teorema 2.
Teorema 2: Dado un positivo y arbitrariamente pequeño , , , para cualquier longitud de bloque y para cualquier tipo con condiciones y , y donde , existe un código con palabras en clave , cada uno de tipo , que satisfacen las siguientes ecuaciones: , , y donde sea positivo y depender solo de , , y el AVC dado.
Prueba del teorema 2 : Consulte el artículo "La capacidad del canal que varía arbitrariamente revisada: positividad, restricciones", al que se hace referencia a continuación para obtener una prueba completa.
Capacidad de AVC aleatorizados
El siguiente teorema será para AVC con código aleatorio . Para tales AVC, el código es una variable aleatoria con valores de una familia de códigos de bloque de longitud n , y estos códigos no pueden depender / depender del valor real de la palabra de código . Estos códigos tienen el mismo valor de probabilidad de error máximo y promedio para cualquier canal debido a su naturaleza aleatoria. Estos tipos de códigos también ayudan a aclarar ciertas propiedades del AVC.
Antes de pasar al Teorema 3, primero debemos definir un par de términos importantes:
es muy similar al ecuación mencionada anteriormente, , pero ahora el pmf se suma a la ecuación, haciendo que el mínimo de basado en una nueva forma de , dónde reemplaza .
Teorema 3: La capacidad para códigos aleatorios del AVC es.
Prueba del teorema 3 : Consulte el artículo "Las capacidades de ciertas clases de canales bajo codificación aleatoria" que se hace referencia a continuación para obtener una prueba completa.