5706

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 58, NO. 11, NOVEMBER 2010

Low Complexity Equalization for Doubly Selective Channels Modeled by a Basis Expansion

Tomasz Hrycak, Saptarshi Das, Gerald Matz, Senior Member, IEEE, and Hans G. Feichtinger

Abstract—We propose a novel equalization method for doubly selective wireless channels, whose taps are represented by an arbitrary Basis Expansion Model (BEM). We view such a channel in the time domain as a sum of product-convolution operators created from the basis functions and the BEM coef?cients. Equivalently, a frequency-domain channel can be represented as a sum of convolution-products. The product-convolution representation provides a low-complexity, memory ef?cient way to apply the channel matrix to a vector. We compute a regularized solution of a linear system involving the channel matrix by means of the GMRES and the LSQR algorithms, which utilize the product-convolution structure without ever explicitly creating the channel matrix. Our method applies to all cyclic-pre?x transmissions. In subcarriers, each iteration of an OFDM transmission with GMRES or LSQR requires only ( log ) ?ops and ( ) memory. Additionally, we further accelerate convergence of both GMRES and LSQR by using the single-tap equalizer as a preconditioner. We validate our method with numerical simulations of a WiMAX-like system (IEEE 802.16e) in channels with signi?cant delay and Doppler spreads. The proposed equalizer achieves BERs comparable to those of MMSE equalization, and noticeably outperforms low-complexity equalizers using an approximation by a banded matrix in the frequency domain. With preconditioning, the lowest BERs are obtained within 3–16 iterations. Our approach does not use any statistical information about the wireless channel. Index Terms—Basis expansion model, doubly selective channels, equalization, OFDM, time-varying channels.

I. INTRODUCTION A. Motivation and Previous Work

I

N the last two decades, there has been a steady increase in the number of applications operating in rapidly varying wireless communication channels. Such channels occur due to user mobility in systems like DVB-T and WiMAX, which have been originally designed for ?xed receivers. Rapidly varying channels lead to signi?cant intercarrier interference (ICI) in multicarrier communication systems, which must be mitigated by an appropriate equalization method. Moreover, several

Manuscript received December 22, 2009; accepted July 14, 2010. Date of publication August 05, 2010; date of current version October 13, 2010. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Geert Leus. This work was supported by the WWTF project MOHAWI (MA 44), the Initiativkolleg Time-Frequency Analysis and Microlocal Analysis of University of Vienna, the Marie Curie Excellence Grant MEXT-CT-2004-517154, FWF Grant S10606, and University of Vienna Computer Science priority program NAHA. T. Hrycak, S. Das, and H. G. Feichtinger are with the Faculty of Mathematics, University of Vienna, 1090 Vienna, Austria (e-mail: saptarshi.das@univie.ac. at). G. Matz is with Institut für Nachrichtentechnik und Hochfrequenztechnik, Vienna University of Technology, 1040 Vienna, Austria. Digital Object Identi?er 10.1109/TSP.2010.2063426

applications have short symbol durations, and therefore require fast equalization algorithms. One such application is Mobile WiMAX (IEEE 802.16e) with a symbol duration of 102.9 s. At present, the most accurate approximations of doubly selective wireless channels with large delay and Doppler spreads are obtained via the basis expansion model (BEM). Consequently, we assume in this paper that the channel is represented in terms of a basis expansion model (BEM), which approximates the channel taps by linear combinations of prescribed basis functions; see [1]–[4]. Choosing an appropriate basis is crucial for accuracy, especially at high Doppler spreads. For example, discrete prolate sequences (DPS) provide a superb approximation, while complex exponentials (CE) give a poor approximation for several reasons; see, e.g., [5]. There also exist methods using differential encoding, which avoid an intermediate estimation step; see [6] and [7]. In the framework of the BEM, channel estimation amounts to an approximate computation of coef?cients for the basis functions. There exist several methods for estimating the BEM coef?cients of doubly selective channel taps, especially with an orthogonal frequency-division multiplexing (OFDM) transmission setup; see [2]–[4] and [8]. Usually, the channel matrix is reconstructed from estimated BEM coef?cients and subsequently used in equalization; see, e.g., [9]. For frequency-selective channels, the conventional single-tap equalization in the frequency domain is a method of choice. However, in the presence of severe ICI, single-tap equalization is unreliable; see [10]–[12]. Several other approaches have been proposed to mitigate ICI in transmissions over rapidly varying channels. For example, [13] describes minimum mean-square error (MMSE) and successive interference cancellation equalizers, which use all subcarriers simultaneously. A similar equalizer is presented in [14]. However, with OFDM subcarriers, it has the complexity of , and storage requirements of the same order of magnitude. Alternatively, only a few selected subcarriers are used in equalization, which amounts to approximating the frequency-domain channel matrix by a banded matrix. This approach has been exploited for design of low-complexity equalizers; see [9] and [15]–[19]. It is well known that approximation with a channel matrix banded in the frequency domain is equivalent to using a BEM with complex exponentials (CE-BEM); see Theorem 1. However, the CE-BEM [17] provides a poor approximation to the channel matrix [5], [20], so this approach leads to a signi?cant loss of information about the channel. A related approach is adopted in [9], where the channel matrix is ?rst estimated using the DPS-BEM, and then re-estimated

1053-587X/$26.00 ? 2010 IEEE

HRYCAK et al.: LOW COMPLEXITY EQUALIZATION FOR DOUBLY SELECTIVE CHANNELS MODELED BY A BASIS EXPANSION

5707

by a matrix banded in the frequency domain, which amounts to a transition to the CE-BEM. However, the DPS-BEM is more accurate than the CE-BEM [5], [20], so during the re-estimation some information about the channel is lost. A time-domain equalizer based on the LSQR algorithm is introduced in [21]. The methods presented in [22]–[24] require a channel matrix vector multiplication at some point in the process of equalization. In upcoming broadband wireless communication systems with signi?cant delay spreads, the number of discrete multipaths is proportional to the bandwidth. For example, in OFDM systems as used with Mobile WiMAX (IEEE 802.16e), a typical , where is the number of the discrete multipaths number of subcarriers. Thus, for such a system, a matrix-vector operamultiplication with the channel matrix requires . As tions, while our method has a complexity of noticed by the authors of [22], their low-complexity method is currently limited to a CE-BEM. Our proposed approach can be used in the settings discussed in the three papers referenced above, and gives rise to low-complexity equalization with arbitrary bases. B. Contributions We introduce a product-convolution (PC) decomposition of a doubly selective time-domain channel matrix as an entirely novel approach to basis expansion models. Equivalently, we view a frequency-domain channel matrix as a sum of convolution-product operators. Either of these decompositions leads to a fast matrix-vector multiplication with the channel matrix. Subsequently, we develop the ?rst low-complexity equalization method that can be used with an arbitrary basis expansion model (BEM). Our method is a signi?cant improvement over its nearest competitor—fast equalization of a channel matrix banded in the frequency domain. Our algorithm only uses estimated BEM coef?cients and the receive signal. We represent the time-domain channel matrix as a sum of product-convolution operators without ever constructing the channel matrix itself. The product operators are diagonal matrices with the basis functions as diagonals. The corresponding BEM coef?cients are used as ?lters in the convolution operators. This particular structure of the channel matrix permits a fast application of the matrix and its conjugate transpose. Therefore, the PC representation combined with classical iterative methods like GMRES [25] and LSQR [26], gives rise to a low-complexity equalizer. Additionally, we further accelerate convergence of both GMRES and LSQR by preconditioning them with the single-tap equalizer. The proposed equalizer has low complexity, and can be used with an arbitrary basis. We demonstrate in Section V, that the product-convolution representation using a well-chosen basis leads to signi?cant improvements in the BER after equalization. Our main contributions can be summarized as follows. ? We introduce a product-convolution decomposition of a doubly selective wireless channel matrix represented via a basis expansion model. ? We introduce a class of low-complexity equalization methods based on the product-convolution representa-

