 Research
 Open Access
 Published:
Optimal MSE solution for a decision feedback equalizer
EURASIP Journal on Advances in Signal Processing volume 2012, Article number: 172 (2012)
Abstract
Due to the inherent feedback in a decision feedback equalizer (DFE) the minimum mean square error (MMSE) or Wiener solution is not known exactly. The main difficulty in such analysis is due to the propagation of the decision errors, which occur because of the feedback. Thus in literature, these errors are neglected while designing and/or analyzing the DFEs. Then a closed form expression is obtained for Wiener solution and we refer this as ideal DFE (IDFE). DFE has also been designed using an iterative and computationally efficient alternative called least mean square (LMS) algorithm. However, again due to the feedback involved, the analysis of an LMSDFE is not known so far. In this paper we theoretically analyze a DFE taking into account the decision errors. We study its performance at steady state. We then study an LMSDFE and show the proximity of LMSDFE attractors to that of the optimal DFE Wiener filter (obtained after considering the decision errors) at high signal to noise ratios (SNR). Further, via simulations we demonstrate that, even at moderate SNRs, an LMSDFE is close to the MSE optimal DFE. Finally, we compare the LMS DFE attractors with IDFE via simulations. We show that an LMS equalizer outperforms the IDFE. In fact, the performance improvement is very significant even at high SNRs (up to 33%), where an IDFE is believed to be closer to the optimal one. Towards the end, we briefly discuss the tracking properties of the LMSDFE.
Introduction
A channel equalizer is an important component of a communication system and is used to mitigate the inter symbol interference (ISI) introduced by the channel. The equalizer depends upon the channel characteristics. A variety of equalizers have been proposed and utilized in communication systems [1–3] Usually simple linear equalizers (LE) would suffice (see for e.g., [1–3]) but for a channel with deep spectral nulls one would require a more complex, non LE like a decision feed back equalizer (DFE).
A LE is a linear filter that is used to mitigate ISI while a Wiener filter (WF) equalizer is an optimal filter that minimizes the mean square error (MSE) between the input symbols and the decoded symbols (decoded after the equalizer). Closed form expression for WF LE is available ([4, 5] etc). This closed form expression involves a matrix inverse which can be computationally intensive if the filter has a large dimension. Alternatively, least mean square linear equalizer (LMSLE), a computationally efficient iterative algorithm, is used extensively (see [4–6]) to obtain the WF equalizer. It can also track the time variations in the WF, if required, as in the case of Wireless channels. For a fixed channel its convergence to the WF has been studied in [6, 7] (see also the references therein). Its performance on a wireless (time varying) channel has been studied theoretically in [8, 9] (see also [4, 5, 10] and the references there in, where the performance has been studied via simulations, approximations and upper bounds on probability of error).
Decision feedback are nonlinear equalizers (a pair of linear filters one in the forward path and another in the feedback path), which can provide significantly better performance than LE [3, 11, 12], especially for ‘bad’ channels. A DFE feeds back the previous decisions of the transmitted symbols, to nullify the ISI due to them (which can now happen without amplifying the thermal noise) and makes a better decision about the current symbol. Although these equalizers have also been used for quite sometime, due to feedback their behavior is much more complex than that of the LEs. Hence their performance is not well understood. Existence of a hard decoder inside the feedback loop, due to its nonlinearity, makes the study all the more difficult. A DFE mainly exploits the finite alphabet structure of the hard decoder output [2, 13] and hence the hard decoder cannot be ignored (i.e., its performance is better than a system with a soft decoder).
Since the statistics of the previous decisions in a DFE are not known, there is no known technique available that provides an minimum MSE (MMSE) DFE (we will call it as DFEWF in the rest of the article) even for a fixed channel [2, 3, 14]. Thus an MMSE DFE is commonly designed by assuming perfect decisions (see, e.g., [2, 15]). For convenience, for the rest of the article, we will call such a DFE as ideal DFE (IDFE). In this article IDFE is also computed using perfect channel estimates. The IDFE often outperforms the Linear WF significantly [3, 11, 12]. But it is generally believed that DFEWF, the true MSE optimal DFE (designed considering the decision errors), can outperform even this.
Another way to obtain an optimal filter is to replace the feedback filter at the receiver by a precoder at the transmitter [3, 14]. This way one can indeed obtain the optimal filter but this requires the knowledge of the channel at the transmitter. For wireless channels, which are time varying, this is often not an attractive solution [2, 3].
Some research has been done to deal with the decision errors in a DFE. Sternad et al. [16] approximated the errors in decisions with an additive white Gaussian noise (AWGN) independent of the input sequence and obtained a DFE WF. But as is stated in the article this approximation is not realistic. Erdogan et al. [13] obtain an H^{∞} optimal DFE taking into account the decision errors. However no comparison to DFEWF was provided.
Ideal DFE also contains a matrix inverse for which LMS is again used as a computationally efficient alternative in practical communications systems. However, convergence of LMSDFE is not well understood even for a fixed channel, again due to the complexity introduced by the feedback. Trajectory of the LMSDFE algorithm, on a fixed channel, with a soft decoder in the feedback loop has been approximated by an ODE in [17]. But this ODE does not approximate the LMSDFE with a hard decoder. Beneveniste et al. [6] have shown the ODE approximation of an LMSDFE with a hard decoder. But the ODE obtained by them is not explicit enough. Furthermore, they do not relate the attractors of this ODE to the DFEWF.
Our conjuncture is that LMS can actually converge to the true DFE WF (obtained considering the decision errors) and one of the main goals of this article is to prove the same. In this article, we study an LMSDFE on a fixed channel using an ODE approximation. Towards this, we first obtain the stationary performance of the system with DFE and prove the existence of DFEWF (the minimum MSE solution) for every channel state (whenever the domain of optimization is compact). We then show that the DFEWF and an LMSDFE attractor are close to each other at high signal to noise ratios (SNRs). We show the same is true for nominal values of SNRs via simulations.
Further we demonstrate via simulations, that the LMSDFE can outperform the commonly used IDFE, at all practical SNRs. An interesting observation is that, the improvement is significant even at high SNRs where an IDFE does not suffer from error propagation and is believed to be close to the true DFEWF.
The article is organized as follows. Our system model, notations and assumptions are discussed in Section “The model and notation”. In Section “The issues and our approach” we discuss our approach. Section “Analysis of LMSDFE and DFEWF” obtains an ODE approximation and then the analysis of the attractors of LMSDFE. Section “Numerical examples” provides some examples. Section “Tracking analysis” briefs the tracking behavior while Section “Conclusions” concludes the article. The sections Appendices 1 to 5 provide proofs for our theorems.
The model and notation
We consider a communication system with a DFE (see Figure 1). Inputs {s_{ k }} enter a finite impulse response channel ${\left\{{z}_{l}\right\}}_{l=0}^{L1}$, and are corrupted by an additive zero mean white Gaussian noise {n_{ k }} with variance σ^{2}. The channel output, u_{ k }, at time k, is given by,
The channel output passes through a DFE given by a linear forward filter θ_{ f } and a linear feedback filter θ_{ b }. In addition, there is a hard decoder Q(.). The output of the decoder at time k is,
We provide below the assumptions made and the notations used in this article. Most of these assumptions can be generalized as discussed at the end of this section.

Sequences {s_{ k }}and {n_{ k }}are independent and identically distributed (i.i.d) sequences and are independent of each other. The inputs {s_{ k }}are uniformly distributed over { + 1,−1}(BPSK modulation).

