Technology

Introduction | The Gibbs Phenomenon | The Pan Filter | Conclusion

INTRODUCTION

For most applications, filtering directly in the Frequency Domain is the simplest and fastest way to digitally filter a signal.

Figure 1: A direct Frequency Domain filter, also known as a Fourier Filter
Figure 1: A direct Frequency Domain filter, also known as a Fourier Filter

Time Domain input data is transformed into the Frequency Domain using a Fast Fourier Transform (FFT), filtered directly in the Frequency Domain by passing or amplifying desired frequencies and zeroing out unwanted ones, and inverse transformed back into the Time Domain using an Inverse Fast Fourier Transform (IFFT). The outputs of the IFFT are then concatenated together if necessary. Direct Frequency Domain filtering is NOT fast convolution (which also uses the FFT & IFFT to filter the signal in conjunction with the Overlap Add and Overlap Save algorithms). Direct Frequency Domain filters are also known as Fourier Filters.

Let us first compare a Fourier Filter with a conventional Finite Impulse Response (FIR) filter. Both are linear filters — this means that the outputs of both filters are stable and scale linearly with the input. (Non-linear filters such as Infinite Impulse Response (IIR) filters are not stable and thus are outside the scope of this discussion.)

Here is a typical FIR filter:

Figure 2: A FIR filter implemented with Time Domain convolution
Figure 2: A FIR filter implemented with direct convolution

We note that FIR filters have many weaknesses:

  • FIR filters are not simple to design

    Figure 3: Frequency Domain characteristics of a low pass FIR filter
    Figure 3: Frequency Domain characteristics of a low pass FIR filter

    • All practical FIR filters have loss characteristics, as seen in the figure above. These loss characteristics can be reduced by increasing the number of taps or coefficients of the filter, but can never be totally eliminated.
    • In addition to having to worry about how many taps you need to use for the filter, there are many different ways to design a FIR filter, with the most popular being the Parks-McClellan algorithm. Successfully designing a FIR filter requires much expertise in the field of digital filter design.
  • The FIR filter is a "laggy" filter, and this lag is intrinsic to the algorithm:
    • As you can see in figure 2, each input to the filter is delayed by the number of taps of the filter. These delayed values are then used in the formation of the output of the filter. This is the “lag” intrinsic to the filter: the lag is the delay between when data is first input to the filter and when the data passes entirely through the filter and is fully filtered.
    • The better the FIR filter, the more taps it has, and the longer the lag.
    • With certain applications, this algorithmic lag is not desirable. Fourier Filters, on the other hand, do not have this algorithmic lag.
  • The beginning and end of the output of a FIR filter needs to be thrown away:
    • Due to the nature of convolution, the beginning and end of the input signal to the FIR filter is not fully filtered and this results in end transients in the output of the filter. These end transients are typically thrown away.
    • This presents a catch-22 situation — higher performing FIR filters have more taps and thus longer end transients, and there is a correspondingly higher amount of data loss in the output of the filter.
    • For some applications the amount of input data to filter is limited. This presents a challenge in designing a filter for these types of applications; you want to keep as much of the filter output as possible and yet still be able to design a well performing filter.
  • FIR filters cannot implement some types of filters:
    • Complex filters (arbitrary magnitude, multi-band, single frequency pass/reject, etc.) are hard to practically implement with FIR filters.
  • FIR filters are not simple to implement, and better performing FIR filters are costly:
    • There are two ways to implement a FIR filter. The first is through direct convolution in the Time Domain, and the second is through fast convolution in the Frequency Domain using the Overlap Add or Overlap Save algorithms. Sometimes an intensive resource usage analysis needs to be completed in order to determine the best way to implement the FIR filter.
    • A decent performing FIR filter has many taps, which makes it slow and consume a lot of resources. To implement larger FIR filters more efficiently, the fast convolution algorithm is used, but can still be slow and costly.
  • A FIR filter requires the offline regeneration of its filter coefficients. There are several drawbacks to this:
    • Every time the filtering requirements change, a new filter must be designed and regenerated, and oftentimes with a costly and complicated filter design program.
    • Multiple FIR filter implementations are needed for multiple filter designs. This may consume a lot of resources.
    • If the filter is implemented on hardware, new filter coefficients must be reloaded onto the hardware each time the filter design changes. If reloading is not possible, the filter must be fixed and cannot change after a certain point in the project.