tion. We use standard iterative methods, like GMRES and LSQR, for equalization without reconstructing the channel matrix. In an OFDM system with subcarriers, each iteration requires ?ops and memory, and achieves BERs comparable with those of MMSE equalization. ? We propose the single-tap equalizer as an ef?cient preconditioner for both GMRES and LSQR. Since the number of discrete multipaths is proportional to the bandwidth, broadband transmissions suffer from a large number of multipaths. For example, Mobile WiMAX (IEEE 802.16e) subcarriers typically exhibits a discrete path delay of with ; see [27]. In such regimes, reducing the comhas plexity and memory requirements by a factor close to signi?cant practical bene?ts. Moreover, for such transmissions an explicit reconstruction of the channel matrix requires memory and ?ops, which is prohibitive in several practical applications. Both GMRES [25] and LSQR [26] are well-known iterative methods for the numerical solution of a system of linear equations; see Appendix A for detailed descriptions. LSQR has excellent regularization properties, and achieves BERs comparable to those of MMSE equalization; see [21], [28], and Section V. Our equalization method applies to any communication systems as long as: — the wireless channel is estimated using a basis expansion model; — the transmission uses a cyclic pre?x (CP). The method applies to, for example, cyclic-pre?x based orthogonal frequency-division multiplexing (CP-OFDM) and single-carrier frequency-division multiplexing (SC-FDM) with a cyclic-pre?x. Our method is quite practical, and may be readily implemented in hardware. In this paper, we describe basic, deterministic versions of the algorithms. Further modi?cations using statistical information, a turbo loop (see, e.g., [9]) or decision feedback can be combined with the proposed product-convolution decomposition. For the sake of clarity of presentation, we describe the methods in their simplest form, without relying on any speci?c probabilistic assumptions. We emphasize that we do not use any approximation of the channel matrix by a matrix banded in the frequency domain. We validate our method with numerical simulations of a WiMAX-like system in channels with severe Doppler shifts. However, our method applies to any cyclic-pre?x communication systems, as long as the wireless channel is modeled by a basis expansion. The proposed equalizer noticeably outperforms current low-complexity equalizers, which are based on an approximation by a banded matrix in the frequency domain. The paper is organized as follows. In Section II, we introduce our transmission setup and an assumed model for the wireless channel. The proposed iterative equalization methods and preconditioners are described in Section III. A detailed description of the algorithm is provided in Section IV. We present our simulation results in Section V, and conclusions in Section VI.

5708

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 58, NO. 11, NOVEMBER 2010

II. SYSTEM MODEL A. Transmission Model Our equalization method applies to any wireless transmission scheme with a cyclic pre?x (CP). For example, our method applies to CP-OFDM and SC-FDM with a cyclic pre?x. In this paper, we focus on CP-OFDM systems operating in doubly selective channels. We consider an equivalent baseband represubcarsentation of a single-antenna OFDM system with riers, although our method can be adapted to a MIMO setup in a straightforward manner. We assume a sampling period of , where denotes the transmit bandwidth. A cyclic is used in every OFDM symbol. We choose pre?x of length so large, that exceeds the channel’s maximum delay, so that we avoid intersymbol interference (ISI). Consequently, throughout this paper we deal with one OFDM symbol at a time, and all further models and formulations refer to one OFDM symbol. Each subcarrier is used to transmit a symbol from a ?nite symbol constellation (e.g., 4-QAM, PSK, 64-QAM). Depending on the transmission setup, some of these symbols may serve as pilots for channel estimation. The OFDM modulator uses the inverse discrete Fourier transform (IDFT) to map the frequency-domain transmit symbols into the time-domain transmit signal (1) . After discarding the cyclic pre?x at the receiver, the receive signal equals (2) Here, denotes complex additive noise of variance is the complex channel tap associated with delay , and is the channel length (maximum discrete-time delay). Consequently, . For simplicity, the channel’s maximum delay equals . In order to we make the worst-case assumption that simplify notation, throughout this paper we consider the signals to be periodically extended with period . Therefore, (2) represents the cyclic convolution of length . We do not use any acyclic convolutions in this paper. Our equalization method applies to any transmission scheme, as long as the time-domain transmit-receive relation can be modeled as (2). Equivalently, the transmit-receive relation (2) can be written as (3) where is the time-domain receive is the time-domain transmit signal, is an additive noise process signal, in the time domain, and is the time-domain channel matrix. A generic OFDM demodulator at the receiver’s end performs the following tasks with the sampled time-domain receive

signal: channel estimation, equalization, demodulation by means of the DFT, quantization, decoding, and deinterleaving. In this paper, we assume that a channel estimate in terms of the BEM coef?cients is already provided. In the next section, we develop methods for equalization of the receive signal using the estimated BEM coef?cients. B. Wireless Channel Representation With BEM We assume a basis expansion model (BEM) for the channel is modeled as a taps. With the BEM, each channel tap . Several linear combination of suitable basis functions bases are proposed in literature, including complex exponentials [29]–[32], complex exponentials oversampled in the frequency domain [33], discrete prolate spheroidal functions [20], polynomials [34], and the Legendre polynomials [8]. is With a speci?c set of basis functions, the channel tap represented as follows: (4) where is the th basis coef?cient of the th channel tap, is the th basis function, and is the BEM model order. Moreover, . Relation (4) is correct up to a modeling error, which can be reduced by increasing the model order . On the other hand, in pilot-based typically decreases the transestimation methods increasing mission capacity. Combining (2) and (4), the time-domain receive signal is expressed as (5) , and is an additive error, which where consists of random noise and a systematic modeling error. C. Equivalence of BEM and Product-Convolution Representation Changing the order of summation in (5), we obtain (6)

Equivalently, the time-domain channel matrix can be expressed as a sum of product-convolutions as follows: (7) where is a diagonal matrix with equal to , is a circulant matrix representing the cyclic convolution and . The above with the th set of the BEM coef?cients formulas lead to a prescription for a fast matrix vector multiplication, and are fundamental to our equalization algorithm.

HRYCAK et al.: LOW COMPLEXITY EQUALIZATION FOR DOUBLY SELECTIVE CHANNELS MODELED BY A BASIS EXPANSION

5709

TABLE I CHARACTERISTICS OF KRYLOV SUBSPACE METHODS GMRES AND LSQR APPLIED TO THE TIME-DOMAIN CHANNEL MATRIX , AND THE TIME-DOMAIN RECEIVE SIGNAL , WITH i ITERATIONS

y

H

both GMRES and LSQR. With the product-convolution structure of the channel matrix , computational complexity is reduced dramatically; see Section IV and Table II. B. Regularizing Properties of LSQR In exact arithmetic, the LSQR algorithm is equivalent to the conjugate gradient method applied to the normal equations [26]. Consequently, within iterations LSQR computes an exact solution of a system, which amounts to Zero Forcing. In practice, the inputs of LSQR are known only approximately, iterations visibly ampli?es the modeling erand using all rors and noise. However, LSQR has a built-in regularization mechanism, with the number of iterations as a regularization parameter. Consequently, an early termination of iterations effectively prevents the ampli?cation of errors and noise. The error obtained using LSQR with the optimal number of iterations is comparable to that of MMSE equalization with the optimal Tikhonov regularization parameter. An excellent survey of regularization methods is given in [28]. A detailed treatment of regularization with LSQR is given in [35, Sec. 7.6]. Combining these two references, one can conclude that LSQR achieves the minimum error possible for a certain class of regularization methods. Our numerical results also con?rm that equalization with LSQR is equivalent to MMSE equalization. Another regularization method consists of applying LSQR to the matrix and the vector de?ned as follows: (10) in order to solve the following least square problem: (11) (12) This approach is commonly known as damped LSQR; see depends on Appendix A. The choice of the parameter ambient noise and the modeling error. Damped LSQR combines LSQR with the Tikhonov regularization, and it has two regularization parameters: the number of iterations and the (continuous) damping parameter. Our numerical simulations show of that the minimum achievable BERs are similar for LSQR and damped LSQR, even if the noise parameters are known exactly at the receiver. However, a major advantage of damped LSQR is that semi-convergence is much milder, that is the BER as a function of the number of iterations grows very slowly after reaching its minimum. The optimal number of LSQR iterations depends directly on the noise level, and the distribution of the singular values of the channel matrix, which in turn depends on the maximum Doppler spread and the maximum delay spread. However, we have observed experimentally, that the number of iterations does not essentially depend on the number of OFDM subcarriers . C. Preconditioning It is well-known that the rate of convergence of the conjugate gradient method depends on the condition number of the underlying matrix. Speci?cally, for a matrix with condition number , the error of CG iterations decreases exponentially at the rate of

