código cíclico

Tipo de código de bloque

En teoría de la codificación , un código cíclico es un código de bloque , donde los desplazamientos circulares de cada palabra de código dan otra palabra que pertenece al código. Son códigos de corrección de errores que tienen propiedades algebraicas que resultan convenientes para una detección y corrección de errores eficiente .

Si 00010111 es una palabra de código válida, al aplicar un desplazamiento circular hacia la derecha se obtiene la cadena 10001011. Si el código es cíclico, entonces 10001011 vuelve a ser una palabra de código válida. En general, aplicar un desplazamiento circular hacia la derecha mueve el bit menos significativo (LSB) a la posición más a la izquierda, de modo que se convierte en el bit más significativo (MSB); las demás posiciones se desplazan 1 hacia la derecha.

Definición

Sea un código lineal sobre un campo finito (también llamado campo de Galois ) de longitud de bloque . Se llama código cíclico si, para cada palabra de código de , la palabra obtenida mediante un desplazamiento cíclico a la derecha de los componentes es nuevamente una palabra de código. Debido a que un desplazamiento cíclico a la derecha es igual a desplazamientos cíclicos a la izquierda, también se puede definir un código cíclico mediante desplazamientos cíclicos a la izquierda. Por lo tanto, el código lineal es cíclico precisamente cuando es invariante ante todos los cambios cíclicos. ${\displaystyle {\mathcal {C}}}$ ${\displaystyle GF(q)}$ ${\displaystyle n}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle c=(c_{1},\ldots ,c_{n})}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle (c_{n},c_{1},\ldots ,c_{n-1})}$ ${\displaystyle GF(q)^{n}}$ ${\displaystyle n-1}$ ${\displaystyle {\mathcal {C}}}$

Los códigos cíclicos tienen alguna restricción estructural adicional sobre los códigos. Se basan en campos de Galois y por sus propiedades estructurales son muy útiles para controles de errores. Su estructura está fuertemente relacionada con los campos de Galois, por lo que los algoritmos de codificación y decodificación de códigos cíclicos son computacionalmente eficientes.

estructura algebraica

Los códigos cíclicos se pueden vincular a ideales en ciertos anillos. Sea un anillo polinomial sobre el campo finito . Identifique los elementos del código cíclico con polinomios de manera que se correspondan con el polinomio : por lo tanto, la multiplicación por corresponde a un desplazamiento cíclico. Entonces es un anillo ideal en y, por tanto , principal , ya que es un anillo ideal principal . El ideal es generado por el único elemento mónico de grado mínimo, el polinomio generador . ^[1] Debe ser un divisor de . De ello se deduce que todo código cíclico es un código polinómico . Si el polinomio generador tiene grado , entonces el rango del código es . ${\displaystyle R=A[x]/(x^{n}-1)}$ ${\displaystyle A=GF(q)}$ ${\displaystyle C}$ ${\displaystyle R}$ ${\displaystyle (c_{0},\ldots ,c_{n-1})}$ ${\displaystyle c_{0}+c_{1}x+\cdots +c_{n-1}x^{n-1}}$ ${\displaystyle x}$ ${\displaystyle C}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle C}$ ${\displaystyle g}$ ${\displaystyle x^{n}-1}$ ${\displaystyle g}$ ${\displaystyle d}$ ${\displaystyle C}$ ${\displaystyle n-d}$

El idempotente de es una palabra clave tal que (es decir, es un elemento idempotente de ) y es una identidad para el código, es decir, para cada palabra clave . Si y son coprimos, dicha palabra siempre existe y es única; ^[2] es un generador del código. ${\displaystyle C}$ ${\displaystyle e}$ ${\displaystyle e^{2}=e}$ ${\displaystyle e}$ ${\displaystyle C}$ ${\displaystyle e}$ ${\displaystyle e\cdot c=c}$ ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle q}$

Un código irreducible es un código cíclico en el que el código, como ideal, es irreducible, es decir, es mínimo en , de modo que su polinomio de control es un polinomio irreducible . ${\displaystyle R}$

Ejemplos

Por ejemplo, si y , el conjunto de palabras de código contenidas en el código cíclico generado por es precisamente ${\displaystyle A=\mathbb {F} _{2}}$ ${\displaystyle n=3}$ ${\displaystyle (1,1,0)}$

