Mejor límite superior de velocidad para códigos q-ary

Question

Entre los muchos límites superiores para familias de códigos en $\mathbb F _2 ^n$ el límite más conocido es el de McEliece, Rodemich, Rumsey y Welch, que establece que la tasa $R(\delta)$ correspondiente a la distancia arelativa de $\delta$ es tal que: \begin{equation*}R(\delta) \leq H_2(\frac{1}{2}-\sqrt{\delta(1-\delta)}) \end{equation*} donde H es la función de entropía binaria. (Existe una ligera mejora de lo anterior en el caso binario, pero dentro del mismo marco) En el caso de códigos q-arios, es decir, códigos sobre $\mathbb F _q ^n$ el límite anterior se generaliza a: \begin{equation*}R(\delta) \leq H_q(\frac{1}{q}(q-1-(q-2)\delta-2\sqrt{(q-1)\delta(1-\delta)})) \end{equation*} Mi pregunta es la siguiente: Para alfabetos de mayor tamaño q, el límite anterior parece debilitarse significativamente. De hecho, observando el crecimiento del límite anterior como $q \rightarrow \infty$ , vemos que: \begin{equation*} R(\delta) \leq 1-\delta+\mathcal{O}(\frac{1}{\log{q}}) \end{equation*} Por lo tanto, parece ser peor que incluso el límite Singleton $R(\delta) \leq 1-\delta$ .

Entonces, ¿cuál es el mejor límite para un alfabeto de gran tamaño? $q$ ? Además, ¿podría alguien indicarme referencias para comparaciones de diferentes límites para mayores $q$ ? Sólo encuentro comparaciones fiables para $q=2$ .

Answer 1

Así, el supuestamente más agudo entre todos los límites conocidos es de alguna manera más pobre que el límite que se aprende en Teoría de la Codificación 101 si el tamaño del alfabeto $q$ se acerca al infinito. Creo que la razón por la que te hace gracia radica en lo que entiendes por "gran $q$ ."

Puedes pensar de esta manera: Si el parámetro $q$ es grande en comparación con la longitud del código $n$ el límite de Singleton es un límite superior extremadamente agudo e invencible. De hecho, es lo mejor posible en el sentido de que hay infinitos códigos no triviales que lo consiguen. Creo que por eso te has visto atrapado en una situación aparentemente contradictoria en la que el "mejor límite superior (MRRW)" no consigue vencer al "límite pobre y elemental (Singleton)".

He aquí una explicación un poco más formal. Los límites superiores de la tasa de información $R$ que estás considerando son las asintóticas descritas por la Función de entropía de Hilbert

$$H_q(x) = x\log_q(q-1)-x\log_qx-(1-x)\log_q(1-x)$$

y el distancia relativa $\delta = \frac{d}{n}$ donde $d$ es la distancia mínima de un código. Los límites de este tipo intentan comprender el comportamiento de la tasa de información cuando la longitud del código $n$ tiende a infinito para un $\delta$ .

Más concretamente, al escribir el mayor número posible de palabras de código para un $q$ código -ary de longitud $n$ y la distancia relativa $\delta$ como $A_q(n,\delta n)$ nos gustaría saber el valor exacto de

$$R_q(\delta) = \lim_{n\rightarrow \infty}\sup n^{-1}\log_qA_q(n,\delta n).$$

El límite MRRW que mencionas es un límite superior bastante bueno para $R_q(\delta)$ obtenidos mediante programación lineal. Por supuesto, la simple y llana cota Singleton también puede verse como una cota superior asintótica si simplemente la reescribimos con $\delta$ es decir, tiene $R \leq 1-\delta$ .

Ahora, lo que hiciste con el límite MRRW parece ser simplemente aplicar

$$\lim_{q\rightarrow \infty}H_q(\delta) = \delta$$

para ver cómo es cuando " $q$ es grande". El problema es que, para obtener un límite superior significativo mejor que el límite de Singleton, hay que considerar exactamente qué se entiende por "grande". $q$ ."

Como probablemente ya sepa, existen códigos que cumplen el límite Singleton. De hecho, es la definición de distancia máxima separable (MDS) códigos. Los famosos Códigos Reed-Solomon son los ejemplos canónicos de este tipo de código, de los que se conjetura que tienen el "mayor" $n$ en relación con $q$ entre todos los códigos MDS (lineales) posibles. En términos más generales, los códigos de geometría algebraica pueden alcanzar

$$R \geq 1 - \delta - \frac{1}{\sqrt{q}-1}$$

cuando la primera potencia $q$ es un cuadrado. Por lo tanto, si su $q$ se encuentra en el intervalo en el que pueden existir códigos MDS, no existe un límite superior general de $R$ puede superar el límite Singleton a menos que sea uno muy artificioso. Si $q$ es lo suficientemente pequeño en comparación con $n$ tal que se pueden realizar códigos increíblemente fuertes como los códigos algebraicos, no esperes que ningún otro límite pueda superarlo.

Por lo tanto, si se desea un límite superior asintótico más fuerte que el límite Singleton, hay que descartar al menos la existencia de códigos MDS haciendo que $q$ crecer lo suficientemente despacio. Aquí hay un teorema que conozco que se puede utilizar para este propósito:

Si existe un $q$ -ary código MDS de longitud $n$ y distancia mínima $d$ entonces $q \geq n-d+2.$

(Para la prueba, véase L. M. G. M. Tolhuizen, On maximum distance separable codes over alphabets of arbitrary size, IEEE Int. Symp. Inf. Theory (1994) 431. )

Así, fijando la distancia relativa $\delta$ la desigualdad puede reescribirse como $q \geq n(1-\delta)+2$ . Por esta condición necesaria para la existencia de un código MDS, si sólo se permite $q$ ser siempre menor que el lado derecho al conducir $n$ hasta el infinito, su límite superior general favorito puede tener la oportunidad de superar el límite de Singleton.

Los códigos MDS y otros códigos de corrección de errores muy potentes son extremadamente importantes y tienen varias conexiones interesantes con otros campos tanto dentro como fuera de las matemáticas. Así que si se pregunta a un teórico de la codificación real, creo que conoce el mejor teorema que se puede explotar para descartar la existencia de códigos MDS y también los mejores métodos para obtener límites superiores nítidos sobre $R$ para $q$ de su talla y ritmo de crecimiento favoritos.