En la teoría de la codificación , un código cíclico es un código de bloque , donde los cambios 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 de errores eficientes .
Definición
Dejar ser un código lineal sobre un campo finito (también llamado campo de Galois )de bloque de longitud n .se llama código cíclico si, para cada palabra de código c = ( c 1 , ..., c n ) de C , la palabra ( c n , c 1 , ..., c n-1 ) enobtenido por un desplazamiento cíclico a la derecha de componentes es nuevamente una palabra de código. Debido a que un desplazamiento cíclico a la derecha es igual a n - 1 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 bajo todos los cambios cíclicos.
Los códigos cíclicos tienen algunas restricciones estructurales adicionales sobre los códigos. Se basan en campos de Galois y por sus propiedades estructurales son muy útiles para el control de errores. Su estructura está fuertemente relacionada con los campos de Galois debido a 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. Dejarser un anillo polinomial sobre el campo finito. Identifique los elementos del código cíclico C con polinomios en R tales que se asigna al polinomio : por tanto, la multiplicación por x corresponde a un desplazamiento cíclico. Entonces C es un ideal en R , y por lo tanto principal , ya que R es un anillo ideal principal . El ideal es generado por el único elemento monico en C de grado mínimo, el polinomio generador g . [1] Debe ser un divisor de. De ello se deduce que todo código cíclico es un código polinomial . Si el polinomio generador g tiene grado d, entonces el rango del código C es.
El idempotente de C es una palabra de código e tal que e 2 = e (es decir, e es un elemento idempotente de C ) ye es una identidad para el código, es decir e c = c para cada palabra de código c . Si n y q son primos entre sí, una de esas palabras siempre existe y es única; [2] es un generador del código.
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 R , por lo que su polinomio de control es un polinomio irreducible .
Ejemplos de
Por ejemplo, si A =y n = 3, el conjunto de palabras de código contenidas en el código cíclico generado por (1,1,0) es precisamente
- .
Corresponde al ideal en generado por .
El polinomio es irreducible en el anillo polinomial y, por tanto, el código es un código irreducible.
El idempotente de este código es el polinomio , correspondiente a la palabra de código (0,1,1).
Ejemplos triviales
Ejemplos triviales de códigos cíclicos son el propio A n y el código que contiene solo la palabra de código cero. Corresponden a los generadores 1 y respectivamente: estos dos polinomios deben ser siempre factores de .
Sobre GF (2) el código de bit de paridad , que consta de todas las palabras de peso par, corresponde al generador. Nuevamente sobre GF (2) esto siempre debe ser un factor de.
Códigos cuasicíclicos y códigos abreviados
Antes de profundizar en los detalles de los códigos cíclicos, primero discutiremos 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 requerida ]
Un El código cuasicíclico es un código de bloque lineal tal que, para algunos que es coprime a , el polinomio es un polinomio de palabra en clave siempre que es un polinomio de palabras en clave.
Aquí, el polinomio de la 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 menor longitud llamado polinomio generador . Cada polinomio de palabra en clave se puede expresar en la forma, dónde es el polinomio generador. Cualquier palabra en clave de un código cíclico se puede asociar con un polinomio de palabra en clave, es decir, . Un código cuasicíclico con igual a es un código cíclico.
Definición
Códigos abreviados:
Un El código lineal se denomina código cíclico abreviado adecuado si se puede obtener eliminando posiciones de un código cíclico.
En los códigos abreviados, los símbolos de información se eliminan para obtener una longitud de bloque deseada menor 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 principio de la palabra de código y se consideran 0. Por lo tanto,- es fijo, y luego se reduce, lo que eventualmente disminuye . No es necesario borrar los símbolos iniciales. Dependiendo de la aplicación, a veces las posiciones consecutivas se consideran 0 y se eliminan.
No es necesario transmitir todos los símbolos que se eliminan y en el extremo receptor se pueden volver a insertar. Para convertir código cíclico para código abreviado, establecer símbolos a cero y elimínelos de cada palabra de código. Cualquier código cíclico se puede convertir en códigos cuasicíclicos eliminando cadael símbolo donde es un factor de . Si los símbolos eliminados no son símbolos de verificación, este código cíclico también es un código abreviado.
Códigos cíclicos para corregir errores
Ahora, comenzaremos la discusión de los códigos cíclicos explícitamente con la detección y corrección de errores . Los códigos cíclicos se pueden usar para corregir errores, como los códigos de Hamming, ya que los códigos cíclicos se pueden usar 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 subsecciones posteriores.
El código de 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 elementos primitivos y como ceros en el porque aquí estamos considerando el caso de dos errores, por lo que cada uno representará un error.
La palabra recibida es un polinomio de grado. dado como
dónde puede tener como máximo dos coeficientes distintos de cero correspondientes a 2 errores.
Definimos el Síndrome Polinomial , como el resto del polinomio cuando se divide por el polinomio generador es decir
como .
Para corregir dos errores
Deje que los elementos del campo y sean 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.
Dejar y .
Estos elementos de campo se denominan "síndromes". Ahora porque es cero en elementos primitivos y , para que podamos escribir y . Si dicen que ocurren dos errores, entonces
y .
Y estos dos pueden considerarse como dos pares de ecuaciones en con dos incógnitas y, por lo tanto, podemos escribir
y .
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 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 de Hamming binario de la forma Ham (r, 2) es equivalente a un código cíclico, [3] y cualquier código de Hamming de la forma Ham (r, q) con r y q-1 primos relativos también es equivalente. a un código cíclico. [4] Dado un código de Hamming de la forma Ham (r, 2) con, el conjunto de palabras de código pares forma un cíclico -código. [5]
Código Hamming para corregir errores individuales
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 una -bit número binario. Existenposibles 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.
Es fácil definir códigos Hamming para alfabetos grandes de tamaño . Necesitamos definir unomatriz con columnas linealmente independientes. Para cualquier palabra de tamañohabrá columnas que son múltiplos entre sí. Entonces, para obtener independencia lineal todos distintos de cero-tuplas con uno como elemento superior más 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.
Entonces, hay columnas distintas de cero con uno como elemento superior más distinto de cero. Por lo tanto, un código de Hamming es un código.
Ahora, para los códigos cíclicos, dejemos ser elemento primitivo en , y deja . Luego y por lo tanto es un cero del polinomio y es un polinomio generador para el código cíclico de longitud de bloque .
Pero para , . Y la palabra recibida es un polinomio de grado dado como
dónde, o dónde representa las ubicaciones de error.
Pero también podemos usar como un elemento de para indexar la ubicación del error. Porque, tenemos y todos los poderes de de a son distintos. Por lo tanto, podemos determinar fácilmente la ubicación del error. de a no ser que que no representa ningún error. Entonces, un código de Hamming es un código de corrección de error único sobre con y .
Códigos cíclicos para corregir errores de ráfaga
Desde el concepto de distancia de Hamming , un código con distancia mínima puede corregir cualquier errores. Pero en muchos canales, el patrón de error no es muy arbitrario, ocurre en 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 de mayor velocidad debido a las menos restricciones. Los códigos cíclicos se utilizan para corregir el error de ráfaga. De hecho, los códigos cíclicos también pueden corregir errores de ráfaga cíclica junto con errores de ráfaga. Los errores de ráfagas cíclicas se definen como
Una ráfaga cíclica de longitud es un vector cuyos componentes distintos de cero se encuentran entre (cíclicamente) componentes consecutivos, el primero y el último de los cuales son distintos de cero.
En forma polinomial ráfaga cíclica de longitud se puede describir como con como polinomio de grado con coeficiente distinto de cero . Aquí define el patrón y define el punto de partida del error. La longitud del patrón viene dada por grados. El polinomio del síndrome es único para cada patrón y viene dado por
Un código de bloque lineal que corrige todos los errores de ráfaga de longitud. o menos debe tener al menos comprobar los símbolos. Prueba: porque cualquier código lineal que pueda corregir el patrón de ráfaga de longitud o menos no puede tener una explosión de longitud o menos como una palabra en clave porque si lo hiciera, entonces una ráfaga de longitud podría cambiar la palabra de código a patrón de ráfaga , que también podría obtenerse cometiendo un error de ráfaga de longitud en toda palabra de código cero. Ahora, dos vectores cualesquiera que sean distintos de cero en el primer los componentes deben ser de diferentes co-conjuntos 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 co-conjuntos es igual al número de tales vectores que son. Por lo tanto, al menos co-conjuntos y por lo tanto al menos símbolo de verificación.
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.
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 un producto de un binomio y un polinomio primitivo. El binomio tiene la forma para algún entero impar positivo . [7] El código de incendio es un código de corrección de errores de ráfaga cíclica sobre con el polinomio generador
dónde 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 tal que divide .
Un código de incendio puede corregir todos los errores de ráfaga de longitud to menos si no hay dos ráfagas y aparecen en el mismo co-set. Esto se puede demostrar por contradicción. Suponga que hay dos ráfagas distintas de cero y de longitud o menos y están en el mismo co-conjunto del código. Entonces, su diferencia es una palabra clave. Como la diferencia es un múltiplo de también es un múltiplo de . Por lo tanto,
.
Esto muestra que es un múltiplo de , Entonces
para algunos . No fue es menos que y es menos que entonces es una palabra en clave. Por lo tanto,
.
Desde el grado es menor que el grado de , no se puede dividir . Si no es cero, entonces tampoco puedo dividir como es menos que y por definición de , divide por no menor que . Por lo tanto y es igual a cero. Eso significa que ambas ráfagas son iguales, contrariamente a lo que se supone.
Los códigos de incendio son los mejores códigos de corrección de ráfagas individuales con alta tasa y se construyen analíticamente. Son de muy alta tasa y cuando y son iguales, la redundancia es mínima y es igual a . Mediante el uso de varios códigos de incendio, también se pueden corregir errores de ráfagas más largas.
Para la detección de errores, los códigos cíclicos se utilizan ampliamente y se denominan códigos de redundancia cíclica .
Códigos cíclicos 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 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 la señal.
Transformada de Fourier sobre campos finitos
Transformada de Fourier sobre campos finitos
La transformada discreta de Fourier del vector viene dado por un vector dónde,
= dónde,
donde exp () es un la raíz de la unidad. Similarmente en el campo finitoLa raíz de la unidad es el elemento. de orden . Por lo tanto
Si es un vector sobre , y ser un elemento de de orden , luego la transformada de Fourier del vector es el vector y los componentes están dados por
= dónde,
Aquí es el índice de tiempo ,es frecuencia yes el espectro . Una diferencia importante entre la transformada de Fourier en el 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 divide . En el caso de campos de extensión, habrá una transformada de Fourier en el campo de extensión. Si divide para algunos . En el vector de dominio del tiempo de campo de Galois está sobre el campo pero el espectro puede estar sobre el campo de extensión .
Descripción espectral de códigos cíclicos
Cualquier palabra en clave de código cíclico de longitud de bloque puede ser representado por un polinomio de grado como máximo . Su codificador se puede escribir como. Por lo tanto, en el dominio de 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, el papel de es especificar aquellos dónde será cero.
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 control, el código cíclico ¿Se acabó el conjunto de palabras? cuyo espectro es cero en los componentes indexados por . Cualquiera de esos espectros tendrá componentes de la forma .
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án obligados a ser cero en ciertos componentes. Pero cada espectro en el campo y cero en ciertos componentes puede no tener transformaciones inversas con componentes en el campo . Dicho espectro no se puede utilizar como códigos cíclicos.
A continuación se muestran los pocos límites del espectro de códigos cíclicos.
BCH obligado
Si ser un factor de para algunos . El único vector en de peso o menos que tiene componentes consecutivos de su espectro igual a cero es un vector todo cero.
Hartmann-Tzeng encuadernado
Si ser un factor de para algunos , y un número entero que es coprime con . El único vector en de peso o menos cuyos componentes espectrales igual a cero para , dónde y , es el vector todo cero.
Roos obligado
Si ser un factor de para algunos y . El único vector en de peso o menos cuyos componentes espectrales igual a cero para , dónde y toma al menos valores en el rango , es el vector todo cero.
Códigos de residuos cuadráticos
Cuando el mejor es un residuo cuadrático módulo el primo hay un código de residuo cuadrático que es un código cíclico de longitud, dimensión y peso mínimo al menos encima .
Generalizaciones
Un código constacíclico es un código lineal con la propiedad de que para alguna constante λ si ( c 1 , c 2 , ..., c n ) es una palabra de código, entonces también lo es (λ c n , c 1 , ..., c n -1 ). Un código negacyclic es un código constacyclic con λ = -1. [8] Un código cuasicíclico tiene la propiedad de que para algunos s , cualquier desplazamiento cíclico de una palabra de código en s lugares es nuevamente una palabra de código. [9] Un código circulante doble es un código cuasicíclico de longitud par con s = 2. [9]
Ver también
- Verificación de redundancia cíclica
- Código BCH
- Código Reed-Muller
- Código binario de Golay
- Código de Golay ternario
- Eugene Prange
Notas
- ^ Van Lint 1998 , p. 76
- ^ Van Lint 1998 , p. 80
- ^ Hill 1988 , págs. 159-160
- ^ Blahut 1983 , Teorema 5.5.1
- ^ Hill 1988 , págs. 162-163
- ^ 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 de Sylvania, Mountain View, CA, Rept. RSL-E-2, 1959.
- ^ 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 de 2013.
- ^ Van Lint 1998 , p. 75
- ↑ a b MacWilliams y Sloane , 1977 , p. 506
Referencias
- Blahut, Richard E. (2003), Códigos algebraicos para la transmisión de datos (2a ed.), Cambridge University Press , ISBN 0-521-55374-1
- Hill, Raymond (1988), primer curso de teoría de la codificación , Oxford University Press , ISBN 0-19-853803-0
- MacWilliams, FJ ; Sloane, NJA (1977), The Theory of Error-Correcting Codes , 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.a 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 , 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 está bajo la licencia Creative Commons Attribution / Share-Alike License .