'ffY seer ion NAV * 1 'UIJATE SCWOL NPS-53Dv76081 NAVAL POSTGRADUATE SCHOOL Monterey, California THE COEFFICIENT SPACE APPROACH TO THE STABILITY OF MULTIDIMENSIONAL DIGITAL FILTERS Daniel L. Davis August 1976 Approved for public release; distribution unlimited Prepared for- Navel Postgraduate School Monterey, Ca . 93940 FEDDOCS D 208.14/2: NPS-53DV76081 NAVAL POSTGRADUATE SCHOOL Monterey, California Rear Admiral Isharn Linder Jack R. Bor sting Superintendent Provost ABSTRACT This report is concerned with the development of a new approach to the problem of stability for multidimensional, causal, recursive, 'all pole', digital filters. The distinguishing feature of this approach is that general stability criteria can be derived directly in terms of the coefficients of the transfer function of the filter. Thus by use of this method it is sometimes possible to determine which coefficients of the transfer function are critical to the stability of the filter, information which is, of course, important in filter design. Also the emphasis of this approach is on the development of a conceptual method for considering the problem in complete generality. Reproduction of all or part of this report is authorized. This report was prepared by: UNCLASSIFIED SECURITY CLASSIFICATION OF THIS PAGE (When Data Entered) REPORT DOCUMENTATION PAGE 1. REPORT NUMBER NPS53Dv76081 2. GOVT ACCESSION NO, READ INSTRUCTIONS BEFORE COMPLETING FORM 3. RECIPIENT'S CATALOG NUMBER 4. TITLE (and Subtitle) The Coefficient Space Approach to the Stability of Multidimensional Digital Filters. 5. TYPE OF REPORT & PERIOD COVERED Technical Report January - March 1976 6. PERFORMING ORG. REPORT NUMBER 7. AUTHORfsj Daniel L. Davis 8. CONTRACT OR GRANT NUMBER(«j Foundation Research 9. PERFORMING ORGANIZATION NAME AND ADDRESS Naval Postgraduate School Monterey, CA 93940 10. PROGRAM ELEMENT, PROJECT, TASK N0001476WR60052 It. CONTROLLING OFFICE NAME AND ADDRESS Navel Postgraduate School Monterey ,Ca. 93940 12. REPORT DATE August 1.976 13. NUMBER OF PAGES 14. MONITORING AGENCY NAME & ADDRESSf// different from Controlling Office) 15. SECURITY CLASS, (of thla report) Unclassified 15a. DECLASSIFI CATION/ DOWN GRADING SCHEDULE 16. DISTRIBUTION STATEMENT (of this Report) Approved for public release: distribution unlimited 17. DISTRIBUTION STATEMENT (of the abatract entered In Block 20, If different from Report) 18. SUPPLEMENTARY NOTES 19. KEY WORDS (Continue on reverae aide If neceaaary and Identify by block number) Digital filter, multidimensions , Stability, coefficient space, 20. ABSTRACT (Continue on reverae aide If neceaaary and Identity by block number) This report is concerned with the development of a new approach to the problem of stability for multidimensional, causal, recursive, 'all pole', digital filters. The distinguishing feature of this approach is that general stability criteria can be derived directly in terms of the coefficients of the transfer function of the filter. Thus by use of this method it is sometimes possible tc determine which coefficients of the transfer function are critical to the stability of the filter, information which is, of course, important in filter DD FORM 1 JAN 73 1473 EDITION OF 1 NOV 65 IS OBSOLETE S/N 0102-014- 6601 | UNCLASSIFIED SECURITY CLASSIFICATION OF THIS PAGE (When Data Sntarad) UNCLASSIFIED .LCUR1TY CLASSIFICATION OF THIS PAGECWian Datm Entered) design. Also the emphasis of this approach is on the development of a conceptual method for considering the problem in complete generality. UNCLASSIFIED SECURITY CLASSIFICATION OF THIS PAGE(TWi«i Data Enit The Coefficient Space Approach to the Stability of Multidimensional Digital Filters 1. Introduction Consider a filter whose transfer function has the form H(z) = 1/(1 - QOf 1 )) (1.1) where z = (z.. , ..., z ) is a vector complex variable, and Q(z") is a polynomial in N variables with real coefficients and zero constant term. Such a transfer function describes an 'all-pole' 'causal', recursive, multidimensional digital filter, and it is known that questions of stability generally reduce to a question of stability for filters of this type. It is also known that such a filter is stable iff P(z) = 1 - Q(z) (1.2) has no zeros 3 - (S-, , ...» S N ) such that |S.| <_ 1 for all i . For this reason, it is convenient terminology to state that a polynomial P(z) of several variables is stable if P(8) = implies that |6.| > 1 for some i . The question of stability then becomes, primarily, the problem of determining if such a polynomial is stable. An N-tuple of the form f = (j , ..., J N )> where each j. is a non- negative integer is called a vector index . If for such an index ~j , we define ~z by 1 Z 2 ' * * Z N U'3) then every polynomial P(z) in N-variables can be written in the form P(z) = J2 ^ * (1.4) where a^. for each * , is a real number, equal to zero except for a finite number of indices (see Davis and Souchon [1975]). For example if 2 P(z 1 ,z 2 ) = 1.00 + 0.5z-z - .llz^z- then a_ = 1.00, a.., = .05, a„, = -.11 and all other coefficients equal zero. Suppose that a fixed, ordered set (j- , j* , ..., "f. ' ) of non-zero, LA K N-dimensional vector indices is given, and consider the set of polynomials of the form K f. P(t) = 1 - ]T a* z x (1.5) i=l * where, for each i , a^. is a real number. Each such polynomial (1.5) J i is naturally associated to the point (au. , . . . , su> ) of K-dimensional J l T K euclidean space. Conversely, each point (A_ , ..., A-_) of K-dimensional J. K. euclidean space is associated to a polynomial of type (1.5) by the correspondence A. = a^ , i = 1, ..., K (1.6) T i V, relative to the ordered set of indices "5*. , . . . , "j* ' . Thus relative to i K this ordered set of indices, K-dimensional space becomes the coefficient space for polynomials of type (1.5). A point (A.. , ..., A^) of this coefficient space will be said to be a stable point if its associated polynomial, namely K T P(z) = 1 - ]T A ± z i (1.7) i=l is stable. The set of all such stable points in the coefficient space will be called the region of stability . The problem that will be considered here is what can be found concerning the region of stability for a given set of vector indices, or equivalently, for a given type of polynomial. In certain cases, the region of stability can be specified completely. Consider the ordered set of indices *J- = (10), "Jl = (01) "f~ = (11). The associated polynomials are of the form P(z 1 ,z 2 ) = 1 - A 1 z 1 - A 2 z 2 - A 3 z 1 z 2 , (1.8) and the associated coefficient space is 3 dimensional euclidean space. Huang [1972] has shown that (1.8) is stable iff |A 3 | < 1 A 1+ A 2 | < 1- A 3 |A 1 -A 2 | < 1+A 3 . The region of stability is illustrated in Figure 1. Also, it can be shown, see Jury [1974] that a similar type of specification can be given for any region of stability associated to polynomials in one variable, or equivalently, to any ordered set of 1-dimensional vector indices. Although, regions of stability can be very difficult to determine for more complicated types of multivariable polynomials, in the following it will be shown that several properties of regions of stability can be derived in general. A 3 FIGURE 1 2. The Basic Theorems Throughout the following it will be assumed that "J 1 , . . . , ^ is a given, fixed, ordered set of N dimensional vector indices. Thus the correspondence between polynomials of the form (1.7) and points (A 1 , . . . , A^.) of K-dimensional space is assumed fixed. The order of a vector index "f = (j-, ..., j M ) is defined by order "f = i. + ... + j„ . j jj_ j n A coefficient A. of a polynomial of type (1.7) is called a leading co effi cient if its associated vector index "j 1 . has maximal order. A polynomial of several variables may have several leading coefficients. Theorem 2.1 If (A.. , . . . , A^) is a stable point of the coefficient space and if A is the sum of the leading coefficients of the polynomial corresponding to this point, then |a| < 1. Proof. Let P(z} be the stable polynomial associated to (A.. , ..., A^) . It follows that the one variable polynomial p(z) defined by p(z) = P(z, ..., z) (2.1) is also stable. Moreover the leading coefficient of p(z) is seen to be A . The polynomial p(z) factors, p(z) = A(z-t 1 )...(z-t M ) (2.2) where t- , ..., t are its complex roots. Since p(z) is stable it follows that |t | > 1 i = 1, ..., M . (2.3) But then, M i = |p(0)| = |a| n t.| (2.4) i=l x where M n i=i n t | > 1 . (2.5) Hence, A < 1 . (2.6) Theorem 2.2 (Necessity Theorem) Let a =» (a.. , . . . , <0 be any N-tuple of complex numbers such that for each i = 1, ..., N , |ct | = 1 , and for each i s ± = a (2.7) is a real number. Then, if (A.. , . . . , A^) is any stable point, it must be true that s^ + ... + SjA, < 1 • (2.8) (Note that since each s. has modulus 1 and is real, each s. must equal +1 or -1.) Proof. Let P("z) be the stable polynomial associated to (A- , ..., A^) . Suppose a satisfies the hypotheses and define p(z) by p(z) = P(a 1 z, ..., a N z) . (2.9) Then p(z) is a one variable polynomial with real coefficients. Moreover K i=l 3 (i) - 1 - y^ a^c^, ••♦» Ojj) (2.10) If K 1 - E Vi i=l K 1] s^ > 1 (2.11) i=l then p(l) £ . (2.12) But p(0) = 1, and p(z), as a function of a real variable, is clearly continuous. Therefore by the intermediate value theorem for real functions, there must exist a real number t , < t <_ 1 , such that p(t) ■ 0. But then P(a 1 t, ..., ty:) = (2.13) and for each i=l, ...,N, |a.t| <_ 1 , a contradiction to the assumption that P(z) is stable. Therefore it must be true that ^s.jA. < 1 . (2.14) Theorem 2.3 (Symmetry Theorem) Let a = (a , . . . , a ) be any N-tuple of complex numbers such that for each i=l, ...,N, |a.| = 1 , and s. = a X (2.15) x is a real number. Then a point (A- , ..., A^) is stable iff the point (S-.A- , ..., slA^) is stable. (Note as before that each s. equals +1 or -1.) Proof. Let P(z.., ..., z ) be the polynomial associated to (A., ..., A^) . Define P' (z. , ...» z ) by P'(z 1 , ..., z N ) = P(a 1 z 1 , ..., djjZjj) . (2.16) It is not difficult to check that P' is the polynomial associated to (S..A.., ..., s^J . Moreover P' is stable iff P is. For P'(B 1 , ..., B N ) = iff P(3]_, ..., 3') = where e! - a.3 ± and for each i Is! I = I a. 6.1 = |S.|» since la. I =1 . 'i' ' i i 1 ' i ' 'i' Theorem 2.4 (Sufficiency Theorem) Let (A- , ..., A^) be a point such that K ^|A.| < 1 . (2.17) i=l Then (A,, ...» A_.) is stable. Proof. Consider the polynomial (1.7) V- j i P( Z;L , ..., z N ) = 1 - 2^ z • (2-18) If P(B) = where |g | <_ 1 , then Therefore £^A 6 i = 1 . (2.19) K "t K 1 = \Y] A. 6 i | y |A.| < 1 (2.20) i=l i=l a contradiction. Corollary 2.1 Let (A. , . . . , iO be a point such that A >_ for all i . Then (A.. , . .., A_J is stable iff K ]£ A. < 1 . (2.21) 1-1 Proof. Apply Theorem 2.2 and Theorem 2.4. Theorem 2.4 and its corollary can be given simple geometric inter- pretations. The region of points (A., ..., A^) satisfying |A 1 | + ... + |Aj < 1 (2.22) describe the K-dimensional 'diamond', centered at the origin and whose points lie along the axes. Theorem 2.4 states that the K-dimensional diamond is wholly enclosed by the region of stability. The Corollary states that in the positive 'quadrant', the region of stability always coincides with the 'diamond' (see Figure 1). In the following, the Symmetry Theorem will be applied to show that regions of stability also satisfy certain geometric symmetries. 3. Symmetry As the proof of Theorem 2.3 shows, symmetries, (in this case sequences of reflections) between the points of the region of stability arise from transformations of the variables of the associated polynomials. The transformation of variable is given by (z.^ ..., Zjj) ■* (z^, ..., z^) = (a.^, ..., ci N z N ) (3.1) where (cc. , . . . , cO is a complex vector satisfying the conditions that for each i , a . = 1 and 1 x ' s ± - ex (3.2) is a real number. Such a stability invariant transformation transforms the coefficients (A.. , ..., A^) into (s.A.., ..., s^O . Since each s always equals +1 or -1, this transformation is geometrically interpreted as a sequence of reflections of the axes. N -*. At least 2 vectors a can be obtained by choosing each a. equal to +1 or -1. The symmetries of the coefficient space thus obtained, however, are not necessarily distinct, and may not include symmetries which can be obtained by allowing the a. to be complex. However, symmetries so obtained are more easily studied and for this reason will be called simple symmetries. In the following we will restrict our attention to the study of simple symmetries. The transformation (symmetry) of the coefficient space determined by the vector a can be described completely by the vector s ■ (s., , ..., S-) specified by eqn. (3.2). Each coordinate of the vectors a = (a_ , ..., a_J and s = (s., ..., s ) equals +1 or -1. However for reasons which will X K. become clear, it will be more convenient to use 1 in place of -1, and in place of 1. The multiplicative relation (eqn. 3.2) between the vectors "s and "a now becomes the following additive one in modulo 2 arithmetic. S i = " " ^i (m0d 2) (3,3) where the ' • ' represents the vector dot product of the 0, 1 vector a with the integer vector index j. . If the N x K integer matrix J is defined by J = (j^ , .... "j" K ) (3.4) 10 then the vector s which describes the simple symmetry arising from the change of variables described by the vector a satisfies "s = a J (mod 2). (3.5) N _* Moreover the 2 possible choices for a can now be viewed as the elements of the N-dimensional vector space over the Galois field, GF(2), of two elements, a tool familiar in algebraic coding theory (Berlekamp [1968]). The simple symmetries can now be easily classified using the linear algebra of these vector spaces. Theorem 3.1 The set of K-dimensional vectors over GF(2) which describe the set of simple symmetries of the region of stability is the set of vectors spanned, modulo 2, by the row vectors of the matrix J . Proof. Each vector Is arises by eqn. 3.5 from an a . Each a = (a. , . . . , cO can be written as a = a-e*!. + ... + a..e XT (3.6) 11 N N where e . = (0, ..., 1, ..., 0) (3.7) with a 1 in the i coordinate. But then s* - = a^e^J) + ... + a (e J) by linearity; and for each i , e.J is the i row of J . (Note also that by the above theorem the set of simple symmetries forms an abelian group.) 11 Corollary 3.1 The number of simple symmetries equals 2 , where L is the modulo 2 rank of the matrix J . Proof. Immediate. Example 3.1 Consider the filter (eqn. 1.8) studied by Huang. The vector indices in this case are t ± = do) f 2 = (01) (3.8) t 3 = (ID . The matrix J is therefore > - (i J I) ■ < 3 -» 2 The modulo 2 rank of J is clearly 2. Thus there are 4 (=2 ) simple symmetries. Each symmetry is described by an element of the row space of J . They are: si = (000) r 2 = (ioi) 1*3 = (011) r 4 = (no which describes the symmetries (A- > A_ t A*) "*" (,A_»A_,A_^ ■*■ (,~A_ > A_ »~A„,J (3.10) (3.11) -> (A 1 ,-A 2 ,-A 3 ) "*■ ( — A^»~A_,A«y . 12 Note that in Figure 1, there are only two different basic shapes for the region of stability in the eight different quadrants of the coefficient space, and that consistent with the above symmetries each shape occurs symmetrically in four quadrants. Example 3.2 Consider a filter whose transfer function is l/PCz" 1 ^" 1 ^" 1 ^" 1 ) (3.12) where P <*1»V*3'V = X " A 1 Z 1 Z 2 " Vl Z 2 2 3 Z 4 ' A 3 Z 1 Z 2 Z 3 Z 4 (3 * 13) a 3 3 A 3 - A 4 z 2 z 3 z 4 - A 5 z lZ3 z 4 In this case the vector indices are f x = (1301) r 2 = (122D ? 3 = (1331) (3.14) ? 4 = (0331) f = (1031) . And the matrix J is therefore J = J u • (3.15) Calculating modulo 2, and row reducing, 13 J 3 I o A i n i I -»■ I n n i ! n I « (3.16) 4 Therefore J has rank 4, and there are 2 = 16 possible distinct simple symmetries. Moreover each possible symmetry can be described by a modulo 2 sum of the rows of J . For example adding every row we obtain t - (1 1 1) (3.17) which corresponds to the symmetry (A 1 ,A 2 ,A 3 ,A 4 ,A 5 ) -> (-A 1 ,A 2 ,A 3 ,-A 4 ,-A 5 ) (3.18) of the coefficient space. Thus, for example, since we know that in the positive quadrant the shape of the region of stability is the part of the diamond in that quadrant it follows that in the quadrant which corresponds to the above symmetry, the region of stability is again the part of the diamond in that quadrant. Example 3.3 Consider the class of polynomials above without the last term. P(z 1 ,z 2 ,z 3 , Z4 ) = 1 - A^z* - A^z^z^ - A 3 z 1 z 2 3 z 3 3 z 4 3 3 - A.z-z z, . (3.19) Since the rank of J will still be four, and the dimension of the coefficient space is four, it follows that every quadrant is symmetrical to every other by an appropriate simple symmetry. That is, every possible change of sign will occur among the simple symmetries. It follows that 14 the region of stability is the diamond, and I a. I + IaJ + |a o | + I A. I < 1 '1' ' 2 ' '3' '4' is a necessary and sufficient condition for the stability of polynomials of this type. 15 REFERENCES Berlekamp, E. R. [1968], Algebraic Coding Theory, McGraw Hill. Davis, D. and Souchon, L. [1975], "Necessary and Sufficient Stability Conditions for N-Dimensional Recursive Digital Filters" Proc. Ninth Asilomar Conference on Circuits, Systems, and Computers, Pacific Grove, CA. Huang, T. S. [1972], " Stability of two dimensional recursive filters" IEEE Trans. Audio. Electroacoustics, Vol. AU-20, pp 115-128, June. Jury, E. [1974], "Inners and Stability of Dynamic Systems" New York: Wiley Interscience. 16 DISTRIBUTION LIST No. of Copies Defense Documentation Center ]2 Cameron Station Alexandria, Virginia 22314 Library 2 Naval Postgraduate School Monterey, California 93940 Dean of Research, Code 012 2 Naval Postgraduate School Monterey, California 93940 Professor Carroll 0. Wilde 1 Chairman, Department of Mathematics Naval Postgraduate School Monterey, California 93940 Professor Daniel L. Davis 10 Department of Mathematics Naval Postgraduate School Monterey, California 93940 Dr. Richard Lau 1 Office of Naval Research Pasadena, California 91100 17 DUDLEY KNOX LIBRARY ■ RESEARCH REPORTS 5 6853 01057933 7 U1743