Citation |

- Permanent Link:
- http://digital.auraria.edu/AA00004136/00001
## Material Information- Title:
- Adaptive blind equalization with applications in communication sysytems [sic]
- Creator:
- Stuck, Gordon H
- Place of Publication:
- Denver, Colo.
- Publisher:
- University of Colorado Denver
- Publication Date:
- 2002
- Language:
- English
- Physical Description:
- 182 leaves : illustrations ; 28 cm
## Thesis/Dissertation Information- Degree:
- Master's ( Master of Science)
- Degree Grantor:
- University of Colorado Denver
- Degree Divisions:
- Department of Electrical Engineering, CU Denver
- Degree Disciplines:
- Electrical Engineering
- Committee Chair:
- Radenkovic, Mike
- Committee Members:
- Bialasiewicz, Jan
Moore, Linda
## Subjects- Subjects / Keywords:
- Digital communications ( lcsh )
Signal processing -- Digital techniques ( lcsh ) Equalizers (Electronics) ( lcsh ) Algorithms ( lcsh ) Algorithms ( fast ) Digital communications ( fast ) Equalizers (Electronics) ( fast ) Signal processing -- Digital techniques ( fast ) - Genre:
- bibliography ( marcgt )
theses ( marcgt ) non-fiction ( marcgt )
## Notes- Bibliography:
- Includes bibliographical references (leaves 181-182).
- General Note:
- Department of Electrical Engineering
- Statement of Responsibility:
- by Gordon H. Stuck.
## Record Information- Source Institution:
- |University of Colorado Denver
- Holding Location:
- |Auraria Library
- Rights Management:
- All applicable rights reserved by the source institution and holding location.
- Resource Identifier:
- 50726356 ( OCLC )
ocm50726356 - Classification:
- LD1190.E54 2002m .S78 ( lcc )
## Auraria Membership |

Full Text |