In contrast, FFT filters do not have any of the weaknesses of FIR filters:

  • FFT filters are easier to design than FIR filters:
    • There is no need to worry about the loss characteristics of the pass, stop, or transition bands, the number of taps of the filter, or which algorithm to use. The design methodology of a Fourier Filter is much simpler as there are far fewer design tradeoffs to worry about (size of the FFT/IFFT, etc.).
    • In fact, Fourier Filters are simple enough for any novice to pick up and use; a PhD in filter design is no longer required. Much design time and engineering man-hours can be saved.
  • As will be shown later, a perfect Fourier Filter (the Pan Filter) does not have lag and contains no beginning and end transients in its output:
    • A perfect Fourier Filter fully filters the entire input signal; none of its output is lagged or needs to be thrown away. There is no need to worry about the trade-off between filter performance and how much data needs to be thrown away. This is especially useful for applications where limited amounts of input data are available.
  • Fourier Filters can implement any type of filter, including ones that FIR filters cannot:
    • The filters created by FFT filters are near-ideal (as shown in the Demos section of this website). Because of this, extremely complex filters like multi-band, arbitrary magnitude, and single frequency pass/reject can easily be implemented. You can realize incredibly steep transitions, extreme stopband attenuation, and also perform special operations like moving frequencies up or down or turning an upper sideband into a lower sideband. These types of filters are almost impossible to implement through conventional means.
  • Fourier Filters are simpler to implement than FIR filters, and high performing filters are much faster and less costly to implement:
    • Simplicity is good — there is only one way to implement a Fourier Filter, and that's in the Frequency Domain. There is no need to perform a complicated analysis of whether or not to implement the filter in the Time Domain or the Frequency Domain.
    • Fourier Filters are fast, sometimes much faster than a comparably performing FIR filter. This is because the FFT and IFFT are extremely efficient. If L is the length of the signal that needs to be filtered, a FFT or IFFT uses on the order of L*log2L multiplications whereas an N tap FIR filter implemented with direct convolution needs L*N multiplications.
    • This is exactly why fast convolution (which uses the FFT & IFFT) is much faster than direct convolution for larger FIR filters: the longer and more complex the filter is, the more efficient its Frequency Domain implementation. Using the same reasoning, Fourier Filtering can create better filters than FIR filters implemented with direct convolution after a certain FIR size.
    • Since both fast convolution and Fourier Filters are faster than direct convolution after a certain FIR size, we then need to compare fast convolution with Fourier Filtering.
      • Fast convolution is implemented in the Frequency Domain using FFTs & IFFTs and the Overlap-Add & Overlap-Save algorithms. The amount of overlap used is roughly equal to the number of taps of the FIR filter. A larger FIR filter requires more overlap, and thus is slower and has a much lower per FFT data throughput.
      • As will be shown, Fourier Filters have a much higher per FFT data throughput than fast convolution if the same FFT/IFFT size is used for both algorithms and comparable performance is desired. Thus Fourier Filtering is faster than fast convolution.
      • Additionally, smaller FFTs & IFFTs are needed with Fourier Filters than with fast convolution to achieve the same level of performance. Consequently, Fourier Filters have much less latency than a comparable FIR filter implemented with fast convolution.
    • The bottom line is that the filters created directly in the Frequency Domain are near-ideal and can be implemented at a fraction of the cost of comparable FIR filters that give a similar level of performance.
  • Fourier Filters do not require the offline regeneration of filter coefficients:
    • Fourier Filters are not derived through mathematical approximation, and thus have no filter coefficients; . a new filter can be designed by just changing the filter band limits. As a result, filters implemented directly in the Frequency Domain can be changed immediately and on the fly. There is no need to purchase expensive filter design software or waste time calculating new filter coefficients every time you want to implement a new filter.
    • Only one FFT/IFFT pair is needed to implement any and all digital filters in the system (whereas multiple implementations are required for FIR filters). The advantage of this is that only one design needs to be tested (instead of multiple designs for FIR filters). You also save valuable computational resources; the same FFT/IFFT pair can be reused to implement all the filters in the system. In addition, multiple copies of the same FFT/IFFT pair can be instantiated throughout the system to implement different filters.
    • Furthermore, filter coefficients do not need to be reloaded onto hardware every time the filter requirements change, saving on the final design complexity and reducing verification time. As an extra level of insurance, the filter can be changed at no additional cost after the project has been completed.

