Código de bloque

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úa 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 .${\displaystyle k}$${\displaystyle n}$${\displaystyle (n,k)}$

Este artículo trata sobre 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 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

${\displaystyle C:\Sigma ^{k}\to \Sigma ^{n}}$.

En este caso, 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.${\displaystyle \Sigma }$${\displaystyle k}$${\displaystyle 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 considerarlo como una potencia principal e identificarse con el campo finito .${\displaystyle \Sigma }$${\displaystyle |\Sigma |}$${\displaystyle q}$${\displaystyle q=2}$${\displaystyle q}$${\displaystyle \Sigma }$ ${\displaystyle \mathbb {F} _{q}}$

La longitud del mensaje k

Los mensajes son elementos de , es decir, cadenas de longitud . Por lo tanto, el número se denomina longitud o dimensión del mensaje de un código de bloque.${\displaystyle m}$${\displaystyle \Sigma ^{k}}$${\displaystyle k}$${\displaystyle k}$

La longitud del bloque n

La longitud de bloque de un código de bloque es el número de símbolos en un bloque. Por tanto, los elementos de son cadenas de longitud y corresponden a bloques que pueden ser recibidos por el receptor. Por eso también se les llama palabras recibidas. Si es para algún mensaje , entonces se llama la palabra clave de .${\displaystyle n}$${\displaystyle c}$${\displaystyle \Sigma ^{n}}$${\displaystyle n}$${\displaystyle c=C(m)}$${\displaystyle m}$${\displaystyle c}$${\displaystyle m}$

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:

${\displaystyle R=k/n}$.

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 cantidad mide la sobrecarga que se produce debido a la codificación con el código de bloque. Es un hecho teórico de información simple que la tasa no puede exceder ya que los datos no pueden comprimirse sin pérdidas en general. Formalmente, esto se deriva del hecho de que el código es un mapa inyectivo.${\displaystyle 1-R}$${\displaystyle 1}$${\displaystyle C}$

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 difieren dos palabras de código distintas, y la distancia relativa es la fracción . Formalmente, para las palabras recibidas , denotemos la distancia de Hamming entre y , es decir, el número de posiciones en las que y difieren. Entonces la distancia mínima del código se define como${\displaystyle \delta }$${\displaystyle d/n}$${\displaystyle c_{1},c_{2}\in \Sigma ^{n}}$${\displaystyle \Delta (c_{1},c_{2})}$${\displaystyle c_{1}}$${\displaystyle c_{2}}$${\displaystyle c_{1}}$${\displaystyle c_{2}}$${\displaystyle d}$${\displaystyle C}$

${\displaystyle d:=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]}$.

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:${\displaystyle 1}$

${\displaystyle \min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [C(m_{1}),C(m_{2})]=\min _{m_{1},m_{2}\in \Sigma ^{k} \atop m_{1}\neq m_{2}}\Delta [\mathbf {0} ,C(m_{1})+C(m_{2})]=\min _{m\in \Sigma ^{k} \atop m\neq \mathbf {0} }w[C(m)]=w_{\min }}$.

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, ya que el cambio de posición de una palabra de código nunca puede producir accidentalmente otra palabra de código. Además, si sólo 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 de${\displaystyle d-1}$${\displaystyle d-1}$${\displaystyle (d-1)/2}$${\displaystyle (d-1)/2}$${\displaystyle (d-1)/2}$se producen 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 , una longitud de mensaje y una distancia . Si el código de bloque es un código de bloque lineal, entonces los corchetes en la notación se utilizan para representar ese hecho. Para los códigos binarios con , el índice a veces se elimina. Para los códigos separables de distancia máxima , la distancia es siempre , pero a veces la distancia precisa no se conoce, no es trivial para probar o afirmar, o no es necesaria. En tales casos, es posible que falte el componente-.${\displaystyle (n,k,d)_{q}}$${\displaystyle \Sigma }$${\displaystyle q}$${\displaystyle n}$${\displaystyle k}$${\displaystyle d}$${\displaystyle [n,k,d]_{q}}$${\displaystyle q=2}$${\displaystyle d=n-k+1}$${\displaystyle d}$

