Digital filter

• US 4,062,060 A
• Filed: 11/01/1976
• Issued: 12/06/1977
• Est. Priority Date: 11/10/1975
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Nussbaumer, Henri J.
• Primary Examiner(s): Smith, Jerry
• Application Number:
  US05/737,631
• Time in Patent Office: 400 Days
• Field of Search: 235/152, 235/156, 328/167, 333/18, 333/28 R, 333/70 T
• US Class Current: 708/315
• CPC Class Codes: G06F 17/156 using a domain transform, e.g. Fourier transform, polynomial transform, number theoretic transform
• CPC Class Codes: H03H 17/0211 using specific transformation algorithms, e.g. WALSH functions, Fermat transforms, Mersenne transforms, polynomial transforms, Hilbert transforms correlation computation G06F17/156

Abstract

The invention covers a precision digital filter for signal samples represented in a digital form. The flow of samples x_o, x₁, x₂, . . . x_n, of the signal is split into blocks of a fixed length which are simultaneously transmitted to two circular convolution generators operating to different prime number modulos. The outputs of the generators are each submitted to a correcting device and the corresponding corrected terms are added. The added terms are each then added to a delayed prior term to generate representations of samples of a filtered signal.

Claims

1. A digital filter for a series of samples of a signal, said filter characterized in that it includes:

an input to which the samples of the signal to be filtered are applied;

an input control means for separating said samples into data blocks of a fixed length;

at least two different circular convolution generators, each having an input receiving each of said data blocks and generating the terms resulting from the circular convolution of the samples of each said block with an associated block of coefficients defining the required filtering operation of the generator;

a product means for each circular convolution generator for multiplying the output of the associated one of said generators by a correcting term specific to the attached generator;

an adder for adding together the corresponding terms in the outputs of said two product means; and

a means for combining selected ones of the terms supplied by said adder to produce a series of samples representing the filtered signal.

2. A digital filter for a series of digitally represented samples of a signal, said filter characterized in that it includes:

an input to which said digitally represented samples of the signal to be filtered are applied;

a control means for separating said digital samples into data blocks of a fixed length;

at least two different circular convolution generators, each having an input receiving each of said data blocks and generating the terms resulting from the circular convolution of each of said blocks when expanded with a sequence of a fixed number of zero terms, with an associated similar sized block of coefficients expanded with the same sequence of a fixed number of zero terms and defining the required filtering operation;

a product means for each convolution generator for multiplying the output of the associated one of said generators by a correcting term specific to the attached generator;

an adder means for adding together corresponding terms in the outputs of said product means; and

a means for sequentially generating digital representations of samples of a filtered signal by adding together selected ones of the terms in the output of said adder means which terms result from the processing of two consecutive input data blocks.

3. A digital filter as in claim 2 further characterized in that each of said two circular convolution generators is comprised of:

a Mersenne transform generator operating upon the blocks of digital values wherein each digital value is representative of a sample of the signal to be filtered;

a memory containing the Mersenne transforms of the coefficients of the desired filter function of the convolution generator with each coefficient being multiplied by a constant factor;

a multiplier means for receiving the terms of data and coefficient transforms from said generator and said memory to generate term-by-term products of said transforms; and

means receiving said product terms for effecting the inverse Mersenne transform of the terms supplied by said multiplier.

4. A digital filter for a series of samples of a signal to be filtered, said filter characterized in that it includes:

an input to which said samples of the signal to be filtered are sequentially applied;

a control means for sequentially splitting the flow of said samples into data blocks of a fixed length;

at least two different circular convolution generators, each generator having an input receiving each of said data blocks and generating the terms resulting from the circular convolution of said received blocks with an associated block of filter coefficients expanded to a given length with a sequence of zero terms;

a product means for each generator for multiplying each of the output terms of each of said generators by a correcting term specific to said generator;

a summing means for addition of corresponding terms in the outputs of said product means; and