[ TOP ]

THE GIBBS PHENOMENON

So filtering directly in the Frequency Domain seems to be a better way to digitally filter a signal than through using conventional methods. However, with all of its advantages, why has this method not been used more often? The reason that this accurate, straightforward, and clear-cut filtering mechanism has not been widely used in the past is because of the Gibbs phenomenon.

The Gibbs phenomenon was first observed by the American mathematical physicist Josiah Gibbs in 1899. It is a spurious oscillation or ringing in the Fourier transform of a signal.

Figure 4: A Time Domain signal of infinite length (extends to +/- infinity)
Figure 4: A Time Domain signal of infinite length (extends to +/- infinity)

Figure 5: The Time Domain signal in figure 4 transformed into the Frequency Domain.
Figure 5: The Time Domain signal in figure 4 transformed into the Frequency Domain. Notice the sharp edges of the frequency content.

Figure 6: The Time Domain signal in figure 4 truncated.
Figure 6: The Time Domain signal in figure 4 truncated. In real life, truncation of input signals is necessary before Frequency Domain transformation due to the finite size of the FFT/IFFT.

The Time Domain signal in figure 6 transformed into the Frequency Domain.
Figure 7: The Time Domain signal in figure 6 transformed into the Frequency Domain. Notice that the frequency content is now smeared due to the Time Domain truncation. This ringing in the Frequency Domain is known as Gibbs ringing or the Gibbs phenomenon.

Fourier Filtering of data containing the Gibbs phenomenon results in outputs that contain large distortions. The following example shows this: a low frequency sinusoid is low pass filtered from out of a noisy sinusoidal sequence. If a Fourier Filter is used to filter the sequence, the Gibbs phenomenon will cause distortions in the output of the Fourier Filter:

Figure 8: The output of the Fourier Filter (WN)
Figure 8: The output of the Fourier Filter (WN), or a FFT filter with no data pre-conditioning

The distortions caused by the Gibbs phenomenon are extremely unpredictable and vary from input to input. This renders the Fourier Filter completely useless for filtering.

The conventional method to treat the Gibbs phenomenon is to gradually taper the ends of the input to zero by applying a non-rectangular window to the input before the Fourier transform. However, the output of this type of filter will still be distorted because the Frequency Domain representation of input is distorted by the window.

The Gibbs phenomenon has been well studied since its discovery, and is believed to be impossible to remove or fully suppress. It simply causes too many distortions in the output of the Fourier Filter and is the major problem with filtering directly in the Frequency Domain. This is the major reason why Fourier Filters have not been widely used in the past to digitally filter signals.

[ TOP ]

THE PAN FILTER

Over the course of his research at Caltech and MIT, Dr. Cheh Pan developed a new understanding of the Gibbs phenomenon. These revolutionary new insights allowed Dr. Pan to develop a new theory & explanation for the Gibbs phenomenon and pioneer methods to completely remove it from the input signal. These methods produce much better results than conventional windows and shall collectively be known as the Pan Filter.

Figure 9: The Pan Filter: a perfected Fourier Filter
Figure 9: The Pan Filter: a perfected Fourier Filter

Over 20 years of research have gone into the development, testing, and successfully application of the technology. The technology itself has been patented, and the results have been published.

Now let us take a look at the example from before, and apply the Pan Filter. The figure below shows the output of the Pan Filter:

