Browse Prior Art Database

Discrete Transforms Filter

IP.com Disclosure Number: IPCOM000085665D
Original Publication Date: 1976-May-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 4 page(s) / 70K

Publishing Venue

IBM

Related People

Nussbaumer, H: AUTHOR

Abstract

It is well known that digital filters can be implemented by using discrete transforms. In such approaches the digital filtering process, which is an aperiodic convolution is first transformed into a succession of periodic convolutions by segmenting the signals into blocks and operating via the overlap-save or the overlap-add method. The periodic convolutions are then implemented by taking the transforms (DFT, Fermat, Mersenne) of the signal and tap blocks, multiplying the transformed points and taking the inverse transform of the products.

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 51% of the total text.

Page 1 of 4

Discrete Transforms Filter

It is well known that digital filters can be implemented by using discrete transforms. In such approaches the digital filtering process, which is an aperiodic convolution is first transformed into a succession of periodic convolutions by segmenting the signals into blocks and operating via the overlap-save or the overlap-add method. The periodic convolutions are then implemented by taking the transforms (DFT, Fermat, Mersenne) of the signal and tap blocks, multiplying the transformed points and taking the inverse transform of the products.

In order for this approach to yield significant computation savings, transforms must first be used that can be computed with a minimum of operations. In this respect, the use of the fast Fourier transform has been first proposed. More recently, Mersenne and Fermat transforms have been shown to be very promising for low-cost implementation of digital filters.

Another way to enhance the computing efficiency of digital filters implemented via discrete transforms, is to improve the process by which the aperiodic convolution is transformed into a succession of periodic convolutions.

The purpose here is to describe an approach that achieves this goal by allowing reduction of the number of transforms required to implement a given filtering process, and by making it possible to operate economically with transforms of shorter length than with the conventional overlap-save and overlap- add approaches. This last point is especially important when Mersenne and Fermat transforms are used, because in that case word length is directly related to transform length.

The overlap methods have one main drawback : the periodic convolution length and, therefore, the transform length is L+N-1 for blocks of data of length N. This means that a lot of computation in evaluating the transforms is wasted for the sole purpose of eliminating interferences between blocks.

This translates into the fact that when computing the transforms, the sequence to be transformed contains either a large number of 0's or redundant information.

Another problem with the two conventional approaches is that for an L taps filter, the optimum block size is L log(2) L. In other words, in order to have good efficiency in segmenting a digital filtering process into circular convolutions, the signal must be segmented into large blocks. However, when Fermat or Mersenne transforms are used, the word length is proportional to transform size. In that case, the designer is faced with the problem of either using large blocks thereby having efficient segmentation but inefficient transforms or the reverse.

To improve this situation, consider an L taps filter with tap values a(o), a(1) ... a(L-1) and an input signal sequence x(n). Now segment the input signal into blocks {x(n)} of length N. N > L.

Now perform the circular convolutions on blocks of length N, the tap blocks being obtained by appending N - L 0's to the L taps values.

1

...