Hamming atado

Límite de los parámetros de un código de bloque

En matemáticas y ciencias de la computación , en el campo de la teoría de codificación , el límite de Hamming es un límite en los parámetros de un código de bloque arbitrario : también se lo conoce como límite de empaquetamiento de esferas o límite de volumen a partir de una interpretación en términos de empaquetar bolas en la métrica de Hamming en el espacio de todas las palabras posibles. Implica una limitación importante en la eficiencia con la que cualquier código de corrección de errores puede utilizar el espacio en el que están incrustadas sus palabras de código . Un código que alcanza el límite de Hamming se dice que es un código perfecto .

Antecedentes sobre los códigos de corrección de errores

Tanto el mensaje original como la versión codificada se componen de un alfabeto de q letras. Cada palabra de código contiene n letras. El mensaje original (de longitud m ) es más corto que n letras. El mensaje se convierte en una palabra de código 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 de código ilegible, a la que simplemente se hace referencia como palabra , como la palabra de código válida "más cercana" a la cadena de n letras recibida.

Matemáticamente, hay exactamente q ^m mensajes posibles de longitud m , y cada mensaje puede considerarse como un vector de longitud m . El esquema de codificación convierte un vector de dimensión m en un vector de dimensión n . Son posibles exactamente q ^m palabras de código válidas, pero se puede recibir cualquiera de las q ⁿ palabras porque el canal ruidoso puede distorsionar una o más de las n letras cuando se transmite una palabra de código.

Declaración del obligado

Definiciones preliminares

Un conjunto de alfabetos es un conjunto de símbolos con elementos. El conjunto de cadenas de longitud del conjunto de alfabetos se denotan como . (Hay cadenas distintas en este conjunto de cadenas). Un código de bloque -ario de longitud es un subconjunto de las cadenas de , donde el conjunto de alfabetos es cualquier conjunto de alfabetos que tenga elementos. (La elección del conjunto de alfabetos no afecta al resultado, siempre que el alfabeto tenga un tamaño de .) ${\displaystyle {\mathcal {A}}_{q}}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {A}}_{q}}$ ${\displaystyle {\mathcal {A}}_{q}^{n}}$ ${\displaystyle q^{n}}$ ${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {A}}_{q}^{n}}$ ${\displaystyle {\mathcal {A}}_{q}}$ ${\displaystyle q}$ ${\displaystyle {\mathcal {A}}_{q}}$ ${\displaystyle q}$

Definiendo el límite

Sea el tamaño máximo posible de un código de bloque -ario de longitud y la distancia de Hamming mínima entre elementos del código de bloque (necesariamente positiva para ). ${\displaystyle \ A_{q}(n,d)}$ ${\displaystyle q}$ ${\displaystyle \ C}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle q^{n}>1}$

Entonces, el límite de Hamming es:

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

dónde

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

Prueba

De la definición se desprende que si como máximo ${\displaystyle d}$

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

Si se cometen 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 enviada). Por lo tanto, se dice que el código es capaz de corregir errores. ${\displaystyle t}$

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

${\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 de código en , y por lo tanto, por la definición de , el mayor número de bolas sin que haya dos bolas que tengan una palabra en común. Tomando la unión de las palabras en estas bolas centradas en palabras de código, se obtiene un conjunto de palabras, cada una contada exactamente una vez, que es un subconjunto de (donde palabras) y por lo tanto: ${\displaystyle C}$ ${\displaystyle t}$ ${\displaystyle {\mathcal {A}}_{q}^{n}}$ ${\displaystyle |{\mathcal {A}}_{q}^{n}|=q^{n}}$

${\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}}}.}$

Radio de cobertura y radio de empaquetamiento

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

De la prueba del límite de Hamming se desprende que para , tenemos: ${\displaystyle t\,=\,\left\lfloor {\frac {1}{2}}(d-1)\right\rfloor }$

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 el límite de Hamming.

Códigos perfectos

Los códigos que alcanzan el límite de Hamming se denominan códigos perfectos . Algunos ejemplos incluyen códigos que tienen solo una palabra de código y códigos que son la totalidad de . Otro ejemplo lo dan 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 de código donde q = 2. Todos estos ejemplos a menudo se denominan códigos perfectos triviales . En 1973, Tietäväinen demostró ^[1] que cualquier código perfecto no trivial sobre un alfabeto de potencias primo tiene los parámetros de un código de Hamming o un código de Golay . ${\displaystyle \scriptstyle {\mathcal {A}}_{q}^{n}}$

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

Véase también

• Límite Gilbert-Varshamov
• Griesmer atado
• Johnson se dirige hacia
• Plotkin atado
• Teoría de la distorsión de la tasa
• Límite singleton

Notas

1. Tietäväinen 1973.
2. McWilliams y Sloane, pág. 19
3. Romano 1992, pág. 140

Referencias

• 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 sobre 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 de corrección de errores . Holanda Septentrional. ISBN 0-444-85193-3.
• Pless, V. (1982). Introducción a la teoría de códigos de corrección de errores . John Wiley & Sons. ISBN 0-471-08684-3.
• Roman, S. (1992), Teoría de la codificación y la información , GTM , vol. 134, Nueva York: Springer-Verlag, ISBN 0-387-97812-7
• Tietäväinen, A. (1973). "Sobre la inexistencia 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 .