Código cíclico

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; las comprobaciones requieren 2 ediciones .

Un código cíclico es un código de bloque lineal que tiene la propiedad de ciclicidad, es decir, cada permutación cíclica de una palabra de código es también una palabra de código. Se utiliza para transformar información para protegerla de errores (consulte Detección y corrección de errores ).

Introducción

Sea una palabra de longitud n sobre un alfabeto de elementos de un campo finito y sea un polinomio correspondiente a esta palabra en una variable formal . Se puede ver que esta correspondencia es un isomorfismo de espacios lineales. Dado que las "palabras" consisten en letras del campo, se pueden sumar y multiplicar (elemento por elemento), y el resultado estará en el mismo campo. El polinomio correspondiente a la combinación lineal del par de palabras y es igual a la combinación lineal de los polinomios de estas palabras . ${\overline {y}}=(y_{0},y_{1},\dots,y_{n-1})\en L^{n}$ $L=GF(q)$ ${\displaystyle y(x)=y_{0}+y_{1}x+y_{2}x^{2}+\dots +y_{n-1}x^{n-1))$ $X$ ${\overline {y}}=m_{1}{\overline {y_{1}}}+m_{2}{\overline {y_{2}}}$ ${\overline {y_{1}}}=(y_{1,0},\dots,y_{1,n-1})$ ${\overline {y_{2}}}=(y_{2,0},\dots,y_{2,n-1})$ ${y}(x)=\sum _{k=0}^{n-1}(m_{1}y_{1k}+m_{2}y_{2k})x^{k}=m_ {1}{\sobrelínea {y_{1}}}(x)+m_{2}{\sobrelínea {y_{2}}}(x)$

Esto nos permite considerar el conjunto de palabras de longitud n sobre un campo finito como un espacio lineal de polinomios de grado máximo n − 1 sobre el campo . $FG(q)$

Descripción algebraica

Si es una palabra código obtenida por un desplazamiento cíclico de un bit a la izquierda de la palabra , entonces el polinomio correspondiente se obtiene a partir del anterior multiplicando por x : $\overrightarrow {c_{1}}$ $\flecha derecha {c}$ $c_{1}(x)$

c_{1}(x)=xc(x)\mod (x^{n}-1)

, utilizando el hecho de que

x^{n}\equiv 1\mod (x^{n}-1).

Desplazamiento a la derecha e izquierda, respectivamente, por bits: $j$

c_{j}(x)=x^{j}c(x)\mod (x^{n}-1),

c_{-j}(x)x^{j}=c(x)\mod (x^{n}-1).

Si es un polinomio arbitrario sobre el campo y es una palabra de código de un código cíclico , entonces también es una palabra de código de este código. $m(x)$ $FG(q)$ $c(x)$ ${\ estilo de visualización (n, k)}$ $m(x)c(x)\mod (x^{n}-1)$

Polinomio generador

Definición

Un polinomio generador de un código cíclico es un polinomio distinto de cero de , cuyo grado es el más pequeño y el coeficiente en el grado más alto . ${\ estilo de visualización (n, k)}$ $C$ $g(x)=\sum \limits _{i=0}^{r}g_{i}x^{i}$ $C$ ${\ estilo de visualización g_ {r} = 1}$

Teorema 1

Si es un código cíclico y su polinomio generador, entonces el grado es , y cada palabra de código se puede representar de manera única como $C$ ${\ estilo de visualización (n, k)}$ $g(x)$ $g(x)$ $r=nk$

{\ estilo de visualización c (x) = m (x) g (x),}

donde el grado es menor o igual a . $m(x)$ $k-1$

Teorema 2

$g(x)$ — polinomio generador del código cíclico — es un divisor del binomio . ${\ estilo de visualización (n, k)}$ ${\ estilo de visualización x^{n}-1}$

Consecuencias

Por lo tanto, cualquier polinomio divisor puede ser elegido como polinomio generador . El grado del polinomio seleccionado determinará el número de símbolos de verificación , el número de símbolos de información . ${\ estilo de visualización x^{n}-1}$ $r$ $k=nr$

Matriz generadora

Los polinomios son linealmente independientes, de lo contrario para distinto de cero , lo cual es imposible. $g(x),xg(x),x^{2}g(x),\dots,x^{k-1}g(x)$ ${\ estilo de visualización m (x) g (x) = 0}$ $m(x)$

Entonces, las palabras de código se pueden escribir, como para los códigos lineales, de la siguiente manera:

{\overline {m}}G=(m_{0},m_{1},\dots,m_{k-1}){\begin{bmatrix}g(x)\\xg(x)\ \\puntos \\x^{k-1}g(x)\end{bmatriz}}=m(x)g(x),