III. EQUALIZATION A. Iterative Equalization Methods It is well known that the conventional single-tap equalization in the frequency domain is inaccurate for doubly selective channels with severe ICI; see [10]–[12]. Direct methods, like MMSE equalization, have high computational complexity and memory usage. Low-complexity methods that rely on approximation by a banded matrix in the frequency domain, are equivalent to using the CE-BEM (see Theorem 1), and correct only relatively modest ICI. In their stead, we propose equalization with iterative methods for the regularized solution of linear systems. In this paper, we use two standard iterative methods, namely GMRES [25] and LSQR [26]. The iterative nature of our method is strictly limited to the algorithms that we use as linear solvers; see Appendix A for their detailed descriptions. In particular, we do not use a feedback loop with partially equalized signal symbols in this paper. Both GMRES and LSQR are Krylov subspace methods, i.e., each approximate solution is sought within an increasing family of Krylov subspaces. Speci?cally, at the th iteration GMRES constructs an approximation within the subspace (8) whereas LSQR within the subspace

(9) For a comparison of GMRES and LSQR, see Table I. Both methods use the number of iterations as a regularization parameter. At each iteration, GMRES and LSQR require the computa, together with tion of matrix-vector products of the form vector additions, scalar multiplications, and ?nding the 2-norms of vectors. Additionally, LSQR needs matrix-vector products of . Since the most expensive part is the computathe form tion of the matrix-vector products, the complexity of one iteration of LSQR is approximately twice that of one iteration of GMRES. In Appendix A, we provide detailed descriptions of

5710

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 58, NO. 11, NOVEMBER 2010

TABLE II THE COMPLEX FLOP COUNT FOR THE PROPOSED ALGORITHM PER OFDM SYMBOL WITH i ITERATIONS OF GMRES, LSQR OR DAMPED LSQR

; see [36, Theorem 10.2.6]. Consequently, CG typically converges much faster if applied to a matrix with a smaller condition number. This observation is routinely used to accelerate convergence of CG (and LSQR) by means of preconditioning. Preconditioning accelerates convergence of CG by effectively replacing a given matrix with one that has a smaller condition number [36, Sec. 10.3]. Similarly, convergence of GMRES can be accelerated if preconditioning can group the matrix eigenvalues in a cluster away in the complex plane; see [37, Corollary from the point 6.33]. For both LSQR and GMRES, an approximate inverse of a matrix is commonly used as a preconditioner, since the condition number of the so preconditioned matrix is reduced, and its in the complex eigenvalues are clustered around the point plane. The ?rst term of the product-convolution representation (7) may be regarded as a crude approximation to equal to is a suitable the channel matrix . Consequently, choice for a preconditioner. Some bases, for example, the Legendre polynomials, or complex exponential basis, contain a is a constant multiple of constant function. In such cases, as a preconditioner. the identity matrix, and we simply use Thus, we actually use the single-tap equalizer in the frequency is the domain as a preconditioner; see (21). The matrix exact inverse of the channel matrix for a purely frequency selective channel, and serves as an approximate inverse for a doubly selective channel matrix with a moderate Doppler shift. Howis not a useful ever, for channels with large Doppler shifts, preconditioner. In order to describe our preconditioner, we introduce a new variable (13) and substitute it into (3) in the following manner (14) (15) (16)

(17) where . In view of (7), we have (18) (19) (20) where for . Clearly, the is also a sum of transformed time-domain channel matrix product-convolutions, so both matrices and can be ap. Algebraically, replacing (3) by (17) plied at a cost is classi?ed as right preconditioning. For some bases, e.g., that is not a constant multiple of the identity of discrete prolates, matrix. In such cases, one should use both left and right preconditioning; see Appendix B for details. The eigenvalues of a representative time-domain channel ma, are shown trix , and its preconditioned version in Fig. 1. We notice that the eigenvalues of the preconditioned are clustered near the point in the complex matrix plane. We have observed experimentally, that preconditioning with the single-tap equalizer is not effective for channels whose Doppler shift exceeds 25% of the intercarrier frequency spacing. Such channels are far away from being frequency selective, and the single-tap equalizer is not a reliable approximate inverse. IV. DESCRIPTION OF THE ALGORITHM A. Decomposition of Channel Matrix The proposed equalization uses only the BEM coef?cients of the channel taps and the time-domain receive signal. We assume that estimates of the BEM coef?cients are known, for example they are provided by one of the estimation methods mentioned in the introduction. In this subsection, we derive algebraic formulas for the algorithms presented in the next subsection. It is well known (for example, see [36, p. 202]) that conjugating a circulant matrix by the discrete Fourier transform

HRYCAK et al.: LOW COMPLEXITY EQUALIZATION FOR DOUBLY SELECTIVE CHANNELS MODELED BY A BASIS EXPANSION

5711

In the frequency domain, (27) has the form (28) (29) (30) (31)

where

is the noise in the frequency domain, (32)

Fig. 1. The eigenvalues of the time-domain channel matrix with a Doppler shift equal to 17% of the inter carrier frequency spacing without preconditioning ‘’ and with preconditioning ‘’.

is the frequency-domain transmit signal as used in (1), and is the receive signal in the frequency domain. Equation (31) demonstrates that a doubly selective frequency-domain channel matrix is the product of a frequency selective (FS) operator , and an operator accounting for ICI. Equivalently, a frequency-domain channel can be represented as a sum of convolution-products. B. Algorithm The proposed equalization algorithm in the time domain is based on (24), and can be summarized as follows: given the time-domain receive signal and the BEM coef?cients , we solve for using iterative solvers GMRES or LSQR, and then . Speci?cally, we perform the we approximate with following steps. from the BEM Step 1) Compute the diagonal matrices ; see (22). coef?cients ; see Step 2) Compute the diagonal matrices (25). Step 3) Solve (27) for using GMRES or LSQR. ; see (32). Step 4) Approximate as Step 5) Quantize according to the alphabet used (4-QAM, PSK, etc.). We employ Step 2) only if we do preconditioning, otherwise we equal to . take A similar algorithm for equalization in the frequency domain can be formulated using (31), with the frequency-domain channel matrix expressed as a sum of convolution-products. Equalization in the time and in the frequency domain gives identical errors, because the errors are related by a unitary operator. Other iterative methods for the solution of linear systems can also be used in place of LSQR and GMRES. C. Computational Complexity We report operation counts of equalization of one OFDM to be precomsymbol. We consider the diagonal matrices puted. The computation of diagonal matrices from the operations. BEM coef?cients in Step 1) requires Whenever preconditioning is used, we perform Step 2) (cre), which requires ation of the diagonal matrices operations. In Step 3), we solve for using iterative methods

