# Discrete Time Systems by Mario A. Jordan and Jorge L. Bustamante - HTML preview

**PLEASE NOTE**: This is an HTML preview only and some elements such as links or page numbers may be incorrect.

Download the book in PDF, ePub, Kindle for a complete version.

**DISCRETE TIME SYSTEMS**

Edited by **Mario A. Jordán **

and** Jorge L. Bustamante**

**Discrete Time Systems**

Edited by Mario A. Jordán and Jorge L. Bustamante

**Published by InTech**

Janeza Trdine 9, 51000 Rijeka, Croatia

**Copyright © 2011 InTech**

All chapters are Open Access articles distributed under the Creative Commons

Non Commercial Share Alike Attribution 3.0 license, which permits to copy,

distribute, transmit, and adapt the work in any medium, so long as the original

work is properly cited. After this work has been published by InTech, authors

have the right to republish it, in whole or part, in any publication of which they

are the author, and to make other personal use of the work. Any republication,

referencing or personal use of the work must explicitly identify the original source.

Statements and opinions expressed in the chapters are these of the individual contributors

and not necessarily those of the editors or publisher. No responsibility is accepted

for the accuracy of information contained in the published articles. The publisher

assumes no responsibility for any damage or injury to persons or property arising out

of the use of any materials, instructions, methods or ideas contained in the book.

**Publishing Process Manager** Ivana Lorkovic

**Technical Editor** Teodora Smiljanic

**Cover Designer** Martina Sirotic

**Image Copyright** Emelyano, 2010. Used under license from Shutterstock.com

First published March, 2011

Printed in India

A free online edition of this book is available at www.intechopen.com

Additional hard copies can be obtained from orders@intechweb.org

Discrete Time Systems, Edited by Mario A. Jordán and Jorge L. Bustamante

p. cm.

ISBN 978-953-307-200-5

**free **online editions of InTech

Books and Journals can be found at

**www.intechopen.com**

Contents

**Preface IX**

**Part 1**

**Discrete-Time Filtering 1**

Chapter 1

**Real-time Recursive State Estimation **

**for Nonlinear Discrete Dynamic Systems **

**with Gaussian or non-Gaussian Noise 3**

Kerim Demirbaş

Chapter 2

**Observers Design for a Class of Lipschitz**

**Discrete-Time Systems with Time-Delay 19**

Ali Zemouche and Mohamed Boutayeb

Chapter 3

**Distributed Fusion Prediction for Mixed **

**Continuous-Discrete Linear Systems 39**

Ha-ryong Song, Moon-gu Jeon and Vladimir Shin

Chapter 4

**New Smoothers for Discrete-time Linear **

**Stochastic Systems with Unknown Disturbances 53**

Akio Tanikawa

Chapter 5

**On the Error Covariance Distribution **

**for Kalman Filters with Packet Dropouts 71**

Eduardo Rohr Damián Marelli, and Minyue Fu

Chapter 6

**Kalman Filtering for Discrete Time Uncertain Systems 93**

Rodrigo Souto, João Ishihara and Geovany Borges

**Part 2**

**Discrete-Time Fixed Control 109**

Chapter 7

**Stochastic Optimal Tracking with Preview **

**for Linear Discrete Time Markovian Jump Systems 111**

Gou Nakura

Chapter 8

**The Design of a Discrete Time Model Following **

**Control System for Nonlinear Descriptor System 131**

Shigenori Okubo and Shujing Wu

VI

Contents

Chapter 9

**Output Feedback Control of Discrete-time **

**LTI Systems: Scaling LMI Approaches 141**

Jun Xu

Chapter 10

**Discrete Time Mixed LQR/H**∞ **Control Problems 159**

Xiaojie Xu

Chapter 11

**Robust Control Design of Uncertain **

**Discrete-Time Systems with Delays 179**

Jun Yoneyama, Yuzu Uchida and Shusaku Nishikawa

Chapter 12

**Quadratic D Stabilizable Satisfactory Fault-tolerant **

**Control with Constraints of Consistent Indices **

**for Satellite Attitude Control Systems 195**

Han Xiaodong and Zhang Dengfeng

**Part 3**

**Discrete-Time Adaptive Control 205**

Chapter 13

**Discrete-Time Adaptive Predictive Control **

**with Asymptotic Output Tracking 207**

Chenguang Yang and Hongbin Ma

Chapter 14

**Decentralized Adaptive Control **

**of Discrete-Time Multi-Agent Systems 229**

Hongbin Ma, Chenguang Yang and Mengyin Fu

Chapter 15

**A General Approach to Discrete-Time **

**Adaptive Control Systems with Perturbed **

**Measures for Complex Dynamics - Case Study: **

**Unmanned Underwater Vehicles 255**

Mario Alberto Jordán and Jorge Luis Bustamante

**Part 4**

**Stability Problems 281**

Chapter 16

**Stability Criterion and Stabilization **

**of Linear Discrete-time System **

**with Multiple Time Varying Delay 283**

Xie Wei

Chapter 17

**Uncertain Discrete-Time Systems with Delayed**

**State: Robust Stabilization with Performance**

**Specification via LMI Formulations 295**

Valter J. S. Leite, Michelle F. F. Castro, André F. Caldeira,

Márcio F. Miranda and Eduardo N. Gonçalves

Chapter 18

**Stability Analysis of Grey Discrete Time **

**Time-Delay Systems: A Sufficient Condition 327**