${\displaystyle ((0,0,0),(1,1,0),(0,1,1),(1,0,1))}$.

Corresponde al ideal generado por . ${\displaystyle \mathbb {F} _{2}[x]/(x^{3}-1)}$ ${\displaystyle (1+x)}$

El polinomio es irreducible en el anillo de polinomio y, por tanto, el código es un código irreducible. ${\displaystyle (1+x)}$

El idempotente de este código es el polinomio , correspondiente a la palabra clave . ${\displaystyle x+x^{2}}$ ${\displaystyle (0,1,1)}$

Ejemplos triviales

Ejemplos triviales de códigos cíclicos son el propio código y el código que contiene sólo la palabra de código cero. Estos corresponden a generadores y respectivamente: estos dos polinomios siempre deben ser factores de . ${\displaystyle A^{n}}$ ${\displaystyle 1}$ ${\displaystyle x^{n}-1}$ ${\displaystyle x^{n}-1}$

El código de bits de paridad , que consta de todas las palabras de peso uniforme, corresponde al generador . Nuevamente, esto siempre debe ser un factor de . ${\displaystyle GF(2)}$ ${\displaystyle x+1}$ ${\displaystyle GF(2)}$ ${\displaystyle x^{n}-1}$

Códigos cuasicíclicos y códigos abreviados

Antes de profundizar en los detalles de los códigos cíclicos, primero analizaremos los códigos cuasicíclicos y abreviados que están estrechamente relacionados con los códigos cíclicos y todos se pueden convertir entre sí.

Definición

Códigos cuasicíclicos: ^{[ cita necesaria ]}

Un código cuasicíclico es un código de bloque lineal tal que, para algunos que son coprimos , el polinomio es un polinomio de palabra en código siempre que sea un polinomio de palabra en código. ${\displaystyle (n,k)}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle x^{b}c(x){\pmod {x^{n}-1}}}$ ${\displaystyle c(x)}$

Aquí, el polinomio de palabra clave es un elemento de un código lineal cuyas palabras clave son polinomios que son divisibles por un polinomio de longitud más corta llamado polinomio generador . Cada polinomio de palabra en clave se puede expresar en la forma , donde está el polinomio generador. Cualquier palabra de código de un código cíclico puede asociarse con un polinomio de palabra de código, es decir, . Un código cuasicíclico igual a es un código cíclico. ${\displaystyle c(x)=a(x)g(x)}$ ${\displaystyle g(x)}$ ${\displaystyle (c_{0},..,c_{n-1})}$ ${\displaystyle C}$ ${\displaystyle \sum _{i=0}^{n-1}c_{i}*x^{i}}$ ${\displaystyle b}$ ${\displaystyle 1}$

Definición

Códigos abreviados:

Un código lineal se denomina código cíclico abreviado propiamente dicho si se puede obtener eliminando posiciones de un código cíclico. ${\displaystyle (n,k)}$ ${\displaystyle b}$ ${\displaystyle (n+b,k+b)}$

En códigos abreviados, los símbolos de información se eliminan para obtener una longitud de bloque deseada más pequeña que la longitud de bloque de diseño. Por lo general, se imagina que los símbolos de información que faltan están al comienzo de la palabra clave y se consideran 0. Por lo tanto, − es fijo y luego disminuye, lo que finalmente disminuye . No es necesario eliminar los símbolos iniciales. Dependiendo de la aplicación, a veces las posiciones consecutivas se consideran 0 y se eliminan. ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle n}$

No es necesario transmitir todos los símbolos que se eliminan y en el extremo receptor se pueden reinsertar. Para convertir código cíclico en código acortado, establezca los símbolos en cero y elimínelos de cada palabra de código. Cualquier código cíclico se puede convertir en códigos cuasicíclicos eliminando cada símbolo donde es un factor de . Si los símbolos eliminados no son símbolos de verificación, entonces este código cíclico también es un código abreviado. ${\displaystyle (n,k)}$ ${\displaystyle (n-b,k-b)}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle n}$

Para corregir errores

