Portal    Foro    Buscar    FAQ    Registrarse    Conectarse


Publicar nuevo tema  Responder al tema 
Página 1 de 1
 
 
División De Polinomios En Módulo 2 En Gambas
Autor Mensaje
Responder citando   Descargar mensaje  
Mensaje División De Polinomios En Módulo 2 En Gambas 
 
Hola

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.

5ae224e6a849c00453ec5d1cafc5aa7c

¿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:
private sub form_open()
dim a as string="1101001"
dim b as string="11011"
dim Resultado as string
Resultado=Polinomio.CalcularDivision(a,b)
end


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
 

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
 

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

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
PRIVATE FUNCTION AgregarCeros(Dividendo AS String, Grado AS Integer) AS String
  
  Dividendo &= String(Grado, "0")
  RETURN Dividendo
END


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
'Función que obtiene el grado de un polinomio. El bit mas significativo es 1.
PRIVATE FUNCTION ObtenerGradoPolinomio(p AS String) AS Integer
  RETURN Len(p) - 1
END


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
PRIVATE FUNCTION QuitarCerosPolinomio(p AS String) AS String  
  p = Mid(p, InStr(p, "1"))
  RETURN p  
END

 



 
última edición por soplo el Martes, 16 Febrero 2010, 20:13; editado 4 veces 
soplo - Ver perfil del usuarioEnviar mensaje privado 
Volver arribaPágina inferior
Responder citando   Descargar mensaje  
Mensaje Re: División De Polinomios En Módulo 2 En Gambas 
 
Que tema interesante. ¡Muchas gracias por darlo a conocer!
Saludos
 



 
abarzuaf - Ver perfil del usuarioEnviar mensaje privado 
Volver arribaPágina inferior
Mostrar mensajes anteriores:    
 
Ocultar¡Este tema fue útil?

 

Elegir valoración:                       

Media de valoración Valoración mínima Valoración máxima Número de valoraciones
10.00 10 10 2
 
OcultarTemas parecidos
Tema Autor Foro Respuestas último mensaje
No hay nuevos mensajes Módulo Y Clase tonixs Controles/Librerías/Componentes 4 Martes, 29 May 2012, 09:37 Ver último mensaje
Shell
No hay nuevos mensajes VSplit1 Mover División Por Código v3ctor Controles/Librerías/Componentes 2 Domingo, 21 Junio 2015, 22:00 Ver último mensaje
v3ctor
No hay nuevos mensajes Hacer Una... Radiografía De Un Módulo O ... vuott General 9 Martes, 25 Octobre 2016, 12:13 Ver último mensaje
Shell
No hay nuevos mensajes Módulo De Inicio tincho Aplicaciones/Fragmentos de Código 10 Lunes, 29 Octobre 2018, 14:40 Ver último mensaje
tincho
 

Publicar nuevo tema  Responder al tema  Página 1 de 1
 

Usuarios navegando en este tema: 0 registrados, 0 ocultos y 1 invitado
Usuarios registrados conectados: Ninguno


 
Lista de permisos
No puede crear mensajes
No puede responder temas
No puede editar sus mensajes
No puede borrar sus mensajes
No puede votar en encuestas
No puede adjuntar archivos
No puede descargar archivos
No puede publicar eventos en el calendario