(DFT) results in a diagonal matrix. The cyclic convolution maare thus expressed as trices (21) where are diagonal matrices, and is the matrix of the DFT coincides with in dimensions. The diagonal of the matrix zero-padded to length , the DFT of the BEM coef?cients as follows: (22) for and denotes the transpose operation. Substituting relation (21) into (19), we get (23) (24) where (25) is a diagonal matrix. Similarly, substituting relation (21) into (13), we get (26) Combining (24) and (17), we express the time-domain receive signal in the following form:

(27)

5712

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 58, NO. 11, NOVEMBER 2010

GMRES or LSQR, which requires operations per iteration. A typical number of iterations does not exceed 16. In Step 4), we compute the frequency-domain transmit signal from using (32), which requires operations. In Step 5), we quantize the signal according to the alphabet operations. A detailed breakdown of used at the cost of computational complexity is provided in Table II. For certain narrowband applications in high Doppler regimes, the number of discrete channel taps is relatively small compared to . For such applications, the convolution should be ?ops per implemented directly with the complexity of iteration. D. Memory The equalization process begins with the time-domain receive signal and the BEM coef?cients , which are stored as and ?oating point complex numbers, respectively. and are diagonal matrices, which are stored as complex numbers each. The matrix-vector multiplications required by GMRES and LSQR are done using pointwise multiplications and the FFT-s of size ; see (24). After the th iteration, vectors of length , while LSQR GMRES requires storing requires storing four vectors of length . Thus, the proposed almemory. gorithm requires E. Comparison With Other Low-Complexity Equalizers Current equalizers achieve a reduced complexity by means of approximation by a banded matrix in the frequency domain [17], [9], [38]. Generally, such methods also require preprocessing with a time domain window, which increases ICI of neighboring subcarriers relative to distant ones. A banded approximation of the frequency domain channel matrix is equivalent to the complex exponential BEM (CE-BEM). A rigorous formulation is given in the following theorem (a related discussion is also provided in [39]). be an arbitrary time-domain Theorem 1: Let , channel matrix with the maximum discrete delay be the (cyclically) banded truncation of the freand let quency-domain channel matrix with the bandwidth . The time-domain matrix is a CE-BEM matrix with the model order , and with . the same maximum discrete delay However, the CE-BEM is known to be inaccurate for doubly selective wireless channels; see [2] and [5]. Setting aside the computational complexity, the most accurate equalization is obtained using the entire channel matrix. This is prominent in the results obtained in [17] by using the matched ?lter bound (MFB) equalization, and in [38] by using the nonbanded block linear equalizer (BLE). Moreover, no windowing is used by the two equalizers. However, the equalization results with the full channel matrix in [9] are not signi?cantly better than those of equalization with a banded approximation. This is because preprocessing with a window in the time domain is done before equalization; see Section VI in [9]. We have observed experimentally that such preprocessing increases the condition number of the whole channel matrix by orders of magnitude and degrades the BER after equalization with the entire channel matrix. Low-complexity equalizers in [9], [17], and [38] use a

Fig. 2. The BER as a function of the number of iterations at the receiver ve20 dB using exact CSI. locity of 175 km/h and the SNR of E =N

=

banded approximation of the frequency domain channel matrix. On the other hand, our proposed algorithm achieves low complexity by means of a representation of the channel matrix as a sum of product-convolution operators, which is inherent in any BEM. Thus, we use sparsity of the channel matrix in a different way than a banded approximation of the channel matrix in frequency domain. It is observed in [21] that for equalization with LSQR is as accurate as one with MMSE. We con?rm this observation experimentally in Section V. The computation of the optimal windows, as suggested in [17], [38], requires the second order channel statistics, which are not easy to obtain. In this paper we discuss methods which do not require any statistical information. Thus, when comparing the proposed equalization method with banded equalizers, we perform a linear preprocessing with a ?xed window before applying the banded equalizer. Speci?cally, we use the Blackman window, which is close to the window proposed in [38]. Figs. 2–4 compare the BERs of the proposed method with equalization using a banded frequency-domain channel matrix, which is preprocessed with a Blackman requires window. The latter equalization with bandwidth operations. The proposed equalizer does not use any windowing. We note that using a time domain window on the receiver’s side is equivalent to using a BEM with a modi?ed basis, namely the one obtained by multiplying the original basis by the window. Thus, a windowed BEM is also encompassed by our method, which applies to arbitrary bases. V. COMPUTER SIMULATIONS A. Simulation Setup Our transmission setup conforms to the IEEE 802.16e speci?cations. We simulate a coded OFDM system with subcarriers, utilizing 2.8 MHz of bandwidth at a carrier 5.8 GHz. We use a cyclic pre?x of length frequency of in order to avoid ISI. Consequently, the sampling period is 0.357 s, and the symbol duration is

HRYCAK et al.: LOW COMPLEXITY EQUALIZATION FOR DOUBLY SELECTIVE CHANNELS MODELED BY A BASIS EXPANSION

5713

maximum Doppler shift by the formula

is related to the receiver velocity

(33) where is the speed of light. To the signal ?ltered through the channel, we add additive white Gaussian noise (AWGN) of . varying energy per data bit to noise spectral density are reported for all the experiThe values of ments. The channel is simulated using the MATLAB Communication Toolbox (version 4.2). At the receiver, we ?rst compute the BEM coef?cients. Speci?cally, in our experiments we use the basis of the Legendre polynomials [8]. In experiments with estimated channel taps, we use the algorithm described in [8] for estimation of the BEM coef?cients. In experiments with the exact channel matrix, we compute the BEM coef?cients by projecting the channel taps on the basis functions. Subsequently, we equalize the receive signal using the proposed algorithm. Finally, the equalized signal is quantized and decoded using the BCJR algorithm and deinterleaved. As a measure of performance, we report the bit error rate (BER) averaged over 100 000 OFDM symbols. B. Discussion of Results First, we study the dependence of the BER on the number of iterations of GMRES, LSQR, and damped LSQR, with and without preconditioning. In the case of GMRES, we only present the results with preconditioning, since in our case without preconditioning GMRES needs approximately iterations to achieve a useful BER. We note that one iteration of LSQR requires approximately twice as many ?ops as that of GMRES; see Table II for details. Figs. 2–4 show the BER as a function of the number of iterations at receiver velocities of 175, 300, and 550 km/h, respectively. We notice, that receiver velocities of 175, 300, and 550 km/h correspond to re?ector velocities of 87.5, 150, and 275 km/h, respectively, and are ubiquitous in the modern environment. Additive noise in the 20 dB. The channel is simulated for a ?xed SNR of exact CSI is used in all these experiments. The BER at iteration number zero corresponds to single-tap equalization, and is shown for comparison. Fig. 2 presents results for the receiver velocity of 175 km/h, which corresponds to a Doppler shift of 0.94 kHz, or about 8.6% of the subcarrier spacing. The BERs of the banded equalizer and , with bandwidth 3 and 7 are equal to respectively. The BER of MMSE equalization equals . The BER of preconditioned GMRES decreases from after one iteration to after eight iterations. The BER of after one iteration to LSQR decreases from after 25 iterations. The BER of preconditioned LSQR decreases after one iteration to after 16 iterations. from after one The BER of damped LSQR decreases from after 25 iterations. iteration to Fig. 3 presents results for the receiver velocity of 300 km/h, which corresponds to a Doppler shift of 1.61 kHz, or about 14.7% of the subcarrier spacing. The BERs of the banded equaland , izer with bandwidth 3 and 7 are equal to

Fig. 3. The BER as a function of the number of iterations at the receiver ve20 dB using exact CSI. locity of 300 km/h and the SNR of E =N

=

Fig. 4. The BER as a function of the number of iterations at the receiver ve20 dB using exact CSI. locity of 550 km/h and the SNR of E =N

