Código de línea

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de enero de 2021; la verificación requiere 1 edición .

En matemáticas y teoría de la información, un código de línea es un tipo de código de bloque utilizado en circuitos de detección y corrección de errores. Los códigos lineales, en comparación con otros códigos, permiten implementar algoritmos más eficientes para codificar y decodificar información.

Fundamentos

En el proceso de almacenar datos y transmitir información a través de redes de comunicación, inevitablemente ocurren errores. El control de integridad de datos y la corrección de errores son tareas importantes en muchos niveles de trabajo con información (en particular, las capas física , de enlace de datos y de transporte del modelo OSI ).

En los sistemas de comunicación, son posibles varias estrategias para tratar los errores:

detección de errores en bloques de datos y solicitud automática de retransmisión de bloques dañados: este enfoque se utiliza principalmente en las capas de transporte y enlace de datos;
detección de errores en bloques de datos y descarte de bloques defectuosos: este enfoque se usa a veces en sistemas de transmisión de medios donde el retraso de la transmisión es importante y no hay tiempo para la retransmisión;
la corrección de errores ( Corrección de errores de reenvío en inglés ) se aplica en la capa física.

Códigos de detección y corrección de errores

Códigos de corrección: códigos que se utilizan para detectar o corregir errores que ocurren durante la transmisión de información bajo la influencia de interferencias , así como durante su almacenamiento.

Para ello, al escribir (transmitir) a los datos útiles, añaden información redundante especialmente estructurada , y al leer (recibir), se utiliza para detectar o corregir errores. Naturalmente, el número de errores que se pueden corregir es limitado y depende del código específico utilizado.

Estrechamente relacionados con los códigos de corrección de errores están los códigos de detección de errores . A diferencia del primero, el segundo solo puede establecer la presencia de un error en los datos transmitidos, pero no corregirlo.

De hecho, los códigos de detección de errores utilizados pertenecen a las mismas clases de códigos que los códigos de corrección de errores. De hecho, cualquier código de corrección de errores también se puede usar para detectar errores (al hacerlo, podrá detectar más errores de los que pudo corregir).

De acuerdo con el método de trabajo con datos, los códigos de corrección de errores se dividen en códigos de bloque , que dividen la información en fragmentos de longitud constante y procesan cada uno de ellos por separado, y códigos convolucionales , que trabajan con datos como un flujo continuo.

Códigos de bloque

Deje que la información codificada se divida en fragmentos de longitud de bits, que se convierten en palabras de código de longitud de bits . Entonces, el código de bloque correspondiente generalmente se denota . En este caso, el número se denomina tasa de código . $k$ $norte$ $(n,k)$ $R={\frac{k}{n}}$

Si el código deja los bits originales sin cambios y agrega comprobaciones , dicho código se llama sistemático , de lo contrario, no sistemático . $k$ $nk$

Puede configurar el código de bloque de diferentes maneras, incluida una tabla donde cada conjunto de bits de información está asociado con un bit de la palabra de código. Sin embargo, un buen código debe cumplir al menos los siguientes criterios: $k$ $norte$

la capacidad de corregir tantos errores como sea posible,
la menor redundancia posible,
facilidad de codificación y decodificación.

Es fácil ver que estos requisitos se contradicen entre sí. Es por eso que hay una gran cantidad de códigos, cada uno de los cuales es adecuado para su gama de tareas.

Casi todos los códigos utilizados son lineales . Esto se debe al hecho de que los códigos no lineales son mucho más difíciles de estudiar y es difícil que proporcionen una facilidad aceptable de codificación y decodificación.

Espacios lineales

Matriz generadora

Sean los vectores la base del espacio lineal . De acuerdo con la definición de base , cualquier vector puede representarse como una combinación lineal de vectores base: , o en forma matricial , como: $\overrightarrow {x_{1}}=(x_{{11}},..,x_{{1n}}),\overrightarrow {x_{2}}=(x_{{21}},..,x_{ {2n}}),..,\overrightarrow {x_{k}}=(x_{{k1}},..,x_{{kn}})$ $C$ $\overrightarrow {v}\en C$ $\overrightarrow {v}={c_{1}}\overrightarrow {x_{1}}+{c_{2}}\overrightarrow {x_{2}}+...+{c_{k}}\overrightarrow {x_ {k}}$

$\overrightarrow {v}=({c_{1}},{c_{2}},..,{c_{k}}){\begin{bmatrix}x_{{11}}&x_{{12}}& ..&x_{{1n}}\\x_{{21}}&x_{{22}}&..&x_{{2n}}\\..&..&..&..\\x_{{k1 }}&x_{{k2}}&..&x_{{kn}}\\\end{bmatrix}}=\overrightarrow {c}G$ ,

