Código cíclico

Tipo de código de bloque

En teoría de codificación , un código cíclico es un código de bloques , 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 son convenientes para la detección y corrección eficiente de errores .

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 es nuevamente una palabra de código válida. En general, al aplicar un desplazamiento circular hacia la derecha, el bit menos significativo (LSB) se desplaza a la posición más a la izquierda, de modo que se convierte en el bit más significativo (MSB); las otras posiciones se desplazan en 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 denomina código cíclico si, para cada palabra de código de , la palabra en 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, un código cíclico también puede definirse mediante desplazamientos cíclicos a la izquierda. Por lo tanto, el código lineal es cíclico precisamente cuando es invariante bajo todos los desplazamientos 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 algunas restricciones estructurales adicionales. Se basan en campos de Galois y, debido a sus propiedades estructurales, son muy útiles para el control de errores. Su estructura está estrechamente 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 pueden vincularse a ideales en ciertos anillos. Sea un anillo polinomial sobre el cuerpo finito . Identifique los elementos del código cíclico con polinomios en tales que se asignan al polinomio : por lo tanto, la multiplicación por corresponde a un desplazamiento cíclico. Entonces es un ideal en , y por lo tanto principal , ya que es un anillo ideal principal . El ideal es generado por el único elemento mónico en de grado mínimo, el polinomio generador . ^[1] Este debe ser un divisor de . De ello se deduce que todo código cíclico es un código polinomial . 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 de código tal que (es decir, es un elemento idempotente de ) y es una identidad para el código, es decir para cada palabra de código . 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 verificación 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 en generado por . ${\displaystyle \mathbb {F} _{2}[x]/(x^{3}-1)}$ ${\displaystyle (1+x)}$

El polinomio es irreducible en el anillo de polinomios y, por lo 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 código . ${\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 únicamente la palabra clave cero. Estos corresponden a los generadores y respectivamente: estos dos polinomios deben ser siempre factores de . ${\displaystyle A^{n}}$ ${\displaystyle 1}$ ${\displaystyle x^{n}-1}$ ${\displaystyle x^{n}-1}$

Sobre el código de bit de paridad , que consta de todas las palabras de peso par, corresponde al generador . Nuevamente sobre 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 cuasiciclicos y acortados, que están estrechamente relacionados con los códigos cíclicos y todos ellos pueden convertirse entre sí.

Definición

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

Un código cuasicíclico es un código de bloque lineal tal que, para algún que es coprimo con , el polinomio es un polinomio de palabra de código siempre que es un polinomio de palabra de 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 de código es un elemento de un código lineal cuyas palabras de código son polinomios que son divisibles por un polinomio de longitud más corta llamado polinomio generador . Cada polinomio de palabra de código se puede expresar en la forma , donde es el polinomio generador. Cualquier palabra de código de un código cíclico se puede asociar con un polinomio de palabra de código, es decir, . Un código cuasicíclico con 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 acortado apropiado si se puede obtener eliminando posiciones de un código cíclico. ${\displaystyle (n,k)}$ ${\displaystyle b}$ ${\displaystyle (n+b,k+b)}$

En los códigos abreviados, se eliminan los símbolos de información para obtener una longitud de bloque deseada menor que la longitud de bloque de diseño. Por lo general, se supone que los símbolos de información que faltan están al principio de la palabra de código y se consideran 0. Por lo tanto, − es fijo y luego se reduce, lo que finalmente disminuye a . 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 volver a insertar. Para convertir un código cíclico en un código abreviado, 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 th 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 errores simples. Asimismo, también se utilizan para corregir errores dobles y errores de ráfaga. Todos los tipos de corrección 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 de código satisfacen . Los códigos cíclicos también se pueden utilizar para corregir errores dobles en el campo . La longitud de bloque será igual a y los elementos primitivos y como ceros en el porque estamos considerando el caso de dos errores aquí, 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 al dividirlo 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)}$

Para corregir dos errores

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