=

0.357 s 102.9 s. The information bits are encoded using a convolutional code of rate 1/2, passed through an interleaver, and mapped to 4-QAM symbols. For experiments with estimated BEM coef?cients, we use a frequency-domain Kronecker delta (FDKD) pilot arrangement in each OFDM symbol, as described in [40], [8]. The pilots are only used for estimation of the BEM coef?cients, and do not have any in?uence on the proposed equalization algorithm. Experiments with exact channel state information (CSI) do not use pilots in transmission. We simulate a wide sense stationary uncorrelated scattering (WSSUS) Rayleigh fading channel with a maximum delay of 11.4 s, which corresponds to the worst case when taps. Each tap has an average path gain of 2 dB and a Jakes Doppler spectrum. We ?lter the simulated transmit signal through channels with varying maximum Doppler shifts. The

5714

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 58, NO. 11, NOVEMBER 2010

respectively. The BER of MMSE equalization equals . The BER of preconditioned GMRES decreases from after one iteration to after 6 iterations. The BER of LSQR decreases from after one iteration to after 24 iterations. The BER of preconditioned LSQR decreases after one iteration to after 14 iterfrom ations. The BER of damped LSQR decreases from after one iteration to after 25 iterations. Fig. 4 presents results for the receiver velocity of 550 km/h, which corresponds to a Doppler shift of 2.95 kHz, or about 27% of the subcarrier spacing. The BERs of the banded equalizer and , with bandwidth 3 and 7 are equal to . respectively. The BER of MMSE equalization equals The BER of preconditioned GMRES decreases from after one iteration to after 5 iterations. The BER of LSQR decreases from after one iteration to after 16 iterations. The BER of preconditioned LSQR decreases after one iteration to after 13 iterations. from after one The BER of damped LSQR decreases from iteration to after 25 iterations. All iterative methods in Figs. 2–4 display the phenomenon known as semi-convergence. Speci?cally, the ?rst few iterations provide approximations of increasing accuracy, which is con?rmed by the decreasing BERs. The subsequent iterations do not further improve the solution, and sometimes even amplify ambient noise, as evidenced by the slowly increasing BERs. We observe that both LSQR and damped LSQR achieve comparable BERs. Thus, we only consider LSQR in our further experiments. Figs. 5–7 show the dependence of the BER on the SNR expressed in terms of the energy per data bit to noise spectral for channels simulated with the receiver density ratio speed of 175, 300, and 550 km/h. In all experiments, the number of iterations depends on the receiver velocity and the iterative method used, but not on the SNR. Speci?cally, the number of 20 dB. For iterations is optimized for a ?xed SNR of example, for the exact channel the iteration numbers are determined from Figs. 2–4. Further optimization of the number of iterations with respect to the SNR is not practical, since the noise level is often unknown. We present our results for channels estimated using a pilot-aided method described in [8], and also the results obtained with the exact channel matrix as a benchmark. We also report the BERs of the banded equalizer with bandwidth 7, and those of the MMSE equalizer. Fig. 5(a) and (b) shows the BER with the exact and estimated CSI, respectively, corresponding to the receiver velocity of 175 km/h, or 8.6% of the subcarrier spacing. With exact CSI, we use 20 iterations of LSQR, and 10 iterations of preconditioned LSQR, and 8 iterations of preconditioned GMRES. With estimated CSI, we use 14 iterations of LSQR, and 8 iterations of preconditioned LSQR, and 5 iterations of preconditioned GMRES. We report the observed BERs for 15 dB, and 25 dB, respectively, which are of high practical interest. With exact CSI, LSQR, respectively, achieves and , preconditioned LSQR the BERs of and , and precondiachieves the BERs of tioned GMRES achieves the BERs of and . and The banded equalizer achieves the BERs of , and the MMSE equalizer achieves the BERs of

Fig. 5. The BER as a function of the SNR expressed as E =N at the receiver velocity of 175 km/h. (a) Using exact CSI. (b) Using estimated CSI.

and , respectively. With estimated CSI, LSQR, respectively, achieves the BERs of and , preconand , ditioned LSQR achieves the BERs of and and preconditioned GMRES achieves the BERs of . The banded equalizer achieves the BERs of and , and the MMSE equalizer achieves the BERs of and , respectively. Fig. 7(a) and (b) shows the BER with the exact and estimated CSI, respectively, corresponding to the receiver velocity of 300 km/h, or 14.7% of the subcarrier spacing. With exact CSI, we use 20 iterations of LSQR, and ten iterations of preconditioned LSQR, and eight iterations of preconditioned GMRES. With estimated CSI, we use ten iterations of LSQR, and six iterations of preconditioned LSQR, and ?ve iterations of preconditioned GMRES. We report the observed BERs for 15 dB, and 25 dB, respectively. The banded equalizer

HRYCAK et al.: LOW COMPLEXITY EQUALIZATION FOR DOUBLY SELECTIVE CHANNELS MODELED BY A BASIS EXPANSION

5715

Fig. 6. The BER as a function of the SNR expressed as E =N at the receiver velocity of 300 km/h. (a) Using exact CSI. (b) Using estimated CSI.

Fig. 7. The BER as a function of the SNR expressed as E =N at the receiver velocity of 550 km/h. (a) Using exact CSI. (b) Using estimated CSI.

achieves the BERs of and , and the MMSE and , respecequalizer achieves the BERs of tively. With exact CSI, LSQR, respectively, achieves the BERs and , preconditioned LSQR achieves the of BERs of and , and preconditioned GMRES and . With estimated achieves the BERs of and CSI, LSQR, respectively, achieves the BERs of , preconditioned LSQR achieves the BERs of and , and preconditioned GMRES achieves the BERs and . The banded equalizer achieves the of and , and the MMSE equalizer BERs of and , respectively. achieves the BERs of Fig. 6(a) and (b) shows the BER with the exact and estimated CSI, respectively, corresponding to the receiver velocity of 550 km/h, or 27% of the subcarrier spacing. With exact CSI, we use 15 iterations of LSQR, and ten iterations of preconditioned

LSQR, and ?ve iterations of preconditioned GMRES. With estimated CSI, we use 14 iterations of LSQR, and 8 iterations of preconditioned LSQR, and ?ve iterations of preconditioned 15 dB, and GMRES. We report the observed BERs for 25 dB, respectively. The banded equalizer achieves the BERs of and , and the MMSE equaland , respecizer achieves the BERs of tively. With exact CSI, LSQR, respectively, achieves the BERs and , preconditioned LSQR achieves the of BERs of and , and preconditioned GMRES and . With estimated achieves the BERs of and CSI, LSQR, respectively, achieves the BERs of , preconditioned LSQR achieves the BERs of and , and preconditioned GMRES achieves the BERs and . The banded equalizer achieves the of and , and the MMSE equalizer BERs of and , respectively. achieves the BERs of

5716

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 58, NO. 11, NOVEMBER 2010