Los códigos cíclicos se pueden utilizar para corregir errores , como los códigos Hamming, ya que los códigos cíclicos se pueden utilizar para corregir un solo error. Asimismo, también se utilizan para corregir errores dobles y errores de ráfaga. Todos los tipos de correcciones de errores se tratan brevemente en las siguientes subsecciones.

El código Hamming (7,4) tiene un polinomio generador . Este polinomio tiene un cero en el campo de extensión de Galois en el elemento primitivo y todas las palabras en código lo satisfacen . Los códigos cíclicos también se pueden utilizar para corregir errores dobles en el campo . La longitud del bloque será igual a los elementos primitivos y como ceros porque aquí estamos considerando el caso de dos errores, por lo que cada uno representará un error. ${\displaystyle g(x)=x^{3}+x+1}$ ${\displaystyle GF(8)}$ ${\displaystyle \alpha }$ ${\displaystyle {\mathcal {C}}(\alpha )=0}$ ${\displaystyle GF(2)}$ ${\displaystyle n}$ ${\displaystyle 2^{m}-1}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha ^{3}}$ ${\displaystyle GF(2^{m})}$

La palabra recibida es un polinomio de grado dado como ${\displaystyle n-1}$ ${\displaystyle v(x)=a(x)g(x)+e(x)}$

donde puede tener como máximo dos coeficientes distintos de cero correspondientes a 2 errores. ${\displaystyle e(x)}$

Definimos el polinomio síndrome , como el resto del polinomio cuando se divide por el polinomio generador , es decir ${\displaystyle S(x)}$ ${\displaystyle v(x)}$ ${\displaystyle g(x)}$

${\displaystyle S(x)\equiv v(x)\equiv (a(x)g(x)+e(x))\equiv e(x)\mod g(x)}$como . ${\displaystyle (a(x)g(x))\equiv 0\mod g(x)}$

Por corregir dos errores

Sean los elementos del campo y los dos números de ubicación del error. Si solo ocurre un error, entonces es igual a cero y si no ocurre ninguno, ambos son cero. ${\displaystyle X_{1}}$ ${\displaystyle X_{2}}$ ${\displaystyle X_{2}}$

Deja y . ${\displaystyle S_{1}={v}(\alpha )}$ ${\displaystyle S_{3}={v}(\alpha ^{3})}$

Estos elementos de campo se denominan "síndromes". Ahora bien, como es cero en los elementos primitivos y , podemos escribir y . Si ocurren dos errores, entonces ${\displaystyle g(x)}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha ^{3}}$ ${\displaystyle S_{1}=e(\alpha )}$ ${\displaystyle S_{3}=e(\alpha ^{3})}$

${\displaystyle S_{1}=\alpha ^{i}+\alpha ^{i'}}$y . ${\displaystyle S_{3}=\alpha ^{3i}+\alpha ^{3i'}}$

Y estas dos pueden considerarse como dos pares de ecuaciones con dos incógnitas y por lo tanto podemos escribir ${\displaystyle GF(2^{m})}$

${\displaystyle S_{1}=X_{1}+X_{2}}$y . ${\displaystyle S_{3}=(X_{1})^{3}+(X_{2})^{3}}$

Por lo tanto, si los dos pares de ecuaciones no lineales se pueden resolver, se pueden usar códigos cíclicos para corregir dos errores.

código hammam

El código Hamming(7,4) se puede escribir como un código cíclico sobre GF(2) con generador . De hecho, cualquier código Hamming binario de la forma Ham(r, 2) es equivalente a un código cíclico, ^[3] y cualquier código Hamming de la forma Ham(r,q) con r y q-1 relativamente primos también es equivalente. a un código cíclico. ^[4] Dado un código Hamming de la forma Ham(r,2) con , el conjunto de palabras en código pares forma un código cíclico. ^[5] ${\displaystyle 1+x+x^{3}}$ ${\displaystyle r\geq 3}$ ${\displaystyle [2^{r}-1,2^{r}-r-2,4]}$

Código Hamming para corregir errores únicos

