Quizá os preguntais para que sirve esto. La división de polinomios se utiliza por ejemplo para calcular el CRC. Hay diversos CRC normalizados (y nosotros podemos usar el que nos de la gana). Por ejemplo la forma correcta de enviar un dato a través de un socket es enviarlo con su crc para que el receptor pueda comprobar la integridad de la información recibida. También por ejemplo las imágenes se almacenan en formatos que comprimen la información y suelen contener CRC. También lor programas de compresión, etc. En realidad los estais usando todo el día en todas partes sin saberlo y en programación a veces al ver como funciona algo te encuentras con este problema del CRC para el cual hay que entender como se dividen polinomios.
Bien, aquí tenis una rutina genérica que sirve para dividir dos polinomios cualesquiera y que en otro capítulo utilizaré para calcular CRC.
Y cuando haya quedado explicado eso lo utilizaré para dos cosas
1. Para que cada vez que envío una información a otra máquina vaya con su CRC y la máquina receptora pueda comprobar la integridad del mensaje
2. Para almacenar datos binarios que lleven su propia autentificación y eviten errores
3. Me meteré en un archivo PNG, extraeré los datos e insertaré algún mensaje oculto en la imagen de tal forma que nadie vea diferencia alguna entre dos imágenes aparentemente iguales, pero una de ellas contendrá un mensaje oculto
Pero eso mas adelante. Ahora me conformo con que se entienda la división de polinomios.
Seguramente quien se enfrenta a este problema sabe ya lo que es esto, pero explicaré algunos fundamentos básicos:
Algunos algoritmos de compresión o de comprobación requieren dividir dos polinomios. Para ello hay que entender que cualquier código binario (unos y ceros) puede ser visto como un polinomio de esta forma
Binario Decimal Polinomio Grado del Polinomio
101 5 1*X² + 0*X¹ + 1*X° = x²+1 2
101010 42 1*X+0*X+1*X³+0*x²+1*X¹+0*x° 5
De manera que utilizando este sistema se puede reducir un polinomio a unos y ceros o viceversa y aplicar a ese código binario reglas matemáticas que sirven para comprimir datos o asegurar su transmisión, etc.
¿Como se hace para dividir un polinomio?
Existen varios métodos. Yo utilizo aquí uno de ellos, pero los demás son tan buenos como este.
¿Como hacemos esto en una aplicación?
Tomemos como ejemplo que quiero dividir el polinomio: x6 + x5 + x3 + 1
Quiero dividirlo entre x4 + x + 1
Primer paso: reducir los polinomios a su valor binario:
Dividendo: 1101001
Divisor: 10011
Segundo paso: obtener el grado del polinomio divisor
Si conozco el polinomio original vel x osea que el grado es 4.
Lo que pasa es que cuando estamos leyendo un ficheor binario no tenemos ese dato y tendríamos que calcularlo. No es necesario porque basta con saber que si el divisor tiene cinco dígitos el grado es 4. El grado siempre es longitud-1
Así que ya sabemos de una forma u otra
dividendo: 1101001
divisor: 10011
Grado divisor: 4
Paso 3: Multiplicar el dividendo
Multiplicamos el dividendo por el grado del divisor. Esto significa meter por la derecha N ceros siendo N el grado del divisor.
Así que ahora tenemos
dividendo: 11010010000 (equivalente a x^10 + x^9 + x^7 + x^4)
divisor: 10011
Grado: 4
Realizar la división con papel y lápiz
donde pongo almohadilla debería haber espacios. Es que en el foro me quita los espacios y no se ve a que altura pongo el divisor
11010010000
11011
------------------- 'realizar la primera división. Hacemos XOR entre los bits correspondientes y el resto se arrastran
01001010000 'este es el resto obtenido que tenemos que volver a dividir pero corriendo el divisor uno a la derecha
#11011
------------------- ' realizar segunda división y quedarnos con el resto. Igual que antes
00000110000 'este es el resto obtenido que tenemos que volver a dividir corriendo el divisor uno a la derecha
##11011
------------------- 'aquí se da el caso que el primer bit del dividendo que tengo que hacer xor vale 0. Podría haber ocurrido
antes pero ocurre ahora. Cuando eso pasa no hago xor y solo corro uno a la derecha
00000110000
###11011
------------------- 'aquí vuelve a pasar. El primer bit a hacer xor del dividendo vale cero así que vuelvo a correr a la derecha
00000110000
####11011
------------------- 'aquí vuelve a pasar. Vuelvo a correr a la derecha sin hacer nada mas
00000110000
#####11011
------------------- 'y vuelve a pasar así que vuelvo a correr a la derecha
00000110000
######11011
------------------- 'y vuelve a pasar así que vuelvo a correr
00000110000
#######11011
------------------- 'el bit del dividendo es uno así que hago xor bit a bit
00000000110
Y ahora la siguiente división sería esta
00000000110
########11011
--------------------
pero no la hago porque llego al final. Es decir tengo que parar de hacer cocientes cuando llego al final y el resultado de la división es 110 que equivale a x²+x
El algoritmo en Gambas
Para usarlo en un form basta con incluir la clase y luego hacer algo como esto:
Esta es la función principal.
División es un código binario lleno de unos y ceros, pero lo he leído de un archivo como string porque no me interesa tener fronteras de bytes sino únicamente la colección de bits con su valor.
El polinomio divisor si es una colección de bytes. La razón es que suelen leerse como binarios al leer el archivo.
PUBLIC FUNCTION CalcularDivision(texto AS String, Polinomio AS string) AS String
DIM GradoPolinomio AS Integer,Resto AS String
Polinomio = QuitarCerosPolinomio(Polinomio) 'quitar al polinomio ceros no significativos
GradoPolinomio = ObtenerGradoPolinomio(Polinomio) 'Obtener el grado del polinomio generador
Texto = AgregarCeros(texto, GradoPolinomio) 'Agregar ceros a mensaje a la derecha
resto = DividirModuloDos(texto, Polinomio) 'efectuar división binaria
RETURN resto
END
DIM GradoPolinomio AS Integer,Resto AS String
Polinomio = QuitarCerosPolinomio(Polinomio) 'quitar al polinomio ceros no significativos
GradoPolinomio = ObtenerGradoPolinomio(Polinomio) 'Obtener el grado del polinomio generador
Texto = AgregarCeros(texto, GradoPolinomio) 'Agregar ceros a mensaje a la derecha
resto = DividirModuloDos(texto, Polinomio) 'efectuar división binaria
RETURN resto
END
Osea que yo cojo primero los dos parámetros. Si he recibido un polinomio divisor como este: 00000101 podría confundirme con su grado. Debo quitarle los ceros no significativos a su izquierda para que luego obtenga su grado correctamente.
Mas abajo están las funciones que lo hacen
Una vez hecho esto obtengo el grado del polinomio. Hay una función mas abajo que lo hace.
Una vez hago esto agrego N ceros al dividendo donde N es el grado del polinomio.
Una vez hago esto realizo la división y me quedo con el resto.
'función que realiza la división entera de dos polinomios
' parámetros de entrada:
' Dividendo --> polinomio a dividir
' Divisor --> polinomio divisor
' Salida:
' El resto de la división
PRIVATE FUNCTION DividirModuloDos(Dividendo AS String, Divisor AS String) AS String
DIM PosIni AS Integer 'en un string de bytes posini indica el primer bit que debe ser xoreado si toca hacerlo
DIM Resto AS String = dividendo
FOR PosIni = 1 TO Len(divisor) + 1 'numero de cocientes a realizar
IF Mid(Resto, PosIni, 1) = "1" THEN 'Si el primer dígito a operar es 1 y por tanto hay que hacer xor
resto = hacerxor(resto, divisor, posini) 'Hacer XOR a bits correspondientes y obtener el resultado
ENDIF
NEXT 'ir a siguiente bit que tendrá que ser operado para xor si corresponde
RETURN resto 'devolver el resto de la división
END
' parámetros de entrada:
' Dividendo --> polinomio a dividir
' Divisor --> polinomio divisor
' Salida:
' El resto de la división
PRIVATE FUNCTION DividirModuloDos(Dividendo AS String, Divisor AS String) AS String
DIM PosIni AS Integer 'en un string de bytes posini indica el primer bit que debe ser xoreado si toca hacerlo
DIM Resto AS String = dividendo
FOR PosIni = 1 TO Len(divisor) + 1 'numero de cocientes a realizar
IF Mid(Resto, PosIni, 1) = "1" THEN 'Si el primer dígito a operar es 1 y por tanto hay que hacer xor
resto = hacerxor(resto, divisor, posini) 'Hacer XOR a bits correspondientes y obtener el resultado
ENDIF
NEXT 'ir a siguiente bit que tendrá que ser operado para xor si corresponde
RETURN resto 'devolver el resto de la división
END
Esta es la función que realiza la división. Para ello hace un bucle donde va moviendo la posición inicial del divisor (posini) y va obteniendo el resto correspondiente. Mira a ver si el primer bit del dividendo es 0 o 1. Si es 1 hay que hacer xor. Si no lo es no hay que hacerlo.
Esta es la función que realiza el xor bit a bit si hay que hacerlo
'función que realiza xor de GradoPolinomio bits en los datos a partir del bit indicado en PosIni
PRIVATE FUNCTION hacerxor(r AS String, d AS String, PosIni AS Integer) AS String
DIM contador AS Integer, s AS String 's=resultado de la operación tras el xor
s = Left(r, PosIni - 1) 'quedarme con los bits que no voy a Xorear
FOR contador = 1 TO Len(d) 'recorrer los bits a operar
s &= CByte(Mid(r, contador + posini - 1, 1)) XOR CByte(Mid(d, contador, 1)) 'obtener bit xoread
NEXT
s &= Mid(r, contador + posini - 1) 'añadir valores no operados al resultado
RETURN s
END
DIM contador AS Integer, s AS String 's=resultado de la operación tras el xor
s = Left(r, PosIni - 1) 'quedarme con los bits que no voy a Xorear
FOR contador = 1 TO Len(d) 'recorrer los bits a operar
s &= CByte(Mid(r, contador + posini - 1, 1)) XOR CByte(Mid(d, contador, 1)) 'obtener bit xoread
NEXT
s &= Mid(r, contador + posini - 1) 'añadir valores no operados al resultado
RETURN s
END
cbyte lo que hace es convertir a byte un valor string. Por eso yo extraigo el valor que quiero, lo convierto a bit y hago el xor.
Al final añado los bits que no he xoreado y que arrastro de antes
'Función que multiplica un polinomio. Agrega GradoPolinomio ceros por la derecha al dividendo
Esta es la función que recibe un polinomio y devuelve su grado. El bit mas significativo debe ser uno y habría que haber quitado los ceros no significativos antes
Y esta es la función que recibe un polinomio y le quita los ceros no significativos
' función que recibe un polinomio y le quita los ceros no significativos
