Capacitancia de Shannon

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 8 de marzo de 2020; las comprobaciones requieren 8 ediciones .

La capacidad de Shannon ( Capacidad de Shannon ) es una característica de un gráfico no dirigido que describe la máxima densidad de codificación con la posibilidad de seguimiento de errores garantizado en el canal de comunicación, cuyo modelo representa este gráfico.

En este modelo, los vértices del gráfico corresponden a los caracteres del alfabeto , y la presencia de una arista entre dos vértices hace que durante la transmisión el primer carácter pueda ser sustituido por el segundo y el segundo por el primero. Las probabilidades o la frecuencia con la que esto sucede no se consideran en el modelo, el objetivo es construir un método de codificación óptimo que sea resistente a errores arbitrariamente impredecibles de este tipo.

A pesar de la formulación "práctica", la tarea de determinar la capacidad de Shannon de un gráfico es actualmente puramente teórica .

Motivación para el aprendizaje

Permita que un texto transmitido utilizando un alfabeto de cinco caracteres se transmita a través de un canal de comunicación : Debido a errores en la transmisión de la señal, los caracteres adyacentes pueden confundirse, así como el último ( ) con el primero ( ). El gráfico que describe los posibles errores de este canal de comunicación será un ciclo de longitud 5. ${\ estilo de visualización \ {0,1,2,3,4\))$ $cuatro$ ${\ estilo de visualización 0}$ $GRAMO$

Si el texto se transmite "tal cual", luego de haber recibido el carácter , el destinatario no podrá comprender si el carácter fue transmitido por el remitente o si fue el carácter transmitido por el remitente , durante cuya transmisión un se produjo un error y se convirtió en un carácter . $2$ $2$ $una$ $2$

Tal ambigüedad siempre puede ocurrir cuando se usan al menos dos caracteres, conectados por un borde en el gráfico de error. Para evitar que esto suceda, puede elegir un conjunto independiente de vértices de este gráfico y codificar el texto solo con los caracteres correspondientes a estos vértices. Al mismo tiempo, para que el valor de la información de cada carácter sufra lo menos posible, es apropiado tomar el tamaño máximo de dichos conjuntos (su tamaño se denota como ). $\ alfa (G)$

En el ejemplo considerado, es obvio y, por lo tanto, el texto debe codificarse con dos caracteres (por ejemplo, y ). Si la longitud del texto transmitido (el número de caracteres del alfabeto original) es igual a , entonces existen todas las variantes de este texto, y para codificarlas todas con caracteres del alfabeto de dos letras, se necesitarán al menos bits , es decir, el tamaño del texto aumentará al menos una vez. ${\ estilo de visualización \ alfa (G) = 2}$ $una$ $3$ $norte$ $5^n$ ${\ estilo de visualización \ log _ {2} {(5^{n})} = n \ log _ {2} 5}$ ${\ estilo de visualización \ registro _ {2} 5}$

Este resultado puede mejorarse si consideramos no el conjunto de errores en la transmisión de cada carácter individual, sino los errores en la transmisión de un par de caracteres. La gráfica de pares de caracteres que pueden sustituirse entre sí (se denota como ) tendrá no menos número de independencia. $G^{2}$

En el ejemplo bajo consideración, y uno de los conjuntos independientes máximos es . Esto significa que los cinco caracteres se pueden usar en el mensaje transmitido, pero con la condición de que cuando se combinen en pares consecutivos, solo se formarán pares de este conjunto (por ejemplo, no se puede usar texto, porque se puede formar a partir de text , que también se utiliza ). Si inicialmente había caracteres en el texto transmitido, cada uno de ellos se puede traducir a uno de estos pares y obtener un texto largo con las propiedades de seguimiento de errores requeridas. Dado que , este método de codificación es más eficiente que el primero. ${\ estilo de visualización \ alfa (G^{2}) = 5}$ ${\ estilo de visualización \ {(0,3), (1,0), (2,2), (3,4), (4,1) \}}$ ${\ estilo de visualización 00}$ $diez$ $norte$ $2n$ ${\ estilo de visualización 2 < \ log _ {2} 5}$

Surge naturalmente la pregunta de si este resultado se puede mejorar considerando triples, cuádruples y más caracteres sucesivos en lugar de pares, y cuál es el mejor resultado que se puede lograr con este método. La formalización de esta pregunta conduce al concepto de capacidad de Shannon.

