Hamming atado

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

En matemáticas e informática , en el campo de la teoría de la codificación , el límite de Hamming es un límite de los parámetros de un código de bloque arbitrario : también se conoce como límite de embalaje de esferas o límite de volumen a partir de una interpretación en términos de bolas de embalaje. en la métrica de Hamming en el espacio de todas las palabras posibles. Proporciona una limitación importante a 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 códigos de corrección de errores

Tanto un mensaje original como una versión codificada están compuestos en 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 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 confusa, denominada simplemente palabra , como la palabra clave válida "más cercana" a la cadena recibida de n letras.

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 m dimensiones en un vector de n dimensiones. Son posibles exactamente q ^m palabras de código válidas, pero cualquiera de las q ⁿ palabras puede recibirse porque el canal ruidoso podría 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 alfabético es un conjunto de símbolos con elementos. Se denota el conjunto de cadenas de longitud en el conjunto alfabético . (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 alfabético es cualquier conjunto alfabético que tenga elementos. (La elección del conjunto de alfabetos no influye en el resultado, siempre que el alfabeto sea del tamaño ). ${\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

Denotemos el tamaño máximo posible de un código de bloque ario de longitud y la distancia mínima de Hamming 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, la cota 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

Se deduce de la definición de que si a lo sumo ${\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 a distancia mínima la decodificará correctamente (es decir, decodifica la palabra recibida como la palabra clave que se envió). Por 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 . Cada par de estas bolas (esferas de Hamming) no se cruzan según 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 se encuentra en una bola de este tipo puede desviarse en la mayoría de los componentes de los del centro de la bola , que es una palabra en clave. El número de dichas palabras se obtiene eligiendo hasta uno de los componentes de una palabra de código para desviarlo a uno de otros posibles valores (recuerde, el código es -ario: toma valores en ). De este modo, ${\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 en código en , y por lo tanto, según la definición de , 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 palabras clave, se obtiene un conjunto de palabras, cada una contada precisamente una vez, es decir, un subconjunto de (donde palabras) y así: ${\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 embalaje.

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 clave de C son mutuamente disjuntas . ${\displaystyle A_{q}(n,d)}$ ${\displaystyle {\mathcal {A}}_{q}^{n}}$ ${\displaystyle {\mathcal {A}}_{q}^{n}}$

De la prueba de la cota de Hamming se puede ver 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.

codigos perfectos

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 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 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 potencia primaria tiene los parámetros de un código Hamming o un código Golay . ${\displaystyle \scriptstyle {\mathcal {A}}_{q}^{n}}$

Un código perfecto puede interpretarse como aquel en el que las bolas de radio de Hamming t centradas en palabras de código 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 palabras clave están separadas 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 casi perfecto si su radio de cobertura es uno mayor que su radio de empaquetadura. ^[3]

Ver también

• Gilbert-Varshamov obligado
• Griesmer obligado
• Johnson obligado
• Plotkin atado
• Teoría de la distorsión de la tasa
• Encuadernado singleton

Notas

1. Tietäväinen 1973.
2. McWilliams y Sloane, pág. 19
3. Romano 1992, pag. 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.
• Colina, R. (1988). Un primer curso de teoría de la codificación . Prensa de la Universidad de Oxford . ISBN 0-19-853803-0.
• MacWilliams, FJ ; NJA Sloane (1977). La teoría de los códigos correctores de errores . Holanda del Norte. ISBN 0-444-85193-3.
• Pless, V. (1982). Introducción a la teoría de los códigos correctores de errores . John Wiley e hijos. 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 inexistencia de códigos perfectos sobre campos finitos". SIAM J. Aplicación. Matemáticas . 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". Revista de Matemáticas de las Montañas Rocosas . 5 (2): 199–224. doi : 10.1216/RMJ-1975-5-2-199 .