Browse Prior Art Database

Digital Filtering using Pseudo Fermat Transforms

IP.com Disclosure Number: IPCOM000086066D
Original Publication Date: 1976-Jul-01
Included in the Prior Art Database: 2005-Mar-03
Document File: 3 page(s) / 41K

Publishing Venue

IBM

Related People

Nussbaumer, H: AUTHOR

Abstract

With the growing number of digital filtering applications, efficient implementation of digital filters is a matter of increasing importance. Discussed here is the use of some finite field transforms as a way to improve efficiency in digital filter computation.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 3

Digital Filtering using Pseudo Fermat Transforms

With the growing number of digital filtering applications, efficient implementation of digital filters is a matter of increasing importance. Discussed here is the use of some finite field transforms as a way to improve efficiency in digital filter computation.

Direct computation of a nonrecursive digital filtering process corresponds to a continuous convolution, and requires N multiplications and N-1 additions per output sample for an N-taps filter. This processing workload can be drastically reduced by computing the convolution with discrete Fourier transforms (DFT).

In such an approach, the continuous convolution is transformed into a series of circular convolutions by dividing the input sequence into blocks, to which a suitable number of 0's are appended as in the conventional overlap-add, overlap- save approaches. The circular convolutions can then be computed by using discrete Fourier transforms evaluated via a fast Fourier transform algorithm (FFT).

With this technique, the bulk of the processing workload corresponds to evaluating the fourier transforms and is proportional to N log(2) N instead of N(2).

Recently, Rader in IEEE Transactions on Computers C21-1269 (1972), Agarwal and Burrus in IEEE Transactions on Acoustics, Speech and Signal Processing ASS P 22-87 (1974), and in Proceedings IEEE 63-550 (1975), have proposed to replace Fourier transforms by Mersenne and Fermat transforms to implement digital filters. These two transforms, which have the convolution property, can be computed without multiplications and are, therefore, potentially much more efficient than the DFT for the evaluation of convolutions.

Their main drawback is that, because all operations are performed in a finite ring of integers with arithmetic carried out modulo p, there is a rigid relationship between transform length and word length. Moreover, and particularly in the case of the Fermat transform, there is only a very limited choice of possible word lengths so that a significant amount of computing power may be wasted, by operating on word lengths much longer than would be required to achieve a given precision on the final result.

Defined here is a complex pseudo Fermat transform which is well adapted for filtering complex signals, and allows increased transforms and convolution lengths when compared to conventional Fermat transforms.

Let p be an integer equal to 2q + 1 and let its prime factorization be: p = p(1)/d(1)/ . p(2)/d(2)/ .... p(i)/d/i// where p(1), p92), .. pi are prime integers.

Define a 4M complex pseudo Fermat transforms Ak of a sequence of integer values {a(n)} where:

(Image Omitted)

and an inverse transform:

1

Pag...