Brevet FR2871252A1 — publié le 20051209

Km KD Îcrr = faK TQ =KD'TCLK =KM'Tcra L'invention concerne un procédé pour générer des suites binaires aléatoires. Le problème que se propose de résoudre l'invention est de générer des suites binaires aléatoires vraies à partir du jitter relatif entre deux signaux d'horloge et de mesurer en temps réel les paramètres statistiques du jitter pour permettre d'évaluer la qualité de la suite aléatoire obtenue ou éventuellement pour signaler un défaut de fonctionnement. Selon l'état antérieur de la technique, on a proposé, pour générer les suites aléatoires dans des circuits logiques et en particulier dans des circuits logiques reconfigurables, d'utiliser un oscillateur libre relié à un ou plusieurs registres à décalage linéaire. On peut citer par exemple le brevet US 6,061,702. On peut citer également l'enseignement du brevet US 6,414,558 qui concerne l'utilisation d'un générateur de séquences aléatoires. On a proposé, par ailleurs, de générer des suites binaires aléatoires à partir du jitter, comme il ressort d'une publication faite par Viktor FISCHER et Milos DRUTAROVSKY ayant pour titre TRUE RANDOM NUMBER GENERATOR EMBEDDED IN RECONFIGURABLE HARDWARE du mois d'Août 2002. Selon cette publication, la qualité de la suite binaire aléatoire est mesurée par des méthodes statistique génériques pour tester le bon fonctionnement du générateur. Ce procédé de mesure statistique peut être appliqué en complément avec les caractéristiques de l'invention. La base du procédé est représentée sur le schéma bloc de la figure 1. Le procédé est basé sur l'utilisation de deux signaux d'horloge logiques CLJ et CLK liés par une relation de la forme: fcrr = fCLK KD Dans cette formule, le plus grand commun diviseur PGCD(KM,KD) =1. Les deux signaux peuvent être obtenus, par exemple, au moyen d'une ou plusieurs boucles à verrouillage de phase (phase-locked loop). Le signal logique de fréquence. est échantillonné dans un block REG (par exemple sous forme d'une bascule) sur le front montant ou descendant du signal de fréquence fcLK. Le block REG mémorise la valeur échantillonnée pendant une période d'horloge du signal CLK. A la sortie du bloc d'échantillonnage REG, le signal Q est statistiquement périodique de période: TQ = KD ' TCLK = KM ' Tcw Si le jitter relatif entre les signaux CLK et CLJ, caractérisé par la valeur o11 est supérieur à la valeur A, définie par la formule suivante 6 > Taj = TcLK = A " 4KD 4KM on obtient, à la sortie du bloc PAR, qui calcule la parité des KD échantillons successifs, une suite binaire aléatoire R. Cette inégalité représente la condition nécessaire au bon fonctionnement du générateur de suites aléatoires dont le débit est 1/TQ bits par seconde. Il est apparu toutefois que le jitter varie d'une manière importante en fonction de nombreux paramètres physiques tels que la tension d'alimentation, les bruits électriques de l'environnement, la température, ce qui peut modifier le fonctionnement du générateur. Il paraît donc important de mesurer les paramètres du jitter pour garantir la qualité des nombres aléatoires à la sortie du générateur. A partir de l'enseignement de cette publication, selon une caractéristique à la base de l'invention, on ajoute la possibilité de mesurer les paramètres du jitter. On propose donc le procédé représenté sur le schéma bloc dans la figure 2. D'abord, dans le bloc GEN VEC (générateur de vecteurs de KD bits), on effectue d'une manière répétitive pendant différentes périodes TQ l'acquisition des suites binaires SB composées de KD échantillons (bits). On obtient donc à la fin de chaque période TQ un vecteur VB. KM Ces vecteurs sont ensuite traités dans le bloc TRAIT VEC (traitement de vecteurs) pour évaluer les paramètres du jitter. A la base de l'information sur ces différents paramètres du jitter, on peut signaler un défaut de fonctionnement du générateur, par exemple au moyen d'un signal d'alarme. Autrement dit, le problème que se propose de résoudre l'invention est de mesurer les paramètres du jitter ce qui permet de garantir la qualité des nombres aléatoires pendant le temps où le signal d'alarme n'est pas actif. Selon une caractéristique à la base de l'invention: on enregistre dans des suites binaires SB KD échantillons successifs du signal CLJ (un bit par échantillon) obtenus pendant des périodes TQ différentes; on réordonne les bits de chaque suite SB en vecteur VB composé de KD bits selon la formule: j=(i KM)modKD où i représente l'index du bit dans la suite SB et j représente l'index du bit correspondant dans le vecteur VB; à partir de vecteurs VB, on évalue un ou plusieurs paramètres P du jitter suivant une méthode choisie; selon les valeurs des paramètres P on peut signaler le bon fonctionnement du 20 générateur par exemple au moyen d'un signal d'alarme. L'invention a été exposée ci-après plus en détail à l'aide des figures annexées dans lesquelles: la figure1 est une mise en oeuvre du procédé selon l'état antérieur de la technique 25 de génération des suites aléatoires sous forme d'un schéma bloc; la figure 2 est une mise en oeuvre du procédé selon l'invention, également sous forme d'un schéma bloc; la figure 3 est un exemple de relation entre le signal d'horloge CLK et le signal d'horloge CLJ, de l'ordonnancement de la suite SB pour obtenir le vecteur VB correspondant, ainsi que de la représentation graphique du vecteur VE obtenu -4-par l'accumulation de N vecteurs VB; Les échantillons (bits) du signal CLJ obtenus à la sortie Q du bloc REG pendant la période TQ forment la suite binaire SB. Ils représentent le signal CLJ dans des phases différentes. Pour reconstruire la forme du signal CLJ à partir de ces échantillons, il faut les réordonner. On renvoie par exemple à la figure 3 qui montre la relation entre le signal d'horloge CLK et le signal d'horloge CLJ pour KM = 5 et KD = 7 (fcW Si l'on considère la formule précédemment indiquée: j=(iÉKM)modKD on obtient: pour i=0, j=(0.5)mod7=0 pour i=1, j = (1. 5) mod 7 = 5 pour i = 2, j =(2.5)mod7 =3 pour i=3, j=(3.5)mod7=1 pour i=4, j = (4. 5) mod 7 = 6 pour i=5, j = (5.5) mod 7 = 4 pour i=6, j=(6.5)mod7=2 Les flèches dans la figure 3 indiquent la suite des opérations à mener pour obtenir le vecteur VB et le vecteur VE. Le vecteur VE présenté dans la figure 3 sous forme graphique est obtenu par l'accumulation de N = 100 vecteurs VB. Les valeurs ei (l'élément j du vecteur VE) qui ne sont pas influencées par le jitter sont égales soit à 100 soit à zéro. Les valeurs échantillonnées dans des zones d'incertitude ont une valeur différente. A partir de ces valeurs on peut caractériser le jitter. 20 Il existe plusieurs possibilités pour évaluer les caractéristiques du jitter à partir de vecteurs VB. On peut à titre d'exemple présenter trois méthodes différentes. La première méthode d'évaluation du jitter consiste à accumuler N vecteurs 5 binaires VB en un seul vecteur VE composé de KD valeurs entières comprises entre 0 et N, puis calculer le paramètre Pl à partir de la formule: KD-1 Pl = C E e (N eJ.) 1 j=0 où ej représente l'élément j du vecteur VE, C1 représente une constante de normalisation. Puisque les valeurs ej qui ne sont pas influencés par le jitter, sont égales soit à 0 soit à N, le terme e j (N ej) sera égal à zéro et ne contribuera pas à la valeur du paramètre P, . Seules les valeurs influencées par le jitter seront prises en compte. En conséquence, la valeur Pl est proportionnelle à la valeur crfit du jitter. Si elle est inférieure au seuil Pl,ef défini au préalable, le générateur ne fonctionne pas correctement et le signal d'alarme est activé. La deuxième méthode d'évaluation du jitter nécessite elle aussi l'accumulation de N vecteurs VB pour obtenir le vecteur VE, ensuite on calcule le paramètre Pl à partir de la formule: 1 KD I/ 1 P2 C2 Ee i=O I\ J où ej représente l'élément j du vecteur VE, C2 représente la constante de normalisation. Pour que les probabilités d'apparition des niveaux logiques 0 et 1 à la sortie du générateur soient identiques, le paramètre P2 doit être égal à zéro. Si sa valeur est positive, la probabilité du niveau 1 est plus élevée que celle du niveau 0. En conséquence, si la valeur absolue du paramètre P2 est inférieure au seuil P2Yef défini au préalable, le générateur ne fonctionne pas correctement et le signal d'alarme est activé. La troisième méthode permet d'évaluer les paramètres dynamiques du jitter, notamment la corrélation entre deux fronts montants ou descendant du signal CLJ. On réalise donc l'opération OU EXCLUSIF bit par bit entre deux vecteurs VB successifs pour obtenir le vecteur VD composé de KD valeurs binaires. La longueur de la suite de bits égaux à un dans ce vecteur VD est proportionnelle au déplacement du front montant ou descendant du signal CLJ par rapport au début de la période TQ. On peut donc mesurer la corrélation P3 entre les positions du front montant ou descendant du signal CLJ dans des périodes TQ successives. Si cette corrélation dépasse le seuil P3ref défini au préalable, le signal d'alarme est activé. 7 REVENDICATIONS - 1 - Procédé pour générer des suites binaires aléatoires à partir du jitter relatif entre deux 5 signaux d'horloge logiques CLK et CLJ liés par une relation de la forme: KM fa./ _ {' /CLK K D où le plus grand commun diviseur PGCD (KM,KD) =1, on échantillonne le signal logique de fréquence faj sur le front montant ou descendant de signal de fréquence fco, ; on mémorise la valeur échantillonnée pendant une période du signal CLK pour obtenir le signal Q; le signal Q est périodique de période: TQ = KD TCLK = KM ' Tcra caractérisé en ce qu' on calcule les paramètres du j itter au moyen de N vecteurs binaires VB acquis à partir du signal Q pendant N périodes TQ. - 2 - Procédé selon revendication 1, caractérisé en ce qu' on enregistre dans une suite binaire SB KD bits du signal Q obtenus pendant la 20 période TQ; on réordonne les bits de la suite SB en vecteur VB selon la formule: j=(i KM) modKD où i représente l'index du bit dans la suite SB et j représente l'index du bit correspondant dans le vecteur VB; - 3 Procédé selon revendication 1 et 2, caractérisé en ce qu' on accumule N vecteurs binaires VB en un seul vecteur VE composé de KD valeurs entières; à partir du vecteur VE on calcule le paramètre P, caractérisant la largeur du jitter, par exemple suivant la formule: KD-1 P=-E e. (N e.) l J J l j=0 où ej représente l'élément j du vecteur VE, Cl représente la constante de normalisation; on génère le signal d'alarme si la valeur du paramètre P, est inférieure au seuil Prej - 4 - Procédé selon revendication 1 et 2, caractérisé en ce qu' on accumule N vecteurs binaires VB en un seul vecteur VE composé de KD valeurs entières; - à partir du vecteur VE on calcule le paramètre P2 caractérisant la probabilité d'apparition de niveaux logiques zéro et un à la sortie du générateur, par exemple suivant la formule: 1 KD-1 P2 C2 E(e. N J où ej représente l'élément j du vecteur VE, C2 représente la constante de 15 normalisation; on génère le signal d'alarme si la valeur absolue du paramètre P2 est supérieure au seuil PZrej; - 5 - Procédé selon revendication 1 et 2, caractérisé en ce qu' - à partir de couples de vecteurs VB (N = 2) on calcule le paramètre P caractérisant la corrélation entre ces vecteurs, par exemple en effectuant l'opération OU EXCLUSIF entre leur bits; on génère le signal d'alarme si la valeur du paramètre P3 est supérieure au seuil P3rej; - 6 - Dispositif pour la mise en oeuvre du procédé selon l'une quelconque des revendications 1 à 5, caractérisé en ce qu'il comprend un bloc bascule assujetti aux deux signaux d'horloge CLK et CLJ et apte à assurer l'échantillonnage, un bloc apte à calculer la parité de KD échantillons du signal CLJ, un bloc apte à assurer l'enregistrement du signal Q pour former la suite SB et pour la transformer en vecteur VB et les blocs aptes à calculer les paramètres P, , P2 ou P3 et les comparer avec les -9-seuils prédéfinis pour générer le signal d'alarme.