Un código cuya distancia mínima es al menos 3, tiene una matriz de verificación cuyas columnas son distintas y distintas de cero. Si una matriz de verificación para un código binario tiene filas, entonces cada columna es un número binario de bits. Hay posibles columnas. Por lo tanto, si una matriz de verificación de un código binario con al menos 3 tiene filas, entonces solo puede tener columnas, no más que eso. Esto define un código, llamado código Hamming. ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle 2^{m}-1}$ ${\displaystyle d_{min}}$ ${\displaystyle m}$ ${\displaystyle 2^{m}-1}$ ${\displaystyle (2^{m}-1,2^{m}-1-m)}$

Es fácil definir códigos Hamming para alfabetos de gran tamaño . Necesitamos definir una matriz con columnas linealmente independientes. Para cualquier palabra de tamaño habrá columnas que son múltiplos entre sí. Por lo tanto, para obtener independencia lineal, todas las tuplas distintas de cero con uno como elemento superior distinto de cero se elegirán como columnas. Entonces dos columnas nunca serán linealmente dependientes porque tres columnas podrían ser linealmente dependientes con la distancia mínima del código como 3. ${\displaystyle q}$ ${\displaystyle H}$ ${\displaystyle q}$ ${\displaystyle m}$

Entonces, hay columnas distintas de cero con uno como elemento superior distinto de cero. Por tanto, un código Hamming es un código. ${\displaystyle (q^{m}-1)/(q-1)}$ ${\displaystyle [(q^{m}-1)/(q-1),(q^{m}-1)/(q-1)-m]}$

Ahora, para códigos cíclicos, sea el elemento primitivo en y sea . Entonces y por lo tanto es un cero del polinomio y es un polinomio generador para el código cíclico de longitud de bloque . ${\displaystyle \alpha }$ ${\displaystyle GF(q^{m})}$ ${\displaystyle \beta =\alpha ^{q-1}}$ ${\displaystyle \beta ^{(q^{m}-1)/(q-1)}=1}$ ${\displaystyle \beta }$ ${\displaystyle x^{(q^{m}-1)/(q-1)}-1}$ ${\displaystyle n=(q^{m}-1)/(q-1)}$

Pero para , . Y la palabra recibida es un polinomio de grado dado como ${\displaystyle q=2}$ ${\displaystyle \alpha =\beta }$ ${\displaystyle n-1}$

${\displaystyle v(x)=a(x)g(x)+e(x)}$

dónde, o dónde representa las ubicaciones de error. ${\displaystyle e(x)=0}$ ${\displaystyle x^{i}}$ ${\displaystyle i}$

Pero también podemos usarlo como elemento para indexar la ubicación del error. Porque tenemos y todos los poderes de from to son distintos. Por lo tanto, podemos determinar fácilmente la ubicación del error a menos que no represente ningún error. Entonces, un código Hamming es un código de corrección de errores único con y . ${\displaystyle \alpha ^{i}}$ ${\displaystyle GF(2^{m})}$ ${\displaystyle g(\alpha )=0}$ ${\displaystyle v(\alpha )=\alpha ^{i}}$ ${\displaystyle \alpha }$ ${\displaystyle 0}$ ${\displaystyle 2^{m}-2}$ ${\displaystyle i}$ ${\displaystyle \alpha ^{i}}$ ${\displaystyle v(\alpha )=0}$ ${\displaystyle GF(2)}$ ${\displaystyle n=2^{m}-1}$ ${\displaystyle k=n-m}$

Para corregir errores de ráfaga

Desde el concepto de distancia de Hamming , un código con una distancia mínima puede corregir cualquier error. Pero en muchos canales el patrón de error no es muy arbitrario, ocurre dentro de un segmento muy corto del mensaje. Este tipo de errores se denominan errores de ráfaga . Entonces, para corregir tales errores obtendremos un código más eficiente y de mayor tasa debido a las menores restricciones. Los códigos cíclicos se utilizan para corregir errores de ráfaga. De hecho, los códigos cíclicos también pueden corregir errores de ráfaga cíclicos junto con errores de ráfaga. Los errores de ráfaga cíclica se definen como ${\displaystyle 2t+1}$ ${\displaystyle t}$

Una ráfaga cíclica de longitud es un vector cuyos componentes distintos de cero se encuentran entre componentes (cíclicamente) consecutivos, el primero y el último de los cuales son distintos de cero. ${\displaystyle t}$ ${\displaystyle t}$