A veces, especialmente para códigos que no son de bloque, la notación se usa para códigos que contienen palabras de código de longitud . Para códigos de bloque con mensajes de longitud superior a un alfabeto de tamaño , este número sería .${\displaystyle (n,M,d)_{q}}$${\displaystyle M}$${\displaystyle n}$${\displaystyle k}$${\displaystyle q}$${\displaystyle M=q^{k}}$

Ejemplos

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 de Hamming (7,4) es un código.${\displaystyle [7,4,3]_{2}}$

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 .${\displaystyle [n,k,d]_{q}}$${\displaystyle d=n-k+1}$${\displaystyle q}$${\displaystyle [n,k,d]_{q}}$${\displaystyle d\leq n-k+1}$${\displaystyle [n,k,d]_{2}}$${\displaystyle n=2^{k-1}}$${\displaystyle d=2^{k-2}}$

Propiedades de detección y corrección de errores

Una palabra de código podría considerarse como un punto en el espacio de dimensión y el código es el subconjunto de . Un código tiene distancia significa que no hay otra palabra de código en la bola de Hamming centrada en con radio , que se define como la colección de palabras de dimensión cuya distancia de Hamming a no es mayor que . Del mismo modo, con distancia (mínima) tiene las siguientes propiedades:${\displaystyle c\in \Sigma ^{n}}$${\displaystyle n}$${\displaystyle \Sigma ^{n}}$${\displaystyle {\mathcal {C}}}$${\displaystyle \Sigma ^{n}}$${\displaystyle {\mathcal {C}}}$${\displaystyle d}$${\displaystyle \forall c\in {\mathcal {C}}}$${\displaystyle c}$${\displaystyle d-1}$${\displaystyle n}$${\displaystyle c}$${\displaystyle d-1}$${\displaystyle {\mathcal {C}}}$${\displaystyle d}$

