(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "The coefficient space appraoch to the stability of multidimensional digital filters"

'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