Instruction FACTA UNIVERSITATIS Series: Electronics and Energetics Vol. 29, N o 4, December 2016, pp. 689 - 700 DOI: 10.2298/FUEE1604689D A NOVEL ANALYTICAL METHOD FOR THE SELECTIVE MULTIPLIERLESS LINEAR-PHASE 2D FIR FILTER FUNCTION  Jelena R. Djordjević-Kozarov, Vlastimir D. Pavlović University of Niš, Faculty of Electronic Engineering, Niš, Serbia Abstract. In this paper, a novel analytical method for new class of selective linear-phase two-dimensional (2D) finite impulse response (FIR) filter functions generated by applying a new modified 2D Christoffel–Darboux formula for classical orthogonal Chebyshev polynomials of the first and the second kind is proposed. Fundamental research proposed in this paper is also illustrated by examples of 2D FIR filter and adequate comparison with new class of multiplierless linear-phase 2D FIR filter function given in the literature. Key words: 2D FIR filter function, Multiplierless, Linear-phase, Frequency response analysis, Chebyshev polynomials, Hilbert transform 1. INTRODUCTION Successful applications of powerful orthogonal polynomials, in the filter theory, are well-known and described in [1]. A lot of problems in various scientific and technical areas have been solved applying the classical Christoffel-Darboux formula for all classic orthogonal polynomials. The new class of the explicit filter functions for continuous signals, generated by the classical Christoffel-Darboux formula for the classical Jacobi orthogonal polynomials, is given in detail in [2]. Design of the linear-phase FIR filters for defined specifications is discussed in [3]. The grid density requirement for the design of FIR filters, with a useful design rule, is presented in detail in [4]. In [5] the authors present the relationship between the accuracy and the frequency grid density in 2-D filter designs. A new formula for determining the frequency grid spacing is proposed. One-dimensional half-band linear-phase FIR filter design approach is efficiently used in realization of 2D linear-phase FIR filter [6]. The paper [7] describes the approach for the successful design of 2D FIR filters with multipliers. Moreover, 2D FIR filters with nonstandard specifications are designed using transformation technique in [8, 9]. They are based on transformation of one-dimensional FIR filters, as well as direct application of the approximation techniques in two dimensions. Received October 13, 2015; received in revised form April 16, 2016 Corresponding author: Jelena R. Djordjević-Kozarov University of Niš, Faculty of Electronic Engineering, Aleksandra Medvedeva 14, Serbia (email: jelena.djordjevic-kozarov@elfak.ni.ac.rs) 690 J. R. DJORDJEVIĆ-KOZAROV, V. D. PAVLOVIĆ A simple recurrence formula for computing the impulse response coefficients of the sinc N FIR filter, consisting of a cascade of N sinc filters, each of length M, is presented in [11]. The initial consideration for the synthesis of the 2D FIR filter functions is given in a short paper [12]. Proposed Christoffel-Darboux formula for four orthogonal polynomials on two equal finite intervals for powerfully generating filter functions is proposed. In [13] is described in detail the analytical method for the synthesis of the multiplierless linear- phase 1D and 2D FIR filter functions in an explicit form using Chebyshev orthogonal polynomials of the first kind. In [14] is described an analytical method for the synthesis of the multiplierless linear-phase 2D FIR filter functions in a compact form that can have the effect of Hilbert transformer in the z2 domain. A novel analytical method for a new class of linear-phase 2D FIR filter functions with a full effect of Hilbert transformer in z1 and z2 domains is proposed in [15]. The main motivation for this research is the extreme property of Christofell-Darboux sum for the classical orthogonal polynomials that provides new results in the continuous domain, the domain of 1D z and 2D z domain. These results are written in explicit form and give a huge contribution to the filter theory. It should be emphasized that the multiplierless solutions are new solutions worthy of attention. There is no effect of the final quantization of filter coefficients because all the filter coefficients are equal per module. This paper presents further generalization of the previous research [4] in two dimensions. The proposed solution is a filter function in the z1 domain, and the Hilbert transformer in the z2 domain, and with the solution from [14] constitutes the whole. An analytical method of the Christoffel-Darboux formula for the classical orthogonal Chebyshev polynomials, of the first and the second kind, is proposed in this paper in an explicit form in continuous domain. Also, the new class of the linear-phase 2D FIR digital filters, generated by the proposed modified formula and by direct mapping from the continuous domain into 2D z domain, is given. In order to illustrate, the examples of the efficient design of the new class of selective linear-phase 2D FIR filter functions are also given. 2. REVIEW OF THE 2D FIR FILTER FUNCTION Multiplierless linear-phase 2D FIR filter function with two free real parameters is considered in this paper. A linear-phase 2D FIR filter of (M x M)-order is defined by 1 2 1 1 2 0 0 ( , , ) ( , , ) M M r k r k H M z z K h M r k z z        (1) where M is desired order of the filter, 1 K is the real constant and ( , , )h M r k are the impulse response coefficients that are real numbers. Squared filter frequency response, in absolute units, can be presented by 1 21 2 1 2 1( , , ) ( , , ) , for , 2 i j H M z z H M z z z e z e     (2) or 2 1 2 1 2 1 2( , , ) ( , , ) ( , , ) i j i j i j H M e e M e e H M e e         (3) Alternatively in dB, squared filter frequency response can be presented by A Novel Analytical Method for the Selective Multiplierless Linear-phase 2D FIR Filter Function 691 1 2( ) 20 log ( , , ) i j a dB H M e e    (4) 3. NEW CLASS OF TWO-DIMENSIONAL LINEAR PHASE MULTIPLIERLESS FIR FILTER FUNCTIONS Directly applying the formula proposed by Eq. (A.8), the new class of non-causal two- dimensional symmetric FIR filter functions can be obtained as 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 2 1 1 1 1 1 1 11 2 2 2 2 2 2 1 2 sin 12 2 2 ( ) ( ) ( , , ) sin 12 2 2 ( ) ( ) M r z z z z z z T U r ri i h r h r H M z z K z z z z z z T U r rj j h r h r                                                                      (5) or 2 2 2 2 1 2 1 1 1 2 2 (M, , ) [( ) ( )] 1 M r r r r r H z z ij K z z z z           (6) Multiplying the Eq. (6) with factor 2 2 1 2 N N z z    , the filter function can be generated as 2 2 2 2 2 2 2 2 1 2 1 1 1 2 2 1 ( , , ) [( ) ( )] M M r M r M r M r r H M z z ij K z z z z               (7) It is obvious from Eq. (7) that the linear-phase FIR filter contains no multipliers and has only adders. The frequency response, 1 2( , , ) i j H M e e   , can be defined as 1 2 ( 2 ) ( 2 ) 1 22 2 1 2 0 ( , , sin (2 ) sin (2 )) i M j M M i j r H M e e e e r r                 (8) and the magnitude characteristic is defined as 1 2 1 2 0 ( , , ) sin (2 ) sin (2 ) Mi j r H M e e r r        (9) and the amplitude characteristic, 1 2 (2 , , )A M   , is defined as 1 2 1 2 0 ( , , ) sin (2 ) sin (2 ) M r A M r r       (10) The linear-phase function, 1 2 (2 , , )M   , can be defined as ( 2 ) ( 2 ) 1 22 2 1 2 ( , , ) i M j M e eM             (11) 692 J. R. DJORDJEVIĆ-KOZAROV, V. D. PAVLOVIĆ A filter function of K = 2R cascaded identical blocks can be written as (H(M, z1, z2)) 2R . If we propose that the filter function H(M, 2R, z1, z2) is performed as a product of three functions of successive orders 1M , M and 1M , than the form of the filter function can be given by: 2 1 2 1 2 1 2 1 2 (2 , , , ) [ ( 1, , ) ( , , ) ( 1, , )] R H R M z z H M z z H M z z H M z z   (12) 4. EXAMPLES OF THE NEW CLASS OF TWO-DIMENSIONAL LINEAR PHASE FIR FILTER FUNCTIONS The proposed design algorithm, for original 2D FIR filter function, has limitations in addition to the filter dimension (6MR x 6MR) and in addition to the value of two free real integer parameters 2R and M. This means that the linear-phase characteristic forms are limited. In Table 1, for some low values of 2R and M, the form of linear-phase characteristics and type of filter functions are given. When 2R is an even number, the proposed filter function has filter properties in both domains. Table 1 Explicit form of the linear phase characteristics of the proposed FIR filter for some low values of free integer parameters 2R and M 2R M 1 ( 4 ) 2( 4 ) 2 2 1 2 2( , , , ) j MR i MR M R e e             Type 4 4 ( 32 ) ( 32 )1 2 1 2 (4, 4, , ) i j e e             z1 Filter z2 Filter 4 5 40 401 2 1 2( 5, 4, , ) i i j j e e              z1 Filter z2 Filter 4 6 ( 48 ) ( 48 ) 1 2 1 2 (6, 4, , ) i j e e             z1 Filter z2 Filter 4 7 ( 56 )( 56 ) 1 2 1 2 (7, 4, , ) ji e e           z1 Filter z2 Filter 4 8 ( 64 )( 64 ) 1 2 1 2 (8, 4, , ) ji e e           z1 Filter z2 Filter 4 9 ( 72 ) ( 72 ) 1 2 1 2 (9, 4, , ) i j e e             z1 Filter z2 Filter 4 10 ( 80 )( 80 ) 1 2 1 2 (10, 4, , ) ji e e           z1 Filter z2 Filter 4 11 ( 88 ) ( 88 ) 1 2 1 2 (11, 4, , ) i j e e             z1 Filter z2 Filter Using the standard technique, the amplitude, magnitude and phase characteristics are obtained from Eq. (7) for the numerical values 2R = 4 and M = 6, and detailed characteristics of the filter function 1 2 ( , , ,2 )H M zR z are given in the following figures. A Novel Analytical Method for the Selective Multiplierless Linear-phase 2D FIR Filter Function 693 (a) (b) Fig. 1 a) 3D plot of normalized amplitude characteristics of proposed 2D FIR filter for 2R =4 and M=6; b) Zoomed panel a) Illustrated examples of pass-band and stop-band characteristics of the considered FIR filter function for given values of attenuation, 1 2 (2 , , , )a R M   , are shown in Fig. 2. (a) (b) Fig. 2 2D contour plot of normalized magnitude characteristics: a) shape of the pass-band with attenuation of 0.28 dB for 2R =4 and M=6; b) shape of the stop-band with attenuation of 100 dB for 2R =4 and M=6 Fig. 3 shows the phase characteristic of the considered linear-phase multiplierless 2D FIR filter function in the initial part, for the same values of the free integer parameters 2R and M, i.e., 2R = 4 and M = 6. 694 J. R. DJORDJEVIĆ-KOZAROV, V. D. PAVLOVIĆ Fig. 3 3-D plot of the phase characteristic of proposed 2D FIR filter for 2R = 4 and M = 6 5. COMPARISON In this part of the paper, the comparison of the proposed solution for the multiplierless linear-phase 2D FIR filter functions and the solution described in [13] is discussed. For the same values of the real free parameters, M and 2R, and the same value of constant group delay we have considered the comparison of amplitude response characteristics and cut-off frequencies of the pass-band of filter and cut-off frequencies of the stop-band of filter. For the value of the free integer parameter 2R = 4, the paper described in [13] and this paper have the same filter property both in z1 and in z2 domain. For the same odd M = 6 we discussed the comparisons between the amplitude responce characteristics, as well as cut-off frequencies of the pass-band of filter with defined attenuation of 0,28 dB and cut- off frequencies of the stop-band of filter with attenuation of 100 dB. We correctly compare two examples of filter functions that have the same values of free real integer parameters, and thus the same form of linear-phase characteristics which is given in a compact explicit form in the next expression ( 48 ) ( 48 )1 22 2 1 2 (6, 4, , ) i j e e             (13) In Fig. 4 are shown the amplitude response characteristics of 2D FIR filter of the solution from [13] and the proposed solution, respectively, for free parameters 2R=4 and M=6. A Novel Analytical Method for the Selective Multiplierless Linear-phase 2D FIR Filter Function 695 (a) (b) Fig. 4 3D contour plot of amplitude response characteristics, review of the comparison between: a) solution from [13], and b) the proposed filter from Eq. (10) Fig. 5 shows zoomed forms of pass-bands of filters with attenuation of 0.28 dB of the solution from [13] and the proposed solution, respectively, for parameters 2R=4 and M=6. (a) (b) Fig. 5 2D contour plot of normalized magnitude characteristics, shape of the pass-band with attenuation of 0.28 dB; review of the comparison between: a) solution from [13], and b) the proposed filter from (10) In Fig. 6 are shown the stop-bands of filters with attenuation of 100 dB of the solution generated by expressions from [13] and proposed solution, respectively. 696 J. R. DJORDJEVIĆ-KOZAROV, V. D. PAVLOVIĆ (a) (b) Fig. 6 2D contour plot of normalized magnitude characteristics, shape of the stop-band with attenuation of 100 dB; review of the comparison between: a) solution from [13], and b) the proposed filter from (10) In Table 2 and Table 3 are given the values of the surface area of pass-band and stop- band, respectively, of considered 2D FIR filter function for different values of given maximal attenuation compared with 2D FIR filter function given in [13]. Results in Table 3 are given in (%) in relation to a total area of the amplitude characteristic. Table 2 Normalized surface area of pass-band for proposed 2D FIR filter function for given values of maximal attenuation compared with 2D FIR filter function given in [13] 2R M passa (dB) Normalized surface area of the proposed filter function pass-band Normalized surface area of the filter function pass-band proposed in [13] 4 6 0.28 24.3284219110 -4 0.6779299310 -4 Table 3 Normalized surface area of stop-band for proposed 2D FIR filter function for given values of maximal attenuation compared with 2D FIR filter function given in [13] 2R M stopa (dB) Normalized surface area of the proposed filter function stop-band (%) Normalized surface area of the filter function stop-band proposed in [13] (%) 4 6 100 21.405425 34.789375 A Novel Analytical Method for the Selective Multiplierless Linear-phase 2D FIR Filter Function 697 6. CONSLUSION This paper presents an original approach to the multiplierless linear-phase 2D symmetric FIR digital filter function synthesis, bringing the significant improvements in the filter theory. The new Christoffel-Darboux formula for classical orthogonal Chebyshev polynomials of the first and the second kind is proposed in Appendix of this paper. The presented formula can be used for successfully solving extremely complicated problems of the linear-phase 2D filter design, with high selectivity and high order. Transition from the continuous domain into the 2D z domain is successfully presented. This new formula can be directly applied in generating 2D filter functions. All parasitic effects, such as Gibbs phenomenon, are suppressed and there is no need for using multipliers. Filters design by the proposed method can be applied in various areas, such as telecommunications, medicine, pharmacy, seismology, general localizations and diagnostics, where they can be of special interest. The illustrated examples of the 3D frequency responses and the corresponding 2D contour plots of the proposed linear-phase 2D FIR filter are also presented. These examples illustrate the high advantages of the proposed approach and an efficient way of designing ultra-selective filters. The difference between capital research described in [13] and the proposed new classes of filter function for even and odd real value of the free parameter 2R, is following. Formulae in the z domain proposed in this paper and in the papers [13] are highly sophisticated and written on the model of extreme properties of Christoffel-Darboux sum for the continuous classical orthogonal polynomials [3]-[5]. The proposed multiplierless filter functions do not have the problem of the final quantization of filter coefficients, and these solutions are still superior and still very useful for real-time and require a minimum area of integrated technology implementation. Undesirable Gibbs phenomenon, presented in the analog and in 1D digital filters, has been completely eliminated by the proposed solution. In many practical solutions that requires a minimum dissipation of DC power supply, this solution successfully realizes circuits without multipliers and without quasi multipliers. Acknowledgement: The paper is a part of the research done within the project No. 32023, funded by the Ministry of Science of the Republic of Serbia. REFERENCES [1] M. Abramowitz, I. Stegun, Handbook on mathematical function, National Bureau of Standards, Applied Mathematics Series, USA, 1964. [2] V. D. Pavlović, “New Class of Filter Functions generated directly by the modified Christoffel–Darboux formula for classical orthonormal Jacobi polynomials, International Journal of Circuit Theory and Applications”, John Wiley & Sons, vol. 40, pp. 1059–1073, 2013. [3] S. N. Hazra, M. S. Reddy, “Design of circularly symmetric low–pass two–dimensional FIR digital filters using transformation”, IEEE Transactions on Circuits and Systems, vol. 33, no. 10, pp. 1022–1026, 1986. [4] R. H. Yang, Y. C. Lim, “Grid density for design of one- and two-dimensional FIR filters”, Electronics Letters, vol. 27, no. 22, pp. 2053–2055, 1991. [5] S. H. Low, Y. C. Lim, “Frequency grid density for the design of 2-D FIR filters”, Electronics Letters, vol. 32, no. 16, pp. 1460–1461, 1996. 698 J. R. DJORDJEVIĆ-KOZAROV, V. D. PAVLOVIĆ [6] A. Klouche-Djedid, S. S. Lawson, “Simple design and realisation of linear phase 2D FIR filters with diamond frequency support”, Electron. Letters, vol. 35, no. 14, pp. 1148–1150, 1999. [7] N. Vijayakumar, K. M. M. Prabhu, “Two-dimensional FIR compaction filter design”, IEE Proc., Vis. Image Process, vol. 148, no. 3, pp. 173–181, 2001. [8] V. L. Narayana Murthy, A. Makur, “Design of some 2-D filters through the transformation technique”, IEE Proc., Vis. Image Process, vol. 143, no. 3, pp. 184–190, 1996. [9] B. G. Mertzios, A. N. Venetsanopoulos, “Fast block implementation of two-dimensional FIR digital filters via the Walsh–Hadamard decomposition”, International Journal of Electronics, vol. 68, no. 6, pp. 991-1004, 1990. [10] S. K. Mitra, Digital signal processing. – The McGraw–Hill Companies, New York, USA, 1998. [11] S. C. Dutta Roy, “Impulse response of sinc N FIR filters”, IEEE Transactions on Circuits and Systems, vol. 53, no. 3, pp. 217–219, 2006. [12] D. G. Ćirić, V. D. Pavlović, “Linear Phase Two-Dimensional FIR Digital Filter Functions Generated by applying Christoffel-Darboux Formula for Orthonormal Polynomials”, ELEKTRONIKA IR ELEKTROTECHNIKA, vol. 4, pp. 39-42, 2012. [13] V.D. Pavlović, N. Doncov, D.G. Ćirić, “1D and 2D Economical FIR Filters Generated by Chebyshev Polynomials of the First Kind”, Int. Journal of Electr., vol. 100, no. 11, pp. 1592-1619, 2013. [14] J.R. Djordjevic-Kozarov, V.D. Pavlovic, “An Analytical Method for the Multiplierless 2D FIR Filter Functions and Hilbert Transform in z2 domain”, IEEE Trans. on Circuits and Systems- II: Express briefs, vol. 60, no. 8, pp. 527-531, 2013. [15] V.D. Pavlovic, J.R. Djordjevic-Kozarov, “Ultra-selective spike multiplierless linear-phase two- dimensional FIR filter function with full Hilbert transform effect”, IET Circuits Devices Syst., vol. 8, no. 6, pp. 532–542, 2014. APPENDIX 1. Proposed mathematical background If 1 ( ) r U x  and 1 ( ) r U y  are two sets of the orthogonal Chebyshev polynomials of the second kind [5], where x and y are real variables and r is the order of the continuous non-periodical polynomials on a finite interval 1 1x   and 1 1y   respectively, with regard to the non- negative continuous weight functions, 1 ( )w x and 2 ( )w y , defined as 2 1 ( ) 1w x x  (A.1) and 2 2 1 ( ) 1 w y y   (A.2) then, for the orthogonal Chebyshev polynomials of the first kind, Tr(y), and the second kind, Ur + 1(x), the following relations are valid 1 1 1 1 1 ( ) ( ) ( ) 0 ; , 0, 1, 2, 3, m k w x U x U x dx m k m k       (A.3) and 1 2 1 ( ) ( ) ( ) 0 ; , 0, 1, 2, 3, m k w y T y T y dy m k m k     (A.4) A Novel Analytical Method for the Selective Multiplierless Linear-phase 2D FIR Filter Function 699 For the polynomial, Tr(y), r-th order norm h2(r), is: 1 2 2 2 1 , 0 ( ) ( ) ( ( )) , 1, 2, 3, 2 r r h r w y T y dy r           (A.5) and for the polynomial Um + 1(x), m-th order norm h1(m), is 1 2 1 1 1 1 ( ) ( ) ( ( )) , 1, 2, 3, 2 mh m w x U x dx m       (A.6) A novel analytical method for the linear phase two-dimensional symmetric FIR digital filter functions generated by applying the modified Christoffel-Darboux formula with alternating sign. Components of that sum are determined by multiplication of orthogonal classical Chebyshev polynomials of the first and the second kind, with x and y as a real continual variables, Ur+1(x), Ur+1(y) and Tr(x), Tr(y), r = 1,2,...,n (where n is the order of the continual orthogonal polynomials), on the equal finite interval [1,1], is proposed in the following explicit form of the orthogonal components: or 1 1 1 1 2 1 2 ( ) ( ) ( ) ( ) ( , ) sin ( ) sin ( ) ( ) ( ) ( ) ( ) n r r r r n r T x U x T y U y x y x y h r h r h r h r       (A.7) i. e. 2 1 1 1 2 ( , ) sin ( ) sin ( ) ( ) ( ) ( ) ( ) n n r r r r r x y x y T x U x T y U y              (A.8) Using the standard technique, the Eq. (A.8) can be mapped into the new domains, analogue, s, and digital, z, [3, 4, 17-19]. Thus, in the z1 domain for example, the following relations are always valid: 1 1 1 1 1 1 22 2 2 2 2 ( cos ) cos ( ) ( ) / 2 ( ) / 2 ( cos ) cos ( ) ( ) / 2 ( ) / 2 j k j k k k k j kj k k k k T x k e e z z T y k e e z z                        (A.9) where Tk (x = cos 1) and Tk (y = cos 2) are the orthogonal continuous Chebyshev polynomials of the first kind, and 1 1 1 1 1 1 1 2 2 2 1 2 2 2 sin ( ) ( ) sin ( ) ( ) /(2 ) ( ) /(2 ) sin ( ) ( y ) sin ( ) ( ) /(2 ) ( ) /(2 ) i k i k k k k j k j k k k k U x k e e i z z i U k e e j z z j                         (A.10) where Uk+1 (x = cos 1) and Uk+1 (y = cos 2) are the orthogonal continuous Chebyshev polynomials of the second kind. As we can see, for odd k, e.g. k = 9, following Eq. (A.12) and Eq. (A.13) the orthogonal Chebyshev polynomials Tk (y) and Uk+1 (x), respectively, becomes 700 J. R. DJORDJEVIĆ-KOZAROV, V. D. PAVLOVIĆ 9 9 2 2 9 9 9 2 2 2 ( ) cos ( 9 ) ( ) / 2 ( ) / 2 j j T y e e z z           (A.11) and 9 9 1 1 9 9 1 10 1 1 1 sin ( ) ( ) sin ( 9 ) ( ) / 2 ( ) / 2 i i U x e e z z            (A.12)