Wen-Jye Shyr and Chao-Hsing Hsu

Contents

VII

Chapter 19

**Stability and L2 Gain Analysis of Switched Linear**

**Discrete-Time Descriptor Systems 337**

Guisheng Zhai

Chapter 20

**Robust Stabilization for a Class of Uncertain **

**Discrete-time Switched Linear Systems 351**

Songlin Chen, Yu Yao and Xiaoguan Di

**Part 5**

**Miscellaneous Applications 361**

Chapter 21

**Half-overlap Subchannel Filtered MultiTone **

**Modulation and Its Implementation 363**

Pavel Silhavy and Ondrej Krajsa

Chapter 22

**Adaptive Step-size Order Statistic LMS-based**

**Time-domain Equalisation in Discrete **

**Multitone Systems 383**

Suchada Sitjongsataporn and Peerapol Yuvapoositanon

Chapter 23

**Discrete-Time Dynamic Image-Segmentation System 405**

Ken’ichi Fujimoto, Mio Kobayashi and Tetsuya Yoshinaga

Chapter 24

**Fuzzy Logic Based Interactive Multiple Model **

**Fault Diagnosis for PEM Fuel Cell Systems 425**

Yan Zhou, Dongli Wang, Jianxun Li, Lingzhi Yi and Huixian Huang

Chapter 25

**Discrete Time Systems with Event-Based Dynamics: **

**Recent Developments in Analysis **

**and Synthesis Methods 447**

Edgar Delgado-Eckert, Johann Reger and Klaus Schmidt

Chapter 26

**Discrete Deterministic and Stochastic Dynamical**

**Systems with Delay - Applications 477**

Mihaela Neamţu and Dumitru Opriş

Chapter 27

**Multidimensional Dynamics: **

**From Simple to Complicated 505**

Kang-Ling Liao, Chih-Wen Shih and Jui-Pin Tseng

Preface

Discrete-Time Systems comprehend an important and broad research fi eld. The con-

solidation of digital-based computational means in the present, pushes a technological

tool into the fi eld with a tremendous impact in areas like Control, Signal Processing,

Communications, System Modelling and related Applications. This fact has enabled

numerous contributions and developments which are either genuinely original as

discrete-time systems or are mirrors from their counterparts of previously existing

continuous-time systems.

This book att empts to give a scope of the present state-of-the-art in the area of Discrete-

Time Systems from selected international research groups which were specially con-

voked to give expressions to their expertise in the fi eld.

The works are presented in a uniform framework and with a formal mathematical

context.

In order to facilitate the scope and global comprehension of the book, the chapters were

grouped conveniently in sections according to their affi

nity in 5 signifi cant areas.

The fi rst group focuses the problem of Filtering that encloses above all designs of State

Observers, Estimators, Predictors and Smoothers. It comprises Chapters 1 to 6.

The second group is dedicated to the design of Fixed Control Systems (Chapters 7 to

12). Herein it appears designs for Tracking Control, Fault-Tolerant Control, Robust Con-

trol, and designs using LMI- and mixed LQR/Hoo techniques.

The third group includes Adaptive Control Systems (Chapter 13 to 15) oriented to the

specialities of Predictive, Decentralized and Perturbed Control Systems.

The fourth group collects works that address Stability Problems (Chapter 16 to 20).

They involve for instance Uncertain Systems with Multiple and Time-Varying Delays

and Switched Linear Systems.

Finally, the fi ft h group concerns miscellaneous applications (Chapter 21 to 27). They

cover topics in Multitone Modulation and Equalisation, Image Processing, Fault Diag-

nosis, Event-Based Dynamics and Analysis of Deterministic/Stochastic and Multidi-

mensional Dynamics.

X

Preface

We think that the contribution in the book, which does not have the intention to be

all-embracing, enlarges the fi eld of the Discrete-Time Systems with signifi cation in the

present state-of-the-art. Despite the vertiginous advance in the fi eld, we think also that

the topics described here allow us also to look through some main tendencies in the

next years in the research area.

**Mario A. Jordán and Jorge L. Bustamante**

IADO-CCT-CONICET

Dep. of Electrical Eng. and Computers

National University of the South

Argentina

**Part 1 **

**Discrete-Time Filtering **

** **

**1**

**Real-time Recursive State Estimation for **

**Nonlinear Discrete Dynamic Systems with **

**Gaussian or non-Gaussian Noise **

Kerim Demirba¸s

*Department of Electrical and Electronics Engineering*

*Middle East Technical University*

*Inonu Bulvari, 06531 Ankara*

*Turkey*

**1. Introduction**

Many systems in the real world are more accurately described by nonlinear models. Since

the original work of Kalman (Kalman, 1960; Kalman & Busy, 1961), which introduces the

Kalman filter for linear models, extensive research has been going on state estimation

of nonlinear models; but there do not yet exist any optimum estimation approaches for

all nonlinear models, except for certain classes of nonlinear models; on the other hand,

different suboptimum nonlinear estimation approaches have been proposed in the literature

(Daum, 2005). These suboptimum approaches produce estimates by using some sorts of

approximations for nonlinear models. The performances and implementation complexities

of these suboptimum approaches surely depend upon the types of approximations which

are used for nonlinear models. Model approximation errors are an important parameter

which affects the performances of suboptimum estimation approaches. The performance of a

nonlinear suboptimum estimation approach is better than the other estimation approaches for