ADAPTIVE BLIND EQUALIZATION
WITH APPLICATIONS IN COMMUNICATION SYSYTEMS by Gordon H. Stuck B.S., Metropolitan State College of Denver, 1992 A thesis submitted to the University of Colorado at Denver in partial fulfillment of the requirements for the degree of Master of Science Electrical Engineering 2002 This thesis for the Master of Science degree by Gordon H. Stuck has been approved by Date Linda Moore Stuck, Gordon H. (M.S., Electrical Engineering) Adaptive Blind Equalization with Applications in Communication Systems Thesis directed by Associate Professor Mike Radenkovic ABSTRACT Adaptive blind identification and equalization with applications in communication systems are presented. Algorithm development and simulation results are given for direct and adaptive solutions of blind fractionally spaced equalization in noisy FIR channels. Additionally, the Constant Modulus Algorithm (CMA), in the context of fractionally spaced equalizers, is given with theoretical background, robustness considerations, and simulation verification. The theory and simulations are primarily verification of results in the recent literature, however some intermediate steps and additional derivations are presented. This abstract accurately represents the content of the candidate's thesis. I recommend its publication. Signed Mike Radenkovic in ACKNOWLEDGEMENT My thanks to my advisor, Dr. Mike Radenkovic, for his guidance, knowledge, and especially patience during this thesis project and my graduate career at UCD. In addition, I am indebted to Sid Henderson for his valuable discussions that helped me understand some key concepts in this work. My appreciation to my coworkers and friends Erwin Siegel, Mark Mauerhan, Richard Rasmussen, and Grant Szabo for their advice, support, and help with editing. Also I am grateful to the management at Agilent Technologies, especially Giampaolo Tardioli and Tom Beckman, for arranging a temporary relocation to Denver to do work on this project. Finally, my sincere and deepest thanks go to my family: my mother Lynn, stepfather Luis, stepmother Pamela, father Harvey, sisters Amy and Nancy, and brother Randy. CONTENTS Figures....................................................................x Tables.....................................................................xii Chapter 1. Introduction to Blind Equalization......................................1 2. Overview................................................................3 3. Notations used Throughout Text..........................................5 4. Problem Description and Mathematical Framework..........................7 4.1 The Composite Channel Model........................................... 9 4.2 Baud and Fractional Sampling...........................................11 4.3 Multichannel Model for Fractionally Spaced Channel.....................12 4.4 Alternate Vector Representation........................................14 4.5 The Equalizer..........................................................15 4.6 Overall Model Derived from Baud Spaced System..........................16 4.7 Pure Delay Equalizer for BSE System is Not Achievable............................................................17 4.8 Overall Model Derived from Fractionally Spaced System................................................................18 4.9 Noise Free Optimal Zero Forcing (ZF) Equalizer.........................21 4.10 Non Blind Optimal MMSE Weiner Equalizer in the Presence of Noise.....................................................22 v 5. Direct Blind Equalization Using Second Order Statistics (SOS).......................................................25 5.1 Cylic Statistical Property of Fractionally Sampled y(n)...................................................................26 5.2 Zero Forcing Direct Blind Equalizer.....................................27 5.3 MMSE Criterion (Weiner) Direct Blind Equalizer..........................29 5.4 Estimation of C2y from Sample Statistics................................32 5.5 Direct Blind Equalizer Calculation Methods..............................32 5.5.1 Batch..................................................................33 5.5.2 Recursive Non-Adaptive.................................................33 5.5.3 Recursive Adaptive Using Cyclic RLS....................................34 5.5.4 Recursive Adaptive Using Cyclic LMS....................................35 6. Direct Blind Equalization using Higher Order Statistics (HOS) with the Constant Modulus Algorithm (CMA)........................................................38 6.1 The CMA Algorithm..................................................... 38 6.2 Development of CMA from Godard [2]......................................40 6.3 More General Criteria...................................................43 6.4 CMA Cost Surface........................................................44 6.5 Robustness of CMA and Effects on the Cost Surface.......................47 6.5.1 Robustness to Equalizer Length.........................................48 6.5.2 Robustness to Channel Disparity........................................48 6.5.3 Robustness to Noise....................................................49 6.5.4 Robustness to a Non Constant Modulus Source............................51 vi 7. Performance Measures of Equalization Algorithms.......................53 7.1.1 MSE..................................................................54 7.2 ISI...................................................................56 7.3 Constellation Plots...................................................57 8. Channel Models Used in Simulation.....................................59 8.1 Channel Class RC: Raised Cosine......................................59 8.2 Channel Class AST: AppSigTec.........................................60 8.3 Channel Class NRR: Nearly Reflected Roots (i.e. Loss of Disparity)....................................................61 8.4 Channel Class NUC: Near Unit Circle..................................62 8.5 Channel Class B: Benign............................................ 62 9. Simulations...........................................................64 9.1 Experiment 1: Performance in Noise with RC Channel...............................................................65 9.1.1 Batch Method....................................................... 65 9.1.2 Recursive Non Adaptive Using Equations (5.32) and (5.29)................................................................68 9.1.3 Optimal MMSE Weiner Equalizer from Equation (4.32)................................................................68 9.2 Experiment 2: Channel Class AST Empirical Channel.....................69 9.2.1 Batch Method.........................................................69 9.2.2 Cyclic RLS Using Equation (5.38).....................................72 9.2.3 Cyclic LMS Using Equation (5.39).....................................72 9.2.4 CMA Using Equation (6.4).............................................75 vii 9.3 Experiment 3: Channel Class NRR......................................78 9.3.1 Batch Method........................................................78 9.3.2 Cyclic RLS Using Equation (5.38)....................................80 9.3.3 Cyclic LMS Using Equation (5.39)....................................80 9.3.4 CMA Using Equation (6.4)............................................83 9.3.5 CMA with Output Rotation Tweak......................................85 9.4 Experiment 4: Time Varying Channels..................................88 9.4.1 Cyclic LMS Using Equation (5.39)....................................88 9.4.2 Cyclic RLS Using Equation (5.38).................................. 91 9.4.3 Recursive Non Adaptive using Equations (5.34) and (5.35)............................................................. 93 10. Matlab Code........................................................ 95 10.1 Filename: ell.m......................................................95 10.2 Filename: el 11.m...................................................100 10.3 Filename: el2.m.....................................................105 10.4 Filename: e211.m....................................................110 10.5 Filename: e221.m....................................................115 10.6 Filename: e213.m....................................................121 10.7 Filename: cmal2.m...................................................127 10.8 Filename: e311.m....................................................134 10.9 Filename: e321.m....................................................138 10.10 Filename: e312.m..................................................144 viii 10.11 Filename: cma31.m 150 10.12 Filename: cma31r.m 10.13 Filename: e41.m... 10.14 Filename: e42.m... 10.15 Filename: e421.m.. References............... 157 164 170 176 181 IX FIGURES Figure 4.1 Very general communications system model...................................7 4.2 More detailed digital communications system................................8 4.3 Correctly designed pulses have no interference at the T-spaced sampling intervals............................................. 9 4.4 Baud spaced (P=l) and fractionally spaced (P=2 or more) composite channel................................................ 10 4.5 SIMO multichannel model for FS channel (P=2)............................ 13 4.6 Baud spaced system model with linear equalizer g(n).....................................................................15 4.7 Fractionally spaced system model with linear equalizer g(n)...........................................................16 4.8 Fractionally spaced multichannel system model with linear equalizer g(n)....................................................16 4.9 Overall baud-spaced system................................................16 6.1 JCmibpsk fr a well behaved noiseless real-valued channel..................................................................45 6.2 JCM contours (solid) and JMSE overlay (dashed) for a well behaved noiseless channel...........................................50 6.3 Effect of Non-CM 32PAM source (Kro = 1.8) on JCM for a well behaved noiseless channel.................................51 7.1 Example constellation plots...............................................58 x 8.1 Two ray multi-path channel with raised cosine pulse shape............................................................60 8.2 NRR channel......................................................62 9.1 Experiment 1 blind MMSE batch method.............................66 9.2 Blind ZF-MMSE FSE batch method...................................71 9.3 Blind ZF-MMSE FSE cyclic LMS method..............................74 9.4 Blind CMA FSE with three MSE calculation methods.................77 9.5 Blind ZF-MMSE FSE batch method...................................79 9.6 Blind ZF-MMSE FSE cyclic LMS method..............................82 9.7 Blind CMA FSE with three MSE calculation methods.................84 9.8 CMA constellation rotation.......................................85 9.9 Blind CMA FSE with three MSE calculation methods.................87 9.10 CMA constellation with manual rotation to match input QAM 16 phase...............................................88 9.11 Blind ZF-MMSE FSE cyclic LMS method..............................90 9.12 Blind ZF-MMSE FSE cyclic RLS method..............................92 9.13 Blind ZF-MMSE FSE recursive non adaptive method..................94 TABLES Table 8.1 Nearly common subchannel roots....................................61 9.1 Optimal Weiner MMSE equalizer comparison..........................69 s I ! xii 1. Introduction to Blind Equalization Linear equalizers are used in digital communication systems at the receiver to help maximize the information throughput. In general, digital communication involves the transmission of analog pulses, also known as symbols, over a channel. Typically the channel is a dispersive medium that introduces memory and spreads the signal over time. This spreading of the symbols can corrupt the precise time spacing and make the symbols spill over and corrupt adjacent symbols. This phenomenon is referred to as inter-symbol interference (ISI). As ISI grows, the probability of detecting a bit or symbol error at the receiver also grows. At high enough data rates all physical channels, such as coax, fiber optic, microwave, and twisted pair, exhibit ISI. Equalization methods estimate the linear filtering dispersion characteristics of the channel and insert an inverse filter at the receiver. The combined channel- equalizer linear filter pair then acts as an ideal channel. In the time domain this would be a Dirac delta impulse response. In the frequency domain this would be a flat line passing all frequencies (i.e. information) without distortion. Usually the non-ideal characteristics of the communications channel are not known a priori, especially in high speed, high capacity channels. The term a prioi 1 is used because some equalizations methods do eventually figure out (and use) the channel characteristics. Prior to the 1980s, most linear equalization methods involved using a training signal that was sent by the transmitter and was already known at the receiver. This consumes valuable channel capacity: A pre-arranged training sequence which is known a priori at the transmitter and receiver can be used to estimate the sequence, though periodic re- training my be necessary. Certain applications where a training sequence is either too costly in usable bandwidth or where a training sequence is impractical require a receiver design which operates on the received signal and possibly some statistics of the source, but not on the actual source sequence itself. Such an approach is termed blind. [6] 2 2. Overview This thesis begins by presenting some introduction to the general problem of blind equalization in communication systems and gives theory and simulation verification of the equalization techniques of Giannakis and Halford [1], It presents the theory and simulations related to the Constant Modulus Algorithm (CMA) technique and explains channel models and performance measures. Chapter 3 is a list of mathematical notations used throughout the text. Chapter 4 introduces a description of the problem of blind equalization in communication systems including channel models, baud and fractional sampling, and system representations via vectors and matrices, and describes the non-blind optimal Weiner Minimum Mean Squared Error (MMSE) equalizer. This is useful for performance comparison of methods in the following chapters. Chapter 5 presents the theory behind second-order-statistics direct blind equalization methods including Zero Forcing (ZF) and ZF-MMSE and shows the conditions needed for perfect equalization (PE). It also gives the equalizer calculation methods of batch, recursive non-adaptive, cyclic Least Mean Squares (LMS), and cyclic Recursive Least Squares (RLS). Chapter 6 develops the theory behind the Constant Modulus Algorithm (CMA), a popular higher-order-statistics blind equalization method and gives a 3 more general criteria related to the CMA. In addition it presents the CM criteria cost surface and studies its robustness under violations of the conditions of PE. Chapter 7 gives a description of the performance measures, such as mean squared error (MSE) and inter-symbol interference (ISI) by which the equalization techniques are compared. Though MSE can be found using input/output data, it gives a derivation using only system parameters. Chapter 8 introduces the channel models used in simulation. Chapter 9 gives a description of the simulations, including graphs and results with comparisons to [1]. Chapter 10 is a listing of the Matlab code used in the simulations. 4 3. Notations used Throughout Text co().............. Information (source) symbols, discrete time to................. Information (source) vector, discrete time hc(t) .............Composite channel, continuous time h ................. Channel impulse response vector, discrete time vc(t)..............Additive noise, continuous time. Assumed to be stationary as well as uncorrelated to co(n) v(n), v..............Additive noise (function and vector form), discrete time g(n), g..............Linear equalizer (function and vector form), discrete time f (n),f.............. Overall system impluse response (function and vetor form), discrete time (n),o>..............Equalizer output. An estimate of the source symbols (fucntion and vector form), discrete time y(n), y..............Input to equalizer (function and vector form), discrete time y0(n),y1(n),y0,yi.... Even and odd subchannel inputs to equalizers (function and vector form), discrete time y(n) = [y0(n)y1(n)]r 0T................. . Combined even and odd subchannel inputs Transpose 5 Conjugation O*........ ( )H or( )*T.......Conjugation and Transpose (Hermitian) r\t w ................. Pseudoinverse * ................. Convolution w.r.t.............. with respect to 6 4. Problem Description and Mathematical Framework A simple and general model for a communications system is comprised of a transmitter, channel, and receiver. See Figure 4.1. Figure 4.1 Very general communications system model The transmitter is fed from an information source, which for the purposes of this thesis we can assume to be binary. The transmitter typically takes groups of n bits from the binary stream input to encode a symbol a, from a finite alphabet, A. An simple example alphabet for four-level PAM would be A = {-3, -1, 1, 3} corresponding to the bit pair set {00, 01, 10, 11}. In this case n=2. Therefore the total number of symbols is 2n = 4. Often the symbols are complex with in-phase and quadrature components such as in the QAM 16 modulation scheme, which will be the primary scheme used in the analysis and simulations in this thesis. QAM 16 has a complex-valued alphabet with n=4 allowing for 16 symbols. This is representative of the dense and complex alphabets used in practice [6]. Compared to simpler modulation schemes, QAM16s dense constellation allows for more bits-per-symbol and thus more bits per hertz. This results in a higher 7 bandwidth efficiency. QAM (16 and higher) is carried by many modem systems [4]. -tb(n) Symbol Estimate hc(t) + vc(t) Primary focus of this paper Figure 4.2 More detailed digital communications system In the transmitter, the complex symbols are modulated onto the amplitude, frequency, and/or phase of analog pulses. These analog pulses are usually designed so that adjacent symbols dont interfere with each other. Ideally one could transmit infinite-frequency impulses which would not require pulse shapes that do not interfere with each other. But bandwidth is limited. Therefore one popular type of pulse is a raised-cosine or root-raised-cosine [7, pg. 546]. Both have time-domain nulls at the symbols intervals and conserve spectral bandwidth. See Figure 4.3 for an example. 8 Symbol n Figure 4.3 Correctly designed pulses have no interference at the T-spaced sampling intervals Next, the analog pulses are up-converted to RF. Sometimes its done in multiple IF stages to increase dynamic range (not shown in Figure 4.2). The RF is then bandpass filtered and transmitted through the channel. At the receiver, the signal is filtered and down converted into baseband. Most likely this downconversion is done in quadrature, similarly to the tranmitter. 4.1 The Composite Channel Model The composite channel hc(t) includes the known transmit and receive filters as well as the unknown channel (see Figure 4.2). This may include transmitter pulse shaping (e.g. raised cosine). The model can also include additive noise vc(t) that is assumed to be stationary and uncorrelated with the baseband information symbols Cfl(n). 9 vc(t) c(t) J0 xc(t)VU yc(t) t = nT P X*___ y(n) Figure 4.4 Baud spaced (P=l) and fractionally spaced (P=2 or more) composite channel The continuous time information signal coc (t), for the purposes of this thesis, is modeled as an impulse train of information symbols co(n): coc(t)= Â£(0(f)5(t-fT). t=-oo The signal at the output of the sampler is (4-1) y c (t) = k (t) h c (t)] + vc (t) = J c (x)h c (t x)dx + vc (t). (4.2) To derive an expression for yc (t) in terms of the discrete information symbols co(n), combine (4.1) and (4.2), yc(t)= X Jco(f)5(t-fT)hc(t-x)dx + vc(t). (4.3) = Â£co(f)hc(t-fT) + vc(t). (4.4) 10 Strictly speaking, the order of summation and integration in (4.3) cant be interchanged. Practically speaking, the number of source symbols is large but finite and the channel is FIR. Therefore (4.3) is absolutely integratable. Hence (4.4) is justified [6]. 4.2 Baud and Fractional Sampling If yc(t) is sampled, as shown in Figure 4.4, at t = nT/P, the received discrete signal y(n) = yc(t) for t = nT/P is With P=l, (4.5) can be written as an equivalent baud-spaced discrete time system The n index in (4.5) and (4.6) above (n=...,-2,-1,0,1,2,...) corresponds to T- spaced (baud spaced) time intervals. Using P=2 (or greater) is the basis for creating a fractionally spaced system. P=2 is the most popular choice for oversampling and is used throughout this thesis. With this, (4.5) can be written as an equivalent fractionally spaced discrete time nT nT (4.5) yBS(n)= Â£co(^)h(n-.o+v(n). (4.6) system 11 (4.7) Yfs (n) = X^)h(n -1) + v(n) = x(n) + v(n). t=-~ Here note that the n index in (4.7), (n = ...,-2,-1,0,1,2,...) corresponds to T/2-spaced (fractionally spaced) time intervals. However, the l index corresponds to baud spaced intervals because the information symbols are always baud spaced. The n index may be confusing. The reader should always look at the current context because sometimes n corresponds to baud (T) spaced time intervals; and other times n corresponds to fractionally (T/2) spaced time intervals. The primary focus of this thesis is the latter, and therefore the FS subscript will be dropped from yFS(n). 4.3 Multichannel Model for F ractionally Spaced Channel It can be seen from (4.7) that the output y(n) with n odd is a function of only the odd coefficients of the channel model h(n) and noise samples v(n). The same can be said for n even. Therefore upon defining y0(n) = y(2n) and y,(n) = y(2n +1), the single-input, single-output (SISO) model of (4.7) becomes an equivalent single-input, multiple-output (SIMO) multichannel model as shown in Figure 4.5 12 v0(n) with y0(n)= ^co(i)h0(n -Â£) + v0(n) e=-~ yi(n)= X(B(^)hi(n-^) + vi(n) h0(n) = h(2n);h1(n) = h(2n+l) x0(n) = x(2n);x1(n) = x(2n+l) v0(n) = v(2n);Vj(n) = v(2n+l) y0(n) = y(2n);y1(n) = y(2n+l). Note that in (4.8) there is a change in the symbol spacing. The n in the equations on the left corresponds to baud spacing within the subchannel signals h, x, v, and y. The u' on the right hand side corresponds to fractional (T/2) spacing. (4.8) (4.9) (4.10) 13 4.4 Alternate Vector Representation A vector representation of the finite-length T/2-spaced channel h(n) and T- spaced subchannels h0(n), h,(n)can be useful in equalizer and system analysis to follow. The following vectors are defined where Lh is the length of the T/2-spaced channel (note that the channel polynomial first vector h has T/2-spaced elements (h0,h,, ...). However when used alone, h can be considered to have T-spaced elements for analysis of baud spaced systems. Vectors can also be used for the finite-length equalizer g and overall system response f (these items will be developed later) in a similar manner to (4.11). In addition the input, intermediate, and output signals such as co(), x(n), v(n), y(n), and (b(n) can be expressed in vector form. These signals are generally considered to have an infinite length index n, but when used in vector form they usually span a finite-length recursive subset as a function of n. When used in the following chapters, they will be clearly defined. (4.11) order would be Lh -1). In general (4.11) is for fractionally spaced analysis and the 14 4.5 The Equalizer Consider now a more complete system model that includes a linear FIR equalizer, g(n), for both the baud spaced and fractionally spaced systems (see Figure 4.6, Figure 4.7, and Figure 4.8) The equalizers g(n), g(n), g0(n),and gj(n)are defined in a similar manner to h in (4.10). Also the equivalent finite vector T/2- spaced representations are defined similar to h, g = Lg 0 Â§1 Â§Lg-lJ CfQ o II go Si -El.-2 h k r 8i = Si S3 * E Lg -1. rj II O HO So Si -gLg-, r' r * 8i = Si Â§3 'Â§Lg-2 . VLg even (4.12) In general (4.12) is for fractionally spaced analysis and the first vector g has T/2- spaced elements (g0,g,, ...). However, when used alone g can be considered to have T-spaced elements for analysis of baud spaced systems. v(n) to(n) >d)(n) Figure 4.6 Baud spaced system model with linear equalizer g(n). Note that n corresponds to baud spacing. 15 v(n) co(n) Figure 4.7 Fractionally spaced system model with linear equalizer g(n). n corresponds to baud spacing, n corresponds to T/2 spacing. vo(n) co(n) (n) v,(n) Figure 4.8 Fractionally spaced multichannel system model with linear equalizer g(n). n corresponds to baud spacing. 4.6 Overall Model Derived f rom Baud Spaced System In the absence of noise, consider the overall baud-spaced system model f co(n) "Q)(n) Figure 4.9 Overall baud-spaced system which can be expressed as L.-l f (n) = Â£g(^)h(n -Â£) = g(n) h(n). (4.13) e=o 16 This convolution can be expressed as the inner product of a channel convolution matrix H, associated with vector h, and the equalizer vector g as f = Hg (4.14) with f = [f0f,...fLg+Lh_1Jr The H channel convolution matrix is defined as (4.15) The combined channel-equalizer vector f is length Lh +Lg -1 and the channel convolution matrix H is length (Lh +Lg -l)xLf, and is Toeplitz [18]. 4.7 Pure Delay Equalizer for BSE System is Not Achievable The desired overall system response f in most applications is a pure delay z5for some integer 5. However, the system of equations in (4.13) is always over determined, so a finite length equalizer g which results in a zero-ISI pure delay system is not achievable. In general, in the absence of noise an infinite length equalizer would be required [6], 17 4.8 Overall Model Derived from Fractionally Spaced System In the absence of noise the overall baud-spaced system model of Figure 4.9 can be derived from the fractionally spaced models of Figure 4.7 and Figure 4.8. The overall system transfer function, f, is always defined as baud spaced, regardless of whether it was originally derived from a baud-spaced or fractionally-spaced channel and equalizer. Here we will look at f(n) and f derived from the T/2-spaced channel and equalizer: Lg-1 Lg"l f (n) = Â£g0 Wh0 (n -1)+ Â£g, (f)h, (n i); (4.16) (=0 1=0 or in vector form: f = h0*g0+h1*g1; (4.17) and equivalently in the z (frequency) domain: F(z_l) = H0 (z-1 )G0 (z-1) + H, (z-1 )G, (z~'). (4.18) The form in (4.17) is equivalent to the integer-valued Diophantine equation. This equation is attributed to Bezout and leads to the Bezout relationship [19] when we let F(z_1) = z~5, which is our desired system response of a pure delay. In the baud-spaced equalizer (BSE) case, the equalizer approximates the inverse of the channel. But here in the fractionally spaced equalizer (FSE) case, g0 and gj and not generally the inverse of the T/2-spaced channel. 18 Similar to equation (4.14), the convolution in (4.16) and (4.17) can be expressed as the inner product of a channel convolution matrix and the equalizer vector. However, since the symbols are transmitted at baud rate and not T/2, the channel convolution matrix H has every other row removed. The result is a row decimated version of (4.14) (4.19) " ho fo u h2 hLh-2 hl h3 h0 h2 h, ho So gl f |_^rh +Lg -l J hL-2 h3 h2 hLh-> 1 The number of equations in (4.20) is (Lh + Lg -1)/ 2. Hi is a generalized Sylvester matrix [18] of the two subchannels. In some texts (4.20) is written in an equally valid, alternate form go r fo g2 f2 = [HIH,] gL,-2 g. = f g3 _gL,-,_ h0 h2 hL. hL hi K- h, h3 hu-, go g2 81,-2 8, g3 Sl.-, (4.21) 19 where = [H0 | H,] is block Toeplitz and H0, H, are the convolution matrices of the two subchannels. H0, Hj have a form similar to H in (4.15). Due to fractional sampling and the corresponding row decimation of H in Hx, the number of equations to be satisfied in (4.20) and (4.21) allows the system of equations to become exactly determined. If the equalizer length Lg is chosen so is square, the system of equations can be exactly solved if Hx is invertible (i.e. full column rank). Therefore, with sufficient equalizer length Lg > Lh -1 the FSE g can be found to achieve a pure delay, perfect equalization (PE) system F(z_1) = z-8 (for some integer 5). It can be shown that if Lg = Lh -1 the equalizer solution is unique. Due to its block Toeplitz structure, Hx will be full row rank and invertible if and only if there are no common subchannel roots in the H0(z_I) and H^z-1) polynomials. When this condition is met, the system is considered to have subchannel disparity. In summary, PE (and hence zero ISI) is possible with a finite length equalizer if these conditions are met: Length: The equalizer is of sufficient length Lg > Lh -1 Noise: There is no additive channel noise Disparity: There are no common subchannel roots in H0(z_l) and H,(z_1) 20 IID Source: The source co(n) is zero mean, iid, and has equiprobable symbols Our analysis of equalization methods (e.g. optimal, blind, and adaptive) will use FSEs only due to their ability to achieve PE with a finite length equalizer, their use in literature, and their frequent application. Any mention of BSEs will be for comparison only. 4.9 Noise Free Optimal Zero Forcing (ZF) Equalizer When the conditions in the previous section are satisfied, and Lg = Lh -1 to result in a square Hx matrix is used, the optimal ZF equalizer can be found by solving (4.19) However, for clarity recall that the goal is to create an overall delay function of z8 for the system response So we replace f, above with su = [Hj]% (4.22) ed+1 = [0 0-010 0] (4.23) d zeros which has a 1 in the (d+l)th position. Also gd is defined as the equalizer corresponding to the delay-d equalizer [1], So (4.23) can be rewritten as & = [hJ' (4.24) 21 4.10 Non Blind Optimal MMSE Weiner Equalizer in the Presence of Noise With channel noise v(n) present (note that here v(n) is fractionally 172 spaced from Figure 4.7 and the n notation has been dropped), which is a more real- world scenario, PE is not possible, even for an FSE. So we desire to strike a compromise between ISI reduction and noise amplification, where the latter is present if a ZF equalizer is applied. So one approach is to minimize the data symbol error e(n) in a mean-squared sense. e(n) = d)n -ton_d (4.25) where d is the choice of system delay. Vector to(n) has not been defined, but here we want to make it a finite length Lg + Lh -1 (or Lf) regressor vector as a function of baud spaced n coLf (n) = [co(n) co(n-l) co(n-(Lg + Lh -2))] (4.26) and also introduce the noise regressor vector vn using the alternate subchannel form similar to g in (4.21) VL (n)s[v(n-l) v(n-3) v(n-L -1) v(n) v(n-2) 6 v(n -Lg)] (4.27) It can be shown that the output can be expressed in the form w(n) = to(n)Tf^ + v(n)Tg = to(n)THig + v(n)Tg . (4.28) 22 Then using ed+1 as defined in (4.23) the desired output o)(n d) is equal to Since the symbol sequence co(n) is assumed here to be iid with variance aj and uncorrelated to the noise v(n) (with variance ov2), the mean square value of the error e(n) is MSE(g,d) = E{l e(n) I2} = a2 (Hig-ed+1)H(Hig-ed+1) + a2gHg . (4.30) This expression has two minimizing parameters g and d. For the optimal MMSE equalizer g, the solution is (see [6 pg 22], [8 pg 713], [5 pg 1931]) 8opt-mmse ~ (Hj.H| H f-IL ) H^ed+1 (4.31) and this is the classic Weiner filter. The corresponding MSE is found by using (4.30) and (4.31) to obtain (see [6 pg 22]) min MSE(g,d) = MSE(d) = ed+1 SOPT-MMSE i-H,(H"H,+-f-i,r,H; 'd+1 (4.32) and the optimal value of delay d is found to be the minimum diagonal element of the matrix in square brackets in (4.32) 23 ^OPT-MMSE arS mjn a (4.33) Jd,d , The reader should note that the optimal MMSE Weiner equalizer in (4.31) is not blind, but requires exact knowledge of the channel parameters. In the blind and adaptive equalization methods and simulations to follow, the optimal MMSE equalizers performance is used as a comparison basis and creates theoretical limit to how well the blind algorithms can perform. 24 5. Direct Blind Equalization Using Second Order Statistics (SOS) It has been shown in a variety of recent papers [12], [13], [14] that the second order statistics (SOS) of the channel output y(n) contains enough information to estimate most communication channels when the outputs are fractionally sampled. Because of this, many effective blind methods have been developed for estimating the channel from the output only SOS. The SOS methods presented in [1] allow for finding the linear equalizer g(n) directly from the data without first having to estimate the channel h(n). In this sense it is a direct method. Two of the methods in [1] will be presented in this thesis with some comments and intermediate derivation steps for clarity and better understanding. The first method is based upon (4.22) to find a ZF (i.e. ISI removal) direct blind equalizer, however this method is not recommended with noise present. The second method, which has similarities to the optimal MMSE equalizer in (4.31), finds a MMSE direct blind equalizer that strikes a compromise between reducing ISI and amplifying the noise. This method is also sometimes referred to by the criterion it is minimizing: direct blind equalization using the MSE criterion. i 25 Before these two direct blind equalization methods are presented, the cyclic statistical property of fractionally sampled y(n) is shown because both methods use this property. 5.1 Cylic Statistical Property of Fractionally Sampled y(n) Similar to (4.26) and (4.27), define the following regressor vectors to represent N vector observations of intermediate system signals x, v, and y of the fractionally spaced, SIMO model of Figure 4.7. xN(n) = [x0(n) x,(n) x0(n-l) x,(n-l) x0(n-N + l) x,(n-N + l)]T vN(n) = [v0(n) v,(n) v0(n-l) v,(n-l) v0(n-N + l) v,(n-N + l)]T 5J yN(n) = [y0(n) yi(n) y0(n-l) yi(n-l) y0(n-N + l) y,(n-N + l)]T The correlation of fractionally spaced y(n) of Figure 4.4 and equation (4.7) is c2y(n;m) = E{y(n)y*(n + m)} (5.2) which expanded is c2y(n;m) = jT ^c2(a(t2-^)h(n-2^)h*(n-2^2) + c2v(m) (5.3) where c2(0(m) = E{oXn)*(n + m)} andc2v(m) = E{v(n)v(n + m)} From (5.3) it can be shown that the correlation c2y(n;m)is periodically time varying in n with period 2 c2y(n;m) = c2y(n + 2^;m)V ^integer (5.4) To prove this, expand the r.h.s. of (5.4) 26 c2y(n + 2^;m) X Xc2B(/2-/1)h(n-2(^I-Â£))h\n-2(Â£2-Â£)) el=^(2=^ + c2v(m) (5.5) then, letting t\ = lx -l and/2 =l2-l, (5.5) becomes c2y(n + 2^;m) = Â£ ^c2(0(^2,-^1,)h(n-2^1,)h(n-2^2,) + c2v(m) (5.6) which has the same form of the r.h.s. of (5.3) and completes the proof that (5.4) is valid. The correlation matrix C 2y that is similar to (5.2), but uses regressor vector yN(n) instead of y(n), is useful in upcoming derivations: C2Ny=E{yN(n)yN(n)H}. (5.7) 5.2 Zero Forcing Direct Blind Equalizer To develop an expression for a ZF direct blind equalizer, start by considering the noise-free correlation matrix of x C2x = HJC2nX (5.8) and, since the input oo(n)is iid, C2(0 = o^I and therefore C^ojHlH;. (5.9) 27 Now, taking the complex conjugate and multiplying by the zero delay (d=0) zero forcing equalizer of (4.24) results in c;*go=Me>= where the last term is expressed in Matlab format (the first colon means all rows and the 1 means the first column). Solving for g0 and expressing the last term as a vector yields g.=^[c;"]'[h(0) 0 ... Of (5.11) and therefore the d=0 ZF equalizer can be found directly from the correlation matrix of the data to within a scale ambiguity of a^h*(0). When the equalizer length is chosen as Lg = Lh -1, C2x is square and the matrix pseudoinverse + in (5.11) can be replaced by a matrix inverse -1 and the equalizer g0 found by solving (5.11) is unique. It is possible to find the delay-d ZF equalizer directly from (5.11). For details on the derivation, see [1]. The result is Cgd=Cg0=aX(:,d+l) (5.12) g =<[C*2r note;* ]%(:,1). (5.13) The delay zero (5.11) and delay-d (5.13) ZF direct blind equalizers remove all the ISI from the system output in an ideal noise free environment. However, with noise present it doesnt do a very good job. Instead the noise is colored or 28 enhanced by the equalizers g0or gd [1]. Thus we will explore a new criterion, minimum mean squared error (MMSE) in the next section. 5.3 MMSE Criterion (Weine r) Direct Blind Equalizer The ZF equalizer of the prior section does not address noise suppression. However, real world signals usually include noise. Therefore we are motivated to find alternate criteria. Similar to (4.24) we consider an FIR Weiner filter to find the minimum mean squared error estimate of cb(n) using only the output y(n). So this method finds the equalizer g(n) so that the MSE-criteria cost function Jd,MSE = e{| cb(n) cofn d) I2} (5.14) is minimized. To begin the derivation, the output cb(n)is defined as L.-l L.-l 6(n) = Â£g0 (Â£)y0 (n Â£) + Â£ g, (f)h, (n -1) 1=0 e=o 1 Lg-l (5.15) =XXsi(Â£)yi(n-^- i=0 (=0 To minimize Jd MSE we take its complex partial derivative w.r.t. the unknown equalizer coefficients and set it equal to zero 2' a (5.16) 29 Swapping the expectation operator with the derivative, and recalling that f(x)2=2f(x)f(x) (presumably due to the chain rule), and using a as defined dx dx in (5.16) temporarily, = E 1 Lg-> X Xg.Wyi(n -1) (n -d) i=o e=o = 0 (5.17) the 2 drops out due to equality with zero and the co(n d) drops out of the partial derivative; thus = E< I a I dgl(m) l H L-l i=0 (=0 > = 0. (5.18) The next simplification requires some inspection of the indices k, m, i, and 1. Doing so it is easy to see that the partial derivative filters out all of the terms except yk(n m) resulting in = e{| a I |yk(n m)|}= 0. (5.19) Re-expanding a, = E 1 L,- X X & (^)yi (n ~ Xn d> |y k (n m)| i=o e=o ) = 0. (5.20) Next apply the rule I a II b 1= ab*, 30 = E 1 Lg_1 2 2 Si Wyk (n m)yi (n-Â£)-(o(n- d)y* (n m) i=o e=o = 0 (5.21) which yields the orthogonality condition i Lg_1 = X X bi WE{yI(n m)Yi (n ^)}]- E{(n d)yk (n m)}= 0. (5.22) i=0 t=0 Focusing on the second expectation, E{co(n-d)y*(n-m)}, (5.23) expand the y k (n m) term to yield E jco(n d) (^)hk(n m f)|. (5.24) Since the noise in uncorrelated with the input and the input is iid, the only correlation above occurs when Â£ in (5.24) is equal to (n-d). The rest of the time the correlation is zero. Therefore (5.24) becomes E{co(n d)co* (n d)hk (n m (n d))} =
and applying this back to equation (5.22),= X X ti (*)EK (n m)yj (n Â£)}] = a^h*k (d m). i=o e=o This equation can be written in matrix/vector form as (5.25) (5.26) 31 E{y*Lg/2(n)yL/2(n)}gd =<^HjI(:,d + l) or (5.27) (5.28) and this is equivalent to (5.12) with the replaced with The final zero delay and arbitrary delay MMSE equalizers are To solve for C^y in (5.7) so that the blind equalizers can be computed, consistent sample estimates must be used because in practice ensemble values are not available; therefore where N is the number of vector observations as introduced in (5.1). It is known that the normalized sample estimate in (5.31) converges in a mean square sense to the true value [1]. 5.5 Direct Blind Equalizer Calculation Methods This section presents four methods for equalizer calculation: (5.29) (5.30) 5.4 Estimation of C2yfrom Sample Statistics (5.31) 32 5.5.1 Batch The previous section gives a batch method of finding the ZF and MMSE equalizers for both zero delay and any delay. The equalizer is found directly without having to estimate the channel first. Implementation by using the batch method is fairly straightforward. For example, the sample estimator in (5.31) is used to calculate for a pre-determined number of samples (e.g. N=100). Then the MMSE zero-delay equalizer g0 is found according to (5.29). This equalizer can then be used in the system. Continuing this process, a new equalizer is calculated every N samples. However, it is also possible to find the estimate in an equivalent recursive manner that avoids having to perform long and computationally wasteful summations starting with the first symbol. Also, adaptive recursive methods that include a forgetting factor, A, are able to perform in situations where the channel parameters a time varying. 5.5.2 Recursive Non-Adaptive The following method gives results that are equivalent to the simple batch method, but does not require redundant wasteful summations starting at the first symbol. However, the method here is non-adaptive. Similar to the batch method, it does not perform well on channels with time varying parameters. To derive this method, start with (5.31) and expand to 33 1 e^(N)=ir-r25,v!(<)yv!(<)+yv!(N-1)yv!(N"1) (=0 N -1*. ^ 1 * ,XT T ,XT C2y(N)+ ^ yLg/2(N l)yLg/2 CN 1) (5.32) which results is a recursive form that can be applied directly to (5.29) to find the MMSE zero-delay equalizer g0. In addition, by using the matrix inversion lemma [19, pg 480], a method for finding g0 is available that does not require the inversion or pseudoinversion of C2y. To use it, letP(N) = [C2 (N)]-1 and apply the matrix inversion lemma to (5.32) p(Nr,=^p(N-l)-1+-U* /2(N-l)y* /2(N-1) N N g (5.33) P(N) = P(N-l)- N-l N yL /2(N-l)y7 /2(N-1) N P(N-l)^--------------77; P(N -1) (5.34) N-l N N-l l + ^y^^N-D^W-Dy^^N-l) This can be applied to (5.29) to find the zero delay MMSE equalizer g0(N) = ^P(N)H(:,l). (5.35) 5.5.3 Recursive Adaptive Usin g Cyclic RLS Using a method similar to the previous section, a forgetting factor X (0 < X < 1) is introduced to lower the influence of past observations on the 34 correlation estimate C2y thus allowing it to track time variations of the channel parameters C;,(N) = Â£X."-'y- 2(/)y7 ,2) + y: ,2(N)y^2(N) *=o (5.36) = XC;y(N-l) + y*Lg/2(N)y[?/2(N). This can be applied directly to (5.29) to find g0. A direct method for finding g0 without inversion or pseudoinversion of C2y is developed in a similar manner to (5.33)-(5.35). Again let P(N) = [C2y(N)]_I and apply the matrix inversion lemma P(N) = Ar'P(N-l)- )t-2P(N-l)y*g/2(N-l)yJg/2(N-l)P(N-l) \ + XyLg/2(N-mN-l)ylgl2(N-\) (5.37) This can be applied to (5.29) to find the zero delay MMSE equalizer i iN+l io(N)=irrP(N)HiH(:,1)' (538) This method can be used in a similar manner to derive the delay d ZF or delay d MMSE equalizer. 5.5.4 Recursive Adaptive Usin g Cyclic LMS A popular method of recursive direct equalizer calculation uses the stochastic gradient descent (SGD) approach in updating the equalizer coefficients. SGD is used in the cyclic LMS method of [1] and the CMA method of [2] and [6]. The CMA is a higher order statistics method that will be covered in a later chapter. 35 The cyclic LMS method updates the equalizer estimate using g0(N) = g0(N 1)i|iVJ0(N) (5.39) where pis the step size and VJ0(N)is the instantaneous approximation to the MMSE-criterion cost function presented in (5.14) as J0 = e| cb(n)-co(n) I2}. Using VJ0 = dJn 3Jn dJn d J 3-L _3go(0) 3g,(0) ag0(l) dgl(l) dg0(Lg-2) dg,(Lg-l) and the results of section 5.3, (5.40) VJ0 = E{yLg/2yL/2 teo - (;>!). (5.4i) allows for the instantaneous approximation at time N, VJ0(N) = yLg/2(N)y[g/2(N)g0(N-l)-o2Hji(:,l) (5.42) which can be used in conjunction with (5.39) to compute the equalizer estimate g0(N)as go(N) = g0(N-l)-|p[y*Lg/2(N)y^g/2(N)g0(N-l)-a2H(:>1)]- (5-43) The choice of p is important in speed of convergence and steady state performance. In simulations to follow, p = 2.5xl03 and p = 1 x 10 3are typical values. The cyclic LMS method presented here and used later in simulations does not rely on an explicit matrix inverse and therefore is not as sensitive to nearly 36 common subchannel roots. It is also somewhat low in computational complexity, but slow to converge [19, p 334-335] 37 6. Direct Blind Equalization using Higher Order Statistics (HOS) with the Constant Modulus Algorithm (CMA) The constant modulus algorithm (CMA) is arguably the most popular blind algorithm for cold startup of a tapped delay line equalizer. It was originally proposed by Godard [2] and developed by Treichler and Agee in [15] and has been the most studied blind adaptation algorithm of the 1990s. It has seen recent application in VLSI chips for HDTV demodulators and also an explosion of use in emerging wireless communications technologies [5]. 6.1 The CMA Algorithm The CMA algorithm is considered a higher order statistics (HOS) method because it accumulates the fourth order moment of the received signal [3]. It is considered constant modulus because the criterion it tries to minimize, JCM, operates purely on the magnitude of the equalizer output. It penalizes deviations in the modulus (i.e. magnitude) of the equalized signal away from a fixed value. It does not operate on phase; and therefore the phase shift of this adaptive equalizer is not determined. This can be seen in the output constellation rotation in the simulations later in this thesis. However, this is not a problem because most modem communication systems use differential encoding that can accommodate for the phase ambiguity [6]. 38 Under the conditions discussed in section 4.8 for perfect equalization (PE) of FSEs (i.e. no noise, sufficient equalizer length, subchannel disparity, and an iid source), the CMA algorithm can achieve PE with the additional constraint of the source having a constant modulus (e.g. BPSK or 4PSK). Surprisingly, CMA can also successfully equalize non constant source alphabets such as QAM 16. The CMA algorithm used in this thesis is the p=2 type proposed by Godard [2] which minimizes the following cost function JCM = E{(l d)(n) I2 -y)2} (6.1) where y is defined as the dispersion constant and is the ratio of the fourth to the second moments of the source sequence, thus y = E{l co(n) l4}/E{l co(n) I2} = E{l co(n) 14}/c2. (6.2) To minimize the CM cost function, a stochastic gradient descent (SGD) search algorithm is used which is similar to the one used with cyclic LMS. It can be shown that the gradient of JCM w.r.t. the equalizer coefficient vector is VgJcM = E{l ffl(n) I2 -y}d)(n)yLg/2(n). (6.3) The algorithm to adaptively update the equalizer coefficients g (at each timestep N) is obtained in a manner similar to the cyclic LMS algorithm in (5.43). The instantaneous approximation to the true gradient in (6.3) is found by dropping the expectation operator. This results in 39 g(N) = g(N-l) + fi{y-1 (b(n) l2}&(n)y*Lg/2(N) (6.4) which is the CMA SGD algorithm. The algorithm minimizes the CM cost by starting somewhere on the CM cost surface (determined by the initialization of g) and following the trajectory of steepest descent. The similarity between the CM criterion and the MSE criterion is strong. Minimizing the CM cost function is equivalent to minimizing the MSE cost function in the vicinity of convergence [15]. CMA is also globally convergent to the MSE minimizing equalizer using a finite length FSE or infinite length BSE under the PE conditions given in section 4.8. With channel noise present, JCM is a close proxy to JMSE [5]. 6.2 Development of CMA from Godard [2] The search for a carrier-phase independent algorithm led Godard to consider blind equalization techniques based only on the signal modulus |yn|. [16] In the following section the development of the CM criterion and the algorithm used for its minimization (CMA) is presented. It is based primarily on Godard [2], Consider first the conventional zero delay MSE criterion derived from (5.14) Using the widely-used LMS algorithm for adaptively minimizing, this leads to (6.5) 40 g(n +1) = g(n) \ y(n)((n)e"J
(6.6) J (6.7)
E I |