an output means for sequentially generating digital representations of samples of the desired filtered signal by selecting some of the terms supplied by said summing means.

5. A digital filter for a series of digitally represented samples of a signal, said filter characterized in that it includes:

an input to which the digital representations of the samples of the signal to be filtered are sequentially applied;

a control means for sequentially separating said representations of said samples into data blocks with a fixed number of samples in each data block;

a first circular convolution generator performing a data converting operation according to the Mersenne transform and generating output terms to a prime number (p) modulo;

a second circular convolution generator also operating according to the Mersenne transform to generate output terms to a second prime number (r) modulo;

a data transfer means for simultaneously applying each of said data blocks to said first and second generators;

a product means for each generator, each product means multiplying the output of the associated one of said generators by a correcting term specific to the associated generator and supplying its product terms to the modulo of its associated generator;

a summing means for term-by-term addition, modulo p·

r, of the corresponding terms supplied by said two product means; and

an output means for generating digital representations of samples of the desired filtered signal by combining the terms supplied by said summing means.

6. A digital filter for a series of representaions of samples of a signal to be filtered, said filter characterized in that it includes:

an input to which the representations of samples of the signal to be filtered are sequentially applied;

control means for sequentially separating said series of samples into blocks of (q+1/2) samples, q being a prime number;

a first device for generating the terms of a Mersenne transform;

means for introducing each of said data blocks into said first device for generating the terms of the Mersenne transform A_K¹ modulo p, of each of said data blocks wherein each of said data blocks has appended thereto a series of (q-1/2) zero terms, where p is a prime number equal to 2^q -1;

a second device for generating the terms of a Mersenne transform;

another means for introducing each of said data blocks into said second device for generating the Mersenne transform A_K², modulo r, of each of said data blocks wherein each block has appended thereto a series of (s - (q+1/2) zero terms, where r is a prime number equal to 2^s -1,;

a memory containing the sets of terms ((1/rq) B_K¹ )_modulo p and ((1/ps) B_K²)_modulo r which terms represent the coefficients of a desired filtering operation expanded with (q-1/2) and s - (q+1/2) zero terms, respectively;

a first means for multiplying, modulo p, the terms A_K¹ from said first Mersenne transform device by the corresponding terms of the set of terms ((1/rq) B_K¹)_modulo p

a second means for multiplying, modulo r, the terms A_K² from said second Mersenne transform device by the corresponding terms of the set of terms ((1/ps) B_K²)_modulo r

a third means for generating, modulo p, the terms of the inverse Mersenne transform of each of the output terms from said first multiplying means;

a fourth means for generating, modulo r, the terms of the inverse Mersenne transform of each of the output terms from said second multiplying means;

a pair of delay means, one for each of said third and fourth means, to buffer for s and q sample times, respectively, the output terms supplied by said third and fourth means;

a first subtraction means for subtracting the terms supplied by said third means from those which have been buffered for s sample times;

a second subtraction means for subtracting the terms supplied by said fourth means from those which have been buffered for q sample times;

a summer for adding, modulo p.r, the corresponding terms supplied by said first and second subtraction means; and

means for adding consecutive ones of the terms resulting from the addition modulo p.r in said summer to generate output terms representing samples of a desired filtered signal.

7. A digital filter for a series of samples of a signal, said filter characterized in that it includes:

an input to which the samples of the signal to be filtered are sequentially applied;

a control means for separating said series of samples into data blocks of a fixed length;

a circular convolution generator having an inut receiving each of said data blocks and generating representations of the terms resulting from circular convolutions between the samples in each data block and a block of coefficients defining the desired filtering operation;

timing means for utilizing said circular convolution generator at least two consecutive times for each of said data blocks;

a product means for multiplying each term in the output of said circular convolution generator by an associated correcting term;

a summing means for adding each output term supplied by said product means to a delayed previously generated term; and

an output means for combining consecutive terms in the output of said summing means to generate a sequence of terms representing a series of samples of the desired filtered signal.