specific models considered, that is, the performance of a suboptimum estimation approach is

model-dependent.

The most commonly used recursive nonlinear estimation approaches are the extended

Kalman filter (EKF) and particle filters. The EKF linearizes nonlinear models by Taylor

series expansion (Sage & Melsa, 1971) and the unscented Kalman filter (UKF) approximates

*a posteriori * densities by a set of weighted and deterministically chosen points (Julier, 2004).

Particle filters approximates *a posterior * densities by a large set of weighted and randomly

selected points (called particles) in the state space (Arulampalam et al., 2002; Doucet et al.,

2001; Ristic et al., 2004). In the nonlinear estimation approaches proposed in (Demirba¸s,

1982; 1984; Demirba¸s & Leondes, 1985; 1986; Demirba¸s, 1988; 1989; 1990; 2007; 2010): the

disturbance noise and initial state are first approximated by a discrete noise and a discrete

initial state whose distribution functions the best approximate the distribution functions of the

disturbance noise and initial state, states are quantized, and then multiple hypothesis testing

is used for state estimation; whereas Grid-based approaches approximate *a posteriori * densities

by discrete densities, which are determined by predefined gates (cells) in the predefined state

space; if the state space is not finite in extent, then the state space necessitates some truncation

of the state space; and grid-based estimation approaches assume the availability of the state

4

Discrete Time Systems

transition density *p*( *x*( *k*) *|x*( *k − * 1)), which may not easily be calculated for state models with

nonlinear disturbance noise (Arulampalam et al., 2002; Ristic et al., 2004). The Demirba¸s

estimation approaches are more general than grid-based approaches since 1) the state space

need not to be truncated, 2) the state transition density is not needed, 3) state models can be

any nonlinear functions of the disturbance noise.

This chapter presents an online recursive nonlinear state filtering and prediction scheme for

nonlinear dynamic systems. This scheme is recently proposed in (Demirba¸s, 2010) and is

referred to as the DF throughout this chapter. The DF is very suitable for state estimation of

nonlinear dynamic systems under either missing observations or constraints imposed on state

estimates. There exist many nonlinear dynamic systems for which the DF outperforms the

extended Kalman filter (EKF), sampling importance resampling (SIR) particle filter (which is

sometimes called the bootstrap filter), and auxiliary sampling importance resampling (ASIR)

particle filter. Section 2 states the estimation problem. Section 3 first discusses discrete noises

which approximate the disturbance noise and initial state, and then presents approximate

state and observation models. Section 4 discusses optimum state estimation of approximate

dynamic models. Section 5 presents the DF. Section 6 yields simulation results of two

examples for which the DF outperforms the EKF, SIR, and ASIR particle filters. Section 7

concludes the chapter.

**2. Problem statement**

This section defines state estimation problem for nonlinear discrete dynamic systems. These

dynamic systems are described by

State Model

*x*( *k *+ 1) = *f *( *k*, *x*( *k*), *w*( *k*))

(1)

Observation Model

*z*( *k*) = *g*( *k*, *x*( *k*), *v*( *k*)),

(2)

where *k * stands for the discrete time index; *f *: **R** *x***R** *mx***R** *n → ***R** *m * is the state transition function; **R** *m * is the *m*-dimensional Euclidean space; *w*( *k*) *∈ ***R** *n * is the disturbance noise vector at time *k*; *x*( *k*) *∈ ***R** *m * is the state vector at time k; *g *: **R** *x***R** *mx***R** *p → ***R** *r * is the observation function; *v*( *k*) *∈ ***R** *p * is the observation noise vector at time *k*; *z*( *k*) *∈ ***R** *r * is the observation vector at time *k*; *x*(0), *w*( *k*), and *v*( *k*) are all assumed to be independent with known distribution functions.

Moreover, it is assumed that there exist some constraints imposed on state estimates. The DF

recursively yields a predicted value ˆ *x*( *k|k − * 1) of the state *x*( *k*) given the observation sequence

from time one to time *k − * 1, that is, *Zk−* 1 Δ

= *{z*(1), *z*(2), . . . , *z*( *k − * 1) *}*; and a filtered value

ˆ *x*( *k|k*) of the state *x*( *k*) given the observation sequence from time one to time *k*, that is, *Zk*.

Estimation is accomplished by first approximating the disturbance noise and initial state with

discrete random noises, quantizing the state, that is, representing the state model with a time

varying state machine, and an online suboptimum implementation of multiple hypothesis

testing.

**3. Approximation**

This section first discusses an approximate discrete random vector which approximates a

random vector, and then presents approximate models of nonlinear dynamic systems.

Real-time Recursive State Estimation for Nonlinear

Discrete Dynamic Systems with Gaussian or non-Gaussian Noise

5

**3.1 Approximate discrete random noise**

In this subsection: an approximate discrete random vector with *n * possible values of a

random vector is defined; approximate discrete random vectors are used to approximate

the disturbance noise and initial state throughout the chapter; moreover, a set of equations

which must be satisfied by an approximate discrete random variable with *n * possible values

of an absolutely continuous random variable is given (Demirba¸s, 1982; 1984; 2010); finally, the

approximate discrete random variables of a Gaussian random variable are tabulated.

Let *w * be an *m*-dimensional random vector. **An approximate discrete random vector with ** *n*

**possible values **of *w*, denoted by *wd*, is defined as an *m*-dimensional discrete random vector

