código polinómico

En teoría de codificación , un código polinómico es un tipo de código lineal cuyo conjunto de palabras de código válidas consta de aquellos polinomios (normalmente de alguna longitud fija) que son divisibles por un polinomio fijo determinado (de longitud más corta, llamado polinomio generador ).

Definición

Fijar un campo finito , cuyos elementos llamamos símbolos . Para construir códigos polinomiales, identificamos una cadena de símbolos con el polinomio ${\displaystyle GF(q)}$ ${\displaystyle n}$ ${\displaystyle a_{n-1}\ldots a_{0}}$

${\displaystyle a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}.\,}$

Fija los números enteros y deja que sea algún polinomio fijo de grado , llamado polinomio generador . El código polinomial generado por es el código cuyas palabras de código son precisamente los polinomios de grado menor que son divisibles (sin resto) por . ${\displaystyle m\leq n}$ ${\displaystyle g(x)}$ ${\displaystyle m}$ ${\displaystyle g(x)}$ ${\displaystyle n}$ ${\displaystyle g(x)}$

Ejemplo

Considere el código polinómico con , y el polinomio generador . Este código consta de las siguientes palabras de código: ${\displaystyle GF(2)=\{0,1\}}$ ${\displaystyle n=5}$ ${\displaystyle m=2}$ ${\displaystyle g(x)=x^{2}+x+1}$

${\displaystyle 0\cdot g(x),\quad 1\cdot g(x),\quad x\cdot g(x),\quad (x+1)\cdot g(x),}$

${\displaystyle x^{2}\cdot g(x),\quad (x^{2}+1)\cdot g(x),\quad (x^{2}+x)\cdot g(x),\quad (x^{2}+x+1)\cdot g(x).}$

O escrito explícitamente:

${\displaystyle 0,\quad x^{2}+x+1,\quad x^{3}+x^{2}+x,\quad x^{3}+2x^{2}+2x+1,}$

${\displaystyle x^{4}+x^{3}+x^{2},\quad x^{4}+x^{3}+2x^{2}+x+1,\quad x^{4}+2x^{3}+2x^{2}+x,\quad x^{4}+2x^{3}+3x^{2}+2x+1.}$

Dado que el código polinomial se define sobre el campo binario de Galois , los elementos polinomiales se representan como una suma de módulo -2 y los polinomios finales son: ${\displaystyle GF(2)=\{0,1\}}$

${\displaystyle 0,\quad x^{2}+x+1,\quad x^{3}+x^{2}+x,\quad x^{3}+1,}$

${\displaystyle x^{4}+x^{3}+x^{2},\quad x^{4}+x^{3}+x+1,\quad x^{4}+x,\quad x^{4}+x^{2}+1.}$

De manera equivalente, expresadas como cadenas de dígitos binarios, las palabras en clave son:

${\displaystyle 00000,\quad 00111,\quad 01110,\quad 01001,}$

${\displaystyle 11100,\quad 11011,\quad 10010,\quad 10101.}$

Este, como todo código polinómico, es de hecho un código lineal , es decir, las combinaciones lineales de palabras de código son nuevamente palabras de código. En un caso como este donde el campo es GF(2), las combinaciones lineales se encuentran tomando el XOR de las palabras de código expresadas en forma binaria (por ejemplo, 00111 XOR 10010 = 10101).

Codificación

En un código polinómico con una longitud de código y un polinomio generador de grado , habrá exactamente palabras de código. De hecho, por definición, es una palabra clave si y sólo si tiene la forma , donde (el cociente ) es de grado menor que . Dado que existen tales cocientes disponibles, existe el mismo número de palabras de código posibles. Por lo tanto, las palabras de datos simples (no codificadas) deben tener una longitud ${\displaystyle GF(q)}$ ${\displaystyle n}$ ${\displaystyle g(x)}$ ${\displaystyle m}$ ${\displaystyle q^{n-m}}$ ${\displaystyle p(x)}$ ${\displaystyle p(x)=g(x)\cdot q(x)}$ ${\displaystyle q(x)}$ ${\displaystyle n-m}$ ${\displaystyle q^{n-m}}$ ${\displaystyle n-m}$

Algunos autores, como (Lidl y Pilz, 1999), sólo analizan el mapeo como la asignación de palabras de datos a palabras de código. Sin embargo, esto tiene la desventaja de que la palabra de datos no aparece como parte de la palabra de código. ${\displaystyle q(x)\mapsto g(x)\cdot q(x)}$

