Hamming obligado - Hamming bound

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 en los parámetros de un código de bloque arbitrario : también se conoce como límite de empaquetamiento de esferas o límite de volumen a partir de una interpretación en términos de empaquetamiento de bolas. en la métrica de Hamming en el espacio de todas las palabras posibles. Proporciona una limitación importante sobre 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 . Se dice que un código que alcanza el límite de Hamming es un código perfecto .

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

Un mensaje original y una versión codificada se componen 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 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, denominada simplemente una palabra , como la palabra de código 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 m- dimensional en un vector n- dimensional. 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 alfabético es un conjunto de símbolos con elementos. Se indica el conjunto de cadenas de longitud en el conjunto alfabético . (Hay cadenas distintas en este conjunto de cadenas.) Un código de bloque 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 alfabético no influye en el resultado, siempre que el alfabeto sea de tamaño ; por ejemplo, cualquier código de bloque definido mediante el alfabeto se puede convertir en uno que utilice el alfabeto mediante un cifrado de sustitución simple y viceversa. código de bloque de longitud 2 , las palabras de código y podrían convertirse a las palabras de código y viceversa. Es posible más de un cifrado de sustitución de este tipo, pero las diferencias son irrelevantes para el límite y su prueba). ${\ 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}$${\ Displaystyle {\ mathcal {A}} _ {3} = \ {1,2,3 \}}$${\ Displaystyle {\ mathcal {B}} _ {3} = \ {A, B, C \}}$${\ Displaystyle {\ text {1}} {\ text {2}}}$${\ Displaystyle {\ text {2}} {\ text {2}}}$${\ Displaystyle {\ text {A}} {\ text {B}}}$${\ Displaystyle {\ text {B}} {\ text {B}}}$

Definiendo el límite

Deje que denotan el tamaño máximo posible de un código ary bloque de longitud y mínima distancia de Hamming entre los elementos del código de bloque (necesariamente positivo 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

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}$

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

Para cada palabra de código , considere una bola de radio fijo alrededor . Cada par de estas bolas (esferas de Hamming) no se cruzan 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 la mayoría de los componentes de los del centro de la bola , que es una palabra clave. El número de tales palabras se obtiene eligiendo hasta de los componentes de una palabra de código para desviarse a uno de los otros valores posibles (recuerde, el código es -ary: 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 (máximo) número total de palabras de código en , y por lo tanto, según la definición de , el mayor número de bolas sin 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, da como resultado un conjunto de palabras, cada una contada precisamente una vez, que es un subconjunto de ( palabras donde ) 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 {matriz}} \ 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 {matriz}}}.}$

Radio de cobertura y radio de empaque

Artículo principal: Delone set

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

De la prueba del encuadernado 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.

Códigos 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 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, se demostró 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 uno 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 empaque). Un código cuasi-perfecto es aquel en el que las bolas de radio de Hamming t centradas en palabras de código están disjuntas y las bolas de radio t +1 cubren el espacio, posiblemente con algunas superposiciones. 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 empaque.

Ver también

• Griesmer obligado
• Límite de singleton
• Con destino a Gilbert-Varshamov
• Plotkin encuadernado
• Johnson obligado
• Teoría de la distorsión de la tasa

Notas

Referencias

• Raymond Hill (1988). Un primer curso de teoría de la codificación . Prensa de la Universidad de Oxford . ISBN   0-19-853803-0 .
• FJ MacWilliams ; NJA Sloane (1977). La teoría de los códigos de corrección de errores . Holanda Septentrional. ISBN   0-444-85193-3 .
• Vera Pless (1982). Introducción a la teoría de los códigos de corrección de errores . John Wiley e hijos. ISBN   0-471-08684-3 .
• Roman, Steven (1992), Teoría de la información y la codificación , GTM , 134 , Nueva York: Springer-Verlag, ISBN   0-387-97812-7
• JH van Lint (1992). Introducción a la teoría de la codificación . GTM . 86 (2ª ed.). Springer-Verlag. ISBN   3-540-54894-7 .
• JH van Lint (1975). "Una encuesta 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 .
• PJ Cameron; JA Thas; SE Payne (1976). "Polaridades de hexágonos generalizados y códigos perfectos". 5 : 525–528. doi : 10.1007 / BF00150782 . Citar diario requiere |journal= ( ayuda )