with *n * possible values whose distribution function the best approximates the distribution

function of *w * over the distribution functions of all *m*-dimensional discrete random vectors

with *n * possible values, that is

*w*

*−* 1

*d *= min

*{*

[ *Fy*( *a*) *− Fw*( *a*)]2 *da}*

(3)

*y D*

**R** *n*

where *D * is the set of all *m*-dimensional discrete random vectors with *n * possible values, *Fy*( *a*)

is the distribution function of the discrete random vector *y*, *Fw*( *a*) is the distribution function

of the random vector *w*, and **R** *m * is the *m*-dimensional Euclidean space. An approximate

discrete random vector *wd * is, in general, numerically, offline-calculated, stored and then used

for estimation. The possible values of *wd * are denoted by *wd* 1, *wd* 2, ...., and *wdn *; and the

occurrence probability of the possible value *wdi * is denoted by *Pw *, that is

*di*

Δ

*Pw *= *Prob{w*

*di*

*d *= *wdi }*.

(4)

where *Prob{wd*(0) = *wdi} * is the occurrence probability of *wdi*.

Let us now consider the case that *w * is an absolutely continuous random variable. Then, *wd * is

an approximate discrete random variable with *n * possible values whose distribution function

the best approximates the distribution function *Fw*( *a*) of *w * over the distribution functions of

all discrete random variables with *n * possible values, that is

*w*

*−* 1

*d *= min

*{J*( *Fy*( *a*)) *}*

*y D*

in which the distribution error function (the objective function) *J*( *Fy*( *a*)) is defined by

*J*( *Fy*( *a*)) Δ

=

[ *Fy*( *a*) *− Fw*( *a*)]2 *da*

**R**

where *D * is the set of all discrete random variables with *n * possible values, *Fy*( *a*) is the

distribution function of the discrete random variable *y*, *Fw*( *a*) is the distribution function of the

absolutely continuous random variable *w*, and **R **is the real line. Let the distribution function

*Fy*( *a*) of a discrete random variable *y * be given by

⎧

⎨0 if *a < y* 1

*Fy*( *a*) Δ

= ⎩ *Fy * if *y*

*i*

*i ≤ a < yi*+1, *i *= 1, 2, . . . , *n − * 1

1

if *a ≥ yn*.

Then the distribution error function *J*( *Fy*( *a*)) can be written as

*y*

*n−* 1

1

*yi*+1

∞

*J*( *Fy*( *a*)) =

*F* 2

∑

[ *Fy − Fw*( *a*)]2 *da *+

[1 *− Fw*( *a*)]2 *da*.

*−*∞ *w*( *a*) *da *+

*i*

*i*=1 *yi*

*yn*

6

Discrete Time Systems

Let the distribution function *Fw *( *a*) of an approximate discrete random variable *w*

*d*

*d * be

⎧

⎨0

if *a < wd* 1

*Fw *( *a*) Δ

= *F*

if *w*

*d*

⎩ *wdi*

*di ≤ a < wdi*+1, *i *= 1, 2, . . . , *n − * 1

1

if *a ≥ wdn*.

It can readily be shown that the distribution function *Fw *( *a*) of the approximate discrete

*d*

random variable *wd * must satisfy the set of equations given by

*Fw *=2 *F*

*d* 1

*w*( *wd* 1);

*Fw *+ *F*

=2 *F*

*di*

*wdi*+1

*w*( *wdi*+1), *i *= 1, 2, . . . , *n − * 2;

(5)

1 + *Fw*

=2 *F*

*dn−* 1

*w*( *wdn*);

*wdi*+1

*Fw *[ *w*

*F*

*di*

*di*+1 *− wdi*]=

*w*( *a*) *da*, *i *= 1, 2, . . . , *n − * 1.

*wdi*

The values *wd* 1, *wd* 2, ..., *wdn*, *Fw *, *F *, ..., *F*

satisfying the set of Eqs. (5) determine the

*d* 1

*wd* 2

*wdn*

distribution function of *wd*. These values can be, in general, obtained by numerically solving

Eqs. (5). Then the possible values of the approximate discrete random variable *wd * become

*wd* 1, *wd* 2, ..., and *wdn *; and the occurrence probabilities of these possible values are obtained

by

⎧

⎨ *Fw*

if *i *= 1

*d* 1

*Pw *=

*F*

*− F*

if *i *= 2, 3, . . . , *n − * 1

*di*

⎩ *wdi*

*wdi−* 1

1 *− Fw*

if *i *= *n*.

*dn*

where *Pw *= *Prob{w*

*di*

*d *= *wdi }*, which is the occurrence probability of *wdi*.

Let *y * be a Gaussian random variable with zero mean and unit variance. An approximate

discrete random variable *yd * with *n * possible values was numerically calculated for different

*n*’s by using the set of Eqs.

(5).

The possible values *yd* 1, *yd* 2, ..., *ydn * of *yd * and the

occurrence probabilities *Py *, *P *, ..., *P*

of these possible values are given in Table 1, where

*d* 1

*yd* 2

*ydn*

Δ

*Py*

= *Prob{y*

*di*

*d *= *ydi }*.

As an example, the possible values of an approximate discrete

random variable with 3 possible values of a Gaussian random variable with zero mean and

unit variance are -1.005, 0.0, and 1.005; and the occurrence probabilities of these possible

values are 0.315, 0.370, and 0.315, respectively. Let *w * be a Gaussian random variable with

