¿Cuál es la más pequeña y más simple de la semilla para un generador de números aleatorios?

Question

Un pequeño microcontrolador (8 bits de Atmel) controla un número de luces para presentar un espectáculo de luz con muchos de fantasía aleatorizado secuencias de luces.

Un adecuado pseudo-RNG hace su trabajo muy bien, pero estoy buscando una buena semilla. Una semilla que va a ser necesario porque si alguien se da múltiples dispositivos al mismo tiempo, no se verá bien si todos ellos generan las mismas secuencias de efectos hasta que poco a poco se separen debido a las pequeñas diferencias en sus fuentes de reloj.

Un método muy bueno para la semilla de un pseudo-RNG, que me utiliza a menudo, es posible en el caso de un dispositivo que tiene que empezar con la prensa de un botón o accionar un interruptor. Tan pronto como el µc está encendida, un muy rápido temporizador puede ser iniciado, y el valor de este temporizador semillas de la RNG tan pronto como se pulsa el botón por primera vez.

El problema es que, en este escenario, no hay botones. El programa debe comenzar tan pronto como se enciende el dispositivo.

El lugar en el PCB es muy limitada (nada más que un par de los más pequeños de componentes SMD podría encajar), así que estoy buscando la más pequeña y más simple posible solución. Por lo tanto, voy a descartar de lujo soluciones como verdadero generador de números aleatorios por hardware, receptores de radio, etc.

Todo lo que tengo es de 16 bit de temporizador-contador de la CPU, y un sin usar portpin que tiene acceso a un ADC.

Mi solución actual es usar un resistor (como imprecisa como sea posible) para proporcionar aproximadamente la mitad de la tensión de alimentación para el ADC pin, y la semilla del generador de números aleatorios con el primer ANUNCIO, el valor de conversión. Sin embargo, hoy en día más del 10% de resistencias tienen una inexactitud, bien por debajo del 1% (que sería divertido imaginar la cara de un proveedor cuando les digo queremos que la peor calidad resistencias SMD pueden encontrar), así que hay una probabilidad muy alta de múltiples unidades de partida con la misma semilla.

Una mejor alternativa sería realizar múltiples conversiones y construir un valor fuera de los bits menos significativos de estas mediciones. Sin embargo, he utilizado el ADC de este µc tipo antes y sé que es muy precisa. Ejecuta el ADC a la mayor velocidad posible podría ser de ayuda aquí.

¿Alguien tiene una idea mejor? La semilla no es necesario ser perfectamente distribuidos de manera uniforme, pero cuanto más uniforme es la distribución es, el mejor. De 16 bits de la semilla con una perfecta distribución uniforme sería un sueño demasiado bueno para ser verdad, pero creo que un medio decente de distribución de más de 5 o 6 bits puede ser suficiente.

Answer 1

Poner en paralelo una resistencia y un condensador entre el A/D pin y la tierra. Hacer que la resistencia bastante alta, preferiblemente por encima de la señal de entrada impedancia requisito para el a/D. Hacer que la constante de tiempo RC tal vez alrededor de 10 µs. Por ejemplo, 100 kΩ y 100 pF suena como una buena combinación.

Para obtener un valor con un poco de aleatoriedad, de la unidad de la clavija en alto por un tiempo, entonces el conjunto es de alta impedancia y tomar un A/D de la lectura de un par de µs más tarde. Particularmente si bien el abuso de la A/D tiempo de la adquisición, la tensión va a ver va a ser dependiente de la R y los valores de C, el pin de la corriente de fuga, otros cerca de ruido y la temperatura.

Coge la baja de bits o de los dos bits bajos y repita según sea necesario para obtener cualquier número de bits aleatorios.

Para un diseño más aleatorio, de realizar este procedimiento de vez en cuando y inyectar bits baja del A/D resultado en el generador de números aleatorios que ya están en uso.

Answer 2

Algunas de las opciones posibles:

1. Pre-programa de una única serie de direcciones para cada dispositivo. Si usted tiene un buen algoritmo generador de números aleatorios, entonces incluso una lista secuencial de una serie de direcciones de producir resultados diferentes resultados.