donde es la matriz generadora , es el polinomio de información. $GRAMO$ $m(x)$

La matriz se puede escribir en forma simbólica: $GRAMO$

G={\begin{bmatrix}g_{0}&g_{1}&\puntos &g_{r-1}&g_{r}&0&\puntos &0\\0&g_{0}&\puntos &g_{r-2 }&g_{r-1}&g_{r}&\dots &0\\\vdots &\vdots &\ddots &\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&\dots &0&g_{0}&g_ {1}&\puntos &g_{r}\end{bmatriz}}.

Matriz de cheques

Para cada palabra clave de un código cíclico, . Por lo tanto, la matriz de verificación se puede escribir como $c(x)=0\mod g(x)$

H={\begin{bmatrix}1&x&x^{2}&\dots &x^{n-2}&x^{n-1}\\\end{bmatrix}}\mod g(x).

Después

{\overline {c}}H^{T}=\sum \limits _{i=0}^{n-1}c_{i}x^{i}=0\mod g(x).

Codificación

Asistemático

Con la codificación no sistemática, la palabra clave se obtiene como el producto de un polinomio de información por uno generador:

{\ estilo de visualización c (x) = m (x) g (x).}

Se puede realizar multiplicando polinomios.

Sistemático

Con la codificación sistemática, la palabra de código se forma en forma de un subbloque de información y una verificación:

c(x)=[s(x)\;m(x)].

Deje que la palabra de información forme las potencias más altas de la palabra de código, luego

c(x)=x^{r}m(x)+s(x),\quad r=nk.

Entonces se sigue de la condición $c(x)=x^{r}m(x)+s(x)=0\mod g(x)$

s(x)=-x^{r}m(x)\mod g(x).

Esta ecuación define la regla de codificación sistemática. Se puede implementar utilizando filtros lineales multiciclo (MLF) .

Ejemplos

Código binario (7,4,3)

Como divisor , elegimos un polinomio generador de tercer grado , luego el código resultante tendrá una longitud , el número de símbolos de verificación (el grado del polinomio generador) , el número de símbolos de información , la distancia mínima . ${\ estilo de visualización x^{7}-1}$ $g(x)=x^{3}+x+1$ ${\ estilo de visualización n = 7}$ $r=3$ $k = 4$ $re=3$

Generando matriz de código:

G={\begin{bmatriz}1&1&0&1&0&0&0\\0&1&1&0&1&0&0\\0&0&1&1&0&1&0\\0&0&0&1&1&0&1\end{bmatriz)),

donde la primera línea es un polinomio con coeficientes en orden ascendente. $g(x)$

Las líneas restantes son desplazamientos cíclicos de la primera línea.

Comprobar matriz :

H={\begin{bmatriz}1&0&0&1&0&1&1\\0&1&0&1&1&1&0\\0&0&1&0&1&1&1\end{bmatriz)),

donde la i -ésima columna, a partir de la 1a, es el resto de la división por el polinomio , escrito en grados ascendentes, a partir de la parte superior. ${\ estilo de visualización x^{i-1}}$ $g(x)$

Entonces, por ejemplo, la cuarta columna es , o en notación vectorial . $h_{4}(x)=x^{3}\mod g(x)=x+1$ $[110]$

Es fácil comprobar eso . ${\ estilo de visualización GH ^ {T} = 0}$

Código binario (15,7,5) BCH

Como polinomio generador , puedes elegir el producto de dos divisores : $g(x)$ ${\ estilo de visualización x^{15}-1}$

g(x)=g_{1}(x)g_{2}(x)=(x^{4}+x+1)(x^{4}+x^{3}+x^{ 2}+x+1)=x^{8}+x^{7}+x^{6}+x^{4}+1.

Entonces cada palabra clave se puede obtener usando el producto del polinomio de información con el grado de la siguiente manera: $m(x)$ $k-1$

{\ estilo de visualización c (x) = m (x) g (x).}

Por ejemplo, una palabra de información corresponde a un polinomio , luego a una palabra de código , o en forma de vector . ${\ estilo de visualización {\ overline {m}} = [1000111]}$ $m(x)=x^{6}+x^{5}+x^{4}+1$ $c(x)=(x^{6}+x^{5}+x^{4}+1)(x^{8}+x^{7}+x^{6}+x^ {4}+1)=x^{14}+x^{12}+x^{9}+x^{7}+x^{5}+1$ ${\overline {c}}=[100001010100101]$

Véase también

Enlaces

Mecanismos de control de integridad de datos.