Elsevier

Signal Processing

Volume 92, Issue 8, August 2012, Pages 1875-1885
Signal Processing

ISI sparse channel estimation based on SL0 and its application in ML sequence-by-sequence equalization

https://doi.org/10.1016/j.sigpro.2011.09.035Get rights and content

Abstract

In this paper, which is an extended version of our work at LVA/ICA 2010 [1], the problem of Inter Symbol Interface (ISI) Sparse channel estimation and equalization will be investigated. We firstly propose an adaptive method based on the idea of Least Mean Square (LMS) algorithm and the concept of smoothed l0 (SL0) norm presented in [2] for estimation of sparse ISI channels. Afterwards, a new non-adaptive fast channel estimation method based on SL0 sparse signal representation is proposed. ISI channel estimation will have a direct effect on the performance of the ISI equalizer at the receiver. So, in this paper we investigate this effect in the case of optimal Maximum Likelihood Sequence-by-Sequence Equalizer (MLSE) [3]. In order to implement this equalizer, we first introduce an equivalent F-model for sparse channels, and then using this model we propose a new method called pre-filtered parallel Viterbi algorithm (or pre-filtered PVA) for general ISI sparse channels which has much less complexity than ordinary Viterbi Algorithm (VA) and also with no considerable loss of optimality, which we have examined by doing some experiments in Matlab/Simulink. Indeed, simulation results clearly show that the proposed concatenated estimation–equalization methods have much better performance than the usual equalization methods such as Linear Mean Square Equalization (LMSE) for ISI sparse channels, while preserving simplicity at the receiver.

Introduction

In the framework of digital communication over band-limited channels, there are special scenarios in which one can model the overall channel as a Finite Impulse Response (FIR) sparse filter which will produce interferences with previous samples, i.e. Inter Symbol Interference (ISI). By the constraint of sparsity, we mean that only a few taps of the overall ISI channel are non-zero. As a result, the vectorized model of the mentioned FIR Channel Impulse Response (CIR) could be considered as a sparse vector. Such channels may be encountered, for example, in wireless multipath fading channels, acoustic underwater channels or even in simplified models of ultra wideband communications [4]. Other applications of sparse channels, such as modelling the overall underground channel for propagation of seismic waves (which appears in the problem of finding the location of oil wells), have also been reported in the literature of geological signal processing [5]. In most of these scenarios, the communication between transmitter and receiver should be as fast and reliable as it can be. Among the major factors that affect the speed and reliability of the overall data communication, one can mention the performance and convergence speed of channel estimation and equalization [3]. In the process of channel estimation, usually the transmitter sends a known-to-receiver training data, and the receiver estimates the CIR using the received observations. This estimated channel will then be used by other elements of the communication systems such as channel equalizer or detectors at the receiver side [3]. In the process of the channel equalization, the receiver tries to compromise the effect of produced ISI, so that the overall detection error of the communication system will be decreased. Accordingly, having a high accurate and fast channel estimator, as well as a high performance equalizer is at the point of interest in the literature of communications through band-limited channels [3].

Considering the problem of estimating the sparse channel, many efforts have been done to design batch estimation algorithms [4], [6], [7]. Most of these algorithms try to exploit the sparsity of the channel or detecting the locations of non-zero taps of the CIR. In addition, adaptive algorithms for sparse channel estimation are also proposed which are based on iterative estimation of the taps of a sparse channel [8], or even adapting the well-known methods of sparse recovery, such as CoSaMP [9], to the problem of sparse channel estimation [10]. On the other side, many efforts have been done to design high-performance equalizers for sparse channels [11], [12]. Among all of the choices for the structure of the equalizer, one may try to use the optimum equalizer in the sense of Mean Square Error (MSE). This equalizer is Maximum Likelihood Sequence-by-Sequence Equalizer (MLSE) which is implemented using Viterbi algorithm [3]. For the case of sparse channels, a simplified structure known as parallel Viterbi algorithm (PVA) has been proposed by McGinty et al. [13], which exploits the sparsity of the channel for decreasing the computation complexity of the MLSE equalizer. Although using PVA reduces the computational complexity of the receiver, it just works for a special type of sparse channels, known as zero-pad channel, in which non-zero taps are equally spaced [13].

