Brevet FR2600440A1 — publié le 19871224

-- i -CIRCUIT DE REGISTRES A DECALAGE A REBOUCLAGE LINEAIRE, A ARCHITECTURE SYSTOLIOUE La présente invention concerne un circuit de registres à décalage à rebouclage linéaire, propre à fournir, à des instants successifs, des échantillons numériques respectifs, dont chacun représente une combinaison linéaire d'échantillons numériques antérieurs et comprend M bits significatifs auxquels s'ajoutent éventuellement, en nombre X éventuellement nul, des bits d'extension de signe, ce circuit 10 comportant N cellules semblables dont chacune forme un chemin de circulation de bits comprenant, en série entre une entrée et une sortie principales de cette cellule, un registre amont contenant P bits, un opérateur de pondération, un opérateur de combinaison à deux entrées et un registre aval contenant Q 15 bits, la sortie du registre amont et l'une des deux entrées de l'opérateur de combinaison constituant respectivement une sortie et une entrée secondaires de la cellule, susceptibles d'être respectivement reliées à une entrée et à une sortie principales d'une cellule suivante du circuit, et la sortie principale de la première cellule étant rebouclée sur l'entrée principale de cette même cellule pour permettre la recirculation des échantillons numériques produits. Les circuits de registres à décalage à rebouclage linéaire, 25 plus connus sous le nom anglais de "Linear feedback shift registers" ou, en abrégé, "LFSR" sont utilisés depuis plusieurs années. Ces circuits ont pour fonction, à partir de N échantillons 30 numériques initiaux, par exemple Sl à SN, de produire de nouveaux échantillons numériques, notés par exemple Sj de façon générique et représentés chacun, pour j supérieur à N, par la combinaison linéaire: Sj=Ni=! ki.Sj-i, dans -2 laquelle les (ki) constituent un ensemble de N coefficients de pondération. La figure 1 représente, de façon schématique, un LFSR d'un premier type connu dans l'art antérieur. Ce LFSR, qui ne os présente pas toutes les caractéristiques énoncées dans le préambule, comporte des registres, par exemple RG1 à RG5, des opérateurs de pondération OP1 à OP5 constitués par exemple par des multiplieurs réalisant une multiplication par des coefficients constants kl à k5, et un opérateur de combinaison OC. Dans ce LFSR, les chemins de circulation de bits, représentés par de simples lignes, sont en réalité des chemins de circulation de bits en parallèle, et sont donc constitués chacun de plusieurs lignes parallèles. De même, les registres et les opérateurs sont des registres et des opérateurs fonctionnant en parallèle, c'est-à-dire agissant sur plusieurs bits à la fois. L'opérateur de combinaison OC, schématiquement représenté sous la forme d'un additionneur unique, n'a pas de réalité physique correspondant à cette forme. Un tel opérateur parallèle OC adopte en fait généralement la 25 forme d'une pyramide d'opérateurs triadiques élémentaires (à deux entrées et une sortie), comme représenté sur la figure 2. Supposons qu'à l'instant 0, les registres RG1 à RGN 30 contiennent les échantillons SN à S1. Au cours du premier cycle de fonctionnement, chaque échantillon numérique passe d'un registre au registre suivant et, simultanément, subit une pondération par l'opérateur OP relié à la sortie du registre dont il sort; les échantillons - 3 -2600440 --3 pondérés sont ensuite, tous en même temps, transmis à l'opérateur de combinaison OC. A la fin du cycle de fonctionnement, ce dernier, supposé constitué de l'additionneur parallèle classique de la figure 05 2, fournit donc un échantillon numérique: SN+1=ii=i ki.SN+l-i, qui est mémorisé dans le registre RG1. Un tel LFSR remplit donc bien la fonction attendue, consistant à fournir des échantillons numériques représentés par des combinaisons linéaires d'échantillons antérieurs. Cependant, compte tenu de la structure de son opérateur de combinaison OC, représenté figure 2, un LFSR de ce type n'est 15 pas susceptible d'être décrit comme un assemblage de N cellules semblables. Ce défaut de structure modulaire est un handicap pour la réalisation des LFSR de ce type sous la forme de circuits intégrés à très grande échelle (VLSI). En effet, la géométrie de l'implantation spatiale des opérateurs triadiques élémentaires constituant l'opérateur de combinaison OC, ainsi que le temps de transfert de cet opérateur, dépendent du nombre N de registres RG1, RG2.., RGN que comporte le 25 circuit. Cet inconvénient est écarté, de façon connue, par l'emploi d'une structure telle que celle du LFSR de la figure 3. Un tel circuit, bien que ne présentant pas non plus toutes les caractéristiques énoncées dans le préambule, laisse cependant déjà apparaître une structure modulaire, puisqu'il est formé de l'assemblage de N cellules semblables, portant les références Cl à CN. - 4 Chaque cellule forme un chemin de circulation de bits en parallèle comprenant, en série, un registre, tel que RG1 à RGN, un opérateur de pondération, tel que OP1 à OPN, et un opérateur de combinaison, tel que OC1 à OCN. Comme dans le LFSR de la figure 1, les regitres, et les opérateurs de pondération et de combinaison ont un fonctionnement parallèle, c'est-àdire que les lignes simples qui les relient les uns aux autres sur le schéma de la figure 3 sont en fait composées de M lignes parallèles, M étant le 10 nombre de bits que comporte chacun des échantillons numériques contenus dans les registres RG1 à RGN. Le LFSR de la figure 3 comprend un multiplexeur MX permettant de relier l'entrée du registre RG1 soit à une entrée E de ce 15 circuit LFSR, soit à la sortie de l'opérateur de combinaison OC1. En toute rigueur, un tel multiplexeur serait également nécessaire dans le LFSR de la figure 1, et son omission sur 20 cette figure ne visait qu'à en simplifier la compréhension. Pendant une phase d'initialisation, le multiplexeur MX du LFSR de la figure 3 relie l'entrée E de ce dernier au registre RG1, de manière à ouvrir l'accès du circuit aux échantillons numériques Sl à SN qui sont initialement fournis sur l'entrée E et qui, à la fin de cette phase d'initialisation, occupent respectivement les registres RGN à RG1. Le multiplexeur MX est alors commandé pour relier la sortie de l'opérateur de combinaison OCl à l'entrée du 30 registre RG1, ce qui autorise la génération de nouveaux échantillons numériques par recirculation des échantillons initiaux Si à SN et traitement par les différents opérateurs. A chaque cycle de calcul, les échantillons numériques stockés -5 dans les registres RG1 à RGN sont, tous en meme temps, transmis aux registres respectifs suivants ainsi qu'aux opérateurs de pondération respectifs OP1 à OPN, dans lesquels ils sont multipliés par des coefficients constants respectifs kl à kN. Ainsi, les échantillons numériques pondérés sont, tous en même temps, disponibles sur les entrées supérieures des opérateurs respectifs OCl à OCN. La somme de ces échantillons pondérés est ensuite retournée au premier registre RG1 à travers le multiplexeur parallèle MX. Or, cette somme d'échantillons n'est disponible sur l'entrée 15 inférieure du multiplexeur. MX que lorsque l'échantillon pondéré par le coefficient kN dans la cellule la plus éloignée du multiplexeur MX a traversé tous les opérateurs de combinaison, c'est-à-dire OCN à OCl, ce qui prend un temps approximativement égal à N fois le temps de transfert à 20 travers un seul opérateur de combinaison tel que OC1. En conséquence, même si le LFSR de la figure 3 a l'avantage de présenter une structure modulaire, descriptible comme l'assemblage de N cellules semblables, il garde en revanche 25 l'inconvénient de conduire à des temps de cycle dépendant du nombre N de celules. Cette dépendance du temps d'élaboration de chaque échantillon vis à vis du nombre de cellules est, de façon connue, 30 éliminée dans le LFSR illustré à la figure 4. Ce dernier, qui présente toutes les caractéristiques énumérées au tout début de la présente description, représente l'art antérieur le plus proche de l'invention. 35 -6 Le LFSR de la figure 4 est décrit par exemple à la page 43 (figure 10) de la revue "Computer" de janvier 1982, dans un article de H.T. Kung (Carnegie-Mellon University). Tout comme dans le LFSR de la figure 3, les chemins de circulation de bits et les opérateurs du LFSR de la figure 4 ont une structure parallèle. En fait, sur le plan de sa constitution, le LFSR de la figure 4 ne se distingue de celui de la figure 3 que par le fait que 10 chaque cellule (telle que Cl à CN) du circuit de la figure 4 comprend, au lieu d'un seul registre (tel que RG1 à RGN), un registre amont à P bits (tel que RGE1 à RGEN) et un registre aval à Q bits (tel que RGS1 à RGSN). Dans l'antériorité connue, les longueurs P et Q des registres amont et aval sont égales. La différence de structure des LFSR des figures 3 et 4 s'accompagne d'une différence de fonctionnement, conduisant à 20 une différence de performances. Dans le LFSR de la figure 4, l'initialisation est faite en injectant alternativement, à travers le multiplexeur MX, un échantillon numérique utile, tel que S1 à SN, et un échantillon nul, c'est-à-dire dont tous les bits sont égaux à zéro. Comme il y a N échantillons numériques utiles, il y a donc également N échantillons nuls, de sorte que la phase 30 d'initialisation prend N+N=2N cycles. Comme il y a N registres amont RGE1 à RGEN, et N registres aval RGSl à RGSN, tous les registres sont remplis à l'instant o se termine la phase d'initialisation. 35 -7 Plus précisément, à cet instant, les registres amont sont, pour la moitié d'entre eux, remplis d'échantillons nuls, et, pour l'autre moitié, remplis par les échantillons de la dernière moitié d'échantillons numériques S1 à SN, tandis que les registres aval contiennent déjà des combinaisons 05 partielles d'échantillons numériques pondérés. Cependant, à chaque cycle, chaque échantillon numérique effectue un trajet élémentaire qui correspond à la distance entre deux registres. En résumé, le LFSR connu de la figure 4 a donc l'avantage de présenter une structure modulaire et d'élaborer, postérieurement à la phase d'initialisation, chacun des échantillons numériques en un temps indépendant du nombre N 15 d'échantillons numériques utiles. Dans le langage de l'homme de l'art, un tel LFSR est dit "systolique". En revanche, ce LFSR connu présente deux inconvénients; le premier est de requérir une phase d'initialisation correspondant à 2N cycles pour N échantillons numériques utiles, et le second est de fournir, en régime stationnaire, un nouvel échantillon numérique utile qu'un cycle sur deux, 25 puisqu'en effet les échantillons numériques produits sont, une fois sur deux, constitués par un échantillon nul. Dans ce contexte, le but de la présente invention est de proposer un LFSR systolique ne requérant qu'une phase d'initialisation de N cycles pour N échantillons numériques utiles et ne produisant que des échantillons numériques utiles. A cette fin, le circuit LFSR de la présente invention, destiné à traiter des échantillons numériques dont chacun comprend M bits significatifs auxquels s'ajoutent éventuellement, en nombre X éventuellement nul, des bits d'extension de signe, et comportant des registres amont contenant chacun P bits, et des registres aval contenant chacun Q bits, est essentiellement caractérisé en ce que les registres amont et aval de chaque cellule sont des registres à décalage série, et en ce que la somme P+Q de leur longueur est égale à la longueur totale M+ X de chacun des échantillons numériques. D'autres caractéristiques et avantages de l'invention ressortiront de la description qui en est faite ci-après en référence aux dessins annexés parmi lesquels: - les figures 1 à 4 représentent l'art antérieur déjà décrit, - la figure 5 représente la structure matérielle d'un circuit LFSR conforme à l'invention, et _- la figure 6 représente, en plus de cette structure matérielle, l'évolution au cours du temps du contenu des registres à décalage d'un tel LFSR, représentative du fonctionnement de ce dernier. Le circuit de registres à décalage à rebouclage linéaire (LFSR) de l'invention, représenté sur la figure 5, comprend N cellules semblables (N est pris égal à 3 sur la figure 5), notées Cl, C2 et C3. Chaque cellule forme un chemin de circulation de bits, symbolisé par une flèche dans la cellule Cl, et comprenant en série, entre une entrée principale, telle que EP1, EP2, EP3, et une sortie principale, telle que SP1, SP2, SP3, de cette cellule, un registre amont à P bits, tel que RGE1, RGE2, 35 --9- RGE3, un opérateur de pondération, tel que OP1, OP2, OP3, un -opérateur de combinaison, tel que OC1, 0C2, OC3 et un registre aval à Q bits, tel que RGSl, RGS2, RGS3. Dans l'exemple illustré aux figures 5 et 6, P est égal à 4 et Q à 1. Selon l'invention, le chemin de circulation de bits que forme chaque cellule est un chemin de bits série, c'est-à-dire que les bits y circulent les uns derrière les autres en empruntant une seule et mème ligne; en particulier, les l0 registres amont et aval sont des registres à décalage série, c'est-à-dire que les bits y sont stockés en ne formant qu'une seule file entre l'entrée et la sortie de chacun de ces -registres. Le circuit LFSR représenté à la figure 5 est destiné à fournir, à des instants successifs, des échantillons numériques Sj respectifs, dont chacun représente une combinaison linéaire d'échantillons numériques antérieurs Sj-N à Sj-l. En particulier, ce circuit peut fournir au moins un échantillon numérique provenant de la combinaison de N échantillons initiaux (c'est-à-dire 3 dans l'exemple choisi), qui sont fournis au circuit au début de son fonctionnement. 25 Conformément à l'invention, chacun de ces échantillons numériques comporte au total P+Q bits (c'est-à-dire 4+1=5, dans l'exemple choisi), parmi lesquels M bits sont des bits significatifs et X bits sont des bits d'extension de signe, 30 ces derniers pouvant ne pas exister (par exemple, M est égal à 5 et X à 0). Les opérateurs de pondération sont typiquement des multiplieurs, opérant par exemple une multiplication des 35 - 10 - 2600440 -10 échantillons numériques par des coefficients constants, tels que kl à kN. La raison qui justifie l'emploi de la dénomination "opérateur de pondération" au lieu de la dénomination "multiplieur" est 05 que ces opérateurs peuvent, de façon connue, travailler dans des ensembles mathématiques autres que l'ensemble des nombres réels dans lequel on définit traditionnellement la multiplication, et par exemple dans un corps de Galois. Les opérateurs de combinaison OCl à OCN symbolisés par des opérateurs triadiques à deux entrées et une sortie, sont typiquement des additionneurs. De même que les opérateurs de pondération, ces opérateurs de 15 combinaison peuvent travailler dans des ensembles autres que l'ensemble des nombres réels, par exemple dans un corps de Galois. Ils peuvent en outre, de façon connue, comporter une mémoire stockant la retenue du résultat de l'addition. La sortie du registre amont (RGE1,.., RGEN) de chaque cellule forme une sortie secondaire (SS1,...,SSN) de cette cellule, tandis que l'une des deux entrées de l'opérateur de combinaison (OC1,..,OCN) de chaque cellule forme une entrée secondaire (ESl,..., ESN) de cette cellule. 25 Dans le circuit, les sortie et entrée secondaires de chaque cellule, hormis la dernière, sont respectivement reliées aux entrée et sortie principale d'une cellule suivante. La sortie secondaire SS3 de la dernière cellule n'est reliée à rien et 30 l'entrée secondaire ES3 de cette dernière cellule reçoit en permanence la valeur 0. La sortie principale SP1 de la première cellule Cl est reliée à l'entrée principale EPi de cette dernière à travers le 35 - 11 multiplexeur série MX, comme c'est le cas pour. le LFSR de la figure 4, à la différence près que le chemin de circulation de bits dans le LFSR de la figure 5 est un chemin série et non un chemin parallèle. Si les coefficients kl, k2,...,kN sont codés sur plusieurs bits, les opérateurs de pondération sont des opérateurs fonctionnant selon le mode série-parallèle, puisque tous les bits de chaque coefficient de pondération kl, k2,..., kN affectent tous les bits de chaque échantillon numérique Sl, 10 S2,..., SN, et puisque les bits de chaque échantillon numérique pondéré sont produits l'un après l'autre, selon un mode série. Les opérateurs de pondération série-parallèle sont bien 15 connus dans l'art antérieur. Un exemple d'un tel opérateur série-parallèle travaillant dans le corps des nombres réels est donné à la figure 1 de l'article de R.F. Lyon paru dans "IEEE Transactions on 20 Communications" en Avril 1976, page 418. Un exemple d'opérateur série-parallèle travaillant dans un corps de Galois est donné à la figure 2.16, page 47, du livre "Algebraic Coding Theory" de Elwyn R. Berlekamp, McGraw-Hill 25 Book Company, 1968. Les opérateurs de combinaison OC1,..., OCN gardent, quant à eux, une structure purement série quel que soit le nombre de bits des coefficients kl,..., kN. 30 Le fonctionnement du LFSR de la figure 5, représentant un exemple de mise en oeuvre de l'invention, est illustré à la figure 6. - 2600440 - 12 Dans la colonne de gauche de cette figure, T représente le temps, dont l'écoulement correspond à un déplacement du haut de la figure 6 vers le bas. Sous la lettre "T" figurent des nombres 1.1 à 4.2 correspondant aux numéros des cycles et d'étapes successifs de calcul (le premier chiffre correspondant au numéro du cycle et le second chiffre correspondant au numéro de l'étape à l'intérieur d'un cycle). - Dans le sens horizontal, la figure 6 est découpée suivant l'arrangement spatial du circuit. 10 Un déplacement de la gauche vers la droite dans les colonnes RGE1, RGE2, RGE3 correspond à une progression des bits des échantillons numériques dans les registres amont respectifs des cellules Cl à C3, tandis qu'un déplacement de la droite 15 vers la gauche dans les colonnes RGS3, RGS2, RGSl correspond à une progression des bits des échantillons numériquespondérés dans les registres aval respectifs des cellules Cl à C3. Les temps 1.1 à 3.5 correspondent à la phase d'initialisation du LFSR. Pendant chaque cycle de celle-ci, le LFSR reçoit, à travers le multiplexeur MX, l'un de 3 échantillons de 5 bits, notés Si, S2 et S3. L'échantillon Si est formé des bits Sll, S12, S13, S14 et S15 qui sont successivement fournis au cours des étapes 1 à 5 du premier cycle. Des notations homologues sont adoptées pour les échantillons 30 S2 et S3. Avant la phase d'initialisation, les registres amont et aval sont supposés ne contenir que des zéros, ou des informations qu'il n'est pas besoin de prendre en considération pour 35 - 13 - 2600440 comprendre le fonctionnement du LFSR tel qu'il est expliqué en référence à la figure 6. A la fin de la première étape du premier cycle (T=l.l), le bit Sll est mémorisé dans la première des 4 bascules du registre RGE1 (c'est-à-dire la bascule à l'extrême gauche sur le dessin). A la fin de la seconde étape (T=l.2) le bit S12 a pris sa place et le bit Sll a été poussé dans la seconde bascule de RGE1. Le processus se poursuit de la même façon jusqu'à la fin du 3ème cycle (T=3.5) qui marque la fin de la phase d'initialisation. Dès la fin du premier cycle (T=l.5), des bits d'échantillons 15 numériques pondérés atteignent les registres aval; par exemple, à T=l.5, (Sl.kl)l, c'est-àdire le premier bit du produit Sl.kl, est stocké dans RGSl; à T=2.1, (Sl. kl)2 est stocké dans le RGSl; à T=2.4, (Sl.k2)l est stocké dans RGS2. Comme cependant ces résultats partiels sont dépourvus d'effets, puisque le multiplexeur isole RGSl de RGE1 pendant toute la phase d'initialisation, ces résultats partiels n'ont en général pas été portés sur la figure 6. Par exception à-ce principe général, la figure 6 fait apparaître, au temps T=3.3, un résultat partiel Hll=(Sl.k3)1 constitué par le premier bit, stocké dans le RGS3, de l'échantillon numérique pondéré Sl.k3. Ce résultat partiel Hll est consolidé, au temps T=3.4, sous la forme d'un nouveau résultat partiel Jll, obtenu par "addition" à Hll de (S2.k2)1 et stocké dans RGS2. Ce dernier résultat partiel Jll est lui-meme consolidé, en T=3.5, en un nouveau résultat Lll, égal à Jll+(S3.kl)l, 35 - 14 stocké dans RGS1. Lll représente le premier bit de la combinaison linéaire Sl.k3+S2.k2+S3.kl puisque Lll=(Sl.k3+S2.k2+S3.kl)l. Au début du 4ème cycle, le multiplexeur MX ouvre la communication entre RGS1 et RGE1 en isolant RGE1 vis-à-vis de l'entrée E: le bit Lll est donc, au 4ème cycle, mémorisé dans la première bascule de RGE1. Le bit suivant, L12, a été préparé entretemps, et prend place, au temps 4. 2 dans la première bascule de RGE1, en repoussant Lll dans la seconde bascule. La figure 6 représente ce processus sous une forme immédiatement compréhensible et il est aisé de voir, par une extrapolation simple, que l'échantillonnumérique Ll=Sl.k3+S2.k2+S3.kl (et qu'on pourrait noter S4 pour assurer une continuité de notation) occupera, au temps 4.5, le registre RGE1 et, partiellement, le registre RGE2, le dernier 20 bit L15 se trouvant dans la première bascule de RGEl,'et le premier bit Lll se trouvant dans la première bascule de RGE2. Le LFSR de l'invention, d'architecture totalement systolique, réduit la phase d'initialisation à un nombre de cycles égal 25 au nombre d'échantillons numériques, supprime la nécessité d'entrelacer les échantillons utiles d'échantillons nuls, et double en conséquence le débit de production des échantillons numériques utiles. Il présente en outre l'avantage de n'utiliser que des composants fonctionnant en mode série, ou série parallèle, dont la structure est généralement beaucoup moins complexe que celle des composants fonctionnant en mode parallèle. - 15 REVENDICATION Circuit de registres à décalage à rebouclage linéaire, propre à fournir, à des instants successifs, des échantillons numériques respectifs (Sj), dont chacun représente une combinaison linéaire d'échantillons numériques antérieurs (Sj-1 à Sj-N)) et comprend M bits significatifs auxquels s'ajoutent éventuellement, en nombre X éventuellement nul, des bits d'extension de signe, ce circuit comportant N cellules semblables (Cl à CN) dont chacune forme un chemin de 10 circulation de bits comprenant, en série entre une entrée et une sortie principales (EP1 à EPN, et SP1 à SPN) de cette cellule, un registre amont (RGE1 à RGEN), contenant P bits, un opérateur de pondération (OP1 à OPN), un opérateur de combinaison à deux entrées (OC1 à OCN) et un registre aval (RGSl à RGSN) contenant Q bits,la sortie du registre amont (RGE1 à RGEN) et l'une des deux entrées de l'opérateur de combinaison (OC1 à OCN) constituant respectivement une sortie et une entrée secondaires (SSl à SSN et ESl à ESN) de la cellule, susceptibles d'être respectivement reliées à une entrée et à une sortie principales d'une cellule suivante du circuit, et la sortie principale (SP1) de la première cellule étant rebouclée sur l'entrée principale (EP1) de cette mème cellule pour permettre la recirculation des échantillons numériques produits, caractérisé en ce que lesdits registres 25 amont (RGE1 à RGEN) et aval (RGSl à RGSN) de chaque cellule sont des registres à décalage série, et en ce que la somme P+Q de leur longueur est égale à la longueur totale M+X de chacun des échantillons numériques.