donde se llama matriz generadora del espacio lineal . $G={\begin{bmatrix}x_{{11}}&x_{{12}}&..&x_{{1n}}\\x_{{21}}&x_{{22}}&..&x_{{2n }}\\..&..&..&..\\x_{{k1}}&x_{{k2}}&..&x_{{kn}}\\\end{bmatriz}}$

Esta relación establece una conexión entre los vectores de coeficientes y los vectores . Al enumerar todos los vectores de coeficientes , puede obtener todos los vectores . En otras palabras, la matriz genera un espacio lineal. $\overrightarrow {c}=({c_{1}},{c_{2}},..,{c_{k}})$ $\overrightarrow {v}\en C$ $\overrightarrow {c}=({c_{1}},{c_{2}},..,{c_{k}})$ $\overrightarrow {v}\en C$ $GRAMO$

Matriz de cheques

Otra forma de definir espacios lineales es describirlos en términos de una matriz de verificación.

Sea un subespacio lineal k-dimensional de un espacio n-dimensional sobre un campo finito y sea un complemento ortogonal de . Entonces, según uno de los teoremas del álgebra lineal, la dimensión es . Por lo tanto, hay r vectores base en . Que la base esté en . $\matemáticas {C}$ $\mathbb {F} _{q}$ ${\matemáticas {W}}$ $\matemáticas {C}$ ${\matemáticas {W}}$ $r=nk$ ${\matemáticas {W}}$ $\overrightarrow {h}_{1}=({{h_{1}}_{1}},...,{{h_{1}}_{n}}),\overrightarrow {h}_{2 }=({{h_{2}}_{1}},...,{{h_{2}}_{n}}),...,\overrightarrow {h}_{r}=({ {h_{r}}_{1}},...,{{h_{r}}_{n}})$ ${\matemáticas {W}}$

Entonces cualquier vector satisface el siguiente sistema de ecuaciones lineales : ${\overrightarrow {v}}\en \mathbb {C}$

${\begin{casos}h_{{11}}x_{1}+h_{{12}}x_{2}+...+h_{{1n}}x_{n}=0\\h_{{21 }}x_{1}+h_{{22}}x_{2}+...+h_{{2n}}x_{n}=0\\...\\h_{{r1}}x_{1 }+h_{{r2}}x_{2}+...+h_{{rn}}x_{n}=0\end{casos}}$

O en forma matricial : $\overrightarrow {v}H^{T}=0$

donde está la matriz de control. $H={\begin{bmatrix}\overrightarrow {h}_{1}\\\overrightarrow {h}_{2}\\...\\\overrightarrow {h}_{r}\\\end{bmatrix }}={\begin{bmatrix}h_{{11}}&h_{{12}}&..&h_{{1n}}\\h_{{21}}&h_{{22}}&..&h_{{ 2n}}\\..&..&..&..\\h_{{r1}}&h_{{r2}}&..&h_{{rn}}\\\end{bmatriz}}$

El sistema reducido de ecuaciones lineales debe considerarse como un sistema de controles para todos los vectores del espacio lineal, por lo que la matriz se denomina matriz de control. ${\ matemáticas {H}}$

Formal definición

Un código lineal de longitud n y rango k es un subespacio lineal C de dimensión k del espacio vectorial , donde es un campo finito de q elementos. Tal código con un parámetro q se llama código q-ario (por ejemplo, si q = 5, entonces este es un código 5-ario). Si q = 2 o q = 3, entonces el código es binario o ternario , respectivamente. ${\matemáticas {F}}_{q}^{n}$ $\mathbb {F} _{q}$

Un código lineal (bloque) es un código tal que el conjunto de sus palabras de código forma un subespacio lineal bidimensional (llamémoslo ) en un espacio lineal bidimensional , isomorfo al espacio de vectores de bits . $k$ $C$ $norte$ $k$

Esto significa que la operación de codificación corresponde a la multiplicación del vector de bits original por una matriz no singular , denominada matriz generadora . $k$ $GRAMO$

Sea un subespacio ortogonal con respecto a , y sea una matriz que define la base de este subespacio. Entonces para cualquier vector es cierto: $C^{\perp}$ $C$ $H$ $\overrightarrow {v}\en C$

\overrightarrow {v}H^{T}=\overrightarrow {0}

Propiedades y teoremas importantes

Distancia mínima y poder corrector

La distancia de Hamming ( métrica de Hamming ) entre dos palabras de códigoesel número de bits diferentes en las posiciones correspondientes, es decir, el número de "unidades" en el vector. $\overrightarrow {v_{1}}$ $\overrightarrow {v_{2}}$ $\overrightarrow {v_{1}}\oplus\overrightarrow {v_{2}}$