2. Dependiendo de su MCU/setup, usted puede tener dos diferentes fuentes de reloj disponibles para el reloj del sistema y el watchdog timer/temporizador contador de entrada. Si uno o ambos de estos han variación significativa, usted puede usar esto para generar una adecuada semilla diferente. Aquí hay un ejemplo que me escribió el cual se utiliza un Arduino interno del temporizador de vigilancia y externa de una XTAL de reloj del sistema.

3. El uso de un transistor BJT y construir un altamente dependiente de la beta del amplificador. Esto se puede leer de un ADC para la semilla.

4. Condensadores/inductores se especifican normalmente en mucho peor tolerancia de las resistencias. Usted podría construir algún tipo de circuito de filtro (RC, RL, LC) con estas y medir la salida con el ADC.

Answer 3

La memoria no inicializada

Usted podría tratar de usar la memoria no inicializada en el micro controlador. El truco es encontrar los bits que tienen la mayoría de los 'equilibrada' flip-flops, y son realmente aleatorios. El procedimiento es leer toda la memoria, reset y repetir un par de veces a medida que los bits son realmente aleatorios. A continuación, utilice este mapa para leer lo suficiente de bits aleatorios para la semilla de su PRNG o LFSR!

Este método debe dar semillas aleatorias, incluso con idéntico hardware, más detalles (y enlaces) están disponibles en este hack-a-day artículo

Me gusta este método porque no requiere de circuitos adicionales o alfileres; el AVR ya ha ram, usted sólo tiene que encontrar el inestable (al azar) bits. También el procedimiento de asignación podría ser automatizado; se puede aplicar el mismo código y el procedimiento de cada dispositivo, y tienen resultados verdaderamente aleatorios!

Answer 4

Lo que hice para un reproductor de MP3 con el azar que es la capacidad de usar un secuenciales diferentes semillas en cada encendido. Me comenzó a la 1 y almacena esta en la EEPROM para que mes siguiente ciclo de potencia usé 2 etc. Esto fue en un ATMEGA168. Como helloworld922 observó incluso una simple secuencial de semillas generará completamente diferente pseudo aleatoria de secuencias.

He utilizado uno de los lineales de congruencia de secuencia aleatoria de los generadores, esto da una distribución uniforme.

int i;
seed = seed * 2053 + 13849;
i = (seed % max) + 1;  // max is the maximum value I want out of the function

Por supuesto, si quieres múltiples unidades tienen diferentes secuencias, incluso a pesar de que puede haber tenido el mismo número de ciclos de potencia, entonces usted necesita algo para empezar al azar.

Esto puede ser hecho por cualquiera de los métodos propuestos por los otros posters - Un método que puedo pensar de que podría utilizar el adaptador de CA cruce por cero de entrar en el procesador, si lo tiene (para lámpara de control de fase, por ejemplo)? Esto podría ser utilizado para muestra el temporizador en el primer cruce siguiente de encendido y, a continuación, utiliza como semilla.

Hay botones de presión en la unidad para seleccionar el modo de etc? Si es así, puede muestra el contador de la primera vez que pulse el botón después de que el MCU está programado puede generar una semilla aleatoria inicialmente y almacenarlo en la memoria EEPROM. Todos los Power-up después de este punto la usan semilla.

Answer 5

Un ADC es una muy buena fuente de aleatoriedad.

Usted no necesita depender de la resistencia de las tolerancias. Cualquier resistencia generará ruido térmico, y el mismo efecto de introducir ruido en el ADC cuando haciendo todo el muestreo y conversión de medidas. (La hoja de datos le dirán acerca de la cantidad de ruido, y qué opciones de configuración son peores/mejores.)

Usted no debe salir de la ADC pin flotante; esto puede permitir que el voltaje de flotación demasiado lejos, y los riesgos de la saturación de la entrada.
(Muchos de los Mcu de permitir el uso de algo así como la mitad de la tensión de alimentación como de la entrada del ADC, para la calibración. Esto ahorra la resistencia externa, y aún le da ruido. De nuevo, consulte la hoja de datos para el peor/mejor de configuración.)

Usted no necesita depender de un solo ADC de medición; se pueden combinar múltiples mediciones con un simple hash o función de suma de comprobación (CRC sería suficiente). Si usted necesita para empezar a utilizar el generador de números aleatorios de inmediato, usted puede combinar el ADC con el resultado actual de la semilla del generador de números aleatorios.