In our experiments, we observe that convergence of GMRES is very slow, which renders the method impractical. Preconditioned GMRES converges fast when applied to doubly selective channels with moderate Doppler shifts. LSQR is very effective for doubly selective channels with moderate to large Doppler shifts. Preconditioning LSQR with the single-tap equalizer accelerates convergence by a factor of about 2 in channels with moderate Doppler spreads. However, it is not effective for channels whose Doppler shift exceeds 25% of the intercarrier frequency spacing. Such channels are far away from being purely frequency selective, and the single-tap equalizer is not reliable as an approximate inverse. , where The banded equalizers have a complexity of is the bandwidth of a banded approximation in the frequency domain; see [9] for more details. In the example discussed in Fig. 3, the complexity of an LSQR based equalizer after 8 iterations is approximately the double of the complexity of a banded equalizer with bandwidth 7. On the other hand, the BER achieved with the LSQR based equalizer is equivalent to that of the full-block MMSE equalizer. LSQR-based equalization outperforms equalization based on approximation by a banded matrix in the frequency domain by approximately a factor of 10 in BER at the normalized Doppler of 27%. Our results indicate that the proposed equalization method can be applied in practice in combination with presently available BEM estimation algorithms. VI. CONCLUSION We present a novel, low-complexity equalization method, which uses the BEM coef?cients of the wireless channel taps without ever creating the channel matrix. The method is aimed at doubly selective channels with moderate and high Doppler spreads. Equalization is performed with classical iterative methods for linear systems, speci?cally with GMRES or LSQR. The main idea is to treat the wireless channel modeled by a basis expansion as a sum of product-convolution operators. This special structure permits a fast computation of matrix-vector products. For example, in case of an OFDM subcarriers, each iteration costs system with operations. Convergence of both GMRES and LSQR can be signi?cantly accelerated by preconditioning with the single-tap equalizer. We typically need 3–16 iterations for convergence. We validate our method by computer simulations, which use existing pilot-aided channel estimation methods. LSQR-based equalization outperforms equalization based on approximation by a banded matrix in the frequency domain by approximately a factor of 10 in BER at the normalized Doppler of 27%.

a linear system derived from the time-domain transmit-receive relation (3) by ignoring the noise component (34) , while and are vectors of The matrix is of size length . GMRES: The th Krylov subspace for the matrix and the vector is de?ned as follows: (35) GMRES approximates the exact solution of (34) by a vector that minimizes the norm of the residual (36) are not necessarily orthogThe vectors onal, so the Arnoldi iteration [36, Sec. 9.4] is used to ?nd orfor . Subsethonormal basis vectors is written as , quently, the vector where is the matrix formed by , and . upper Hessenberg The Arnoldi process produces an which satis?es matrix (37) Because has orthogonal columns, we have (38) , and . Therefore, where be found by minimizing the norm of the residual can

(39) , which is solved This is a linear least squares problem of size using the QR factorization. One can summarize the GMRES method as follows. At every step of the iteration: 1) Do one step of the Arnoldi method. which minimizes using the QR factor2) Find the ization. . 3) Compute The steps are repeated until the residual norm is smaller than a required threshold. LSQR: LSQR is an iterative algorithm for the approximate solution of the linear system (34). In exact arithmetic, LSQR is equivalent to the conjugate gradient method for the normal . In the th iteration, one constructs equations a vector in the Krylov subspace

APPENDIX A GMRES AND LSQR In this Appendix, we give a detailed description of GMRES [25] and LSQR [26], two well-known iterative methods for the numerical solution of a system of linear equations. We consider (40) that minimizes the norm of the residual .

HRYCAK et al.: LOW COMPLEXITY EQUALIZATION FOR DOUBLY SELECTIVE CHANNELS MODELED BY A BASIS EXPANSION

5717

LSQR consists of two steps: the Golub–Kahan bidiagonalization and the solution of a bidiagonal least squares problem. The , Golub–Kahan bidiagonalization [36] constructs vectors and positive constants as follows: 1. Set . , set 2. For

The process is terminated if or . In exact arithmetic, the ’s are orthonormal, and so are the ’s. Therefore, one can reduce the approximation problem over the th Krylov subspace to the following least square problem: (41) is the lower bidiagonal matrix with on the main diagonal, and on the ?rst subdiagonal. This least squares problem is solved at a negligible . cost using the QR factorization of the bidiagonal matrix Finally, the th approximate solution is computed as (42) where

The parameter is related to the power of the noise , and is known as the Tikhonov regularization parameter. We note that a similar approach can be used in the frequency domain. We can approximately compute using LSQR as explained in the previous subsection, but now LSQR is applied to the matrix and . This variant of LSQR using the regularization parameter is known as damped LSQR. We note that setting to zero reduces damped LSQR to standard LSQR as described in the previous section. In formula (44), a preconditioned channel matrix can also be used to achieve faster convergence. The most computationally expensive part of each iteration of damped LSQR is one matrix-vector product with the ma. trix , and another matrix-vector product with the matrix Clearly, the computation of one matrix-vector product with ei, requires more complex ther the matrix or the matrix ?ops than one matrix-vector product with the matrix or , respectively. We demonstrate that the computation of matrix, requires vector products with the matrix or ?ops, where is the number of sub-carriers for OFDM transmission; see Section IV. Thus, the computational complexity of per iteration. damped LSQR is

APPENDIX B LEFT PRECONDITIONING If a constant function is the ?rst basis function of a BEM, is typically useful as a right preconditioner. then the matrix With extensive numerical simulations, we have found no difas a left or as a right preference in BER between using as a right preconditioner preserves the conditioner. Using product-convolution structure of the transformed time-domain as a left precondichannel matrix. On the other hand, using tioner transforms the time-domain channel matrix into a sum of convolution-product-convolution operators. Consequently, preon the left is computationally more exconditioning by pensive than preconditioning on the right. For a BEM which is often a suitable left does not include a constant function, preconditioner. Left preconditioning can be introduced into the time-domain transmit-receive relation (3) as follows: (47) (48) where is the transformed time-domain receive signal, and is the transformed noise. Substituting (7) in (47), we obtain (49) (50) (51) where is the transformed time-domain channel is also a sum of product-convolution opermatrix. Clearly, ators, which allows a fast computation of matrix-vector products and . with

The second LSQR step solves the least squares problem (41) using the QR factorization of . The computational costs of this step are negligible due to the bidiagonal structure of . Furthermore, [26] introduced a simple recursion to compute and via a simple vector update from the approximate solution obtained in the previous iteration. Damped LSQR: The following transmit–receive relation is presented in (3), (43) where is the time domain receive signal, is the time domain transmit signal, is the time domain channel matrix, and is the additive noise. The objective of equalization is to compute the transit signal , given the received signal , and an estimate of the channel matrix . MMSE equalization is formulated as follows: (44) (45) where (46)

5718

IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 58, NO. 11, NOVEMBER 2010

REFERENCES

