código de bloque

Familia de códigos de corrección de errores que codifican datos en bloques.

En 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 una manera 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 los códigos Reed-Solomon , los códigos Hamming , los códigos Hadamard , los códigos Expander , los códigos Golay y los códigos 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 bloques algebraicos o códigos de bloques cíclicos, porque pueden generarse utilizando polinomios booleanos.

Los códigos de bloques algebraicos suelen descodificarse 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 . Según esta definición, los códigos como los códigos turbo , los códigos convolucionales terminados y otros códigos iterativamente decodificables (códigos tipo turbo) también se considerarían códigos de bloque. Un codificador convolucional no terminado sería un ejemplo de 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 bloques algebraicos".

El código de bloque y sus parámetros.

Los códigos de corrección de errores se utilizan para transmitir datos digitales de manera confiable a través de canales de comunicación no confiables sujetos al ruido del canal . Cuando un remitente quiere transmitir un flujo de datos posiblemente muy largo utilizando un código de bloque, el remitente divide el flujo en partes de algún tamaño fijo. Cada una de estas piezas se denomina mensaje y el procedimiento dado por el código de bloque codifica cada mensaje individualmente en una palabra en clave, también denominada bloque en el contexto de los códigos de bloque. Luego, el remitente transmite todos los bloques al receptor, quien a su vez puede utilizar 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}}$.

Aquí, es un conjunto finito y no vacío y y son números 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 prima e identificarlo 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 del mensaje o dimensión de un código de bloque. ${\displaystyle m}$ ${\displaystyle \Sigma ^{k}}$ ${\displaystyle k}$ ${\displaystyle k}$

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 tanto, los elementos de son cadenas de longitud y corresponden a bloques que puede recibir el receptor. De ahí que también se les llame palabras recibidas. Si se trata de algún mensaje , se denomina 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 velocidad de un código de bloque se define como la relación entre la longitud del mensaje y la longitud del 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 por la codificación con el código de bloque. Es un hecho teórico de información simple que la velocidad no puede excederse, ya que los datos, en general, no se pueden comprimir sin pérdidas. 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 dos palabras de código distintas difieren, 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 equivale 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 errores que pueden cambiar los símbolos de la palabra clave enviada pero nunca los borramos ni los agregamos, entonces el número de errores es el número de posiciones en las que difieren la palabra clave enviada y la palabra recibida. Un código con distancia d permite que el receptor detecte hasta errores de transmisión, ya que cambiar las posiciones de una palabra de código nunca puede generar accidentalmente otra palabra de código. Además, si no se producen más que 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 se producen más de 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 que tiene el receptor de afrontar esta situación es utilizar la decodificación de listas , en la que el decodificador genera una lista de todas las palabras en clave en un radio determinado. ${\displaystyle d-1}$ ${\displaystyle d-1}$ ${\displaystyle (d-1)/2}$ ${\displaystyle (d-1)/2}$ ${\displaystyle (d-1)/2}$

Notación popular

La notación describe un código de bloque sobre un alfabeto de tamaño , con una longitud de bloque , longitud de mensaje y 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 códigos binarios con , a veces se elimina el índice. Para los códigos separables de distancia máxima , la distancia siempre es , pero a veces no se conoce la distancia precisa, no es trivial probarla o indicarla, 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 bloqueo. 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 que consta de 4 bits en una palabra clave de 7 bits añadiendo 3 bits de paridad. Por tanto, este código es un código de bloque. Resulta que también es un código lineal y que tiene distancia 3. En la notación abreviada anterior, esto significa que el código Hamming(7,4) es un código. ${\displaystyle [7,4,3]_{2}}$