• ${\displaystyle {\mathcal {C}}}$puede detectar errores: debido a que una palabra de código es la única palabra de código en la bola de Hamming centrada en sí misma con radio , ningún patrón de error 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 de código de , se detectan los errores (pero no hay garantía de corregirlos).${\displaystyle d-1}$${\displaystyle c}$${\displaystyle d-1}$${\displaystyle d-1}$${\displaystyle {\mathcal {C}}}$
• ${\displaystyle {\mathcal {C}}}$puede corregir errores. Debido a que una palabra de código es la única palabra de código 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 superponen entre sí. Por lo tanto, si consideramos que la corrección de errores es encontrar la palabra de código más cercana a la palabra recibida , siempre que el número de errores no sea mayor , solo hay una palabra de código en la bola de hamming centrada en el radio , por lo tanto, todos los errores podrían corregirse. .${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$${\displaystyle c}$${\displaystyle d-1}$${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$${\displaystyle y}$${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$${\displaystyle y}$${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$
• Para decodificar en presencia de más que errores, se puede utilizar la decodificación de lista o la decodificación de máxima verosimilitud .${\displaystyle (d-1)/2}$
• ${\displaystyle {\mathcal {C}}}$puede corregir borrados . Por el borrado significa que la posición del símbolo de borrado se conoce. La corrección podría lograrse sin pasar por la decodificación: al pasar, la posición borrada se rellena con el símbolo y se lleva a cabo la corrección del error. Debe pasar que el número de errores no sea mayor y, por lo tanto, los borrados podrían corregirse.${\displaystyle d-1}$ ${\displaystyle q}$${\displaystyle i^{th}}$${\displaystyle i^{th}}$${\displaystyle \textstyle \left\lfloor {{d-1} \over 2}\right\rfloor }$

Límites inferior y superior de los códigos de bloque

Límite de Hamming

Hay límites teóricos (como el límite de Hamming), pero otra cuestión es qué códigos se pueden construir realmente. Es como empacar esferas en una caja de muchas dimensiones. Este diagrama muestra los códigos construibles, que son lineales y binarios. El eje x muestra el número de símbolos protegidos k , el eje y el número de símbolos de verificación necesarios n – k . Se muestran los límites para diferentes distancias de Hamming desde 1 (sin protección) a 34. Los códigos perfectos están marcados con puntos:

• naranja claro en el eje x : códigos triviales desprotegidos
• naranja en el eje y : códigos de repetición triviales
• naranja oscuro en el conjunto de datos d = 3: códigos Hamming perfectos clásicos
• rojo oscuro y más grande: el único código Golay binario perfecto

Familia de códigos

${\displaystyle C=\{C_{i}\}_{i\geq 1}}$se llama familia de códigos , donde es un código con aumento monótono .${\displaystyle C_{i}}$${\displaystyle (n_{i},k_{i},d_{i})_{q}}$${\displaystyle n_{i}}$

La tasa de la familia de códigos C se define como${\displaystyle R(C)=\lim _{i\to \infty }{k_{i} \over n_{i}}}$

La distancia relativa de la familia de códigos C se define como${\displaystyle \delta (C)=\lim _{i\to \infty }{d_{i} \over n_{i}}}$

Para explorar la relación entre y , se conocen un conjunto de límites superior e inferior de códigos de bloque.${\displaystyle R(C)}$${\displaystyle \delta (C)}$

Hamming obligado

Artículo principal: Hamming obligado

${\displaystyle R\leq 1-{1 \over n}\cdot \log _{q}\cdot \left[\sum _{i=0}^{\left\lfloor {{\delta \cdot n-1} \over 2}\right\rfloor }{\binom {n}{i}}(q-1)^{i}\right]}$

Singleton obligado

Artículo principal: Singleton obligado

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:

${\displaystyle R+\delta \leq 1+{\frac {1}{n}}}$.

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.${\displaystyle k+d\leq n+1}$

Atado a Plotkin

Artículo principal: Plotkin encuadernado

Para , . En otras palabras, .${\displaystyle q=2}$${\displaystyle R+2\delta \leq 1}$${\displaystyle k+2d\leq n}$

Para el caso general, los siguientes límites de Plotkin son válidos para cualquiera con distancia d :${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$

1. Si ${\displaystyle d=\left(1-{1 \over q}\right)n,|C|\leq 2qn}$
2. Si ${\displaystyle d>\left(1-{1 \over q}\right)n,|C|\leq {qd \over {qd-\left(q-1\right)n}}}$

Para cualquier código q -ary con distancia ,${\displaystyle \delta }$${\displaystyle R\leq 1-\left({q \over {q-1}}\right)\delta +o\left(1\right)}$

Atado a Gilbert-Varshamov

Artículo principal: Gilbert-Varshamov encuadernado

${\displaystyle R\geq 1-H_{q}\left(\delta \right)-\epsilon }$, donde , es la función de entropía q -ary.${\displaystyle 0\leq \delta \leq 1-{1 \over q},0\leq \epsilon \leq 1-H_{q}\left(\delta \right)}$${\displaystyle H_{q}\left(x\right)~{\overset {\underset {\mathrm {def} }{}}{=}}~-x\cdot \log _{q}{x \over {q-1}}-\left(1-x\right)\cdot \log _{q}{\left(1-x\right)}}$

Johnson obligado

Artículo principal: Johnson obligado

Definir . Sea el número máximo de palabras de código en una bola de Hamming de radio e para cualquier código de distancia d .${\displaystyle J_{q}\left(\delta \right)~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(1-{1 \over q}\right)\left(1-{\sqrt {1-{q\delta \over {q-1}}}}\right)}$
${\displaystyle J_{q}\left(n,d,e\right)}$${\displaystyle C\subseteq \mathbb {F} _{q}^{n}}$

Luego tenemos el Johnson Bound  :, si${\displaystyle J_{q}\left(n,d,e\right)\leq qnd}$${\displaystyle {e \over n}\leq {{q-1} \over q}\left({1-{\sqrt {1-{q \over {q-1}}\cdot {d \over n}}}}\,\right)=J_{q}\left({d \over n}\right)}$

Elias-Bassalygo encuadernado

Artículo principal: Elias Bassalygo encuadernado

${\displaystyle R={\log _{q}{|C|} \over n}\leq 1-H_{q}\left(J_{q}\left(\delta \right)\right)+o\left(1\right)}$

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 del 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

1. Christian Schlegel y Lance Pérez (2004). Codificación Trellis y turbo . Wiley-IEEE. pag. 73. ISBN 978-0-471-22755-7.

Este artículo necesita citas adicionales para su verificación . Por favor, ayuda a mejorar este artículo mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado. Buscar fuentes:  "Código de bloque"  -  noticias  · periódicos  · libros  · académico  · JSTOR ( septiembre de 2008 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

• 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