Frontiers in Signal Processing

Review of Unbiased FIR Filters, Smoothers, and Predictors for Polynomial Signals

Download PDF (1713.2 KB) PP. 1 - 29 Pub. Date: January 17, 2018

DOI: 10.22606/fsp.2018.21001

Author(s)

Yuriy S. Shmaliy^*
Electronics Engineering Department, DICIS, Universidad de Guanajuato, Salamanca, Mexico
Yrjö Neuvo
Department of Communications and Networking, Aalto University, Aalto, Finland
Sanowar Khan
Department of Electrical and Electronic Engineering, City, University of London, London EC1V 0HB, UK

Abstract

Extracting an estimate of a slowly varying signal corrupted by noise is a common task. Examples can be found in industrial, scientific and biomedical instrumentation. Depending on the nature of the application the signal estimate is allowed to be a delayed estimate of the original signal or, in the other extreme, no delay is tolerated. These cases are commonly referred to as filtering, prediction, and smoothing depending on the amount of advance or lag between the input data set and the output data set. In this review paper we provide a comprehensive set of design and analysis tools for designing unbiased FIR filters, predictors, and smoothers for slowly varying signals, i.e. signals that can be modeled by low order polynomials. Explicit expressions of parameters needed in practical implementations are given. Real life examples are provided including cases where the method is extended to signals that are piecewise slowly varying. A critical view on recursive implementations of the algorithms is provided.

Keywords

Polynomial signal, unbiased FIR filter, trend analysis, signal prediction, signal smoothing,digital filter design

References

[1] Y. Bar-Shalom and X.-R. Li, Estimation and Tracking: Principles, Techniques, and Software. Artech House,1993.

[2] B. Hofmann-Wellenhof, B. H. Lichtenegger, and J. Collins, GPS Theory and Practice, 2nd Ed. Springer-Verlag,1997.

[3] Y. S. Shmaliy, GPS-based Optimal FIR Filtering of Clock Models. Nova Science, 2009.

[4] A. Shukla and E. Alkhalifa, Biomedical Engineering and Information Systems: Technologies, Tools and Applications. IGI Global Medical Information Science Reference, 2010.

[5] R. E. Kalman, “A new approach to linear filtering and prediction problems,” Journal of Basic Engineering,vol. 82, no. 1, pp. 35–45, 1960.

[6] R. E. Kalman and R. S. Bucy, “New results in linear filtering and prediction theory,” Journal of Basic Engineering, vol. 83D, no. 1, pp. 95–108, 1961.

[7] A. H. Jazwinski, Stochastic Processes and Filtering Theory. Academic Press, 1970.

[8] W. Kwon and S. Han, Receding Horizon Control: Model Predictive Control for State Models. Springer, 2005.

[9] Y. S. Shmaliy, “Linear optimal FIR estimation of discrete time-invariant state space models,” IEEE Trans. on Signal Processing, vol. 58, no. 6, pp. 3086–3096, 2010.

[10] N. Wiener, The extrapolation, interpolation, and smoothing of stationary time series. John Wiley & Sons,1949.

[11] C. F. Gauss, Theory of the Combination of Observations Least Subject to Errors. SIAM Publ., 1995.

[12] S. M. Key, Fundamentals of Statistical Signal Processing: Estimation Theory. Prentice-Hall, 1993.

[13] L. A. Zadeh and J. R. Ragazzini, “An extension of Wiener’s theory of prediction,” Journal of Applied Physics,vol. 21, no. 2, pp. 645–655, 1950.

[14] K. R. Johnson, “Optimum, linear, discrete filtering of signals containing a nonrandom compionent,” IRE Trans. Information Theory, vol. 2, no. 2, pp. 49–55, 1956.

[15] M. Blum, “On the mean square noise power of an optimum linear discrete filter operating on polynomial plus white noise input,” IRE Trans. Information Theory, vol. 3, no. 4, pp. 225–231, 1957.

[16] W. F. Trench, “A general class of discrete time-invariant filters,” Journal of the Society for Industrial and Applied Mathematics, vol. 9, no. 3, pp. 405–421, 1961.