La distancia mínima del código de línea es el mínimo de todas las distancias Hamming de todos los pares de palabras clave. $d$

El peso de un vector es la distancia de Hamming entre este vector y el vector cero, en otras palabras, el número de componentes distintos de cero del vector. $w$

Teorema 1:

La distancia mínima de un código de línea es igual al mínimo de los pesos de Hamming de las palabras de código distintas de cero: $d$

$d=\min _{{\overrightarrow {c}\in C,\overrightarrow {c}\not =\overrightarrow {0}}}(w(\overrightarrow {c}))$

Prueba:

La distancia entre dos vectores satisface la igualdad , donde es el peso de Hamming del vector . Del hecho de que la diferencia de dos palabras de código cualesquiera de un código lineal es también una palabra de código de un código lineal, se sigue el enunciado del teorema: $d(\flecha derecha {x},\flecha derecha {y})$ $d(\overrightarrow {x},\overrightarrow {y})=w(\overrightarrow {x}-\overrightarrow {y})$ $w(\overrightarrow {t})$ $\overrightarrow {t}$ $d=\min _{{\overrightarrow {c}\in C,\overrightarrow {c}\not =\overrightarrow {0}}}w(\overrightarrow {c})$

La distancia mínima de Hamming es una característica importante de un código de bloque lineal. Define otra característica no menos importante: la capacidad correctiva : $d$

$t=\izquierda\lpiso {\frac {d-1}{2}}\derecha\rpiso$ , aquí los paréntesis angulares denotan redondeo "hacia abajo".

El poder de corrección determina cuál es el número máximo de errores en una palabra de código que se puede garantizar que el código corrija.

Vamos a explicar con un ejemplo. Supongamos que hay dos palabras de código A y B, la distancia de Hamming entre ellas es igual a 3. Si se transmitió la palabra A y el canal introdujo un error en un bit, se puede corregir, ya que incluso en este caso la palabra recibida está más cerca de palabra de código A que B. Pero si el canal introdujo errores de dos bits, el decodificador puede suponer que se transmitió la palabra B.

El número de errores detectados es el número de errores en los que el decodificador puede detectar una situación de error (y, por ejemplo, iniciar la retransmisión del mensaje). este numero es

f=d-1

Teorema 2 (sin demostración):

Si alguna columna de la matriz de verificación H de un código lineal (n, k) es linealmente independiente, entonces la distancia mínima del código es al menos d. Si hay d columnas linealmente dependientes, entonces la distancia mínima del código es exactamente d. $l\leqslant d-1$

Teorema 3 (sin demostración):

Si la distancia mínima de un código lineal (n, k) es d, entonces cualquier columna de la matriz de verificación H es linealmente independiente y hay d columnas linealmente dependientes. $l\leqslant d-1$

Códigos de Hamming

Históricamente, los " códigos de Hamming " deberían llamarse códigos de R. Fisher y se introdujeron en 1942 (Fisher RA The Theory of Confuding in Factor to Thr Theory). Los códigos de Hamming son los códigos lineales más simples con una distancia mínima de 3, es decir, capaces de corregir un error. El código de Hamming se puede representar de tal manera que el síndrome

\overrightarrow {s}=\overrightarrow {r}H^{T}

, donde es el vector aceptado,

\overrightarrow{r}

será igual al número de posición en el que ocurrió el error. Esta propiedad hace que la decodificación sea muy fácil.

Código Reed-Muller

El código Reed-Muller es un código de bloque binario lineal. Con cierto método de construcción, puede ser sistemático. En general, el código Reed-Muller no es cíclico. Los códigos Reed-Muller vienen dados por los siguientes parámetros: para cualquier valor dey, llamado orden del código, menor que: $metro$ $r$ $metro$

longitud de la palabra clave

{\ estilo de visualización n = 2 ^ {m};}

longitud de la parte de información

k=1+C_{m}^{1}+\puntos +C_{m}^{r};

longitud de la pieza de prueba

nk=1+C_{m}^{1}+\dots +C_{m}^{mr-1};

distancia mínima de código

d_{min}=2^{señor}.

El código Reed-Muller se determina utilizando una matriz generadora que consta de vectores base, que se construye de acuerdo con la regla:

sea un vector, todos los componentes del cual son iguales a 1;

V_{0}

sean las filas de una matriz cuyas columnas son todos conjuntos binarios de longitud

{\displaystyle V_{1},\ V_{2},\puntos V_{m))

metro.

