En la teoría de la 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 cierta longitud fija) que son divisibles por un polinomio fijo dado (de menor longitud, llamado polinomio generador ).
Definición
Arreglar un campo finito , cuyos elementos llamamos símbolos . Con el fin de construir códigos polinomiales, identificamos una cadena de simbolos con el polinomio
Fijar enteros y deja ser 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.
Ejemplo
Considere el código polinomial sobre con , y polinomio generador . Este código consta de las siguientes palabras de código:
O escrito explícitamente:
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:
De manera equivalente, expresadas como cadenas de dígitos binarios, las palabras de código son:
Esto, como todo código polinomial, 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 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 , dónde (el cociente ) es de grado menor que. Puesto que haytales cocientes disponibles, hay el mismo número de posibles palabras de código. Por lo tanto, las palabras de datos simples (no codificadas) deben tener una longitud
Algunos autores, como (Lidl & Pilz, 1999), solo discuten 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.
En cambio, el siguiente método se usa a menudo para crear un código sistemático : dada una palabra de datos de longitud , primero multiplica por , que tiene el efecto de cambiar por lugares a 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 el extremo derecho símbolos de . Para calcularlo, calcule el resto de dividir por :
dónde es de grado menor que . La palabra de código correspondiente a la palabra de datos. entonces se define como
Tenga en cuenta las siguientes propiedades:
- , que es divisible por . En particular, es una palabra de código válida.
- Desde es de grado menor que , el más a la izquierda símbolos de de acuerdo con los símbolos correspondientes de . En otras palabras, la primeralos símbolos de la palabra de código son los mismos que los de la palabra de datos original. El restantelos símbolos se denominan dígitos de suma de comprobación o bits de comprobación .
Ejemplo
Para el código anterior con , y polinomio generador , obtenemos la siguiente asignación de palabras de datos a palabras de código:
- 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 una manera sencilla a través de la división de polinomios por el polinomio generador dando como resultado un resto distinto de cero.
Suponiendo que la palabra de código está libre de errores, un código sistemático se puede decodificar simplemente eliminando el dígitos de la suma de comprobación.
Si hay errores, se debe realizar la corrección de errores antes de la decodificación. Existen algoritmos de decodificación eficientes para códigos polinomiales específicos, como los códigos BCH .
Propiedades de los códigos polinomiales
Como para 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 una palabra de código distinta de cero con un solo conjunto de bits.
Las propiedades más específicas de un código polinomial a menudo dependen de propiedades algebraicas particulares de su polinomio generador. A continuación, se muestran algunos ejemplos de estas propiedades:
- Un código polinomial es cíclico si y solo si el polinomio generador se divide.
- Si el polinomio generador es primitivo , entonces el código resultante tiene una distancia de Hamming de al menos 3, siempre que.
- 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 logre una gran distancia de Hamming.
La naturaleza algebraica de los códigos polinomiales, con polinomios generadores elegidos inteligentemente, a menudo también se puede aprovechar 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 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 , 2da edición, Wiley, 2004.
- R. Lidl y G. Pilz. Álgebra abstracta aplicada, 2ª edición. Wiley, 1999.