${f}_{\mathcal{N}}\left(y\right)$ is the N dimensional standard i.i.d Gaussian density, where N is the dimension of the vector y, i.e., ${f}_{\mathcal{N}}\left(y\right)={\left(2\Pi \right)}^{N/2}\mathit{ex}{p}^{\frac{{\lefty\right}^{2}}{2}}$. Whenever not mentioned, integrability is with respect to ${f}_{\mathcal{N}}\left(y\right)\mathit{dy}$.

The equalizer forward, feedback filters are given by ${\left\{{\theta}_{{f}_{l}}\right\}}_{l=0}^{{N}_{f}1}$, ${\left\{{\theta}_{{b}_{l}}\right\}}_{l=1}^{{N}_{b}}$ respectively. Also, let ${N}_{L}\triangleq {N}_{f}+L1$.

We assume that the symbols are modulated using BPSK and so the hard decoder equals, Q(x):=1_{{x≥0}}−1_{{x<0}}in (1).

For any vector, x, x_{ l }represents its l^{th}component and ${x}_{l}^{k}$, l≤k, represents the vector [ x_{ k }x_{k−1} … x_{ l } ]^{T}.
The following vector notations are used:
$$\begin{array}{ll}{S}_{k}& \triangleq \phantom{\rule{2em}{0ex}}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}{s}_{k{N}_{L}+1}^{k},\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}{N}_{k}\triangleq \phantom{\rule{1em}{0ex}}{n}_{k{N}_{f}+1}^{k},\\ {U}_{k}& \triangleq \phantom{\rule{2em}{0ex}}\phantom{\rule{0.3em}{0ex}}{u}_{k{N}_{f}+1}^{k},\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}{\u015c}_{k}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{2.77695pt}{0ex}}\triangleq \phantom{\rule{1em}{0ex}}{\u015d}_{k{N}_{b}+1}^{k},\\ {X}_{k}& \triangleq \phantom{\rule{1em}{0ex}}\phantom{\rule{0.3em}{0ex}}{\left[\phantom{\rule{2.77695pt}{0ex}}{U}_{k}^{T}\phantom{\rule{2.77695pt}{0ex}}\phantom{\rule{2.77695pt}{0ex}}{\u015c}_{k1}^{T}\phantom{\rule{2.77695pt}{0ex}}\right]}^{T},\phantom{\rule{2em}{0ex}}\phantom{\rule{1em}{0ex}}\phantom{\rule{0.3em}{0ex}}{G}_{k}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{2.77695pt}{0ex}}\phantom{\rule{0.3em}{0ex}}\triangleq \phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}{\left[\phantom{\rule{2.77695pt}{0ex}}{S}_{k}^{T}\phantom{\rule{2.77695pt}{0ex}}\phantom{\rule{2.77695pt}{0ex}}{X}_{k}^{T}\phantom{\rule{2.77695pt}{0ex}}\right]}^{T},\\ {\theta}_{f}& \triangleq \phantom{\rule{2em}{0ex}}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}{{\theta}_{f}}_{0}^{{N}_{f}1},\phantom{\rule{2em}{0ex}}\phantom{\rule{2em}{0ex}}\phantom{\rule{0.3em}{0ex}}{\theta}_{b}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{2.77695pt}{0ex}}\triangleq \phantom{\rule{2em}{0ex}}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}{{\theta}_{b}}_{1}^{{N}_{b}},\\ {J}_{k}& \triangleq \phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}{\left[\phantom{\rule{2.77695pt}{0ex}}{S}_{k}^{T}\phantom{\rule{2.77695pt}{0ex}}\phantom{\rule{2.77695pt}{0ex}}{\u015c}_{k1}^{T}\phantom{\rule{2.77695pt}{0ex}}\phantom{\rule{2.77695pt}{0ex}}{N}_{k}^{T}\phantom{\rule{2.77695pt}{0ex}}\right]}^{T},\phantom{\rule{2em}{0ex}}\Theta \phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}\phantom{\rule{2.77695pt}{0ex}}\triangleq \phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}{\left[{{\theta}_{f}}^{T}\phantom{\rule{2.77695pt}{0ex}}\phantom{\rule{2.77695pt}{0ex}}{{\theta}_{b}}^{T}\right]}^{T},\\ Z& \triangleq \phantom{\rule{0.3em}{0ex}}\left[\phantom{\rule{2.77695pt}{0ex}}{z}_{0},\phantom{\rule{2.77695pt}{0ex}}\phantom{\rule{2.77695pt}{0ex}}{z}_{1}\phantom{\rule{2.77695pt}{0ex}}\dots \phantom{\rule{2.77695pt}{0ex}}{z}_{L1}\phantom{\rule{2.77695pt}{0ex}}\right].\end{array}$$In the above, S_{ k },U_{ k },N_{ k }and ${\u015c}_{k1}$, respectively represent the vector of input symbols, channel outputs, noise samples and the decoder decisions that influence the equalizer output at time k. Vector X_{ k } forms input to the equalizer at time k while G_{ k }, J_{ k } are the two alternate representations of the system state at time k. Vector Z is the vector form of the channel while θ_{ f }, θ_{ b } are that of the equalizer feedforward and feedback filters.

Θ_{ k }represent the time varying equalizer at time k.

Let $\mathcal{S}:=\{+1,1\}$. Under the above assumptions, {G_{ k }} and {J_{ k }} are Markov chains for a fixed channel, equalizer pair at (Z,Θ). These two Markov chains take values in ${\mathcal{S}}^{{N}_{L}}\times {\mathcal{S}}^{{N}_{b}}\times {\mathcal{R}}^{{N}_{f}}$, where $\mathcal{R}$ is the set of real numbers. The current and the previous states of both these Markov chain are represented by the ordered pairs (i,y), (j,y^{′}) respectively. Here i,j take values from the discrete part of the state part of the state space, ${\mathcal{S}}^{{N}_{L}}\times {\mathcal{S}}^{{N}_{b}}$, while y,y^{′} take values in ${\mathcal{R}}^{{N}_{f}}$.

Ψ={ψ_{ l }}l=0N_{ L }−1 represents the convolution of the channel {z_{ l }} and the forward filter θ_{ f }.

The input to the hard decoder for a given state of the Markov chain is represented by,
$${e}_{\Theta}(i,y):=\sum _{l=0}^{{N}_{L}1}{\psi}_{l}{s}_{kl}+\sum _{l=0}^{{N}_{f}}{{\theta}_{f}}_{l}{n}_{kl}+\sum _{l=1}^{{N}_{b}}{{\theta}_{b}}_{l}{\u015d}_{kl}.$$Note that ${\u015d}_{k1}=Q\left({e}_{\Theta}\right(j,{y}^{\prime}\left)\right)$.

B(Θ,δ), $\stackrel{\u0304}{B}(\Theta ,\delta )$ are the open and closed balls respectively with center Θ and radius δ.