El código Reed-Muller de orden th contiene vectores y todos los productos componentes o un número menor de estos vectores como base. $r$ ${\displaystyle V_{0},\ V_{1},\puntos V_{m))$ $r$

Método general para codificar códigos de línea

Un código lineal de longitud n con k símbolos de información es un subespacio lineal k-dimensional, por lo que cada palabra clave es una combinación lineal de los vectores base del subespacio : $\overrightarrow {g_{1}}=(g_{{11}},..,g_{{1n}}),\overrightarrow {g_{2}}=(g_{{21}},..,g_{ {2n}}),..,\overrightarrow {g_{k}}=(g_{{k1}},..,g_{{kn}})$

$\overrightarrow {c}={m_{1}}\overrightarrow {g_{1}}+{m_{2}}\overrightarrow {g_{2}}+...+{m_{k}}\overrightarrow {g_ {k}}$ .

O usando la matriz generadora:

$\overrightarrow {c}=\overrightarrow {m}G=({m_{1}},{m_{2}},..,{m_{k}}){\begin{bmatrix}g_{{11}} &g_{{12}}&..&g_{{1n}}\\g_{{21}}&g_{{22}}&..&g_{{2n}}\\..&..&..&. .\\g_{{k1}}&g_{{k2}}&..&g_{{kn}}\\\end{bmatriz}}$ , dónde $\overrightarrow {m}=({m_{1}},..,{m_{k}}),{m_{1}},..,{m_{k}}\in {\mathbb {Q}}$

Esta relación es la regla de codificación según la cual la palabra de información se asigna al código. $\overrightarrow {m}=({m_{1}},..,{m_{k}})$ $\overrightarrow {c}=({c_{1}},..,{c_{n}})$

Método general para detectar errores en código lineal

Cualquier código (incluido el no lineal) se puede decodificar utilizando una tabla regular, donde cada valor de la palabra recibida corresponde a la palabra transmitida más probable . Sin embargo, este método requiere el uso de tablas enormes ya para palabras de código de longitud relativamente pequeña. $\overrightarrow {r_{i}}$ $\overrightarrow {u_{i}}$

Para códigos lineales, este método se puede simplificar significativamente. En este caso, para cada vector recibido , se calcula el síndrome . Dado que , donde es la palabra clave y es el vector de error, entonces . Luego, utilizando la tabla de síndromes, se determina un vector de error, con la ayuda de la cual se determina la palabra de código transmitida. En este caso, la mesa es mucho más pequeña que cuando se usa el método anterior. $\overrightarrow {r_{i}}$ $\overrightarrow {s_{i}}=\overrightarrow {r_{i}}H^{T}$ $\overrightarrow {r_{i}}=\overrightarrow {v_{i}}+\overrightarrow {e_{i}}$ $\overrightarrow {v_{i}}$ $\overrightarrow {e_{i}}$ $\overrightarrow {s_{i}}=\overrightarrow {e_{i}}H^{T}$

Códigos cíclicos lineales

A pesar de que la corrección de errores en los códigos lineales ya es mucho más fácil que la corrección en la mayoría de los códigos no lineales, para la mayoría de los códigos este proceso sigue siendo bastante complicado. Los códigos cíclicos , además de una decodificación más sencilla, tienen otras propiedades importantes.

Un código cíclico es un código lineal con la siguiente propiedad: si es una palabra de código, entonces su permutación cíclica también es una palabra de código. $\overrightarrow{v}$

Las palabras de un código cíclico se representan convenientemente como polinomios. Por ejemplo, una palabra clave se representa como un polinomio . En este caso, el desplazamiento cíclico de la palabra clave es equivalente a multiplicar el polinomio por el módulo . $\overrightarrow {v}=(v_{0},v_{1},...,v_{{n-1}})$ $v(x)=v_{0}+v_{1}x+...+v_{{n-1}}x^{{n-1}}$ $X$ $x^n-1$

En adelante, salvo que se indique lo contrario, supondremos que el código cíclico es binario , es decir, ... puede tomar los valores 0 o 1 . $v_{0},v_{1}$

Polinomio generador

Se puede demostrar que todas las palabras de código de un código cíclico particular son múltiplos de cierto polinomio generador . El polinomio generador es un divisor . $g(x)$ $x^n-1$

Con la ayuda de un polinomio generador, la codificación se realiza mediante un código cíclico. En particular:

la codificación no sistemática se realiza multiplicando el vector codificado por : ; $g(x)$ $v(x)=u(x)g(x)$

la codificación sistemática se lleva a cabo “añadiendo” a la palabra codificada el resto de la división por , es decir, . $x^{{nk}}u(x)$ $g(x)$ $v(x)=x^{{nk}}u(x)+[x^{{nk}}u(x)\mod g(x)]$