[1] T. Zemen and C. F. Mecklenbraeuker, “Time-variant channel estimation using discrete prolate spheroidal sequences,” IEEE Trans. Signal Process., vol. 53, no. 9, pp. 3597–3607, Sep. 2005. [2] Z. Tang, R. C. Cannizzaro, G. Leus, and P. Banelli, “Pilot-assisted time-varying channel estimation for OFDM systems,” IEEE Trans. Signal Process., vol. 55, no. 5, pp. 2226–2238, May 2007. [3] Z. Tang and G. Leus, “Pilot schemes for time-varying channel estimation in OFDM systems,” in Proc. IEEE Workshop Signal Processing Advances Wireless Communications (SPAWC), Helsinki, Finland, Jun. 2007, pp. 1–5. [4] C. Shin, J. G. Andrews, and E. J. Powers, “An ef?cient design of doubly selective channel estimation for OFDM systems,” IEEE Trans. Wireless Commun., vol. 6, no. 10, pp. 3790–3802, Oct. 2007. [5] T. Zemen, C. F. Mecklenbrauker, and R. R. Müller, “Time variant channel equalization for MC-CDMA via Fourier basis functions,” in Proc. MC-SS Workshop 2003, Oberpaffenhofen, Germany, 2003, pp. 451–458. [6] X. Ma, G. B. Giannakis, and B. Lu, “Block differential encoding for rapidly fading channels,” IEEE Trans. Commun., vol. 52, no. 3, pp. 416–425, 2004. [7] A. Cano, X. Ma, and G. B. Giannakis, “Block differential modulation over doubly selective wireless fading channels,” IEEE Trans. Commun., vol. 53, no. 12, pp. 2157–2166, 2005. [8] T. Hrycak, S. Das, G. Matz, and H. G. Feichtinger, “Practical estimation of rapidly varying channels in OFDM systems,” in preparation. [9] K. Fang, L. Rugini, and G. Leus, “Low-complexity block turbo equalization for OFDM systems in time-varying channels,” IEEE Trans. Signal Process., vol. 56, no. 11, pp. 5555–5566, Nov. 2008. [10] P. Robertson and S. Kaiser, “The effects of Doppler spreads in OFDMA mobile radio systems,” in Proc. 50th IEEE VTS Vehicular Technology Conf. (VTC) 1999—Fall, Amsterdam, The Netherlands, Sep. 1999, vol. 1, pp. 329–333. [11] Y. Li and L. J. Cimini, “Bounds on the interchannel interference of OFDM in time-varying impairments,” IEEE Trans. Commun., vol. 49, no. 3, pp. 401–404, Mar. 2001. [12] M. Russell and G. L. Stuber, “Interchannel interference analysis of OFDM in a mobile environment,” in Proc. 45th IEEE Vehicular Technology Conf., Chicago, IL, Jul. 1995, vol. 2, pp. 820–824. [13] Y.-S. Choi, P. J. Voltz, and F. A. Cassara, “On channel estimation and detection for multicarrier signals in fast and selective Rayleigh fading channels,” IEEE Trans. Commun., vol. 49, no. 8, pp. 1375–1387, Aug. 2001. [14] X. Cai and G. B. Giannakis, “Bounding performance and suppressing intercarrier interference in wireless mobile OFDM,” IEEE Trans. Commun., vol. 51, no. 12, pp. 2047–2056, Dec. 2003. [15] A. Gorokhov and J.-P. Linnartz, “Robust OFDM receivers for dispersive time-varying channels: Equalization and channel acquisition,” IEEE Trans. Commun., vol. 52, no. 4, pp. 572–583, Apr. 2004. [16] L. Rugini, P. Banelli, and G. Leus, “Simple equalization of time-varying channels for OFDM,” IEEE Commun. Lett., vol. 9, no. 7, pp. 619–621, Jul. 2005. [17] P. Schniter, “Low-complexity equalization of OFDM in doubly selective channels,” IEEE Trans. Signal Process., vol. 52, no. 4, pp. 1002–1011, Apr. 2004. [18] G. Taub?ck, M. Hampejs, G. Matz, F. Hlawatsch, and K. Gr?chenig, “LSQR-based ICI equalization for multicarrier communications in strongly dispersive and highly mobile environments,” presented at the 8th IEEE Workshop Signal Processing Advances Wireless Communications, Helsinki, Finland, Jun. 2007. [19] S. U. Hwang, J. H. Lee, and J. Seo, “Low complexity iterative ICI cancellation and equalization for OFDM systems over doubly selective channels,” IEEE Trans. Broadcast., vol. 55, no. 1, pp. 132–139, Mar. 2009. [20] T. Zemen and C. F. Mecklenbrauker, “Time-variant channel equalization via discrete prolate spheroidal sequences,” in Conf. Rec. 37th Asilomar Conf. Signals, Systems, Computers, Nov. 2003, vol. 2, pp. 1288–1292. [21] T. Hrycak and G. Matz, “Low-complexity time-domain ICI equalization for OFDM communications over rapidly varying channels,” in Proc. Asilomar Conf. Signals, Systems, Computers, Paci?c Grove, CA, Oct./Nov. 2006, pp. 1767–1771. [22] I. Barhumi and M. Moonen, “MLSE and MAP equalization for transmission over doubly selective channels,” IEEE Trans. Veh. Technol., vol. 58, no. 8, pp. 4120–4128, Oct. 2009.

[23] I. Barhumi, G. Leus, and M. Moonen, “Equalization for OFDM over doubly selective channels,” IEEE Trans. Signal Process., vol. 54, no. 4, pp. 1445–1458, Apr. 2006. [24] L. Song and J. K. Tugnait, “Doubly-selective fading channel equalization: A comparison of the Kalman ?lter approach with the basis expansion model-based equalizers,” IEEE Trans. Wireless Commun., vol. 8, no. 1, pp. 60–65, 2009. [25] Y. Saad and M. Schultz, “GMRES: A generalized minimum residual algorithm for solving non-symmetric linear systems,” SIAM J. Scientif. Stat. Comput., vol. 7, pp. 856–869, 1986. [26] C. C. Paige and M. A. Saunders, “LSQR: An algorithm for sparse linear equations and sparse least square problems,” ACM Trans. Math. Softw., vol. 8, pp. 43–71, 1982. [27] Draft IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems, IEEE Draft Standard 802.16e/D7, 2005. [28] A. Neumaier, “Solving ill-conditioned and singular linear systems: A tutorial on regularization,” SIAM Rev., vol. 40, pp. 636–666, 1998. [29] M. K. Tsatsanis and G. B. Giannakis, “Modelling and equalization of rapidly fading channels,” Int. J. Adapt. Control Signal Process., vol. 10, pp. 159–176, 1996. [30] G. B. Giannakis and C. Tepedelenlioglu, “Basis expansion models and diversity techniques for blind identi?cation and equalization of timevarying channels,” in Proc. IEEE, 1998, pp. 1969–1986. [31] H. A. Cirpan and M. K. Tsatsanis, “Maximum likelihood blind channel estimation in the presence of Doppler shifts,” IEEE Trans. Signal Process., vol. 47, no. 6, pp. 1559–1569, Jun. 1999. [32] M. Guillaud and D. T. M. Slock, “Channel modeling and associated inter-carrier interference equalization for OFDM systems with high Doppler spread,” in Proc. IEEE Int. Conf. Acoustics, Speech, Signal Processing (ICASSP), Apr. 2003, vol. 4, pp. 237–240. [33] G. Leus, “On the estimation of rapidly varying channels,” in Proc. Eur. Signal Processing Conf. (EUSIPCO), Sep. 2004, vol. 4, pp. 2227–2230. [34] D. K. Borah and B. T. Hart, “Frequency-selective fading channel estimation with a polynomial time-varying channel model,” IEEE Trans. Commun., vol. 47, no. 6, pp. 862–873, Jun. 1999. [35] A. Bjorck, Numerical Methods for Least Squares Problems, 1st ed. Philadelphia, PA: SIAM, 1995. [36] G. Golub and C. F. van Loan, Matrix Computations, 3rd ed. Baltimore, MD: The Johns Hopkins Univ. Press, 1996. [37] Y. Saad, Iterative Methods for Sparse Linear Systems, 2nd ed. Philadelphia, PA: SIAM, 2003. [38] L. Rugini, P. Banelli, and G. Leus, “Low-complexity banded equalizers for OFDM systems in Doppler spread channels,” EURASIP J. Appl. Signal Process., pp. 1–13, 2006. [39] Z. Tang, “OFDM transmission over rapidly changing channels,” Ph.D. dissertation, Faculty of Electr. Eng., Math., and Comp. Sci., Delft Univ. Technol., Delft, The Netherlands, 2007. [40] A. P. Kannu and P. Schniter, “MSE-optimal training for linear timevarying channels,” in Proc. IEEE Int. Conf. Acoustics, Speech, Signal Processing (ICASSP), Mar. 2005, vol. 3, pp. 789–792.

Tomasz Hrycak received the Ph.D. degree in mathematics from Yale University, New Haven, CT. Since 2005, he has been working in the Department of Mathematics at the University of Vienna, Austria. He develops numerical algorithms for signal processing and inverse problems.

Saptarshi Das received the M.Sc. degree in applied statistics and informatics from the Indian Institute of Technology, Bombay, in 2005 and the Dr.rer.nat. degree in mathematics from the University of Vienna, Austria, in 2009. From March 2007 to September 2009, he worked as a Research Assistant with in the Initiativkolleg framework of the University of Vienna. Since September 2009, he has been working as a Postdoctoral Researcher in the Faculty of Mathematics at the University of Vienna. He develops numerical algorithms for signal processing, image processing, and data mining.