mean *E{w} * and variance *σ* 2. This random variable can be expressed as *w *= *yσ *+ *E{w}*.

Hence, the possible values of an approximate discrete random variable of *w * are given by

*wdi *= *ydiσ *+ *E{w}*, *where i *= 1, 2, 3, ..., *n*; and the occurrence probability of the possible value

*wdi * is the same as the occurrence probability of *ydi*, which is given in Table 1.

**3.2 Approximate models**

For state estimation, the state and observation models of Eqs. (1)and (2) are approximated by

the time varying finite state model and approximate observation model which are given by

Finite State Model

*xq*( *k *+ 1) = *Q*( *f *( *k*, *xq*( *k*), *wd*( *k*)))

(6)

Approximate Observation Model

*z*( *k*) = *g*( *k*, *xq*( *k*), *v*( *k*)),

(7)

Real-time Recursive State Estimation for Nonlinear

Discrete Dynamic Systems with Gaussian or non-Gaussian Noise

7

*n*

*yd* 1

*yd* 2

*yd* 3

*yd* 4

*yd* 5

*yd* 6

*yd* 7

*yd* 8

*yd* 9 *yd* 10

*Py*

*P*

*P*

*P*

*P*

*P*

*P*

*P*

*P*

*P*

*d* 1

*yd* 2

*yd* 3

*yd* 4

*yd* 5

*yd* 6

*yd* 7

*yd* 8

*yd* 9

*yd* 10

1 0.000

1.000

2 -0.675 0.675

0.500 0.500

3 -1.005 0.0

1.005

0.315 0.370 0.315

4 -1.218 -0.355 0.355 1.218

0.223 0.277 0.277 0.223

5 -1.377 -0.592 0.0

0.592 1.377

0.169 0.216 0.230 0.216 0.169

6 -1.499 -0.768 -0.242 0.242 0.768 1.499

0.134 0.175 0.191 0.191 0.175 0.134

7 -1.603 -0.908 -0.424 0.0

0.424 0.908 1.603

0.110 0.145 0.162 0.166 0.162 0.145 0.110

8 -1.690 -1.023 -0.569 -0.184 0.184 0.569 1.023 1.690

0.092 0.124 0.139 0.145 0.145 0.139 0.124 0.092

9 -1.764 -1.120 -0.690 -0.332

0

0.332 0.690 1.120 1.764

0.079 0.106 0.121 0.129 0.130 0.129 0.121 0.106 0.079

10 -1.818 -1.199 -0.789 -0.453 -0.148 0.148 0.453 0.789 1.199 1.818

0.069 0.093 0.106 0.114 0.118 0.118 0.114 0.106 0.093 0.069

Table 1. Approximate Discrete Random Variables the best Approximating the Gaussian

Random Variable with Zero Mean and Unit Variance

where *wd*( *k*) is an approximate discrete random vector with, say, *n * possible values of the

disturbance noise vector *w*( *k*); this approximate vector is pre(offline)-calculated, stored and

then used for estimation to calculate quantization levels at time *k *+ 1; the possible values of

*wd*( *k*) are denoted by *wd* 1( *k*), *wd* 2( *k*), ...., and *wdn*( *k*) ; *Q *: **R** *m → ***R** *m * is a quantizer which first divides the *m*-dimensional Euclidean space into nonoverlapping generalized rectangles

(called gates) such that the union of all rectangles is the *m*-dimensional Euclidean space, and

then assigns to each rectangle the center point of the rectangle, Fig. 1 (Demirba¸s, 1982; 1984;

2010); *xq*( *k*), *k > * 0, is the quantized state vector at time *k * and its quantization levels, whose

number is (say) *mk*, are denoted by *xq* 1( *k*), *xq* 2( *k*), ...., and *xqm *( *k*). The quantization levels *k*

of *xq*( *k *+ 1) are calculated by substituting *xq*( *k*) = *xqi*( *k*) ( *i *= 1, 2, . . . , *mk*) for *xq*( *k*) and *wd*( *k*) = *wdj*( *k*) ( *j *= 1, 2, . . . , *n*) for *wd*( *k*) in the finite state model of Eq. (6). As an example, let the quantization level *xqi*( *k*) in the gate *Gi * be mapped into the gate *Gj * by the *lth*-possible

value *wdl*( *k*) of *wd*( *k*), then, *x*( *k *+ 1) is quantized to *xqj*( *k *+ 1), Fig. 1. One should note that the approximate models of Eqs. (6) and (7) approach the models of Eqs. (1) and (2) as the gate

sizes ( *GS*) *→ * 0 and *n → *∞. An optimum state estimation of the models of Eqs. (6) and (7) is

discussed in the next section.

**4. Optimum state estimation**

This section discuses an optimum estimation of the models of Eqs. (6) and (7) by using

multiple hypothesis testing.

On the average overall error probability sense, optimum

estimation of states of the models of Eqs. (6) and (7) is done as follows: Finite state model

8

Discrete Time Systems

*x *( *k*)

*qi*

*G*

*m*

*R*

*i*

*f *( *k*, *x *( *k*), *w *( *k*)) (

*x k * )

1

*qi*

*di*

*x*( *k * )

1

*Gj*

(

*Q *(

*x k * ))

1 *x *( *k * )

1

*qj*

*x *( *k* )

1

*qj*

Fig. 1. Quantization of States