En forma polinómica, la explosión cíclica de longitud se puede describir como un polinomio de grado con un coeficiente distinto de cero . Aquí se define el patrón y se define el punto de partida del error. La longitud del patrón está dada por grados . El polinomio del síndrome es único para cada patrón y está dado por ${\displaystyle t}$ ${\displaystyle e(x)=x^{i}b(x)\mod (x^{n}-1)}$ ${\displaystyle b(x)}$ ${\displaystyle t-1}$ ${\displaystyle b_{0}}$ ${\displaystyle b(x)}$ ${\displaystyle x^{i}}$ ${\displaystyle b(x)+1}$

${\displaystyle s(x)=e(x)\mod g(x)}$

Un código de bloque lineal que corrija todos los errores de ráfaga de longitud o menos debe tener al menos símbolos de verificación. Prueba: porque cualquier código lineal que pueda corregir un patrón de ráfaga de longitud o menos no puede tener una ráfaga de longitud o menos como palabra clave porque si lo hiciera, una ráfaga de longitud podría cambiar la palabra clave a un patrón de ráfaga de longitud , que también podría obtenerse. cometiendo un error de ráfaga de longitud en todas las palabras de código cero. Ahora, dos vectores cualesquiera que sean distintos de cero en los primeros componentes deben ser de diferentes coconjuntos de una matriz para evitar que su diferencia sea una palabra clave de ráfagas de longitud . Por lo tanto, el número de tales coconjuntos es igual al número de vectores que son . Por lo tanto, al menos co-conjuntos y, por lo tanto, al menos el símbolo de verificación. ${\displaystyle t}$ ${\displaystyle 2t}$ ${\displaystyle t}$ ${\displaystyle 2t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle t}$ ${\displaystyle 2t}$ ${\displaystyle 2t}$ ${\displaystyle q^{2t}}$ ${\displaystyle q^{2t}}$ ${\displaystyle 2t}$

Esta propiedad también se conoce como límite de Rieger y es similar al límite Singleton para la corrección de errores aleatorios.

Códigos de fuego como límites cíclicos

En 1959, Philip Fire ^[6] presentó una construcción de códigos cíclicos generados por el producto de un binomio y un polinomio primitivo. El binomio tiene la forma de algún número entero impar positivo . ^[7] El código de incendio es un código de corrección de errores de ráfaga cíclica con el polinomio generador ${\displaystyle x^{c}+1}$ ${\displaystyle c}$ ${\displaystyle GF(q)}$

${\displaystyle g(x)=(x^{2t-1}-1)p(x)}$

donde es un polinomio primo con grado no menor que y no divide . La longitud del bloque del código de incendio es el número entero más pequeño que divide . ${\displaystyle p(x)}$ ${\displaystyle m}$ ${\displaystyle t}$ ${\displaystyle p(x)}$ ${\displaystyle x^{2t-1}-1}$ ${\displaystyle n}$ ${\displaystyle g(x)}$ ${\displaystyle x^{n}-1}$

Un código de incendio puede corregir todos los errores de ráfaga de longitud t o menos si no aparecen dos ráfagas en el mismo conjunto conjunto. Esto se puede demostrar por contradicción. Supongamos que hay dos ráfagas distintas de cero y de longitud o menos y que están en el mismo conjunto conjunto del código. Entonces, su diferencia es una palabra clave. Como la diferencia es múltiplo de, también lo es . Por lo tanto, ${\displaystyle b(x)}$ ${\displaystyle x^{j}b'(x)}$ ${\displaystyle b(x)}$ ${\displaystyle x^{j}b'(x)}$ ${\displaystyle t}$ ${\displaystyle g(x)}$ ${\displaystyle x^{2t-1}-1}$