Formal definición

Para determinar la capacidad de Shannon se utiliza una definición auxiliar del producto directo de gráficas:

$G_{1}\times G_{2}=(V_{1},E_{1})\times (V_{2},E_{2})=(V',E')$ , dónde

V'=V_{1}\veces V_{2}

((v_{1},w_{1}),(v_{2},w_{2}))\en E'\iff ((v_{1},v_{2})\en E_{ 1}\lor v_{1}=v_{2})\land ((w_{1},w_{2})\in E_{2}\lor w_{1}=w_{2})\land (( v_{1},w_{1})\no =(v_{2},w_{2}))

Esta operación, salvo isomorfismo , es asociativa y conmutativa, por lo que se puede definir naturalmente el grado de un grafo :

{\displaystyle G^{k}=G\veces G^{k-1))

Definición

La capacidad de Shannon del gráfico es [1] $GRAMO$

c(G)=\sup \limits _{n\in {\mathbb {N} }}{\sqrt[{n}]{\alpha (G^{n)))))=\lim \ límites _ {n\to \infty }{\sqrt[{n}]{\alpha (G^{n))}}

La última igualdad se debe al hecho de que [2] . ${\ estilo de visualización \ alfa (G \ veces H) \ geq \ alfa (G) \ alfa (H)}$

La naturaleza de la convergencia

Límite alcanzable

No siempre se alcanza el límite de secuencia . Por ejemplo, cuando es la unión de un ciclo de longitud 5 ( ) y un vértice aislado, entonces , pero ${\sqrt[{n}]{\alpha (G^{n))}}$ $GRAMO$ ${\ estilo de visualización C_ {5}}$ $c(G)={\sqrt {5}}+1$ ${\sqrt[{n}]{\alpha (G^{n})}}<{\sqrt {5}}+1$

Esto se debe a que y , por lo que lo mismo es cierto para la unión de un vértice aislado con cualquier grafo para el cual $\alpha (G^{n})=\sum \limits _{k=1}^{n}{{\binom {n}{k}}\alpha ({C_{5}}^{k })}+1$ ${\ estilo de visualización \ alfa (C_{5}) <c (C_ {5})}$ $H$ ${\ estilo de visualización \ alfa (H) <c (H)}$

Tasa de crecimiento

Una pregunta relevante es qué tan rápido se acercan los valores . En 2006, Alon y Lyubetsky mostraron. que para un tamaño de gráfico suficientemente grande, un número finito de valores no es suficiente para saber con una precisión de al menos hasta . En el mismo trabajo, plantean varias hipótesis sobre este tema. [3] $\alpha _{n}={\sqrt[{n}]{\alpha (G^{n)))))$ ${\ estilo de visualización c (G)}$ $\alpha_{n}$ $GRAMO$ $|G|^{\varepsilon}\forall\epsilon >0$

Teorema

Para cualquier número entero , existe un gráfico arbitrariamente grande y de tamaño tal que $v$ $norte$ $GRAMO$ $norte$

${\ estilo de visualización \ alfa _ {k} = O (\ log N)}$ a ${\ estilo de visualización k <v}$

${\ estilo de visualización \ alfa _ {v} = N ^ {\ frac {1} {v}}}$

Descripción del diseño

La demostración de Alon y Lyubetsky era probabilística (es decir, no se puede deducir de ella una construcción específica de un solo grafo , pero se ha probado la existencia de tal).

Consideraron un gráfico completo de vértices ( -un número entero suficientemente grande), cuyas aristas se dividen en grupos y se elimina aleatoriamente una arista de cada grupo (equiprobablemente a lo largo de todas las aristas del grupo). ${\ estilo de visualización nv}$ $norte$

Si indexamos los vértices del grafo en pares , entonces dos aristas y pertenecen al mismo grupo si: ${\ estilo de visualización (i, k), i \ en [1; n], k \ en [1; v]}$ ${\ estilo de visualización ((i_{1},k_{1}),(j_{1},l_{1}))}$ ${\ estilo de visualización ((i_{2},k_{2}),(j_{2},l_{2}))}$

$i_{1}=i_{2}$
${\ estilo de visualización j_{1}=j_{2))$
$l_{1}-k_{1}=l_{2}-k_{2}$

Visualmente, esto se puede representar cuando se representa un gráfico en un toroide como una agrupación de bordes obtenidos entre sí por traslación paralela a lo largo de una línea recta (ver imagen).