The equalizer output without noise, e_{ Θ }(i,0)≠0for all values of i at the LMS attractor. Without this assumption the LMS algorithm makes more errors than the correct decisions.
Thus, the channel outputs {u_{ k }}pass through a DFE Θ with a hard decoder. The performance of this system will depend upon the DFE filters Θ. We are interested in a filter Θ that minimizes the commonly used criterion, the mean of the squared error between the input symbol s_{ k } and their corresponding decisions Θ^{t}X_{ k }(MSE):
The LMS algorithm,
a computationally efficient iterative algorithm, is expected to provide the MMSE solution. However, with a feedback structure inserted, the convergence behavior of LMS is not understood properly. In fact, it is not even clear if the minimum mean square problem is well posed neither is it clear if an MMSE solution exists. Even prior to these questions, one first needs to define the expectation in (2) appropriately. One is often interested in optimizing a stationary performance, i.e., expectation in (2) is with respect to the stationary distribution of the system. However the stationary distribution depends upon the parameter Θ. The existence of the stationary distribution for any given Θ is not known. We take up these issues one by one and our final goal is to show that the above iterative algorithm (3) indeed converges close to the MMSE solution.
One can easily extend the theory of this article to any finite alphabet (complex) input source with any arbitrary distribution and to a complex channel. However we stick to BPSK modulation and to a real channel to keep the explanations simple. Also, the theory to follow, considers an optimal equalizer for delay 0. The entire theory will go through for any arbitrary delay. Indeed in Section “Numerical examples”, an example with an optimal equalizer for delay 1, is presented. This is once again done to simplify the explanations.
The issues and our approach
A DFEWF on a fixed channel (if it exists) is given by,
where the expectation on the right hand side is defined under stationarity for a given Θ. Vector ${X}_{k}={\left[{U}_{k}^{T},\phantom{\rule{2.77695pt}{0ex}}{\u015c}_{k1}^{T}\right]}^{T}$, includes previous decisions ${\u015c}_{k1}$ and hence its stationary distribution depends upon the parameter Θ. Thus this is a complex case of optimization in which, the stationary distribution defining the average cost also depends upon the parameter to be optimized. There is no known technique to compute a WF, Θ^{∗} of (4), even for a fixed channel.
In practical systems, a DFE WF is commonly designed assuming perfect decisions (i.e., ${\u015c}_{k}={S}_{k{N}_{b}+1}^{k}$), which we have called IDFE. It is easy to see that the IDFE for a fixed channel is given by,
This computation may be expensive because of matrix inversion and LMS (3) is actually used as an alternative [4, 5]. Our claim is that in case of a DFE, apart from being computationally efficient the LMS algorithm also outperforms the IDFE, Θ_{IDFE}. This is because we will see briefly that the LMS attractors are close to DFEWF while IDFE is away from DFEWF. We achieve this goal by showing that the LMSDFE attractors are close to that of the DFEWF at high SNRs (later in Section “Numerical examples” we show that this covers the practically used SNRs). Further, LMS can also be used to track the channel variations. We first study an LMSDFE on a fixed channel and later on briefly discuss its tracking behavior.
Another issue related to (4) is that we should take the expectation in the right hand side under stationarity. However, it appears that the existence of stationary distribution of {X_{ k }} for a given Θ is not known. Thus, first, in Theorem 2, we show the existence of a unique stationary distribution (and stationary density w.r.t. ${f}_{\mathcal{N}}\left(y\right)\mathit{dy}$) for {X_{ k }} for any Θ.
As is usually done in adaptive algorithm analysis, we study the LMSDFE using an ODE approximating it. Using the stationary distribution of {X_{ k }} we convert the ODE in [6] to the following more tractable ODE,
The attractors of the LMSDFE will be the zeros of the RHS of the above ODE, while the DFEWF will be a zero of the gradient (if it exists) of the cost in the RHS of (4). Under certain conditions (with ∇representing the gradient),
where Π_{ Θ } is the stationary density of the Markov chain, {J_{ k }}, w.r.t. the Lebesgue measure, when the DFE Θ is used. One can expect the LMSDFE attractors to be close to the DFEWF, if the second term in the RHS of (6) is close to zero. However, we could not even get differentiability of Π_{ Θ }. Nevertheless, we achieve the required differentiability (Theorem 3) by considering a hard decoder that is a slightly perturbed version of the original hard decoder. We also show that the DFEWF and an LMSDFE attractor of this perturbed decoder converge to that of the original hard decoder as the level of perturbation tends to zero (Theorem 4). We then analyze this perturbed decoder and show that the LMSDFE attractors of this decoder are close to its DFEWFs at high SNR (Theorem 5). This suggests that at high SNR an LMS attractor for the original decoder is close to its DFEWF.
Analysis of LMSDFE and DFEWF
We provide a step by step analysis of LMSDFE and its connection to DFEWF in this section, while addressing the issues raised in Section “The issues and our approach” one after the other.
Previous ODE approximation result
We start with an ODE approximation for LMSDFE, which will be used in the subsequent sections for performance analysis. DFE with a hard decoder has been approximated by an ODE in [6]. We start our LMSDFE analysis with this ODE. We reproduce the ODE approximation result of [6] here in our notations. Towards this goal, as a first step, we write down the ODE approximating LMSDFE (3): let Θ(t,a) denote the solution of the ODE,
with initial condition Θ(0)=a, where ${P}_{\Theta}^{n}$ is the nstep transition function of the Markov chain J_{ k }with DFE Θ, and ${P}_{\Theta}^{n}{H}_{\Theta}(j,{y}^{\prime})$ is the expectation of the function H_{ Θ }(G) (defined in (3)) using the conditional measure P Θ n(.j,y^{′})(Note G_{ k } is a fixed function of J_{ k }). The limit in (7) will be independent of the initial condition (j,y^{′}) ([6], p. 252).
It is easy to see that the LMS algorithm satisfies all the required hypothesis of ([6], Theorem 13, p. 278) and hence one can approximate its trajectory on any finite time scale with the solution of the ODE (7), the precise result is:
Theorem 1
For any initial condition Θ_{0}, finite time T, with $t\left(r\right):=\sum _{k=0}^{r}{\mu}_{k}$,
whenever μ_{ k }≤1 for all k and if $lim\underset{k}{inf}\frac{{\mu}_{k+r}}{k}>0$for every integer r. ▀
Stationary distribution and a simplified ODE
We will show below that the RHS of the ODE (7) is same as that of the ODE (5) and hence equate the ODE (7) with a more tractable ODE (5). As a first step, we prove that the Markov chain {J_{ k }} has a stationary distribution for any given DFE, channel pair (Z,Θ). In the following, at many places we do not include channel value Z for notation, as this article mainly works with fixed channel behavior. However the proofs are applicable for any pair (Z,Θ) and the notation includes Z, when required to be specific.
Theorem 2
The following results hold:

(i)
For every fixed (Z,Θ), Markov chain {J _{ k }}has a unique stationary distribution π _{Z,Θ}.

(ii)
Starting from any initial condition (i,y), the nstep transition measure (${P}_{\Theta}^{n}\left(.\righti,y)$) of the Markov chain converges geometrically to the stationary distribution, Π _{ Θ }, in total variation norm.

(iii)
The continuous part of the stationary distribution has a density, Π _{ Θ }that is continuous with respect to (Z,Θ)in L _{1}norm.

