بازسازی ورودی دودویی برای سیستم های خطی: تجزیه و تحلیل عملکرد

Recovering the digital input of a time-discrete linear system from its (noisy) output is a significant challenge in the fields of data transmission, deconvolution, channel equalization, and inverse modeling. A variety of algorithms have been developed for this purpose in the last decades, addressed to different models and performance/complexity requirements. In this paper, we implement a straightforward algorithm to reconstruct the binary input of a one-dimensional linear system with known probabilistic properties. Although suboptimal, this algorithm presents two main advantages: it works online (given the current output measurement, it decodes the current input bit) and has very low complexity. Moreover, we can theoretically analyze its performance: using results on convergence of probability measures, Markov processes, and Iterated Random Functions we evaluate its long-time behavior in terms of mean square error.

Consider the input/output linear system equation(1) View the MathML source{xk=qxk−1+wuk−1k=1,…,Kyk=cxk+nk Turn MathJax on with K∈NK∈N (possibly tending to infinity), uk∈{0,1}uk∈{0,1} for k=0,…,K−1k=0,…,K−1, xk∈Rxk∈R for k=0,…,Kk=0,…,K, yk,nk∈Ryk,nk∈R for k=1,…,Kk=1,…,K, q,w,c∈Rq,w,c∈R, and q∈(0,1)q∈(0,1) to preserve stability. Our aim is to recover the binary input ukuk, in an online fashion, given the output ykyk corrupted by a noise nknk. To this purpose, we retrieve a low-complexity algorithm introduced in [1] and discussed in [2] and [3], and we propose a comprehensive theoretical analysis of its performance. As a result of the analysis, we will be able to evaluate the performance as a function of the system’s parameters. The digital signal reconstruction problem is a paradigm in data transmissions, where signals arising from finite alphabets are sent over noisy continuous channels, and in hybrid frameworks, where digital and analog signals have to be merged in the same system. In [1], a slightly different instance of model (1) was derived as time discretization of a convolution system and the input estimation described as a deconvolution problem. The same can be achieved for model (1): if we consider the system equation(2) View the MathML source{x′(t)=ax(t)+bu(t)t∈[0,T]y(t)=cx(t)+n(t)x(0)=x0u(t),x(t),y(t),a,b,c∈R,a<0 Turn MathJax on we have equation(3) View the MathML sourcex(t)=etax0+b∫0tea(t−s)u(s)ds. Turn MathJax on Given equation(4) View the MathML sourceu(t)=∑k=0K−1uk1[kτ,(k+1)τ[(t),uk∈U={0,1},τ>0 Turn MathJax on we can discretize in the following way: by defining View the MathML sourcexk≔x(kτ)for k=0,1,…,K=T/τ Turn MathJax on equation(5) q≔eτa∈(0,1)q≔eτa∈(0,1) Turn MathJax on View the MathML sourcew≔b1−eτa−a=−ba(1−q) Turn MathJax on we obtain equation(6) View the MathML sourcexk=qkx0+bqk∫0kτe−as∑h=0K−1uh1[hτ,(h+1)τ[(s)ds=qkx0+bqk∑h=0k−1uh∫hτ(h+1)τe−asds=qkx0+b−aqk∑h=0k−1uhe−a(h+1)τ(1−eaτ)=qkx0+w∑h=0k−1uhqk−1−h Turn MathJax on from which we have the recursive formula equation(7) xk=qxk−1+wuk−1.xk=qxk−1+wuk−1. Turn MathJax on In system (2), recovering u(t)u(t) basically consists in the inversion of the convolution integral View the MathML sourcey(t)=cetax0+cb∫0tea(t−s)u(s)ds+n(t) Turn MathJax on (where n(t)n(t) represents an additive noise), which is a long-standing mathematical ill-posed problem: small observation errors may produce defective solutions. Several estimation approaches have been studied in the last fifty years and the literature on deconvolution is widespread: we refer the reader to early papers [4] and [5] and to later ones [6], [7], [8] and [9], which also show some possible applications in geophysics, astronomy, image processing and biomedical systems. For more references, see [10]. Most of the known deconvolution methods exploit the regularity of the input function to provide good estimations. This work instead is a contribution for deconvolution in case of discontinuous input functions. Considering a binary alphabet, which has been chosen mainly to keep the analysis straightforward, is consistent with many applications: the output of several digital devices, such as computers and detection devices [2], are binary. Nevertheless, the algorithm and the analysis presented in this paper could be generalized to larger alphabets with not much effort. In [1], low-complexity decoding algorithms were introduced, derived from the optimal BCJR [11] algorithm, and applied to perform the deconvolution of the system (2) with a=0a=0 and b=c=1b=c=1. In this work, we apply the simplest of those algorithms, the so-called One State Algorithm (OSA for short) to the system (1). We then describe the performance in terms of Mean Square Error (MSE) for long-time transmissions, through a probabilistic analysis arising from the Markovian behavior of the algorithm. The scheme of the analysis is the same proposed in [1], but leads to completely different scenarios: while for a=0a=0 and b=c=1b=c=1 standard ergodic theorems for denumerable Markov Processes were sufficient to compute the MSE, in the present case the denumerable model does not proved the expected results, and more sophisticated arguments are used, arising from Markov Processes, Iterated Random Functions (IRF for short) and sequences of probability measures. The paper is organized as follows. In Section 2 we complete the description of the system, giving some observations and probabilistic assumptions; in Sections 3 and 4, we present our algorithm and some simulations. The core of the paper is the performance analysis provided in Section 5. Finally we propose some concluding observations. Notice that Sections 2 and 3 mainly retrieve the model presented in [1] and [2]. 1.1. Notation We use the following notation throughout the paper: View the MathML sourceP indicates a discrete probability, while P(⋅,⋅)P(⋅,⋅) is the transition probability kernel of a Markov Process; EE is the stochastic mean. B(S)B(S) indicates the Borel σσ-field of a space SS. Given a bounded measurable function vv defined on a space SS, Pv(x)=∫Sv(y)P(x,dy)Pv(x)=∫Sv(y)P(x,dy). For every measure μμ on (S,B(S))(S,B(S)) and F∈B(S)F∈B(S), μP(F)=∫DP(x,F)μ(dx)μP(F)=∫DP(x,F)μ(dx). The complementary error function erfcerfc is defined as View the MathML sourceerfc(x)=2π∫x+∞e−t2dt, x∈Rx∈R; the indicator function 1A(x)1A(x) is equal to one if x∈Ax∈A, and zero otherwise. Moreover we often use the following acronyms: OSA for One State Algorithm, MSE for Mean Square Error, IRF for Iterated Random Functions, and MAP for Maximum a Posteriori.

In this paper, we have proposed using the One State decoding algorithm to recover the binary input of a linear system and we have analyzed its behavior. When the system has particular contractive properties, the analysis is based on Iterated Random Functions, while in the non-contractive case known results from the convergence of probability measures can be exploited. The theoretical results allow us to predict the Mean Square Error of the One State Algorithm for long-time transmissions, given the parameters of the system and some prior probabilistic information. Simulations and theoretical results are consistent. The One State Algorithm could be extended to multi-dimensional problems and to the recovery of digital inputs arising from larger source alphabets and with different probabilistic distributions. Moreover, its use for problems with feedback, such as channel equalization, should be further studied.