Códigos CRC

Los códigos CRC (comprobación de redundancia cíclica - verificación redundante cíclica) son códigos sistemáticos diseñados no para corregir errores, sino para detectarlos. Utilizan el método de codificación sistemática descrito anteriormente: la "suma de control" se calcula dividiendo por . Dado que no se requiere corrección de errores, la validación de la transmisión se puede realizar de la misma manera. $x^{{nk}}u(x)$ $g(x)$

Así, la forma del polinomio g(x) especifica un código CRC específico. Ejemplos de los polinomios más populares:

nombre clave	la licenciatura	polinomio
CRC-12	12	$x^{12}+x^{11}+x^{3}+x^{2}+x+1$
CRC-16	dieciséis	$x^{16}+x^{15}+x^{2}+1$
CRC- CCITT	dieciséis	$x^{16}+x^{12}+x^{5}+1$
CRC-32	32	$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^ {8}+x^{7}+x^{5}+x^{4}+x^{2}+x+1$

Códigos BCH

Los códigos Bose-Chowdhury-Hockwingham (BCH) son una subclase de códigos cíclicos binarios. Su característica distintiva es la capacidad de construir un código BCH con una distancia mínima no inferior a la dada. Esto es importante porque, en términos generales, determinar la distancia mínima del código es una tarea muy difícil.

Matemáticamente, la construcción de códigos BCH y su decodificación utilizan la descomposición del polinomio generador en factores en el campo de Galois . $g(x)$

Códigos Reed-Solomon

Los códigos Reed-Solomon (códigos RS) son en realidad códigos BCH no binarios , es decir, los elementos del vector de código no son bits, sino grupos de bits. Los códigos Reed-Solomon son muy comunes y funcionan con bytes ( octetos ).

Ventajas y desventajas de los códigos de línea

+ Debido a la linealidad, para memorizar o enumerar todas las palabras del código, basta almacenar en la memoria del codificador o decodificador una parte significativamente menor de ellas, es decir, solo aquellas palabras que forman la base del espacio lineal correspondiente. Esto simplifica enormemente la implementación de dispositivos de codificación y decodificación y hace que los códigos lineales sean muy atractivos desde el punto de vista de las aplicaciones prácticas.

— Aunque los códigos lineales, por regla general, se adaptan bien a ráfagas de errores raras pero grandes , su eficiencia con errores frecuentes pero pequeños (por ejemplo, en un canal con AWGN ) es menos alta.

Evaluación del desempeño

La eficiencia de los códigos está determinada por la cantidad de errores que puede corregir, la cantidad de información redundante que debe agregarse y la complejidad de la implementación de la codificación y decodificación (tanto hardware como software ).

Códigos atados y perfectos de Hamming

Que exista un código de bloque binario con capacidad correctiva . Entonces se cumple la siguiente desigualdad (llamada cota de Hamming ): $(n,k)$ $t$

\sum _{i=0}^{t}{C_{n}^{i}}\leq 2^{nk}

Los códigos que satisfacen este límite de igualdad se dice que son perfectos . Los códigos perfectos incluyen, por ejemplo, los códigos de Hamming. Los códigos con gran poder correctivo que se usan a menudo en la práctica (como los códigos Reed-Solomon) no son perfectos.

Ganancia de energía

Cuando se transmite información a través de un canal de comunicación, la probabilidad de error depende de la relación señal/ruido en la entrada del demodulador, por lo que a un nivel de ruido constante, la potencia del transmisor tiene una importancia decisiva. En los sistemas satelitales y móviles, así como en otros tipos de comunicaciones, la cuestión del ahorro de energía es aguda. Además, en ciertos sistemas de comunicación (por ejemplo, el teléfono), las restricciones técnicas no permiten un aumento ilimitado de la potencia de la señal.

Dado que la codificación de corrección de errores permite la corrección de errores, su aplicación puede reducir la potencia del transmisor, dejando sin cambios la tasa de información. La ganancia de energía se define como la diferencia entre las relaciones s/n en presencia y ausencia de codificación.

Aplicación

Se aplican códigos de línea:

en sistemas de comunicación digital , incluyendo: satélite, radioenlace, celular, transmisión de datos por canales telefónicos;
en sistemas de almacenamiento de información, incluidos magnéticos y ópticos;
en protocolos de red de varios niveles .

Literatura

Diccionario Explicativo de Sistemas de Computación. ed. V. Illingworth y otros: Per. De inglés. - M.: Mashinostroenie , 1990. 560 p.: il.