In this work, which is an extended version of our work presented at LVA/ICA 2010 [1], we investigate these two problems of channel estimation and equalization in the case of ISI sparse channels with a novel approach. According to our best knowledge, all of the works around the problem of channel estimation and equalization have considered the ISI channel as an “FIR causal filter” with no constraint on the taps. The first contribution of our work is to solve these two problems under the assumption of using a matched filter structure at the receiver, which is a well-known receiver structure when communicating data through a band-limited channel (ISI channel) [3], [4]. In this situation, the resulting sparse FIR channel can be assumed to be minimum phase [3] (the reason of this assumption is described in Section 2, in which we have shown that by sampling the output of the channel and using a whitening discrete-time filter the end, we may model the whole CIR as a minimum-phase FIR filter). This assumption can make our equalization problem much easier to solve. More accurately, as will be shown in Section 3 of this work, it will help us to adapt PVA using a pre-filter at the receiver in order to implement MLSE with much less complexity. All in all, using this assumption we develop our algorithms in order to find the solutions to both the estimation and equalization problems. Finally, we experimentally examine the efficiency of the proposed algorithms in a concatenation of estimation and equalization stages.

This paper is divided into three main parts. In the first part of this paper, motivated by the smoothed l0-norm (SL0) algorithm [2] which is known as a fast sparse representation technique, we propose two new approaches for sparse channel estimation problem. Firstly, by modifying LMS algorithm introduced by Widrow and Hoff [14], we propose a new adaptive algorithm for channel estimation, called SL0-LMS. This algorithm is similar to the algorithms proposed in [8] (which are named as Zero-Attracting LMS (ZA-LMS) and Re-Weighted Zero-Attracting LMS (RZA-LMS) in [8]): it just differs by the regularization term and the possibility of varying this regularization term and the weight of this term adaptively. We mathematically show that by exploiting the sparsity information and using the concept of smoothed l0-norm we can improve the estimation performance in the sense of MSE, comparing to standard LMS method. We also provide a local convergence analysis of our proposed algorithm. We show that by choosing some parameters of our algorithm wisely at each iteration, we can guarantee both stability and performance of our algorithm. Furthermore, we will experimentally investigate the effect of adding a smoothed l0 norm penalty term to the cost function on the learning curve of LMS, and will investigate the improved tracking behaviour and steady state error of our proposed algorithm. Accordingly, we will experimentally show that it has better steady state and tracking behaviour in comparison to ZA-LMS and RZA-LMS. The second proposed algorithm is a non-adaptive algorithm which uses SL0 in a direct manner to estimate channel coefficients by finding the sparsest solution1 of an under-determined system of linear equations [2]. Although this algorithm is non-adaptive, it uses the speed of SL0 while preserving enough accuracy for the equalization stage. It is important to mention that none of the proposed algorithms in this part depend on the assumption of modelling the channel as a minimum phase filter and can be used if we do not use the matched filter structure at the receiver.

In the next part, high-performance equalization based on the MLSE (also known as the Viterbi equalization [3]) will be described. In conventional ISI sparse channels, implementation of the MLSE using the ordinary Viterbi algorithm is almost impossible (because the computational complexity of the receiver grows exponentially with the channel memory [3]). However, as mentioned earlier, in some special cases known as zero-pad ISI channels the parallel Viterbi algorithm is used instead of the ordinary Viterbi algorithm [15], [13]. In PVA a number of trellises are used after symbol deinterlacing and placing symbols into different groups. In fact, symbols that produce ISI on each other will be placed in the same group and Viterbi equalization will be performed separately on each group. The performance of this structure is the same as of a conventional Viterbi equalizer (as this structure is just an implementation of the Viterbi equalizer), while having much lesser complexity. In the case of general ISI sparse channels, according to our best knowledge, no such solution is yet presented in the literature. So, we propose a new method for using PVA in general ISI sparse channels based on the modelling of the ISI channel with a minimum-phase FIR filter. Our idea is based on the usage of a pre-filter at the receiver. In fact, this filter will re-shape the channel structure to a zero-pad channel which is presented in [15] and so, applying the PVA method will be possible afterwards. Although this method is not optimal, as we will see in experimental results, we do not have considerable amount of loss in optimality in most practical cases.

