Luces de Belén mediante un generador de números verdaderamente aleatorios 
Para la generación de números aleatorios en circuitos digitales existen, principalmente, dos opciones: por un lado el uso de LFSRs (registros de desplazamiento con realimentación lineal) de ciclo maximal, que son circuitos deterministas con los que se obtienen números pseudoaleatorios, y, por otro lado, el uso de algún parámetro físico que realmente tenga un comportamiento ruidoso y nos permita extraer números de él, algo que no sea determinista. La primera opción es la que he utilizado siempre hasta ahora pero con la excusa del montaje del Belén de este año, se propone la implementación de un generador de números "verdaderamente" aleatorios (TRNG) para generar el brillo del firmamento del Belén. El resultado visual es el de siempre, la diferencia es que la secuencia de brillos es realmente aleatoria.

Objetivo

La idea es la misma de años anteriores: generar destellos aleatorios en un firmamento artificial hecho de Leds blancos para el montaje del Belén. Debido a que la secuencia de destellos no tiene por qué ser "realmente" aleatoria, hasta ahora nos bastaba con un generador de números pseudoaleatorios implementado con un LFSR de ciclo maximal (un puñado de biestables y una función de transición basada en dos o tres puertas lógicas, poco más).

Los LFSRs son, por definición, deterministas, no existe ninguna "magia" en ellos, lo que sucede es que la secuencia de números que generan es lo suficientemente "extraña" y aparentemente no determinista, como para que, a ojos de un observador humano, parezca que realmente se están generando números totalmente aleatorios. En este post se hace una introducción y una explicación muy completa sobre el fundamento, uso e implementación de LFSRs en circuitos digitales.

Buscar una fuente de ruido

En nuestro caso, si queremos generar números verdaderamente aleatorios, debemos buscar una fuente de ruido físico que podamos traducir en una secuencia de números (o, al menos, en una secuencia aleatoria de 0s y 1s). Una primera aproximación electrónica podría ser implementar un ADC y leer mediante ese ADC alguna fuente de ruido electrónico analógico.

Una buena opción en este sentido es aprovechar la característica de ruido de que se produce de forma natural en los transistores de unión cuando se polariza la unión base-emisor de forma inversa, dejando el colector al aire.



Esta características de los transistores de unión es bien conocida y muy usada en generadores de ruido analógicos, ya que el ruido que genera se asemeja mucho al ruido blanco y no requiere una excesiva calibración.

En el caso de que necesitemos generar números aleatorios de esta manera debemos colocar un ADC para leer el ruido que genere el transistor y ya tendríamos nuestro TRNG. Esta aproximación es correcta pero engorrosa y costosa por las siguientes razones:

- Requiere de circuitería analógica: no siempre podremos disponer de ella y es algo más delicada siempre a la hora de diseñarla, calibrarla y testearla.

- Requiere de un ADC: Los ADCs son recursos caros, incluso aunque los implementemos en forma de delta-sigma, consumen recursos y siempre requieren de una parte de electrónica analógica que, como se comentó antes, requiere más calibración, testeo y cuidado en el diseño.

La pregunta que surge es ¿Habría posibilidad de encontrar una fuente de ruido dentro de un circuito digital de tal forma que nos permita implementar un TRNG directamente en una FPGA o en un ASIC? Lo cierto es que sí y no es nada complicado.

Oscilador en anillo

Un oscilador en anillo es un tipo especial de oscilador digital formado por un bucle cerrado de una cantidad impar de inversores.



Como se puede comprobar, al haber una cantidad impar de inversores, el circuito será aestable y la oscilación que se genera (en cualquiera de sus inversores) tendrá una frecuencia inversamente proporcional a la suma de los tiempos de propagación de todas las puertas inversoras. Hasta aquí parece un oscilador más, pero lo cierto es que, al ser un oscilador no sintonizado (no se utiliza un cristal de cuarzo para mantener una frecuencia estable, como los osciladores "reales" que se utilizan habitualmente en los circuitos digitales) la frecuencia y ciclo de trabajo dependerá del tiempo de propagación de las puertas lógicas y este tiempo de propagación nunca es fijo, dependerá de:

- La tecnología de fabricación.

- La distancia en el sustrato que haya entre la salida de una puerta y la entrada de la puerta siguiente.

- Las impurezas en el sustrato (siempre las hay).

- La temperatura.

- Radiación electromagnética externa que afecte al circuito.



Por eso los fabricantes de circuitos digitales nunca dan un tiempo exacto de propagación de puerta, dan un rango (para un rango determinado de temperatura y de condiciones determinadas). Es este jittering (desplazamiento de fase y/o de frecuencia) que se produce en estos osciladores lo que podemos aprovechar como fuente de ruido.

Extraer el ruido de jittering

Si definimos dos o más osciladores en anillo "teóricamente" iguales (por ejemplo con la misma cantidad de puertas y aunque compartan sustrato, en la misma FPGA o ASIC), lo cierto es que acabarán desfasándose unos con otros de forma aleatoria debido a las razones anteriormente citadas. En el paper An embedded true random number generator for FPGAs (Kohlbrenner P. y Gaj K., 2004) se introduce esta técnica y se plantea un circuito auxiliar muestrador que permite obtener una secuencia de bits muy próxima a una distribución uniforme (ruido blanco). Yo he simplificado mucho dicho muestreador: no genera una secuencia de distribución uniforme pero para el caso que nos ocupa cumple su cometido correctamente ya que lo único que hago es muestrear la función XOR entre la salida de ambos osciladores en anillo y meter el bit resultante en un registro de desplazamiento.



