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 xR mxR 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 xR mxR 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