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 - QOf1)) (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-, , ...» SN) 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) = 0 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 , ..., JN)> where each j. is a non-
negative integer is called a vector index. If for such an index ~j , we
define ~z by

1 Z2 ' * * ZN 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(z1,z2) = 1.00 + 0.5z-z - .llz^z-

then a_0 = 1.00, a.., = .05, a„, = -.11 and all other coefficients equal
zero.

Suppose that a fixed, ordered set (j- , j*0, ..., "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)

Ji

is naturally associated to the point (au. , . . . , su> ) of K-dimensional

Jl TK

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)

Ti

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(z1,z2) = 1 - A1z1 - A2z2 - A3z1z2 , (1.8)

and the associated coefficient space is 3 dimensional euclidean space.
Huang [1972] has shown that (1.8) is stable iff

|A3| < 1

A1+A2| < 1- A3

|A1-A2| < 1+A3 .

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.

A3

FIGURE 1

2. The Basic Theorems

Throughout the following it will be assumed that "J1 , . . . , ^ is a
given, fixed, ordered set of N dimensional vector indices. Thus the
correspondence between polynomials of the form (1.7) and points
(A1 , . . . , A^.) of K-dimensional space is assumed fixed.

The order of a vector index "f = (j-, ..., jM) is defined by

order "f = i. + ... + j„ .

j jj_ jn

A coefficient A. of a polynomial of type (1.7) is called a leading
coefficient if its associated vector index "j1. 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-t1)...(z-tM) (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(a1z, ..., aNz) . (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) £ 0 . (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 , 0 < t <_ 1 , such that p(t) ■ 0. But
then

P(a1t, ..., ty:) = 0 (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'(z1, ..., zN) = P(a1z1, ..., 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'(B1, ..., BN) = 0 iff P(3]_, ..., 3') = 0 where e! - a.3± and for

each i Is! I = I a. 6.1 = |S.|» since la. I =1 .
'i' ' i i1 ' 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- ji
P(Z;L, ..., zN) = 1 - 2^ z • (2-18)

If P(B) = 0 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 >_ 0 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

|A1| + ... + |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.^, ..., ciNzN) (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 0
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.

Si = " " ^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..eXT (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)

f2 = (01) (3.8)

t3 = (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)

r2 = (ioi)

1*3 = (011)

r4 = (no

which describes the symmetries

(A- > A_ t A*) "*" (,A_»A_,A_^

■*■ (,~A_ > A_ »~A„,J

(3.10)

(3.11)

-> (A1,-A2,-A3)
"*■ (— 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 " A1Z1Z2 " VlZ223Z4 ' A3Z1Z2Z3Z4 (3*13)

a 3 3 A 3
- A4z2z3z4 - A5zlZ3z4

In this case the vector indices are

fx = (1301)

r2 = (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 0 0 1 1) (3.17)

which corresponds to the symmetry

(A1,A2,A3,A4,A5) -> (-A1,A2,A3,-A4,-A5) (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(z1,z2,z3,Z4) = 1 - A^z* - A^z^z^ - A3z1z23z33z4

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 + |ao| + 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