${\displaystyle b(x)=x^{j}b'(x)\mod (x^{2t-1}-1)}$.

Esto muestra que es un múltiplo de , entonces ${\displaystyle j}$ ${\displaystyle 2t-1}$

${\displaystyle b(x)=x^{l(2t-1)}b'(x)}$

para algunos . Ahora bien, como es menor que y es menor que es una palabra clave. Por lo tanto, ${\displaystyle l}$ ${\displaystyle l(2t-1)}$ ${\displaystyle t}$ ${\displaystyle l}$ ${\displaystyle q^{m}-1}$ ${\displaystyle (x^{l(2t-1)}-1)b(x)}$

${\displaystyle (x^{l(2t-1)}-1)b(x)=a(x)(x^{2t-1}-1)p(x)}$.

Como el grado es menor que el grado de , no se puede dividir . Si no es cero, entonces tampoco se puede dividir porque es menor que y, por definición , no se divide por menor que . Por lo tanto y es igual a cero. Eso significa que ambas ráfagas son iguales, contrariamente a lo que se supone. ${\displaystyle b(x)}$ ${\displaystyle p(x)}$ ${\displaystyle p(x)}$ ${\displaystyle b(x)}$ ${\displaystyle l}$ ${\displaystyle p(x)}$ ${\displaystyle x^{l(2t-1)}-1}$ ${\displaystyle l}$ ${\displaystyle q^{m}-1}$ ${\displaystyle m}$ ${\displaystyle p(x)}$ ${\displaystyle x^{l(2t-1)}-1}$ ${\displaystyle l}$ ${\displaystyle q^{m}-1}$ ${\displaystyle l}$ ${\displaystyle j}$

Los códigos de incendio son los mejores códigos de corrección de ráfaga única con alta tasa y están construidos analíticamente. Son de tasa muy alta y cuando y son iguales, la redundancia es mínima y es igual a . Al utilizar varios códigos de incendio también se pueden corregir errores de ráfaga más largos. ${\displaystyle m}$ ${\displaystyle t}$ ${\displaystyle 3t-1}$

Para la detección de errores se utilizan ampliamente códigos cíclicos y se denominan códigos de redundancia cíclica . ${\displaystyle t-1}$

En la transformada de Fourier

Las aplicaciones de la transformada de Fourier están muy extendidas en el procesamiento de señales. Pero sus aplicaciones no se limitan únicamente a campos complejos; Las transformadas de Fourier también existen en el campo de Galois . Los códigos cíclicos que utilizan la transformada de Fourier se pueden describir en un entorno más cercano al procesamiento de señales. ${\displaystyle GF(q)}$

Transformada de Fourier sobre campos finitos

Transformada de Fourier sobre campos finitos

La transformada discreta de Fourier del vector viene dada por un vector donde, ${\displaystyle v=v_{0},v_{1},....,v_{n-1}}$ ${\displaystyle V=V_{0},V_{1},.....,V_{n-1}}$

${\displaystyle V_{k}}$= donde, ${\displaystyle \Sigma _{i=0}^{n-1}e^{-j2\pi n^{-1}ik}v_{i}}$

${\displaystyle k=0,.....,n-1}$

donde exp( ) es una raíz enésima de la unidad. De manera similar, en el campo finito, la raíz de la unidad es un elemento de orden . Por lo tanto ${\displaystyle -j2\pi /n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle \omega }$ ${\displaystyle n}$

Si es un vector terminado y es un elemento de orden , entonces la transformada de Fourier del vector es el vector y los componentes están dados por ${\displaystyle v=(v_{0},v_{1},....,v_{n-1})}$ ${\displaystyle GF(q)}$ ${\displaystyle \omega }$ ${\displaystyle GF(q)}$ ${\displaystyle n}$ ${\displaystyle v}$ ${\displaystyle V=(V_{0},V_{1},.....,V_{n-1})}$

${\displaystyle V_{j}}$= donde, ${\displaystyle \Sigma _{i=0}^{n-1}\omega ^{ij}v_{i}}$

${\displaystyle k=0,.....,n-1}$

Aquí está el índice de tiempo , la frecuencia y el espectro . Una diferencia importante entre la transformada de Fourier en un campo complejo y el campo de Galois es que el campo complejo existe para cada valor de mientras que en el campo de Galois existe solo si se divide . En el caso de campos de extensión, habrá una transformada de Fourier en el campo de extensión si se divide por algunos . En el campo de Galois, el vector en el dominio del tiempo está sobre el campo, pero el espectro puede estar sobre el campo de extensión . ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle V}$ ${\displaystyle \omega }$ ${\displaystyle n}$ ${\displaystyle \omega }$ ${\displaystyle n}$ ${\displaystyle q-1}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle n}$ ${\displaystyle q^{m}-1}$ ${\displaystyle m}$ ${\displaystyle v}$ ${\displaystyle GF(q)}$ ${\displaystyle V}$ ${\displaystyle GF(q^{m})}$