of Eq. (6) is represented by a trellis diagram from time 0 to time *k *(Demirba¸s, 1982; 1984;

Demirba¸s & Leondes, 1985; Demirba¸s, 2007). The nodes at time *j * of this trellis diagram

represent the quantization levels of the state *x*( *j*). The branches of the trellis diagram represent

the transitions between quantization levels. There exist, in general, many paths through this

trellis diagram. Let *Hi * denote the *ith * path (sometimes called the *ith * hypothesis) through the

trellis diagram. Let *xiq*( *j*) be the node (quantization level) through which the path *Hi * passes

at time *j*. The estimation problem is to select a path (sometimes called the estimator path)

through the trellis diagram such that the average overall error probability is minimized for

decision (selection). The node at time *k * along this estimator path will be the desired estimate

of the state *x*( *k*). In Detection Theory (Van Trees, 2001; Weber, 1968): it is well-known that the

optimum decision rule which minimizes the average overall error probability is given by

*Select Hn as the estimator path i f M*( *Hn*) *≥ M*( *Hl*) *f or all l *= *n*,

(8)

where *M*( *Hn*) is called the metric of the path *M*( *Hn*) and is defined by

*M*( *Hn*) Δ

= ln *{p*( *Hn*) *Prob{observation sequence | Hn}}*,

(9)

where ln stands for the natural logarithm, *p*( *Hn*) is the occurrence probability (or the *a*

*priori probability*) of the path *Hn*, and *Prob{observation sequence | Hn} * is the conditional

probability of the observation sequence given that the actual values of the states are equal

to the quantization levels along the path *Hn*. If the inequality in the optimum decision rule

becomes an equality for an observation sequence, anyone of the paths satisfying the equality

can be chosen as the estimator path, which is a path having the biggest metric.

It follows, from the assumption that samples of the observation noise are independent, that

*Prob{observation sequence | Hn} * can be expressed as

*k*

*Prob{observation sequence | Hn} *= ∏ *λ*( *z*( *j*) *| xnq*( *j*))

(10)

*j*=1

Real-time Recursive State Estimation for Nonlinear

Discrete Dynamic Systems with Gaussian or non-Gaussian Noise

9

where

*λ*( *z*( *j*) *|xnq*)( *j*)) Δ= 1

if z(j) is neither available nor used for estimation

(11)

*p*( *z*( *j*) *|xnq*( *j*))

if z(j) is available and used for estimation,

in which, *p*( *z*( *j*) *|xnq*( *j*)) is the conditional density function of *z*( *j*) given that the actual value of state is equal to *xnq*( *j*), that is, *x*( *j*) = *xnq*( *j*); and this density function is calculated by using the observation model of Eq. (2).

It also follows, from the assumption that all samples of the disturbance noise and the initial

state are independent, that the *a priori probability * of *Hn * can be expressed as

*k*

*p*( *Hn*) = *Prob{xq*(0) = *xnq*(0) *} *∏ *T*( *xnq*( *j − * 1) *→ xnq*( *j*)),

(12)

*j*=1

where *Prob{xq*(0) = *xnq*(0) *} * is the occurrence probability of the initial node (or quantization

level) *xnq*(0), and *T*( *xnq*( *j − * 1) *→ xnq*( *j*)) is the transition probability from the quantization

level *xnq*( *j − * 1) to the quantization level *xnq*( *j*)), that is, *T*( *xjq*( *i − * 1) *→ xnq*( *j*)) Δ

= *Prob{xq*( *j*) =

*xnq*( *j*) *|xq*( *j − * 1) = *xnq*( *j − * 1) *}*, which is the probability that *xnq*( *j − * 1) is mapped to *xnq*( *j*) by the finite state model of Eq. (6) with possible values of *wd*( *j − * 1). Since the transition from

*xnq*( *j − * 1) to *xnq*( *j*) is determined by possible values of *wd*( *j − * 1), this transition probability is the sum of occurrence probabilities of all possible values of *wd*( *j − * 1) which map *xnq*( *j − * 1) to

*xnq*( *j*).

The estimation problem is to find the estimator path, which is the path having the biggest

metric through the trellis diagram. This is accomplished by the Viterbi Algorithm (Demirba¸s,

1982; 1984; 1989; Forney, 1973); which systematically searches all paths through the trellis

diagram. The number of quantization levels of the finite state model, in general, increases

exponentially with time *k*. As a result, the implementation complexity of this approach

increases exponentially with time k (Demirba¸s, 1982; 1984; Demirba¸s & Leondes, 1985;

Demirba¸s, 2007). In order to overcome this obstacle, a block-by-block suboptimum estimation

scheme was proposed in (Demirba¸s, 1982; 1984; Demirba¸s & Leondes, 1986; Demirba¸s, 1988;

1989; 1990). In this estimation scheme: observation sequence was divided into blocks of

constant length. Each block was initialized by the final state estimate from the last block. The

initialization of each block with only a single quantization level (node), that is, the reduction

of the trellis diagram to one node at the end of each block, results in state estimate divergence

for long observation sequences, i.e., large time *k*, even though the implementation complexity

of the proposed scheme does not increase with time (Kee & Irwin, 1994). The online and

recursive state estimation scheme which is recently proposed in (Demirba¸s, 2010) prevents

state estimate divergence caused by one state initialization of each block for the block-by-block

estimation. This recently proposed estimation scheme, referred to as the DF throughout