In the last part, computer simulations with Matlab/Simulink will be used to obtain the performance of our proposed algorithms. The results of these mentioned simulations will verify the performance of the presented algorithms on the both estimation of the channel and equalization of the produced ISI. It is important to note that the overall performance of the receiver system (as a concatenation of channel estimation and ISI equalization) depends on both of these parts which will be evaluated in these simulations and is considered as the overall measure of efficiency of the proposed algorithms for both estimation and equalization tasks.2

Section snippets

ISI sparse channel estimation

In this section, we would like to estimate the ISI sparse channel coefficients while transmitting digital bits through this channel using Binary Phase Shift Keying (BPSK) modulation [3].3 We assume that the BPSK modulator maps the incoming digital bits to the symbols {±1}. Accordingly, assuming a signaling

Pre-filtered PVA equalization in general ISI sparse channels

After estimating channel coefficients using one of the methods of the previous section, high-performance equalization in general ISI sparse channels will be investigated in this section. One of the properties of such channels is that they have a large amount of memory while having a few number of significant coefficients. Hence, implementation of the optimum ISI equalizer (MLSE) using Viterbi algorithm is almost impossible for these channels (because computational complexity of the receiver

Experimental results

In this section, we first compare the performance of channel estimators mentioned in Section 2.1 which are the SL0-LMS (Eq. (15)), ZA-LMS (Eq. (10)), RZA-LMS (Eq. (12)) and the standard LMS. In the first experiment, the input signal is an equiprobable random vector of ±1 with length 5000 and the additive noise is white Gaussian random sequence of length 5000 and variance 103. The channel has 256 taps where only 28 of them (randomly selected) are non-zero. The value of each non-zero tap is also

Conclusion

In this paper, we extended our work presented at LVA/ICA 2010 by providing further theoretical details and simulations. First, we proposed two sparse channel estimators, one adaptive and one non-adaptive, based on the concept of smoothed l0 norm. Our adaptive SL0-LMS algorithm exploits the sparse structure of the channel by adding a regularization term (the smoothed l0 norm of the channel) to the LMS cost function. Then we provided a mathematical analysis for showing the local convergence of

References (22)

  • D. Needell et al.

    CoSaMP: iterative signal recovery from incomplete and inaccurate samples

    Applied and Computational Harmonic Analysis

    (2009)
  • R. Niazadeh et al.

    Adaptive and non-adaptive ISI sparse channel estimation based on SL0 and its application in ML sequence-by-sequence equalization

  • H. Mohimani et al.

    A fast approach for overcomplete sparse decomposition based on smoothed l0-norm

    IEEE Transactions on Signal Processing

    (2009)
  • J. Proakis

    Digital Communication

    (2001)
  • S.V.C. Carbonelli et al.

    Sparse channel estimation with zero tap detection

    IEEE Transactions on Communications

    (2007)
  • N. Chapman et al.

    Deconvolution of marine seismic data using the l1 norm

    Geophysical Journal of the Royal Astronomical Society

    (1983)
  • S. Cotter et al.

    Sparse channel estimation via matching pursuit with application to equalization

    IEEE Transactions on Communications

    (2002)
  • S.V.W. Li et al.

    Estimation of rapidly time-varying sparse channels

    IEEE Journal of Oceanic Engineering

    (2007)
  • Y. Chen et al.

    Sparse LMS for system identification

  • N. Kalouptsidis et al.

    Adaptive algorithms for sparse non-linear channel estimation

    Relation

    (2010)
  • M. Kocic et al.

    Sparse equalization for real-time digital underwater acoustic communications

  • Cited by (0)

    This work has been partially funded by Iran Telecom Research Center (ITRC) and Iran National Science Foundation (INSF). Part of this work was done when the second author was in sabbatical at the University of Minnesota.

    View full text