En la teoría de la codificación , los códigos de bloque son una familia grande e importante de códigos de corrección de errores que codifican datos en bloques. Existe una gran cantidad de ejemplos de códigos de bloque, muchos de los cuales tienen una amplia gama de aplicaciones prácticas. La definición abstracta de códigos de bloque es conceptualmente útil porque permite a los teóricos de la codificación, matemáticos e informáticos estudiar las limitaciones de todos los códigos de bloque de forma unificada. Estas limitaciones suelen adoptar la forma de límites que relacionan entre sí diferentes parámetros del código de bloque, como su velocidad y su capacidad para detectar y corregir errores.
Ejemplos de códigos de bloque son códigos Reed-Solomon , códigos de Hamming , códigos de Hadamard , códigos Expander , códigos de Golay , y los códigos de Reed-Muller . Estos ejemplos también pertenecen a la clase de códigos lineales y, por lo tanto, se denominan códigos de bloques lineales . Más particularmente, estos códigos se conocen como códigos de bloque algebraicos, o códigos de bloque cíclicos, porque pueden generarse utilizando polinomios booleanos.
Los códigos de bloque algebraicos se decodifican normalmente de forma rígida mediante decodificadores algebraicos. [ jerga ]
El término código de bloque también puede referirse a cualquier código de corrección de errores que actúe sobre un bloque de bits de datos de entrada para producir bits de datos de salida . En consecuencia, el codificador de bloques es un dispositivo sin memoria . Bajo esta definición, los códigos tales como códigos turbo , códigos convolucionales terminados y otros códigos decodificables iterativamente (códigos tipo turbo) también se considerarían códigos de bloque. Un codificador convolucional no terminado sería un ejemplo de un código sin bloque (sin marco), que tiene memoria y, en cambio, se clasifica como un código de árbol .
Este artículo trata de los "códigos de bloque algebraicos".
El código de bloque y sus parámetros
Códigos de corrección de errores se utilizan para fiable de transmisión de datos digitales sobre poco fiable canales de comunicación sujeta a ruido de canal . Cuando un remitente desea transmitir un flujo de datos posiblemente muy largo utilizando un código de bloque, el remitente divide el flujo en partes de un tamaño fijo. Cada una de estas piezas se llama mensaje y el procedimiento dado por el código de bloque codifica cada mensaje individualmente en una palabra de código, también llamada bloque en el contexto de los códigos de bloque. El remitente luego transmite todos los bloques al receptor, quien a su vez puede usar algún mecanismo de decodificación para (con suerte) recuperar los mensajes originales de los bloques recibidos posiblemente dañados. El rendimiento y el éxito de la transmisión general dependen de los parámetros del canal y del código de bloque.
Formalmente, un código de bloque es un mapeo inyectivo
- .
Aquí, es un finito y no vacío conjunto y y son enteros. El significado y la importancia de estos tres parámetros y otros parámetros relacionados con el código se describen a continuación.
El alfabeto Σ
El flujo de datos a codificar se modela como una cadena sobre algún alfabeto . El tamaño del alfabeto a menudo se escribe como . Si, entonces el código de bloque se denomina código de bloque binario . En muchas aplicaciones es útil considerarpara ser un poder primordial , y para identificarcon el campo finito .
La longitud del mensaje k
Los mensajes son elementos de , es decir, cadenas de longitud . De ahí el númerose denomina longitud o dimensión del mensaje de un código de bloque.
La longitud del bloque n
La longitud del bloque de un código de bloque es el número de símbolos en un bloque. Por lo tanto, los elementos de son cadenas de longitud y corresponden a los bloques que puede recibir el receptor. Por eso también se les llama palabras recibidas. Si por algún mensaje , luego se llama la palabra clave de .
La tasa R
La tasa de un código de bloque se define como la relación entre la longitud de su mensaje y la longitud de su bloque:
- .
Una tasa alta significa que la cantidad de mensaje real por bloque transmitido es alta. En este sentido, la tasa mide la velocidad de transmisión y la cantidadmide la sobrecarga que se produce debido a la codificación con el código de bloque. Es un simple hecho teórico de información que la tasa no puede excederdado que, en general, los datos no pueden comprimirse sin pérdidas. Formalmente, esto se deriva del hecho de que el código es un mapa inyectivo.
La distancia d
La distancia o distancia mínima d de un código de bloque es el número mínimo de posiciones en las que dos palabras de código distintas difieren, y la distancia relativa es la fracción . Formalmente, por palabras recibidas, dejar denotar la distancia de Hamming entre y , es decir, el número de posiciones en las que y diferir de. Entonces la distancia mínima del código Se define como
- .
Dado que cualquier código tiene que ser inyectivo , dos palabras de código cualesquiera no estarán de acuerdo en al menos una posición, por lo que la distancia de cualquier código es al menos. Además, la distancia es igual al peso mínimo para códigos de bloques lineales porque:
- .
Una distancia mayor permite una mayor corrección y detección de errores. Por ejemplo, si solo consideramos los errores que pueden cambiar los símbolos de la palabra de código enviada pero nunca los borramos ni los agregamos, entonces el número de errores es el número de posiciones en las que la palabra de código enviada y la palabra recibida difieren. Un código con distancia d permite al receptor detectar hasta errores de transmisión desde el cambio las posiciones de una palabra de código nunca pueden producir accidentalmente otra palabra de código. Además, si no más deCuando se producen errores de transmisión, el receptor puede decodificar de forma única la palabra recibida en una palabra de código. Esto se debe a que cada palabra recibida tiene como máximo una palabra de código a distancia. Si mas deocurren errores de transmisión, el receptor no puede decodificar de forma única la palabra recibida en general, ya que puede haber varias palabras de código posibles. Una forma en que el receptor puede hacer frente a esta situación es utilizar la decodificación de lista , en la que el decodificador genera una lista de todas las palabras de código en un determinado radio.
Notación popular
La notación describe un código de bloque sobre un alfabeto de tamaño , con una longitud de bloque , longitud del mensaje y distancia . Si el código de bloque es un código de bloque lineal, entonces los corchetes en la notaciónse utilizan para representar ese hecho. Para códigos binarios con, el índice a veces se elimina. Para códigos separables de distancia máxima , la distancia es siempre, pero a veces no se conoce la distancia precisa, no es trivial de probar o afirmar, o no es necesaria. En tales casos, el-es posible que falte un componente.
A veces, especialmente para los códigos que no son de bloque, la notación se utiliza para códigos que contienen palabras en clave de longitud . Para códigos de bloque con mensajes de longitud sobre un alfabeto de tamaño , este número sería .
Ejemplos de
Como se mencionó anteriormente, existe una gran cantidad de códigos de corrección de errores que en realidad son códigos de bloque. El primer código de corrección de errores fue el código Hamming (7,4) , desarrollado por Richard W. Hamming en 1950. Este código transforma un mensaje de 4 bits en una palabra de código de 7 bits añadiendo 3 bits de paridad. Por lo tanto, este código es un código de bloque. Resulta que también es un código lineal y que tiene una distancia 3. En la notación abreviada anterior, esto significa que el código Hamming (7,4) es un código.
Los códigos Reed-Solomon son una familia de códigos con y siendo un poder primordial . Los códigos de rango son una familia de códigos con . Los códigos de Hadamard son una familia de códigos con y .
Propiedades de detección y corrección de errores
Una palabra en clave podría considerarse como un punto en el -espacio de dimensión y el codigo es el subconjunto de . Un codigo tiene distancia significa que , no hay otra palabra clave en la bola de Hamming centrada en con radio , que se define como la colección de -dimensiona palabras cuya distancia de Hamming a no es más que . Similar, con distancia (mínima) tiene las siguientes propiedades:
- puede detectar errores: porque una palabra en clave es la única palabra en clave en la bola de Hamming centrada en sí misma con radio , sin patrón de error de o menos errores podrían cambiar una palabra de código a otra. Cuando el receptor detecta que el vector recibido no es una palabra clave de, los errores se detectan (pero no hay garantía de corregirlos).
- puede corregir errores. Porque una palabra en clave es la única palabra en clave en la bola de Hamming centrada en sí misma con radio , las dos bolas de Hamming centradas en dos palabras de código diferentes respectivamente con ambos radios no se superpongan entre sí. Por lo tanto, si consideramos la corrección de errores como encontrar la palabra de código más cercana a la palabra recibida, siempre que el número de errores no sea superior a , solo hay una palabra de código en la bola de hamming centrada en con radio , por lo tanto, todos los errores pueden corregirse.
- Para decodificar en presencia de más de se pueden utilizar errores, decodificación de lista o decodificación de máxima probabilidad .
- puede corregir borrados . Por el borrado significa que la posición del símbolo de borrado se conoce. La corrección se puede lograr mediante-pasando la decodificación: En pasar la posición borrada se llena con el símbolo y se lleva a cabo la corrección de errores. Debe pasar que el número de errores no sea más de y por lo tanto, los borrados podrían corregirse.
Límites inferior y superior de los códigos de bloque
Familia de códigos
se llama familia de códigos , donde es un código con aumento monótono .
La tasa de la familia de códigos C se define como
La distancia relativa de la familia de códigos C se define como
Para explorar la relación entre y , se conoce un conjunto de límites superior e inferior de códigos de bloque.
Hamming obligado
Límite de singleton
El límite de Singleton es que la suma de la tasa y la distancia relativa de un código de bloque no puede ser mucho mayor que 1:
- .
En otras palabras, cada código de bloque satisface la desigualdad . Los códigos Reed-Solomon son ejemplos no triviales de códigos que satisfacen el límite único con igualdad.
Plotkin encuadernado
Para , . En otras palabras,.
Para el caso general, los siguientes límites de Plotkin son válidos para cualquier con distancia d :
- Si
- Si
Para cualquier código q -ary con distancia,
Con destino a Gilbert-Varshamov
, dónde , es la función de entropía q -ary.
Johnson obligado
Definir .
Dejarser el número máximo de palabras de código en una bola de Hamming de radio e para cualquier códigode distancia d .
Luego tenemos el Johnson Bound :, Si
Con destino a Elias-Bassalygo
Empaquetaduras de esferas y celosías
Los códigos de bloque están vinculados al problema del empaquetado de esferas, que ha recibido cierta atención a lo largo de los años. En dos dimensiones, es fácil de visualizar. Tome un montón de monedas de un centavo sobre la mesa y júntelas. El resultado es un patrón hexagonal como un nido de abejas. Pero los códigos de bloque se basan en más dimensiones que no se pueden visualizar fácilmente. El poderoso código Golay utilizado en las comunicaciones en el espacio profundo utiliza 24 dimensiones. Si se utiliza como un código binario (que suele ser), las dimensiones se refieren a la longitud de la palabra de código como se define anteriormente.
La teoría de la codificación utiliza el modelo de esfera N- dimensional. Por ejemplo, cuántos centavos se pueden empaquetar en un círculo sobre una mesa o en 3 dimensiones, cuántas canicas se pueden empaquetar en un globo. Otras consideraciones entran en la elección de un código. Por ejemplo, el empaque hexagonal en la restricción de una caja rectangular dejará un espacio vacío en las esquinas. A medida que aumentan las dimensiones, el porcentaje de espacio vacío se reduce. Pero en determinadas dimensiones, el embalaje ocupa todo el espacio y estos códigos son los llamados códigos perfectos. Hay muy pocos de estos códigos.
Otra propiedad es el número de vecinos que puede tener una sola palabra de código. [1] Nuevamente, considere las monedas de un centavo como ejemplo. Primero empacamos los centavos en una cuadrícula rectangular. Cada centavo tendrá 4 vecinos cercanos (y 4 en las esquinas que están más lejos). En un hexágono, cada centavo tendrá 6 vecinos cercanos. Respectivamente, en tres y cuatro dimensiones, el empaque máximo viene dado por el de 12 caras y el de 24 celdas con 12 y 24 vecinos, respectivamente. Cuando aumentamos las dimensiones, el número de vecinos cercanos aumenta muy rápidamente. En general, el valor viene dado por los números de besos .
El resultado es que también aumenta el número de formas en que el ruido hace que el receptor elija un vecino (por lo tanto, un error). Esta es una limitación fundamental de los códigos de bloque y, de hecho, de todos los códigos. Puede ser más difícil provocar un error en un solo vecino, pero el número de vecinos puede ser lo suficientemente grande como para que la probabilidad total de error sufra realmente. [1]
Ver también
- Capacidad de canal
- Teorema de Shannon-Hartley
- Canal ruidoso
- Decodificación de listas [1]
- Embalaje de esfera
Referencias
- ↑ a b c Christian Schlegel y Lance Pérez (2004). Codificación enrejado y turbo . Wiley-IEEE. pag. 73. ISBN 978-0-471-22755-7.
- JH van Lint (1992). Introducción a la teoría de la codificación . GTM . 86 (2ª ed.). Springer-Verlag. pag. 31 . ISBN 3-540-54894-7.
- FJ MacWilliams ; NJA Sloane (1977). La teoría de los códigos de corrección de errores . Holanda Septentrional. pag. 35 . ISBN 0-444-85193-3.
- W. Huffman; V.Pless (2003). Fundamentos de los códigos de corrección de errores . Prensa de la Universidad de Cambridge. ISBN 978-0-521-78280-7.
- S. Lin; DJ Jr. Costello (1983). Codificación de control de errores: fundamentos y aplicaciones . Prentice Hall. ISBN 0-13-283796-X.
enlaces externos
- Charan Langton (2001) Conceptos de codificación y codificación de bloques