US 4,974,186 AGrant
Generalized Digital Multiplier and Digital Filter Using Said Multiplier
Issue Date:1990-11-27
•6 Claims
•6 Drawing Sheets
Abstract
The multiplier according to the invention comprises N shift registers (RD.sub.O, . . . , RD.sub.N-1) containing the words x.sub.i on B bits, N conditional adders (AdC.sub.O, . . . , AdC.sub.N-1) each adding to the partial sum which they receive a constant coefficient (a.sub.1), conditional on the value of the bit (x.sub.i,j) which they receive from the associated register (RD.sub.1) and an adder accumulator (AdAc). The digital filter using such a multiplier also comprises a parallel word input register.
Metadata
Assignee
- Etat Francais Represente par le Ministere des Postes, des Telecommunication et de L'Espace (CNET)
Inventors
- Pierre Duhamel
- Zhijian Mou
- Michel Cand
Application Information
Application Number:US 3008843
Filing Date:1989-01-24
Priority Date:1988-02-02
Art Unit:231
Classifications
IPC:
G06F 750
Field of Search:
364750.5;724.16;728.01;728.03
Patent Drawings (6 sheets)
Description
Background of the Invention
1. Field of the Invention
The present invention relates to a generalized digital multiplier and a digital filter using said multiplier.
Discussion of Related Art
Digital multipliers are used in digital signal processing, in the calculation of quantities called "scalar products" (or sometimes "internal products") in the form: ##EQU1## In this expression, i designates a rank or order, the terms x.sub.i a group of N variable signals and terms a.sub.i a group of N given coefficients which are constant. Such products are in particular found in digital filtering.
In order to calculate the quantity defined by (1), use is sometimes made of a circuit as shown in FIG. 1. A multiplier 10 receives on a first input 12 successively x.sub.i and on a second input 14 successively a.sub.i. At its output 16, the multiplier successively supplies the products a.sub.i x.sub.i. An accumulator 18 has first and second inputs 20, 24 and an output 22 looped onto the second input 24. After N clock strokes (if i assumes all the integral values between 0 and N-1), the accumulator supplies the sought product P.
Another way of carrying out this operation consists of using a procedure called "distributed arithmetic". It firstly consists of breaking down the terms x.sub.i into their B bits: ##EQU2## in which j ranges between 0 (lowest order bit) and B-1 (highest order bit). This, shown in equation 1, involves a double summation: ##EQU3## In this operation, it is possible to reverse the order of the summations and write: ##EQU4## As the bits x.sub.ij can assume the value 0 or 1, each product a.sub.i x.sub.ij 2.sup.j, for j given, is equal either to 0 or to a.sub.i 2.sup.j. The sum f.sub.j of N such products is the sum of N terms, whereof each can assume two values. Therefore this sum can assume 2.sup.N different values. All these 2.sup.N values are determined and can be calculated beforehand because the a.sub.i are themselves determined and known.
Thus, the bracketed term in equation (3) is equal to one of the terms of this group of values and which is defined by the N bits x.sub.ij, in which the order j is fixed and the order i varies from 0 to N-1.
A multiplier for performing this procedure is in the form shown in FIG. 2. Shift registers R.sub.0, R.sub.1, R.sub.i, R.sub.N-1 with B cells, each contain the B bits of each word x.sub.i. A read only memory or ROM 30 of two words of m bits has N Inputs E.sub.1, E.sub.2 . . . , E.sub.i . . . , E.sub.N-1 connected to the respective outputs of the N registers R.sub.i. In said memory are placed the 2.sup.N possible values referred to hereinbefore for the partial products. Memory 30 has an output S connected to an adder-accumulator 34 with a first input 35, an output 36 and a second input 37. Output 36 is relooped onto the second input 37. A not shown clock times the shifting in the registers, the reading of the memory and the adder-subtractor.
When after a clock stroke a group of N bits x.sub.ij (j determined, i between 0 and N-1) is applied to the memory inputs E.sub.1. . . , E.sub.N-1, the memory is addressed by this group and supplies the corresponding product f.sub.j. It is then necessary to form the sum of these partial products, which is carried out by adder 34.
For simplification purposes, it is assumed hereinbefore that all the products to be added were positive, i.e. that only additions had to be carried out. However, in practice the considered numbers have a sign. Therefore the supplementary question arises as to the sign of the various manipulated quantities. However, the Expert knows how to solve this question (use of the two's complement binary code) and it is consequently unnecessary to go into detail about this here.
Another method for obtaining a scalar product is the use of a so-called "parallel multiplier" circuit. On having to multiply a term a by a term x to obtain the partial product Pr, as stated hereinbefore for (3), it is possible to break down x into its bits: ##EQU5## The product ax is consequently in the form: ##EQU6## The term X.sub.j is a bit equal to 0 or 1. The term a2.sup.j is a word shifted by j positions.
Thus, in material terms, the expression (4) represents the addition to the partial result obtained before order j of a word a shifted by j positions, conditionally with respect to the value of bit A.sub.j of order j of the binary representation of term a: ##EQU7## The general diagram of a parallel multiplier for 4 bit words (which corresponds in the present notation to N=4) is shown in FIG. 3. It comprises four adders Ad.sub.0, Ad.sub.1, Ad.sub.2 and Ad.sub.3, each constituted by four cells, whose structure is given in FIG. 4. A cell C comprises a first input 40 receiving a first bit, a second input 42 receiving a second bit, a hold input 44, a hold output 46, a propagation input 48 and a propagation output 50.
The four cells of the first adder Ad.sub.0 respectively form the products A.sub.0 X.sub.0, A.sub.1 X.sub.0, A.sub.2 X.sub.0 and A.sub.3 X.sub.0.
Adder Ad.sub.1 is shifted by one position to the left compared with adder Ad.sub.0. Its four cells perform the operation consisting of adding to the results supplied by the four cells of adder Ad.sub.0, the word a (A.sub.3 A.sub.2 A.sub.1 A.sub.0) shifted by one position to the left.
Finally, the multiplier has eight outputs P.sub.0 to P.sub.7 on which is found the result of the product of a by x.
Each adder of the multiplier of FIG. 3 can be diagrammatically represented in the manner shown in FIG. 5. A conditional adder Ad.sub.i comprises an input E.sub.i receiving a word to which is added the word a conditionally to the value of bit X.sub.i and supplies the result on output S.sub.i.
The block diagram of a parallel multiplier is consequently that of FIG. 6 with B conditional adders Ad.sub.0, Ad.sub.1 . . . Ad.sub.B-1.
In practice, as a is known, it is a question of carrying out an addition, whereof one of the operands (a) is known. This constant is broken down into bits (A.sub.0, A.sub.1 . . . A.sub.B-1) equal to 0 or 1, as a function of a known distribution. Thus, in advance, it is possible to produce specialized adders for each constant. For this purpose, it is merely necessary to adapt a conventional cell, like that of FIG. 4, in order to specialize it for the addition of a bit equal to 0 or 1. Therefore the complexity of the circuit is reduced by a factor almost equal to 2.
French patent application No. 86.13222 filed on Sept. 22 1986 describes two specialized addition cells of this type. This is illustrated by the attached FIGS. 7a and 7b. The addition cell of FIG. 7a comprises a data input x.sub.i receiving a bit, an inverter 50, a hold input C.sub.i, a switch 52 constituted by a P channel CMOS transistor 53 and a N channel CMOS transistor 55, an excusive OR gate 56 having an output S.sub.i, a N channel CMOS transistor 58 receiving a fixed potential V.sub.SS corresponding to logic state 1 and supplying a hold output signal C.sub.i+1. Transistors 53 and 55 respectively receive on their gates the bits X.sub.i and X.sub.i. Transistor 58 is controlled by the complement A.sub.i of bit A.sub.i.
The cell of FIG. 7b comprises the same elements, except that transistors 53 and 55 no longer receive X.sub.i and X.sub.i and instead receive X.sub.i and X.sub.i and that the P channel CMOS transistor 59 receives a fixed potential V.sub.dd corresponding to logic state 0.
The addition cells of FIGS. 7a and 7b are shown in the form of logic gates in FIGS. 8a and 8b. The addition cell of FIG. 8a is thus reduced to two logic gates, namely an exclusive OR gate 60 and an AND gate 62. Each gate receives on one input the bit X.sub.i and on the other input the hold bit C.sub.i. The AND gate 62 supplies the hold bit C.sub.i+1 and the exclusive OR gate 60 the sum bit S.sub.i.
The addition cell shown in FIG. 8b comprises an inverter 63, an exclusive OR gate 60 and an OR gate 64. Inverter 63 receives bit X.sub.i. Its output is connected to one of the inputs of the exclusive OR gate 60, whilst the other input receives the hold bit C.sub.i. The output of the exclusive OR gate 60 supplies the sum S.sub.i. Finally, OR gate 54 receives on its inputs bits X.sub.i and C.sub.i and supplies the hold bit C.sub.i+1.
Thus, a complete adder comprises addition cells like those shown in FIGS. 7a and 7b or 8a and 8b. These addition cells are connected in series, i.e. the hold output of one addition cell is connected to the hold input of the following addition cell.
FIG. 9 diagrammatically shows an adder of this type. It comprises a group of addition cells CA.sub.0, CA.sub.1, CA.sub.j, CA.sub.B-1, which are connected in series. Each addition cell receives a bit X.sub.j and has a specific structure, which is a function of the logic value of the bit A.sub.j of the fixed and known operand A.sub.B-1, . . . A.sub.1, A.sub.0.
In order to obtain an operational adder from said adder, it is necessary to add a multiplexer as shown in FIG. 10. In the latter, the conditional adder of order i, i.e. AdC.sub.i is constituted by an adder Ad.sub.i according to FIG. 9 and receives a partial sum S.sub.i from a multiplexer MX.sub.i having two inputs, one input e.sub.i being connected to the output of adder Ad.sub.i and the other e'.sub.i to the input of said same adder. This multiplexer has a control input ec.sub.i, which receives the bit X.sub.i, which is a conditional bit, as well as an output s.sub.i, which supplies a new sum S.sub.i+1. If the conditional bit X.sub.i is at 0, the multiplexer directly supplies S.sub.i "short-circuiting" adder Ad.sub.i, so that we obtain S.sub.i+1 -S.sub.i. If the conditional bit X.sub.i is at 1, the addition carried out in Ad.sub.i is taken into account and a new sum S.sub.i+1 differing from S.sub.i is obtained (S.sub.i+1 -S.sub.i +a.sub.i).
Such an adder can be used no matter what the sign of the two operands. In the case where the fixed operand is negative, it is merely necessary to choose the addition cells in such a way that this operand is represented in two's complement code.
The adder can also be used as a subtractor, it being sufficient in this case to interchange the addition cells of the first and second type which, as in the preceding case, amounts to adding the complement of the fixed operand and to wire the hold bit C.sub.0 to the logic value 1, which amounts to adding the fixed operand -B to the variable operand A.
A parallel multiplier, like that shown in FIG. 6, constituted by adders like that of FIG. 10 treating a fixed operand, therefore makes it possible to obtain a product of type ax. In order to obtain a quantity of form: ##EQU8## it is necessary to have a plurality of N multipliers of this type, each dedicated to one of the fixed operands a.sub.0 . . . a.sub.N-1 and each receiving the N terms X.sub.0 . . . X.sub.N-1. A final adder will give the scalar product P.
Although satisfactory in certain respects, these devices, no matter whether they are based on distributed arithmetic or parallel multipliers with a fixed operand, are complex and difficult to realize. Thus, although distributed arithmetic is well adapted when the length of the scalar products is limited (typically below 10) it becomes problematical beyond this, because the size of the memory increases exponentially with the length. For great lengths it is necessary to subdivide the memory into several submemories, whose partial results must then be summated. With regards the integrated circuit performing the operation, this will lead to a loss of a considerable part of the regularity of the etching design. As regards the solution with parallel multipliers, the control of the arrival of the different coefficients is difficult and the connections between the elements have prohibitive lengths on the integrated circuit.
Summary of the Invention
The present invention relates to a multiplier obviating these disadvantages.
It therefore recommends an adder, whose structure makes it possible to simplify the checking part. There is no longer any need to control the arrival of the coefficients (by buses, memories, sequencers, etc.) and prevent local connections, or at least reduce their length. The design of the corresponding integrated circuit is very repetitive, based on a very limited number of cells. The size of this design increases with N, but only in a linear manner therewith. Moreover, the flow rate of such a device can be adapted by introducing the necessary number of "pipeline" stages. The invention achieves this result through the use of a series bit, parallel word input device and an original multiplier circuit carrying out a parallel processing, the bit-series processing being carried out in an output accumulator.
More specifically, the present invention relates to a generalized numerical multiplier able to calculate a quantity P of form: ##EQU9## in which the terms a.sub.i are binary words corresponding to N given coefficients and the terms x.sub.i are binary words of B bits corresponding to N variable signals, said generalized digital multiplier being characterized in that it comprises: N shift registers with parallel word input on B bits and series bit output, the ith register containing the B bits of the binary word x.sub.i,
N conditional adders, each provided with a data input, a data output and a control input, the control input of the ith conditional adder being connected to the output of the ith shift register, the data input and the data output of the ith conditional adder being respectively connected to the data output of the (i-1) ith conditional adder and to the data input of the (i+1) ith conditional adder, said ith conditional adder incorporating the term a.sub.i and adding the latter to the signal received on its data input, conditionally with respect to the value of the jth bit x.sub.ij of the word x.sub.i, said bit being received on the control input,
an adder accumulator provided with first and second data inputs, the first data input being connected to the output of the Nth conditional adder, said adder accumulator also having a data output connected to the second data input of said adder accumulator following the shifting of the bits by one position,
a clock circuit for the control in parallel of the shifting of the B bits contained in the N series registers and passing the order j from 0 to B-1 and
the sought quantity P being supplied on the data output of the adder accumulator every B clock stroke.
The present invention also relates to a non-recursive digital filter implementing the multiplier defined hereinbefore for the calculation of an expression in form: ##EQU10## characterized in that it comprises:
a general input register with N registers of B bits, each register having a parallel input on B bits and a first parallel output on B bits, said registers being interconnected in parallel by said parallel inputs-outputs, each register also having a second parallel output,
a digital multiplier according to the aforementioned definition with a group of shift registers and a group of conditional adders, in which the parallel word input of the ith shift register is connected to the second output of the register of the same order i.
Brief Description of the Drawings
The features and advantages of the invention can be better gathered from the following description of non-limitative embodiments and with reference to the attached drawings:
FIG. 1 is a block diagram of a prior art circuit for calculating P;
FIG. 2 is a block diagram of prior art multiplier;
FIG. 3 is a block diagram of further prior art parallel multiplier;
FIG. 4 is a block diagram of a prior art adder cell;
FIG. 5 is a block diagram of a prior art conditional adder;
FIG. 6 is a block diagram of a further prior art parallel multiplier;
FIGS. 7a and 7b are block diagrams of prior art specialized addition cells;
FIGS. 8a and 8b are block diagrams of prior art logic gate cells;
FIG. 9 is a block diagram of a prior art adder;
FIG. 10 is a block diagram of a prior art multiplexer;
FIG. 11 is a block diagram of a group of conditional adders according to the invention.
FIG. 12 is the block diagram of the multiplier according to the invention.
FIG. 13 is a block diagram of a digital filter according to the invention.
FIG. 14 is a block diagram of a filter with a parallel structure.
Detailed Description of Preferred Embodiments
Returning to the problem to be solved, which is the calculation of the product: ##EQU11## it was shown hereinbefore that this product could be placed in the form: ##EQU12##
The expression in brackets can be written: ##EQU13## in which each of the variables u.sub.i can assume two different values. Thus, the function f.sub.j can assume 2.sup.N different values in accordance with the values of the N coefficients u.sub.i forming it, which is the very basis of the aforementioned distributed arithmetic.
According to the invention, function f.sub.j is calculated by a group of conditional adders and not with the aid of a ROM as was the case in the prior art. Such a group is shown in FIG. 11 with the convention already used relative to FIG. 5, namely a conditional adder of order i, designated AdC.sub.i, adds a.sub.i to the number which it receives, conditional on the value of the variable u.sub.i. The represented group comprises N adders of this type, namely AdC.sub.0. . . AdC.sub.N-1 and finally delivers the function f.sub.j defined by (5).
Such a circuit may appear similar to the prior art parallel multiplier, as illustrated in FIG. 6. However, two essential differences must be stressed. In the adder according to the invention, the constants to be added to each stage differ between the individual stages. It is for this reason that the inventors refer to this multiplier as being "generalized" as opposed to the prior art multipliers, which are to a certain extent specialized, because the constant to be added is always the same. There is no one position shifting between the individual stages (corresponding to multiplication by 2).
However, as a result of the structural similarity between the generalized multiplier according to the invention and the known parallel multiplier, all the variants which have been developed on the latter in order to improve the operating speed are applicable to the generalized multiplier according to the invention.
The generalized multiplier according to the invention can be in two different forms, as a function of whether use is made of specialized conditional adders in a predetermined addition, as described hereinbefore relative to FIG. 9, or whether use is made of a particular means as a loaded memory point prior to starting up the device for the appropriate value. The first mode is more compact than the second, but it remains specialized in a particular calculation and is shown in FIG. 12.
As shown, the generalized digital multiplier comprises:
N shift registers RD.sub.0, RD.sub.1 . . . RD.sub.i, RD.sub.N-1 with parallel word input on B bits and series bit output, the ith register RD.sub.i containing the B bits of the binary word x.sub.i,
N conditional adders AdC.sub.0, AdC.sub.1 . . . AdC.sub.i . . . AdC.sub.N-1, the ith adder having a data input ed.sub.i, a data output sd.sub.i and a control input ec.sub.i, the control input ec.sub.i of the ith conditional adder AdC.sub.i being connected to the output of the ith shift register RD.sub.i, the data input ed.sub.i and the data output sd.sub.i of the ith conditional adder being respectively connected to the data output of the (i-1) ith conditional adder and to the data input of the (i+1) ith conditional adder,
an adder accumulator AdAc provided with first and second data inputs Ed.sub.1, Ed.sub.2, the first data input Ed.sub.1 being connected to the output sd.sub.N-1 of the conditional adder of order N-1, the adder accumulator AdAc also comprising a data output Sd looped onto the second data input Ed.sub.2 of said same adder accumulator, but following a shift by one position (towards the right if the bits contained in the registers RD.sub.i have their lowest order leftmost and to the left in the opposite case), said shift being symbolized in FIG. 12 by a block designated DEC,
a clock circuit H for controlling the shifting of the bits contained in the N registers RD.sub.0 . . . RD.sub.N-1.
This multiplier functions as follows. The shift registers RD.sub.0 . . . RD.sub.i . . . RD.sub.N-1 contain the words x.sub.0 . . . x.sub.i . . . x.sub.N-1. For each clock stroke, the bits of these words are shifted by one position to the right. After j clock strokes on the N outputs of said registers are found the N bits of order j of the words x.sub.i, i.e. x.sub.0,j, x.sub.1,j, . . . x.sub.N-1,j. The conditional adders AdC.sub.0 . . . AdC.sub.i . . . AdC.sub.N-1 are able to add a word, respectively a.sub.0, a.sub.1 . . . a.sub.i . . . a.sub.N-1 to the word which they receive on their data input, conditional on the value of the bits x.sub.0,j, x.sub.1,j, . . . x.sub.i,j, . . . x.sub.N-1,j which they receive on their control input.
The final conditional adder AdC.sub.N-1 supplies the sum f.sub.j : ##EQU14## The adder accumulator AdAc adds to each f.sub.j the f.sub.j-1 which has been previously obtained but shifted to the right by one position (corresponding to a division by 2). Following N additions of this type, i.e. after B clock strokes, we obtain: ##EQU15## i.e. the sought scalar product P (cf. (1)).
In the circuit of FIG. 12, each conditional adder can be formed in the manner shown in FIG. 10.
This processing of the sign bit in all cases takes place in the same way as for distributed arithmetic: substraction of the partial result f(x.sub.0,B-1, x.sub.1,B-1, . . . x.sub.N-1,B-1) from the content of the accumulator in the case of using the two's complement code.
The multiplier described hereinbefore can be used for forming a non-recursive digital filter. It is known that such a filter is described by the equation: ##EQU16## in which a.sub.i are coefficients of the filter, x.sub.n-i words of order n-i, in which n is a fixed index and i a summation index. In other words, digital filtering of a sampled signal is the calculation of a sum of delayed and weighted samples.
It is easy to recognize in (6) a particular case of (1). The non-recursive digital filtering of equation (6) consequently amounts to the calculation of a scalar product, in which x.sub.i are x.sub.n-i.
A multiplier adapted to digital filtering will have the same structure as in the embodiment of FIG. 12, but the processed digital words would have a slightly different meaning: in the shift register RD.sub.i appears the word x.sub.n-i, with its B bits x.sub.n-i,B-1, . . . , x.sub.n-i,1, . . . , x.sub.n-i,0 and in the conditional adders are obtained the coefficients of the filter a.sub.0, a.sub.1 . . . a.sub.i . . . a.sub.n-1. Therefore the multiplier output will give the component of order n of the filtered signal, i.e. y.sub.n.
In order to obtain the following component y.sub.n+1, it is necessary to process the samples x.sub.n+1, x.sub.n. . . x.sub.n-i+1, i.e. shift by one order the set of samples. A complete filter must have a supplementary register able to receive N words representing the N samples necessary for filtering and this is shown in FIG. 13. The filter shown in the latter comprises a general input register 50, a group of shift registers 60, a group of conditional adders 70 and an adder accumulator AdAc.
The input register 50 comprises N registers REG.sub.n, REG.sub.n-1, . . . REG.sub.n-i, . . . REG.sub.n-N-1. All these registers have B bits and are loaded by words of B bits applied in parallel. The group of said N words consequently represents a "photograph" of the sampled signal, which is applied to an input 52.
Each of the registers REG loads one of the shift registers of block 60, the B bits being applied in parallel. Each word is then read by shifting, i.e. bitwise for the processing by block 70. Thus, when the final word x.sub.n has been introduced into 50, i.e. into the first register REG.sub.n, the filter can calculate the filtering component y.sub.n.
In order to define the operating frequencies of these various parts of such a filter, it is assumed that block 50 operates at a signal frequency f.sub.s (at the word), that the content of said block is recorded at frequency f.sub.r in block 60 (recording frequency) and that the shift registers (at the bit) of block 60 operate at frequency f.sub.c, which is the calculating frequency of block 70. The bits constituting the component y.sub.n are consequently obtained at speed Bf.sub.c.
A device characterized by:
will carry out a FIR-type filtering as described by equation (6). Thus, typically, with existing technology it is possible to obtain f.sub.c =25 MHz. Thus, for B=8 bits, a device can carry out a filtering at a rate of 3 MHz.
It is possible to realize a filter with an output subsampled by a factor M, i.e. in which all the samples are not calculated and instead one sample out of M is calculated, i.e. y.sub.n+M, Y.sub.n+2M, etc.
The following parameters can be chosen:
The filter according to the invention lends itself to a parallel structure, as illustrated in FIG. 14. The device shown comprises three filters F.sub.1, F.sub.2 and F.sub.3. Each filter has, as illustrated by FIG. 13, a word shifting block 50, a bit shifting block 60 and a calculating block 70. These blocks are allocated numbers 1,2 or 3 for filters F.sub.1, F.sub.2 and F.sub.3.
Filters F.sub.1, F.sub.2 and F.sub.3 have the same input E, in such a way that all the samples x.sub.n, x.sub.n-1, x.sub.n-2, etc. are applied to the registers 50/1, 50/2 and 50/3, which at a given instant contain the same words. However, the recording instants differ in the blocks 60/1, 60/2 and 60/3. When, at time t.sub.0, registers 50/1, 50/2 and 50/3 contain the sequence x.sub.n, x.sub.n-1, x.sub.n-2, etc. (i.e. at the instant corresponding to the notations of FIG. 14), the recording of register 50/1 takes place in register 60/1.
The recording in register 60/2 will only take place after a time interval T, i.e. at t.sub.0 +T, if T designates the sampling period corresponding to the frequency of signal f.sub.s. In other words, the recording in 60/2 will take place when the sample x.sub.n+1 has been introduced into the input registers 50/1, 50/2 and 50/3.
In the same way, at instant t.sub.0 +2T recording of the sample in block 60/3 takes place, i.e. at an instant when the last sample entered will be x.sub.n+2.
In such a structure, the calculating block 70/1 will supply a filtering coefficient y.sub.n. Following an interval T, block 70/2 will supply the coefficient y.sub.n+1 and after a new interval T, block 70/3 will supply coefficient y.sub.n+2. Block 70/1 then supplies a new coefficient y.sub.n+3, block 70/2 the coefficient y.sub.n+4, block 70/3 the coefficient y.sub.n+5, etc. All these coefficients will be combined (as a result e.g. of a three-state output) and will form the continuous sequence of filtering components.
Naturally, although the variant illustrated in FIG. 14 has three filters in parallel, this has only been given in an explanatory manner and the invention covers all filters with parallel structures, no matter what the number of subassemblies. In general terms, it is possible to place in parallel L filters subsampled in a ratio M and operating at recording instants or times shifted by Ts/L, if Ts is the period corresponding to the signal frequency Fs. With L=2, one obtains two filters F.sub.1 and F.sub.2 and it is possible to choose for each of these filters:
For f.sub.c =24 MHz, B=8 bits, we obtain f.sub.s =6 MHz and f.sub.s =3 MHz.
The phases of the two recording frequencies f.sub.r must be different and shifted by B/2f.sub.c.
Thus, in such parallel structure devices, only part 50 operates at the signal frequency f.sub.s. Therefore it is this part which will limit the possible rate by placing devices in parallel. All the other frequencies are of the order f.sub.c.
It is possible to choose the frequencies f.sub.c, f.sub.r, f.sub.s, in such a way that the sums y.sub.n are subsampled by a factor M times less than the sampling factor of a device.
It is therefore possible to obtain identical circuits, so that one of them produces the frequency f.sub.r and in turn supplies a sync signal enabling it to produce its own frequency f.sub.r, which is phase displaced and whereby the second device in turn supplies another sync signal and so on.
It is possible to recapitulate the different parameters involved in a parallel structure filter in the manner described hereinbefore:
L: number of circuits to be connected in parallel,
M: subsampling level,
f.sub.c : calculating frequency,
f.sub.s : signal frequency,
f.sub.r : recording frequency
E.sub.sync : sync input
S.sub.sync : sync output,
B: number of bits of the input signal,
DS: S.sub.sync -E.sub.sync =time lag between signals f.sub.r of two successive circuits.
All these parameters are in fact dependent on four fundamental data f.sub.c, f.sub.s, M, B, so that we obtain:
The first unconnectd sync input will indicate a non-shifted recording frequency, DS indicating the shift with the following circuit.
The subassembly [L, M, max(f.sub.c, f.sub.s)], (B naturally being known at the time of designing the circuit) supplies all the parameters permitting an easy generation of the other signals and also a simple use of the circuit. For example, it is possible to choose the following circuit:
f.sub.s 50 MHz, f.sub.c =25 MHz, B=8, M=1, N=40.
We obtain: L=16 circuits in parallel,
From the standpoint of the material realization of the circuit, each circuit has approximately 30,000 transistors in CMOS technology and 3 "pipeline" levels. Such a circuit can be used as a filter in a modem intended for artificial satellites.
A group of 16 identical circuits connected in a simple manner (identical inputs, identical outputs, quasi-identical controls) thus permits digital filtering at a 50 MHz sampling frequency.
It is obvious that the structure described hereinbefore have been diagrammatically represented so as to show their essential functions. In practice, i.e. in an integrated circuit performing these functions, it is possible to distribute these means in a different way, e.g. by interleaving or mixing them. Thus, the registers of part 50 could be brought closer to the registers of part 60 to facilitate the recording of the samples.
It is also possible to produce integrated circuits in such a way that the specification of the coefficients of the filter is only involved during the final masking operation. Thus, on request, it is possible to very rapidly produce a given filter on the basis of the previously obtained gate arrays.
Claims
We claim:
1. Generalized digital multiplier able to calculate a quantity P of form: ##EQU17## in which the terms a.sub.i are binary words corresponding to N given coefficients and the terms x.sub.i are binary words of B bits corresponding to N variable signals, said generalized digital multiplier being characterized in that it comprises: N shift registers (RD.sub.0, . . . RD.sub.N-1) with parallel word input on B bits and series bit output, the ith register (RD.sub.i) containing the B bits of the binary word x.sub.i, N conditional adders (AdC.sub.0, . . . , AdC.sub.N-1) each provided with a data input, a data output and a control input, the control input (ec.sub.i) of the ith conditional adder (AdC.sub.i) being connected to the output of the ith shift register, (RD.sub.i), the data input (ed.sub.i) and the data output (sd.sub.i) of the ith conditional adder (AdC.sub.i) being respectively connected to the data ouput of the (i-1) ith conditional adder and to the data input of the (i+1) ith conditional adder, said ith conditional adder (AdC.sub.i) incorporating the term a.sub.i and adding the latter to the signal received on its data input, conditionally with respect to the value of the jth bit x.sub.ij of the word x.sub.i, said bit being received on the control input (ec.sub.i), an adder accumulator (AdAc) provided with first and second data inputs, (Ed.sub.1, Ed.sub.2) the first data input (Ed.sub.1) being connected to the output (sd.sub.N-1) of the Nth conditional adder, (AdC.sub.N-1), said adder accumulator (AdAc) also having a data output (Sd) connected to the second data input (Ed.sub.2) of said adder accumulator (AdAc) following the shifting of the bits by one position, a clock circuit (H) for the control in parallel of the shifting of the B bits contained in the N series registers (RD.sub.0, . . . , RD.sub.N-1) and passing the order j from 0 to B-1 and the sought quantity P being supplied on the data output of the adder accumulator (AdAc) every B clock stroke.
2. Digital multiplier according to claim 1, characterized in that each conditional adder (AdC.sub.i) is constituted by an adder (Ad.sub.i), and a multiplexer (MX.sub.i) with two data inputs (e.sub.i, e'.sub.i) respectively connected to the input and output of the adder (Ad.sub.i) and a control input (Ec.sub.i) connected to the output of the shift register of the same order (RD.sub.i) and receiving a bit (x.sub.ij).
3. Non-recursive digital filter for the calculation of an expression in form: ##EQU18## in which the terms a.sub.i are binary words corresponding to N given coefficients and the terms x.sub.i are binary words of B bits corresponding to N variable signals, said filter comprising: a general input register with N shift registers (REG.sub.n, . . . , REG.sub.n-N+1) of B bits, each register having a parallel input on B bits and a first parallel output on B bits, said registers being interconnected in parallel by said parallel inputs-outputs, each register also having a second parallel output, said shift registers (REG.sub.n, . . . , REG.sub.n-N+1) operating at a frequency fs' and a digital multiplier comprising: N shift registers (RD.sub.0, . . . , RD.sub.N-1) with parallel word input on B bits and series bit output, the ith register (RD.sub.i) containing the B bits of the binary word x.sub.i, said parallel word input of a ith register (RD.sub.i) being connected to said second output of the ith register (REG.sub.i) of said general input register, said shift register (RD.sub.0, . . . , RD.sub.N-1) operating at a frequency f.sub.r, N conditional adders (AdC.sub.0, . . . , AdC.sub.N-1) each provided with a data input, a data output (ec.sub.i) of the ith conditional adder (AdC.sub.i) being connected to the output of the ith register, (RD.sub.i), the data input (ed.sub.i) and the data output (sd.sub.i) of the ith conditional adder (AdC.sub.i) being respectively connected to the data output of the (i-1)th conditional adder and to the data input of the (i+1)th conditional adder, said ith conditional adder (AdC.sub.i) incorporating the term a.sub.i and adding the latter to the signal received on its data input, conditionally with respect to the value of the jth bit x.sub.ij of the word x.sub.j, said bit being received on the control input (ec.sub.i), said conditional adders (AdC.sub.0, . . . , Adc.sub.N-1) operating at a calculating frequency f.sub.c, an adder accumulator (AdAc) provided with first and second data inputs, (Ed.sub.1, Ed.sub.2) the first data input (Ed.sub.1) being connected to the output (sd.sub.N-1), sid adder accumulator (AdAc) also having a data output (Sd) connected to the second data input (Ed.sub.2) of said adder accumulator (AdAc) following the shifting of the bits by one position, a clock circuit (H) for the control in parallel of the shifting of the B bits contained in the N series registers (RD.sub.0, . . . , RD.sub.N-1) and passing the order j from 0 to B-1 and the sought quantity P being supplied on the data output of the adder accumulator (AdAc) every B clock stroke.
4. Digital filter according to claim 3, wherein said f.sub.r =f.sub.s and f.sub.c =Bf.sub.s.
5. Digital filter according to claim 3, further including a means for operating with subsampling of a factor M and f.sub.r =f.sub.s /M and f.sub.c =BF.sub.s /M.
6. A digital filter comprising L filters (F.sub.1, F.sub.2, etc . . . ) in parallel, said L filters having a common input (E) receiving samples (x.sub.n, x.sub.n-1, etc.) at a signal frequency f.sub.s, each filter only recording the samples at a frequency f.sub.r =f.sub.s /L at different times between individual filters and shifted by (Ts/L), in which Ts designates the period corresponding to frequency F.sub.s, said filters having outputs being connected at a single output constituting an output of said digital filter, each filter calculating an expression in form: ##EQU19## in which the terms a.sub.i are binary words corresponding to N given coefficients and the terms x.sub.i are binary words of B bits corresponding to N variable signals, each filter comprising: a general input register with N shift registers (REG.sub.n, . . . , REG.sub.n-N+1) of B bits, each register having a parallel input on B bits and a first parallel output on B bits, said registers being interconnected in parallel by said parallel inputs-outputs, each register also having a second parallel output, said shift registers (REG.sub.n, . . . , REG.sub.n-N+1) operating at a frequency f.sub.s, a digital multiplier comprising: N shift registers (RD.sub.0, . . . , RD.sub.N-1) with parallel word input on B bits and series bit output, the ith register (RD.sub.i) containing the B bits of the binary word x.sub.i, said parallel word input of a ith register (RD.sub.i) being connected to said second output of the ith register (REG.sub.i) of said general input register, said shift register (RD.sub.0, . . . , RD.sub.N-1 operating at a frequency f.sub.r, N conditional adders (AdC.sub.0, . . . , AdC.sub.N-1) each provided with a data input, a data output and a control input, the control input (ec.sub.i) of the ith conditional adder (AdC.sub.i) being connected to the output of the ith register, (RD.sub.i), the data input (ed.sub.i) and the data output (sd.sub.i) of the ith conditional adder (AdC.sub.i) being respectively connected to the data output of the (i-1)th conditional adder and to the data input of the (i+1)th conditional adder, said ith conditional adder (AdC.sub.i) incorporating the term a.sub.i and adding the latter to the signal received on its data input, conditionally with respect to the value of the jth bit x.sub.ij of the word x.sub.j, said bit being received on the control input (ed.sub.i), said conditional adders (AdC.sub.0, . . . , AdC.sub.N-1) operating at a calculating frequency f.sub.c, an adder accumulator (AdAc) provided with first and second data inputs, (Ed.sub.1, Ed.sub.2) the first data input (Ed.sub.1) being connected to the output (sd.sub.N-1), said adder accumulator (AdAc) also having a data output (Sd) connected to the second data input (ED.sub.2) of said adder accumulator (AdAc) following the shifting of the bits by one position, a clock circuit (H) for the control in parallel of the shifting of the B bits contained in the N series registers (RD.sub.0', . . . , RD.sub.N-1) and passing the order j from 0 to B-1 and the sought quantity P being supplied on the data output of the adder accumulator (AdAc) every B clock stroke.