(iv)
The MSE under stationarity is continuous in (Z,Θ).
Proof: Please see Appendix 1. ▀
For each Θ, {J_{ k }} is a Markov chain taking values in ${\mathcal{S}}^{{N}_{L}}\times {\mathcal{S}}^{{N}_{b}}\times {\mathcal{R}}^{{N}_{f}}$. Its transition function
where $\stackrel{\u0304}{\delta}(y,{y}^{\prime})$ equals 1 when the vector formed from all but the last component of the vector y^{′}equals the vector formed from all but the first component of the vector y and otherwise zero and $\stackrel{~}{\delta}(i,j)=\stackrel{\u0304}{\delta}\left({i}_{1}^{{N}_{L}},{j}_{1}^{{N}_{L}}\right)\stackrel{\u0304}{\delta}\left({i}_{{N}_{L}+1}^{{N}_{b}+{N}_{L}},{j}_{{N}_{L}+1}^{{N}_{b}+{N}_{L}}\right)$ (note that the first component, ${i}_{1}^{{N}_{L}}$, represents the sample value of S_{ k }, while the second one, ${i}_{{N}_{L}+1}^{{N}_{b}+{N}_{L}}$, represents the sample value of ${\u015c}_{k1}$). The only component of the transition function (8) that depends upon Θ is ${P}_{\Theta}({i}_{{N}_{L}+1}=1j,{y}^{\prime})={1}_{\left\{{e}_{\Theta}(j,{y}^{\prime})>0\right\}}$.
By i.i.d nature of the input s_{ k }and noise n_{ k } one can choose n_{0}large enough such that the continuous part of the n step transition function ${P}_{\Theta}^{n}(i,y\in Bj,{y}^{\prime})$ is absolutely continuous with respect to ${f}_{\mathcal{N}}\left(y\right)\mathit{dy}$ for all n≥n_{0}. Further, n_{0} is chosen larger than N_{ L } to ensure ensure s_{ k }, ${S}_{k{n}_{0}}$ are independent. Fix one such n. The corresponding density (Radon–Nikodym derivative)
where
From (9) it is easy to see that the density of the nstep transition function ${p}_{\Theta}^{n}(i,yj,{y}^{\prime})\le 1$, for all values of i,y, j,y^{′} and n≥n_{0}. Also, we have by Theorem 2.ii, $\left{p}_{\Theta}^{n}\left(.\rightj,{y}^{\prime}){\Pi}_{\Theta}\right\to 0$ for every value of j,y^{′}as n→∞ in L_{1} norm. Further, the function H_{ Θ }() (given in (3)) can be bounded uniformly by, H_{ Θ }(G_{ k })≤C_{1}X_{ k }^{2} + C_{2}X_{ k } for all Θ in a small neighborhood, for some appropriate constants C_{1}, C_{2}. The above bound is square integrable and depends only on {J_{ k }}. Hence Lemma 1 of Appendix 5 is applicable and we have,
Thus ODE (7) simplifies to ODE (5).
By Theorem 2, MSE is a continuous function of Θ and so by confining our search in (4) to a compact region, we obtain the existence of the WF, DFEWF. Next we consider the LMS attractors which are now the attractors of ODE (5). The ODE attractors will be zeros of the RHS of (5), while the DFEWF will be a zero of the gradient (if it exists) of the MSE (the cost in the RHS of (4)). As discussed in Section “The issues and our approach”, these two can be related as in (6) and for comparison of the two zeros, one needs to study, ∇_{ Θ }Π_{ Θ }, the gradient of the stationary density. That is, to get the connection between an LMSDFE attractor and the DFEWF one needs to consider the differentiability of the stationary density.
Differentiability of the stationary density
One can see from Equation (9) that it is difficult to comment on differentiability of the nstep transition density itself. Thus, it is even more difficult to discuss the differentiability of the stationary density. To proceed further with the analysis, we perturb the hard decoder Q such that the nstep transition density and the stationary density become differentiable. Next we show that the LMS attractors and the DFEWF of this perturbed decoder converge to that of the original decoder as the level of perturbation tends to zero. Finally we study the DFE using these perturbed decoders in Section “LMS attractors versus WF at high SNRs”.
We alter the decoder function Q(x)(of Equation (1)) to,
where ε_{0} is a small constant. Also, in (10) when x≤ε_{0}, ${Q}_{{\epsilon}_{0}}\left(x\right)$ will be taken as −1 when it is not 1. Observe that the perturbed decoder is also a hard decoder. With the perturbed decoder ${Q}_{{\epsilon}_{0}}\left(x\right)$, the Θ dependent component of the transition function is,
The partial derivative, $\frac{\partial {P}_{\Theta}^{\left({\epsilon}_{0}\right)}({i}_{{N}_{L}+1}=1j,{y}^{\prime})}{\mathrm{\partial \Theta}}$ exists everywhere and equals,
By the uniform upper bound on the derivative (11) and by the bounded convergence theorem one can see that the nstep transition density (9) (with n≥n_{0}) becomes differentiable (details are in Appendix 2, Lemma 2) and equals (using the notations of Equation (9)),
For these perturbed decoders, we show that the stationary density (with respect to ${f}_{\mathcal{N}}\left(y\right)\mathit{dy}$) also becomes differentiable. Furthermore, using an Implicit function theorem, we get a bound on the norm of this gradient.
Theorem 3
For every ε_{0}>0, for every Θ_{0}, the Markov chain {J_{ k }} has a unique stationary distribution, ${\Pi}_{\Theta}^{\left({\epsilon}_{0}\right)}$. It’s continuous part has a density, ${\Pi}_{\Theta}^{\left({\epsilon}_{0}\right)}$, that is continuously differentiable with respect to Θ in L_{2} norm. Further, for every δ>0 and ${\sigma}_{0}^{2}>0$ there exists a constant C<∞ such that for all Θ∈B(Θ_{0},δ), ${\sigma}^{2}\le {\sigma}_{0}^{2}$,
Proof: The proof is provided in Appendix 2. ▀
We conclude this section by showing that the DFEWFs and the LMSDFE attractors of the perturbed decoder converge to that of the original decoder. In the following, let ${\Theta}_{n}^{\ast}$ and ${\Theta}_{n}^{\text{LMS}}$ denote the DFEWF and an LMSDFE attractor (whose existence at high SNRs with small ε_{0} is established at the end of Appendix 4 and hence is assumed in the proof of the following theorem) for perturbation ${{\epsilon}_{0}}_{n}$.
Theorem 4
For any σ^{2}, for any sequence ${{\epsilon}_{0}}_{n}\to 0$, there exists a subsequence ${{\epsilon}_{0}}_{\mathit{\text{nk}}}\to 0$, a DFEWF Θ^{∗} of the original decoder and an LMSDFE attractor Θ^{LMS} of the original decoder, such that,
Proof: Please see Appendix 3. ▀
Thus we can always take the perturbation ε_{0}in (10) small enough such that the LMS attractors and the DFEWFs for the perturbed decoder are close enough to the corresponding equalizers for the original decoder. Henceforth, we analyze these perturbed decoders to draw important conclusions.
LMS attractors versus WF at high SNRs
In this section we would like to understand the connection between an LMS attractor and a DFEWF for a perturbed decoder. Since the former is a zero of the RHS of Equation (5) and the later is the zero of the gradient of the MSE (the cost in the RHS of (4)), we study the connection between the two.
Fix an ε_{0}>0. With the error defined by, err_{ Θ }(J_{ k }):=(s_{ k }−e_{ Θ }(J_{ k }))(note that i defined in the notations in Section “The model and notation” represents, $({S}_{k},{\u015c}_{k1})$, the discrete part of the Markov chain, {J_{ k }}),
Here equality a follows by the existence of the stationary density ${\Pi}_{\Theta}^{\left({\epsilon}_{0}\right)}$ with respect to the Gaussian measure ${f}_{\mathcal{N}}\left(y\right)\mathit{dy}$. Equality b is given by Lemma 2 of Appendix 5. The above equality above equality (14) is true for any ε_{0}>0 and for any σ^{2}. We will show below that the DFEWF will be close to the limiting LMSDFE if the second term on the right hand side of (14) is small.
We have assumed that ${S}_{k}^{t}\Psi +{\theta}_{b}^{t}{\u015c}_{k1}\ne 0$ at an LMS attractor. By continuity, ${S}_{k}^{t}\Psi +{\theta}_{b}^{t}{\u015c}_{k1}\ne 0$ for all Θ in a small neighborhood of the LMS attractor. We can further choose an ε_{1} small enough such that
for all $({S}_{k},{\u015c}_{k1})$ and for all Θ in a small neighborhood of an LMS attractor. Choose ε_{0}≤ε_{1}. By Chebyshev’s inequality, if 0∉[c−ε_{0},c + ε_{0}](for some c) and if n is a Gaussian random variable with mean zero and variance σ^{2}, then
Thus, from the upper bound (13) of Theorem 3, for any fixed ε_{0}≤ε_{1},
Thus by Cauchy Schwartz inequality as σ^{2}→0(note err_{ Θ }has all moments),
Next we show the following: (15) implies the LMSDFE attractors will be close to the DFEWFs. In general two functions f_{1}, f_{2}can be close to each other at every point, but their zeros may be far apart, i.e., if x_{1} is a zero of f_{1} then f_{2}(x_{1}) can be close to zero but the zero of f_{2}closest to x_{1}may still be far away. It is useful to rule out this possibility in our scenario. We show this using the following theorem. Define,
Theorem 5
There exists an ε_{2}with 0<ε_{2}≤ε_{1} such that for any ε_{0}≤ε_{2}, there exists a continuous function $q:B(0,\delta )\subset \mathcal{R}\times \mathcal{R}\mapsto {\mathcal{R}}^{{N}_{f}}$, with
Proof: Please see Appendix 4. ▀
Using the above theorem, we obtain the proximity of LMS attractors and the WFs in the following.
For any fixed ε_{0}≤ε_{2}, $\left{\nabla}_{\Theta}{\Pi}_{\Theta}^{\left({\epsilon}_{0}\right)}\right$ near an LMS attractor, tends to zero as σ^{2}→0. Thus by (15), there exists a small enough ${\sigma}_{0}^{2}$ such that for all ${\sigma}^{2}\le {\sigma}_{0}^{2}$,
Note that q(σ^{2},0) is a zero of s(Θ,σ^{2}) (note w(q(σ^{2},0),σ^{2},0)=s(Θ,σ)) and hence is an LMS attractor at σ^{2}. Similarly from (14), q(σ^{2},η_{ w })is a zero of the gradient of MSE cost and hence is a DFEWF. Thus, for all ${\sigma}^{2}\le {\sigma}_{0}^{2}$, the LMS attractors, q(σ^{2},0), by continuity arguments of Theorem 5 will be close to that of the WFs, q(σ^{2},η_{ w }).
It is clear from the above Theorem that at high SNRs, for very small ε_{0}(close to the practical decoder), the LMS attractor is close to the DFEWF. Since, IDFE Θ_{IDFE}, is designed with an improper assumption (like perfect decisions), there is a good chance of these filters to be inefficient in comparison to the LMS attractors. We will see this in the examples provided in Section “Numerical examples”.
We conclude this section by pointing out another useful consequence of the Theorem 5. This theorem also establishes the existence of the LMS attractors at high SNRs for perturbed decoders with perturbation level ε_{0} small. A Remark at the end of Appendix 4 establishes this point.
One of the uses of the above ODE approximation is that, one can approximately obtain the performance (e.g., Bit error rate, MSE) of LMSDFE at any time by using the trajectory of this ODE. Of course, obtaining bit error rate (BER) theoretically is still a problem because the BER of a system with a fixed known channel and a fixed DFE is still not available. But our ODE approximation is still useful because one can obtain the performance (transient as well as stationary) of the LMSDFE with only one simulation, which would not be possible otherwise. This is because by Theorem 1, the ODE solution approximates the LMSDFE trajectory in probability.
Numerical examples
In this section we reinforce the theory developed so far using some examples. We take a few examples of channels obtained from previous studies and show the proximity of the DFEWF and the LMS attractor for practical values of SNRs. We also show that in many cases, the IDFE performs much worse than the DFEWF but an LMS attractor performs close to the DFEWF. BER and the MSE are used to compare the various equalizers. For every sample of the channel, we have used MonteCarlo simulations to estimate the corresponding BER and MSE using one million samples of data.
DFEWF, Θ^{∗}, for every sample of the channel is obtained by running a gradient descent type of algorithm on the cost function (4) itself, where the gradient was approximated at each point by finite difference approximation, [E_{Θ + Δ}(X(Θ + Δ)^{t}(Θ + Δ)−s]^{2}−E_{ Θ }(X(Θ)^{t}(Θ)−s)^{2}) /Δ. Here the expectation E_{ Θ }(X(Θ)^{t}(Θ)−s)^{2} is estimated by the sample path averages,
using a large number of samples, N. Vector sequence ${\left\{{X}_{i}\left(\Theta \right)\right\}}_{i=1}^{N}$ is obtained by running the DFE with fixed coefficients Θ(and on a channel that is fixed at its current sample). Thus Θ^{∗} is estimated as the limit of the steepest descent algorithm:
Here s_{k,i} are i.i.d with the distribution of the inputs, s_{ k }. Sequences {Δ_{ k }}and {μ_{ k }}are chosen appropriately to reduce to zero. In our simulations we used ${\mu}_{k}=\frac{0.07}{{k}^{0.6}}$, Δ_{ k }=5μ_{ k } and N=4×10^{5}.
Least mean square attractors are obtained as the time limit of the LMS algorithm (3), with similar settings as with DFEWF estimation.
We consider two examples in Tables 1 and 2. In Table 1, we have used an interesting example (significant part of the raised cosine channel of ([1], p. 199)) to show that the LMS attractors are close to the WFs at practical SNRs. Its coefficients are provided in the table. We also provide BER in this table. We further show the euclidean distance between the equalizer and the corresponding DFEWF in first subcolumns. One can see that the distance between the LMSDFE and DFEWF is small while that between the IDFE and DFEWF is large. One can also see an improvement up to 18% in BER in LMSDFE in comparison to the IDFE. In fact this improvement is more at high SNRs (where the IDFE is assumed to have lesser problem because of error propagation). Further, the BER of the DFEWF is close to that of the LMS attractor.
We have developed the theory for an equalizer with delay zero. One can easily extend these results to the equalizer with any arbitrary delay. In fact, the channel in Table2is one such example. Here the equalizer with delay 1 will be the best one. The channel of Table 2 is very widely used (see [1], p. 165 and [4], p. 414). We can see once again a huge improvement (up to 30%) in BER for the LMSDFE with respect to Θ_{IDFE}. We also see that the LMS attractors are close to the DFEWF, Θ^{∗}for all practical SNRs.
In this section, we are comparing directly the time limits of LMS algorithm (3) with that of the true DFEWF iteration mentioned at the beginning of this section. These two limits are further compared with IDFE, closed form expression. That the LMS trajectory approximates the solution of the ODE (5) is established theoretically (Theorem 1) in this article. In [9, 18] etc., we have demonstrated the same even via numerical simulations, for time varying channels. In Figures two, three and four of [9], it is shown numerically that the LMS trajectory approximates the appropriate ODE solution when the underlying channel is a time varying AR (2) process.
Tracking analysis
LMS being an iterative algorithm can track the channel variations if the update coefficients μ_{ k }, in (3), converge to a non zero value. In [9, 18], we study the tracking behavior of an LMSDFE, while it is operating on a wireless channel characterized by an AR(2) process. We demonstrate that an LMSDFE can also track the time varying DFEWF, whose variations result from the variations in a wireless channel. We also show that LMSDFE can outperform the IDFE, on a time varying channel.
Conclusions
Obtaining MSE optimal filter for DFE is a longstanding problem. Precoding provides one practical solution but may not be feasible with wireless channels. The difficulty in the design and or analysis is because, the analysis of the past decisions (with feedback) is not known so far. To circumvent this, one commonly uses the optimal WF obtained assuming perfect past decisions. LMS, a computationally efficient alternative, is an iterative algorithm designed to converge to the WF. However, once again because of the feedback involved, complete analysis of an LMSDFE is not available.
We show via ODE analysis, that LMS itself can provide/track the optimal WF. This article concentrates on fixed channel behavior and proves that the attractors of the LMS are close to that of the optimal DFE at high SNRs. Proofs become nontrivial partly because of the nondifferentiability of the hard decoder. We circumvent this problem, by studying another hard decoder which is a slightly perturbed version of the original one. We first show that the LMS attractors and the DFEWFs of the perturbed decoder converge to that of the original decoder and then show that the two themselves are close to each other at high SNRs. Next, we show by examples that the SNRs need not be very high, i.e., in fact practically used SNRs (upto 1.5 dB) can be sufficient. We also show that the BER (probability of error) of the commonly used WF, designed assuming perfect past decisions (also using perfect channel estimates), can be up to 33% higher than the optimal WF even at high SNRs (where the former is believed to be closer to the later).
In [18], we show that the LMSDFE converges and then moves close to the instantaneous DFEWF after the initial transience, while it is tracking a DFEWF of a wireless channel modeled by an AR(2) process. We also show in [18] that the performance measures BER and MSE of the LMSDFE are close to that of the DFEWF after the transient period, while that of an IDFE are substantially inferior to that of the DFEWF and the LMSDFE.
Thus we conclude: (1) in case of a DFE, an LMS algorithm (originally designed for computational efficiency) converges and/or tracks a filter close to the Wiener solution; (2) the closed form expression for DFE WF (obtained after approximating the decision errors to zero) is far away from the Wiener solution and its performance can be significantly inferior.
Appendices
Appendix 1
Proof of Theorem 2: Using the results of [19], we prove the existence and continuity of the stationary distribution of the Markov chain, {J_{ k }}. For any (Z_{0},Θ_{0}) and for any ε>0, ε_{0}>0,
Continuity of the map considered in (16) and compactness of the closed balls $\stackrel{\u0304}{B}({\Theta}_{0},\epsilon )$, $\stackrel{\u0304}{B}({Z}_{0},{\epsilon}_{0})$ ensures M_{1}<∞.
The map (Θ,N_{ k })↦θ_{ f }^{t}N_{ k } is continuous and hence the inverse image of the open set {x>−M_{1}}under this map is open. Thus it is possible to get a open set C and a δ≤ε such that,
Thus whenever $\Theta \in \stackrel{\u0304}{B}({\Theta}_{0},\epsilon )$ and $Z\in \stackrel{\u0304}{B}({Z}_{0},{\epsilon}_{0})$, the decoder (1) outputs 1 (irrespective of the inputs/past decisions) when the noise vector is in C. Hence,
where sets ${C}_{1}\in {\mathcal{R}}^{{N}_{b}}$, ${C}_{2}\in {\mathcal{R}}^{{N}_{f}}$ are selected such that their respective Lebesgue measures are not equal to zero and ∩l=k−N_{ b }−1k{N_{ l }∈C}⊃C_{1}×C_{2}.
Define $\mathcal{G}:=\left[\phantom{\rule{2.77695pt}{0ex}}1\phantom{\rule{2.77695pt}{0ex}}\phantom{\rule{0.3em}{0ex}}.\phantom{\rule{2.77695pt}{0ex}}.\phantom{\rule{0.3em}{0ex}}\phantom{\rule{2.77695pt}{0ex}}1\phantom{\rule{2.77695pt}{0ex}}\right]\times \left[\phantom{\rule{2.77695pt}{0ex}}1\phantom{\rule{0.3em}{0ex}}\phantom{\rule{2.77695pt}{0ex}}.\phantom{\rule{2.77695pt}{0ex}}.\phantom{\rule{0.3em}{0ex}}\phantom{\rule{2.77695pt}{0ex}}1\phantom{\rule{2.77695pt}{0ex}}\right]\times {\mathcal{R}}^{{N}_{f}}$. For any n_{0}>max{N_{ b } + N_{ f } + 1,N_{ L }}, for any initial condition ${J}_{k{n}_{0}}$, for any measurable set B_{ N }, and for any $\Theta \in \stackrel{\u0304}{B}({\Theta}_{0},\delta )$, $Z\in \stackrel{\u0304}{B}({Z}_{0},{\epsilon}_{0})$
where α:=P(S_{ k }=[ 1 .. 1 ])P(N k−N_{ b } + N_{ f }k−N_{ f }∈C_{1}). Thus for any $\Theta \in \stackrel{\u0304}{B}({\Theta}_{0},\delta )$, $Z\in \stackrel{\u0304}{B}({Z}_{0},{\epsilon}_{0})$ and for any initial condition ${J}_{k{n}_{0}}$, the n_{0}step conditional measure is majorized:
where the measure ${\nu}_{{n}_{0}}\left(\right)$ is defined by, ${\nu}_{{n}_{0}}\left(\right[\phantom{\rule{2.77695pt}{0ex}}1\phantom{\rule{2.77695pt}{0ex}}\phantom{\rule{0.3em}{0ex}}.\phantom{\rule{2.77695pt}{0ex}}.\phantom{\rule{0.3em}{0ex}}\phantom{\rule{2.77695pt}{0ex}}1\phantom{\rule{2.77695pt}{0ex}}]\times [\phantom{\rule{2.77695pt}{0ex}}1\phantom{\rule{0.3em}{0ex}}\phantom{\rule{2.77695pt}{0ex}}.\phantom{\rule{2.77695pt}{0ex}}.\phantom{\rule{2.77695pt}{0ex}}\phantom{\rule{0.3em}{0ex}}1\phantom{\rule{2.77695pt}{0ex}}]\times {B}_{E}):=\mathrm{\alpha P}({N}_{k}\in {B}_{E}\cap {C}_{2})$. Thus the entire state space ${\mathcal{S}}^{{N}_{L}}\times {\mathcal{S}}^{{N}_{b}}\times {\mathcal{R}}^{{N}_{f}}$ is ${\nu}_{{n}_{0}}$small (hence also a petite set) for all the Markov chains {J_{ k }}, parameterized by $\Theta \in \stackrel{\u0304}{B}({\Theta}_{0},\delta )$ and $Z\in \stackrel{\u0304}{B}({Z}_{0},{\epsilon}_{0})$. Then using ([19], Proposition 9.1.7, p. 206 and Theorem 10.01, p. 230) one obtains the existence and uniqueness of the stationary distribution, π_{Z,Θ}for each Z,Θ.
Define $\rho =1{\nu}_{{n}_{0}}\left(\mathcal{G}\right)$. Then, by ([19], Theorem 16.2.4 in page 392), for all $\Theta \in \stackrel{\u0304}{B}({\Theta}_{0},\delta )$, $Z\in \stackrel{\u0304}{B}({Z}_{0},{\epsilon}_{0})$ and for all initial conditions (j,y^{′}) we get:
where . represents the total variation norm. This along with the continuity of the transition function, establishes the continuity of the stationary distribution π_{Z,Θ} under total variation norm at (Z_{0},Θ_{0}). This is because, for any $\Theta \in \stackrel{\u0304}{B}({\Theta}_{0},\delta )$ and $Z\in \stackrel{\u0304}{B}({Z}_{0},{\epsilon}_{0})$
for all n≥1, where the last equality follows by continuity of the transition function with respect to (Z,Θ). By letting n→∞
The stationary distribution, π_{Z,Θ}, has discrete and continuous components. The continuous component of π_{Z,Θ}, is absolutely continuous with respect to the measure ${f}_{\mathcal{N}}\left(y\right)\mathit{dy}$ for every (Z,Θ). Hence the stationary density, π_{Z,Θ}for {J_{ k }}exists. Continuity in total variation norm of the stationary distribution implies the continuity of the stationary densities in L_{1}norm ([20], Theorem 8.2, p. 110). It is also easy to see that the stationary density Π_{Z,Θ}(i,y)≤1 for all (i,y).
Now by fixing the channel at some value Z, MSE, the cost in RHS of Equation (4), can be rewritten as, ${E}_{\Theta}{\left[{\Theta}^{t}Xs\right]}^{2}=\sum _{S,\u015c}{E}_{{f}_{\mathcal{N}}}\left[{\left({\Theta}^{t}Xs\right)}^{2}{\Pi}_{\Theta}\right]$. Lemma 1 in Appendix 5, now gives the continuity of the MSE with respect to Θ for any fixed Z.
One can show the same conclusions for the Markov chain, {G_{ k }}, as G_{ k }=Γ(J_{ k }) for some fixed oneone, onto C^{∞} function Γ, whenever the channel and equalizer values are fixed. ▀
Appendix 2
Proof of Theorem 3: The existence and continuity of the stationary density ${\Pi}_{\Theta}^{\left({\epsilon}_{0}\right)}$ for every ε_{0}is achieved in a similar way as in the proof of the Theorem 2. The only difference being, ε_{0} must be added to −M_{1} in the definition of the set (17). We leave superscript ε_{0}to simplify the notations in the rest of this proof.
We use Implicit function theorem to prove differentiability. For that, we will consider the Banach spaces:

