Código cíclico

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

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

Muchos tipos de códigos correctores de errores de uso común pueden representarse como códigos cíclicos, incluidos los códigos BCH , los códigos Reed-Solomon y algunas clases de códigos de verificación de paridad de baja densidad definidos a partir de geometrías finitas. ^{[ 4 ]}

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

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

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

${\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 en${\displaystyle GF(2^{m})}$con dos incógnitas y por lo tanto podemos escribir

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

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

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

Es fácil definir códigos de Hamming para alfabetos grandes de tamaño${\displaystyle q}$Necesitamos definir uno${\displaystyle H}$matriz con columnas linealmente independientes. Para cualquier palabra de tamaño${\displaystyle q}$Habrá columnas que sean múltiplos entre sí. Por lo tanto, para obtener independencia lineal, todos los valores distintos de cero deben ser iguales.${\displaystyle m}$Las tuplas cuyo elemento distinto de cero sea uno se elegirán como columnas. Por lo tanto, dos columnas nunca serán linealmente dependientes, ya que tres columnas podrían serlo con una distancia mínima de 3 en el código.

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

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

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

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

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

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

En 1959, Philip Fire ^{[ 8 ]} 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${\displaystyle x^{c}+1}$para algún entero impar positivo${\displaystyle c}$. ^{[ 9 ]} El código de fuego es un código de corrección de errores de ráfaga cíclica sobre${\displaystyle GF(q)}$con el polinomio generador

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

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

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

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

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

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

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

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

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

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

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

Transformada de Fourier sobre campos finitos

La transformada discreta de Fourier de un vector${\displaystyle v=v_{0},v_{1},....,v_{n-1}}$ está dado por un vector${\displaystyle V=V_{0},V_{1},.....,V_{n-1}}$dónde,

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

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

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

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

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

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

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

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

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

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

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

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

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

Un código constacíclico es un código lineal con la propiedad de que para alguna constante${\displaystyle \lambda }$si${\displaystyle (c_{1},c_{2},\dots ,c_{n})}$es una palabra clave, entonces también lo es${\displaystyle (\lambda c_{n},c_{1},\dots ,c_{n-1})}$. Un código negacíclico es un código constacíclico con${\displaystyle \lambda =-1}$. ^{[ 10 ]}

Un código cuasicíclico (código QC) tiene la propiedad de que para algún${\displaystyle s}$divisor${\displaystyle n}$, cualquier cambio cíclico de una palabra clave por${\displaystyle s}$lugares es de nuevo una palabra clave. Es decir, para alguna constante${\displaystyle s}$, si${\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}$es una palabra clave, entonces también lo es${\displaystyle (c_{-s},c_{1-s},\dots ,c_{n-s-1})}$donde todos los subíndices se reducen mod${\displaystyle n}$. ^{[ 11 ]} Dicho código se conoce como un${\displaystyle s}$-Código QC. Un código circulante doble es un código cuasicíclico de longitud par con${\displaystyle s=2}$. ^{[ 11 ]}

Un${\displaystyle (n,k)}$El código lineal se denomina código cíclico abreviado si se puede obtener eliminando${\displaystyle b}$puestos de un${\displaystyle (n+b,k+b)}$Código cíclico. Los códigos de esta forma generalmente no son cíclicos. ^{[ 12 ]}

En los códigos abreviados, se eliminan símbolos de información para obtener una longitud de bloque deseada menor que la longitud de bloque original. Al eliminar el primero${\displaystyle b}$El uso de símbolos es un enfoque común; en principio, cualquier conjunto de símbolos de información puede eliminarse. ^{[ 12 ]} Cualquier código cíclico puede convertirse en un código cuasicíclico eliminando cada${\displaystyle b}$-ésimo símbolo, donde${\displaystyle b}$es un factor de${\displaystyle n}$. Si los símbolos omitidos no son símbolos de control, este código cíclico también es un código cíclico abreviado.

Los códigos cuasi-retorcidos (códigos QT) combinan las propiedades de los códigos constacíclicos y cuasicíclicos, con el desplazamiento producido por${\displaystyle s}$lugares y con un multiplicador de${\displaystyle \lambda }$. Es decir, para algunas constantes${\displaystyle \lambda }$y${\displaystyle s}$, si${\displaystyle (c_{0},c_{1},\dots ,c_{n-1})}$es una palabra clave, entonces también lo es${\displaystyle (\lambda c_{-s},c_{1-s},\dots ,c_{n-s-1})}$donde todos los subíndices se reducen mod${\displaystyle n}$. ^{[ 13 ]} Los códigos multi-retorcidos son generalizaciones adicionales de los códigos QT, que unen múltiples códigos QT de extremo a extremo. ^{[ 13 ] [ 14 ]}