[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

EP0175623A1 - Dispositif de traitement en temps réel de signal numérique par convolution - Google Patents

Dispositif de traitement en temps réel de signal numérique par convolution Download PDF

Info

Publication number
EP0175623A1
EP0175623A1 EP85401858A EP85401858A EP0175623A1 EP 0175623 A1 EP0175623 A1 EP 0175623A1 EP 85401858 A EP85401858 A EP 85401858A EP 85401858 A EP85401858 A EP 85401858A EP 0175623 A1 EP0175623 A1 EP 0175623A1
Authority
EP
European Patent Office
Prior art keywords
circuit
circuits
base
modulo
adder
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Withdrawn
Application number
EP85401858A
Other languages
German (de)
English (en)
Inventor
Pierre Duhamel
Hendrik Holmann
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Individual
Original Assignee
Individual
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Individual filed Critical Individual
Publication of EP0175623A1 publication Critical patent/EP0175623A1/fr
Withdrawn legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/10—Complex mathematical operations
    • G06F17/15—Correlation function computation including computation of convolution operations
    • G06F17/156—Correlation function computation including computation of convolution operations using a domain transform, e.g. Fourier transform, polynomial transform, number theoretic transform

Definitions

  • the invention can be used in all installations requiring digital signal processing and finds a particularly important application in digital filters, incorporated in particular in modems constituting interfaces between a digital system and a transmission channel.
  • TNE integer transform
  • a is a Nth primitive root of the modulo unit M.
  • the TNE 1 circuit performs the reverse transformation.
  • the first solution is the most advantageous because it easily allows a decomposition into transforms of short length which can be calculated using fast algorithms.
  • the invention aims to provide a real-time processing device using the NET, with a module M of the form 2 P - 2 + 1 (the particular form 2 2q - 2 + 1 being more advantageous for certain operations), leading to significantly simplified operations, including offsets.
  • the invention proposes in particular a device for real-time processing of digital signal by convolution, comprising a multiplier circuit associated with circuits for transformation into whole numbers, with module M of the form on each input, and to a transformation circuit inverse on the output, characterized in that each of the circuits with integer transformation is preceded by an arithmetic base change and coding circuit, and in that the inverse transformation circuit is followed by a decoding circuit and back to the starting base, said circuits being provided so that a number X modulo M in the original base in power of 2 corresponds, in the new base, a number than
  • N 3 or 4
  • each operation makes correspond, to two numbers x and y already coded in the form C (x) and C (y), the code of the sum C (x + y) or another combination.
  • Code additions and subtractions are the only essentials: the other operations are only useful for shifting, where modulo additions provide only a simplification.
  • the first circuit which will be described with reference to FIG. 4 allows these four operations to be carried out using simple adder-subtractors.
  • the second circuit shown in Fig. 5, performs these operations using adders-subtractors in addition to 2.
  • a simplified version only performing the code subtraction additions is given in Figure 5.
  • Figure 4 shows a possible embodiment of an "out of code" adder-subtractor, comprising four simple elementary adder-subtractors 20-11, 20-12, 20-13 and 20-14.
  • the adder-subtractor is intended to process numbers X and Y of each 2q bits to provide a number Z, also of 2q bits.
  • Each elementary adder-subtractor has two inputs, identified by E1 and E2 and a retaining input ri. It has a result output S and a carry output r0.
  • the operation to be performed is fixed by the binary level g applied to the flag input F and the logic level p applied to the carry input ri of the elementary adder-subtractor 20-12.
  • the q least significant bits of X and Y are respectively applied to the inputs E1 and E2 of the elementary adder-subtractor 20-12; the most significant bits of X and Y are respectively applied to the inputs E1 and E2 of the elementary adder-subtractor 20-11.
  • the output r0 of the adder-subtractor 20-12 is applied both to the input ri of the adder-subtractor 20-11 and to the input ri of the adder-subtractor 20-14.
  • the holding output r0 of the adder-subtractor 20-11 is applied to the flag inputs F of the adder-subtractors 20-13 and 20-14.
  • the output S of the adder-subtractor 20-13 then supplies the q most significant bits of Z; the output S of the adder-subtractor 20-t4 gives q-1 the least significant bits of Z. Finally, the least significant bit of Z is supplied by a NON OR EXCLUSIVE gate 54 whose inputs receive the outputs r0 of adders-subtractors 20-13 and 20-14. It should be noted that these two adder-subtractors carry out operations which are limited to carry-over propagations. Insofar as the use of identical elementary blocks is not essentially sought, the elements 20-13 and 20-14 can be simplified significantly.
  • the elementary add-subtraction components 20 in addition to 2 could be formed by putting in series three elements each working on four bits in addition to 2.
  • the four adders-subtractors 20 are divided into two layers.
  • the second layer will be simpler to produce in monolithic integration than the first, one of the signals entering each of the elementary addition-subtraction components 23 and 24 of the second layer being a word of at most 2 bits.
  • Figure 6 shows a circuit providing the transform of length 3 from the three numbers already coded and brought into the new base, C (x0), C (x1) and C (x2).
  • This circuit processes the q most significant bits (MSB) and the q least significant bits (LSB) separately. It is particularly simple since it does not involve inversion of the input signals C (x0), C (x1), C (x2). This result was achieved by an appropriate choice of operations carried out by the different operators. We see that these can all be formed by circuits of the type shown either in Figure 4, or in Figure 5, or in Figure 5a.
  • FIG. 7 shows, similarly to FIG. 6, a circuit making it possible to supply the transform as an integer of length 4, by a constitution which also makes it possible to eliminate the inversions of input signals.
  • all the elementary adder-subtractor components can be constituted either by the adder-subtractors of general application in FIGS. 4 and 5, or by the simplified version of FIG. 5a.
  • the 2q-bit links and the q-bit links we have not differentiated in Figure 7 the 2q-bit links and the q-bit links. It should simply be noted in FIG. 7 that the output of the 2q bit adder-subtractor 22-1 is split into four parts of each q / 2 bit.
  • the two least significant outputs s0 and s1 are applied to the addition input of the adder-subtractor 22-5, in a different combination.
  • the most significant outputs s2 and s3 are applied, similarly, to the addition input of the adder-subtractor 22-5 and to the subtraction input of the adder-subtractor 22-5, the fourth series of q / 2 bits being a series of 1.
  • module M and of length N using 2 as the root of the unit are particularly interesting: we can notably cite those mentioned in the article "Longer NTT's with 2 as a root of unity" by H. Hollmann et al, in ICASSP, 1983.
  • the circuit 23 shown in Figure 8 makes it possible to calculate C (2 k . X) from C (x). Physically, this operation is carried out by elementary shifts, each corresponding to a multiplication by 2.
  • the corresponding circuit comprises an adder-subtractor 24 which, this time, cannot have the simplified constitution shown in FIG. 5a.
  • the two inputs of this adder 24 receive a combination of the least significant and most significant bits of C (x), introduced into a register 26 provided with an inverter recirculation loop 28.
  • the byte of 2q bits to be multiplied by 2 k is loaded in parallel in both terminal parts, each having q positions, of the shift register 26 whose capacity is 3q bits.
  • the adder-subtractor 24 provides the result by addition modulo M.
  • FIG. 9 shows a circuit 23 constituting an alternative embodiment using the same components 24, 26 and 28 as Figure 8.
  • Figure 10 shows yet another variant, which allows the use of the simplified adder-subtractor of Figure 5, but requires the addition of two additional inverters 30.
  • the shift registers 26 of FIGS. 8, 9 and 10 can be physically constituted by multiplexers, controlled by the value of k (number of shifts) thus a shift of k positions is done in a single clock stroke, this which saves time.
  • the processing device comprises, in addition to the transform calculation circuits, the circuits 12 and 14 (base change, coding and decoding) and the general multiplication circuit 10.
  • Figures 12 and 13 show two circuits for performing base change and coding in the event that it is assumed that all of the processed signals are positive. This condition can easily be fulfilled by adding a constant to the input signal.
  • One of the inputs receives the quantity X to be coded in the form C (x).
  • the other entry receives, as most significant digits, q zeros, as least significant digits, the most significant q digits of X.
  • the output of the adder-subtractor 24 provides the inverse of C (x), which makes it possible to recover C (x ) by simple interposition of inverters 34.
  • this circuit requires only an adder-subtractor, 2q inverters and a manipulation on the bits of X. The result is obtained by adding words, "outside the code", and complementing the result.
  • the variant embodiment shown in FIG. 13 uses an adder-subtractor 24 which can, this time, be of the simplified type shown in FIG. 5a. It includes, as input elements, a set of inverters 36 which provide the complement of X as an output. This complement is applied to one of the inputs of the adder-subtractor 24. The other input receives, as as most significant digits, q "one", as least significant digits, the q most significant bits of the complement. The result C (x) is then obtained directly at the output of the adder 24.
  • circuits making it possible to pass from the number coded in the new base to a number coded in addition to 2 in the starting base (base of the powers of 2) can also be carried out in a simple way. This operation is performed by circuit 14 on the result C (y) of the inverse integer transform TNE 1 in Figure 2.
  • the circuit can be that shown in Figure 14. It includes a set of inverters 38 intended to complement the input signal C (y) and a conventional subtractor 40.
  • L input + of the subtractor receives the complement of C (y).
  • the entry - receives q zeros as most significant bits, the four most significant bits of the complement of C (y) as least significant bits.
  • the circuit can be that of FIG. 15. It includes an adder-subtractor 42 having a flag input F which allows two different operating modes according to that this input is zero or 1.
  • the + input of the adder-subtractor 42 receives the complement to 2 of the signal C (y) produced by inverters 44.
  • the other input receives q zeros as bits of most significant, the output of a two-to-one multiplexer 46 as least significant bits.
  • One of the inputs of the multiplexer receives the most significant bits of C (y). the other the complement of this number of q bits, developed by inverters 48.
  • the most significant bit of C (y) which represents the sign, is applied to the input F and to the command input of multiplexer 46.
  • the output of the multiplexer is constituted by the complement of the most significant bits of C (y) and the adder-subtractor 42 operates in subtraction mode.
  • the output Y is then constituted by the difference between C (y) and the q most significant bits of C (y), assigned to the least significant.
  • Figures 16 and 17 show two other circuits constituting variants of that of Figure 15, also making it possible to obtain Y in addition to 2 from C (y) and being able to use elementary adders-subtractors of the kind of that shown in Figure 3 and which, depending on the flag F, provides on its output:
  • the operations are carried out on numbers of 2q bits.
  • the sign bit of C (y) (most significant bit) is applied as a restraint input ri. This same sign bit is applied as the value of the q most significant bits at the additive input of the elementary adder-subtractor.
  • Y is constituted by C (y) from which the q most significant bits of C (y) are subtracted, reduced to the least significant.
  • the output of the multiplexer is then in this case that which receives the q most significant bits via inverters 52.
  • circuit can then be the one shown in Figure 18, where the upper part corresponds to the first term of the above equation.
  • K can in this case be much weaker than in a representation in the form of a binary number affected by a sign for a usual calculation.
  • the invention is susceptible of very numerous variant embodiments, relating both to the constitution of the components and to their association.
  • the elementary circuits used are very general: the modulo M adders-subtractors previously described can be used regardless of the value chosen. There is thus a block which will be used alone apart from current elements. Only the base coding-changing and decoding-returning to the starting base circuits depend on the value chosen for f. Both the adder-subtractors and the offset elements do not depend on the total transform length. They only depend on the module M chosen. Only the circuit making it possible to recombine the short length transforms will be modified, depending on the total transform length, a circuit formed from multiplication circuits by 2 and by q2 in the case, which will be the most frequent, where the we take 2 or ⁇ 2 as the Nth root of the modulo M unit.

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Mathematical Physics (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • Computing Systems (AREA)
  • Databases & Information Systems (AREA)
  • Software Systems (AREA)
  • General Engineering & Computer Science (AREA)
  • Algebra (AREA)
  • Complex Calculations (AREA)
  • Error Detection And Correction (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

Le dispositif, utilisable dans les installations exigeant un traitement numérique du signal, comprend un circuit multiplieur associé à des circuits à transformation en nombre entier, à module M de la forme 2<p> - 2<q> + 1 sur chaque entrée et à un circuit de transformation inverse sur la sortie. Chacun des circuits à transformation en nombres entiers (16) est précédé d'un circuit de changement de base arithmétique et de codage (12) et le circuit de transformation inverse est suivi d'un circuit de décodage et de retour à la base de départ (14). Ces circuits sont prévus de façon qu'un nombre X modulo M dans la base d'origine en puissances de 2 corresponde, dans la nouvelle base, à un nombre <IMAGE> fo étant un entier compris entre 1 et M-1.

Description

  • L'invention concerne les dispositifs pour effectuer, sur un signal, un traitement en temps réel, nécessitant donc une vitesse élevée de calcul, comportant le calcul de produits de convolution que l'on peut ramener à des convolutions circulaires de la forme :
    Figure imgb0001
    où n = 0, 1,..., N-1, sont pris modulo N ainsi que n-k.
  • L'invention est utilisable dans toutes les installations exigeant un traitement numérique du signal et elle trouve une application particulièrement importante dans les filtres numériques, incorporés notamment aux modems constituant interfaces entre un système numérique et un canal de transmission.
  • L'obtention d'une vitesse de traitement élevée passe par la réduction de la complexité des calculs à effectuer par point de la convolution à calculer. Une solution classique utilisée est l'application de la transformée de Fourier discrète sur x(n) et h(n) et de la transformée inverse après multiplication des résultats. Mais cette solution fait intervenir des nombres complexes et conduit à des erreurs d'arrondi. Au surplus, le nombre de multiplications et d'additions nécessaire par point de la convolution, même lorsqu'on utilise des algorithmes évolués (transformée de Fourier rapide, algorithme de Winograd), reste excessif pour permettre un traitement en temps réel de débits élevés de données.
  • Une solution qui parait plus avantageuse consiste à utiliser la transformée en nombres entiers (TNE) qui conduit à un dispositif de calcul de produits de convolution du genre montré en Figure 1. L'entrée et la sortie des circuits de TNE sont reliées par la relation :
    Figure imgb0002
    avec k = 0,1,..., N-1.
  • Dans cette formule, a est une racine primitive Nième de l'unité modulo M.
  • Le circuit TNE 1 effectue la transformation inverse.
  • Les avantages que l'on peut attendre des TNE sont de deux ordres. La convolution est obtenue exactement, sans bruit de calcul, pourvu que sa valeur soit inférieure à M. Si le couple longueur N - module M est correctement choisi, a peut être très simple, par exemple égal à 2. Dans ce cas, la transformée ne comporte plus de multiplications générales, mais uniquement des multiplications par 2k qui sont réalisées par décalage dans des circuits binaires. Pour des transformées plus longues, on peut également adopter a = √2. Là encore, on supprime les multiplications, dans la partie transformée, sans augmenter notablement le nombre d'additions. Mais on se heurte en contrepartie à deux inconvénients : les multiplications sont remplacées par des manipulations au niveau de l'élément binaire (bit) ; les opérations, notamment les additions, doivent être effectuées en modulo M. L'examen détaillé montre que l'on ne tire véritablement parti de ces simplifications qu'en les mettant en oeuvre dans des transformées de petite longueur, notamment pour N = 4 et N = 3. Mais, dans la pratique, il est nécessaire de disposer de transformées de longueur totale très supérieure, ce qui implique d'utiliser des transformées décomposables en transformées de faible longueur.
  • La prise en considération de ces motifs a conduit jusqu'ici à adopter essentiellement des arithmétiques de TNE utilisant des valeurs de M résultant de sommes ou différences de deux ou trois puissances de 2 différentes.
  • Dans le premier cas, où M = 2n ± 1, on se trouve en présence de deux transformées connues (Mersenne et Fermat) pour lesquelles l'arithmétique est simple. Mais ces transformées ne permettent pas de grandes longueurs N de convolution.
  • Dans le second cas, les arithmétiques actuellement utilisées ne sont intéressantes que pour des valeurs de M permettant de travailler avec 2 comme racine primitive de l'unité modula M, ce qui conduit à M = 22q - 2q+1 ou M = 22q-1 - 2 q+1.
  • La première solution est la plus avantageuse car elle autorise facilement une décomposition en transformées de faible longueur pouvant se calculer à l'aide d'algorithmes rapides.
  • Ces solutions, même conjuguées à un codage "diminué de 1" qui fait correspondre C(x) = x-1 à x, pour simplifier les décalages, restent insuffisantes. Le niveau de complexité du décalage reste encore de trois additions dans le cas où M = 2 2q - 2 q+1.
  • L'invention vise à fournir un dispositif de traitement en temps réel utilisant les TNE, avec un module M de la forme 2P - 2+1 (la forme particulière 22q - 2+1 étant plus avantageuse pour certaines opérations), conduisant à des opérations notablement simplifiées, notamment les décalages.
  • Dans ce but, l'invention propose notamment un dispositif de traitement en temps réel de signal numérique par convolution, comprenant un circuit multiplicateur associé à des circuits à transformation en nombres entiers, à module M de la forme
    Figure imgb0003
    sur chaque entrée, et à un circuit à transformation inverse sur la sortie, caractérisé en ce que chacun des circuits à transformation en nombres entiers est précédé d'un circuit de changement de base arithmétique et de codage, et en ce que le circuit de transformation inverse est suivi d'un circuit de décodage et de retour à la base de départ, lesdits circuits étant prévus de façon qu'à un nombre X modulo M dans la base d'origine en puissance de 2 corresponde, dans la nouvelle base, un nombre
    Figure imgb0004
    que
    Figure imgb0005
  • Dans la nouvelle base arithmétique, plusieurs séries de f. et e. conduisant aux mêmes circuits arith- métiques sont possibles. Mais elles doivent remplir les conditions :
    • (f , M) = 1 (c'est-à-dire que fo et M sont premiers entre eux, fo étant un entier compris entre 1 et M-1),
      Figure imgb0006
  • Deux cas pratiques du fait de leur simplicité consistent à prendre :
    Figure imgb0007
    ou
    Figure imgb0008
  • Une étude théorique montre qu'il s'agit bien d'une base arithmétique pour l'ensemble des entiers modulo M : tout nombre 0 ≤ X< M a une seule représentation binaire dans la nouvelle base, à l'exception de 2q-1 nombres qui ont exactement deux représentations, ce qui n'a aucune importance pour les circuits, pourvu que l'on sache décoder ces deux représentations. Dans le cas, important en pratique, où P = 2q, f = 1, l'ensemble de ces nombres est constitué par les multiples de 2q.
  • Le codage (ainsi que le décodage) peut être effectué après changement de base aussi bien qu'avant changement de base. Mais, dans le second cas, ce codage fera correspondre C(X) = X-f à X. On verra dans la suite que le choix fo =-1 permet de regrouper codage et changement de base dans le même circuit.
  • L'invention sera mieux comprise à la lecture de la description qui suit de dispositifs qui en constituent des modes particuliers d'exécution, donnés à titre d'exemples non limitatifs. La description se réfère aux dessins qui l'accompagnent, dans lesquels :
    • - la Figure 1, déjà mentionnée, est un schéma de principe d'un dispositif de calcul de produits de convolution utilisant des circuits de TNE,
    • - la Figure 2, similaire à la Figure 1, montre un dispositif de traitement de signal faisant intervenir deux signaux d'entrée X et H, correspondant à des nombres modulo M, exprimés en base habituelle des puissances de 2, et un signal de sortie Y, convolution circulaire de X et H,
    • - la Figure 3 est un schéma montrant les notations utilisées pour désigner les entrées et sorties d'un additionneur-soustracteur élémentaire utilisé dans les différents circuits du dispositif,
    • - les Figures 4 et 5 sont des synoptiques d'additionneurs-soustracteurs d'application générale, celui de la Figure 5 associant plusieurs additionneurs-soustracteurs élémentaires en complément à 2 ;
    • - la Figure 5a, similaire à la Figure 5, montre une réalisation simplifiée,
    • - les Figures 6 et 7 sont des synoptiques de circuits de transformation en nombres entiers de longueur 3 et 4, respectivement,
    • - la Figure 8 est un synoptique d'un circuit de multiplication par 2k dans le code, utilisable dans des circuits de recombinaison de transformées de longueur faible,
    • - les Figures 9 et 10 montrent des variantes de réalisation de la Figure 8,
    • - la Figure 11 est un synoptique d'un circuit de multiplication par √2 dans le code, utilisable dans des circuits de recombinaison de transformées courtes,
    • - les Figures 12 et 13 sont des synoptiques montrant deux circuits possibles de codage et de changement de base, faisant correspondre C(x) à X,
    • - la Figure 14, similaire aux Figures 12 et 13, est un schéma de principe d'un circuit de décodage et de retour à la base d'origine faisant correspondre Y à C(y),
    • - la Figure 15, similaire à la Figure 14, montre un circuit de décodage et de retour à la base de départ fournissant Y sous forme de complément à 2,
    • - les Figures 16 et 17 sont des synoptiques de variantes de réalisation de la Figure 15,
    • - la Figure 18 est un synoptique de principe d'un circuit de multiplication général utilisable dans le dispositif de la Figure 3,
  • les Figures 12 à 17 correspondent toutes au cas f = -1, où les opérations de codage (respectivement de décodage) et de changement de base (respectivement de retour à la base de départ) sont effectuées dans le même circuit.
  • Avant de décrire des circuits permettant de mettre en oeuvre l'invention, on définira le synoptique du dispositif dans son ensemble, puis les fonctions à remplir par ses blocs constitutifs.
  • Comme le montre la Figure 2, sur chacune des voies aboutissant au jeu de multiplicateurs 10 la donnée d'entrée Xn ou Hn (représentée par un multiplet en numération binaire, modulo M) est appliquée à un circuit 12 de changement de base et de codage pour donner naissance à une valeur codée C(xn) ou C(hn). Les deux opérations peuvent être effectuées dans un ordre quelconque. Pour Xn par exemple, on peut :
    • - soit effectuer d'abord le changement de base, qui transforme la valeur X en x, puis le codage pour transformer x en C(x) = x-fo,
    • - soit effectuer le codage C(X) = X-fo avant le changement de base qui donne C(x).
  • Le circuit 14 de décodage et de retour à la base de départ utilise la possibilité déjà citée de recombiner ces deux opérations dans le cas où f = -1.
  • Les circuits 16 et 18 destinés à calculer les transformées TNE et TNE utiliseront toujours des circuits fournissant des transformées de faible longueur, généralement correspondant à N = 3 ou 4, associés à des circuits d'assemblage de telles transformées pour arriver à la longueur requise. On cherchera à réaliser les circuits fournissant les transformées de faible longueur à partir d'un petit nombre de types d'opérateurs afin de faciliter la conception et la fabrication des circuits.
  • On décrira maintenant, successivement :
    • - les composants élémentaires utilisés dans les circuits,
    • - des constitutions possibles de blocs additionneurs-soustracteurs incorporant les éléments de base,
    • - les circuits d'élaboration de transformées de longueur 3 et de longueur 4,
    • - les circuits nécessaires à l'assemblage de telles transformées pour obtenir des transformées de longueur supérieure,
    • - et enfin les circuits qu'on peut qualifier d'extérieurs à la TNE, c'est-à-dire les circuits de changement de base, de codage, de décodage et de multiplication générale calculant le produit de convolution.
  • Les opérateurs seront décrits dans leur application à des transformées où P = 2q. Mais les résultats sont en général également vrais pour d'autres couples de valeurs de P et de q qui ne respectent pas cette condition.
    • Composants élémentaires
  • Les composants élémentaires utilisés dans la constitution des additionneurs-soustracteurs en arithmétique modulo M (Figures 4, 5 et 5a) sont en nombre aussi faible que possible. Ils interviennent chacun sur q bits (ou sont constitués par l'association d'éléments traitant chacun un nombre de bits qui est un sous-multiple de q).
  • Ces composants élémentaires comportent des inverseurs logiques, ainsi que des circuits ET, OU et OU EXCLUSIF de type classique. Ils comportent surtout des composants élémentaires additionneurs-soustracteurs 20. Dans le circuit de la Figure 4, il s'agit d'additionneurs-soustracteurs simples ; dans les circuits des Figures 5 et 5a, il s'agit d'additionneurs-soustracteurs en complément à 2. Les notations qui seront utilisées apparaissent sur la Figure 3 où :
    • x et y désignent les nombres appliqués à l'entrée,
    • z désigne le nombre apparaissant en sortie,
    • ri est la retenue entrante,
    • ro est la retenue sortante,
    • F est une entrée "fanion", destinée à fixer le mode de travail, par exemple :
    • pour F = 0, z = x+y+ri+2q.r0
    • pour F = 1, z = x+y+ri+2q.rO
  • Les notations x et y utilisées ici pour décrire le fonctionnement en additionneur et en soustracteur ne doivent évidemment pas être confondues avec celles qui interviennent dans le traitement global de convolution.
  • On utilisera par ailleurs les notations g0 et g1 pour désigner les commandes qui permettent de réaliser les divers types d'opérations requis, selon le Tableau I ci-après :
    Figure imgb0009
  • On voit que chaque opération fait correspondre, à deux nombres x et y déjà codés sous la forme C(x) et C(y), le code de la somme C(x+y) ou une autre combinaison.
  • Les additions et soustractions code sont les seules indispensables : les autres opérations ne sont utiles que pour le décalage, où les additions modulo n'apportent qu'une simplification.
  • Le premier circuit qui va être décrit en faisant référence à la Fig. 4 permet d'effectuer ces quatre opérations à l'aide d'additionneurs-soustracteurs simples. Le second circuit, représenté en Fig. 5, effectue ces opérations à l'aide d'additionneurs-soustracteurs en complément à 2. Une version simplifiée n'effectuant que les additions soustractions code est donnée en Figure 5.
    • Additionneur-soustracteur
  • La Figure 4 montre une réalisation possible d'un additionneur-soustracteur "hors du code", comportant quatre additionneurs-soustracteurs élémentaires simples 20-11, 20-12, 20-13 et 20-14. L'additionneur-soustracteur est prévu pour traiter des nombres X et Y de chacun 2q bits pour fournir un nombre Z, également de 2q bits. Chaque additionneur-soustracteur élémentaire comporte deux entrées, identifiées par E1 et E2 et une entrée de retenue ri. Il comporte une sortie de résultat S et une sortie de retenue r0.
  • Le circuit de la Figure 4 permet d'effectuer, sur les données X et Y, l'une quelconque des opérations:
    • addition code, addition modulo, soustraction code, soustraction modulo.
  • L'opération à effectuer est fixée par le niveau binaire g appliqué sur l'entrée de fanion F et le niveau logique p appliqué à l'entrée de retenue ri de l'additionneur-soustracteur élémentaire 20-12.
  • Les q bits de poids faible de X et de Y sont respectivement appliqués aux entrées E1 et E2 de l'additionneur-soustracteur élémentaire 20-12 ; les bits de poids fort de X et de Y sont respectivement appliqués aux entrées E1 et E2 de l'additionneur-soustracteur élémentaire 20-11. La sortie r0 de l'additionneur-soustracteur 20-12 est appliquée à la fois à l'entrée ri de l'additionneur-soustracteur 20-11 et à l'entrée ri de l'additionneur-soustracteur 20-14. La sortie de retenue r0 de l'additionneur-soustracteur 20-11 est appliquée aux entrées de fanion F des additionneurs-soustracteurs 20-13 et 20-14. La sortie S de l'additionneur-soustracteur 20-13 fournit alors les q bits de poids fort de Z ; la sortie S de l'additionneur-soustracteur 20-t4 donne q-1 des bits de poids faible de Z. Enfin, le bit de poids le plus faible de Z est fourni par une porte NON OU EXCLUSIF 54 dont les entrées reçoivent les sorties r0 des additionneurs-soustracteurs 20-13 et 20-14. Il faut remarquer que ces deux additionneurs-soustracteurs effectuent des opérations qui se limitent à des propagations de retenue. Dans la mesure où on ne recherche pas essentiellement l'emploi de blocs élémentaires identiques, les éléments 20-13 et 20-14 peuvent être simplifiés de façon notable.
  • Dans ces conditions, on obtient la sortie Z donnée par le Tableau II ci-dessous :
    Figure imgb0010
    Figure imgb0011
  • Le circuit de la Fig. 5 permet , de son côté, de réaliser l'ensemble des fonctions définies dans le Tableau I sur des entrées constituées par des nombres de q bits, avec par exemple q = 12, et forme aussi un additionneur-soustracteur d'application générale, mais, cette fois-ci, utilisant des additionneurs-soustracteurs élémentaires en complément à 2. Eventuellement, les composants élémentaires 20 d'addition-soustraction en complément à 2 pourront être constitués par mise en série de trois éléments travaillant chacun sur quatre bits en complément à 2.
  • Le circuit de la Figure 5 comporte quatre composants élémentaires d'addition-soustraction 20-1, 20-2, 20-3 et 20-4 dont les entrées de fanion sont respectivement désignées par F1, F2, F3 et F4. Ces additionneurs sont associés à des circuits assurant les fonctions ET (indiqués A), OU (indiqués V) et OU EXCLUSIF (indiqués 0 ). L'examen du circuit montre que F1 = F2 = g1 et que la valeur prise par les fanions F3 et F4 est :
    Figure imgb0012
  • Les sorties U1 et UO prennent de leur côté la valeur :
    Figure imgb0013
    Figure imgb0014
  • On obtient alors, en sortie du circuit, la valeur de z donnée par le Tableau I pour chaque couple de valeurs de g0 et g1, sur 2q bits, soit q bits de poids faible (ou LSB) et q bits de poids fort (ou MSB).
  • On voit que l'emploi de la base définie par la formule (2) permet de n'utiliser qu'un seul schéma de circuit pour constituer l'ensemble des quatre types d'additions et de soustractions modulo M nécessaires au calcul des transformées, définies par le Tableau I.
  • Les quatre additionneurs-soustracteurs 20 sont répartis en deux couches. La deuxième couche sera plus simple à réaliser en intégration monolithique que la première, un des signaux entrant sur chacun des composants élémentaires d'addition-soustraction 23 et 24 de la seconde couche étant un mot d'au plus 2 bits.
  • On peut utiliser, au lieu du schéma de la Figure 5. celui qui est montré en Figure 5a, mais uniquement pour effectuer des additions-soustractions réalisées dans le code de transformation, ce qui exclut les opérations définies par les deuxième et quatrième lignes du Tableau I.
  • Les circuits de la Figure 5a n'utilisent, pour tous les fanions, qu'une seule valeur g, qui peut prendre les deux valeurs de g1 du Tableau I et permet de remplir toutes les fonctions correspondant à g = 0 dans ce Tableau.
  • On verra que ce circuit simplifié est suffisant dans beaucoup de cas, en dépit de ces limitations.
  • Il faut relever au passage que l'utilisation en cascade d'un ET et d'un OU EXCLUSIF n'est nullement essentielle pour former le bit de poids le plus faible de z : tout autre schéma réalisant la fonction OU EXCLUSIF sur la sortie r0 de 20-4, le complément de la sortie r0 de 20-3 et le bit de poids le plus faible de la sortie de résultat de 20-4 serait utilisable.
  • Sur les Figures qui vont maintenant être décrites et montrent les circuits d'élaboration des transformées de longueur 3 et 4 à partir de blocs du genre montré en Figure 5 ou 5a, les entrées g0 et g1 ne seront pas représentées pour plus de simplicité, les valeurs données à g0 et g1 étant seules indiquées.
    • Circuit d'élaboration de TNE de longueur 3 ou 4 sur des mots codés et dans la nouvelle base
  • La Figure 6 montre un circuit fournissant la transformée de longueur 3 à partir des trois nombres déjà codés et amenés dans la nouvelle base, C(x0), C(x1) et C(x2). Ce circuit traite séparément les q bits de poids fort (MSB) et les q bits de poids faible (LSB). Il est particulièrement simple puisqu'il ne comporte pas d'inversion des signaux d'entrée C(x0), C(x1), C(x2). Ce résultat a été atteint par un choix approprié des opérations effectuées par les différents opérateurs. On voit que ces derniers peuvent tous être constitués par des circuits du type montré soit en Figure 4, soit en Figure 5, soit en Figure 5a.
  • On voit que la transformée de longueur 3 est ainsi obtenue en utilisant uniquement sept additionneurs modulo M répartis en deux couches, ce qui se traduit par quatre couches de composants élémentaires 20. Pour réaliser une transformée de Fourier rapide de même longueur, il aurait fallu utiliser deux couches de trois additionneurs travaillant chacun sur des nombres complexes et une couche de multiplicateurs, plus lents et beaucoup plus compliqués.
  • La Figure 7 montre, de façon similaire à la Figure 6, un circuit permettant de fournir la transformée en nombre entier de longueur 4, par une constitution qui permet encore d'éliminer les inversions de signaux d'entrée. Là encore, on voit que tous les composants élémentaires additionneurs-soustracteurs peuvent être constitués soit par les additionneurs-soustracteurs d'application générale des Figures 4 et 5, soit par la version simplifiée de la Fig. 5a. Pour plus de simplicité, on n'a pas différencié sur la Figure 7 les liaisons à 2q bits et les liaisons à q bits. Il faut simplement remarquer sur la Figure 7 que la sortie de l'additionneur-soustracteur 22-1 de 2q bits, est découpée en quatre parties de chacune q/2 bits. Les deux sorties s0 et s1 de poids faible sont appliquées sur l'entrée d'addition de l'additionneur-soustracteur 22-5, dans une combinaison différente. Les sorties de poids fort s2 et s3 sont appliquées, de façon similaire, sur l'entrée d'addition de l'additionneur-soustracteur 22-5 et sur L'entrée de soustraction de l'additionneur-soustracteur 22-5, la quatrième série de q/2 bits étant une série de 1.
    • Circuits d'assemblage des transformées de longueur 3 et 4 en transformées de longueur supérieure
  • Le processus d'assemblage de transformées théoriques de nombres est en lui-même connu et il est largement utilisé dans des circuits d'assemblage de transformées de Fourier rapides. Cet assemblage implique essentiellement des multiplications par 2k et par V2. Mais la mise en oeuvre du processus est notablement simplifiée dans le cas de l'invention, comme cela apparaitra à l'examen des circuits qui vont maintenant être décrits.
  • Certains couples de module M et de longueur N utilisant 2 comme racine de l'unité sont particulièrement intéressants : on peut notamment citer ceux mentionnés dans l'article "Longer NTT's with 2 as a root of unity" de H. Hollmann et al, dans ICASSP, 1983.
  • Le circuit 23 montré en Figure 8 permet de calculer C(2k .x) à partir de C(x). Physiquement, cette opération est effectuée par des décalages élémentaires, correspondant chacun à une multiplication par 2. Le circuit correspondant comporte un additionneur-soustracteur 24 qui, cette fois, ne peut pas avoir la constitution simplifiée montrée en Figure 5a. Les deux entrées de cet additionneur 24 reçoivent une combinaison des bits de poids faible et de poids fort de C(x), introduits dans un registre 26 muni d'une boucle de recir- culation à inverseur 28. Le multiplet de 2q bits à multiplier par 2k est chargé en parallèle dans les deux parties terminales, ayant chacune q positions, du registre à décalage 26 dont la contenance est de 3q bits. Par application d'un signal d'horloge sur une entrée non représentée, k décalages successifs sont effectués sur le registre. L'additionneur-soustracteur 24 fournit le résultat par addition modulo M.
  • Les quatre demi-mots appliqués aux entrées de l'additionneur-soustracteur 24 peuvent être combinés de manière différente de celle de la Figure 8. La Figure 9 montre un circuit 23 constituant une variante de réalisation utilisant les mêmes composants 24, 26 et 28 que la Figure 8.
  • La Figure 10 montre une autre variante encore, qui autorise l'emploi de l'additionneur-soustracteur simplifié de la Figure 5, mais exige l'adjonction de deux inverseurs supplémentaires 30.
  • Les registres à décalage 26 des Figures 8, 9 et 10 peuvent être constitués physiquement par des multi- plexeurs, commandés par la valeur de k (nombre de décalages) ainsi un décalage de k positions se fait en un seul coup d'horloge, ce qui constitue un gain de temps.
  • Il ne sera nécessaire de disposer d'un circuit de multiplication par √2 que pour certaines valeurs de N qui amènent à utiliser V2 comme racine Nième de l'unité. Par exemple, pour P = 2q, avec N = 6q, on a :
    Figure imgb0015
  • Dans ce cas, le changement de base permet de gagner une addition par rapport aux méthodes habituelles de multiplication parV2 : cette multiplication peut se faire à l'aide du circuit 32 de la Figure 11 et met en oeuvre deux additionneurs-soustracteurs 24 qui peuvent être de type simplifié ;
  • Le mot de code C(x) est coupé en huit parties de même longueur x0,... x8 qui sont redistribuées aux entrées des soustracteurs 24 "dans le code". Pour faciliter la lecture du schéma, les connexions ne sont pas indiquées, mais on voit que les mots appliqués aux entrées sont :
    • Premier soustracteur :
      Figure imgb0016
      Figure imgb0017
  • Deuxième soustracteur :
    • entrée + : sortie du premier additionneur
      Figure imgb0018
    Circuits extérieurs aux TNE et TNE 1
  • Le dispositif de traitement comporte, en plus des circuits de calcul de transformée, les circuits 12 et 14 (changement de base, codage et décodage) et le circuit de multiplication générale 10.
  • On donnera maintenant, à titre d'exemples, des circuits appropriés lorsque le changement de base tel que défini par la formule (2) est effectué en prenant f0= -1. Les circuits de changement de base et de codage peuvent alors être très simples, car les deux opérations n'en font plus qu'une seule, constituée par le passage du "complément à 2" sur la base habituelle des puissances de 2, au nombre codé et représenté dans la nouvelle base.
  • Les Figures 12 et 13 montrent deux circuits permettant d'effectuer le changement de base et le codage dans le cas où l'on s'impose que tous les signaux traités sont positifs. Cette condition peut aisément être remplie en additionnant une constante au signal d'entrée.
  • Le circuit montré en Figure 12 comporte un additionneur-soustracteur 24 auquel est appliquée une commande gO = 1, ce qui exclut l'utilisation du montage de la Figure 5a. L'une des entrées reçoit la grandeur X à coder sous la forme C(x). L'autre entrée reçoit, comme chiffres de poids fort, q zéros, comme chiffres de poids faible, les q chiffres de poids fort de X. La sortie de l'additionneur-soustracteur 24 fournit l'inverse de C(x), ce qui permet de récupérer C(x) par simple interposition d'inverseurs 34. On voit que ce circuit exige uniquement un additionneur-soustracteur, 2q inverseurs et une manipulation sur les bits de X. Le résultat est obtenu par addition de mots, "hors du code", et complémentation du résultat.
  • La variante de réalisation montrée en Figure 13 utilise un additionneur-soustracteur 24 qui peut, cette fois, être du type simplifié montré en Figure 5a. Elle comporte, comme éléments d'entrée, un jeu d'inverseurs 36 qui fournissent en sortie le complément de X. Ce complément est appliqué sur l'une des entrées de l'additionneur-soustracteur 24. L'autre entrée reçoit, en tant que chiffres de poids fort, q "un", en tant que chiffres de poids faibles, les q bits de poids fort du complément. Le résultat C(x) est alors obtenu directement en sortie de l'additionneur 24.
  • Le codage et le changement de base se ramèneraient simplement à une complémentation dans le cas où X est codé sur moins de q bits. Mais, du fait de l'adjonction d'une constante au signal d'entrée pour rendre X positif ou nul, cette condition ne sera généralement pas remplie.
  • Dans le cas où l'on s'impose que X est donné en complément à 2 sur q bits, ou moins, le codage et le changement de base constituent une seule opération qui est très simple : il suffit d'étendre X sur 2q bits, par propagation du bit de signe dans un registre, puis de complémenter le registre ainsi obtenu.
  • Les circuits permettant de passer du nombre codé dans la nouvelle base à un nombre codé en complément à 2 dans la base de départ (base des puissances de 2) peuvent également être réalisés de façon simple. Cette opération est effectuée par le circuit 14 sur le résultat C(y) de la transformée en nombre entier inverse TNE 1 sur la Figure 2.
  • Dans le cas où Y est un nombre binaire positif ou nul, le circuit peut être celui montré en Figure 14. Il comporte un jeu d'inverseurs 38 destinés à complémenter le signal d'entrée C(y) et un soustracteur classique 40. L'entrée + du soustracteur reçoit le complément de C(y). L'entrée - reçoit q zéros en tant que bits de poids fort, les quatre bits de poids fort du complément de C(y) en tant que bits de poids faible.
  • Dans la mesure où l'on veut disposer de Y sous forme de son complément à 2, le circuit peut être celui de la Figure 15. Il comporte un additionneur-soustracteur 42 présentant une entrée de fanion F qui permet deux modes de fonctionnement différents suivant que cette entrée est à zéro ou à 1. L'entrée + de l'additionneur-soustracteur 42 reçoit le complément à 2 du signal C(y) élaboré par des inverseurs 44. L'autre entrée reçoit q zéros en tant que bits de poids fort, la sortie d'un multiplexeur deux vers un 46 en tant que bits de poids faible. L'une des entrées du multiplexeur reçoit les bits de poids fort de C(y). l'autre le complément de ce nombre de q bits, élaboré par des inverseurs 48. Le bit de poids le plus fort de C(y), qui représente le signe, est appliqué à l'entrée F et à l'entrée de commande du multiplexeur 46.
  • Lorsque ce bit de signe est à zéro, ce sont les bits de poids fort de C(y) qui sont appliqués à la seconde entrée de l'additionneur-soustracteur 42 et l'opération effectuée consiste en l'addition de C(y) et des q bits de poids fort de C(y), affectés des poids faibles. L'additionneur-soustracteur est alors en mode addition.
  • Si au contraire le bit de poids fort de C(y) est égal à 1, la sortie du multiplexeur est constituée par le complément des bits de poids fort de C(y) et l'additionneur-soustracteur 42 fonctionne en mode soustraction. La sortie Y est alors constituée par la différence entre C(y) et les q bits de poids fort de C(y), affectés au poids faible.
  • D'autres variantes encore de réalisation des circuits de changement de base et de décodage sont possibles, utilisant l'addition-soustraction modulo M dans le code.
  • Les Figures 16 et 17 montrent deux autres circuits constituant des variantes de celui de la Figure 15, permettant également d'obtenir Y en complément à 2 à partir de C(y) et pouvant utiliser des additionneurs-soustracteurs élémentaires du genre de celui montré en Figure 3 et qui, selon l'état du fanion F, fournit sur sa sortie :
  • Figure imgb0019
    Figure imgb0020
  • Les opérations sont effectuées sur des nombres de 2q bits.
  • Dans le cas de la Figure 16, C(y) est appliqué sur l'entrée qui est soustractive pour F = 1 et le fanion est mis à 1. Le bit de signe de C(y) (bit de poids le plus fort) est appliqué comme entrée de retenue ri. Ce même bit de signe est appliqué en tant que valeur des q bits de poids fort à l'entrée additive de l'additionneur-soustracteur élémentaire.
  • Dans le cas de la Figure 17, c'est le bit de signe de C(y) qui est appliqué à l'entrée de fanion F.
  • L'opération effectuée par l'additionneur-soustracteur 20 est une addition lorsque le fanion F est à zéro, une soustraction lorsque ce fanion est à un. Si le bit de signe de C(y) est égal à 0, on obtient en sortie Y = C(y) avec les q bits de poids fort de C(y) ramenés aux poids les plus faibles de Y. La sortie du multiplexeur 50 est en effet alors l'entrée constituée par les q bits de poids fort de C(y).
  • Si au contraire le bit de signe de C(y) est égal à 1, Y est constitué par C(y) dont sont retranchés les q bits de poids fort de C(y), ramenés aux poids faibles. La sortie du multiplexeur est alors en effet dans ce cas celle qui reçoit les q bits de poids fort par l'intermédiaire d'inverseurs 52.
  • Enfin, le circuit 10 de la Figure 2, qui doit réaliser une multiplication générale, doit être prévu pour effectuer, terme à terme, N multiplications entre :
    • - les multiplicandes constitués par les N mots transformés des N mots entrants Xn,
    • - les N multiplicateurs constitués par les N mots transformés à partir des N mots entrants Hn.
  • Ces multiplications peuvent être réalisées en utilisant la technique, bien connue, d'additions et de décalages successifs. Mais il est plus avantageux d'utiliser les opérateurs simples déjà définis permettant la multiplication par toute puissance de 2 modulo M (Figures 8, 9 et 10) et ceux permettant la multiplication par V2 modulo M (Figure 11). Ce résultat peut être atteint par un processus de traitement qu'on peut qualifier de "méthode des additions-décalages généralisés" et qui sera maintenant décrit.
  • Lorsque l'on doit multiplier deux nombres X et H l'un par l'autre et que H est fixe, on décompose H en plusieurs termes :
    Figure imgb0021
  • Les termes de H peuvent être ordonnés sous la forme :
    Figure imgb0022
  • Le circuit peut alors être celui schématisé en Figure 18, où la partie haute correspond au premier terme de l'équation ci-dessus.
  • Il faut relever que K peut dans ce cas être beaucoup plus faible que dans une représentation sous forme d'un nombre binaire affecté d'un signe pour un calcul habituel.
  • L'invention est susceptible de très nombreuses variantes de réalisation, portant aussi bien sur la constitution des composants que sur leur association.
  • Dans tous les cas, les circuits élémentaires utilisés présentent une grande généralité : les additionneurs-soustracteurs modulo M précédemment décrits sont utilisables quelle que soit la valeur de f choi- sie. On dispose ainsi d'un bloc qui sera seul utilisé en dehors d'éléments courants. Seuls les circuits de codage-changement de base et de décodage-retour à la base de départ dépendent de la valeur choisie pour f . Aussi bien les additionneurs-soustracteurs que les éléments de décalage ne dépendent pas de la longueur de transformée totale. Ils dépendent uniquement du module M choisi. Seul sera modifié, en fonction de la longueur de transformée totale, le circuit permettant de recombiner les transformées de faible longueur, circuit constitué à partir de circuits de multiplication par 2 et par q2 dans le cas, qui sera le plus fréquent, où l'on prend 2 ou √2 comme racine Nième de l'unité modulo M.

Claims (12)

1. Dispositif de traitement en temps réel de signal numérique par convolution, comprenant un circuit multiplieur associé à des circuits à transformation en nombres entiers, à module M de la forme :
Figure imgb0023
sur chaque entrée et à un circuit à transformation inverse sur la sortie,
caractérisé en ce que chacun des circuits à transformation en nombres entiers (16) est précédé d'un circuit de changement de base arithmétique et de codage (12) et en ce que le circuit de transformation inverse est suivi d'un circuit de décodage et de retour à la base de départ (14), lesdits circuits étant prévus de façon qu'un nombre X modulo M dans la base d'origine en puissances de 2 corresponde, dans la nouvelle base, à un nombre
Figure imgb0024
f0 étant un entier compris entre 1 et M-1 et les coefficients fi et ej remplissant les conditions
Figure imgb0025
2. Dispositif selon la revendication 1, caractérisé en ce que chacun des circuits à transformation en nombres entiers (16) est constitué de plusieurs circuits fournissant chacun une transformée de longueur 3 ou 4 et d'un circuit de recombinaison des transformées de longueur 3 ou 4 pour atteindre la longueur totale de la transformée.
3. Dispositif selon la revendication 1 ou 2, caractérisé en ce que les circuits de transformation en nombres entiers utilisent un module M de la forme 2 2q -2q + 1 ; et 2 ou √2 comme racine primitive Nième de l'unité modulo M.
4. Dispositif selon la revendication 1, 2 ou 3, caractérisé en ce que les circuits de changement de base et de codage sont constitués par un circuit unique, f0 étant pris égal à -1 dans le changement de code.
5. Dispositif selon l'une quelconque des revendications précédentes, caractérisé en ce que les circuits de transformation en nombres entiers (TNE et TNE-1) ainsi que les circuits de décodage et de changement de base sont constitués par association d'additionneurs-soustracteurs élémentaires identiques modulo M permettant de réaliser au moins les fonctions addition- soustraction simple et addition puis addition de fo (dite addition "dans le code") ou soustraction puis soustraction de f (dite soustraction "dans le code"). 0
6. Dispositif selon la revendication 3, caractérisé en ce que le circuit de multiplication par √2 est constitué de façon à réaliser deux additions modulo M, dans le code.
7. Dispositif selon la revendication 3, caractérisé en ce que le circuit de multiplication par 2k est constitué d'un registre à décalage suivi d'un seul additionneur dans le code modulo M ou d'une seule addition simple modulo M, quelle que soit la valeur de k (Figure 8 ou 9).
8. Dispositif selon la revendication 1, 2 ou 3, caractérisé en ce que chaque circuit de transformation en nombres entiers de longueur N = 3 comprend sept additionneurs modulo M répartis en deux couches, les quatre additionneurs (22-1 à 22-4) de la première couche recevant des combinaisons différentes des bits de poids faible et de poids fort des trois nombres codés et amenés dans la nouvelle base (C(x ), C(x), C(x2)) tandis que les trois additionneurs de la seconde couche (22-5 à 22-7) reçoivent des combinaisons différentes des sortie.s de la première couche (Figure 6).
9. Dispositif selon l'une quelconque des revendications précédentes, caractérisé en ce que le circuit multiplieur (10), destiné à effectuer, terme à terme, N multiplications entre N mots C(-X) transformés de N mots entrants Xn et N multiplicateurs constitués de N mots transformés de -N mots entrants Hn, comporte des moyens (23) de multiplication des termes de la décomposition de Hn sur la base des puissances successives de √2 par C(X), des moyens additionneurs (22) recevant les sorties des moyens de multiplication, et un circuit (32) de multiplication par √2 des sorties des moyens additionneurs (Figure 18).
10. Dispositif selon l'une quelconque des revendications précédentes, caractérisé en ce que le circuit de décodage et de retour à la base de départ (14) comprend uniquement un additionneur-soustracteur (20) monté pour recevoir : sur une entrée soustractive la transformée C(y) à 2q bits ; sur une entrée de retenue le bit de poids fort constituant le bit de signe de la transformée C(y) ; sur les bits de poids fort de son entrée additive, ledit bit de signe ; sur les bits de poids faible de son entrée additive, les bits de poids forts de la transformée C(y) ; et fournissant sur sa sortie le nombre décodé et ramené dans la base de départ en complément à deux (Figure 18).
11. Dispositif selon la revendication 5, caractérisé en ce que chaque additionneur-soustracteur "hors du code" ou "dans le code" comprend uniquement des moyens pour effectuer une addition et des reports de retenue (Figure 4).
12. Dispositif selon la revendication 11, prévu pour traiter des nombres de 2q bits et fournir un nombre de 2q bits, caractérisé en ce qu'il comprend quatre additionneurs-soustracteurs simples (20-11 à 20-14) opérant sur 2 bits et montés de façon à recevoir des combinaisons différentes de bits de poids fort et de poids faible et des circuits NON-OU EXCLUSIFS de sortie.
EP85401858A 1984-09-24 1985-09-24 Dispositif de traitement en temps réel de signal numérique par convolution Withdrawn EP0175623A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
FR8414624 1984-09-24
FR8414624A FR2570853B1 (fr) 1984-09-24 1984-09-24 Dispositif de traitement en temps reel de signal numerique par convolution

Publications (1)

Publication Number Publication Date
EP0175623A1 true EP0175623A1 (fr) 1986-03-26

Family

ID=9307996

Family Applications (1)

Application Number Title Priority Date Filing Date
EP85401858A Withdrawn EP0175623A1 (fr) 1984-09-24 1985-09-24 Dispositif de traitement en temps réel de signal numérique par convolution

Country Status (4)

Country Link
US (1) US4788654A (fr)
EP (1) EP0175623A1 (fr)
JP (1) JPS6186872A (fr)
FR (1) FR2570853B1 (fr)

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2238893A (en) * 1989-12-08 1991-06-12 Philips Electronic Associated Convolution apparatus
GB2238892A (en) * 1989-12-08 1991-06-12 Philips Electronic Associated Convolution apparatus
CN112465130A (zh) * 2019-09-09 2021-03-09 脸谱公司 数论变换硬件

Families Citing this family (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5179529A (en) * 1989-03-31 1993-01-12 Hughes Aircraft Company High speed fourier transform engine
FI111592B (fi) * 2001-09-06 2003-08-15 Oulun Yliopisto Menetelmä ja laite peräkkäisten kuvien koodaamiseksi
US8500108B2 (en) * 2009-08-13 2013-08-06 John E. Rode Stackable belleville spring
WO2021238749A1 (fr) 2020-05-29 2021-12-02 Huawei Technologies Co., Ltd. Procédé et appareil de traitement de signal, et récepteur cohérent

Family Cites Families (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
FR2308143A1 (fr) * 1975-04-16 1976-11-12 Ibm France Dispositif generateur de fonction de convolution discrete et filtre numerique incorporant ledit dispositif
US4181968A (en) * 1978-06-14 1980-01-01 The United States Of America As Represented By The Secretary Of The Army Method and apparatus for forming convolutions of two complex number sequences using the fermat number transform
US4216475A (en) * 1978-06-22 1980-08-05 The United States Of America As Represented By The Secretary Of The Army Digital beam former

Non-Patent Citations (2)

* Cited by examiner, † Cited by third party
Title
IEEE TRANSACTIONS ON ACOUSTICS, SPEECH AND SIGNAL PROCESSING, vol. ASSP-22, no. 2, avril 1974, pages 87-97, IEEE, R.C. AGARWAL et al.: "Fast convolution using fermat number transforms with applications to digital filtering" *
SYSTEMS-COMPUTERS-CONTROLS, vol. 14, no. 1, janvier-février 1983, pages 29-38, Scripta Publishing Co., Silver Spring, Maryland, US; Y. MORIKAWA et al.: "Hardware realization of high-speed butterly for the maximal length fermat number transform" *

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2238893A (en) * 1989-12-08 1991-06-12 Philips Electronic Associated Convolution apparatus
GB2238892A (en) * 1989-12-08 1991-06-12 Philips Electronic Associated Convolution apparatus
CN112465130A (zh) * 2019-09-09 2021-03-09 脸谱公司 数论变换硬件

Also Published As

Publication number Publication date
FR2570853B1 (fr) 1987-01-02
JPS6186872A (ja) 1986-05-02
JPH03661B2 (fr) 1991-01-08
FR2570853A1 (fr) 1986-03-28
US4788654A (en) 1988-11-29

Similar Documents

Publication Publication Date Title
EP0265336B1 (fr) Opérateur polynomial dans les corps de Galois, et processeur de traitement de signal numérique comportant un tel opérateur
EP0204603B1 (fr) Circuit de calcul rapide de la transformée en cosinus, directe ou inverse, d&#39;un signal discret
EP0314559A1 (fr) Circuit de calcul utilisant une arithmétique résiduelle
FR2587819A1 (fr) Dispositif de calcul d&#39;une transformee de fourier discrete, glissante et non recursive, et son application a un systeme radar
EP0262032B1 (fr) Additionneur binaire comportant un opérande fixé, et multiplieur binaire parallèle-série comprenant un tel additionneur
EP0223657A1 (fr) Dispositif de calcul d&#39;une transformée de fourier discrète, et son application à la compression d&#39;impulsion dans un système radar
EP1368747A1 (fr) Procede et dispositif pour reduire le temps de calcul d&#39;un produit, d&#39;une multiplication et d&#39;une exponentiation modulaire selon la methode de montgomery
FR2793971A1 (fr) Multiplieur de nombres complexes
EP0437876B1 (fr) Multiplieur série programmable
EP0692762A1 (fr) Circuit logique de multiplication parallèle
EP0259231B1 (fr) Dispositif de détermination de la transformée numérique d&#39;un signal
EP0110767B1 (fr) Multiplieur binaire rapide
EP0175623A1 (fr) Dispositif de traitement en temps réel de signal numérique par convolution
EP0237382B1 (fr) Dispositif de transformée en cosinus d&#39;un signal numérique échantilloné
EP0206892A1 (fr) Procédé de traitement de signaux numérisés représentatifs d&#39;une image origine
EP0020185B1 (fr) Procédé et dispositif d&#39;addition, de manière parallèle-série d&#39;un grand nombre de mots
EP1071008B1 (fr) Procédé pour effectuer une multiplication avec accumulation dans un corps de Galois.
EP0327445A1 (fr) Multiplieur numérique généralisé et filtre numérique mettant en oeuvre ce multiplieur
EP0341097B1 (fr) Additionneur de type récursif pour calculer la somme de deux opérandes
EP0285495B1 (fr) Système de traitement numérique de signal à bancs de filtres
FR2585150A1 (fr) Multiplieur pour la multiplication de deux nombres complexes
EP1335277B1 (fr) Opérateur saturant à haute efficacité
CA2359198C (fr) Unite de calcul pour l&#39;execution d&#39;un protocole cryptographique
EP4170479A1 (fr) Circuit intégré comprenant un calculateur matériel et procédé de calcul correspondant
EP0241352A1 (fr) Circuit pour effectuer une transformation linéaire sur un signal numérique

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

AK Designated contracting states

Kind code of ref document: A1

Designated state(s): DE GB NL

17P Request for examination filed

Effective date: 19860806

17Q First examination report despatched

Effective date: 19890609

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWN

18D Application deemed to be withdrawn

Effective date: 19891220