En cambio, el siguiente método se utiliza a menudo para crear un código sistemático : dada una palabra de datos de longitud , primero se multiplica por , lo que tiene el efecto de desplazarse lugares hacia la izquierda. En general, no será divisible por , es decir, no será una palabra clave válida. Sin embargo, existe una palabra de código única que se puede obtener ajustando los símbolos de la derecha . Para calcularlo, calcula el resto de dividir por : ${\displaystyle d(x)}$ ${\displaystyle n-m}$ ${\displaystyle d(x)}$ ${\displaystyle x^{m}}$ ${\displaystyle d(x)}$ ${\displaystyle m}$ ${\displaystyle x^{m}d(x)}$ ${\displaystyle g(x)}$ ${\displaystyle m}$ ${\displaystyle x^{m}d(x)}$ ${\displaystyle x^{m}d(x)}$ ${\displaystyle g(x)}$

${\displaystyle x^{m}d(x)=g(x)\cdot q(x)+r(x),\,}$

donde es de grado menor que . La palabra de código correspondiente a la palabra de datos se define entonces como ${\displaystyle r(x)}$ ${\displaystyle m}$ ${\displaystyle d(x)}$

${\displaystyle p(x):=x^{m}d(x)-r(x),\,}$

Tenga en cuenta las siguientes propiedades:

1. ${\displaystyle p(x)=g(x)\cdot q(x)}$, que es divisible por . En particular, es una palabra clave válida. ${\displaystyle g(x)}$ ${\displaystyle p(x)}$
2. Como es de grado menor que , los símbolos de más a la izquierda concuerdan con los símbolos correspondientes de . En otras palabras, los primeros símbolos de la palabra de código son los mismos que los de la palabra de datos original. Los símbolos restantes se denominan dígitos de suma de control o bits de control . ${\displaystyle r(x)}$ ${\displaystyle m}$ ${\displaystyle n-m}$ ${\displaystyle p(x)}$ ${\displaystyle x^{m}d(x)}$ ${\displaystyle n-m}$ ${\displaystyle m}$

Ejemplo

Para el código anterior con , y polinomio generador , obtenemos la siguiente asignación de palabras de datos a palabras de código: ${\displaystyle n=5}$ ${\displaystyle m=2}$ ${\displaystyle g(x)=x^{2}+x+1}$

• 000 ↦ 000 00
• 001 ↦ 001 11
• 010 ↦ 010 01
• 011 ↦ 011 10
• 100 ↦ 100 10
• 101 ↦ 101 01
• 110 ↦ 110 11
• 111 ↦ 111 00

Descodificación

Un mensaje erróneo se puede detectar de forma sencilla mediante la división del polinomio por el polinomio generador, lo que da como resultado un resto distinto de cero.

Suponiendo que la palabra clave esté libre de errores, se puede descodificar un código sistemático simplemente eliminando los dígitos de la suma de comprobación. ${\displaystyle m}$

Si hay errores, se debe realizar la corrección de errores antes de decodificar. Existen algoritmos de decodificación eficientes para códigos polinomiales específicos, como los códigos BCH .

Propiedades de los códigos polinomiales

Como ocurre con todos los códigos digitales, las capacidades de detección y corrección de errores de los códigos polinomiales están determinadas por la distancia mínima de Hamming del código. Dado que los códigos polinomiales son códigos lineales, la distancia mínima de Hamming es igual al peso mínimo de cualquier palabra de código distinta de cero. En el ejemplo anterior, la distancia mínima de Hamming es 2, ya que 01001 es una palabra de código y no hay ninguna palabra de código distinta de cero con un solo bit establecido.

Las propiedades más específicas de un código polinómico a menudo dependen de propiedades algebraicas particulares de su polinomio generador. A continuación se muestran algunos ejemplos de tales propiedades:

• Un código polinómico es cíclico si y sólo si el polinomio generador se divide . ${\displaystyle x^{n}-1}$
• Si el polinomio generador es primitivo , entonces el código resultante tiene una distancia de Hamming de al menos 3, siempre que . ${\displaystyle n\leq 2^{m}-1}$
• En los códigos BCH , el polinomio generador se elige para que tenga raíces específicas en un campo de extensión, de manera que se logre una alta distancia de Hamming.

La naturaleza algebraica de los códigos polinomiales, con polinomios generadores inteligentemente elegidos, a menudo también puede aprovecharse para encontrar algoritmos eficientes de corrección de errores. Este es el caso de los códigos BCH .

Familias específicas de códigos polinomiales.

• Códigos cíclicos – cada código cíclico es también un código polinómico; un ejemplo popular es el código CRC .
• Códigos BCH : una familia de códigos cíclicos con una alta distancia de Hamming y algoritmos de corrección de errores algebraicos eficientes.
• Códigos Reed-Solomon : un subconjunto importante de códigos BCH con una estructura particularmente eficiente.

Referencias

• WJ Gilbert y WK Nicholson: Álgebra moderna con aplicaciones , segunda edición, Wiley, 2004.
• R. Lidl y G. Pilz. Álgebra abstracta aplicada, 2ª edición. Wiley, 1999.