El código VHDL asociado sería el siguiente:

library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity Max1000TRNG is
    port  (
        ClkIn : in std_logic;
        Led1Out : out std_logic;
        Led2Out : out std_logic;
        Led3Out : out std_logic;
        Led4Out : out std_logic;
        Led5Out : out std_logic;
        Led6Out : out std_logic;
        Led7Out : out std_logic;
        Led8Out : out std_logic;
        Star1Out : out std_logic;
        Star2Out : out std_logic;
        Star3Out : out std_logic;
        Star4Out : out std_logic;
        Star5Out : out std_logic;
        Star6Out : out std_logic;
        Star7Out : out std_logic;
        Star8Out : out std_logic
    );
end entity;

architecture A of Max1000TRNG is
    signal CounterD : std_logic_vector(23 downto 0);
    signal CounterQ : std_logic_vector(23 downto 0);
    signal FreeOsc1A : std_logic;
    signal FreeOsc1B : std_logic;
    signal FreeOsc1C : std_logic;
    signal FreeOsc1D : std_logic;
    signal FreeOsc1E : std_logic;
    signal FreeOsc2A : std_logic;
    signal FreeOsc2B : std_logic;
    signal FreeOsc2C : std_logic;
    signal FreeOsc2D : std_logic;
    signal FreeOsc2E : std_logic;
    attribute keep : boolean;
    attribute keep of FreeOsc1A : signal is true;
    attribute keep of FreeOsc1B : signal is true;
    attribute keep of FreeOsc1C : signal is true;
    attribute keep of FreeOsc1D : signal is true;
    attribute keep of FreeOsc1E : signal is true;
    attribute keep of FreeOsc2A : signal is true;
    attribute keep of FreeOsc2B : signal is true;
    attribute keep of FreeOsc2C : signal is true;
    attribute keep of FreeOsc2D : signal is true;
    attribute keep of FreeOsc2E : signal is true;
    signal RandomD : std_logic_vector(7 downto 0);
    signal RandomQ : std_logic_vector(7 downto 0);
    signal LatchD : std_logic_vector(7 downto 0);
    signal LatchQ : std_logic_vector(7 downto 0);
begin
    process (ClkIn)
    begin
        if (ClkIn'event and (ClkIn = '1')) then
            CounterQ <= CounterD;
            RandomQ <= RandomD;
            LatchQ <= LatchD;
        end if;
    end process;

    -- free oscillator 1
    FreeOsc1A <= not(FreeOsc1E);
    FreeOsc1B <= not(FreeOsc1A);
    FreeOsc1C <= not(FreeOsc1B);
    FreeOsc1D <= not(FreeOsc1C);
    FreeOsc1E <= not(FreeOsc1D);
    -- free oscillator 2
    FreeOsc2A <= not(FreeOsc2E);
    FreeOsc2B <= not(FreeOsc2A);
    FreeOsc2C <= not(FreeOsc2B);
    FreeOsc2D <= not(FreeOsc2C);
    FreeOsc2E <= not(FreeOsc2D);
    -- random bit generated from jittering between free oscillators
    RandomD <= RandomQ(6 downto 0) & (FreeOsc1A xor FreeOsc2A);
    -- latch the random number every time counter overflows
    CounterD <= std_logic_vector(unsigned(CounterQ) + 1);
    LatchD <= RandomQ when (CounterQ = std_logic_vector(to_unsigned(0, 24))) else
              LatchQ;
    Led1Out <= LatchQ(0);
    Led2Out <= LatchQ(1);
    Led3Out <= LatchQ(2);
    Led4Out <= LatchQ(3);
    Led5Out <= LatchQ(4);
    Led6Out <= LatchQ(5);
    Led7Out <= LatchQ(6);
    Led8Out <= LatchQ(7);
    Star1Out <= LatchQ(0);
    Star2Out <= LatchQ(1);
    Star3Out <= LatchQ(2);
    Star4Out <= LatchQ(3);
    Star5Out <= LatchQ(4);
    Star6Out <= LatchQ(5);
    Star7Out <= LatchQ(6);
    Star8Out <= LatchQ(7);
end architecture;

Nótese el uso de la palabra reservada "attribute" para definir un atributo booleano llamado "keep" asociado a las señales de los osciladores en anillo. Este atributo se utiliza para indicarle al entorno de desarrollo que no simplifique la función booleana y que mantenga ("keep") las señales indicadas, aunque al entorno le parezcan "desechables". Mediante este truco obligamos al entorno de desarrollo a implementar los osciladores en anillo con el número exacto de puertas que necesitamos.



Como siempre, el código fuente puede descargarse de la sección soft.

¡Feliz Navidad!

[ añadir comentario ] ( 2170 visualizaciones )   |  [ 0 trackbacks ]   |  enlace permanente
  |    |    |    |   ( 3 / 212 )

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Siguiente> >>