martes, 21 de mayo de 2013

Generación de números aleatorios con PIC en ASM.

- Introducción -

La generación de numero aleatorios suele ser complicado mas cuando se programa en ensamblador ya que al hacerlo en un lenguaje de medio o alto nivel los mismos ya poseen funciones especificas para la tarea haciendo la programación mas fácil.

Ahora bien, ¿ que pasa cuando programamos en ansamblador ? Pues tendremos que crear nuestras propias funciones y aquí veremos como crear una de ellas.

  
- Aproximación -

Para generar números aleatorios se puede recurrir a numerosos procedimientos. Por ejemplo, Supongamos un dado electrónico en el que el usuario presiona un pulsador y, luego de la animación, aparece un valor aleatorio en el mismo. Una aproximación, sin cuidar demasiado la probabilidad de cada numero, es hacer correr el TMR0 (Temporizador), cuando el usuario presiona la tecla se lee el mismo y de ahí se calcula para terminar con un numero aleatorio entre 1 y 6 que sera luego lo que el dado mostrara.
En ese caso se cuenta con que el usuario no sabe en que numero esta el TMR0 y que presionara el pulsador de una manera aleatoria y no cada un tiempo especifico y preciso.

La aproximación funciona y haciendo un poco mas de trabajo podemos extraer un numero aleatorio. Ahora supongamos que el sistema tiene que mostrar cada 10 segundos un numero aleatorio. ¿ Serviría el método anterior ?
Veamos: digamos que son 10 números (1 al 10), el temporizador se incrementa cada 1 segundo por lo que tardara 10 segundos en rebalsar. Encendemos el sistema y el mismo, cuando lee el TMR0 este posee el numero 3.
Ahora el sistema espera 10 segundos y lee nuevamente el TMR0. Después de 10 segundos obviamente el TMR0 estará en 3. No muy aleatorio ¿ verdad ?  :lol:

Una solución para el problema anterior seria crear una tabla de números aleatorios. El problema es que si necesitamos 255 numero ocuparía muchísima memoria en el programa.

Para solucionar eso creamos nuestra función que nos devolverá un numero aleatorio. Para este caso también hay muchas maneras, la que usaremos ahora esta basada en el desplazamiento y en compuertas XOR. Este método, si se aplica correctamente, nos devolverá un numero aleatorio de longitud máxima. ¿Que significa de longitud máxima ? que no repetirá ningún numero y al final obtendremos 255 números aleatorios hasta que la secuencia vuelva a comenzar. Hay que aclarar que debido a lo ultimo este método genera números Pseudos-aleatorios.



- Código -

El método se basa en el siguiente diagrama:



Se aprecia que el sistema toma 2 grupos de 2 bits cada uno, realiza una operación XOR con cada grupo y el resultado de cada uno alimenta otra compuerta XOR. Por ultimo el resultado de esta ultima compuerta alimenta el bit de mayor peso luego de que toda la cadena haya sido desplazada a la derecha.
La condición esencial del circuito es que la cadena no puede comenzar con el numero 0. De suceder esto el sistema quedara en 0 indefinidamente. Por lo que, antes de empezar habrá que cargar la cadena con un valor cualquiera distinto de cero -muchas veces llamado este valor "semilla" ya que es el que alimenta/genera el resto de los números-

Como código termine con el siguiente -debería recordar karnaugh y ver si se puede reducir a algo mas fácil pero seguí con las compuertas XOR-

Random
              btfsc   Dato, 4
              incf     Conta, f
              btfsc   Dato, 3
              incf     Conta, f
              btfsc   Dato, 2
              incf     Conta, f
              btfsc   Dato, 0
              incf     Conta, f

              rrf       Conta, f
              rrf       Dato, f

              clrf     Conta
              return

Se preguntaran donde esta las operaciones XOR en el código. Es ahí donde radica un poco lo lindo del código:

Veamos como es la tabla de verdad de la compuerta XOR:

AB ----- Out
00 ------- 0
01 ------- 1
10 ------- 1
11 ------- 0

Ahora si observamos cual seria la salida de la compuerta que alimenta el registro de desplazamiento veremos algo curioso:

ABCD ---- Out ---- Cantidad de unos.
0000 ------ 0 ------------ 0
0001 ------ 1 ------------ 1
0010 ------ 1 ------------ 1
0011 ------ 0 ------------ 2
0100 ------ 1 ------------ 1
0101 ------ 0 ------------ 2
0110 ------ 0 ------------ 2
0111 ------ 1 ------------ 3
1000 ------ 1 ------------ 1
1001 ------ 0 ------------ 2
1010 ------ 0 ------------ 2
1011 ------ 1 ------------ 3
1100 ------ 0 ------------ 2
1101 ------ 1 ------------ 3
1110 ------ 1 ------------ 3
1111 ------ 0 ------------ 4

(Donde AB seria los bits 0 y 2 que alimentan una de las XOR, CD los bit 3 y 4 que alimentan otra de las compuertas XOR y por ultimo la salida es la que presenta la compuerta XOR que opera sobre los dos grupos mencionados anteriormente AB y CD)

Se ve que la salida de la tercera compuerta es alta solo cuando la cantidad de unos que alimentan las dos primeras compuertas es un numero impar. Por lo que solamente habrá que contar la cantidad de números 1 que aparecen en los 4 bit (bit 0, bit 2, bit 3 y bit 4), de ser impar alimentar la cadena con un 1 y en caso contrario con un 0. Todo esto obviamente luego de desplazar la cadena a la derecha.

- Conclusiones -

Cuando se inicializa el PIC habrá que cargar el registro "Dato" con algún numero distinto de 0 como explique anteriormente y luego de llamar la función esta cambiara el registro Dato con el nuevo valor aleatorio.

La función solo tarda 11 pulsos de reloj (si no contamos los 2 para llamar la función y los 2 para volver de la misma) con lo que es muy rápida.

2 comentarios:

  1. Respuestas
    1. Hola.

      Sinceramente no conozco un buen método o el correcto para hacerlo.

      Dependiendo de lo que quieras hacer mas específicamente se me ocurren algunas ideas.

      Si creas un arreglo con dos letras y otro con tres letras puedes luego indexarlas para crear palabras. Algunas quedaran sin significado pero que pueden llegar a ser correctas. Los arreglos no serian muchos ya que por ejemplo "NP" no esta permitido en el español ya que lo correcto es "MP". Luego creas dos números aleatorios, uno que usaras para elegir los trozos y otro para ver cuantos trozo compondrá la palabra.

      La otra forma que se me ocurre es tener un diccionario, al menos de las palabras mas usadas, e indexarlo con un puntero aleatorio.

      La otra es conseguir una cantidad infinita de monos que tecleen al azar y, con el tiempo adecuado, quizás logren escribir todas lo creado por el hombre en la historia. (Se pueden reemplazar los monos por micros XD).

      Saludos.

      Eliminar