Jump to content United States-English
HP.com Home Products and Services Support and Drivers Solutions How to Buy
» Contact HP

hp.com home

Technical Reports

printable version

HP Labs

» Research
» News and events
» Technical reports
» About HP Labs
» Careers @ HP Labs
» People
» Worldwide sites
» Downloads
Content starts here

Click here for full text: PDF

On the Optimality of Symbol by Symbol Filtering and Denoising

Ordentlich, Erik; Weissman, Tsachy


Keyword(s): filtering; denoising; smoothing; state estimation; hidden Markov models; entropy rate; large deviations

Abstract: Please Note. This abstract contains mathematical formulae which cannot be represented here. We consider the problem of optimally recovering a finite-alphabet discrete-time stochastic process {X1} from its noise-corrupted observation process {Zt}. In general, the optimal estimate of Xt will depend on all the components of {Zt} on which it can be based. We characterize non-trivial situations (i.e., beyond the case where (Xt, Zt) are independent) for which optimum performance is attained using "symbol by symbol'' operations (a.k.a. "singlet decoding''), meaning that the optimum estimate of Xt depends solely on Zt. For the case where {Xt} is a stationary binary Markov process corrupted by a memoryless channel, we characterize the necessary and sufficient condition for optimality of symbol by symbol operations, both for the filtering problem (where the estimate of Xt is allowed to depend only on and the denoising problem (where the estimate of Xt is allowed dependence on the entire noisy process). It is then illustrated how our approach, which consists of characterizing the support of the conditional distribution of the noise- free symbol given the observations, can be used for characterizing the entropy rate of the binary Markov process corrupted by the BSC in various asymptotic regimes. For general noise-free processes (not necessarily Markov), general noise processes (not necessarily memoryless) and general index sets (random fields) we obtain an easily verifiable sufficient condition for the optimality of symbol by symbol operations and illustrate its use in a few special cases. For example, for binary processes corrupted by a BSC, we establish, under mild conditions, the existence of a d > 0 such that the "say-what- you-see'' scheme is optimal provided the channel crossover probability is less than d. Finally, we show how for the case of a memoryless channel the large deviations (LD) performance of a symbol by symbol filter is easy to obtain, thus characterizing the LD behavior of the optimal schemes when these are singlet decoders (and constituting the only known cases where such explicit characterization is available). Notes:

36 Pages

Back to Index

»Technical Reports

» 2009
» 2008
» 2007
» 2006
» 2005
» 2004
» 2003
» 2002
» 2001
» 2000
» 1990 - 1999

Heritage Technical Reports

» Compaq & DEC Technical Reports
» Tandem Technical Reports
Privacy statement Using this site means you accept its terms Feedback to HP Labs
© 2009 Hewlett-Packard Development Company, L.P.