[17] Y. S. Shmaliy and O. Ibarra-Manzano, “Noise power gain for discrete-time FIR estimators,” IEEE Signal Processing Letters, vol. 18, no. 4, pp. 207–210, 2011.

[18] P. Peebles, “An alternate approach to the prediction of polynomial signals in noise from discrete data,” IEEE Trans. on Aerospace Electron. Systems, vol. 6, no. 4, pp. 534–543, 1970.

[19] P. Kovanic, “Accuracy limitations in an unbiased optimum data treatment,” Journal of Computational Physics,vol. 6, no. 3, pp. 473–482, 1970.

[20] S. Alterman, “Discrete-time least squares, minimum mean square error, and minimax estimation,” IEEE Trans. Comm. Tech., vol. 14, no. 3, pp. 302–308, 1966.

[21] P. Heinonen and Y. Neuvo, “FIR-median hybrid filters with predictive FIR substructures,” IEEE Trans. Acoust. Speech Signal Process., vol. 36, no. 6, pp. 892–899, 1988.

[22] J. Astola, P. Heinonen, and Y. Neuvo, “Linear median hybrid filters,” IEEE Trans. Circuits and Systems,vol. 36, no. 11, pp. 1430–1438, 1988.

[23] T. G. Campbell and Y. Neuvo, “Predictive FIR filters with low computational complexity,” IEEE Trans. Circuits and Systems, vol. 38, no. 9, pp. 1067–1071, 1991.

[24] S. J. Ovaska, O. Vainio, and T. I. Laakso, “Design of predictive IIR filters via feedback extension of FIR forward predictors,” IEEE Trans. on Instrum. and Measur., vol. 46, no. 5, pp. 1196–1210, 1997.

[25] P. T. Harju and T. I. Laakso, “Polynomial predictors for complex-valued vector signals,” Electron. Letters, vol. 31, no. 19, pp. 1650–1652, 1995.

[26] P. H?ndel and P. Tichavsky, “Asymptotic noise gain of polynomial predictors,” Signal Processing, vol. 62, no. 2, pp. 247–250, 1997.

[27] K. Koppinen, “Analysis of the asymptotic impulse and frequency responses of polynomial predictors,” Signal Processing, vol. 84, no. 3, pp. 549–560, 2004.

[28] S. Samadi and A. Nishihara,“Explicit formula for predictive FIR filters and differentiators using Hahn orthogonal polynomials,” IEICE Trans. Fundamentals, vol. E90-A, no. 8, pp. 1511–1518, 2007.

[29] S. J. Ovaska, O. Vainio, and T. I. Laakso, “Design of predictive IIR filters via feedback extension of FIR forward predictors,” IEEE Trans. Instrum. Measur., vol. 46, no. 5, pp. 1196–1201, 1997.

[30] R. Wichman, J. T. Astola, P. J. Heinonen, and Y. A. Neuvo, “FIR-median hybrid filters with excellent transient response in noisy conditions,” IEEE Trans. Acoust. Speech Signal Process., vol. 38, no. 12, pp.2108–2117, 1990.

[31] O. Vainio and S. J. Ovaska, “Noise reduction in zero crossing detection by predictive digital filtering,” IEEE Trans. Industr. Electron., vol. 42, no. 1, pp. 58–62, 1995.

[32] T. I. Laakso and S. J. Ovaska, “Prefiltering approach for optimal polynomial prediction,” IEEE Trans. Signal Process., vol. 4, no. 3, pp. 701–705, 1996.

[33] J. M. A. Tanskanen and V. Dimitrov, “Round-off error-free fixed-point design of polynomial FIR predictors and predictive FIR differentiators,” Digital Signal Processing, vol. 13, no. 1, pp. 42–57, 2003.

[34] J. A. Honkanen, T. I. Laakso, S. J. Ovaska, and I. Hartimo, “Lowpass IIR predictors for discrete-time signal processing,” Digital Signal Processing, vol. 5, no. 3, pp. 133–139, 1995.

[35] Y. S. Shmaliy, “A simple optimally unbiased MA filter for timekeeping,” IEEE Trans. on Ultrason. Ferroelec. Freq. Control, vol. 49, no. 6, pp. 789–797, 2002.