$X={\mathcal{R}}^{{N}_{f}+{N}_{b}}$ with Euclidean norm.

$Y=\{g:{\mathcal{S}}^{{N}_{L}+{N}_{b}}\times X\to \mathcal{R};\leftg\right<\infty \}$ with L_{2} norm, ., defined by,
$$\leftg\right:=\frac{1}{\left\mathcal{S}\right}\sum _{i}{\left({\int}_{y}{\leftg(i,y)\right}^{2}{f}_{\mathcal{N}}\left(y\right)\mathit{dy}\right)}^{1/2},$$where $\left\mathcal{S}\right$ represents the cardinality of set ${\mathcal{S}}^{{N}_{L}+{N}_{b}}$.
Fix n_{0}>max{N_{ f } + N_{ b },N_{ L }}. We consider the following continuous map f:X×Y↦Y,
where,
Observe that (Θ,Π_{ Θ }) is a zero of f.
By Lemmas 1 and 2 the function f is differentiable with respect to Π and Θ, respectively and further the derivative $\frac{\mathrm{\partial f}}{\mathrm{\partial \Pi}}$ is a homeomorphism. Also, $\left{\left(\frac{\mathrm{\partial f}}{\mathrm{\partial \Pi}}\right)}^{1}\right$ and $\left\frac{\mathrm{\partial f}}{\mathrm{\partial \Theta}}\right$ are upper bounded locally by the RHS of (18) and (24) respectively.
Using similar logic one can easily show that both the partial derivatives of f are continuous in (Θ,Π). Hence by Implicit function theorem on Banach spaces, ([21], Theorem 3.1.10 and Corollary 3.1.11, p. 115), the map Θ↦Π_{ Θ }is continuously differentiable and the derivative is given by,
Upper bound 13 is obtained by bounding the above gradient using the upper bounds (18) and (24). ▀
Lemma 1.
f is differentiable with respect to Π and the derivative is a homeomorphism. Also for any $\delta >0,{\sigma}_{0}^{2}>0$ there exists a constant C_{0}<∞ such that,
for all Θ∈B(Θ_{0},δ), ${\sigma}^{2}\le {\sigma}_{0}^{2}$.
Proof: The function f is affine linear in the second variable Π∈Y. Thus,
We will show below that this map is oneone through contradiction. It is easy to see that g(Θ,Π)−Π is in the set,
Operator, Γ that maps $\Pi \mapsto \left(\sum _{j}{\int}_{{y}^{\prime}}{\Pi}_{(}j,{y}^{\prime}\left){f}_{\mathcal{N}}\right({y}^{\prime})d{y}^{\prime}\right)$, i.e.,
has onedimensional range which lies inside ${\mathcal{H}}^{c}$. We can show that the partial derivative (19) is oneone, if we show that there is no common nonzero vector in the null space of both the operators. Say there exists a vector Π≠0 in the null space of both the operators. Let,
As Π is in the null space of the operator, Γ,
Hence Π_{1}=2α. Also, because g(Θ,Π)=Π,
Then,
This provides a contradiction as $0<{\nu}_{{n}_{0}}\left(Y\right)<1$ and hence Π_{1}=g(Θ,Π)_{1}<Π_{1}. This proves that the partial derivative (19) is oneone. The inequality is obtained by using the majorizing measure, ${\nu}_{{n}_{0}}\left(.\right)$, defined in the proof of continuity of stationary distribution.
The map g(Θ,Π)is compact integral operator ([22], Example 2, p. 277). The last map of the partial derivative has onedimensional range and hence is compact. Therefore, the partial derivative equals T−I, where T is a compact operator. Then by Riesz–Schauder Theory ([22], Theorem 1, p. 283), the fact that $\frac{\mathrm{\partial f}}{\mathrm{\partial \Pi}}$ is oneone implies that it is onto and also further that the inverse is bounded. Hence $\frac{\mathrm{\partial f}}{\mathrm{\partial \Pi}}$ is a linear homeomorphism.
Furthermore, the mapping $({\sigma}^{2},\Theta )\mapsto \left{\left[{\left(\right)close="">\frac{\mathrm{\partial f}}{\mathrm{\partial \Pi}}}_{}(\Theta ,{\Pi}_{\Theta})\right]}^{}1\right$ is continuous. This continuity follows by the joint continuity of the n_{0}step transition function, ${p}_{\Theta}^{{n}_{0}}(i,yj,{y}^{\prime})$ with respect to (σ^{2},Θ) and then by bounded convergence theorem (as ${p}_{\Theta}^{{n}_{0}}(i,yj,{y}^{\prime})+1$ is uniformly bounded) and finally by the continuity of the map x↦x^{−1} ([23], p. 135). Hence the lemma follows for some C_{0}<∞, $\delta >0,{\sigma}_{0}^{2}>0$. ▀
Lemma 2.
f is differentiable with respect to Θ. The partial derivative ${\left(\right)close="">\frac{\mathrm{\partial f}}{\mathrm{\partial \Theta}}}_{}(\Theta ,{\Pi}_{\Theta})$ is upper bounded by bound (24).
Proof: We reintroduce the notations that will be used here (notation of Equation (9)).