this chapter, first prunes all paths going through the nodes which do not satisfy constraints

imposed on estimates and then assigns a metric to each node (or quantization level) in the

trellis diagram. Furthermore, at each time (step, or iteration), the number of considered state

quantization levels (nodes) is limited by a selected positive integer *MN*, which stands for

the maximum number of quantization levels considered through the trellis diagram; in other

words , *MN * nodes having the biggest metrics are kept through the trellis diagram and all the

paths going through the other nodes are pruned. Hence, the implementation complexity of

the DF does not increase with time. The number *MN * is one of the parameters determining

the implementation complexity and the performance of the DF.

10

Discrete Time Systems

**5. Online state estimation**

This section first yields some definitions, and then presents the DF.

**5.1 Definitions**

**Admissible initial state quantization level **: a possible value *xqi*(0) Δ

= *xdi*(0) of an

approximate discrete random vector *xq*(0) Δ

= *xd*(0) of the initial state vector *x*(0) is said

to be an admissible quantization level of the initial state vector (or an admissible initial

state quantization level) if this possible value satisfies the constraints imposed on the state

estimates. Obviously, if there do not exist any constraints imposed on the state estimates,

then all possible values of the approximate discrete random vector *xq*(0) are admissible.

**Metric of an admissible initial state quantization level**: the natural logarithm of the

occurrence probability of an admissible initial quantization level *xqi*(0) is referred to as the

metric of this admissible initial quantization level. This metric is denoted by *M*( *xqi*(0)), that

is

*M*( *xqi*(0)) Δ

= ln *{Prob{xq*(0) = *xqi*(0) *}}*.

(13)

where *Prob{xq*(0) = *xqi*(0) *} * is the occurrence probability of *xqi*(0).

**Admissible state quantization level at time ** *k*: a quantization level *xqi*( *k*) of a state vector

*x*( *k*), where *k ≥ * 1, is called an admissible quantization level of the state (or an admissible

state quantization level) at time *k * if this quantization level satisfies the constraints imposed

on the state estimates. Surely, if there do not exist any constraints imposed on the state

estimates, then all the quantization levels of the state vector *x*( *k*), which are calculated by Eq.

(6), are admissible.

**Maximum number of considered state quantization levels at each time**: *MN * stands for the

maximum number of admissible state quantization levels which are considered at each time

(step or iteration) of the DF. *MN * is a preselected positive integer. A bigger value of *MN * yields

better performance, but increases implementation complexity of the DF.

**Metric of an admissible quantization level (or node) at time ** *k***, where ** *k ≥ * 1: the metric of an

admissible quantization level *xqj*( *k*), denoted by *M*( *xqj*( *k*)), is defined by

*M*( *xqj*( *k*)) Δ

=max *{M*( *xqn*( *k − * 1)) + *ln*[ *T*( *xqn*( *k − * 1) *→ xqj*( *k*))] *}*

*n*

+ *ln*[ *λ*( *z*( *k*) *|xqj*( *k*))],

(14)

where the maximization is taken over all considered state quantization levels at time *k − * 1

which are mapped to the quantization level *xqj*( *k*) by the possible values of *wd*( *k − * 1); *ln*

stands for the natural logarithm; *T*( *xqn*( *k − * 1) *→ xqj*( *k*)) is the transition probability from

*xqi*( *k − * 1) to *xqj*( *k*) is given by

*T*( *xqi*( *k − * 1) *→ xqj*( *k*)) = ∑ *Prob{wd*( *k − * 1) = *wdn*( *k − * 1) *}*,

(15)

*n*

where *Prob{wd*( *k − * 1) = *wdn*( *k − * 1) *} * is the occurrence probability of *wdn*( *k − * 1) and the summation is taken over all possible values of *wd*( *k − * 1) which maps *xqi*( *k − * 1) to *xqj*( *k*); in

Real-time Recursive State Estimation for Nonlinear

Discrete Dynamic Systems with Gaussian or non-Gaussian Noise

11

other words, the summation is taken over all possible values of *wd*( *k − * 1) such that

*Q*( *f *( *k − * 1, *xqi*( *k − * 1), *wdn*( *k − * 1))) = *xqj*( *k*);

(16)

and

*λ*( *z*( *k*) *|xqj*( *k*)) Δ= 1

if z(j) is neither available nor used for estimation

(17)

*p*( *z*( *k*) *|xqj*( *k*))

if z(j) is available and used for estimation,

in which, *p*( *z*( *k*) *|xqj*( *k*)) is the conditional density function of *z*( *k*) given that the actual value of state *x*( *k*) = *xqj*( *k*), and this density function is calculated by using the observation model

of Eq. (2).

**5.2 Estimation scheme (DF)**

A flowchart of the DF is given in Fig. 3 for given *Fw*( *k*)( *a*), *Fx*(0)( *a*), *MN*, *n*, *m *, and *GS*; where *Fw*( *k*)( *a*) and *Fx*(0)( *a*) are the distribution functions of *w*( *k*) and *x*(0) respectively, *n * and *m * are the numbers of possible values of approximate random vectors of *w*( *k*) and *x*(0) respectively;

*GS * is the gate size; and *z*( *k*) is the observation at time *k*. The parameters *MN*, *n*, *m *, and *GS * determine the implementation complexity and performance of the DF. The number of

possible values of the approximate disturbance noise *wd*( *k*) is assumed to be the same, *n *, for