Sea 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, por ejemplo, se producen 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 estos 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 utilizar códigos cíclicos para corregir dos errores.

Código de Hamming

El código Hamming(7,4) puede escribirse 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 primos entre sí 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 de 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 de Hamming para corregir errores individuales

Un código cuya distancia mínima es al menos 3, tiene una matriz de comprobación cuyas columnas son todas distintas y no nulas. Si una matriz de comprobación para un código binario tiene filas, entonces cada columna es un número binario de 0 a 100 bits. Hay columnas posibles. Por lo tanto, si una matriz de comprobació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 de Hamming para alfabetos grandes de tamaño . Necesitamos definir una matriz con columnas linealmente independientes. Para cualquier palabra de tamaño habrá columnas que sean múltiplos entre sí. Por lo tanto, para obtener independencia lineal, se elegirán como columnas todas las tuplas distintas de cero con uno como el elemento distinto de cero más alto. 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}$

Por lo tanto, hay columnas distintas de cero con un elemento distinto de cero como el más alto. Por lo 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 bien, para los códigos cíclicos, sea 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)}$

donde, o donde representa las ubicaciones de los errores. ${\displaystyle e(x)=0}$ ${\displaystyle x^{i}}$ ${\displaystyle i}$

Pero también podemos utilizar como elemento de para indexar la ubicación del error. Debido a que , tenemos y todas las potencias de desde hasta son distintas. Por lo tanto, podemos determinar fácilmente la ubicación del error desde a menos que represente que no hay error. Por lo tanto, un código de Hamming es un código de corrección de errores único sobre 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

Según 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, sino que se produce en segmentos muy cortos del mensaje. Este tipo de errores se denominan errores de ráfaga . Por lo tanto, para corregir dichos errores, obtendremos un código más eficiente y de mayor velocidad 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íclicos 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 ráfaga cíclica de longitud se puede describir como un polinomio de grado con coeficiente distinto de cero . Aquí se define el patrón y se define el punto de inicio del error. La longitud del patrón se da por deg . El polinomio de síndrome es único para cada patrón y se da 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 corrige todos los errores de ráfaga de longitud o menos debe tener al menos símbolos de verificación. Demostración: 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 de código porque si la tuviera, una ráfaga de longitud podría cambiar la palabra de código a un patrón de ráfaga de longitud , que también podría obtenerse al hacer un error de ráfaga de longitud en todas las palabras de código cero. Ahora, cualesquiera dos vectores que no sean cero en los primeros componentes deben ser de diferentes coconjuntos de una matriz para evitar que su diferencia sea una palabra de código de ráfagas de longitud . Por lo tanto, el número de tales coconjuntos es igual al número de tales vectores que son . Por lo tanto, al menos coconjuntos y, por lo tanto, al menos 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 de Singleton para la corrección de errores aleatorios.

Los códigos de incendio como límites cíclicos

En 1959, Philip Fire ^[6] presentó una construcción de códigos cíclicos generados por un producto de un binomio y un polinomio primitivo. El binomio tiene la forma de algún entero impar positivo . ^[7] El código Fire 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 a . La longitud del bloque del código de incendio es el entero más pequeño tal que divide a . ${\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 incendios puede corregir todos los errores de ráfaga de longitud t o menor si no aparecen dos ráfagas y en el mismo conjunto. Esto se puede demostrar por contradicción. Supongamos que hay dos ráfagas distintas de cero y de longitud o menor y están en el mismo conjunto del código. Por lo tanto, su diferencia es una palabra de código. Como la diferencia es un múltiplo de , también es un múltiplo de . 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 demuestra que es un múltiplo de , por lo que ${\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 entonces 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)}$.