[36] ——, “An unbiased FIR filter for TIE model of a local clock in applications to GPS-based timekeeping,”IEEE Trans. on Ultrason. Ferroelec. Freq. Control, vol. 53, no. 5, pp. 862–870, 2006.

[37] ——, “An iterative Kalman-like algorithm ignoring noise and initial conditions,” IEEE Trans. Signal Processing,vol. 59, no. 6, pp. 2465–2473, 2011.

[38] P. Castro-Tinttori and Y. S. Shmaliy, “Implementation of digital FIR filters with polynomial impulse responses,”Circuits, Systems, Signal Processing, vol. 31, no. 2, pp. 611–626, 2012.

[39] ——, “Computationally efficient FIR filtering of polynomial signals in DFT domain,” Circuits, Systems, Signal Processing, vol. 31, no. 6, pp. 2153–2166, 2012.

[40] L. R. Rabiner and B. Gold, Theory and Applications of Digital Signal Processing. Prentice-Hall, 1975.

[41] Y. S. Shmaliy, “Unbiased FIR filtering of discrete time polynomial state space models,” IEEE Trans. on Signal Processing, vol. 57, no. 4, pp. 1241–1249, 2009.

[42] J. Levine, “The statistical modeling of atomic clocks and the design of time scales,” Review of Scientific Instruments, vol. 83, no. 2, pp. 021 101–1–021 101–28, 2012.

[43] ——, “Time synchronization over the Internet using an adaptive frequency-locked loop,” IEEE Trans. Ultrason. Ferroelect. Freq. Control, vol. 46, no. 4, pp. 888–896, 1999.

[44] T. Iwata, M. Imae, T. Suzuyama, H. Murakami, and K. Y., “Simulation and ground experiments of remote synchronization system for on-board crystal oscillator of Quazi-Zenith Satelite System,” Journal of the Institute of Navigation, vol. 53, no. 4, pp. 231–235, 2006.

[45] Y. Kou, Y. Jiao, D. Xu, M. Zhang, Y. Liu, and L. X., “Low-cost precise measurement of oscillator frequency instability based on GNSS carrier observation,” Advances in Space Research, vol. 51, no. 6, pp. 969–977, 2013.

[46] L. Arceo-Miquel, Y. S. Shmaliy, and O. Ibarra-Manzano, “Optimal synchronization of local clocks by GPS 1PPS signals using predictive FIR filters,” IEEE Trans. Instrum. Meas., vol. 58, no. 6, pp. 1833–1840, 2009.

[47] Y. S. Shmaliy, “An unbiased p-step predictive FIR filter for a class of noise free discrete-time models with independently observed states,” Signal, Image and Video Processing, vol. 3, no. 2, pp. 127–135, 2009.

[48] L. J. Morales-Mendoza and Y. S. Shmaliy, “Moving average hybrid filter to the enhancing ultrasound image processing,” IEEE Latin America Trans., vol. 8, no. 1, pp. 9–16, 2010.

[49] Y. S. Shmaliy and L. J. Morales-Mendoza, “FIR smoothing of discrete-time polynomial models in state space,”IEEE Trans. Signal Processing, vol. 58, no. 5, pp. 2544–2555, 2010.

[50] Y. S. Shmaliy and L. Arceo-Miquel, “Efficient predictive estimator for holdover in GPS-based clock synchronization,” IEEE Trans. on Ultrason. Ferroelec. Freq. Control, vol. 55, no. 10, pp. 2131–2139, 2008.

[51] Y. S. Shmaliy, “Linear unbiased prediction of clock errors,” IEEE Trans. on Ultrason. Ferroelec. Freq. Control,vol. 56, no. 9, pp. 2027–2029, 2009.

[52] O. Vite-Chavez, R. Olivera-Reyna, O. Ibarra-Manzano, Y. S. Shmaliy, and L. Morales-Mendoza, “Time-variant forward-backward fir denoising of piecewise-smooth signals,” Int. J. Electron. Commun. (AEU), vol. 67, no. 5, pp. 406–413, 2013.