Grados y métodos de estudio

Los algoritmos generales para calcular la capacidad de Shannon se desconocen a partir de 2019. Esto se debe no solo al hecho de que el problema del número de independencia en sí mismo es NP-completo y, por lo tanto, computacionalmente difícil, sino también al hecho de que, para los valores calculados para small , el problema de predecir el crecimiento adicional de estos las cantidades tampoco son triviales. ${\ estilo de visualización \ alfa (G^{k})}$ $k$

Además, ni siquiera se conoce el valor exacto de la capacidad para un ciclo de longitud 7 o mayor de longitud impar. [4] [5] Sin embargo, para ciclos de longitud impar, se conoce la ley límite [6] :

c(C_{2n+1})=n+{\frac {1}{2}}+o(1)

Número de Lovas

Laszlo Lovas demostró en 1979 que . [7] Como prueba, derivó un límite superior general para la capacidad de Shannon en términos de una característica de un sistema de vectores cuya estructura está relacionada con la del gráfico , a saber $c(C_{5})={\sqrt {\alpha (C_{5}^{2)))))={\sqrt {5))$ ${\ estilo de visualización (u_ {i}) _ {i \ en V}}$ $G=(V,E)$

u_{i}^{\mathrm {T} }u_{j}={\begin{cases}1,&i=j,\\0,&(i,j)\notin E.\end{cases }}

Con este enfoque, para obtener una estimación superior, basta presentar al menos un sistema de vectores con las propiedades necesarias, es decir, se pasa del problema de demostración al problema de presentación de un contraejemplo .

En la construcción de Lovas, solo el número de vectores debe coincidir con el tamaño del gráfico, pero no la dimensión del espacio . Por ejemplo, se usaron vectores tridimensionales para la prueba . $c(C_{5})={\sqrt {5}}$

Estimaciones algebraicas

Haemers obtuvo una estimación de capacidad en términos del rango de matrices de estructura similar a la matriz de adyacencia , a saber

c(G)\leq R(G)=\min_{B}\operatorname {rango} (B),

donde el mínimo se toma sobre todas las matrices de tamaño en un campo arbitrario tal que: $B$ $n\veces n$

$b_{ii}\not =0$
${\ estilo de visualización (i, j) \ no \ en E \ Rightarrow b_ {ij} = 0}$

Por lo tanto, para la estimación superior también es suficiente proporcionar al menos una matriz que tenga un rango pequeño. [ocho] $B$

Véase también

El problema de los conjuntos independientes

Notas

↑ La designación a veces también se usa ${\ estilo de visualización \ Theta (G)}$
↑ Diapositivas de la conferencia MIPT "Modelo gráfico de un canal de comunicación. Capacitancia de Shannon" . Fecha de acceso: 30 de diciembre de 2019. Archivado desde el original el 13 de enero de 2017. (indefinido)
↑ Alon, Noga & Lubetzky, Eyal (2006), La capacidad de Shannon de un gráfico y los números de independencia de sus poderes , IEEE Transactions on Information Theory T. 52: 2172–2176 , DOI 10.1109/tit.2006.872856 .
↑ ver, por ejemplo, arXiv:1504.01472 Archivado el 30 de diciembre de 2019 en Wayback Machine , donde la mejora numérica de sus puntajes se presenta como un tema para un trabajo separado
↑ Capacidad de Shannon de los siete ciclos . Fecha de acceso: 30 de diciembre de 2019. Archivado desde el original el 30 de diciembre de 2019. (indefinido)
↑ Bowman, Tom (2003), Un teorema del límite para las capacidades de Shannon de los ciclos impares, Actas de la sociedad matemática estadounidense Vol. 131(11): 3559-3569
↑ Lovász, László (1979), Sobre la capacidad de Shannon de un gráfico , IEEE Transactions on Information Theory T. IT-25(1) , DOI 10.1109/TIT.1979.1055985
↑ Haemers, Willem H. (1978), Un límite superior para la capacidad de Shannon de un gráfico , Colloquia Mathematica Societatis János Bolyai T. 25: 267–272 , < https://pure.uvt.nl/portal/files/997000 /SUPERIOR___.PDF > Archivado el 4 de marzo de 2016 en Wayback Machine . La definición aquí corrige un error tipográfico en este documento.