Hamming se dirigió

En matemáticas e informática , específicamente en el campo de la teoría de la codificación , la cota de Hamming es un límite para los parámetros de un código de bloques arbitrario . También se la conoce como cota de empaquetamiento de esferas o cota de volumen, debido a una interpretación que se refiere al empaquetamiento de esferas en la métrica de Hamming en el espacio de todas las palabras posibles. Esta cota impone una limitación importante a la eficiencia con la que cualquier código corrector de errores puede utilizar el espacio en el que se encuentran sus palabras de código. Un código que alcanza la cota de Hamming se denomina código perfecto .

Un mensaje original y una versión codificada se componen de un alfabeto de q letras. Cada palabra clave contiene n letras. El mensaje original (de longitud m ) es más corto que n letras. El mensaje se convierte en una palabra clave de n letras mediante un algoritmo de codificación, se transmite a través de un canal ruidoso y, finalmente, el receptor lo decodifica. El proceso de decodificación interpreta una palabra clave distorsionada, denominada simplemente palabra , como la palabra clave válida más cercana a la cadena recibida de n letras.

Matemáticamente, existen exactamente q ^m posibles mensajes de longitud m , y cada mensaje puede considerarse un vector de longitud m . El esquema de codificación convierte un vector m- dimensional en un vector n- dimensional. Son posibles exactamente q ^m palabras clave válidas, pero se puede recibir cualquiera de q ⁿ palabras, ya que el canal ruidoso podría distorsionar una o más de las n letras al transmitir una palabra clave.

Se deduce de la definición de${\displaystyle d}$que si como máximo

${\displaystyle t=\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor }$

Si se producen errores durante la transmisión de una palabra clave, la decodificación de distancia mínima la decodificará correctamente (es decir, decodificará la palabra recibida como la palabra clave que se envió). Por lo tanto, se dice que el código es capaz de corregir errores.${\displaystyle t}$errores.

Para cada palabra clave${\displaystyle c\in C}$Consideremos una bola de radio fijo.${\displaystyle t}$alrededor${\displaystyle c}$Cada par de estas bolas ( bolas de Hamming ) no se intersecan por el${\displaystyle t}$-propiedad correctora de errores.${\displaystyle m}$sea ​​el número de palabras en cada bola (es decir, el volumen de la bola). Una palabra que está en dicha bola puede desviarse como máximo${\displaystyle t}$componentes de aquellos del centro de la bola , que es una palabra clave. El número de tales palabras se obtiene entonces eligiendo hasta${\displaystyle t}$del${\displaystyle n}$componentes de una palabra clave para desviarse a uno de${\displaystyle (q-1)}$otros posibles valores (recuerde, el código es${\displaystyle q}$-ario: toma valores en${\displaystyle {\mathcal {A}}_{q}^{n}}$). De este modo,

${\displaystyle m={\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}.}$

${\displaystyle A_{q}(n,d)}$es el número total (máximo) de palabras clave en${\displaystyle C}$y por lo tanto, por definición de${\displaystyle t}$, el mayor número de bolas sin que dos bolas tengan una palabra en común. Tomando la unión de las palabras en estas bolas centradas en las palabras clave, resulta en un conjunto de palabras, cada una contada exactamente una vez, que es un subconjunto de${\displaystyle {\mathcal {A}}_{q}^{n}}$(dónde${\displaystyle |{\mathcal {A}}_{q}^{n}|=q^{n}}$palabras) y así:

${\displaystyle A_{q}(n,d)\times m=A_{q}(n,d)\times {\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}\leq q^{n}.}$

De dónde:

${\displaystyle A_{q}(n,d)\leq {\frac {q^{n}}{\begin{matrix}\sum _{k=0}^{t}{\binom {n}{k}}(q-1)^{k}\end{matrix}}}.}$

Para un${\displaystyle A_{q}(n,d)}$código C (un subconjunto de${\displaystyle {\mathcal {A}}_{q}^{n}}$), el radio de cobertura de C es el valor más pequeño de r tal que cada elemento de${\displaystyle {\mathcal {A}}_{q}^{n}}$está contenido en al menos una bola de radio r centrada en cada palabra clave de C. El radio de empaquetamiento de C es el mayor valor de s tal que el conjunto de bolas de radio s centradas en cada palabra clave de C son mutuamente disjuntas .

De la demostración de la cota de Hamming, se puede ver que para${\displaystyle t\,=\,\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor }$, tenemos:

s ≤ t y t ≤ r .

Por lo tanto, s ≤ r y si se cumple la igualdad, entonces s = r = t . El caso de igualdad significa que se alcanza la cota de Hamming.

Los códigos que alcanzan el límite de Hamming se denominan códigos perfectos . Los ejemplos incluyen códigos que tienen solo una palabra clave y códigos que son la totalidad de${\displaystyle {\mathcal {A}}_{q}^{n}}$Otro ejemplo lo proporcionan los códigos de repetición , donde cada símbolo del mensaje se repite un número fijo impar de veces para obtener una palabra clave donde q = 2. Todos estos ejemplos se denominan a menudo códigos perfectos triviales . En 1973, Tietäväinen demostró ^{[ 1 ]} que cualquier código perfecto no trivial sobre un alfabeto de potencia prima tiene los parámetros de un código de Hamming o un código de Golay .

Un código perfecto puede interpretarse como aquel en el que las bolas de radio de Hamming t centradas en las palabras clave llenan exactamente el espacio ( t es el radio de cobertura = radio de empaquetamiento). Un código cuasi-perfecto es aquel en el que las bolas de radio de Hamming t centradas en las palabras clave son disjuntas y las bolas de radio t + 1 cubren el espacio, posiblemente con algunas superposiciones. ^{[ 2 ]} Otra forma de decirlo es que un código es cuasi-perfecto si su radio de cobertura es uno mayor que su radio de empaquetamiento. ^{[ 3 ]}

• Gilbert-Varshamov está vinculado
• Griesmer se dirige
• Johnson se dirige
• Plotkin estaba atado
• Teoría de la distorsión de la tasa
• Singleton

• PJ Cameron; JA Thas; SE Payne (1976). "Polaridades de hexágonos generalizados y códigos perfectos". Geometriae Dedicata . 5 (4): 525– 528. doi : 10.1007/BF00150782 . S2CID 121071671 . 
• Hill, R. (1988). Un primer curso de teoría de la codificación . Oxford University Press . ISBN 0-19-853803-0.
• MacWilliams, FJ ; NJA Sloane (1977). La teoría de los códigos correctores de errores . North-Holland. ISBN 0-444-85193-3.
• Pless, V. (1982). Introducción a la teoría de los códigos correctores de errores . John Wiley & Sons. ISBN 0-471-08684-3.
• Roman, S. (1992), Codificación y teoría de la información , GTM , vol.  134, Nueva York: Springer-Verlag, ISBN 0-387-97812-7
• Tietäväinen, A. (1973). "Sobre la no existencia de códigos perfectos sobre cuerpos finitos" . SIAM J. Appl. Math . 24 : 88–96 . doi : 10.1137/0124010 .
• van Lint, JH (1992). Introducción a la teoría de la codificación . GTM . Vol.  86 (2.ª  ed.). Springer-Verlag. ISBN 3-540-54894-7.
• van Lint, JH (1975). "Un estudio de códigos perfectos" . Rocky Mountain Journal of Mathematics . 5 (2): 199– 224. doi : 10.1216/RMJ-1975-5-2-199 .