Descripción espectral

Cualquier palabra de código de código cíclico de longitud de bloque se puede representar mediante un polinomio de grado como máximo . Su codificador se puede escribir como . Por lo tanto, en el dominio de la frecuencia, el codificador se puede escribir como . Aquí el espectro de palabras en clave tiene un valor en pero todos los componentes en el dominio del tiempo son de . Como el espectro de datos es arbitrario, la función de es especificar aquellos en los que será cero. ${\displaystyle n}$ ${\displaystyle c(x)}$ ${\displaystyle n-1}$ ${\displaystyle c(x)=a(x)g(x)}$ ${\displaystyle C_{j}=A_{j}G_{j}}$ ${\displaystyle C_{j}}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle GF(q)}$ ${\displaystyle A_{j}}$ ${\displaystyle G_{j}}$ ${\displaystyle j}$ ${\displaystyle C_{j}}$

Por lo tanto, los códigos cíclicos también se pueden definir como

Dado un conjunto de índices espectrales , cuyos elementos se denominan frecuencias de verificación, el código cíclico es el conjunto de palabras cuyo espectro es cero en los componentes indexados por . Cualquier espectro de este tipo tendrá componentes de la forma . ${\displaystyle A=(j_{1},....,j_{n-k})}$ ${\displaystyle C}$ ${\displaystyle GF(q)}$ ${\displaystyle j_{1},...,j_{n-k}}$ ${\displaystyle C}$ ${\displaystyle A_{j}G_{j}}$

Entonces, los códigos cíclicos son vectores en el campo y el espectro dado por su transformada de Fourier inversa está sobre el campo y está obligado a ser cero en ciertos componentes. Pero cada espectro en el campo y cero en ciertos componentes puede no tener transformaciones inversas con los componentes en el campo . Dicho espectro no puede utilizarse como códigos cíclicos. ${\displaystyle GF(q)}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle GF(q)}$

A continuación se presentan algunos límites en el espectro de códigos cíclicos.

BCH vinculado

Si es un factor de para algunos . El único vector de peso o menos que tiene componentes consecutivos de su espectro iguales a cero es el vector todo cero. ${\displaystyle n}$ ${\displaystyle (q^{m}-1)}$ ${\displaystyle m}$ ${\displaystyle GF(q)^{n}}$ ${\displaystyle d-1}$ ${\displaystyle d-1}$

Hartmann-Tzeng obligado

Si es un factor de para algunos y un número entero coprimo con . El único vector de peso o menos cuyos componentes espectrales son iguales a cero para , donde y , es el vector todo cero. ${\displaystyle n}$ ${\displaystyle (q^{m}-1)}$ ${\displaystyle m}$ ${\displaystyle b}$ ${\displaystyle n}$ ${\displaystyle v}$ ${\displaystyle GF(q)^{n}}$ ${\displaystyle d-1}$ ${\displaystyle V_{j}}$ ${\displaystyle j=\ell _{1}+\ell _{2}b(\mod n)}$ ${\displaystyle \ell _{1}=0,....,d-s-1}$ ${\displaystyle \ell _{2}=0,....,s-1}$

Roos atado

Si es un factor de para algunos y . El único vector de peso o menos cuyos componentes espectrales son iguales a cero para , donde y toma al menos valores en el rango , es el vector todo cero. ${\displaystyle n}$ ${\displaystyle q^{m}-1}$ ${\displaystyle m}$ ${\displaystyle GCD(n,b)=1}$ ${\displaystyle GF(q)^{n}}$ ${\displaystyle d-1}$ ${\displaystyle V_{j}}$ ${\displaystyle j=l_{1}+l_{2}b(\mod n)}$ ${\displaystyle l_{1}=0,...,d-s-2}$ ${\displaystyle l_{2}}$ ${\displaystyle s+1}$ ${\displaystyle 0,....,d-2}$

Códigos de residuos cuadráticos