Gerald Matz (S’95–M’01–SM’07) received the Dipl.-Ing. and Dr.techn. degrees in electrical engineering in 1994 and 2000, respectively, and the Habilitation degree for communication systems in 2004, all from the Vienna University of Technology, Vienna, Austria.

HRYCAK et al.: LOW COMPLEXITY EQUALIZATION FOR DOUBLY SELECTIVE CHANNELS MODELED BY A BASIS EXPANSION

5719

Since 1995, he has been with the Institute of Communications and RadioFrequency Engineering, Vienna University of Technology, where he currently holds a tenured position as Associate Professor. From March 2004 to February 2005, he was on leave as an Erwin Schr?dinger Fellow with the Laboratoire des Signaux et Systèmes, Ecole Supérieure d’Electricité, France. During summer 2007, he was a Guest Researcher with the Communication Theory Lab at ETH Zurich, Switzerland. He has directed or actively participated in several research projects funded by the Austrian Science Fund (FWF), the Vienna Science and Technology Fund (WWTF), and the European Union. He has published more than 130 papers in international journals, conference proceedings, and edited books. His research interests include wireless communications, statistical signal processing, and information theory. Prof. Matz serves on the IEEE Signal Processing Society (SPS) Technical Committee on Signal Processing for Communications and Networking and on the IEEE SPS Technical Committee on Signal Processing Theory and Methods, and he is an Associate Editor for the IEEE TRANS. SIGNAL PROCESS.. He was an Associate Editor for the IEEE SIGNAL PROCESSING LETTERS from 2004 to 2008 and for the EURASIP journal SIGNAL PROCESSING from 2007 to 2010.

He was Technical Program Co-Chair of EUSIPCO 2004 and has been on the Technical Program Committee of numerous international conferences. In 2006, he received the Kardinal Innitzer Most Promising Young Investigator Award.

Hans G. Feichtinger received the Ph.D. degree in mathematics and the Habilitation degree from the University of Vienna, Austria, in 1974 and 1979, respectively. He is a Professor at the Department of Mathematics at the University of Vienna. He has published more than 140 publications in both pure and applied mathematics. His research interests include harmonic and time-frequency analysis, especially Gabor and wavelet analysis. Prof. Feichtinger serves as the Editor-in-Chief of the Journal of Fourier Analysis and Applications, and as an Associate Editor of the following journals: the Journal of Approximation Theory, the Journal of Function Spaces and Applications, and Sampling Theory in Signal and Image Processing.

- ESTIMATION OF BASIS EXPANSION MODELS FOR DOUBLY SELECTIVE CHANNELS
- Time-domain channel shortening and equalization of OFDM over doubly-selective channels
- Reduced-complexity space-time turbo-equalization for frequency-selective MIMO channels
- Optimal Training for Block Transmissions over Doubly-Selective Fading Channels
- 06107431A Low-Complexity Design of Linear Precoding for MIMO Channels with Finite-Alphabet Inputs
- A DECODER FOR LOW-COMPLEXITY EQUALIZATION OF CODED FREQUENCY SELECTIVE MIMO CHANNELS
- Low-complexity Turbo equalization for time-varying channels
- Complexity analysis of a parallel lattice basis reduction algorithm
- SPACE-TIME MATRIX MODULATION EXTENSION TO UNKNOWN DOUBLY SELECTIVE MIMO CHANNELS
- W. A Complexity Constraint Best-Basis Wavelet Packet Algorithm for Image Compression. submi

- Low Complexity Equalization for Doubly Selective Channels Modeled by a Basis Expansion
- 盛世桃园楼盘营销策划方案
- 护理人员进修申请表
- 描写彩虹的精美现代儿童诗
- ACS型电子天*操作规程
- 2019年小学数学特岗教师面试试讲教案【范文汇编】
- 廖耀湘将军生*事迹介绍
- 广东省肇庆市端州区西区2016届九年级上学期期末考试英语试题(原卷版)
- 合肥无线电一厂华飞经营维修部分部企业信用报告-天眼查
- 东莞市绿凯节能科技有限公司企业信息报告-天眼查
- 恒文初三化学中考模拟试卷
- 第4章 综合指标 统计学,课件,ppt
- 【黄冈市蔡河中学陈小兵汇编】新人教版九年级化学上册 第七单元 燃料及其利用 教材图片课件
- 牛津译林版英语七年级下Unit 1《Dream homes》(reading 2)ppt课件
- 2017-2022年中国电容包装机行业市场研究及投资战略预测报告(目录)
- 儿童小说：喜羊羊与灰太狼之丰收喜羊羊与灰太狼之牛气冲天动画片
- 山西省粮食买卖合同【标准版】
- bbc音乐会管弦乐团为漫步拉开序幕
- 人教版数学小学五年级上册-第一单元-第2课时 小数乘小数(1)课件
- 银行银行承兑汇票管理办法(试行)模版
- 新标准英语(三起)Module 9 Unit 1 Best wishes to you!教学反思

- 儿童乐园活动方案(儿童乐园开业方案)
- 落实指导组扫黑除恶专项斗争工作反馈问题整改工作方案
- 钳工培训教案十三
- 让员工死心塌地工作：最佳薪酬体系讲议-PPT精选文档106页
- 上饶市三一办公设备有限公司企业信用报告-天眼查
- 传统食品致癌性大于苏丹红一号.doc
- 2016年北京电影学院电影声音制作考研辅导班笔记资料 导师作品 导师论文 复试要求
- openstack创建实例，报错No valid host was found
- 余姚市兴和酒吧娱乐有限公司企业信用报告-天眼查
- 优秀教师度考核个人工作总结1(四篇)
- 有关花的唐诗
- 九年级道德与法治下册第六单元放眼世界迎接挑战6.1世界的潮流与趋势第1框和*发展的时代主题课件粤教版
- 英国留学行前准备不可忽略的问题
- 2020年山西省粮食买卖合同
- vivoy67和x7买哪个好
- 安全教育黑板报图示
- 以秋天为话题的作文
- 结婚祝福成语摘抄
- 活动平板心电图QRS波振幅间期及其乘积诊断冠心病的价值
- 2006年上海市公务员考试行测真题【完整+答案+解析】
- 从法律角度谈中国茶文化遗产的保护
- 【推荐下载】化工行业将成为工业智能机器人的新蓝海
- 青岛坤雅居装饰工程有限公司(企业信用报告)- 天眼查
- 高一物理运动快慢的描述—速度2(201909)
- 个人账簿记账本Excel模板
- 浙江省发展和改革委员会关于浙江大学医学院附属第一医院庆春路院
- 污水管工作联系单
- 狐狸和小白兔的故事
- 关于EOF和Ctrl+Z~
- 2020春部编版三年级语文下册口语交际 趣味故事会 公开课PPT教学课件(17张ppt)
- 会计实训心得体会范文[工作范文]
- 纳米羟基磷灰石复合树脂材料修复牙体缺损的疗效观察
- 去吉隆坡要签证？
- 街道2018上半年工作总结范文与街道2018年全民健身周活动工作总结汇编.doc
- 大连长海许嘉雯海珍品有限公司(企业信用报告)- 天眼查
- 小米头戴蓝牙耳机说明书
- 2014通化事业单位通用知识复*资料：常识问题之中国文学史上的十
- 2019教育一年级下册品德课件上学真快乐北师大版共18张PPT数学
- 青胡椒油树脂化学成分的研究
- 大唐盛世如何饮茶
- 2019公司营销党支部下半年工作计划
- 5.机械设计制造及自动化专业本科人才培养方案-2013071