Los códigos Reed-Solomon son una familia de códigos que tienen y son un poder principal . Los códigos de rango son una familia de códigos con . Los códigos 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 dimensiones 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 dimensiones cuya distancia de Hamming no es mayor que . De manera similar, 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 en clave es la única palabra en clave en la bola de Hamming centrada en sí misma con un radio , ningún patrón de error o menos errores podrían cambiar una palabra en clave por otra. Cuando el receptor detecta que el vector recibido no es una palabra clave de , se detectan los errores (pero no hay garantía de corrección). ${\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 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 en clave diferentes respectivamente con ambos radios no se superponen entre sí. Por lo tanto, si consideramos que la corrección de errores consiste en encontrar la palabra de código más cercana a la palabra recibida , siempre que el número de errores no sea mayor que , 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 probabilidad . ${\displaystyle (d-1)/2}$
• ${\displaystyle {\mathcal {C}}}$Puede corregir borrados . Por borrado se entiende que se conoce la posición del símbolo borrado. La corrección se puede lograr mediante la decodificación de paso: al pasar, la posición borrada se llena con el símbolo y se lleva a cabo la corrección de errores. Debe haber un paso para que el número de errores no sea mayor y por lo tanto se puedan corregir los borrados. ${\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 códigos de bloque

Límite de Hamming ^{[ se necesita aclaración ]}

Existen límites teóricos (como el límite de Hamming), pero otra cuestión es qué códigos se pueden construir realmente. ^{[ se necesita aclaración ]} Es como empaquetar esferas en una caja en 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 . Están trazados los límites para diferentes distancias de Hamming desde 1 (desprotegido) hasta 34. Marcados con puntos están los códigos perfectos:

• 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 binario Golay 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 conoce un conjunto de límites inferiores y superiores de códigos de bloque. ${\displaystyle R(C)}$ ${\displaystyle \delta (C)}$

Hamming atado

${\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]}$

Encuadernado singleton

El límite 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 singleton con igualdad. ${\displaystyle k+d\leq n+1}$

Plotkin atado

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

Gilbert-Varshamov obligado

${\displaystyle R\geq 1-H_{q}\left(\delta \right)-\epsilon }$, donde , es la función de entropía q -aria. ${\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

Definir . Sea el número máximo de palabras en clave 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}}$

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

Elías – Bassalygo obligado

${\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 el de un nido de abejas. Pero los códigos de bloque dependen de 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 código binario (que suele serlo), las dimensiones se refieren a la longitud de la palabra clave como se define anteriormente.

La teoría de la codificación utiliza el modelo de esfera N -dimensional. Por ejemplo, ¿cuántas monedas de un centavo se pueden empaquetar en un círculo sobre una mesa o en 3 dimensiones, cuántas canicas se pueden empaquetar en un globo terráqueo? Otras consideraciones entran en juego a la hora de elegir un código. Por ejemplo, el empaquetado hexagonal en la restricción de una caja rectangular dejará espacios vacíos en las esquinas. A medida que las dimensiones aumentan, el porcentaje de espacio vacío disminuye. Pero en determinadas dimensiones, el embalaje utiliza todo el espacio y estos códigos son los llamados códigos perfectos. Hay muy pocos de estos códigos.

Otra propiedad es la cantidad de vecinos que puede tener una sola palabra de código. ^[1] Nuevamente, considere los centavos como ejemplo. Primero empaquetamos las monedas de un centavo en una cuadrícula rectangular. Cada centavo tendrá 4 vecinos cercanos (y 4 en las esquinas que están más alejadas). En un hexágono, cada centavo tendrá 6 vecinos cercanos. Respectivamente, en tres y cuatro dimensiones, el empaquetamiento máximo lo dan las 12 caras y 24 celdas con 12 y 24 vecinos, respectivamente. Cuando aumentamos las dimensiones, el número de vecinos cercanos aumenta muy rápidamente. Por lo general el valor viene dado por los números de los besos .

El resultado es que también crece el número de formas en que el ruido puede hacer que el receptor elija un vecino (y, por 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 causar un error a un solo vecino, pero el número de vecinos puede ser lo suficientemente grande como para que la probabilidad total de error realmente se vea afectada. ^[1]

Ver también

• Capacidad del canal
• Teorema de Shannon-Hartley
• canal ruidoso
• Lista de decodificación ^[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.

• JH van Lint (1992). Introducción a la teoría de la codificación. GTM . vol. 86 (2ª ed.). Springer-Verlag. pag. 31.ISBN​ 3-540-54894-7.
• FJ MacWilliams ; NJA Sloane (1977). La teoría de los códigos correctores de errores . Holanda del Norte. 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