Digital filter generating a discrete convolution function

A device for generating the convolution function of two series of 4p discrete values {a.sub.n } and {b.sub.n }, where p is a prime number, characterized in that it includes:

• a. a first means including a pair of devices, each device receiving sequentially and in series by bit the terms {a.sub.n } or {b.sub.n } and providing as output the associated sets of terms ##EQU27## from said device receiving the {b.sub.n } terms wherein k takes all the integer values from 0 to p-1, the double parentheses ((--)) indicate that the enclosed quantity is to be taken modulo the Mersenne number M.sub.p = 2.sup.p -1 and the brackets <-->
• indicate that the enclosed quantity is to be taken modulo p;
• b. a pair of second means for providing cyclic access to said A.sub.i,k and B.sub.i,k terms provided by said devices of said first means;
• c. a pair of third means connected to said second means for alternately adding and subtracting by pairs the terms A.sub.i,k and B.sub.i,k respectively as received from the associated one of said second means wherein k successively takes all the integer values from 0 to p-1;
• d. a pair of fourth means each connected to one of said third means and each for computing one of the complex Mersenne transforms {A.sub.k } or {B.sub.k } of series {a.sub.n } or {b.sub.n }, from the terms provided by said third means;
• e. a fifth means connected to the one of said fourth means computing the transform {B.sub.k } for multiplying terms B.sub.k by a given constant value q;
• f. a sixth means connected to said fourth and fifth means for multiplying term by term, the terms A.sub.k provided by the {A.sub.k } one of said fourth means with the corresponding terms provided by said fifth means to supplying a sequence of terms C.sub.k ;
• g. a seventh means connected to said sixth means for sequentially receiving in series by bit, the terms C.sub.k provided by said sixth means, and including a device computing by successive accumulations, the following terms:
• ##EQU28## for the values of m comprised between zero and p-1;
• h. an eighth means for providing cyclic access to successive ones of the terms c.sub.i,m generated by said seventh means;
• i. a ninth means for alternately adding and subtracting pairs of the terms c.sub.i,m made accessible by said eighth means;
• and
• j. a tenth means connected to said ninth means for computing the real and imaginary components of the inverse Mersenne transforms of terms C.sub.k from the terms provided by said ninth means.

A digital filter with filtering coefficients {b.sub.n } characterized in that it includes:

• a first means for separating the input signal samples into blocks of 2p samples;
• a pair of second means each for appending a sequence of 2p consecutive zeroes to alternate blocks of 2p samples;
• a third means including a pair of convolution functions generators, each connected to one of said second means to receive therefrom alternate ones of said blocks of 2p samples with an appended sequence of zeroes and forming a sequence of terms representing a convolution of said blocks of samples with appended zeroes;
• and
• a fourth means connected to both said convolution function generators of said third means to add sequentially the terms provided by said function generators.

A digital filter with filtering coefficients {b.sub.n } characterized in that it includes:

• a first means for separating samples of an input signal into blocks of 2p consecutive samples and having a pair of outputs, each supplying alternate blocks of said samples;
• a second means comprising a first and a second complex Mersenne converter, one connected to each of said outputs of said first means and each of said converters including:
• a. a means for appending a sequence of 2p zeroes to each of said blocks of samples;
• b. an input storage device for recirculating the input data;
• c. an accumulator and shift register assembly receiving said recirculated data and
• d. an adder-subtractor fed by said shift register;
• each converter generating a transformed sequence of said samples;
• a memory containing amplified complex Mersenne transforms of said filtering coefficients;
• a pair of multiplying means fed by said memory and each multiplying means also connected to one or the other of said first and second converters;
• a pair of adding means connected to the outputs of said multiplying means, one of said adding means for adding the real components of the outputs of said multiplying means, and the other adding the corresponding imaginary components of said outputs;
• an inverse complex Mersenne converter connected to the outputs of said pair of adding means, said inverse converter including:
• a recirculation device,
• an accumulator and shift register assembly connected to said recirculation device and,
• an adder-subtractor combining the real terms provided by said shift register assembly.

A digital filtering device characterized in that it includes:

• a first means for separating the samples of the signal to be filtered into blocks of 2p samples where p is a prime number;
• a second means for appending to each block a sequence of 2p zeroes, thus forming blocks a.sub.n of words;
• a third means responsive to said first and second means for retaining two consecutive blocks a.sub.n and a.sub.n +4p;
• a fourth means having an input from said third means and for providing terms {A.sub.k } and {A.sub.k } representing the real and imaginary terms respectively of the complex Mersenne transforms of the series of blocks {a.sub.n } and {a.sub.n +4p};
• a fifth means for storing the Mersenne transform {B.sub.k } of a group of amplified coefficients of {b.sub.n } defining the filter with a gain q;
• a sixth means receiving said terms of both of said transforms and for producing, term by term, the products of qA.sub.k.B.sub.k and qA.sub.k.B.sub.k ;
• a seventh means connected to said sixth means for adding these products term by term;
• and
• an eighth means receiving said terms from said seventh means and providing the inverse complex Mersenne transforms of said terms as a digital representation of a filtered input signal.