Figure 10: The output of the Pan Filter (DF)
Figure 10: The output of the Pan Filter (DF)

As you can see, the Pan Filter completely removes the Gibbs phenomenon. The result of the Pan Filter is a clean, fully filtered output signal with no lag and no beginning and end transients. The Pan Filter solves the over 100 year old problem of the Gibbs phenomenon and works with ALL signals and filter types in ALL cases. In other words, the Pan Filter is a perfected Fourier Filter.

Offline data can now be accurately and quickly filtered and analyzed. In real time, a rolling filter can be successfully constructed without producing spurious transients, enabling Fourier Filtering to be a viable alternative for digitally filtering a signal for the first time in history.

[ TOP ]

Conclusion

The Pan Filter is a complete system of designing efficient, near-ideal filters directly in the Frequency Domain. It perfects Fourier Filtering by completely removing the Gibbs phenomenon from the FFT of a signal, resulting in no spurious transients in the output of the filter. As a result, the Pan Filter is simply the best filter to use for offline data analysis. In addition, the Pan Filter provides near-ideal filtering results at a fraction of the cost of conventional methods. This makes it particularly suitable for applications where computational resources (area, power), latency, or speed (data throughput) is an issue. From another perspective, given the same amount of computational resources, you can achieve much better filtering results with the Pan Filter.

In summary, the Pan Filter:

  • Is simple to design and can implement all types of near-ideal "brickwall" filters.
  • Does not have a laggy response or beginning/ending transients.
  • Can easily create complex filters that conventional methods cannot. It allows for ALL types of spectral shapes for the filter as a result of removing the Gibbs phenomenon.
  • Does not require the offline calculation of filter coefficients. This means that it does not require the use of expensive or complicated filter design software to generate these coefficients.
  • Is easy enough for any novice to pick up & use. Using the Pan Filter will save on engineering design and verification time.

When the Pan Filter is used for Data Analysis (one single FFT/IFFT pair used to filter the input signal), it:

  • Is simply the easiest to use & best performing filter there is.
    • There is no need to worry about which filter algorithm to use or the number of taps of the filter.
    • The phase of the input signal is also not changed during the filtering process.
  • Is much more powerful than conventional filters as the ends of the output of the filter do not need to be thrown away.
    • There is also no trade off between filter performance and data loss in the output of the filter.
  • Is much faster than comparable conventional filters, especially for higher order filters.

In Real Time (a rolling filter is used to filter the input signal), the Pan Filter:

  • Is not a laggy filter.
  • Provides near-ideal performance at a much cheaper cost than a similarly performing FIR filter.
    • It achieves 20 to 50+ dB more noise rejection than a comparably sized conventional filter.
    • It is 100's to 1000's of coefficients or taps smaller than a comparably performing conventional filter.
    • It is much faster than a comparably performing near-ideal FIR filter in terms of both speed and latency because it uses fewer resources to achieve the same results.
  • The Pan Filter is also simpler to implement than a conventional filter.
    • Only one filter design is needed to implement all filters in the system.
    • It does not require the loading the filter coefficients onto hardware.
    • It is easy to design, easy to use, and easy to validate. It is also easily ported from one project to the next.

The Pan Filter is a next generation digital filter that is simple & easy-to-use, and designed to meet all your digital filtering needs. It is a breakthrough in digital filtering technology and will fundamentally change the way signals are digitally filters. It is very easy to swap out fast convolution with the Pan Filter since both algorithms use the FFT & IFFT. Consequently, the Pan Filter will eventually replace many FIR filters.

There are many benefits to using the Pan Filter in your system. Offline data will be filtered faster and more accurately, communication devices will have clearer conversations, and audio devices will have cleaner, crisper sound. It will result in products that are of higher quality & performance, simpler design, and lower cost. The Pan Filter will enable your company to stay at the forefront of technology and help you attain or retain a leadership position in your industry.

Though the basic techniques of the Pan Filter are simple, the technology behind them and its implementation are not. For more information on the Pan Filter, please email info@panfilter.com.

[ TOP ]