all iterations, i.e., for all *k*. The filtered value ˆ *x*( *k|k*) and predicted value ˆ *x*( *k|k − * 1) of the state

*x*( *k*) are recursively determined by considering only *MN * admissible state quantization levels

with the biggest metrics and discarding other quantization levels at each recursive step (each

iteration or time) of the DF. Recursive steps of the DF is described below.

*Initial Step (Step 0): * an approximate discrete random vector *xd*(0) with *m * possible values of

the initial state *x*(0) is offline calculated by Eq. (3). The possible values of this approximate

random vector are defined as the initial state quantization levels (nodes). These initial state

Δ

quantization levels are denoted by *xq* 1(0), *xq* 2(0), ..., and *xqm*(0), where *x*

=

*qi*(0)

*xdi*(0) ( *i *=

1 2 ... *m*). Admissible initial state quantization levels, which satisfy the constraints imposed

on state estimates, are determined and the other initial quantization levels are discarded. If

the number of admissible initial quantization levels is zero, then the number, *m*, of possible

values of the approximate initial random vector *xd*(0) is increased and *the initial step * of the

DF is repeated from the beginning; otherwise, the metrics of admissible initial quantization

levels are calculated by Eq. (13). The admissible initial state quantization levels (represented

by *xq* 1(0), *xq* 2(0), ..., and *xqN *(0)) and their metrics are considered in order to calculate state

0

quantization levels and their metrics at time *k *= 1. These considered quantization levels are

denoted by nodes (at time 0) on the first row (or column) of two rows (or columns) trellis

diagram at the first step *k *= 1 of the DF, Fig. 2.

*State estimate at time * 0 *: * if the mean value of *x*(0) satisfies constraints imposed on state estimates

such as the case that there do not exist any estimate constraints , then this mean value is taken

as both ˆ *x*(0 *|* 0) and ˆ *x*(0 *|* 0 *− * 1); otherwise, the admissible initial state quantization level (node)

with the biggest metric is taken as both the filtered value ˆ *x*(0 *|* 0) and predicted value ˆ *x*(0 *|* 0 *− * 1)

of the state *x*(0), given no observation.

*Recursive Step (Step k): * An approximate discrete disturbance noise vector *wd*( *k − * 1) with

*n * possible values of the disturbance noise *w*( *k − * 1) is offline obtained by Eq. (3). The

quantization levels of the state vector at time *k * are calculated by using the finite state model

of Eq. (6) with all the considered quantization levels (or nodes) *xq* 1( *k − * 1), *xq* 2( *k − * 1) ...

*xqN *( *k − * 1) at time *k − * 1; and all possible values *w*

*k−* 1

*d* 1( *k − * 1), *wd* 2( *k − * 1), ..., *wdn*( *k − * 1)

of the approximate discrete disturbance noise vector *wd*( *k − * 1) . That is, substituting the

12

Discrete Time Systems

*x *( *k* )

1

1

*q*

*x *( *k* )

1

*x*

( *k* )

1

*qi*

*qNk * 1

*x *( *k *)

*x *( *k *)

*x *( *k *)

*x*

( *k*)

*q* 1

*q * 3

*qj*

*qNk*

Fig. 2. Two Row Trellis Diagram of Admissible State Quantization Levels

considered state quantization levels *xqi*( *k − * 1) ( *i *= 1, 2, . . . , *Nk−* 1) for *xq*( *k − * 1) and the

possible values *wd*( *k − * 1) = *wdj*( *k − * 1) ( *j *= 1, 2, . . . , *n*) for *wd*( *k − * 1) in the finite state model of Eq. (6), the quantization levels of the state at time *k * are calculated (generated). The

admissible quantization levels at time *k*, which satisfy constraints imposed on state estimates,

are determined and non-admissible state quantization levels are discarded. If the number

of admissible state quantization levels at time *k * is zero, then a larger *n*, *MN * or smaller *GS*

is taken and *the recursive step at time k * of the DF is repeated from the beginning; otherwise,

the metrics of all admissible state quantization levels at time *k * are calculated by using Eq.

(14). If the number of admissible state quantization levels at time *k * is greater than *MN*, then

only *MN * admissible state quantization levels with biggest metrics, otherwise, all admissible

state quantization levels with their metrics are considered for the next step of the DF. The

considered admissible quantization levels (denoted by *xq* 1( *k*), *xq* 2( *k*), ..., *xqN *( *k*)) and their

*k*

metrics are used to calculate the state quantization levels and their metrics at time *k *+ 1. The

considered state quantization levels at time *k * are represented by the nodes on the second row

(or column) of two rows (or columns) trellis diagram at *the recursive step k * and on the first row

(or column) of two rows (or columns) trellis diagram at *the recursive step k *+ 1, Fig. 2; where

the subscript *Nk*, which is the number of considered nodes at the end of *Recursive step k*, is less

than or equal to *MN*; and the transition from a node at time *k − * 1, say *xqi*( *k − * 1), to a node at

time *k *, say *xqj*( *k*), is represented by a directed line which is called a branch. *Estimate at time*

*k: * the admissible quantization level (node) with the biggest metric at time *k * is taken as the

desired estimate of the state at time *k*, that is, the node with the biggest metric at time *k * is the

desired predicted value of *x*( *k*) if *z*( *k*) is neither available nor used for estimation; otherwise,

the node at time *k * with the biggest metric is the filtered value of *x*( *k*). If there exist more than