$i=\left[{S}_{k+{n}_{0}({N}_{f}+L2)}^{k+{n}_{0}},{\u015c}_{k+{n}_{0}1({N}_{b}1)}^{k+{n}_{0}1}\right]$, $y={N}_{k+{n}_{0}({N}_{f}1)}^{k+{n}_{0}}$, represent the current state of the Markov Chain, at k + n_{0}.

$j=\left[{S}_{k({N}_{f}+L2)}^{k},{\u015c}_{k({N}_{b}1)}^{k1}\right],{y}^{\prime}={N}_{k({N}_{f}1)}^{k}$ represent the initial condition for n_{0}−step transition function, which transition function, which is the state of the Markov chain at k.

$l=\left[{S}_{k+1}^{k+{n}_{0}({N}_{f}+L3)},{\u015c}_{k}^{k+{n}_{0}1({N}_{b}2)}\right]$, v=N k + 1k + n_{0}−(N_{ f }−2)represent the intermediate input, decision and noise vectors.

$x\left(q\right):=\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}\left[{S}_{k+{n}_{0}q({N}_{f}+L1)}^{k+{n}_{0}q},\phantom{\rule{2.77695pt}{0ex}}{\u015c}_{k+{n}_{0}q{N}_{b}}^{k+{n}_{0}q1},\phantom{\rule{2.77695pt}{0ex}}{N}_{k+{n}_{0}q{N}_{f}}^{k+{n}_{0}q}\right]$ represent the intermediate state of the Markov chain at k + n_{0}−q.
To begin with, we will show component wise differentiability of the function f, i.e., differentiability of f(Θ,Π)(i,y) for every (i,y). We will show the differentiability of the n_{0}−step transition function, ${p}_{\Theta}^{{n}_{0}}\left(i,yj,{y}^{\prime}\right)$ along with that. Positive and finite constants (like c, c^{′′}etc) are introduced in the derivations as and when required. While obtaining upper bounds we have taken advantage of the finite alphabet nature of the set $\mathcal{S}$. By simple computations, one can see that the density with respect to the Gaussian measure is,
Hence,
The only component of the above functions, depending upon Θ is ${P}_{\Theta}\left({\u015d}_{k+{n}_{0}q}\rightj,{y}^{\prime})$. By (11),
uniformly in (i,y), for every Θ, (j,y^{′}) and for every q. Thus for any Θ_{ h } in a small neighborhood of 0 and for any i,y, j,y^{′}, Θ and q (by mean value ([24], Theorem X.4.5, p.312)),
For obtaining the above upper bound, the mean value theorem is used as explained below for a two dimensional function, which can easily be generalized to any ndimensional function. Say f is any function of two variables. One can write, f(a + h,b + k)−f(a,b) as sum of terms f(a + h,b + k)−f(a + h,b)−f(a,b + k) + f(a,b), f(a + h,b)−f(a,b) and f(a,b + k)−f(a,b). The first term is bounded by mean value theorem for two variables, ([23], Theorem 9.40, p.235), while the remaining two terms can be bounded using mean value theorem for one variable, ([23], Theorem 5.10, p.108).
Finally by dominated convergence theorem, we will obtain the existence of the following partial derivatives, in the paragraphs that follow:
For obtaining the partial derivative (23), we will need to study the following set of functions one for each different value of i,j,l,r
One can easily see from (21) that the function inside each of the above integral is dominated by some constant multiple of the integrable function,
and that the above bound is is integrable by Cauchy Schwartz inequality. So by dominated convergence theorem, the limit $\underset{\left{\Theta}_{h}\right\to 0}{lim}$ (which arises while defining the partial derivate) can be taken inside the integral for every i,j,l,r and this establishes the existence of component wise partial derivative, ${\left(\right)close="">\frac{\mathrm{\partial f}}{\mathrm{\partial \Theta}}}_{}\Theta ,\Pi $. Also, this component wise partial derivative, is uniformly upper bounded by,
where the constant c^{′′}depends on Π.
One can now prove the existence of the overall partial derivative $\frac{\mathrm{\partial f}}{\mathrm{\partial \Theta}}$ at every (Θ,Π)using the above upper bound and the dominated convergence theorem (in L_{2} norm). Consider the limit,
The first equality follows because the function inside the integral tends to zero at every point and is upper bounded by the following integrable function,
We will now upper bound this partial derivative for all (Θ,Π_{ Θ }). First observe that, because Π_{ Θ }(i,y)≤1for all (i,y), from (11),
for some appropriate constants c_{1},c_{2},c_{3}. Then using ${\left(\sum _{k=1}^{n}{a}_{k}\right)}^{2}\le n\sum _{k=1}^{n}{a}_{k}^{2}$, x^{2}≤x (when x≤1), we get,
where the constants b_{ l }take values ${S}_{k}^{t}\Psi +{\theta}_{b}^{t}{\u015c}_{k1}$. ▀
Appendix 3
Proof of Theorem 4: Let ${f}_{1}(\Theta ,{\epsilon}_{0}):={E}_{{J}_{k}\left(\Theta \right)}^{\left({\epsilon}_{0}\right)}\left[{\text{err}}_{\Theta}{\left({J}_{k}\right)}^{2}\right],$ and ${f}_{2}(\Theta ,{\epsilon}_{0}):=\left{E}_{{J}_{k}\left(\Theta \right)}^{\left({\epsilon}_{0}\right)}{\nabla}_{\Theta}\left[{\text{err}}_{\Theta}{\left({J}_{k}\right)}^{2}\right]\right.$ Note that for any fixed ε_{0}, LMS attractors will be the zeros, i.e., minima of f_{2}(.,ε_{0}) while the DFEWFs are the minima of the MSE cost, f_{1}(.,ε_{0}).Also note that ε_{0}=0corresponds to the original decoder.
Let $\left\{{{\epsilon}_{0}}_{n}\right\}$ be any sequence converging to 0. Let $\Omega =\left\{{{\epsilon}_{0}}_{n}\right\}$. Take a compact set C large enough such that the WF is inside it (as Θ is increased to infinity, eventually MSE will start increasing and will tend to infinity). One can follow steps as in Theorem 2 and show that the stationary density ${\Pi}_{{\Theta}_{n}}^{{{\epsilon}_{0}}_{n}}$ converges to ${\Pi}_{\Theta}^{0}$ as $({{\epsilon}_{0}}_{n},{\Theta}_{n})\to (0,\Theta )$. Similarly, one can also show that both functions f_{1},f_{2}are jointly continuous in (Θ,ε_{0})∈C×Ω.
The domain of the parameter Θ for every ε_{0}, say D(ε_{0}), is the same compact set C and hence the correspondence ε_{0}↦D(ε_{0})is compact and continuous [25]. Then by the maximum theorem ([25], p. 235), ${{D}_{1}}_{n}^{\ast}:=\text{arg}\phantom{\rule{0.3em}{0ex}}{\text{min}}_{\Theta \in C}{f}_{1}(\Theta ,{{\epsilon}_{0}}_{n})$ and ${{D}_{2}}_{n}^{\ast}:=\text{arg}\phantom{\rule{0.3em}{0ex}}{\text{min}}_{\Theta \in C}{f}_{2}(\Theta ,{{\epsilon}_{0}}_{}$