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 sus palabras de códigoestán incrustados. 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 n 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 alfabeto es un conjunto de símbolos con elementos. El conjunto de cuerdas de longitud. en el conjunto de alfabeto se denotan . (Existen cadenas distintas en este conjunto de cadenas). -código de bloque de longitud es un subconjunto de las cadenas de , donde el alfabeto ¿Hay algún conjunto de alfabeto que tenga elementos. (La elección del alfabeto no hace ninguna diferencia en el resultado, siempre que el alfabeto sea de tamaño ; por ejemplo, cualquier código de bloque definido usando el alfabeto se puede convertir a uno usando el alfabeto mediante un cifrado de sustitución simple y viceversa. EG para el código de bloque de longitud 2 , las palabras de código y podría convertirse a las palabras de código y 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).
Definiendo el límite
Dejar denotar el tamaño máximo posible de un -código de bloque de orden de longitud y distancia mínima de Hamming entre elementos del código de bloque (necesariamente positivo para ).
Entonces, el límite de Hamming es:
dónde
Prueba
Se deduce de la definición de que si a lo sumo
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 lo tanto, se dice que el código es capaz de corregir errores.
Para cada palabra en clave , considere una bola de radio fijo alrededor . Cada par de estas bolas (esferas de Hamming) no se cruzan por el-propiedad de corrección de errores. Dejarser el número de palabras en cada bola (en otras palabras, el volumen de la bola). Una palabra que está en una bola así puede desviarse como máximocomponentes de los del centro de la bola , que es una palabra clave. El número de tales palabras se obtiene eligiendo hasta de El componentes de una palabra clave para desviarse a uno de posibles otros valores (recuerde, el código es -ary: toma valores en ). Por lo tanto,
es el (máximo) número total de palabras de código en , y así, por 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 (dónde palabras) y así:
De dónde:
Radio de cobertura y radio de empaque
Por 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 deestá 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.
De la prueba del encuadernado de Hamming, se puede ver que para , 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 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 . [1]
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. [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 empaque. [3]
Ver también
Notas
- ^ Hill (1988) p. 102
- ^ McWilliams y Sloane, p. 19
- ^ Roman 1992 , pág. 140
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 . Cite journal requiere
|journal=
( ayuda )