Télécom Robotics

Générateur aléatoire

Il nous faut maintenant générer un facteur aléatoire compris en n et (n+Δn). Pour l'instant on le prendra uniformément distribué, mais il serait souhaitable dans la suite de modifier le générateur aléatoire pour compenser la dépendance des fréquences en 1/n...

Pour générer un nombre pseudo-aléatoire entre n et (n+Δn), on va le générer entre 0 et 1, on le multipliera par Δn, et on ajoutera n. C'est pour cela qu'on parle depuis le début de n et (n+Δn) et non pas de nmin et nmax...

La génération d'un nombre pseudo aléatoire compris en 0 et 1 sera fait au moyen d'un LFSR. Ce ne sont pas les meilleurs générateurs aléatoires (ce sont même presque les pires...), mais ils ont le mérite d'être faciles à implémenter, et extrêmement rapides. Il en existe deux formes :

• de Fibonacci, aussi appelée many-to-one, construite avec une grosse porte XOR
• de Galois, aussi appelée one-to-many, construite à l'aide de plusieurs XOR à 2 entrées.

Pour plus de précision sur les LFSR, on pourra se rapporter cette page de New Wave Instruments.

Pour nous, nous avons choisi un LFSR de Galois sur 32 bits à 16 taps, correspondant au polynôme générateur suivant : P=x^{32}+x^{31}+x^{28}+x^{27}+x^{24}+x^{23}+x^{20}+x^{19}+x^{18}+x^{15}+x^{12}+x^{11}+x^{8}+x^{7}+x^{3}+x^{2}+1  

Le code du LFSR est disponible ici.  

Le LFSR nous sort un nombre pseudo-aléatoire sur 32 bits. Il faut maintenant en extraire un nombre sur 11 bits (qui sera considéré comme la partie décimale de 0,xxx) et le multiplier par Δn (appelé period_range dans le code). On pourrait utiliser les multiplieurs intégrés aux Stratix, mais pour rester générique et rapide quel que soit le FPGA utilisé, nous implémentons le multiplieur à la main, à l'aide d'additions et de décalage successifs. La multiplication se fait alors en 12 cycles.

Pour cela, on utilise une machine à états basique :

• premier état (1 cycle) : on initialise toutes les variables, et on récupère le nombre aléatoire (r) du LFSR.
• deuxième état (12 cycles) : c'est la multiplication proprement dite. On additionne les puissances successives de r si elles sont présentes dans period_range, c'est-à-dire si le bit correspondant de period_range vaut '1'. On obtient ainsi un nombre compris entre 0 et Δn (vu la façon dont l'algorithme est implémenté, ce nombre est en fait compris entre 0 et Δn-11).
• troisième état (1 cycle) : on ajoute à ce nombre n (period_min). On obtient ainsi un nombre aléatoire compris entre n et n+Δn (period_min et period_min+period_range).

Le module réalisant cette fonction est appelé gene_aleatoire, et instancie le LFSR. Son code est disponible ici..