Cuando el código primo es un residuo cuadrático módulo, el código primo es un código de residuo cuadrático que es un código cíclico de longitud , dimensión y peso mínimo al menos por encima de . ${\displaystyle l}$ ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle (p+1)/2}$ ${\displaystyle {\sqrt {p}}}$ ${\displaystyle GF(l)}$

Generalizaciones

Un código constacíclico es un código lineal con la propiedad de que para alguna constante λ si ( c ₁ ,c ₂ ,..., c _n ) es una palabra de código entonces también lo es (λ c _n ,c ₁ ,..., c _{n -1} ). Un código negagíclico es un código constacíclico con λ=-1. ^[8] Un código cuasicíclico tiene la propiedad de que, para algunos s , cualquier desplazamiento cíclico de una palabra en código en s lugares es nuevamente una palabra en código. ^[9] Un código de doble circulación es un código cuasicíclico de longitud par con s =2. ^[9] Los códigos cuasi-torcidos y los códigos multi-torcidos son generalizaciones adicionales de los códigos constacíclicos . ^{[10] [11]}

Ver también

• código BCH
• Código binario Golay
• Verificación de redundancia cíclica
• Eugenio Prange
• Código Reed-Muller
• Código ternario Golay

Notas

1. Van Lint 1998, pág. 76
2. Van Lint 1998, pág. 80
3. Colina 1988, págs. 159-160
4. Blahut 2003, Teorema 5.5.1
5. Colina 1988, págs. 162-163
6. P. Fuego, E, P. (1959). Una clase de códigos binarios de corrección de errores múltiples para errores no independientes. Laboratorio de sistemas de reconocimiento Sylvania, Mountain View, CA, Rept. RSL-E-2, 1959.
7. Wei Zhou, Shu Lin, Khaled Abdel-Ghaffar. Corrección de errores aleatorios o en ráfagas basada en códigos Fire y BCH. ITA 2014: 1-5 2013.
8. Van Lint 1998, pág. 75
9. MacWilliams y Sloane 1977, pág. 506
10. Aydin, Nuh; Siap, Irfan; K. Ray-Chaudhuri, Dijen (2001). "La estructura de códigos cuasi-retorcidos de 1 generador y nuevos códigos lineales". Diseños, Códigos y Criptografía . 24 (3): 313–326. doi :10.1023/A:1011283523000. S2CID  17376783.
11. Aydin, Nuh; Halilović, Ajdin (2017). "Una generalización de códigos cuasi torcidos: códigos multitorcidos". Campos finitos y sus aplicaciones . 45 : 96-106. arXiv : 1701.01044 . doi : 10.1016/j.ffa.2016.12.002 . S2CID  7694655.

Referencias

• Blahut, Richard E. (2003), Códigos algebraicos para la transmisión de datos (2ª ed.), Cambridge University Press , ISBN 0-521-55374-1
• Hill, Raymond (1988), Un primer curso de teoría de la codificación , Oxford University Press , ISBN 0-19-853803-0
• MacWilliams, FJ ; Sloane, NJA (1977), La teoría de los códigos correctores de errores , Nueva York: North-Holland Publishing, ISBN 0-444-85011-2
• Van Lint, JH (1998), Introducción a la teoría de la codificación , Textos de posgrado en matemáticas 86 (3.ª ed.), Springer Verlag , ISBN 3-540-64133-5

Otras lecturas

• Ranjan Bose , Teoría de la información, codificación y criptografía , ISBN 0-07-048297-7 
• Irving S. Reed y Xuemin Chen, Codificación de control de errores para redes de datos , Boston: Kluwer Academic Publishers, 1999, ISBN 0-7923-8528-4 . 
• Scott A. Vanstone , Paul C. Van Oorschot, Introducción a los códigos de corrección de errores con aplicaciones , ISBN 0-7923-9017-2 

enlaces externos

• Apuntes de clase de John Gill (Stanford): notas n.° 3, 8 de octubre, folleto n.° 9 Archivado el 23 de octubre de 2012 en Wayback Machine , EE 387.
• Apuntes de clase de Jonathan Hall (MSU) – Capítulo 8. Códigos cíclicos - págs. 100 - 123
• David Terr. "Código cíclico". MundoMatemático .

Este artículo incorpora material del código cíclico de PlanetMath , que tiene la licencia Creative Commons Attribution/Share-Alike License .