Low-pass filtering through different types of windows in linear time
Ejaz Ahmad Ansari, Nandana Rajatheva · 2010
This paper proposes a new, simple and efficient method in time domain for processing the input data through rectangular, triangular, trapezoidal and exponential shaped windows in linear time. The data processing involves convolution and correlation of the input data sequence with various types of windows representing the LTI-systems. First, we devise a very simple and fast algorithm known as fast low-pass filtering using windows (FLPFW) which processes the input data sequence of length L through a rectangular shaped window of length M by taking exactly 2× (L - 1) addition operations only. These exact number of addition operations remain independent to the size, M of the rectangular shaped window. We then process the input data sequence through other three types of windows by calling this algorithm efficiently (known as modified FLPFW). The key feature of the modified FLPFW is that it performs data processing tasks through first three types of windows by incurring additions as basic operations only. It does not consume any multiplication / division operations for this purpose. Moreover, FLPFW can also process the input data through a moving average filter containing taps, M if its output generated sequences are multiplied by 1/M. Finally, we show that it outperforms all the existing techniques with respect to exact number of arithmetic operations consumed by it and its worst case time complexity grows linearly with the length of the input data sequence, i.e., O(L).