Dado que el grado es menor que el grado de , no se puede dividir . Si no es cero, entonces tampoco se puede dividir, ya que es menor que y por definición de , divide por un número no menor que . Por lo tanto , y es igual a cero. Eso significa que ambas ráfagas son iguales, contrariamente a la suposición. ${\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áfagas únicas con una tasa alta y se construyen analíticamente. Tienen una tasa muy alta y cuando y son iguales, la redundancia es mínima y es igual a . Al usar múltiples códigos de incendio, también se pueden corregir errores de ráfagas más largas. ${\displaystyle m}$ ${\displaystyle t}$ ${\displaystyle 3t-1}$

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

Sobre 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 los 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 cuerpos finitos

Transformada de Fourier sobre cuerpos finitos

La transformada de Fourier discreta de un 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 ésima de la unidad. De manera similar, en el cuerpo finito, la raíz ésima 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 sobre , y es un elemento de 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 , es la frecuencia y es el espectro . Una diferencia importante entre la transformada de Fourier en un campo complejo y un campo de Galois es que el campo complejo existe para cada valor de mientras que en el campo de Galois existe solo si divide . En el caso de los campos de extensión, habrá una transformada de Fourier en el campo de extensión si divide para algún . En el campo de Galois, el vector del 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 puede representarse mediante un polinomio de grado como máximo . Su codificador puede escribirse como . Por lo tanto, en el dominio de la frecuencia, el codificador puede escribirse como . Aquí, el espectro de la palabra de código 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 donde 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}}$

Así, los códigos cíclicos también pueden definirse como

Dado un conjunto de índices espectrales, , cuyos elementos se denominan frecuencias de control, el código cíclico es el conjunto de palabras en 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}}$

Por lo tanto, los códigos cíclicos son vectores en el campo y el espectro dado por su transformada de Fourier inversa se encuentra sobre el campo y está restringido a ser cero en ciertos componentes. Pero todo espectro en el campo y cero en ciertos componentes puede no tener transformadas inversas con componentes en el campo . Dicho espectro no puede usarse como códigos cíclicos. ${\displaystyle GF(q)}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle GF(q^{m})}$ ${\displaystyle GF(q)}$

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

BCH vinculado

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

Límite Hartmann-Tzeng

Si es un factor de para algún , y un entero que es coprimo con . El único vector en de peso o menos cuyos componentes espectrales son iguales a cero para , donde y , es el vector de todos los ceros. ${\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}$

Canguros atados

Si es un factor de para algunos y . El único vector en 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 primo es un residuo cuadrático módulo el primo existe un código de residuo cuadrático que es un código cíclico de longitud , dimensión y peso mínimo al menos sobre . ${\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 negacíclico es un código constacíclico con λ=-1. ^[8] Un código cuasicíclico tiene la propiedad de que para algún s , cualquier desplazamiento cíclico de una palabra de código por s lugares es nuevamente una palabra de código. ^[9] Un código doble circulante es un código cuasicíclico de longitud par con s =2. ^[9] Los códigos cuasitrenzados y los códigos multitrenzados son generalizaciones adicionales de los códigos constacíclicos . ^{[10] [11]}

Véase también

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

Notas

1. Van Lint 1998, pág. 76
2. Van Lint 1998, pág. 80
3. Hill 1988, págs. 159-160
4. Blahut 2003, Teorema 5.5.1
5. Hill 1988, págs. 162-163
6. P. Fire, E, P. (1959). Una clase de códigos binarios de corrección de errores múltiples para errores no independientes. Sylvania Reconnaissance Systems Laboratory, Mountain View, CA, Rept. RSL-E-2, 1959.
7. Wei Zhou, Shu Lin, Khaled Abdel-Ghaffar. Corrección de errores aleatorios o de ráfaga 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-torcidos 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-trenzados: códigos multi-trenzados". 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 transmisión de datos (2.ª ed.), Cambridge University Press , ISBN 0-521-55374-1
• Hill, Raymond (1988), Un primer curso sobre 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 de corrección 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

Lectura adicional

• 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.
• Notas de clase de Jonathan Hall (MSU) – Capítulo 8. Códigos cíclicos - págs. 100 - 123
• David Terr. "Código cíclico". MathWorld .

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