[53] H. Hamboa-Rosales, L. Morales-Mendoza, and Y. S. Shmaliy, “Unbiased impulse responses - A class of discrete orthogonal polynomials,” ICIC Express Letters, vol. 7, no. 7, pp. 2005–2010, 2013.

[54] L. J. Morales-Mendoza, H. Gamboa-Rosales, and Y. S. Shmaliy, “A new class of discrete orthogonal polynomials for blind fitting of finite data,” Signal Processing, vol. 93, no. 7, pp. 1785–1793, 2013.

[55] L. Chang, “On Kalman-like finite impulse response filters,” arXiv:1501.07132.

[56] A. Savitzky and M. J. E. Golay, “Smoothing and differentiation of data by simplified least squares procedures,” Analytical Chemistry, vol. 36, no. 8, pp. 1627–1639, 1964.

[57] A. Lepek, “Clock prediction and characterization,” Metrologia, vol. 34, no. 5, pp. 379–386, 1997.

[58] L. Yin, R. Yang, and Y. Neuvo, “Weighted median filters: a tutorial,” IEEE Trans. on Circuits and Systems-II: Analog and Digital Signal Processing, vol. 43, no. 3, pp. 157–192, 1996.

[59] L. J. Morales-Mendoza, R. F. Vazquez-Bautista, E. Morales-Mendoza, Y. S. Shmaliy, and H. Gamboa-Rosales,“A new recursive scheme of the unbiased FIR filter to image processing,” Procedia Engineering, vol. 35.

[60] “ITU-T Recommendation G.810. Definitions and terminology for synchronization networks.”

[61] “EN 300 462-4-1 v1.1.1, European Standard (Telecommunications series) Transmission and Multiplexing(TM); Generic requirements for synchronization networks; Part 4-1: Timing characteristics of slave clocks suitable for synchronization supply to Synchronous Digital Hierarchy (SDH) and Plesiochronous Digital Hierarchy (PDH) equipment.”

[62] Y. S. Shmaliy, O. Ibarra-Manzano, L. Arceo-Miquel, and J. Munoz-Diaz, “A thinning algorithm for GPS-based unbiased FIR estimation of a clock TIE model,” Measurement, vol. 41, no. 5, pp. 538–550, 2008.

[63] Y.-K. Lee, S.-H. Yang, C.-B. Lee, and M.-B. Heo, “Estimation of GPS holdover performance with ladder algorithm used for an UFIR filter,” Journal of Institute of Control, Robotics and Systems, vol. 21, no. 7, pp.669–676, 2015.

[64] K. Gentile, “The AD9548 as a GPS Disciplined Stratum 2 Clock. Analog Devices,” AN-1002 Application Note.

[65] J. Lee, S. Hwang, D.-H. Yu, C. Park, and S. Lee, “Software-based performance analysis of a pseudolite time synchronization method depending on the clock source,” Journal of Positioning, Navigation and Timing,vol. 3, no. 4, pp. 163–170, 2014.

[66] Y. Zhang, W. Lu, D. Lei, Y. Huang, and D. Yu, “Effective PPS signal generation with predictive synchronous loop for GPS,” IEICE Trans. on Communications, vol. E97-B, no. 8, pp. 1742–1749, 2014.

[67] Y. Chen, S. Ding, Z. Xie, Z. Qi, and X. Liang, “Design study for a quasisynchronous CDMA sensor data collection system: an LEO satellite uplink access technique based on GPSS,” International Journal of Distributed Sensor Networks, vol. ID 421745.

[68] R. Y. Ramlall, “Method for Doppler-aided GPS carrier-tracking using p-step ramp unbiased finite impulse response predictor,” International Journal of Distributed Sensor Networks, vol. U.S. Patent 8 773 305, July 8.

[69] J. B. Fu, J. Sun, F. Gao, and L. S., “Maneuvering target tracking with improved unbiased FIR filter,” in Proc. 2014 Int. Radar Conf. (Radar). IEEE, 2014, pp. 1–5.

[70] J. Fu, J. Sun, S. Lu, and Y. Zhang, “Maneuvering target tracking with modified unbiased FIR filter,” Journal of Beijing Univ. of Aeronautics and Astronautics, vol. 41, no. 1, pp. 77–82, 2015.