Código de bloque

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

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 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 los códigos Reed-Solomon, códigos Hamming, códigos Hadamard, códigos Expander, códigos Golay y 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 normalmente se decodifican mediante decodificadores algebraicos.

El término código bloque puede también referirse a cualquier código de error que actúe en un bloque de ${displaystyle k}$ bits de datos de entrada para producir ${displaystyle n}$ bits of output data ${displaystyle (n,k)}$ . En consecuencia, el codificador de bloques es un sin memoria Dispositivo. Bajo esta definición, códigos como turbo, códigos convolutivos terminados y otros códigos iterativamente decodificables (códigos similares a turbo) también se considerarían códigos bloque. Un encoder conversor no definido sería un ejemplo de un código no bloqueado (sin mancha) que ha memoria y es clasificado como código de árbol.

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 a ruido de 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 llamada 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í, ${displaystyle Sigma$ es un conjunto finito y no vacío ${displaystyle k}$ y ${displaystyle n}$ son enteros. El significado y significado 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 para ser codificado se modela como una cadena sobre algunos alfabeto ${displaystyle Sigma$ . El tamaño ${displaystyle Silencio.$ del alfabeto se escribe a menudo como ${displaystyle q}$ . Si ${displaystyle q=2}$ , entonces el código de bloques se llama a binario código de bloqueo. En muchas aplicaciones es útil considerar ${displaystyle q}$ ser un poder primario, e identificar ${displaystyle Sigma$ con el campo finito ${displaystyle mathbb {F} _{q}$ .

La longitud del mensaje k

Los mensajes son elementos ${displaystyle m}$ de ${displaystyle ¡Sigma!$ , es decir, cuerdas de longitud ${displaystyle k}$ . Por lo tanto el número ${displaystyle k}$ se llama longitud del mensaje o dimensión de un código de bloques.

La longitud del bloque n

El longitud del bloque ${displaystyle n}$ de un código de bloque es el número de símbolos en un bloque. Por lo tanto, los elementos ${displaystyle c}$ de ${displaystyle Sigma ^{n}$ son cuerdas de longitud ${displaystyle n}$ y corresponden a bloques que pueden ser recibidos por el receptor. Por lo tanto también son llamados recibidos palabras. Si ${displaystyle c=C(m)}$ para algún mensaje ${displaystyle m}$ Entonces ${displaystyle c}$ se llama la palabra clave ${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 grande 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 ${displaystyle 1-R}$ mide el sobrecabezamiento que ocurre debido a la codificación con el código de bloques. Es un simple hecho teórico de la información que la tasa no puede exceder ${displaystyle 1}$ ya que los datos en general no pueden ser comprimidos sin pérdidas. Formally, esto se deriva del hecho de que el código ${displaystyle C}$ es un mapa inyectable.

La distancia d

El 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 clave distintas, y el relativa distancia ${displaystyle delta }$ es la fracción ${displaystyle d/n}$ . Formally, for received words ${displaystyle c_{1},c_{2} Sigma ^{n}$ , vamos ${displaystyle Delta (c_{1},c_{2}}$ denota la distancia Hamming entre ${displaystyle C_{1}$ y ${displaystyle c_{2}$ , es decir, el número de posiciones en las que ${displaystyle C_{1}$ y ${displaystyle c_{2}$ difieren. Entonces la distancia mínima ${displaystyle d}$ del código ${displaystyle C}$ se define como

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

Puesto que cualquier código tiene que ser inyectable, cualquier dos palabras clave no estará de acuerdo en al menos una posición, por lo que la distancia de cualquier código es al menos ${displaystyle 1}$ . Además, el distancia iguales a los peso mínimo para códigos de bloques lineales porque:

{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 _{min Sigma ^{k} atop mneq mathbf {0}w[C(m)]=w_{min }

Una distancia mayor permite más corrección y detección de errores. Por ejemplo, si sólo consideramos errores que pueden cambiar símbolos de la palabra clave enviada pero nunca borrarlos o añadirlos, entonces el número de errores es el número de posiciones en las que la palabra clave enviada y la palabra recibida difieren. Un código con distancia $d$ permite al receptor detectar hasta ${displaystyle d-1}$ errores de transmisión desde el cambio ${displaystyle d-1}$ las posiciones de una palabra clave nunca pueden producir accidentalmente otra palabra clave. Además, si no hay más que ${displaystyle (d-1)/2}$ errores de transmisión ocurren, el receptor puede decodificar únicamente la palabra recibida a una palabra clave. Esto es porque cada palabra recibida tiene en la mayoría de una palabra clave a distancia ${displaystyle (d-1)/2}$ . Si más que ${displaystyle (d-1)/2}$ errores de transmisión ocurren, el receptor no puede decodificar únicamente la palabra recibida en general, ya que puede haber varias posibles codewords. Una manera para que el receptor pueda hacer frente a esta situación es utilizar la decodificación de listas, en la que el decodificador produce una lista de todas las palabras clave en un determinado radio.

Notación popular

La notación ${displaystyle (n,k,d)_{q}$ describe un código de bloque sobre un alfabeto ${displaystyle Sigma$ de tamaño ${displaystyle q}$ , con una longitud de bloque ${displaystyle n}$ , longitud del mensaje ${displaystyle k}$ , y distancia ${displaystyle d}$ . Si el código de bloques es un código de bloque lineal, entonces los soportes cuadrados en la notación ${displaystyle [n,k,d]$ están acostumbrados a representar ese hecho. Para códigos binarios con ${displaystyle q=2}$ , el índice se cae a veces. Para los códigos separables de distancia máxima, la distancia es siempre ${displaystyle d=n-k+1}$ , pero a veces la distancia precisa no es conocida, no-trivial para probar o declarar, o no es necesaria. En tales casos, ${displaystyle d}$ - El cliente puede estar desaparecido.

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

Ejemplos

Como se mencionó anteriormente, hay un gran número de códigos de corrección de errores que en realidad bloquean los códigos. El primer código de error fue el código Hamming(7,4), desarrollado por Richard W. Hamming en 1950. Este código transforma un mensaje consistente en 4 bits en una palabra clave de 7 bits añadiendo 3 bits de paridad. Por lo tanto este código es un código de bloqueo. Resulta que también es un código lineal y que tiene distancia 3. En la notación de mano corta arriba, esto significa que el código Hamming(7,4) es un ${displaystyle [7,4,3]_{2}$ código.

Reed – Los códigos Salomón son una familia de ${displaystyle [n,k,d]$ códigos con ${displaystyle d=n-k+1}$ y ${displaystyle q}$ ser un poder primario. Los códigos Rank son familia de ${displaystyle [n,k,d]$ códigos con ${displaystyle dleq n-k+1}$ . Códigos de Hadamard son una familia de ${displaystyle [n,k,d]_{2}$ códigos con ${displaystyle n=2^{k-1}$ y ${displaystyle d=2^{k-2}$ .

Propiedades de detección y corrección de errores

Un código ${displaystyle cin Sigma }$ podría considerarse como un punto ${displaystyle n}$ - espacio de separación ${displaystyle Sigma ^{n}$ y el código ${displaystyle {fnMithcal}}$ es el subconjunto de ${displaystyle Sigma ^{n}$ . Un código ${displaystyle {fnMithcal}}$ tiene distancia ${displaystyle d}$ significa que ${displaystyle forall cin {fnMitcal {C}}$ , no hay otra palabra clave en el Hamming bola centrado en ${displaystyle c}$ con radio ${displaystyle d-1}$ , que se define como la colección de ${displaystyle n}$ -dimensión palabras cuya Hamming distance a ${displaystyle c}$ no es más que ${displaystyle d-1}$ . Análogamente, ${displaystyle {fnMithcal}}$ con (mínimo) distancia ${displaystyle d}$ tiene las siguientes propiedades:

${displaystyle {fnMithcal}}$ puede detectar ${displaystyle d-1}$ errores: Porque una palabra clave ${displaystyle c}$ es la única palabra clave en la bola Hamming centrado en sí mismo con radio ${displaystyle d-1}$ , sin patrón de error ${displaystyle d-1}$ o menos errores podrían cambiar una palabra clave a otra. Cuando el receptor detecta que el vector recibido no es una palabra clave ${displaystyle {fnMithcal}}$ , los errores son detectados (pero no hay garantía para corregir).
${displaystyle {fnMithcal}}$ puede corregir ${displaystyle textstyle leftlfloor {{d-1} over 2}rightrfloor }$ errores. Porque una palabra clave ${displaystyle c}$ es la única palabra clave en la bola Hamming centrado en sí mismo con radio ${displaystyle d-1}$ , las dos bolas Hamming centradas en dos palabras clave diferentes respectivamente con ambos radios ${displaystyle textstyle leftlfloor {{d-1} over 2}rightrfloor }$ no se solapan entre sí. Por lo tanto, si consideramos la corrección del error como encontrar la palabra clave más cercana a la palabra recibida ${displaystyle y}$ , siempre y cuando el número de errores no sea más que ${displaystyle textstyle leftlfloor {{d-1} over 2}rightrfloor }$ , sólo hay una palabra clave en la bola de adelgazamiento centrado en ${displaystyle y}$ con radio ${displaystyle textstyle leftlfloor {{d-1} over 2}rightrfloor }$ , por lo tanto todos los errores podrían ser corregidos.
Para decodificar en presencia de más que ${displaystyle (d-1)/2}$ se pueden utilizar errores, decodificación de listas o decodificación de máxima probabilidad.
${displaystyle {fnMithcal}}$ puede corregir ${displaystyle d-1}$ borrado. Por borrado significa que la posición del símbolo borrado es conocida. La corrección podría lograrse ${displaystyle q}$ -pasando la decodificación: In ${displaystyle i^{th}}$ pasar la posición borrada está llena de ${displaystyle i^{th}}$ símbolo y corrección de errores se lleva a cabo. Debe haber un paso que el número de errores no es más que ${displaystyle textstyle leftlfloor {{d-1} over 2}rightrfloor }$ y, por lo tanto, las borraciones podrían ser corregidas.

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

Familia de códigos

${displaystyle C={C_{i} 1}$ se llama familia de códigos, donde ${displaystyle C_{i}$ es un ${displaystyle (n_{i},k_{i},d_{i}_{q}$ código con aumento monotónico ${displaystyle No.$ .

Tasa familia de códigos $C$ se define como ${displaystyle R(C)=lim _{ito infty }{k_{i} {}}$

Distancia relativa familia de códigos $C$ se define como ${displaystyle delta (C)=lim _{ito infty }{d_{i} {}}$

Para explorar la relación entre ${displaystyle R(C)}$ y ${displaystyle delta (C)}$ , se conoce un conjunto de límites inferiores y superiores de códigos bloque.

Hamming atado

{displaystyle Rleq 1-{1over n}cdot log _{q}cdot left[sum ¿Qué? {deltacdot ################################################################################################################################################################################################################################################################ - Sí.

Encuadernación singleton

El límite Singleton es que la suma de la velocidad 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 bloques satisface la desigualdad ${displaystyle k+dleq n+1}$ . Los códigos Reed-Solomon son ejemplos no-triviales de códigos que satisfacen al singleton ligado con la igualdad.

Plotkin obligado

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

Para el caso general, los siguientes límites de Plotkin tienen para cualquier ${displaystyle Csubseteq mathbb {F} _{q} {n}}$ con distancia $d$ :

Si ${displaystyle d=left(1-{1over q}right)n,tenciónC sobrevivirleq 2qn}$
Si ${displaystyle d confianzaleft(1-{1over q}right)n, WordPressC habitleq {qd over {qd-left(q-1right)n}}$

Para cualquier $q$ - código diario con distancia ${displaystyle delta }$ , ${displaystyle Rleq 1-left({q over {q-1}right)delta +oleft(1right)}$

Gilbert-Varshamov atado

${displaystyle Rgeq 1-H_{q}left(delta right)-epsilon }$ , donde ${displaystyle 0leq delta leq 1-{1 over q},0leq epsilon leq 1-H_{q}left(delta right)}$ , ${displaystyle H_{q}left(xright)~{overset {compset {mathrm {def} }{}{=}{q}{q}{q} {q-1}-left(1-xright)cdot log _{q}{q}{left(1-xright)}}}$ es $q$ - función de entropía.

Johnson atado

Define ${displaystyle J_{q}left(delta right)~{overset {compset {mathrm {def} }{}{=}~left(1-{1 over q}right)left(1-{sqrt) {1-{qdelta over {q-1}}right)}$ .
Vamos. ${displaystyle J_{q}left(n,d,eright)}$ ser el número máximo de palabras clave en una bola Hamming de radio $e$ para cualquier código ${displaystyle Csubseteq mathbb {F} _{q} {n}}$ distancia $d$ .

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

Elias–Bassalygo atado

{displaystyle R={log} ¿Por qué? 1-H_{q}left(J_{q}left(delta right)right)+oleft(1right)}

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 nido de una abeja. 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 el número de vecinos que puede tener una sola palabra de código. 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. En general, el valor viene dado por los números de besos.

El resultado es que el número de formas en que el ruido hace que el receptor elija un vecino (de ahí un error) también crece. Esta es una limitación fundamental de códigos de bloque, y de hecho todos los códigos. Puede ser más difícil causar un error un solo vecino, pero el número de vecinos puede ser lo suficientemente grande como para que el la probabilidad total de error realmente se ve afectada.