Código polinomial

En teoría de codificación , un código polinomial es un tipo de código lineal cuyo conjunto de palabras de código válidas consiste en aquellos polinomios (generalmente de una longitud fija) que son divisibles por un polinomio fijo dado (de longitud más corta, llamado polinomio generador ).

Definición

Fijemos un cuerpo finito , cuyos elementos llamamos símbolos . Para los fines de construir códigos polinómicos, 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}.\,}$

Fijemos los números enteros y sea un 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 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 polinomial con , y 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 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 de código 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 en realidad un código lineal , es decir, las combinaciones lineales de palabras de código son a su vez 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 polinomial sobre con longitud de código y polinomio generador de grado , habrá exactamente palabras de código. De hecho, por definición, es una palabra de código si y solo 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 (sin codificar) 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 & 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 de código válida. Sin embargo, hay una palabra de código única que se puede obtener ajustando los símbolos más a la derecha de . Para calcularla, calcule 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 de código válida. ${\displaystyle g(x)}$ ${\displaystyle p(x)}$
2. Como es de grado menor que , los símbolos más a la izquierda de 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 comprobación o bits de comprobación . ${\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 manera sencilla mediante la división polinomial por el polinomio generador dando como resultado un resto distinto de cero.

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

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

Propiedades de los códigos polinómicos

Al igual que ocurre con todos los códigos digitales, la capacidad de detección y corrección de errores de los códigos polinómicos está determinada por la distancia mínima de Hamming del código. Como los códigos polinómicos 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 dichas propiedades:

• Un código polinomial es cíclico si y sólo si el polinomio generador divide a . ${\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 , se elige que el polinomio generador 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 polinómicos, con polinomios generadores elegidos inteligentemente, también se puede aprovechar a menudo para encontrar algoritmos de corrección de errores eficientes. 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 polinomial; un ejemplo popular es el código CRC .
• Códigos BCH : una familia de códigos cíclicos con alta distancia de Hamming y algoritmos eficientes de corrección de errores algebraicos.
• 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 , 2.ª edición, Wiley, 2004.
• R. Lidl y G. Pilz. Álgebra abstracta aplicada, 2.ª edición. Wiley, 1999.