Multimodulus Algorithms for Blind Equalization by Jian Yang M.Sc. in Electrical Engineering, University of British Columbia, Vancouver, Canada A Thesis Submitted in Partial Fulfillment of the Requirements for the Degree of P H . D IN APPLIED SCIENCE in the Department of Electrical Engineering We accept this thesis as conforming to the required standard © JIAN Y A N G , Aug., 1997 University of British Columbia In presenting this degree at the thesis in University of partial fulfilment of of department this thesis for or by his or requirements British Columbia, I agree that the freely available for reference and study. I further copying the representatives. an advanced Library shall make it agree that permission for extensive scholarly purposes may be her for It is granted by the understood that head of copying my or publication of this thesis for financial gain shall not be allowed without my written permission. Department The University of British Columbia Vancouver, Canada Date DE-6 (2/88) fob 2 3 /? 3 7 Abstract In bandwidth-efficient digital transmission, the training of a receiver requires a start-up procedure. This start-up includes the three steps of setting the automatic gain control, recovering timing, and converging the adaptive filters. For many applications, start-up is facilitated by using a known training sequence, which can be used as an ideal reference by the receiver. However, sometimes the use of a training sequence is not feasible or not desirable. In this case, start-up has to be done blindly. The most challenging aspect of blind start-up is the convergence of the adaptive equalizer. This function is called blind equalization. Without ideal reference, the receiver has to make decisions about what data have been transmitted. Normally we use a decision device to make the assumptions on the input signals. This decision device is also called a slicer. These decisions are highly unreliable because the received data are corrupted by intersymbol interference due to distortion introduced by the communication link. As a result, the equalizer does not converge with the conventional least mean square (LMS) algorithm because the probability of wrong decisions is too high. The requirement for reducing wrong decisions leads to the development of blind algorithms. Several algorithms were developed in the past for blind equalization. The two most common ones are the constant modulus algorithm (CMA) and the reduced constellation algorithm (RCA). Both algorithms have been successfully used in many practical applications in data communications. However, improved blind algorithms are still in demand in order to meet the requirements of high data rate communications, where the implementation of blind equalization is required to be simple and reliable. RCA is simple to implement but is not very reliable. C M A is very reliable but has a high complexity., In this thesis, an improved blind algorithm, called multimodulus algorithm (MMA), is proposed. This new algorithm is more reliable than RCA and less complex than CMA. Blind algorithms, such as RCA or C M A , do not take full advantage of the knowledge of the statistics of the data signal, because they only use one statistical quantity, called modulus, during blind convergence. In contrast, M M A makes better usage of the knowledge of the statistics of the data signal and employs multiple moduli to achieve initial convergence. The use of multiple moduli makes M M A very flexible and easily adaptable to applications using two-dimensional transmission schemes with nonsquare or very dense signal constellations. Both R C A and C M A are not very effective for these types of applications. Most blind equalization algorithms minimize a cost function. Our investigation has shown that the minimum (residual) value of this cost function has a great influence on the reliability and speed of convergence of the corresponding blind algorithm. For example, for C M A , RCA and M M A , this residual value increases when the bandwidth efficiency of the transmission system increases, and the blind algorithms suffer a corresponding decrease in performance. Two generalized versions of M M A are proposed to circumvent the above problem. One is called generalized M M A (GMMA). The basic version of M M A uses multiple moduli primarily for nonsquare constellations when nonuniform symbol distributions are utilized. Multiple moduli are also used with G M M A but the additional purpose there is to decrease the residual value of the cost function. A similar effect is achieved by using another blind algorithm, called windowed M M A (WMMA). With W M M A , only one modulus is used, but the tap coefficients of the filter are only updated with some of the data, which leads to a reduction of the residual value of the cost function. The new M M A algorithm has been extensively tested with computer simulations. Most simulation results presented here were obtained with the 155 Mb/s 64-CAP transceiver specified in the A T M L A N standard for category 3 unshielded-twisted-pair office wiring. However, our results are equally applicable to other applications, such as the 52 Mb/s 16-CAP transceiver defined in DAVIC's specification for fiber-to-the-curb networks. Some preliminary experimental results obtained in the laboratory with such a 16-CAP transceiver are presented in this thesis. The computer simulations and laboratory experiments have confirmed that the basic M M A and its generalized algorithms show improved blind convergence performance or complexity savings when compared to previously available algorithms. M M A will likely be incorporated in future broadband access systems from Lucent Technologies, and will replace RCA and C M A , which were previously used, or eliminate the need for a training sequence. til Contents Abstract i? Acknowledgements yjj List of Tables iy/ List of Figures Vj| 1 Introduction 2 1.1 Applications of Blind Equalization 2 1.2 Bandwidth-Efficient Transmission Schemes 5 1.2.1 Multilevel Encoding 6 1.2.2 Efficient Spectral Shaping 13 1.2.3 Maximum Bandwidth Efficiency 14 1.3 Digital C A P Transceivers 15 1.4 The Concept of Blind Equalization 20 1.5 Literature Review 22 1.6 Thesis Overview 23 2 System Configuration 25 2.1 Linear Equalizer Structures 25 2.2 Problem Formulation 30 3 MultiModulus Algorithm (MMA) 3.1 3.2 4 37 Overview of Blind Algorithms 37 3.1.1 Reduced Constellation Algorithm (RCA) 38 3.1.2 Constant Modulus Algorithm (CMA) 41 MMA 44 3.2.1 Square Constellations 45 3.2.2 Nonsquare Constellations 47 3.2.3 ISI Optimization 50 3.3 Comparison of the Three Algorithms 55 3.4 Summary of Results 57 Generalized M M A (GMMA) 60 4.1 Cost Function Analysis 61 4.2 Principle of Multimodulus 65 4.3 Parameter Design 68 4.4 Examples 74 5 Windowed M M A (WMMA) 6 76 5.1 Algorithm Structure 76 5.2 Half-Constellation W M M A 77 5.3 Edge-Point W M M A 5.4 Filter Adaptation < 81 82 Computer Simulations and Laboratory Experiments 86 6.1 Simulation Environment 86 6.2 Computer Experiments 87 6.2.1 MMA 87 6.2.2 GMMA 6.2.3 WMMA 6.3 . '. 89 93 Laboratory Experiments 96 IV- 6.4 6.3.1 Testing E n v i r o n m e n t 100 6.3.2 E x p e r i m e n t a l Results 100 Remarks 101 7 Conclusions 107 7.1 Contributions 107 7.2 Future Work 110 Appendix A: Shaping Filter 112 Appendix B: Calculating of the Constant R 113 Appendix C: Cost Function and the Eye Opening 117 Bibliography 120 V List of Tables 2.1 Minimum values of the M M A cost function 36 3.1 Constant R for symbol levels ± 1 , ± 3 , ± 2 m — 1 3.2 Characteristics of the blind equalization algorithms 59 4.1 Parameters for 256-CAP 74 5.1 5.2 Constant R for half-constellation W M M A Comparison of cost functions 79 80 6.1 Parameters for 256-CAP 91 6.2 Choices of blind equalization algorithms 0.1 Step sizes for C-CAP 57 . 105 119 List of Figures 1.1 Applications of blind equalization 4 1.2 Multiple level encoding 8 1.3 NRZ and 2B1Q line code 9 1.4 Definition of excess bandwidth 10 1.5 Communication link using C A P 11 1.6 Signal constellations for two-dimensional encoding 12 1.7 Efficient spectral shaping 14 1.8 CAP versus Q A M 16 1.9 Impulse response of shaping filters 18 1.10 Frequency response of shaping filters with different excess bandwidths 19 1.11 Two-step blind equalization 21 1.12 Eye diagram and eye opening . 22 2.1 Block diagram and details of phase-splitting FSLE 27 2.2 Block diagrams of complex FSLEs 28 2.3 Various transfer functions obtained with CAP transceiver 31 2.4 Unequalized signal constellation 33 2.5 Impulse responses of shaping filters for 256-CAP 34 3.1 Interpretation of the cost function used by three differrent blind equalization . . . . 38 3.2 Diagonal solution for 64-CAP 41 3.3 144-point solution for 128-CAP 42 3.4 45 degree rotation 44 3.5 15 degree rotation 45 3.6 M M A moduli for 128-point signal constellation 48 3.7 Communication link 51 4.1 Errors for CF and LMS algorithm 62 4.2 G M M A design parameters for 256-CAP 69 4.3 Flow-chart for the design of the G M M A parameters 70 5.1 Half-constellation W M M A for 64-CAP 84 5.2 Edge-point W M M A for 64-CAP 85 6.1 MSE learning curves for various blind algorithms used for 64-CAP 88 6.2 Cost function evolution for M M A and G M M A when used with 256-CAP 90 6.3 After convergence with M M A 92 6.4 After convergence with optimized G M M A 92 6.5 Cost function evolution for M M A and W M M A when used with 64-CAP 94 6.6 MSE learning curves for various MMAs 95 6.7 After convergence with M M A 6.8 After convergence with half-constellation W M M A 97 6.9 After convergence with edge-point W M M A 98 • 97 6.10 After convergence with LMS algorithm 98 6.11 DSP16 setup in lab experiment 99 6.12 DSP test: M M A without noise 102 6.13 Transmitted signal with RF interference 103 6.14 DSP test: M M A and RCA with R F interference and no D F E 104 6.15 DSP test: M M A with R F interference and D F E 106 Vlll List of Abbreviations ADSL: asymmetric digital subscriber line A / D : analog-to-digital (converter) AGC: automatic gain control AWG: American wire gauge ATM: asynchronous transfer mode B A L U N : balance/unbalance C A P : carrierless amplitude modulation/phase modulation CMA: constant modulus algorithm DAB: digital audio broadcast DAVIC: digitial audio-visual council D / A : digital-to-analog (converter) DFE: decision feedback equalizer DSP: digital signal processing (or processor) HDTV: high definition T V FIFO: first-in-first-out FIR: finite impulse response FSLE: fractionally spaced linear equalizer F T T C : fiber-to-the-curb G M M A : generalized multimodulus algorithm ISI: intersymbol interference L A N : local area network LMS: least mean square LPF: low pass filter ~ M M A : multimodulus algorithm MSE: mean squared error N E X T : near end crosstalk NRZ: non-return to zero 3.4 45 degree rotation 44 3.5 15 degree rotation 45 3.6 " M M A m o d u l i for 128-point signal constellation 48 3.7 C o m m u n i c a t i o n link 51 4.1 E r r o r s for C F and L M S a l g o r i t h m 62 4.2 G M M A design parameters for 2 5 6 - C A P 69 4.3 Flow-chart for the design of the G M M A parameters 70 5.1 Half-constellation W M M A for 6 4 - C A P 84 5.2 Edge-point W M M A for 6 4 - C A P 85 6.1 M S E learning curves for various b l i n d algorithms used for 6 4 - C A P 88 6.2 Cost function evolution for M M A and G M M A when used w i t h 2 5 6 - C A P 90 6.3 After convergence w i t h M M A 92 6.4 After convergence w i t h o p t i m i z e d G M M A 92 6.5 Cost function evolution for M M A and W M M A when used w i t h 6 4 - C A P 94 6.6 M S E learning curves for various M M A s 6.7 After convergence w i t h M M A 97 6.8 After convergence w i t h half-constellation W M M A 97 6.9 After convergence w i t h edge-point W M M A 98 . . • 95 6.10 After convergence w i t h L M S a l g o r i t h m 98 6.11 D S P 1 6 setup i n lab experiment 99 6.12 D S P test: M M A w i t h o u t noise 102 6.13 T r a n s m i t t e d signal w i t h R F interference 103 6.14 D S P test: M M A a n d R C A w i t h R F interference and no D F E 104 6.15 D S P test: M M A w i t h R F interference and D F E 106 x Q A M : quadrature a m p l i t u d e m o d u l a t i o n R C A : reduced constellation a l g o r i t h m R F : radio frequency S D V : switched d i g i t a l video 2 B 1 Q : two-binary one-quaternary U T P : unshielded twisted pair W M M A : windowed multimodulus algorithm Acknowledgements I w o u l d like to t h a n k my supervisor Professor G u y A . D u m o n t for his help a n d support d u r i n g the course of this work. I w o u l d like to thank my Technical M a n a g e r D r . J . J . Werner who benefited me greatly from his twenty years of experience i n d a t a c o m m u n i c a t i o n s at B e l l L a b s , a n d m y D i r e c t o r D r . V i c t o r Lawrence for his support of this work. I w o u l d like to t h a n k my colleague D a l e H a r m a n who c o n t r i b u t e d to the e x p e r i m e n t a l lab work w i t h the real-time a n d real world D S P setups. T h a n k s also to the other members of the A d v a n c e d D a t a C o m m u n i c a t i o n s G r o u p of B e l l L a b s Innovations for their help a n d encouragements. Chapter 1 Introduction In many applications of data communications, blind algorithms are required to provide initial convergence of the adaptive equalizer. Blind algorithms behave differently from traditional adaptive algorithms, because they provide filter adaptation without accurate reference signals. In the next section, we describe some applications where blind equalization is required or desirable. Section 1.2 discusses some fundamental concepts, such as bandwidth efficiency, C A P line codes, and blind equalization. Finally, a literature review and a thesis review are provided at the end of the chapter. 1.1 Applications of B l i n d Equalization Asynchronous transfer mode (ATM) local area network (LAN) standards for telephone wiring in office buildings have recently been finalized [1]. These standards are different from previous L A N standards in that they use bandwidth-efficient digital transmission schemes. For such transmission schemes, the initial training of a receiver consists of the three main steps of setting the automatic gain control (AGC), recovering timing (clock synchronization), and converging the adaptive filters. This initial training is called start-up. For many applications, start-up is facilitated by using a training sequence. With a training sequence, an equalizer receives data that consist of known patterns also called ideal references. When the transmitted data are known, the equalizer can calculate meaningful errors with respect to the equalizer's outputs because filter adaptation is done with an ideal reference. However, when the use of a training sequence is not feasible or not 1 desirable, the adaptive filters require a b l i n d start-up. W i t h o u t ideal reference, filter a d a p t a t i o n is called b l i n d equalization. T h e major disadvantage of b l i n d e q u a l i z a t i o n is that it takes much more time to converge an equalizer t h a n is feasible w i t h a n ideal reference. T h e decision to use b l i n d equalization depends on the applications. Sometimes the use of b l i n d equalization is just a n o p t i o n a n d may be chosen for cost reasons. However, due to environment realities a n d systems considerations i n networks, the use of b l i n d e q u a l i z a t i o n may often be the only choice. T h e following gives examples of applications w h i c h t y p i c a l l y use b l i n d equalization. • Point-to-Point Networks: F i g . 1.1(a) shows a point-to-point c o m m u n i c a t i o n l i n k used for A T M - L A N applications [17] [18]. C o m m u n i c a t i o n between the A T M L A N s w i t c h and the l o c a l workstations is done on two separate twisted pairs. T h e usage of a t r a i n i n g sequence is not specified i n any of the A T M L A N standards w h i c h have been recently developed. T h u s , w h e n the w o r k s t a t i o n i n F i g . 1.1(a) is powered on, b o t h receivers must go t h r o u g h a b l i n d start-up. • Broadcast Networks In the broadcast network shown i n F i g . 1.1(b), the same signal is received by a m u l t i p l i c i t y of receivers. T h i s type of network topology w i l l be used i n f o r t h c o m i n g cable T V a n d wireless applications, such as h i g h definition T V ( H D T V ) a n d d i g i t a l audio broadcast ( D A B ) . T h e number of receivers that w i l l be involved i n these applications c a n range from several hundreds to several m i l l i o n s . U n d e r these conditions, it is not feasible for the t r a n s m i t t e r to send a dedicated t r a i n i n g sequence to each receiver. H D T V a n d D A B solve the start-up p r o b l e m by p e r i o d i c a l l y sending a t r a i n i n g sequence, w h i c h results i n a r e d u c t i o n of the a c t u a l d a t a rate available to the user. For this a n d other reasons, it is expected that a periodic t r a i n i n g sequence w i l l not be made available for forthcoming cable T V applications, so that the receivers w i l l need a b l i n d start-up. • Point-to-Multipoint Networks T h e configuration i n F i g . 1.1(c) is used for voiceband modems. M o r e recently, this network topology has also been adopted for l o c a l d i s t r i b u t i o n i n fiber-to-the-curb ( F T T C ) network architectures used for switched d i g i t a l video ( S D V ) systems [1] [5] [13]. I n F i g . 1.1(c), the t r a n s m i t t e r on the left continuously transmits the same downstream signal to a l l the receivers on the right. T h e upstream 2 d. Signal Identification - Wiretapping Figure 1.1: Applications of blind equalization 3 channel, in the opposite direction, is shared by all the transmitters on the right. Transmission in this direction is done in a bursty fashion. That is, each transmitter on the right transmits for a short period of time, when requested to do so by the downstream channel, and then stops. The upstream burst modem has to start up very fast in order to minimize the overhead associated with start-up. Thus, a training sequence is required. On the other hand, blind start-up is mandatory for the downstream channel if one wants to avoid the transmission of a periodic training sequence. To see why, we can consider the F T T C application, for example. In this case, the transceivers on the right in Fig. 1.1(c) are located in set-top boxes (of PCs). When one of the set-top boxes is suddenly turned on the corresponding receiver has to be trained. Sending a training sequence to this receiver in the downstream channel would disrupt transmission to the other set-top boxes, which is unacceptable. Thus, the receiver has to start blindly. • Signal Identification- Wiretapping The last application of blind equalization discussed here is signal identification [3]. For a variety of reasons, it may be desirable to tap a communication link and try to identify the kind of signal that is being transmitted. This is being done, for example, for signal classification purposes in the telephone network, as is graphically illustrated in Fig. 1.1(d). A general purpose receiver is fed the tapped signal and first determines whether the signal on the telephone connection is a speech signal or a data signal. If it is a data signal, it tries to blindly equalize this signal and determine its type from the equalized output signal and some other parameters. In summary, blind equalization is desirable in many applications because it reduces complexity and may be the only alternative available. Popular blind equalization algorithms have been developed for many years. However, improved algorithms for blind equalization are still in high demand in high-rate data communications. 1.2 Bandwidth-Efficient Transmission Schemes Advanced techniques are required in order to meet the demand for high data rate communications. In A T M L A N applications using category 3 wiring, for example, bandwidth-efficient transmission schemes are now being used to increase the data rate available on the desktop [1]. In the L A N 4 community, transmission or modulation schemes are also called line codes, and we will occasionally use this expression. Bandwidth efficiency for high data rates (>50 Mb/s) over category 3 cables in office buildings is required because the useful bandwidth of a 100m category 3 cable is about 30 MHz, and because there are stringent radiation limit requirements above 30 MHz. The bandwidth efficiency I is defined as where R is the data rate, expressed in bits per second (bps), W is the bandwidth utilization of the data signal, expressed in hertz (Hz), and the bandwidth efficiency I is expressed in bps/Hz. We see that the bandwidth efficiency can be improved by either increasing R for a given W, or by decreasing W for a given R. This can be done by using two independent techniques, which are multilevel encoding and efficient (Nyquist) spectral shaping. 1.2.1 Multilevel Encoding The first technique that can be used to increase bandwidth efficiency is multilevel encoding. In the following, we show how the bandwidth efficiency is increased by using this technique. Examples are given for one-dimensional (1-D) and two-dimensional (2-D) transmission schemes. Special attention is given to a 2-D scheme called carrier less amplitude modulation/phase modulation (CAP). • One-dimensional multilevel mapping The simplest transmission scheme available uses binary encoding, in which two possible symbol levels (±1) are used to transmit one bit of information. With multilevel encoding, blocks of m bits are mapped into symbols that have more than two values. Fig. 1.2 shows examples of binary encoding and multilevel encoding. With the non-return-to-zero (NRZ) line code shown in Fig. 1.2 (a), each single bit is encoded into ± 1 values. With the two-binary one-quaternary (2B1Q) line code shown in Fig. 1.2 (b), blocks of two bits are encoded into four possible values proportional to {±1, ±3}. In general, the encoding of blocks of m bits requires the usage of 2 m different symbol values. For a given bit rate R, multilevel encoding reduces the bandwidth requirements by a factor of m because the width of the square pulses used by the line codes is increased by m. Fig. 1.3 shows the Fourier transforms of the pulses used for the NRZ and 2B1Q transmission schemes, when they 5 provide the same d a t a rate R. It is usually assumed that the useful b a n d w i d t h W of N R Z a n d 2 B 1 Q extends up to the first n u l l . For N R Z this first n u l l occurs at a frequency w h i c h is equal to the b i t rate R, so that R = W a n d the b a n d w i d t h efficiency of N R Z is 1 b p s / H z . For 2 B 1 Q we have W = y , so that the b a n d w i d t h efficiency is 2 b p s / H z . T h e rate at w h i c h the square pulses i n F i g . 1.2 are sent t h r o u g h the channel is called s y m b o l rate. We see that half the s y m b o l rate is needed for 2 B 1 Q compared to N R Z . T h u s , i n general, i f 1 / T a n d W are the s y m b o l rate a n d b a n d w i d t h required for b i n a r y encoding, then the usage of m u l t i l e v e l encoding reduces these requirements to 1/mT a n d Wjm. Therefore, one-dimensional d i g i t a l transmission schemes can p o t e n t i a l l y provide a b a n d w i d t h efficiency close to m b p s / H z by using m u l t i l e v e l encoding only. It w i l l be shown i n section 1.2.2 that this b a n d w i d t h efficiency c a n be further increased to 2 m b p s / H z by using efficient spectral shaping. • Two-dimensional encoding and signal constellation T w o - d i m e n s i o n a l m a p p i n g is another technique w h i c h can be used to increase b a n d w i d t h efficiency. A s shown i n F i g . 1.5 (a), blocks of bits are first m a p p e d into two separate pulse streams. After c o n v o l v i n g w i t h two shaping filters, the two pulse streams are then added for transmission over the channel. I n this case, the two shaping filters are required to have some well-defined properties. F o r two-dimensional encoding, they are required to have the same spectral a m p l i t u d e characteristics, and impulse responses w h i c h are orthogonal to each other. W h e n two-dimensional encoding is used, it is convenient to introduce the concept of signal constellation, w h i c h is the display of a l l the possible discrete symbols i n the complex plane [27]. T h e signal constellations used for some L A N applications are shown i n F i g . 1.6. For instance, for 6 4 - C A P , blocks of six bits (i.e. m = 4) are represented by s i x t y four possible complex symbols or two-dimensional points. O n e way of d o i n g this is to m a p the first three bits into symbols a n a n d the last three bits into symbols b . T h r e e bits can represent eight d e c i m a l numbers or s y m b o l n levels. I n the A T M L A N standard, we use o d d integer numbers to represent the s y m b o l levels, a n d the b i t - t o - s y m b o l m a p p i n g is as follows 000 - > 1 001 -> 3 0 1 0 - > 5 0 1 1 - > 7 1 0 0 - » - 1 6 101 -»> —3 110 -> - 5 111->-7 (1.2) Bits 0 1 0 0 1 0 0 0 0 NRZ 1 1 t -1 (a) H-3A l+A 2B1Q 1 o-A -3A A=1/5 (b) Multilevel encoding maps blocks of bits into multilevel pulses • The encoding of blocks of m bits requires 2 m different pulse levels Figure 1.2: Multiple level encoding 7 8 PAM G(f) =0 P(f) CAP • 1/2T, 1/T, Figure 1.4: Definition of excess bandwidth 9 inphase shaping p 0 scrambled *\ Encoder d a t a in quadrature shaping p kT fit; D/A LPF signal out kT' a . Transmitter structure c h a n n e l H(f) in-phase FIR signal decision device C A/D kT' Decoder quadrature FIR decision device d b b. R e c e i v e r structure Figure 1.5: Communication link using C A P 10 kT descrambled d a t a out A n example of a bit sequence and of the corresponding t r a n s m i t t e d symbols is given below bit sequence : 0 1 1 0 1 0 1 0 1 0 0 0 symbol a n : 7 I -3 symbol b n : 5 | 1 ••• | | (1.3) • • •. (1.4) • •• (1.5) T h e two-dimensional symbols {a ,b } can be represented as two-dimensional (or complex) points n i n the (a ,b ) plane. n n n W e c a l l t h e m real a n d i m a g i n a r y s y m b o l s , or in-phase a n d q u a d r a t u r e phase symbols, a n d the symbols A n symbol a n and b n = a n + jb n are called complex or 2-D s y m b o l s . Since each takes one of eight possible values { ± 1 , ± 3 , ± 5 , ± 7 } , the display of a l l the possible combinations {a , b } requires a total of 8 x 8 = 64 points, as shown i n F i g . 1.6. W i t h 2-D m u l t i l e v e l n n encoding only, it is possible to achieve a b a n d w i d t h efficiency of y b p s / H z . T h i s c a n be increased to m b p s / H z by using efficient spectral shaping, w h i c h w i l l be discussed i n S e c t i o n 1.2.2. I Q F i g u r e 1.6: S i g n a l constellations for two-dimensional encoding • Encoding improvement factors We now provide formal definitions for the improvement factors i n b a n d w i d t h efficiency that result from multilevel encoding [27]. M u l t i l e v e l encoding reduces the b a n d w i d t h requirement because it allows a decrease i n s y m b o l rate for a given bit rate R. Specifically, the reduction i n s y m b o l rate is equal to the number of bits t r a n s m i t t e d i n each s y m b o l p e r i o d . P u l s e a m p l i t u d e m o d u l a t i o n ( P A M ) 11 is a one-dimensional transmission scheme. If m i bits are m a p p e d into one-dimensional symbols for P A M then the s y m b o l rate is reduced by a factor m i w i t h respect to 2 - P A M , w h i c h is a 2-level P A M line code ( N R Z is a n example of a 2 - P A M system w i t h m i = 1). If m 2 bits are m a p p e d into two-dimensional symbols for C A P then the s y m b o l rate is reduced by a factor m / 2 w i t h respect 2 to 4 - C A P , w h i c h is a 4-point C A P line code ( m = 2). Since m i a n d m are also the ratios between 2 the bit rates R 2 a n d the s y m b o l rate 1 / T i a n d 1 / T , respectively, the improvement factors 2 IF e n c in b a n d w i d t h efficiency due to multilevel encoding alone can be w r i t t e n as 1.2.2 R IFenc — , = m i 1/Ti IF = 77^ e n c = ^ for 1 — D line codes (1.6) for 2 - D . l i n e codes (1.7) Efficient Spectral Shaping T h e second technique that can be used to increase b a n d w i d t h efficiency is efficient spectral shaping. W i t h this technique, the square pulses used for N R Z a n d 2 B 1 Q i n F i g . 1.7, w h i c h have one s y m b o l p e r i o d d u r a t i o n , are replaced w i t h smoother pulses whose d u r a t i o n is several s y m b o l periods. E x a m p l e s of such pulses w i l l be provided i n later sections. W i t h efficient spectral shaping, the m i n i m u m b a n d w i d t h W i that can be used for the transmission of the signals is given by [27]: m n • W i = 2 T f f ° 1~D transmission schemes using a s y m b o l rate r m n • W i — m n for 2-D transmission schemes using a s y m b o l rate y r T h e amount of b a n d w i d t h used i n excess of the theoretical m i n i m u m is called excess b a n d w i d t h ( E B W ) , as shown i n F i g l . 4 . L e t W be the a c t u a l b a n d w i d t h u t i l i z a t i o n , we then have EBW = EBW = X 2 - = ~H W Wmin W ~ W W m i "min n 2Tl = ~l W /T2 J- / for 1 - D schemes for 2 - D schemes (1.8) (1.9) J- 2 where the excess b a n d w i d t h is expressed as a percentage of the m i n i m u m b a n d w i d t h . Thus, a system that uses the theoretical m i n i m u m b a n d w i d t h has zero excess b a n d w i d t h , a n d a system that uses twice the theoretical m i n i m u m b a n d w i d t h has 100% excess b a n d w i d t h ( E B W = 1 ) . 12 NRZ 0 -T/2 1.4 T/2 ' .EoulWlSt Ii 1.0 . CKaa»BW90« E u a u 8VV 100 « - o.» - u0.4 • y ^ ta • •I 0 SYMBOL T o.i pcnoo oi oi 0.4 os oo or oo FncoucMor ni) Figure 1.7: Efficient spectral shaping 1.2.3 Maximum Bandwidth Efficiency Multilevel encoding and efficient spectral shaping are two techniques which can be used independently to improve bandwidth efficiency. The best results are obtained when the two techniques are combined. In this case, the maximum bandwidth efficiency that can be achieved for 1-D and 2-D line codes is given by -^2,max R R mm R W l/2Ti min R 1/T = = 2m\ (1.10) ru2 (1.11) 2 Given a 1-D line code, it is always possible to design a 2-D line code which, provides the same bit rate R and uses the same bandwidth W. This can be done by mapping twice the number of bits in each complex symbol, i.e., m = 2mi, and using a symbol rate that is half that of the 1-D 2 line code, i.e., 1/T = l/2Ti. However, it is not always straightforward to design a 1-D line code 2 which is equivalent to a given 2-D line code. For example, for 32-CAP, we have m = 5, and an 2 13 oo io equivalent 1-D line code would require m i = 212. — 2.5, which is not easily implementable. 1.3 Digital C A P Transceivers This section discuss the digital C A P transceivers, which are used in A T M L A N and other applications. • CAP versus QAM Carrierless amplitude modulation/phase modulation (CAP) is a bandwidth-efficient two-dimensional passband line code. CAP is closely related to the more familiar quadrature amplitude modulation (QAM) transmission scheme. In voiceband modems, Q A M has been used for over 25 years, while C A P has been used for over 15 years. However, CAP is simpler to implement digitally. Transceiver structures for the CAP and Q A M transmission schemes are shown in Fig. 1.8. Both schemes use two-dimensional encoding. With the conventional Q A M transceiver structure shown in Fig. 1.8 (a), a modulator and a demodulator are required at the transmitter and receiver. The two modifications for Q A M that lead to a C A P system are shown in Figs. 1.8 (b) and 1.8(c) [4]. The first modification is to replace the low-pass filters in Fig. 1.8 (a) with in-phase and quadrature passband shaping filters, as shown in Fig. 1.8 (b). In order to remain compatible with the Q A M system in Fig. 1.8 (a), it is necessary to rotate the symbols at the symbol rate before feeding them to the shaping filters. A similar rotator must also be used at the receiver. Note that the rotator will be discussed in Section 3.1.2 and here we simply express the equation of how to computing the rotator 9 = Im{Y * A * } n n (1.12) The next modification, which leads to C A P , is to remove the rotators at the transmitter and receiver, as shown in Fig. 1.8 (c). This C A P system will generally not be compatible with the structures shown in Fig. 1.8 (b) and Fig. 1.8 (c), but provides the same theoretical performance, while being simpler to implement. • Structure of CAP transceivers The structure defined by the A T M L A N standard for a digital C A P transceiver is illustrated in Figl.5. At the input of the transmitter, the scrambled data are fed into an encoder, where 14 cosw t cosw t c c g(t) • 9(t) slicer U®—J g(t) slicer x g(t) sinw t sinw t c c a. Conventional QAM transceiver structure jwcnT -jwcnT a A b. Modified QAM transceiver structure H ,nW e » slicer 1* slicer w • -7=— P(t) •„<»> c. CAP transceiver structure Figure 1.8: C A P versus Q A M 15 w the b i t - t o s y m b o l m a p p i n g is performed by a two-dimensional m u l t i l e v e l encoder. maps blocks of bits into two-dimensional m u l t i l e v e l s y m b o l streams a n and b . n T h e encoder For instance, for the 6 4 - C A P a p p l i c a t i o n , three bits are m a p p e d into eight-level symbols i n each d i m e n s i o n , that is, {on} = {b } n = {±1, ±3, ±5, ±7}. N o t e that o d d integers are used as s y m b o l levels for the A T M standard [1]. A 6 4 - C A P signal constellation is shown i n F i g . 1.6 (b). T h e encoded symbols are then fed into two p a r a l l e l shaping filters, one is a n in-phase a n d the other one is a quadrature phase filter p . n filter p n D e t a i l s for the design of the shaping filters can be found i n A p p e n d i x A or [18] a n d [27]. T y p i c a l l y , the shaping filters have square-root raised cosine characteristics. T h e impulse responses of the shaping filters for the A T M L A N 6 4 - C A P s t a n d a r d are p l o t t e d i n F i g . 1.9. F i g s . 1.10 (a) a n d (b) show the frequency responses of the shaping filters for baseband a n d passband, respectively. T h e 6 4 - C A P transceiver uses a s y m b o l rate 1 / T = 2 5 . 9 2 M b a u d , a n d a center frequency / = 1 5 M H z . Since each 6 4 - C A P s y m b o l represents 6 bits, we have c a b i t rate R = 25.92 x 6 = 155.52 M b / s . T h e b a n d w i d t h efficiency achieved by the 6 4 - C A P system is equal to: I = 155.52/30 « 5.2 b p s / H z . T h e two shaping filters of a C A P transceiver have impulse responses w h i c h form a H i l b e r t pair. T h e transfer function of a filter that produces a H i l b e r t transform is given by —jsgn(f). T h a t is, the two shaping filters have the following relation PQU) = -jsgnU)PiU) where a n d PQ(/) (1-13) are the transfer functions of the in-phase a n d quadrature phase shaping filters respectively. T h e o u t p u t s of the two shaping filters i n F i g . 1.5 are subtracted (or added) a n d the result is then fed into a digital-to-analog ( D / A ) converter followed by a n i n t e r p o l a t i n g low-pass-filter ( L P F ) . T h e analog C A P signal that is launched o n the line c a n be expressed as oo s(t)= oo anP(t-nT)- £ n=—oo b p{t-nT) n (1.14) n=—oo where p(t) a n d p(t) are the overall impulse responses of the cascades of shaping filters, D / A , a n d low-pass filter. I n the case of the A T M standard, the signal s(t) is t r a n s m i t t e d t h r o u g h unshielded twisted pair ( U T P ) category 3 cables w i t h lengths up to 100 meters. 16 Figure 1.9: Impulse response of shaping filters 17 1/T = 25Mbauds a = 0.2 1.2 H 1.0 LU Q 0.8 3 a) H _l Q_ 2 < 0.6 0.4 0.2 0.0 T 20 —I 25 - 30 FREQUENCY (MHz) b) . FREQUENCY (MHz) Figure 1.10: Frequency response of shaping filters w i t h different excess b a n d w i d t h s 18 A t the receiver, the i n c o m i n g signal r(t) is s a m p l e d at the s a m p l i n g rate 1 / T ' . W e chose to use the phase-splitting equalizer i n our receiver, because it is one of the simplest receiver structures available for the n o r m a l mode of operation [30]. F i g . 1.5 shows the structure of the phase-splitting equalizer. I n this configuration, an in-phase filter c „ a n d a quadrature phase filter d as the two F I R adaptive filters for the equalizer. are employed n W h e n an ideal reference is not provided, a decision device is required after the equalizer to determine the t r a n s m i t t e d s y m b o l s a n the outputs y n and y n and b n from of the equalizer. F i n a l l y , a decoder makes a symbol-to-bit m a p p i n g and its output is fed to a descrambler (not shown) whose o u t p u t is' the t r a n s m i t t e d b i t stream. T h e phase s p l i t t i n g equalizer w i l l be discussed i n more details i n subsequent sections. 1.4 The Concept of B l i n d Equalization W h e n adaptive equalizers are i n i t i a l l y adapted w i t h o u t the help of a n ideal reference, they do not always converge. W i t h o u t an ideal reference, the decisions o n the equalizer's o u t p u t s have to be made w i t h a decision device, called a slicer, as s h o w n i n F i g . 2.1(a). A t the b e g i n n i n g of start-up, the equalizer's o u t p u t s are corrupted by a lot of i n t e r s y m b o l interference (ISI). I n this case, the slicer makes m a n y w r o n g decisions because of the severely distorted signals. T h e equalizer cannot converge i f the p r o b a b i l i t y of wrong decisions is too h i g h . B l i n d algorithms have the property of reducing w r o n g decisions (in some sense), so that equalizers can converge w i t h c o r r u p t e d data. B l i n d algorithms behave differently from the s t a n d a r d least mean square ( L M S ) a l g o r i t h m . In the L M S a l g o r i t h m , the cost function m i n i m i z e s errors c o m p u t e d between the slicer's i n p u t and output or between the equalizer's o u t p u t a n d a n i d e a l reference, i f available. T h e cost function m i n i m i z e d by the L M S a l g o r i t h m is the mean-square error ( M S E ) defined as CF = J where Y n = E[\E \ (LMS)] 2 min n is the equalizer's complex output, A n = E[\Y -A \ } 2 n n (1.15) is the slicer's complex o u t p u t or ideal reference, a n d [•] means e x p e c t a t i o n [9]. For b l i n d algorithms, different types of cost functions are utilized. For instance, for one form of the constant m o d u l u s a l g o r i t h m ( C M A ) , the cost function m i n i m i z e s 19 the dispersion of the equalizer's complex outputs around a circle CF = J = E[e (CMA)] = E[(\Y \ 2 ex 2 r>n n R)} 2 (1.16) 2 where the constant R is computed as E[\A \ E[\A \*} R (1.17) n n and is a statistical function of the symbols a and b . This type of constant appears in other n n blind algorithms, but is computed differently. The general principle of a blind start-up procedure is shown in Fig. 1.11. Initially, a blind adaptation algorithm, which minimizes the cost function in (1.16), for example, is used to partially converge the equalizer. We say that the algorithm is used to open the eye diagram, or simply the eye. Once the eye is open, the receiver switches to the standard LMS algorithm, which minimizes the cost function (MSE) in (1.15). kT' RCA quadrature FiFvy r — * LMS IS. Figure 1.11: Two-step blind equalization The expressions eye diagram and eye opening were originally coined when signal processing at the receiver was done in the analog world. A n analog eye diagram can be observed on an oscilloscope 20 by superposing all the possible waveforms of the signal in a symbol period when the transmitted data are random. Examples of eye diagrams for two- and eight-level data signal are shown in Fig. 1.12. The expression eye opening refers to the maximum spacing that exists between adjacent signal levels in Fig. 1.12. It should be clear from the figure that the eye diagrams on the right have a larger eye opening than the eye diagrams on the left, and that the latter would be more sensitive to noise than the former. Nowadays, the expressions eye diagram and eye opening are also used to describe a signal constellation and the amount of opening that exists adjacent clusters in the two-dimensional constellation obtained in a digital receiver. Figure 1.12: Eye diagram and eye opening 1.5 Literature Review Several blind algorithms have been developed to tackle the problem of blind start-up. The first major contribution to the field of blind equalization was made by Sato in 1975 [24]. The Sato algorithm applies to one-dimensional modulation schemes only. The algorithm was subsequently 21 generalized to two-dimensional m o d u l a t i o n schemes i n [8] a n d [10] a n d is called R C A i n this thesis. F i g . 3.1(a) shows the m o d u l u s used by R C A w i t h a 6 4 - C A P signal constellation. D u r i n g b l i n d startup, the equalizer m i n i m i z e s a cost function that is c o m p u t e d w i t h respect to a reduced constellation consisting of four points. T h e constant R represents the m o d u l u s of the four points a n d is c o m p u t e d from the statistics of the symbols a n and b n of the 64-point constellation. M o r e details o n R C A w i l l be given i n later sections. A n o t h e r w e l l - k n o w n b l i n d equalization a l g o r i t h m is called the constant m o d u l u s a l g o r i t h m ( C M A ) a n d was first described i n d e t a i l i n [8] a n d [11] a n d i n some workshop papers by G o d a r d and B e n veniste, w h i c h are not readily available. T h i s a l g o r i t h m was then extensively studied i n the literature [2], [7], [16] and [19] because of its nice m a t h e m a t i c a l structure. T h e a l g o r i t h m is especially well suited to applications where the receiver has to do b o t h channel e q u a l i z a t i o n a n d carrier recovery. C M A minimizes the dispersion of the equalizer's o u t p u t samples w i t h respect to a circle w i t h radius R, as shown i n F i g 3 . 1 ( b ) . W e can achieve more reliable convergence by using C M A t h a n by using R C A . However, as w i l l be shown later, because of the cost function used by C M A , the a l g o r i t h m does not provide linear phase equalization. T h i s may result i n a rotated signal constellation at the o u t p u t of the equalizer. After achieving convergence w i t h C M A , we have to use other techniques to tune the signal constellation to its final p o s i t i o n . T h i s makes the a l g o r i t h m i m p l e m e n t a t i o n c o m p l i c a t e d compared to other algorithms. M a n y researchers have investigated the issue of what types of signal statistics should be used for the cost functions of b l i n d algorithms [16] [20] [26]. M o s t investigations seem to indicate that secondorder statistics provide less robust systems t h a n higher order statistics. O u r own investigations, reported here, indicate that fourth-order statistics seem to provide the best compromise between performance a n d cost of i m p l e m e n t a t i o n . 1.6 Thesis Overview T h e thesis is organized as follows. C h a p t e r 2 describes the transceiver used for the A T M L A N standard a n d other applications. I n the same chapter, the p r o b l e m f o r m u l a t i o n for the equalizer structure that is being used is given i n terms of performance a n d reliability. 22 C h a p t e r 3 gives a detailed description of the proposed new M M A a l g o r i t h m . T h e algorithm's performance is then compared to the other two major b l i n d algorithms, i.e., R C A and C M A . T h e following chapter provides an investigation of the effect of the m i n i m u m value of the cost functions, w h i c h then leads to the definition of the generalized M M A intended for h i g h l y b a n d w i d t h efficient applications using large signal constellations. I n C h a p t e r 5, w i n d o w e d algorithms for M M A are proposed as a n extension of M M A to improve convergence speed. C o m p u t e r simulations for M M A a n d its modified versions as well as p r e l i m i n a r y experimental results o b t a i n e d i n the laboratory are provided i n C h a p t e r 6. F i n a l l y , we s u m m a r i z e our results for the b l i n d M M A algorithms, and present suggestions for further work. 23 24 Chapter 2 System Configuration In this thesis, b l i n d e q u a l i z a t i o n algorithms are used for the 155 M b / s 6 4 - C A P transceiver specified i n the A T M L A N s t a n d a r d [1]. However, the same algorithms can equally well be used for other applications, such as the 51 M b / s 1 6 - C A P transceiver used i n the D A V I C specification for F T T C networks [5]. T o implement the specified system, we use at the t r a n s m i t t e r a two-dimensional transmission scheme w i t h two parallel s h a p i n g filters whose impulse responses form a H i l b e r t pair. A t the receiver, several equalizer structures c a n be used for the two-dimensional C A P transceiver. A m o n g those structures, we have chosen the phase-splitting filter configuration to perform b l i n d equalization. I n the next section, we give a d e s c r i p t i o n of the transmitter a n d receiver structures. T h e n we formulate the problems associated w i t h the chosen equalizer structure. 2.1 Linear Equalizer Structures A t a receiver, several equalizer structures c a n be used for the two-dimensional C A P transceiver. T h r e e c o m m o n l y used structures are the two-filter (or phase-splitting) structure s h o w n i n F i g . 2.1(a), the cross-coupled structure shown i n F i g . 2.2(a), a n d the four-filter structure s h o w n i n F i g . 2.2(b). T h e use of each structure has its advantages a n d disadvantages. Decisions have to be made de- p e n d i n g on the a p p l i c a t i o n . T h e use of either the cross-coupled filter structure or the four-filter structure generally results i n stable b l i n d convergence. However, these equalizers do not necessarily provide the best steady-state performance for a given amount of complexity. B y using the two- filter structure, the equalizer does not necessarily provide stable i n i t i a l b l i n d convergence, However, this structure gives the best steady-state performance a n d the simplest i m p l e m e n t a t i o n among the three structures. B a s e d on the above considerations, we have chosen the two-filter structure for the 6 4 - C A P A T M L A N standard a p p l i c a t i o n because it provides the best performance i n steady-state operation w i t h the least amount of complexity. T h e price one has to pay by using the phase-splitting equalizer is that it is difficult to converge b l i n d l y at start-up w i t h a h i g h degree of reliability. T h e new techniques proposed i n this thesis a n d i n related work solve this p r o b l e m [29] [30]. T h e two-filter structure is shown i n F i g . 2.1(a), a n d details of the structure are given i n F i g . 2.1(b). Such a filter is also called a phase-splitting filter because the two filters converge to in-phase a n d quadrature phase filters c and d„, respectively, w h i c h have phase characteristics that differ by 90 n degrees. A t the i n p u t of the receiver i n F i g . 2.1(b) the received signal r(t) (t) = Y^i n (t r a s can be w r i t t e n as - nT) - b s(t - nT)] + f(t) n (2.1) n where 1 / T is the s y m b o l rate, £(f) is a d d i t i v e noise i n t r o d u c e d i n the channel, a n d s(t) a n d s(t) are overall impulse responses of the channel a n d t r a n s m i t t e r shaping filters. These impulse responses c a n be w r i t t e n as s(t) = p(t) ® h(t) s{t) = p(t) <g> h{t) (2.2) where p(t) a n d p(t) are the impulse responses of the in-phase a n d q u a d r a t u r e shaping filters at the transmitter a n d h(t) is the impulse response of the channel. T h e o u t p u t of the fractionally spaced linear equalizer is c o m p u t e d at the s y m b o l rate 1 / T . F o r the applications considered here, the s a m p l i n g rate 1 / T ' of the A / D is t y p i c a l l y chosen to be three or four times higher t h a n the s y m b o l rate 1 / T , so that T/T' = i, where i is a positive integer. T h e reason for choosing T/T' = 3 or 4 is to guarantee two desirable features: 1) Satisfy N y q u i s t ' s s a m p l i n g theorem, i.e. the s a m p l i n g rate has to be at least twice the highest frequency component of the analog signal. 2) K e e p the s a m p l i n g rate as low as possible, w i t h o u t v i o l a t i n g 1) so that the cost of the V L S I i m p l e m e n t a t i o n of the A / D and D / A is as low as possible. A s seen i n F i g . 2.1(a), the received s i g n a l r(t) is i m m e d i a t e l y fed to two adaptive filters c a n d d. T h e two filters share the same tapped delay line w h i c h stores sequences of successive A / D samples. 25 inphase r i/r>i/r slicer FIRC k y •> a n A/D quadrature kT" —*v+/f— ni/ FIR d -> b„ slicer ' n a. Phase-Splitting F S L E O- <J> o0 c c M ' d 0 o 0 k-2 di0 d 0 2 K5 n y n k-N 4r Ki)— b. Details of A d a p t i v e Filters F i g u r e 2.1: B l o c k d i a g r a m a n d details of phase-splitting F S L E 26 y N r T" nT o0 2 k-1 k T -*0 c 0 ii2f T' A/D KD- a. Cross-Coupled FSLE b. Four-Filter FSLE F i g u r e 2.2: B l o c k diagrams of complex F S L E s 27 T h e following definitions are made for the vectors r ( n T ) , c(nT) a n d d ( n T ) = c n [r/t,r^-i, [ o, c i , . . . , Civ] = vector o f i n — phase t a p coefficients = d c = T rjt_/v] = vector o f A / D samples i n delay line = vector o f quadrature tap coefficients [ d o , d \ , . . . , dx\ (2.3) (2.4) (2-5) where the superscript T denotes vector transpose, a n d the subscript n is a short n o t a t i o n for the s y m b o l p e r i o d nT. For the 6 4 - C A P A T M standard, we use i = 3, so that we have k = 3 * n . T h e outputs y a n d y n n of the equalizer are computed at the s y m b o l rate 1 / T N y =Yl - N °™ ^ r n 771 = ~ k m ) A) T ™ (( Vn=Y, 0 d 771 = r k - ^ /^ m (-) T 2 6 0 T h e equalizer's outputs can also be expressed i n vector form Vn = c £ r y = d£r n n Y = C^r n n (2.7) n where we have defined the c o m p l e x quantities + Yn = Vn C„ jy n = C n (2.8) + jd n Note that the t a p coefficients are initialized w i t h s h a p i n g filters. I n steady-state operation, the slicers are used to make decisions a a n d b o n the received samples, as shown i n F i g . 2.1(a). T h e n n equalizer's errors e a n d e are computed at the slicers as n n Cn ; Vn = c T n a n &n n Vn = b =d r — b n n n n (2-9) T h e t a p coefficients of the filters are then u p d a t e d b y using the L M S a l g o r i t h m . T h e tap u p d a t i n g algorithms for the two filters are given by c n (2.10) d + i = d - fie r (2.11) n + i = c„ - fie r n and n n n n where [i is a s m a l l number called step size. T h e above equations also provide the generic form for all the t a p u p d a t i n g algorithms discussed i n this thesis, except that, for b l i n d equalization, e n e are not c o m p u t e d according to (2.9). n 28 and A s p o i n t e d out i n C h a p t e r 1, for a b l i n d start-up we need at least two different tap u p d a t i n g algorithms. F i r s t , the eye is opened w i t h a b l i n d a l g o r i t h m , a n d then the tap u p d a t i n g algorithms in (2.10) a n d (2.11) are used to achieve steady-state convergence. 2.2 Problem Formulation F i g . 1.5 shows a t y p i c a l c o m m u n i c a t i o n l i n k i n c o r p o r a t i n g a C A P transceiver. T h e transmitter, on the top, transmits a signal that represents a block of bits, is m a p p e d to symbols a n d send out thought shaping filters. T h e signal is passed t h r o u g h a channel w i t h transfer function H(f). At the o u t p u t of the channel, some noise £(£) is added to the C A P signal a n d the result appears at the i n p u t of the receiver. The channel can severely distort the C A P signal as shown i n F i g . 2.3. C u r v e 1, i n this figure, shows the s p e c t r u m of the C A P signal at the o u t p u t of the transmitter. C u r v e 2 shows the s p e c t r u m of the same signal at the output of the channel, w h i c h is assumed to be a 100m unshielded twisted pair category 3 cable. N o t i c e that the signal has been severely attenuated a n d distorted at higher frequencies after passing t h r o u g h the channel. For the A T M C A P a p p l i c a t i o n , the d o m i n a n t component of the noise £(t) i n F i g . 1.5 is near-end crosstalk ( N E X T ) . T h e power of this type of noise increases by 15 d B per decade w i t h frequency. N E X T w i l l not be discussed any further here because it does not have a significant effect o n b l i n d equalization, for reasons w h i c h w i l l be discussed later. N E X T m o d e l i n g is discussed i n d e t a i l i n Refs. [18], [19] a n d [28]. The purpose of the receiver i n F i g . 1.5 is to compensate for the d i s t o r t i o n i n t r o d u c e d by the channel a n d to m i n i m i z e the effects of noise. I n this thesis, only linear receivers w i l l be considered. A linear receiver performs linear filtering operations only, a n d does not perform any nonlinear operations. It is a well-known result that the o p t i m u m linear receiver consists of a matched filter followed by a symbol-spaced F I R filter, as shown i n F i g . 3.7 [9] [21]. T h e m a t c h e d filter m a x i m i z e s the signal-to-noise ratio ( S N R ) at the i n p u t of the b a u d sampler, a n d the F I R filter removes the ISI i n t r o d u c e d by the channel and matched filter. It c a n be shown that the receiver structure i n F i g . 1.5 implements d i g i t a l l y a n d adaptively the 29 1.2 1 - Transmit Shaping Filter 2 - Overall Channel 3 - Z F Linear Equalizer 4 - Optimum Linear FREQUENCY (MHz) F i g u r e 2.3: Various transfer functions obtained w i t h C A P transceiver 30 o p t i m u m linear receiver for C A P signals. T h i s type of receiver structure is called a fractionally spaced linear equalizer ( F S L E ) [22]. T h e m a g n i t u d e of the transfer function synthesized by the two adaptive filters i n F i g . 1.5 is shown as C u r v e 4 i n F i g . 2.3. C u r v e 3 i n this figure corresponds to the transfer function of a n equalizer that compensates for the channel d i s t o r t i o n only, and does n o t h i n g against noise. T h i s is the transfer function synthesized by the so-called zero-forcing linear equalizer, w h i c h s i m p l y "inverts" the channel. C u r v e 4 for the o p t i m u m linear receiver was obtained i n the presence of N E X T . T h i s type of noise has more energy at higher frequencies than at lower frequencies, w h i c h explains the shape of the transfer function synthesized by the F S L E . T h i s transfer function goes to zero i n the upper roll-off region where the noise is large and the signal is weak, a n d it amplifies signals i n the lower roll-off region, where the signal is strong and the noise is s m a l l . I n the flat region of the t r a n s m i t t e d spectrum, the F S L E has essentially the same transfer function as the zero-forcing equalizer. Before an equalizer has i n i t i a l l y converged, it has to deal w i t h a s i g n a l w h i c h has been severely d i s t o r t e d by the channel, as s h o w n i n F i g . 2.3. T h e signal constellation at the o u t p u t of the equalizer i n F i g . 1.5 before convergence is started is shown i n F i g . 2.4. T h i s constellation has n o t h i n g is c o m m o n w i t h the 64-point constellation used at the transmitter (see F i g . 1.6). It s h o u l d be clear from F i g . 2.4 t h a t a n a l g o r i t h m , such as the decision directed L M S a l g o r i t h m , w h i c h makes a decision on w h i c h s y m b o l has been t r a n s m i t t e d a n d then computes a n error w i t h respect to this decision, has no chance to be successful i n converging. T h i s is why other algorithms, better suited to b l i n d start-up, have to be u t i l i z e d . T h e m a i n challenge i n the i m p l e m e n t a t i o n of b l i n d start-up is to provide reliable i n i t i a l convergence. For a l l the equalizer structures, this means that a good i n i t i a l eye o p e n i n g of the signal constellation can be achieved. I n a d d i t i o n , for the phase-splitting filter structure, this also means that the equalizer does not converge to w r o n g solutions. I n this thesis we concentrate on the former issue. T h e issue of w r o n g solutions for the phase-splitting equalizer is discussed i n detail i n related work [30]. I n i t i a l b l i n d convergence is affected by two factors. O n e factor is the signal d i s t o r t i o n caused by large i n t e r s y m b o l interference. T h e other factor is the residual value o f the cost function after convergence. B o t h effects grow w i t h increasing m, where m denotes the number of s y m b o l levels. 31 REAL F i g u r e 2.4: U n e q u a l i z e d s i g n a l constellation F i g . 2.5 shows pulses sent by a 2 5 6 - C A P transmitter. Severe ISI is i n t r o d u c e d when these pulses are distorted a n d start overlapping after passing t h r o u g h a channel. T h e performance analysis of b l i n d algorithms is more c o m p l i c a t e d t h a n for the L M S a l g o r i t h m . For the L M S a l g o r i t h m , the cost function used to u p d a t e the filter's tap coefficients is the same as that used to measure the mean-square error ( M S E ) , a n d is given by CF = MSE = E[e ] = E[(y 2 r>n T h e cost function i n (2.12) converges to zero when y n -» a . n - a)] 2 n n (2.12) I n practice, due to l i m i t a t i o n s caused by finite filter length, step sizes, etc, a n d the presence of additive noise i n the channel, the cost function i n (2.12) is not zero but assumes some s m a l l values. T h e L M S a l g o r i t h m c a n provide a n o p t i m u m solution i n terms of M S E . However, this is not necessarily the case for b l i n d algorithms. For example, i n one possible i m p l e m e n t a t i o n of M M A , w h i c h is discussed later, the cost function 32 F i g u r e 2.5: Impulse responses of s h a p i n g filters for 2 5 6 - C A P m i n i m i z e d by the filter's tap u p d a t i n g a l g o r i t h m for the in-phase tap coefficients is given by CF y where y n = E[4JCF)] = E[{yl - R)) 2 2 (2.13) is the in-phase o u t p u t sample of the equalizer. E v e n w h e n the equalizer converges, i.e. Vn -> o-n, we have CF y ^ 0. So that (2.13) becomes CF = E[(a - R ) } = C 2 a 2 n 2 (2.14) T h e stochastic gradient a l g o r i t h m w h i c h m i n i m i z e s the M S E i n (2.12) was p r e v i o u s l y given i n (2.10) a n d (2.11). T h e corresponding a l g o r i t h m w h i c h m i n i m i z e s the M M A cost function i n (2.13) w i l l be derived later (see equations (3.29) a n d (3.30). W e repeat here these a l g o r i t h m s as they are used 33 for the in-phase tap coefficients: c MSE : MMA : (2.15) n+1 = c„ - n(yl - R )y r,n 2 Cn+i D u r i n g final convergence, i.e., w h e n y n (2.16) n -> a , the correction t e r m for the L M S a l g o r i t h m i n (2.15) n goes to zero. A s a result, the tap coefficients settle to their o p t i m u m values w i t h very little tap fluctuations. T h e same is not true for the tap u p d a t i n g a l g o r i t h m i n (2.16). W h e n y n correction t e r m does not go to zero. A s a result, the tap coefficients keep o p t i m u m values. T h i s creates tap fluctuation fluctuating - » a , the n a r o u n d their noise at the output of the equalizer, a n d does not allow the M S E i n (2.12) to go to zero. T h e o n l y way to have the M S E go to zero w o u l d be to use a step size that goes to zero, i.e. fj, —> 0 i n (2.16). However, this m a y not be possible i n a finite-precision environment, a n d w o u l d not be desirable even i f enough precision were available, because the convergence time w o u l d be too long. A s the n u m b e r m of s y m b o l levels increases, the tap fluctuation noise i n t r o d u c e d by a b l i n d u p d a t i n g a l g o r i t h m becomes more a n d more significant w h e n compared to the spacing between adjacent symbols i n the signal constellation. A s a result, as m increases, it becomes more a n d more difficult to o p e n the eye. O u r investigation has shown that there is a direct c o r r e l a t i o n between the ease w i t h w h i c h the eye can be open a n d the m i n i m u m (residual) value of the cost function that is b e i n g m i n i m i z e d by the b l i n d a l g o r i t h m . T h e larger this m i n i m u m value, the more difficult it becomes to open the eye. A detailed s t u d y of the effect of the residual values of cost functions is given i n Section 4.1 a n d A p p e n d i x C , or i n [30]. In T a b l e 2.1, we list c o m p u t e d values for several C A P systems. W e see that the residual values of the cost functions increase w i t h increasing m. T h e r e s i d u a l value is about 14 d B for 1 6 - C A P , a n d increases to 52 d B for 1 0 2 4 - C A P . T h e above result has led to the proposal of the modified M M A algorithms, w h i c h are presented i n Chapters 4 a n d 5. T h e cost functions of these modified algorithms have residual values w h i c h are smallet t h a n the residual value of the cost function of the basic M M A a l g o r i t h m . A s a result, the modified M M A a l g o r i t h m s can be used w i t h denser signal constellations a r i d / o r provide faster i n i t i a l b l i n d convergence. 34 CF/CAP 4-CAP 16-CAP 64-CAP 256-CAP 1024-CAP m 1 2 4 8 16 0 14.2 27.7 40 52 CF an Table 2.1: M i n i m u m values of the M M A cost function 35 36 Chapter 3 MultiModulus Algorithm ( M M A ) T h e m a i n challenge i n the i m p l e m e n t a t i o n of b l i n d start-up is to provide a reliable convergence. R e l i a b l e convergence of the equalizer includes two features. O n e feature is the opening of the eye d i a g r a m , a n d the other one is avoiding w r o n g solutions. I n the overview of b l i n d algorithms, we w i l l see that b o t h R C A a n d C M A cannot guarantee b o t h features at the same time. T o meet the requirements for b l i n d equalization, we propose i n this chapter a n i m p r o v e d a l g o r i t h m , called M M A . E n h a n c e d versions of this a l g o r i t h m w i l l be discussed i n the next two chapters. T h e major a t t r i b u t e of M M A is the usage of m u l t i p l e m o d u l i , w h i c h provides more flexibility a n d leads to a n i m p r o v e d convergence. W e also show that M M A is a b l i n d a l g o r i t h m w h i c h can remove a l l ISI. A t the end of this chapter, M M A is analyzed a n d compared to R C A a n d M M A . 3.1 Overview of B l i n d Algorithms R C A a n d C M A are two different b l i n d algorithms. However, d u r i n g cost function m i n i m i z a t i o n , b o t h of t h e m employ constants w h i c h relate to the statistics of the symbols a n and b . The principle n of the two algorithms is i l l u s t r a t e d i n F i g . 3.1(a) and (b). F o r R C A , the cost function is defined w i t h respect to four points, as shown i n F i g . 3.1(a), a n d for C M A , the cost function is defined w i t h respect to a circle, as shown i n F i g . 3.1(b). T h e values of the constants w h i c h define the four points for R C A and the circle for C M A are functions of the statistics of the symbols a n and b. n b. CMA a. RCA c. MMA F i g u r e 3.1: Interpretation of the cost function used by three differrent b l i n d equalization 3.1.1 Reduced Constellation Algorithm ( R C A ) T h e first a l g o r i t h m considered i n the overview of b l i n d algorithms is R C A , w h i c h has the simplest i m p l e m e n t a t i o n [9]. Before discussing R C A we briefly revisit the L M S a l g o r i t h m , w h i c h is used i n the steady-state mode of operation. W i t h the L M S a l g o r i t h m , the cost function that is m i n i m i z e d is the M S E , where the error is c o m p u t e d by s u b t r a c t i n g the o u t p u t s of the slicer from its inputs. T h e M S E is expressed as MSE where Y n and A n = E[\E \ } E[\Y -A \ } 2 = 2 n n (3.1) n represent inputs a n d outputs of the slicer respectively. In (3.1), the complex quantities are defined i n the following way Yn = E JVn Y — A n = n y + n A = a + n n n e = n y n jb — n a n E n = e + je e = n n y n n — b n (3.2) (3-3) W i t h o u t ideal reference, many w r o n g decisions w o u l d be made at the slicers d u r i n g i n i t i a l convergence, a n d the equalizer w o u l d usually not converge w i t h the L M S a l g o r i t h m d u r i n g b l i n d start-up. 37 In this case, a b l i n d a l g o r i t h m is required to solve the p r o b l e m of m a k i n g w r o n g decisions. T h e key element i n b l i n d algorithms is the use of the statistics of the symbols A . Instead of using i n d i v i d u a l n symbols A n as reference, a b l i n d equalizer uses correction terms, w h i c h are derived w i t h respect to constants whose values are functions.of the statistics of the symbols A . B y a p p l y i n g such a technique, the p r o b a b i l i t y of w r o n g decisions c a n be significantly reduced. T h i s concept is now n demonstrated for R C A . W i t h the R C A a l g o r i t h m , the error used i n the t a p u p d a t i n g a l g o r i t h m is derived w i t h respect to a signal constellation that has a smaller number of points than the received constellation. A s i l l u s t r a t e d i n F i g . 3.1 (a), it is assumed that the o r i g i n a l signal constellation uses. 64 complex symbols. F o r the R C A a l g o r i t h m , the reduced constellation t y p i c a l l y consists of four signal points only. It s h o u l d be noted that the R C A a l g o r i t h m requires the use of a decision device to select the closest signal point from the reduced constellation. T h e error between the received sample Y a n d the closest signal point A n r<n E, = Y- r n n of the reduced constellation is the complex number A rtn = Y - R * sgn{Y ) n (3.4) n where the constant R is a statistical function of the symbols A , sgn(-) is the signum function, a n d n the subscript r indicates that the error is derived w i t h respect to a reduced constellation. Note that the expression Y — Rsgn(Y ) corresponds to the case where the reduced constellation consists n n of four points. T h e reduced constellation a l g o r i t h m m i n i m i z e s the following cost function CF = E[\Yn, - i , „ | ] = E[\Y -R*sgn(Y )\ } 2 r 2 r n n (3.5) A derivation for the value o f the constant R c a n be found i n A p p e n d i x B . T h e m a i n steps for c o m p u t i n g this constant are briefly repeated here. T h e constant R is c o m p u t e d under the c o n d i t i o n that the channel is perfectly equalized, that is, y -» a n and y n n -> b . U s i n g (2.10) a n d (2.11) i n n (3.5), we get the following expression for the gradient of the cost f u n c t i o n i n (3.5) w i t h respect to the complex t a p vector C n V ( C F ) = 2E[(Y - Rsgn(Y ))r } C Setting V c n n n (3.6) to zero a n d assuming perfect equalization, we get the following value for R E[\A \ ] E[\a \]+E[\b \} 2 R= n n 38 n (3.7) N o t e that the constant R is a statistical function of the symbols A a n d that it takes different n values for different constellations. N o w , consider the phase-splitting equalizer structure shown i n F i g . 2.1. U s i n g equations (2.7) a n d (3.5), the following equations result e ,n = Vnr a , = c£r - Rsgn{y ) r n e n n r>n =y - 6 n = dr T r > n n - Rsgn(y ) n (3.8) T h e gradients of the cost function i n equation (3.5) w i t h respect t o the tap vectors c„ a n d d are n equal to ' V ( C F ) = 2E[e r ] (3.9) V ( C T ) = 2E[e r ] (3.10) C rtn d r>n n n T h e nonaveraged gradients i n (3.9) a n d (3.10) c a n be used i n a stochastic gradient a l g o r i t h m to adapt the t a p coefficients of the equalizer, so that the following tap u p d a t i n g algorithms result c + i -c - ne r = c - fi[y - Rsgn(y )]r (3.11) i = d - ixe Tn = d„ - n[y - Rsgn(y )]r (3.12) n d n + n n r>n n n T>n n n n n n n where r is i n i t i a l i z e d w i t h zeros a n d c a n d d are i n i t i a l i z e d w i t h values corresponding to the i n phase a n d quadrature shaping filters. T h e above tap u p d a t i n g algorithms have been derived for the phase-splitting equalizer structure. O t h e r c o m m o n l y used equalizer structures are the cross-coupled a n d the four-filter F S L E structures shown i n F i g . 2.2. A detailed s t u d y o f the i m p l e m e n t a t i o n of R C A for these structures c a n be found i n [30]. For R C A , the cost function m i n i m i z a t i o n is done w i t h respect t o a reduced signal constellation that consists of four-points. Because o f the usage of the constant R, the p r o b a b i l i t y of m a k i n g w r o n g decisions ( i n a statistical sense) is significantly reduced, a n d this leads t o i n i t i a l equalizer convergence. After achieving i n i t i a l convergence w i t h R C A , the equalizer switches t o the L M S a l g o r i t h m t o o b t a i n steady-state convergence performance. O n e of the problems of R C A w h e n used w i t h the phase-splitting equalizer is that it c a n easily converge to w r o n g solutions. T h e most c o m m o n l y observed w r o n g s o l u t i o n is the diagonal solution, w h i c h is obtained when the in-phase a n d quadrature filter synthesize the same transfer function. 39 T h e result is that the o u t p u t s of the two filters are the same a n d the signal constellation becomes a diagonal, as shown i n F i g . 3.2. F i g u r e 3.2: D i a g o n a l solution for 6 4 - C A P 3.1.2 Constant Modulus Algorithm ( C M A ) T h i s section provides a general overview of the C M A a l g o r i t h m [9] [11]. minimizes the dispersion of the equalizer's output samples Y n R. T h i s is graphically illustrated i n F i g . 3.1(b). T h e C M A algorithm w i t h respect to a circle w i t h radius U n l i k e R C A , w h i c h uses second-order statistics only, C M A has a generalized form w h i c h uses higher-order statistics of the equalizer's output signals. T h e C M A a l g o r i t h m minimizes the following cost function: CF = E[{\Y \ -R ) ) L n 1 2 (3.13) where L is a positive integer. W i t h C M A , a true two-dimensional cost function is used to m i n i m i z e the dispersion of the complex o u t p u t s Y n w i t h respect to a two-dimensional contour. A value L = 2 40 10 8 4 6 4 > Lt < § < A 2 ? * t v «• >; Jr- » * 'f ** 0 iv ^ 1 ~*. -:. f # 4r • * y * * * v: $ -A. * .* * * •«» *i ••% r: 4? *t ~~ - 2 •At -4 i. >f. s> * s». •»• *»• * ** .-fe. »; .r^- -p. t *; V* '.V -6 -8 -10 -10 -5 0 REAL 5 10 F i g u r e 3.3: 144-point s o l u t i o n for 1 2 8 - C A P is c o m m o n l y used i n practice, so that the cost function i n (3.13) becomes CF = E[(\Y \'- R ) } 2 2 (3-14) n Now, consider the phase-splitting equalizer structure i n F i g . 2.1. U s i n g (2.7), the gradients of the cost function i n (3.14) w i t h respect to the t a p vectors c a n d d„ are given b y n V ( C F ) = E[(\Y f - R )y r } V ( C F ) = E[(\Y \ - R )y r ] z C n n 2 n d 2 n n (3.15) n S e t t i n g the gradients to zero a n d assuming a perfectly equalized channel we get the following value for R? E[\A \ } E[\A \ } 4 R = l n (3.16) 2 n T h i s expression holds for the usual case where the statistics of the symbols a n a n d b are the same. n For L = 2, we have the following stochastic gradient tap u p d a t i n g algorithms Cn+i = - n(\Y \ 2 c n n d +i = d„ - n(\Y \ ~ 2 n n 41 R )y r n (3.17) R )y rn (3.18) 2 n 2 n C M A differs from R C A i n several respects. R C A only uses knowledge of second-order statistics of the signals, whereas C M A can use higher-order statistics. It is not p r a c t i c a l to use statistics w h i c h are higher t h a n the fourth-order statistics, because of trade-off considerations between cost and performance. F o r C M A , the i n i t i a l d y n a m i c behavior is an increasing function of the order of the statistics b e i n g used. However, the c o m p u t a t i o n of the equalizer coefficients q u i c k l y becomes unmanageable i n (3.17) a n d (3.18) w h e n L increases. I n a d i g i t a l i m p l e m e n t a t i o n , a processor based receiver w i t h finite coefficient precision w o u l d suffer precision a n d overflow problems [11]. In this thesis, we always assume the usage of the fourth-order C M A a l g o r i t h m w i t h L = 2 i n (3.13). A n o t h e r difference between the two algorithms is the error contour used for the cost function. T h e cost function m i n i m i z a t i o n of R C A refers to a four-point constellation, whereas i n C M A , the m i n i m i z a t i o n refers to a circle. E v e n t h o u g h the cost function of R C A is defined i n two dimensions, it can equally well be defined as two separate cost functions i n one d i m e n s i o n . However, C M A uses a true two-dimensional cost function, w h i c h makes the two channels dependent. linear phase offset cannot be done because of the following reasons. complex tap vector C„ by a n angle 9, i.e. C also rotate the complex output sample Y n E q u a l i z a t i o n of A s s u m e that we rotate the ->• C e . It is easily verified from (2.7) that this w i l l j e n n of the equalizer by a n angle 0, i.e. Y —> Y e^ . U s i n g 9 n n this rotated o u t p u t i n the C M A cost function i n (3.14) we get CF(9) = E[(\Y e> \ - R ) } = E[(\Y \ - R ) ) e 2 2 2 2 n T h u s , r o t a t i n g the c o m p l e x tap vector C n 2 2 n (3.19) does not change the value of the cost function, i n c l u d i n g its m i n i m u m value. A n y rotated version of a tap vector C n that m i n i m i z e s the C M A cost function also provides a m i n i m u m of this cost function. A s a result, even t h o u g h C M A can open the eye, it generally w i l l generate a rotated signal constellation at the output of the equalizer, as shown i n F i g . 3.4 a n d F i g . 3.5. T h i s undesirable feature of C M A is a direct consequence of the cost function that is used, a n d does not depend o n the equalizer structure under consideration. In p r a c t i c a l applications where C M A is used, the equalizer is followed by a n adaptive rotator, w h i c h repositions the signal constellation i n the right place. T h e phase of s i g n a l constellation is 42 10 1 1 I? 8 6 4 > 2 ».v < §< o * ~ *Vff. \V . * -2 v# -4 -6 jit -8 -10 -10 -5 0 REAL 5 10 Figure 3.4: 45 degree rotation computed as c ^ = , 7m{y„*^„} \A>\ r E [ 1 ] (3.20) Then the gradient descent algorithm can be used to update filter taps 0n+i = An - l^e (3.21) The rotator must also be used in the steady-state mode of operation, which is undesirable for the applications considered here, because it increases the steady-state complexity and power dissipation of the receiver. 3.2 M M A Through the overview of blind algorithms, we have seen the problems associated with R C A and CMA. RCA is simple but not very reliable, and especially prone to creating diagonal solutions. The use of C M A can avoid diagonal solutions, but C M A cannot complete an entire equalization and requires additional functions, which makes it more expensive. M M A is proposed as an improved 43 10 8 6 4 > 2 GC < < 0 2 -2 -4 -6 -8h -5 0 5 REAL 10 Figure 3.5: 15 degree rotation blind algorithm to overcome the problems created by RCA and C M A [29]. It is more reliable than RCA and does not require the additional complexity needed by C M A for steady-state operation. The main feature of M M A is the use of multiple moduli, which makes it very flexible and easily adaptable to nonsquare constellations and to large constellations. The algorithm using multiple moduli for large constellations is called generalized M M A , and this algorithm will be studied in the following chapter. In this section, we study the M M A algorithm's use of multiple moduli for nonsquare constellations. In the following, we first describe the usage of M M A for square constellations such as 64-CAP, and then for nonsquare constellations such as 128-CAP, for which multiple moduli are used to accommodate the nonuniform distribution of equalizer output samples. 3.2.1 Square Constellations The main feature of M M A is that it minimizes the dispersion of the equalizer's output samples around multiple piecewise linear moduli. All possible usages of moduli can be summarized in one general expression, which is CF = E[{&- R (y f L n 44 + (j£ - R^y f] n (3.22) where L is a positive integer, and R{y ) and R{y ) are output-sample-dependent constants. The n n values of R(y ) and R{y ) are determined by the region in the complex plane in which the equalizer n n outputs y and y are located. In comparison to CMA, n MMA makes two changes. One change is n made by treating the two dimensions separately. The other change is the usage of multiple moduli, that is, R is a function of the distribution of the equalizer's outputs y and y . The two changes n n make MMA behave differently from CMA. We first study MMA for square constellations, which is the simplest form of MMA. For square constellations, R(y ) = R{y ) = R = constant, so that the cost function in (3.22) becomes n n CF = CF + CF = E[(y% - R ) } + E[(y% - R ) } L T 2 L (3.23) 2 Q Equation (3.23) includes two cost functions. Unlike CMA, this is not a true two-dimensional cost function. Rather, the cost function CF in (3.23) is the sum of two one-dimensional cost functions CFi and CFQ. Graphically, the moduli of MMA for square constellations are given by two straight lines along each dimension, as shown in Fig. 3.1(c). For the phase-splitting equalizer structure shown in Fig. 2.1, the gradients of the cost function in (3.23) with respect to the tap vectors c and d are equal to n n V (CF) = 2L * E[(y^ - R ) \y \ - y r ] (3.24) = 2L * E[(yj; - R ) \yn\ - y r } (3.25) C V (CF) d L 2 L 2 n L n 2 L n 2 n n Assuming a perfectly equalized channel, i.e. y —• a and y -> 6 , and setting the gradients to n n n n zero the following value for the constant R is obtained L , L _ E[a ] E[tf] 2 L n E[\a \L] E[\b \ n n Due to the use of the independent cost functions and because the symbols a and b are assumed n n to have the same statistics, the constant R can be derived from either CFj or CFQ. For the general form of MMA in (3.23), the following stochastic gradient tap updating algorithms apply c d n + 1 n + 1 = c„ - M(y£ = d„ - (3.27) R )\yn\ - y r L L 2 n n - R )\y \ - y r L L n 45 2 n n (3-28) T h e best compromise between cost a n d performance is achieved w i t h L = 2, i n w h i c h case the tap u p d a t i n g algorithms become Cn+l c n ~ Hit/I ~ R )Vnr,n (3.29) n (3.30) 2 d +i n where the constant R is c o m p u t e d as E[a ] (3.31) n In this section, the M M A tap u p d a t i n g algorithms have been derived for the phase-splitting equalizer structure. T h e corresponding algorithms for the cross-coupled a n d four-filter F S L E structures c a n be found i n [29]. A l t h o u g h C M A a n d M M A have s i m i l a r a l g o r i t h m i c structures, they p e r f o r m different functions. Because the cost functions for M M A operate i n separate dimensions, M M A c a n a c c o m p l i s h complete equalization, w h i l e C M A c a n o n l y do it p a r t i a l l y . 3.2.2 Nonsquare Constellations T h e use of one constant R is the simplest a p p l i c a t i o n of M M A . T h e use of m u l t i p l e m o d u l i for nonsquare constellations is considered as the first extension of M M A . I n this case, m u l t i p l e m o d u l i are used w h e n a n o n u n i f o r m s y m b o l d i s t r i b u t i o n occurs across each d i m e n s i o n , as shown i n F i g . 3.6. For nonsquare constellations, R is not a constant, instead, m u l t i p l e m o d u l i R are required because the o u t p u t samples y n and y n have different d i s t r i b u t i o n s d e p e n d i n g o n their values. I n the case of nonsquare constellations, the signal constellation is designed i n such a way that the discrete levels for the symbols a n a n d 6 do not have the same p r o b a b i l i t y of occurence. F o r instance, for 1 2 8 - C A P n we have a number of s y m b o l levels m = 6. However, these levels are d i v i d e d into two subsets, w h i c h are a ^\ = { ± 1 , ± 3 , ± ' 5 , ± 7 } , a n d a ^ n n = {±7,±9}. T h e two subsets of s y m b o l s have a different p r o b a b i l i t y of occurence, as shown i n F i g . 3.6. If one constant R is used for a l l the symbols, the knowledge of the s y m b o l statistics is not p r o p e r l y used, a n d the equalizer m a y converge to w r o n g solutions. O n e w r o n g s o l u t i o n is called the 144-point s o l u t i o n [29], w h i c h occurs w h e n the in-phase a n d q u a d r a t u r e filters converge to i m p u l s e responses w h i c h are offset by a s y m b o l p e r i o d . 46 Q Q FL FL R< a. Moduli for In-Phase Dimension b. Moduli for Quadrature Phase Dimension Q c. Moduli for Both Dimensions F i g u r e 3.6: M M A m o d u l i for 128-point signal constellation 47 T h e M M A cost function for nonsquare constellations m i n i m i z e s the dispersion of the equalizer's o u t p u t samples y n and y n w i t h respect to piecewise straight lines. Because there are two subsets of symbols, we need two constants R to provide efficient statistical d e s c r i p t i o n of the symbols a. n A s shown i n F i g . 3.6, the two constants R are represented by two straight lines. T h e cost functions are given by the piecewise nonlinear functions CFj = E[(yZ - R[) ] 2 CF = E[(y^ - R[) } 2 Q if \y \<K CFi = E[(y^ - R%) ] if \y \ > K (3.32) if \y \<K C'F = E[{y^ - R%) ) if \y \ > K (3.33) n 2 2 n Q n n (3.34) where K refers to the b o u n d a r y separating the two sets of symbols. T h e use o f m u l t i p l e m o d u l i i n M M A for nonsquare constellations is i l l u s t r a t e d i n F i g . 3.6. T h i s figure shows a 1 2 8 - C A P signal constellation, for w h i c h blocks of seven bits are m a p p e d into 2 = 128 c o m p l e x symbols. B y using 7 the 12 s y m b o l levels ( ± 1 , ± 3 , ± 5 , ± 7 , ± 9 , ± 1 1 } we can define 12 x 12 = 144 complex symbols, so that 144-128=16 points are redundant a n d c a n be e l i m i n a t e d . F o r t y p i c a l applications where 1 2 8 - C A P is used, the four outer points i n each quadrant are e l i m i n a t e d . T h i s reduces the peakpower-to-average-power ratio of the C A P signal, w h i c h is always a desirable feature i n practice. For the 1 2 8 - C A P constellation shown i n F i g . 3.6, a p r o b a b i l i t y o f two-thirds is used for s y m b o l set one, \y \ < K. T h e n K is calculated as n 2 K = - * 2m (3.35) o where m indicates the number o f s y m b o l levels of C - C A P a n d C refers to the number o f constellation points. K = 8 is o b t a i n e d for 1 2 8 - C A P . It means that s y m b o l set one has s i x s y m b o l levels for y n Vn < 8, a n d s y m b o l set two has four s y m b o l levels for > 8. In the following, the c a l c u l a t i o n o f the moments of the symbols a is i l l u s t r a t e d for 1 2 8 - C A P . T h e n c o m p u t a t i o n o f the moments o f symbols is considered i n one quadrant for the in-phase d i m e n s i o n . 48 Let us define s y m b o l set one for y < K and s y m b o l set two for the rest. T h e p r o b a b i l i t y P\ for n s y m b o l set one is c o m p u t e d as * = £ * ™ = ^ (3-37) a n d P2 for each s y m b o l i n set two is c o m p u t e d as 4 P 2 = 2m 1 C * l ~ * m = , 8 ( 3 ' 3 8 ) T h e m o d u l i R\ and R2 for nonsquare constellation are c o m p u t e d from equation 3.26 by evalua t i n g the moments of the symbols over the set of s y m b o l levels to w h i c h a given m o d u l u s applies (illustrated below). A s an example, consider F i g . 3.6, w h i c h shows the m o d u l i for the d i m e n s i o n and w h i c h applies to the real symbols a n in-phase of a 1 2 8 - C A P signal constellation. T h e mo- ments of the symbols c a n be c o m p u t e d by considering the first quadrant only. Consider the subset of 24 symbols i n this quadrant w h i c h applies to R\. b n = 1,3,5,7. So that each value of a n subset has 8 symbols for w h i c h a n For these symbols a n = 1,3,, 5 , 7 , 9 , 1 1 a n d occurs w i t h p r o b a b i l i t y 4/24 = 1/6. = 1,3,5,7 and b n Similarly, the R2 = 9,11, so that each value of a n occurs w i t h p r o b a b i l i t y 2/8 = 1/4. T h u s , the variance of the symbols becomes [ l] = E a E[a ] = 2 n ^ ( l + 3 + 5 + 7 + 9 + l l ) ^47.67 2 2 2 2 2 2 fori?! | ( 1 + 3 + 5 + 7 ) = 21 for R 2 2 2 2 2 (3.39) (3.40) O t h e r moments for the symbols are c o m p u t e d i n a s i m i l a r fashion. T h e two m o d u l i are given by Ri = 9.2 and R2 — 6.1" for 1 2 8 - C A P . T h e p r o b a b i l i t y of converging to a wrong 144-point solution is significantly reduced by using two m o d u l i for nonsquare constellations. Because of the use of m u l t i p l e m o d u l i , the constants R can provide adequate knowledge of the statistics of the s y m b o l d i s t r i b u t i o n . T h e number of constants R is equal to the number of s y m b o l sets h a v i n g different statistics. 3.2.3 ISI Optimization In this section it is shown that m i n i m i z a t i o n of the M M A cost function removes ISI at the o u t p u t of the equalizer. 49 bits encode shaping filter linear distortion transmitter s decision device FSLE channel h decoder receiver c Figure 3.7: Communication link where a is the vector of in-phase symbols and the vector w denotes the vector of symbol-spaced n samples of the overall impulse response of the transmission link w = s ®h ®c n n (3.42) n The input and channel vectors an and w are defined as follows a£ = [a ,... ,a ,... ,a fc_Af] (3.43) w = [w ,wi,...,w ] (3.44) T n+fc n 0 n+ N where N + 1 is the number of samples. With a perfectly equalized channel and no ISI at the input of the slicer, the channel vector w has only one nonzero entry equal to one and can be written as: w^ = [0,...,0,l,0,...,0] ^ v fc 50 ' (3.45) bits where k indicates the channel a n d equalizer delay expressed i n s y m b o l periods. It is easily verified from (3.43) a n d (3.45) that Vn = w f a [ = a (3.46) n So that the equalizer's o u t p u t is indeed ISI free. U s i n g (3.41), the second order e x p e c t a t i o n of the sample y n is E[y ] = £ [ w a w 2 T n n r ] - £[w a a Tw] = w £[ T a r i T n n aTl a£]w (3.47) W i t h the usual a s s u m p t i o n that different symbols are uncorrelated we get E[a £] nB = E[a ]*I 2 (3.48) n where I is the u n i t y d i a g o n a l m a t r i x , so that N E[y ] = £ [ a ] w w = E[a ] £ w 2 r 2 n 2 n (3.49) fc=0 In order to show that m i n i m i z a t i o n of the cost function results i n zero ISI, we can show that E[(yl - R)} 2 2 > E[{al - R)] 2 2 (3.50) and that the m i n i m u m is achieved w h e n the channel vector w satisfies (3.45). W e now provide two such proofs, one for a constrained p r o b l e m a n d one for a nonconstrained p r o b l e m . A result w h i c h w i l l be useful i n the following analysis is: £> ) >£^ 2 i 2 4 i -> QL>) = 22 i £ ™ i + * (3.51) i E q u a l i t y i n (3.51) holds i f a n d only i f one of the terms Wi is nonzero a n d a l l the other terms are zero. ( E q u a l i t y also holds for the t r i v i a l case where a l l the terms IO, are zero.) Constrained problem In this scenario, we" assume that the channel vector w c a n be w r i t t e n as w T — [x,...,x, 1,x,... ,x] (3.52) T h a t is, one of the entries of the vector is constrained to r e m a i n equal to one, a n d the other entries can take any value. T h i s a s s u m p t i o n is a good a p p r o x i m a t i o n of what is done i n practice w h e n 51 the gain of the A G C a n d the i n i t i a l values of the equalizer are p r o p e r l y chosen. It is easily verified that, w i t h the constraint i n (3.52) the following holds: N E^^ (- ) 1 3 53 k=0 and the equal sign holds i f and only i f the channel vector satisfies the ISI free c o n d i t i o n i n (3.45). T h e c o n d i t i o n i n (3.50) can be w r i t t e n as E[y } - 2E[y }R + R > E[a ] - 2E[a ]R 4 2 n 2 4 2 n n E[y ] - 2E[y ]R 4 2 2 n 2 n + R 4 > E{a ) - 2E[a ]R 4 2 n (3.54) (3.55) 2 n R e p l a c i n g R b y its value a n d using (3.49) i n (3.55), we c a n further simplify the equation to E[y }>E[a }(2j2™l-V 4 (3-56) 4 n k F r o m the inequality i n (3.53), we then have E[y } = E[a }[2J2^l-l}>E[a } 4 4 (3.57) 4 l n k a n d equality c a n only h o l d i f the channel vector satisfies the ISI free c o n d i t i o n i n (3.45). Unconstrained problem We now remove the constraint i n (3.52) of keeping one entry of the channel vector equal to one. U s i n g results given i n [25], it is possible to show that K(y ) = E[y ] — 3E [y ] K(a ) = K(a )J2^k n n 4 2 • 2 (3.58) (3.59)' n k where K(y ) n a n d K(a ) n are called the kurtosis of the equalizer o u t p u t samples a n d symbols, respectively. W e c a n use (3.49) a n d (3.59) to solve for E[y ] i n (3.59) a n d we get: 4 E[y ) = E[a ]^w 4 4 4 n - ZE \a \^ 2 2 n - 4 W k (3-60) U s i n g (3.51) o n the right i n (3.60) we get: E[y } = E[a }Y,wi 4 n 52 + 36E [a } 2 2 n (3.61) R e p l a c i n g R by its value a n d using (3.59), the 1-D cost function o f M M A i n (3.23) c a n be w r i t t e n as E[(y - R ) } = E[y ] - 2E[a ] £ 2 2 w +R 2 n n 2 n (3.62) 4 k U s i n g (3.61) i n (3.62), we get E[(y - R ) ) 2 2 = 2 n E[a*] + 3SE [a ] - 2E[a ] £ 2 n k E[a ][J2wt-2Y;™l} Replacing Ylk t m t n e 2 (3.64) 2 n k above equation b y its value o n the right i n (3.51), we have E[(y -R ) } 2 + Z5E [a ]+R* n k w (3.63) 2 n k = w 2 2 2 n = E[a ][(Y w ) -2Y -8] = E[a }[(£w -l)-l-5) 2 n i 2 + 36E {a } + R 2 k 2 /W k 2 (3.65) 4 n k + UE [a ] + R 2 2 n 2 (3.66) i n k = E[4][(£ w -l)-l}- 5[E[a ] - 3E [a }} + R 2 2 k n 2 (3.67) 4 n it F r o m (3.67) we conclude that the following holds: E[(y - R ) } > -E[a ) + R = E[(a - R ) } (3.68) ($2wl - l ) > 0 (3.69) 2 2 2 4 n 2 n 2 2 n if and 2 E[a ] - 3E [a ] < 0 2 n 2 n k T h e left c o n d i t i o n is always true. T h e right c o n d i t i o n says that the kurtosis of the symbols has to be always negative. E q u a l i t y c a n o n l y h o l d i f £fc w\ = 1 a n d S = 0 i n (3.67). F r o m (3.51), this implies that o n l y one Wk c a n b e nonzero a n d J^k w w = 1 implies t h a t t h e nonzero t e r m has to b e one, so that the channel vector w has t o have the ISI-free form given i n (3.45) T o show that the kurtosis of the s y m b o l s used i n t y p i c a l signal constellation is always negative we can use the results obtained i n A p p e n d i x B . T h e second a n d fourth-order moments of the symbols are obtained from (0.23), (0.25) a n d (0.26), a n d we get K(a ) n = ^]-3 B [a ] = ^(4m -l)(12m -7)-3*l(4m -l) = -^-(4m -l)[12m -7-5(4m -l)] 15 (3.71) = --^(4m -l)(4m 15 (3.72) 2 2 2 2 J 2 2 2 2 2 + l) 53 2 2 (3.70) It is obvious that the values i n the brackets are always larger t h a n zero for m > 1. A s a result K{a ) < 0 n for m > 1 (3.73) a n d this completes the p r o o f that m i n i m i z a t i o n of the M M A cost function leads to ISI free output samples of the equalizer. 3.3 Comparison of the Three Algorithms So far, three different b l i n d equalization a l g o r i t h m s have been studied. T h e preference for each of t h e m depends on the a p p l i c a t i o n . I n this section, the algorithms are a n a l y z e d a n d compared i n terms of convergence, reliability a n d complexity. Algorithmic structures F i r s t of a l l , we s t u d y the r e l a t i o n between the three algorithms. F o r convenience, the cost functions of the three algorithms are repeated as follows. MSE = E[\Y -A \ ] CF = E[\Y -Rsgn(Y )\ ] = E[(\Y \ -R ) ] rca CF cma CFmma = (3.74) 2 n n 2 (3.75) n n 2 2 2 n E[(yl - R ) 2 = E[(y 2 y -R ) } 2 n + 2 2 (3.76) n + (y - R ) } 2 2 2 2 (3.77) n where we have also i n c l u d e d the M S E , w h i c h is the cost function for the L M S a l g o r i t h m . N o t e that the M S E a n d the cost function for R C A use second-order statistics of the samples Y n a n d the other two use fourth-order statistics. T h e tap u p d a t i n g algorithms are o b t a i n e d by t a k i n g the gradient of the cost functions w i t h respect to the tap coefficients, a n d t h e n u s i n g the nonaveraged gradients i n a stochastic gradient algorithm. F o r the phase-splitting equalizer, a l l the tap u p d a t i n g algorithms for the in-phase coefficients, for example, have the following generic form: Cn+i = c where c n is the in-phase tap vector, r n n - fj,k r n (3.78) n is the vector of A / D samples, a n d k t e r m , w h i c h is correlated w i t h the vector r n n is a correction of A / D samples a n d is different for each a l g o r i t h m . 54 Specifically, we have LMS : k = y -a RCA : k = y - Rsgn(y ) (3.80) CMA : k = (y + y -R )y (3.81) MMA : k = (y - R )y (3.82) n n n (3.79) n n n 2 n 2 n 2 n 2 n n 2 n n T h e cost function for R C A a n d the L M S a l g o r i t h m are the same, except t h a t the sliced outputs a n = Rsgn(y ) are o b t a i n e d w i t h a four-point slicer. Otherwise, the i m p l e m e n t a t i o n o f the two n algorithms is identical. T h i s makes R C A easy to i m p l e m e n t a n d easy to analyze, a n d explains w h y R C A is w i d e l y used i n p r a c t i c a l applications. It is interesting t o note that C M A a n d M M A are identical for one-dimensional transmission schemes. F o r example, assume that we only have the in-phase d i m e n s i o n so t h a t y n i n (3.76) a n d (3.77) is zero. W e t h e n have for b o t h cases CF! = E[(y - R ) } 2 2 (3.83) 2 n W e see that the cost functions of C M A a n d M M A are i d e n t i c a l under c e r t a i n c o n d i t i o n s . T h e two algorithms have the same s t a t i s t i c a l orders a n d the same a l g o r i t h m i c structures. E x c e p t for linear channel phase e q u a l i z a t i o n , the two algorithms c a n achieve the same performance. T h e major difference between C M A a n d M M A is the way they use the c o m p l e x samples Y = n Vn+jy-n- C M A treats the samples y a n d y as one c o m p l e x sample Y . T h i s leads to the following n n n result CF (9) cma N o t e that the cost function CF cma , CF (9) mma = E[\Y e> \ - R ] = E[\Y \ - R ] 0 2 2 2 n (3.84) 2 n is independent of 9. T h e cost function of M M A is given by = E[(y c o s 9 - R ) 2 2 2 n 2 + (y s i n 9 - R ) } 2 2 Note that i n t h e above equation, the cost function CF n mma 2 2 (3.85) is a function o f 9. C M A is able t o converge to a n y rotated version o f the signal constellations. I n contrast, for M M A , only one 9 m i n i m i z e s the cost function. Therefore, w i t h M M A , ISI e q u a l i z a t i o n a n d phase recovery can be done jointly, a n d the a d d i t i o n a l rotator is not required t o tune the constellation t o its final position. 55 In summary, even t h o u g h C M A a n d M M A are somewhat s i m i l a r , they 'produce completely different results. Moreover, they associate w i t h different problems. T h e use of C M A is expensive because a rotator is required after the equalizer i n steady-state operation. However, C M A is attractive because of its a b i l i t y to converge w i t h o u t creating d i a g o n a l solutions. P a r t i c u l a r l y , i n the case of the phase-splitting equalizer structure, the two filters converge independently w i t h o u t any c o u p l i n g between the two channels. I n this case, the p o s s i b i l i t y of creating diagonal solutions exists for any a l g o r i t h m that simultaneously equalizes magnitude, phase, a n d phase offset as well. T h e c a l c u l a t i o n of R c a n be found i n A p p e n d i x B . T h e values of the constants R for the three algorithms are listed i n T a b l e 3.1 for square a n d nonsquare C A P applications. Algorithm/CAP 4-CAP 16-CAP 32-CAP 64-CAP 128-CAP 256-CAP 512-CAP 1024-CAP RCA 1 2.50 3.64 5.25 7.45 10.63 15.00 21.31 MMA 1 2.86 4.32 6.08 8.88 12.34 17.87 24.76 CMA 1.414 3.63 5.11 7.62 10.49 15.39 21.11 30.9 M M A #1 - - 4.49 - 9.22 - 18.55 - MMA - - 2.86 - 6.08 - 12.34 - R 2 T a b l e 3.1: C o n s t a n t R for s y m b o l levels ± 1 , ± 3 , . . ' . , ± 2 m — 1 N o t e that R r c a < i? m m a < Rcma- It shows that the constant i i is larger for the second-order a l g o r i t h m R C A t h a n those of the fourth-order algorithms of M M A a n d C M A , a n d R is larger for the two-dimensional a l g o r i t h m C M A t h a n that of one-dimensional one M M A . 3.4 Summary of Results T h e investigation of the three algorithms shows that each a l g o r i t h m has its advantages a n d disadvantages. T h e major attributes of each a l g o r i t h m can be s u m m a r i z e d as follows. T h e major a t t r a c t i o n of R C A is its s i m p l i c i t y a n d ease of i m p l e m e n t a t i o n . Its i m p l e m e n t a t i o n is the same as that of the L M S a l g o r i t h m . However, good performance is difficult to o b t a i n because 56 of the l i m i t a t i o n s that result from the usage of second-order statistics only. T h e r e l i a b i l i t y is p o o r and the p r o b a b i l i t y of creating diagonal solutions is the highest a m o n g the three algorithms. T h e advantages of C M A are its robustness a n d reliability, p a r t i c u l a r l y to d i a g o n a l solutions. T h e m a i n disadvantage of C M A is its complexity. W i t h C M A , equalization can o n l y be p a r t i a l l y done, and a rotator is needed to complete the whole equalization, w h i c h significantly increases the cost of i m p l e m e n t a t i o n for steady-state operation. It s h o u l d be p o i n t e d out, however, that there are some applications, such as voiceband and cable modems, where r o t a t i o n of the constellation is required anyway for other purposes, such as t r a c k i n g frequency offset i n t r o d u c e d i n the channel. I n this case, the need to do r o t a t i o n does not increase the cost of i m p l e m e n t a t i o n , a n d C M A becomes a very attractive approach. M M A is a new b l i n d e q u a l i z a t i o n a l g o r i t h m that was first proposed i n [29] [30]. It is a two-dimensional a l g o r i t h m that can be considered to be a s u p e r p o s i t i o n of two independent one-dimensional algorithms s i m i l a r to C M A . It uses high-order statistics so that it has a fast convergence rate, a n d it is more i m m u n e to d i a g o n a l solutions t h a n R C A . However, when magnitude a n d phase offset equalization are done at once, the p o s s i b i l i t y of occasionally converging to a diagonal s o l u t i o n s t i l l exits. Solutions to help i n these situations are discussed i n related work [30]. O n e of the major advantages of M M A over b o t h R C A a n d C M A is its flexibility. Because M M A can easily use m u l t i p l e m o d u l i , w h i c h is difficult to do w i t h R C A a n d C M A , it can be adapted to applications for w h i c h R C A a n d C M A are not very effective. O n e example, presented i n this chapter, is the case of nonsquare constellation. A n o t h e r example, discussed i n the next chapter, is that of very dense signal constellation. T h e characteristics of the three algorithms are s u m m a r i z e d i n Table. 3.2. W e see that none of the algorithms has a l l the desirable features. B y using M M A , we can o b t a i n adequate reliable a n d fast convergence at relatively low cost. 57 Algorithm Reliability Complexity Convergence rate* Flexibility RCA low low second fastest low MMA high medium fastest very h i g h CMA very h i g h high slowest low * For the A T M L A N a p p l i c a t i o n . T a b l e 3.2: Characteristics of the b l i n d e q u a l i z a t i o n algorithms T a b l e 3.2: Characteristics o f the b l i n d equalization algorithms 58 59 Chapter 4 Generalized M M A (GMMA) O n e aspect of the flexibility p r o v i d e d by M M A was demonstrated i n the previous chapter, where it was shown how it can easily be modified to accommodate nonsquare signal constellations a n d take advantage of the fact that these constellations have subsets of s y m b o l levels w i t h different statistics. These modifications facilitate the eye o p e n i n g of nonsquare constellations a n d greatly decrease the p r o b a b i l i t y of converging to w r o n g solutions, especially the 144-point s o l u t i o n for 1 2 8 - C A P . B o t h R C A a n d C M A cannot easily be modified to accommodate nonsquare constellation a n d get s i m i l a r benefits. A n o t h e r aspect of the flexibility p r o v i d e d by M M A is demonstrated i n this chapter, where we show how it can be modified to ease the eye opening of signal constellations w i t h a very large number of s y m b o l levels. T h i s is achieved by d i v i d i n g the complex plane of in-phase a n d quadrature output samples of the equalizer into several disjoint regions, w h i c h a l l have their o w n cost functions a n d m o d u l i . T h i s modified M M A a l g o r i t h m is called generalized M M A (GMMA). G M M A can open the eye of very large signal constellations for w h i c h R C A , C M A a n d standard M M A w o u l d not be effective. T h i s is demonstrated by the analysis given i n A p p e n d i x C , where the relationship between the M S E a n d the m i n i m u m value of the s t a n d a r d M M A cost function is discussed. G M M A can handle very large signal constellations because the residual values of the cost functions obtained w i t h G M M A c a n be made m u c h smaller t h a n the residual values obtained w i t h the other algorithms. T h e definition of the various subsets of equalizer output samples a n d corresponding m o d u l i used by G M M A is not straightforward, a n d has to be made carefully i f one wants to get the benefits p r o v i d e d by this a l g o r i t h m . T o address this p r o b l e m , we present here a n iterative a l g o r i t h m , w h i c h uses a n equal energy type of p r i n c i p l e a n d leads to the definition of n e a r - o p t i m u m subsets of equalizer output samples a n d corresponding m o d u l i . 4.1 Cost Function Analysis T h e study of cost functions is essential to the understanding of the convergence of a b l i n d equalizer. Cost functions for b l i n d algorithms behave differently from that of the s t a n d a r d L M S a l g o r i t h m . For the standard L M S a l g o r i t h m , the cost function m i n i m i z e s the error e n o u t p u t signals Y and a n u n k n o w n sequence of t r a n s m i t t e d symbols A n CF where Y n = E[(Y - = y +jyn, and e n(LMS) Tt A)] n = E[(y 2 n n - and A n n a) 2 n a +jb - = n n + [(y - n b)] 2 n between the equalizer's n = E[e {LMS) + e 2 n 2 n (LMS)] W h e n a t r a i n i n g sequence is available, the errors (4.1) e {LMS) r>n can be calculated i n a meaningful way from the equalizer's outputs. In this case, we say that channel equalization is done w i t h ideal reference. the u n k n o w n i n p u t s a n and b n However, w i t h o u t ideal reference, have to be decided at the slicers [30]. Initially, w i t h this approach, a b l i n d equalizer makes too many w r o n g decisions because the signals are severely corrupted by i n t e r s y m b o l interference (ISI). F o r severe ISI channels, a b l i n d equalizer cannot converge i f the L M S a l g o r i t h m is used at the b e g i n n i n g of start-up. In order to reduce the p r o b a b i l i t y of m a k i n g w r o n g decisions, several b l i n d algorithms are proposed to make a n equalizer converge d u r i n g b l i n d start-up [30]. I n the case of M M A , the cost function m i n i m i z e s the dispersion of the constellation a r o u n d linear contours, a n d it is given by CF = E[(yl - R) 2 2 + (y - R ) ] 2 2 2 = £[e 2 n (CF) + e 2 n (CF)] (4.2) where the constant R is given by " *RJ (4 ' 3) C o m p a r i n g the two cost functions i n (4.1) a n d (4.2), we can see that errors have different interpretations for the L M S a l g o r i t h m a n d M M A . T h e difference can also be visualized i n F i g . 4.1 where 60 the errors filter e , (LMS) T n e , (CF) are shown. I n the L M S a l g o r i t h m , the error for the in-phase and T n e ^ (LMS) is defined as r n e r > n ( L M 5 ) =y - a n (4.4) n Q e.J(CF) J . y n -7_ -5 -3 -1 1 * -(2m-1)-(2m-3) . i . • 3 i I 5 7 * ] 2 m - 3 2m-1 z o n e two * • • • * * ' i zone one * • • F i g u r e 4.1: E r r o r s for C F a n d L M S a l g o r i t h m T h e taps are u p d a t e d i n the opposite d i r e c t i o n of the gradient c When n + 1 = c „ - ne {LMS)r Ttn n = c - n{y - a „ ) r n n (4.5) n y a n d a represent the i n p u t a n d o u t p u t o f the slicer, the error e (CF) n n rtTl tap u p d a t i n g is equivalent to the error measured at the slicer. T h e error e , (CF) r n used d u r i n g is defined differently. N o t e that the L M S a l g o r i t h m uses second-order statistics of the signals, whereas M M A uses fourth-order statistics. I n order to compare the two algorithms, we use the M M A w i t h L = 1. 61 For one-dimensional M M A w i t h L — 1, the error e {CF) o f the generalized M M A becomes TiTl e , {CF) = \y \-R r n . n (4.6) T h e filter's taps are updated as follows c n + i =c - ne , {CF)r n T n = c - /j,{\y \ - R)r n n n n (4.7) T h e taps are not exactly u p d a t e d i n the d i r e c t i o n of the slicer's errors. Instead, error m i n i m i z a t i o n is done w i t h reference to the constant R that has statistical i n f o r m a t i o n a b o u t the real symbols a . n T h e d i r e c t i o n of filter a d a p t a t i o n depends o n the constant R, w h i c h depends o n m . I n summary, the error e (LMS) rn is a well-defined quantity. A n equalizer c a n converge to o p t i m a l solutions when errors are d i r e c t l y calculated w i t h respect to the i n p u t s a n d o u t p u t s of the slicer. I n contrast, the error e r > n ( C F ) has o n l y a s t a t i s t i c a l meaning. A n equalizer is not always guaranteed to converge to o p t i m a l solutions i n terms of mean-square error ( M S E ) . For b l i n d algorithms, we usually have CF ^ 0 w h e n a n equalizer has converged. T h a t is, residual values o f the cost function exist. A t this stage, i n order to understand the M M A b l i n d a l g o r i t h m , it is necessary to investigate what are the r e s i d u a l values o f the cost function CF. start-up w i t h a perfect convergence, y —> a . n the cost function n Consequently as was shown i n the previous chapter, CF converges to CF an CF = E[{yl - R ) } 2 T h e cost function For a blind CF an -> 2 CF = E[(a - R ) } 2 an 2 2 n is then expanded, factorized a n d simplified as follows CF an = E[(a -R ) } 2 2 2 n = E[a -2a R 2 n +R] 2 A n = E[a -2a §^ R*) 2 n = n ]+ E[a ]-2E[a }§$\ R* 2 n 62 n + (4.8) N o t e that o n l y the analysis for the in-phase d i m e n s i o n is p r o v i d e d , a n d that the same analysis applies to the quadrature phase d i m e n s i o n . I n order to evaluate the cost function, we need to express CF an as a function of the n u m b e r of s y m b o l levels m . C a l c u l a t i o n s of moments of d a t a symbols c a n be found i n A p p e n d i x B . F o r M M A , the constant i? is given by „ R a n d the fourth moment of the symbols a n 12m -7 , (4.9) 2 2 2 = N is given by £[a ] = ^ ( 4 m - l ) ( 1 2 m - 7 ) 2 (4.10) 2 n T h e n the cost function CF an can be r e w r i t t e n as CF = R^-Elai] = ( ^ ^ ) = ^(12m -7)(m -l) = — ( 1 2 m - 1 9 m + 7) an 2 (4.11) - ^ ( 4 m 2 1 2 - l ) ( 1 2 m 2 - 7 ) (4.12) (4.13) 2 f\ 4 (4.14) 2 E q . 4.14 gives a simple way to express the cost function after convergence. Steady-state values of the cost f u n c t i o n CF c a n then be easily calculated. T h e number of an s y m b o l levels m (in magnitude) can be c o m p u t e d from the number of constellation points C for C-CAP Vc m = — E q . 4.14 shows that CF an = 0 for m = 1, a n d CF an m = 2, a n d CF an ^ 0 for m ^ 1. For instance, c a l c u l a t i n g an gives the following results: CF (4.15) = 0 for 4 - C A P w i t h m = 1, CF an CF an = 14.2 d B for 1 6 - C A P w i t h = 27.7 d B (we choose d B i n measurement) for 6 4 - C A P w i t h m = 4, It means that the o p t i m u m convergence for a b l i n d equalizer can o n l y be achieved for 4 - C A P w i t h m = 1. R e s i d u a l values of the cost function CF an significantly increase w i t h increasing m . U l t i m a t e l y , for large values of the n u m b e r m , residual values of CF an become so large that a b l i n d equalizer fails to converge. R e s i d u a l values of CF an are increasing functions of the number m , a n d a n equalizer's convergence is d i r e c t l y affected by those values. I n conclusion, the r e l i a b i l i t y of a b l i n d a l g o r i t h m is highly 63 degraded w i t h increasing m. W h e n the residual values o f CF increase b e y o n d some quantity, an the eye d i a g r a m fails to open. It has been found that a s t a n d a r d M M A is o n l y effective for C A P applications w i t h m less that eight w h i c h corresponds to 2 5 6 - C A P . 4.2 Principle of M u l t i m o d u l u s W i t h M M A , the use o f more t h a n one m o d u l u s for each d i m e n s i o n was o r i g i n a l l y proposed for nonsquare constellations [29]. M M A m i n i m i z e s the dispersion of the equalizer's o u t p u t samples y n a r o u n d piecewise linear contours. T h e general form of the in-phase M M A cost function for L = 2 is given b y CF = E[(y -R (y )) } 2 2 n (4.16) 2 n where values o f R(y ) are determined b y the d i s t r i b u t i o n function o f the samples y . For square n n constellations, R becomes a single constant. F o r nonsquare constellations, however, R{y ) takes n m u l t i p l e values that depend o n the n u m b e r o f sets o f symbols a n w i t h different statistics. F o r instance, for 1 2 8 - C A P , t h e symbols are t r a n s m i t t e d i n two sets, whose values are given b y ai = { ± 1 , ± 3 , ± 5 , ± 7 } and a = { ± 9 , ± 1 1 } . 2 of symbols a\^ a n d a , n 2 n T w o constants R\ a n d R are necessary because the sets 2 have different p r o b a b i l i t y d i s t r i b u t i o n s . T h e s t u d y i n [29] shows that the use o f m u l t i p l e m o d u l i leads t o a r e d u c t i o n o f the number o f w r o n g solutions. P a r t i c u l a r l y , the p r o b a b i l i t y of creating the 144-point s o l u t i o n for 1 2 8 - C A P is significantly reduced w h e n two m o d u l i R are used. F u r t h e r s t u d y has shown that, even for square constellations, t h e use o f m u l t i p l e m o d u l i can improve the r e l i a b i l i t y of convergence. T h e u l t i m a t e knowledge one c a n have about the statistics of the t r a n s m i t t e d symbols is t o k n o w exactly w h i c h symbols have been t r a n s m i t t e d . T h i s can be the case at start-up o n l y w h e n a t r a i n i n g sequence is u t i l i z e d , or i n steady-state, w h e n the eye is open a n d w r o n g decisions occur rarely. I n this case, the M S E is the best cost function a n d the corresponding L M S a l g o r i t h m is t h e best t a p u p d a t i n g a l g o r i t h m . However, the L M S a l g o r i t h m cannot be used d u r i n g b l i n d start-up because o f excessive ISI w h i c h creates t o o m a n y w r o n g decisions. A t the low end of our knowledge of the statistics of the t r a n s m i t t e d symbols are single one or two-dimensional contours a r o u n d w h i c h the d i s p e r s i o n of the symbols is m i n i m i z e d . 64 Usage of this type of knowledge leads to M M A a n d C M A . T h e advantages of using this type of approach is that most output samples o f the equalizer are meaningful. T h a t is, there are many less w r o n g decisions. The difficulty w i t h using single contours is that the correction terms used i n the t a p u p d a t i n g algorithms become very large c o m p a r e d to the spacing between adjacent symbols. A s a result, it becomes increasingly difficult to open the eye w h e n the number m o f s y m b o l levels increases. F o r very large values of m , opening of the eye w o u l d require such a s m a l l step size that the convergence time w o u l d b e unacceptable. T h i s issue is discussed i n more d e t a i l i n A p p e n d i x C . M i n i m i z i n g the dispersion of subsets o f equalizer output samples y n a r o u n d several contours m i n i m i z e s the m a x i m u m values that c a n be assumed b y the correction terms i n the t a p u p d a t i n g algorithms. T h i s facilitates the o p e n i n g o f the eye. However, w i t h such a n approach, more w r o n g correction terms are going to be used d u r i n g i n i t i a l b l i n d start-up. T h a t is, because of ISI, some samples y w i l l appear i n a w r o n g area i n the complex plane a n d w i l l be used to compute a n correction t e r m w i t h respect to the w r o n g m o d u l u s . In m a n y ways, this p r o b l e m is s i m i l a r to the p r o b l e m experienced b y the L M S a l g o r i t h m d u r i n g i n i t i a l b l i n d start-up. T h e difference is that L M S w o u l d almost always use the w r o n g correction t e r m w h e n there is severe ISI, whereas G M M A , i f it is well designed, w i l l use a large enough correct correction terms to allow the eye to open. F i g . 4.1 shows the two errors used d u r i n g filter a d a p t a t i o n . between e , (LMS) r n a n d e n(CF), Tt L e t V e represent the difference that is, V e = e {CF)-e , {LMS). Ttn T n T h e constant R s t a t i s t i c a l l y describes a i n two different ways, a n d i t depends o n the d i s t r i b u t i o n of y . W e d i v i d e the samples n y n n into two zones. F o r instance, i n 6 4 - C A P , we compute that R = 6. A s shown i n F i g . 4.1, we d i v i d e d a t a into two zones above a n d below the dotted line corresponding to y n a s m a l l number. W h e n the samples y n = 4. L e t 5 denotes are d i s t r i b u t e d i n zone one, V e =< S. Correspondingly, the residual value o f the cost function CF is smaller. T h i s makes the equalizer converge almost to o p t i m a l s o l u t i o n . W h e n the samples y are located i n zone two, V e > S. T h e large V e gives an n the large residual value o f the cost f u n c t i o n CF . an difficult. 65 Consequently, i t makes the o p e n i n g of the eye W e conclude that d u r i n g b l i n d start-up, V e contributes different effects to steady-state convergence depending o n the d i s t r i b u t i o n of a . W h e n samples a n are d i s t r i b u t e d near the constant R, n the absolute values of the two errors are equal to or close to zero, and the equalizer can a p p r o x i mately converge to the o p t i m a l values that can be achieved w i t h the L M S a l g o r i t h m . Otherwise, the equalizer converges to a s o l u t i o n w i t h residual M S E . A t this point, m u l t i p l e m o d u l i are required so that the use of the constant R can represent knowledge of statistics of s y m b o l s a efficiently n under the c o n d i t i o n of m i n i m a l w r o n g decisions. W e conclude that m u l t i p l e m o d u l i are also necessary for square constellations. I n fact, the use of generalized M M A is just a n a t u r a l extension of M M A . I n M M A for nonsquare constellation, m u l t i p l e m o d u l i are required to satisfy nonuniform d i s t r i b u t i o n of y , n of y n whereas the a l g o r i t h m of m u l t i l e v e l m o d u l i is designed for u n i f o r m d i s t r i b u t i o n to improve convergence reliability. We now discuss the concept of sample subsets used i n G M M A . A sample subset is defined as i Vn = {Vn,i} i = !,•••, I (4.17) W h e r e I < m. T h e cost function m i n i m i z a t i o n is done w i t h respect to each sample subset CF=-J2CF = -J2E[(yl -R ) ] 2 l (4.18) 2 l T h e cost function is reduced to the cost functions CFi corresponding to the subset y i. W h e n an n% equalizer converges, we have y n —> a , or, i n terms of sample subset, we have {y ,i} n n { n,i}a The m i n i m u m of the cost function i n (4.18) is given by CF an = -J2 1 CF a n t i = - £ i=i - R)] 2 (4.19) 2 i=i when the outputs of the equalizer have converged to constellation points a ^. n constant R4 refers to the set of symbols I n this case, the a j. n W h e n using sample subsets, the overall system performance is determined b y the i n d i v i d u a l performance for each d a t a subset, so that a performance criterion is required for the system. T h e analysis i n the previous section shows that the r e l i a b i l i t y of convergence depends o n the residual values of the cost functions i n steady state. It is n a t u r a l then to use the equal cost function m i n i m i z a t i o n procedure. T h a t is, the cost functions 66 CF ^ an are m i n i m i z e d i n such a way that the residual value of each CF ^ an is reduced to the same amount. W i t h equal cost function m i n i m i z a t i o n , we have CF anti =C (4.20) where C is a s u i t a b l y chosen constant. W i t h G M M A , the equalizer tries to reduce the residual value o f the cost function i n order to achieve a good eye opening. 4.3 Parameter Design In this section, we show how to select the subsets of samples used for G M M A . W i t h M M A , only one constant R needs to be determined for a given constellation. U n l i k e M M A , several parameters are needed to describe sample subsets i n G M M A . I n a d d i t i o n , because the sample subsets y ,i are n undefined at the beginning of the a l g o r i t h m , a n u m e r i c a l s o l u t i o n cannot be easily derived. O u r study shows that cost functions c a n be expressed as a function o f the n u m b e r m [30]. W e c a n also express the cost function CF ^ an sample subset as a function o f m , , where 2 m , — 1 is the highest s y m b o l level for i, as shown i n F i g . 4.2. W i t h one u n k n o w n m,-, the cost function CF i = C can be an< numerically solved. O t h e r parameters c a n be solved as well i f they c a n be expressed as a function ofmj. In summary, m , is the fundamental parameter i n the overall system design because it c a n be d i r e c t l y derived for a given cost function. A n iterative a l g o r i t h m is developed to calculate the parameter m , , the flow chart o f w h i c h is shown i n F i g . 4.3. T h e c a l c u l a t i o n of m ; starts w i t h i = 1, a n d m , is then sequentially calculated. F i n a l l y , the p r o g r a m terminates w h e n the c o n d i t i o n 2mi — 1 > M is satisfied, where M = 2m — 1. After mi is derived, other parameters c a n be derived i f they c a n be expressed as a function of ra{. F i g . 4.2 shows the parameters required for G M M A . T h e parameters a n d their corresponding algorithms are defined as follows. a. T h e number of s y m b o l levels m j for each sample set y i. F o r the i t h sample set, m j c a n be S n< s c o m p u t e d i f m , is provided m si - mi- rrii-i 67 (4.21) parameter (level) t5 .13 t1 J9_ 7 ~I i-1. M (2m-1) m, (2m,-1) m (2m, 1) nr M r 5 3 1 -1 -3 -5 -7 -9 -t1 -t3 -t5 Q F i g u r e 4.2: G M M A design parameters for 2 5 6 - C A P F i g . 4.2 shows the three parameters i n a 256-point constellation, b. T h e sample b o u n d a r y Wi. T h e parameter W{ is defined as u>i ' 2mj (4.22) Wi is the parameter required to describe the sample subset y ,i. n N o t e that Wi is chosen as above because o d d number are used-for the s y m b o l s . W i t h such a definition a n d s y m b o l levels w h i c h are o d d integers, the sample b o u n d a r y lies at equal distance between two s y m b o l levels. W h e n Wi is defined, the sample subset y . j is described as n Wi-i < \Vn,i\ < Wi 68 (4.23) Consequently, the s y m b o l subset a ,i n is described as Wi-\ F i g . 4.2 shows Wi a n d Wi-\ < \a i\ < Wi (4.24) n< as two dotted lines. c. T h e constant Ri for subset y ^. n W h e n m{ is defined, the constant Ri can be easily calculated. Details can be found i n [30]. F i g 4.2 shows the required Ri for sample set y ^ n ^ start m as a solid line. ^ 1 i= 2 f r—Yes i=i+1 Q exit ^ F i g u r e 4.3: Flow-chart for the design of the G M M A parameters T h e general a l g o r i t h m description to calculate the system parameters for G M M A has been prov i d e d . T h e special case of 2 5 6 - C A P is now discussed. I n this example, the number of s y m b o l levels is given by m = 8, the largest s y m b o l level is M — 15, a n d the residual values of the cost function CF an i n d B is chosen to be CdB — 28 d B (experimental). T h e number CdB — 28 d B refers to the residual values of CF an required by M M A for 6 4 - C A P . CdB is n o r m a l l y chosen experimentally. 69 1. T h e c a l c u l a t i o n of rrii starts w i t h i — 1. W h e n the index i is equal to one, the c a l c u l a t i o n of mi is simple. T h e cost function CF i as a function of m i is given by ant CF = E[(a - R)] 2 an<1 2 ntl = ^(12m 75 2 4 - 19m? + 7) (4.25) In this design, we assume C = 28 d B . N o t e that the constant C i n l o g a r i t h m i c scale needs to be converted to linear scale. S e t t i n g CF ^ = C, we o b t a i n one positive solution. Note that n o r m a l l y an the solution is not a n integer, a n d a n integer solution is obtained by r o u n d i n g the number m*. T h e same rule w i l l be a p p l i e d i n the rest of the report to o b t a i n positive integer solutions. I n this case, we have m i = 4. For the d a t a set y ,\, the number of s y m b o l level m i is given by n s mi s = mi — > mi = 4 (4.26) T h e d a t a b o u n d a r y wi is t h e n c o m p u t e d as wi = 2 m j = 2 * 4 = 8 (4.27) For this value of wi, the samples y i are described as n< ' 0 < \y \ < 8 nA (4.28) Correspondingly, the symbols a ^\ are restricted to n on.1 = { ± 1 , ± 3 , ± 5 , ± 7 } (4.29) T h e constant R\ can be c o m p u t e d from Rl = ^ = -^T^ = V -+ * i * 6 . (4.30) For sample set y i , the equalizer m i n i m i z e s the dispersion a r o u n d the constant R\ = 6 when the n i equalizer's o u t p u t samples satisfying 0 < | y i | < 8 are used d u r i n g the filter adaptation. n ] 2. T h e above described the d e r i v a t i o n for i — 1. F o r i / CF mti = EKal, - R)} 2 70 2 1, the cost function CF = R an 4 - E[a* A t i is w r i t t e n as (4.31) T o compute CF i, b o t h Rt a n d a ^ aTlj must be determined as a function of m^. It s h o u l d be noted n that the i n i t i a l index of a j n does not start w i t h one. In order to use the results i n [29] to compute E[a ] as follows the s y m b o l moments, we rewrite n>i -. mi mi-i EO = ^-C£;<- KH E n=l S 1 S becomes n n>1 =^-K(48m 4 4 32 n=l where m i = m , — m j _ i . T h e n the expectation of a ^ E[a ] (- ) - 4 0 m + 7) - m _ ( 4 0 m f _ i - 4 0 m _ i + 7)] 2 2 (4.33) 2 i 1 a n d the constant Ri is given by D 2 -^[ n,i] 2 12 , a 2 \ IA O A \ R a n d E[a ] into the cost function CF ,i, the following results: 2 Substituting ni CF ,i a a = R$-E[a* \ (4.35) = (yK -m _ )) -^-[m (48m -40m fi 2 2 2 4 1 2 i + 7) (4.36) - m _ i ( 4 0 m t i - 4 0 m _ ! + 7)] - 2 i 64, 4 2Jr = m i 8 + o ( m o - m ? + i m 4 \ 368 - ^ ~ "25~ i m i - i + 9 2 m i 7 n i 16 - ~ y i m 1 2 2 m J-i( m ;;~ m \ «n\ i-i) (4-38) 7 i - i ) ~ 77 m (4.37) (4.39) 15 I n the iterative a l g o r i t h m , m j _ i is k n o w n , and m , is u n k n o w n . O n e variable is u n k n o w n for the equation CF j = C, so that the equation can be u n i q u e l y solved. For i — 2 a n d m\ = 4, we o b t a i n a the positive integer s o l u t i o n m2 = 6. T h e following is the c a l c u l a t i o n of the number m , for i — 2 s m i = rrii — rrii-\ S —y m2 S = rri2 — mi = 6 — 4 = 2 (4.40) T h e sample boundary^ is given, by W i W i t h Wi-x = 8, the sample subset y ^ n = 2m = 2 * 6 = 12 i 2 (4.41) is defined by 8 < \y ,2\ < 12 n 71 (4.42) For the s y m b o l subset a , two s y m b o l levels are i n c l u d e d nj2 a n > 2 = {±9,±11} (4.43) W i t h k n o w n mt a n d m j _ i , the constant Ri can be c o m p u t e d . F o r i = 2, we have R\ = ' ^ ( 2 _ m\) 5 m i ? ( 6 - 4 ) = 105 5 2 = 2 -> R 2 = 10.25 For sample set y 2i the equalizer m i n i m i z e s the dispersion a r o u n d the constant R (4.44) n% 2 = 10.25 w h e n the samples are restricted to 8 < |y ,2| < 12. n 3. I n this step, the c o n d i t i o n a l equation 2mj — 1 > M is tested. For i = 2 a n d M = 15, the c o n d i t i o n is not satisfied since 2m 2 — 1 = 11 < M. T h u s , the index counter is incremented w i t h 1 — 1 + 1 = 3. T h e p r o g r a m returns to step 2. R e p e a t i n g the c a l c u l a t i o n i n step 2 for i = 3, the following values are obtained: = 8, m 3 = 2, = 16 a n d i?3 = 14.17. Therefore, the samples S y ,3 are defined as n 12 < | y „ , | < oo (4.45) 3 a n d two s y m b o l levels are i n c l u d e d i n a$ n a , n For the sample set y 12 < |y ,3| < n n ) 3 3 - {±13, ±15} (4.46) , the equalizer m i n i m i z e s the d i s p e r s i o n a r o u n d R$ = 14.17 w h e n samples are used d u r i n g the tap u p d a t i n g . 4. T h e c o n d i t i o n a l e q u a t i o n m , > M is satisfied w i t h 7713 = 8 since 2mj — 1 = 15 = M , so that the iterative a l g o r i t h m for 2 5 6 - C A P is t e r m i n a t e d for i = 3. T h i s completes the parameter c a l c u l a t i o n of G M M A for 2 5 6 - C A P . T o satisfy the equal cost function m i n i m i z a t i o n , a t o t a l of three sample subsets is required, as shown i n F i g . 4.2. I n this figure, the three sample subsets are d i v i d e d by the dotted lines Wi, a n d three m o d u l i Ri are represented by solid lines. T h e equalizer m i n i m i z e s the dispersion at the equalizer's output samples w i t h respect to three m o d u l i , respectively, d u r i n g the filter a d a p t a t i o n . 72 4.4 Examples Table 4.1 shows the parameters calculated for 2 5 6 - C A P , where y \ is for M M A , y \ nt are for half-constellation M M A , a n d y \, y$ nt and y ^ n ni 1 ~ 7 9 ~ 11 13 ~ 15 9 ~ 15 1 ~ 15 Vn,i Vn,l Vn,2 Vn,3 Un,4 2/71,5 CF 27.7 26 29 35 40 TTlyji 4 2 2 4 8 R 6 10.35 14.2 13 12.34 1 ~ 8 8 ~ 12 12 ~ oo 8 ~ oo 1 ~ oo Wi-l y^ n are for G M M A . I n fact, three different n Constant/a„ Wi ~ and T a b l e 4.1: Parameters for 2 5 6 - C A P algorithms are characterized i n T a b l e 4.1, the s t a n d a r d M M A , the half-constellation M M A , a n d the G M M A . For M M A w i t h sample set y 5, n> of the cost function CF , a n is very h i g h . A b o u t 40 d B of residual value exists w h e n the equalizer W h e n the sample set y converges. i n the last c o l u m n of Table 4.1, the residual value n is equally split between subsets y j a n d y ^, n n the residual value for the second h a l f constellation is about 8 d B larger t h a n that of the first half. It means that equal cost function m i n i m i z a t i o n is not achieved w i t h a subset selection that s i m p l y splits the signal constellation into two subsets having the same number of symbols. F i n a l l y , equivalent cost function m i n i m i z a t i o n is achieved by the G M M A w i t h equal cost function m i n i m i z a t i o n . A s shown i n Table 4.1, w h e n three d a t a subsets are used as y \, n> function CF i an< y ,2 n a n d y 3, n> the residual values of the cost are reduced to be a p p r o x i m a t e l y the same. Summary: G M M A is proposed as a n extension of M M A by using m u l t i p l e m o d u l i along each dimension. T h e cost function analysis showed that the residual values of the cost function are nonzero, a n d these values grow w h e n the number of s y m b o l levels increases. W e need to reduce those m i n i m u m values i f we want to improve the performance of the eye opening. T h i s is realized 73 by using m u l t i p l e m o d u l i along each d i m e n s i o n of symbols. B y d o i n g this, we introduce sample subsets into the a l g o r i t h m . T h e residual values of the cost functions c a n then be m i n i m i z e d i n each subset. In this case, each constant R can efficiently represent the knowledge of the statistics of the symbols i n the corresponding subset. In this chapter, the use of m u l t i p l e m o d u l i is demonstrated by the design given for 2 5 6 - C A P . Because sample subsets are not able to be determined at the beginning, R cannot be s i m p l y derived. T h e c a l c u l a t i o n of m u l t i p l e R is provided by a sequential c o m p u t i n g a l g o r i t h m . T h e analysis shows that by a p p l y i n g three constants Ri to a 2 5 6 - C A P , the cost function can be m i n i m i z e d to s i m i l a r s m a l l values. T h i s greatly facilitates the o p e n i n g of the eye. 74 75 Chapter 5 Windowed M M A (WMMA) W i t h M M A , m i n i m u m values of the cost functions are generally nonzero a n d the values increase when the n u m b e r of s y m b o l levels increases. W i t h G M M A , r e d u c t i o n of the m i n i m u m value of the cost function is realized by using m u l t i p l e m o d u l i along each d i m e n s i o n . W i n d o w e d algorithms for M M A are proposed as another approach to realize a r e d u c t i o n of this m i n i m u m value. T h e study shows that errors contribute different effects to filter a d a p t a t i o n d e p e n d i n g o n how close the samples are d i s t r i b u t e d a r o u n d the constant R. only part of data. T h e convergence rate can be i m p r o v e d by using T w o algorithms w i l l be proposed as applications of w i n d o w e d algorithms for M M A w i t h i m p r o v e d convergence rate [30]. 5.1 Algorithm Structure It was shown i n the previous section that a cost function usually does not converge to zero w i t h b l i n d algorithms except for 4 - C A P . B o t h the eye d i a g r a m opening a n d convergence rate are affected by residual values of the cost function, or more accurately, by erroneous quantities used i n the cost function. L e t A e denote the difference between the error e , (CF) a n d the error e (LMS), as r n rtn shown i n F i g . 4.1. T h e convergence rate of a n equalizer is a decreasing function o f the value of A e . F i g . 4.1 shows that the values of A e vary according to its d i s t r i b u t i o n . If A e c a n be m i n i m i z e d by some constraints, the equalizer's convergence c a n be i m p r o v e d . A new a l g o r i t h m is required so that the cost function can m i n i m i z e the error difference A e . A modified version of M M A , called w i n d o w e d M M A , is proposed as a ' n e w a l g o r i t h m w i t h i m proved convergence properties. I n this a l g o r i t h m , the cost function is designed i n such a way that the error difference A e can be m i n i m i z e d . F u r t h e r study of F i g . 4.1 shows that A e has different effects on the cost function d e p e n d i n g o n the absolute value of the distance \y \ — R, or the secondn order q u a n t i t y y 2 - R. 2 F i g . 4.1 shows clearly that the error difference A e is p r o p o r t i o n a l to the distance | | y | — R\. Therefore, a new a l g o r i t h m is developed so that filter tap u p d a t i n g needs to be n done only w i t h those d a t a w h i c h have relatively s m a l l values of | | y | — R\. n W M M A is a modified version of M M A , except that a sample w i n d o w is used d u r i n g a d a p t a t i o n . T h e W M M A scheme is i l l u s t r a t e d i n F i g . 5.1 where the sample w i n d o w is defined by two d o t t e d lines a l o n g each d i m e n s i o n . W i t h W M M A , o n l y some of the samples y n > w are used d u r i n g filter a d a p t a t i o n , whereas w i t h M M A a l l the samples are used. F i g . 5.1 shows the w i n d o w parameters defined w i t h half-constellation W M M A for 6 4 - C A P . W h e n m = 4 is used as the b o u n d a r y line of the sample w i n d o w , the samples y , or \y \ > 4. Consequently, the new = {±5, ±7}. F i g . 5.1 also shows the new w are given by \y \ n w > m, n constellation used for a d a p t a t i o n includes symbols o „ w i U J n constants R represented by two solid lines, a n d R = 6.4 is required for the equalizer to converge to the constellation w i t h symbols anjW = { ± 5 , ± 7 } . Two applications of W M M A are the half-constellation W M M A , a n d the edge-point WMMA. T h e two algorithms use the same cost function, except for the different definitions of the sample windows. Because different sets of samples y n are used d u r i n g filter a d a p t a t i o n , different results can be achieved i n terms of cost function o p t i m i z a t i o n . 5.2 The Half-Constellation W M M A half-constellation W M M A is proposed as the first i m p l e m e n t a t i o n of the W M M A concept, and the schematic d i a g r a m of this a l g o r i t h m for 6 4 - C A P is i l l u s t r a t e d i n F i g . 5.1, w h i c h shows the sample w i n d o w . I n the case of the in-phase d i m e n s i o n the samples y n the w i n d o w boundaries m w w i t h \y \ n < m w a n d \y ,w\ > n^w n are d i v i d e d into two sets by W i t h new samples y ,w, n the cost function CF is redefined as CF = E[{y -Rl) } 2 2 ntW 76 (5.1) N o t e that the constant R is changed to R because o n l y a subset o f signals y w n t W is used t o converge the equalizer. T h e equalizer's taps are u p d a t e d w i t h samples yn.w and r e m a i n unchanged w i t h samples y . For the half-constellation W M M A , the w i n d o w b o u n d a r y m is defined as n w m =m w (5.2) where m indicates the number o f s y m b o l levels, a n d the m a g n i t u d e of the highest s y m b o l level is given b y 2 m — 1. T h e w i n d o w b o u n d a r y m is defined i n such a way that the same number of w inner-point a n d outer-point symbols a are i n c l u d e d a r o u n d the constant R. I n other words, we can n say that the samples y UyW used to update the taps are s y m m e t r i c a l l y d i s t r i b u t e d o n b o t h sides of R. It is called half-constellation W M M A because the number o f p a r t i a l symbols a ^ that construct n the new constellation is h a l f the number o f the o r i g i n a l symbols a . For the half-constellation n W M M A , the constant Ru, needs t o be evaluated w i t h respect t o symbols a , . n Vn,wi w w W i t h the samples the cost function CF now converges to the symbols a „ , W ; U CF = E[{yl tW - Rlf] -+ CF = £ [ « „ - R ) ] 2 2 W (5.3) T h e n the constant Ry, is c o m p u t e d as [a ] E n N o t e that the i n i t i a l index of a , n w nw does not start w i t h one. I n order t o use the results derived for the symbols a i n [30], we need t o derive the moments for the symbols a , n n A n example is given for t h e c a l c u l a t i o n of E[a 2 ]. n 1 w w w i t h a r b i t r a r y i n i t i a l index. T h e second-order expectation is r e w r i t t e n as M n=l M W n—l T h e parameter w denotes the number of s y m b o l levels required for the constellation i n c l u d i n g a , . n w For the half-constellation W M M A , we s i m p l y have w = \-m ' (5.6) E q . 5.6 means that half the number o f the o r i g i n a l s y m b o l levels m is required. M denotes the number of the largest s y m b o l levels a n d the parameter M w 77 T h e parameter denotes the number of s y m b o l levels below the w i n d o w b o u n d a r y m . T h e parameters are given by w M = 2 m - 1 and M w T h e constant R w =m - 1 (5.7) c a n then be calculated as EK ] Rl tW 1|V «n - E5L"i o i l mLZjn=l L\T [2-in=l ° n M — - M w 2 ry-*m - E S U <\ — En=l n\ < 2 ry->m §(48m 4] a — 4 0 m + 7) - 30 * f ( 4 m - l ) - f ( m 4 _ 7 2 ^ 4 2 2 m ( M m m 2 - l ) + f(7m2-l) 93m - 70m + 7 4 2 35m - 5 2 Values of the constant R for M M A a n d the constant R^ for W M M A are p r o v i d e d i n Table 5.1. W e Parameter/CAP 16-CAP 64-CAP 256-CAP 1024-CAP m 2 4 8 16 R 2.86 6.08 12.34 24.76 m w 1 2 4 8 Rw 3 6.4 12.97 26.05 T a b l e 5.1: C o n s t a n t R for half-constellation WMMA observe i n T a b l e 5.1 that the values of Rw are always larger t h a n those of R. It means that the constant R is smaller w h e n the i n i t i a l s y m b o l starts from one. N e x t we compute the residual values of the cost function for the half-constellation W M M A show how m u c h r e d u c t i o n can be obtained. T h e simplified expression for the cost function 78 to CF an was derived i n Section 1. It changes to the following w i t h R w CF = R -E[a ] 4 an -+ 4 n a n d E[a . n CF =R -E[a 4 an w (5.8) ntW Replacing i ? with 2 _ 93m - 70m + 7 4 2 ~ w 2 (5.9) 35m -5 2 and replacing E[a^ ] w i t h w E[a , ) = 4 2(93m 4 - 7 0 m + 7) 2 n w the cost function CF a>w CF an (5.10) m for the half-constellation W M M A is t h e n obtained as — R%~ £ [ ( a = 2 , - -R^) ] 2 ; U i ? - E[a ] 4 n>w (93m - 70m + 7) 4 — 2 (35m - 5 ) 2 2 93m - 70m + 7 4 n —2* 2 2 m 2_ ( 9 3 m - 7 0 m + 7 ) ( m + 2 ) ( m - 2) ( 1 7 m - 2) 75 * 7m - 1 4 2 2 2 i I Setting CF = 0, we o b t a i n one positive integer solution, w h i c h is m = 2 for 1 6 - C A P . T h e comparison of residual values o f cost functions for M M A a n d half-constellation W M M A is p r o v i d e d i n T a b l e 5.2. It c a n be seen i n this T a b l e that the cost function for 1 6 - C A P becomes zero, a n d that a Cost f x m c t i o n / C A P 16-CAP 64-CAP 256-CAP 1024-CAP m 2 4 8 16 14.2 27.7 40 52 0 22 35 47 14.2 5.7 4.95 4.79 CF mma CF wmma ACF (dB) (dB) T a b l e 5.2: C o m p a r i s o n of cost functions reduction of about 5 d B c a n be o b t a i n e d for other C A P systems. T h u s , b y using W M M A , the cost function CF a<n becomes o p t i m u m for 1 6 - C A P . F o r other C A P systems, the cost function CF atU 79 is reduced. R e d u c t i o n of the residual values of the cost function CF a>n leads to i m p r o v e d reliability and convergence rate of b l i n d equalizers. 5.3 Edge-Point W M M A Edge-point W M M A is proposed as the second a p p l i c a t i o n o f W M M A . T h e cost function for halfconstellation W M M A i n (5.1) c a n be d i r e c t l y a p p l i e d to edge-point W M M A , except that a m o d ification is made for the sample w i n d o w parameters. F i g . 5.2, where the w i n d o w b o u n d a r y m is defined as w m = 2{m-l) w W i t h such a definition, the symbols a ^ n T h e w i n d o w parameters are illustrated i n w (5.11) are given b y a 2 m - i - T h e symbols used for filter adapta- t i o n are only those that have the largest values. F i g . 5.2 shows that these symbols are geometrically located at the edge of the o r i g i n a l constellation. Because o n l y one s y m b o l level is involved, the calculation o f is s i m p l y given b y Rw — o, ,w = 2 m - 1 (5.12) n T h e above equation yields the following equality Rl = E[a ] 2 (5.13) n>w E q . 5.13 further leads to the result CF , a w = E[(a -R ,) ] 2 2 iW 2 -+ 0 (5.14) E q . 5.14 shows t h a t zero value can be achieved w i t h such a cost function. T h a t is, w i t h edge-point W M M A , the cost function becomes o p t i m u m for any C A P system. T h e edge-point and^half-constellation M M A are basically the same except that they use different window parameters. However, the difference i n parameter results i n different performance. T h e o retically, o p t i m u m convergence c a n only be achieved for 1 6 - C A P w i t h half-constellation W M M A , and c a n be achieved for any C A P a p p l i c a t i o n w i t h edge-point W M M A under conditions to be discussed later. 80 T h e choice o f design parameters o f edge-point constellation is simple a n d easy to implement. However, expected performance cannot be achieved for h i g h level C A P applications because other factors also affect convergence, such as the lack of d a t a samples y . n 5.4 Filter Adaptation T w o W M M A algorithms were proposed i n the previous section. W e now derive the algorithms for u p d a t i n g the t a p coefficients. F o r simplicity, the previous analysis for W M M A was o n l y given for the in-phase d i m e n s i o n . T h e complete two-dimensional cost function for W M M A is given b y CF = [(yl - R ) 2 w 2 W + (y - R )} 2 2 n!W (5.15) 2 W T h e cost functions c a n be a p p l i e d to b o t h half-constellation a n d edge-point W M M A s b y using different definitions for y , , n w as shown i n Section 2. T h e gradients o f the cost function i n (5.15) w i t h respect to the t a p vectors c„ a n d d„ are equal to V c = (yl, w - Rl)yn,w*n V = (yl d - Rl)y r jW ntW n (5.16) T h e filter's taps are t h e n u p d a t e d i n a stochastic fashion i n the opposite d i r e c t i o n o f the gradient c n + i = c„ - n(yl, d + i = d - ii(yl n Note that y n<w and R w n - R )y ,wr (5.17) - R )y wrn (5.18) 2 w w n n 2 tW w n} are different for t h e two versions o f W M M A . In the i m p l e m e n t a t i o n o f the algorithms, t h e samples y n<w are n o r m a l l y calculated b y using a comparator, o r a l o o k - u p table. A l t e r n a t i v e l y , a nonlinear function / ( • ) is proposed t o determine p a r t i a l samples y ,w T h e function / ( • ) is defined as n f(yn) = \[l + sgn(y -m J] (5.19) f(yn) = \[l + sgn(y -m )} (5.20) 2 2 n 2 2 n w (5.21) 81 So that ( f(Vn) = ( \y\ < m 0 if 1 otherwise w fiVn) { = { 0 \y\ < m if w 1 • otherwise where m w = m for half-constellation W M M A , a n d m w — 2 ( m — 1) for edge-point W M M A . T h e use of the nonlinear equation / ( . ) gives the following r e l a t i o n f(Vn) = Vn,w f{Vn) = Vn, (5.22) W T h e cost function CF c a n be r e w r i t t e n as CF = [f(y )(y - R J 2 n 2 2 n + f(y )(y - R J } 2 n 2 2 (5.23) n and the corresponding t a p u p d a t i n g a l g o r i t h m becomes c „ + i = c - nf{y )(yl - R )y Tn n n w (5.24) n d + i = d „ - fj,f(y ){yl - Rl)y r n n n (5.25) n In the case of the in-phase d i m e n s i o n , b o t h (5.24) a n d (5.17) c a n be used to d o filter adaptation. S u m m a r y : T h e half-constellation M M A a n d edge-point M M A are proposed as i m p r o v e d M M A algorithms. B o t h algorithms provide some improvement i n cost function m i n i m i z a t i o n . I n theory, cost function o p t i m i z a t i o n can be achieved for any a p p l i c a t i o n . However, filter a d a p t a t i o n cannot be done w i t h insufficient samples. So the w i n d o w e d algorithms are l i m i t e d to some specific applications. In p a r t i c u l a r , W M M A is attractive to some a p p l i c a t i o n s w i t h a m e d i u m size n u m b e r o f s y m b o l levels. E v e n t h o u g h o n l y p a r t i a l d a t a are used, a better convergence performance c a n be achieved t h a n w i t h the full a l g o r i t h m i m p l e m e n t a t i o n because the residual value o f the W M M A cost function is smaller t h a n that o f M M A a n d it leads to r e d u c t i o n of the t a p u p d a t i n g 82 fluctuation. -R-m. m...R n.w • 3 . y. *n . R m,. -a -R a. In-phase dimension b. quadrature phase dimension Q i — - > j_ _ r L • ! ' * c. Two dimensions Figure 5.1: Half-constellation WMMA for 64-CAP 83 Q Q i m.. a . In-phase d i m e n s i o n b. quadrature p h a s e d i m e n s i o n Q •f- i I L. .J c. T w o d i m e n s i o n s Figure 5.2: Edge-point W M M A for 64-CAP 84 85 Chapter 6 Computer Simulations and Laboratory Experiments In C h a p t e r 3 t h r o u g h C h a p t e r 5, we have presented a detailed s t u d y of M M A a n d its generalized algorithms. T h e i m p r o v e d convergence performance of M M A is demonstrated i n this chapter t h r o u g h computer simulations a n d l a b o r a t o r y experiments. 6.1 Simulation Environment In chapter 2, we described i n d e t a i l the receiver structures required for b l i n d equalization. A m o n g s t the possible alternatives, we chose a receiver using a phase-splitting equalizer of the type that is used for the 6 4 - C A P A T M L A N standard. [1]. T h i s s t a n d a r d specifies square-root raised cosine shaping filters w i t h 15% excess b a n d w i d t h . T h e s y m b o l rate for the A T M s t a n d a r d is 1 / T = 25.92 M b a u d , a n d a T / 3 tap spacing is used for the F S L E , so that the s a m p l i n g rate of the A / D is 77.76 M H z . T h e two shaping filters used at the t r a n s m i t t e r form a H i l b e r t pair. T h a t is, they have the same a m p l i t u d e characteristics, a n d phase characteristics that differ by 90 degrees. W i t h the above parameters, we o b t a i n a d a t a rate of 155.52 M b / s for 6 4 - C A P , a n d 207.36 M b / s for 2 5 6 - C A P . I n laboratory experiments, signals are t r a n s m i t t e d over a n 100 meter unshielded t w i s t e d p a i r ( U T P ) category 3 cable. I n the computer simulations, we use the equivalent channel models p r o v i d e d i n [18]. . A t the receiver, we chose the phase-splitting filter as the equalizer's configuration. I n the A T M L A N s t a n d a r d for 6 4 - C A P , a n equalizer span of 16T is required i n [18]. So that a t o t a l number of 48 taps is used for each filter of the equalizer. T h i s number of taps has been used i n a l l the simulations presented here for 6 4 - C A P a n d 2 5 6 - C A P . M o s t of the simulations use 6 4 - C A P and 2 5 6 - C A P , b u t C A P systems using other signal constellations have been studied. In t y p i c a l A T M L A N networks, the m a i n noise i n the system is near-end crosstalk (NEXT). C a n c e l l a t i o n of N E X T can be efficiently done w i t h N E X T cancelers or N E X T equalizers [18]. I n this thesis, i n order to emphasis the s t u d y of b l i n d algorithms, we are o n l y concerned w i t h simulations o p e r a t i n g w i t h o u t noise, w h i c h is justified by the fact that ISI is the d o m i n a n t interference d u r i n g initial training. R e l i a b l e convergence includes two c r i t e r i a . O n e is the q u a l i t y of the eye d i a g r a m opening, a n d the other is the r e d u c t i o n of w r o n g solutions, p a r t i c u l a r l y of diagonal solutions for the phase s p l i t t i n g equalizer. T h e r e d u c t i o n of the p r o b a b i l i t y of creating w r o n g solutions is discussed i n related work by the authors [30] a n d is not covered i n this thesis. 6.2 Computer Experiments T h e performance of M M A a n d its generalized algorithms have been tested t h r o u g h computer simulations using the above-mentioned design parameters. 6.2.1 MMA We first test M M A for the 6 4 - C A P a p p l i c a t i o n . It is p a r t i c u l a r l y interesting to compare the convergence performances of M M A a n d R C A . F i g . 6.1 shows the t y p i c a l M S E learning curves for R C A a n d M M A i n m u l t i p l e s i m u l a t i o n runs. N o t e that the sudden desending w i t h those curves show the s w i t c h i n g from b l i n d equalization to the L M S a l g o r i t h m . It is obvious from the figure that the equalizer converges faster w i t h M M A t h a n w i t h R C A . T h e equalizer's convergence t i m e w i t h M M A is half that needed for R C A . N o t e that the same step size \x = 0.0001 is used for b o t h algorithms. M M A c a n converge faster t h a n 86 RCA because it uses higher order statistics of the signals [11]. 0 1 2 3 4 5 6 iteration 7 8 9 1 Q 10 4 Figure 6.1: MSE learning curves for various blind algorithms used for 64-CAP However, it should be pointed out that recent experimental results seem to show that this advantage of MMA may not be significant for small signal constellations, such as 4-CAP and 16-CAP, which are used in other types of applications. The implementation of the MMA algorithm is more complicated than that of RCA. The tap updating algorithms for RCA and MMA are given by the following equations c„+i = c„ - u[y - Rsgn(y )]r n n C n + i = c„ - /u(y 2 87 - R )y T 2 n n n (6.1) (6.2) where (6.1) is used for RCA and (6.2) is used for M M A . The above tap updating algorithms apply to the in-phase dimension, and similar equations apply to the quadrature dimension. Eq. (6.2) requires higher-order calculations than (6.1). However, the computational cost can be significantly reduced for M M A if a power-of-two multiplier is used for tap updating [6]. The use of M M A not only provides a good convergence.rate, but it also gives a good immunity against wrong convergence to diagonal solutions. Comparing to RCA, M M A reduces the probability of diagonal solutions by about 90% with our computer simulations. For blind start-up, a satisfactory convergence time for the applications considered here is 1 to 2 seconds. For the 16-CAP 51.84 Mb/s system, the symbol rate 1/T is equal to 12.96 Mbaud, so that the symbol period T is equal to T = s e c o n gsxio 6 1 2 d - Assuming that each tap updating iteration is done in 500 symbol periods (500 T),which is easily done in VLSI, and assuming that is takes 30000 iterations to blindly converge the equalizer, we get a convergence time r equal to r = 30000 x 12.96 x 10 6 « 1.2second (6.3) v ; which is perfertly acceptable for the applications considered. 6.2.2 GMMA The important feature of M M A is that multiple moduli are employed, whereas only one modulus is used for RCA and C M A . With M M A , the use of multiple moduli is especially useful for nonsquare constellations and constellations with a high number of symbol levels. In this chapter, we focus the discussion on how multiple moduli can be applied to high symbol level applications, in which case M M A is called generalized M M A (GMMA). The convergence performance of G M M A is tested for the 256-CAP application. In the previous sections, we suggested to use multiple moduli for M M A in order to reduce J , thus improving the ex eye opening. The parameters in Table 6.1 show that the residual values of the cost functions are changed when different M M A algorithms are used for the equalizer. Fig. 6.2 shows a comparison between the evolution of the cost functions for M M A and G M M A . The first plot, curve 1, is obtained for standard M M A . Notice that this curve has a small dynamic range and a large residual value. By using M M A , we obtain only about 2 dB of change, and J ex is about 40 dB high for 256-CAP. Fig. 6.3 shows the converged signal constellation with MMA. The poor performance of the eye opening is mainly caused by the small dynamics and high J ex 1 of the MMA cost function. 1.5 iteration 2.5 x 10 Figure 6.2: Cost function evolution for MMA and GMMA when used with 256-CAP Curve 2 in Fig. 6.2 is obtained when multiple moduli are used for MMA. In this test, we use multiple moduli but not as previously specified for GMMA. In this test, we just equally split the output samples. We see from Table 6.1 that the residual values of the cost functions are equal to 27.7 dB and 35 dB if the samples are equally split in subsets y p and y n n> 3. Notice that the use of equally divided samples does not lead to the same residual values for each sample subset. The maximum J ex is only reduced by 5 dB, and the dynamics of the cost function is not improved very 89 much. C u r v e 3 i n F i g . 6.2 corresponds to G M M A for w h i c h the equal energy p r i n c i p l e is a p p l i e d to define the various m o d u l i . I n this test, the o u t p u t samples are d i v i d e d into three parts, for w h i c h the residual values of the cost function are equal to 27.7 d B , 26 d B , a n d 29 d B , as shown i n T a b l e 6.1, for subsets y ,2, Un,i a n d y $. n subset a n n C u r v e 3 i n F i g . 6.2 shows the e v o l u t i o n of the cost function for the = { ± 1 3 , ± 1 5 } , w h i c h has the largest residual cost function. Table 6.1 shows cost function computations, a n d F i g . 6.2 shows computer s i m u l a t i o n results. Notice that there is a very good m a t c h between the theoretical a n d computer s i m u l a t i o n results. Constant/a 1 ~ 15 1 ~ 7 9 ~ 15 9 ~ 11 13 ~ 15 Dn,i Vn,l Un,2 Vn,3 Vn,4 Vn,5 CF 40 27.7 35 26 29 8 4 4 2 2 12.34 6 1.3 10.35 14.2 1 ~ oo 1 ~ 8 8 ~ oo 8 ~ 12 12 ~ oo R Wi ~ Wi-l n T a b l e 6.1: Parameters for 2 5 6 - C A P F i g . 6.3 shows the signal constellation o b t a i n e d w i t h M M A , a n d F i g . 6.4 shows the signal constell a t i o n after converging w i t h G M M A . C l e a r l y , a better eye opening c a n be obtained by using G M M A rather t h a n M M A . However, G M M A c a n o n l y be a p p l i e d to signal constellations w i t h a number of symbols smaller or equal to 256. Otherwise, there are too m a n y subsets of symbols w h i c h include one or two symbols only. F i g . 6.2 confirms the result stated i n C h a p t e r 4, w h i c h says that the best b l i n d convergence is o b t a i n e d w i t h cost functions w h i c h have the smallest residual J ex largest d y n a m i c s d u r i n g convergence. 90 a n d the 15 10 QC < i < ° -10 -15 -15 -10 -5 0 10 5 15 REAL F i g u r e 6.3: After convergence w i t h M M A 15 « •J. ** 10 5 0 * 4v> •il •* * ii«* *• ; •I ^ & % * .<f. i • > r. » v r ' H I ,->. % .* i > "A .» * # '* > V* '* * • J " h •>• % s; •? >• T j& • > vi-. j« xjt- V" •5 ••/• « c ^ » *v •*» *5 S *• s a •i -5 .T *r t* •i 'I/ .*\ i *' : -10 ; • * V -\. sr XI •ir.:\. *. :*nV: •i» A • ik »• ir i -15 * V- > :^ * :^ .* -15 >'T -10 -5 * <* >» n? • ' • 0 5 10 15 REAL F i g u r e 6.4: After convergence w i t h o p t i m i z e d 91 GMMA ' 6.2.3 W M M A T h e use of m u l t i p l e m o d u l i is one way of reducing the residual values of the cost functions. In C h a p t e r 5, we proposed W M M A as an alternative approach to improve cost function reduction. In this thesis, the performance of W M M A is tested for the 6 4 - C A P a p p l i c a t i o n . In contrast to G M M A , W M M A o n l y uses one constant R, a n d cost function reduction is obtained by using a w i n d o w i n g technique. T h a t is, we update the filters w i t h only those samples w h i c h provide m i n i m u m residual values of the cost function. W e have proposed two w i n d o w i n g algorithms, called the half-constellation a l g o r i t h m a n d the edge-point constellation a l g o r i t h m . T h e simulations w i l l be analyzed w i t h respect to the cost function and the M S E . Evolution of the Cost Function C o m p u t e r s i m u l a t i o n results for W M M A are shown i n F i g . 6.5. T h i s figure shows the evolution of the cost function d u r i n g convergence for various W M M A algorithms. C u r v e 1 corresponds to the M M A cost function, a n d is given as a reference. A s seen i n F i g . 6.5, M M A can provide about 2 d B of variation for the cost function, w h i c h causes slow filter convergence. T h e first variation of W M M A is the half-constellation W M M A , i n w h i c h half of the samples are used d u r i n g filter a d a p t a t i o n as shown i n F i g . 5.1. C u r v e 2 i n F i g . 6.5 gives the evolution of the cost function for the half-constellation W M M A . N o t i c e the i m p r o v e d convergence i n terms of reduced residual value a n d increased d y n a m i c range of the cost function. For the 6 4 - C A P a p p l i c a t i o n w i t h the half-constellation W M M A , we c o m p u t e d J ex — 22 d B , as shown i n T a b l e 5.2. S i m i l a r values are o b t a i n e d through computer simulations, as shown i n F i g . 6.5. C u r v e 3 i n F i g . 6.5 corresponds to the edge-point W M M A , i n w h i c h only edge-point samples are used d u r i n g filter adaptation. I n theory, we can o b t a i n an o p t i m a l s o l u t i o n by using the edge-point W M M A . In practice, .the residual value of the cost function is not zero, but very s m a l l as shown by curve 3 i n F i g . 6.5. We give i n Table 5.2 the theoretical calculations of J ex gives J ex = 27.7 d B for M M A , a n d J value of J ex ex for 6 4 - C A P . N o t i c e that the calculation = 22 d B for the half-constellation W M M A . T h e theoretical is equal to zero for the edge-point W M M A . A s was the case for G M M A , we see that 92 30 I 4 1 MMA 25 A 20 -\ \ CO Li. o MMA 0.5 1.5 iteration 2.5 x 10 F i g u r e 6.5: C o s t f u n c t i o n e v o l u t i o n for M M A a n d W M M A w h e n used w i t h 6 4 - C A P the agreement between the theoretical values calculated i n T a b l e 5.2 a n d the e x p e r i m e n t a l results o b t a i n e d i n F i g . 6.5 is excellent. Evolution of the M S E The simulations demonstrate how well b l i n d convergence is i m p r o v e d w i t h various versions of W M M A . F i g . 6.6 shows the M S E comparison of M M A , the half-constellation W M M A , a n d the edge-point W M M A . T h e equalizer achieves the best steady-state b l i n d convergence performance w i t h edge-point W M M A . 93 ! -5 -10 WMMA LU £ -15 \ -20 -25 -30 0.5 1.5 iteration 2.5 x 10 F i g u r e 6.6: M S E learning curves for various M M A s In F i g s . 6.7 t h r o u g h F i g . 6.10, we show the plots of converged 64-point signal constellations for various algorithms. F i g . 6.7 shows the signal constellation after converging w i t h M M A , and F i g . 6.10 shows the result w i t h L M S . T h e two figures t e l l us that even t h o u g h we can achieve i n i t i a l convergence w i t h the b l i n d a l g o r i t h m , we have to rely on the L M S a l g o r i t h m to o b t a i n the o p t i m u m steady-state performance. F i g . 6.8 shows the converged constellation w i t h the halfconstellation W M M A , a n d F i g . 6.9 shows the constellation o b t a i n e d w i t h the edge-point W M M A . T h e convergence performance is i m p r o v e d by u s i n g the half-constellation W M M A , a n d is further improved by using the edge-point W M M A . F r o m F i g s . 6.9 a n d F i g . 6.10, we see that almost the 94 same steady-state convergence performance is achieved by using the edge-point W M M A a n d the L M S algorithms. N o t e that the step size used for the edge-point W M M A is about five times larger t h a n for the other algorithms. T h e use of w i n d o w e d M M A , especially edge-point W M M A , is l i m i t e d to a p p l i c a t i o n s w i t h a l i m ited number of s y m b o l levels. T h e number of edge points i n a signal constellation is p r o p o r t i o n a l to the number m of s y m b o l levels, a n d the number of signal points i n the constellation is p r o p o r t i o n a l to m . If we assume that a l l the symbols have the same p r o b a b i l i t y of occurence, then the p r o b a b i l 2 ity of sending edge points is inversely p r o p o r t i o n a l to m. T h u s , for very large signal constellations, reasonable convergence speed cannot be obtained due to the lack of a sufficient number of iterations d u r i n g filter a d a p t a t i o n . 6.3 Laboratory Experiments E x p e r i m e n t a l results are not yet available for the 155 M b / s 6 4 - C A P A T M L A N a p p l i c a t i o n . H o w ever, the basic M M A b l i n d e q u a l i z a t i o n a l g o r i t h m has recently been i m p l e m e n t e d i n real time o n two different l a b o r a t o r y experimental setups for two other applications. T h e first experimental setup implements the 51.84 M b / s 1 6 - C A P transceiver specified by D A V I C i n [5] for F T T C networks. T h e second e x p e r i m e n t a l setup implements several a s y m m e t r i c d i g i t a l subscriber line ( A D S L ) transceivers, w h i c h use a variety of signal constellations a n d provide d a t a rates i n the megabit per second range. . I n b o t h cases, the M M A a l g o r i t h m is performing very well, a n d has demonstrated its s u p e r i o r i t y over the R C A a l g o r i t h m w h i c h was previously used. Experimental comparison w i t h C M A has not been done yet. T h e e x p e r i m e n t a l results presented here are for the e x p e r i m e n t a l 51.84 M b / s 1 6 - C A P transceiver specified by D A V I C . T h i s transceiver has to operate i n a n environment that is m u c h harsher t h a n the A T M L A N environment, a n d t h e experimental results described here reflect this fact. Specifically, this a p p l i c a t i o n requires the usage of a decision feedback equalizer ( D F E ) , w h i c h is more complex t h a n the linear equalizer considered i n the rest of this thesis, a n d is also significantly more difficult to t r a i n b l i n d l y . A s a result, since they were available, we decided to also show some experimental results obtained w i t h a D F E . T h i s D F E uses M M A for the convergence of the feedforward filter, 95 10 i 1 8 *• 6 A- ». 4 4" •3*' ft 2 GC < Z & 0 (3 < •Sr- A- ••• -2 -4 -6 -8 i -10 -10 0 REAL 10 F i g u r e 6.7: After convergence w i t h M M A 10 8 6 1 * *• .ft" •* •T 4 > cc 1 ¥• *• 2 •it o < - •* •ft > *• -2 *• -4 -6 #•• •ft -8 < -10 -10 > -5 0 REAL 5 F i g u r e 6.8: After convergence w i t h half-constellation 96 10 WMMA 10 8 6 T > 2 Mf * < .* < *: ~ * * * * 4 * * * * * * •* -6 •*- * If *- * V -2 -4 » « •"ft * * * * * * -8 -10 -10 -5 0 REAL 5 F i g u r e 6.9: After convergence w i t h edge-point 10 * * * 6 cr < * 2 * * it it • ¥. < 2 * * * ft •* * * «i» *• -10 -10 * * * '¥ •4 A * o < WMMA 1 8 4 10 -5 0 REAL 5 F i g u r e 6.10: After convergence w i t h L M S a l g o r i t h m 97 10 1000'24 AWG-UTP cable BALUN — • tone gen. — * combiner line samples 38.88 MHz FIFO (chip) tap updates 10 KHz DSP16 (25 MHz) computing clock 60-80 MHz • f— • •• • • •• • •• •• •• •• IBM Compatible oscilloscope / spectral analyzer F i g u r e 6.11: D S P 16 setup i n lab experiment as described i n [30]. T h e purpose for showing these results is that they highlight another major advantage of M M A over b o t h R C A a n d C M A , w h i c h is the fact that M M A c a n readily be used w i t h a D F E , whereas the two other algorithms cannot. I n one of the experiments described later, M M A was able to open the eye for the D F E under extremely severe conditions of channel impairment and interference, whereas R C A was completely unable to do so. 98 \ 6.3.1 Testing Environment F i g . 6.11 shows the real-time and real w o r l d D S P setup used i n the laboratory. I n this setup, signals are t r a n s m i t t e d over a 1000 foot 24 A m e r i c a n wire gauge ( A W G ) - U T P cable. W h e n a noisy environment is simulated for R F interference, a single tone generator is connected to the receiver t h r o u g h a balance/unbalance ( B A L U N ) connector a n d a combiner. T h e receiver is p a r t i t i o n e d into two m a i n blocks. O n e consists of two very fast F I R filter chips, w h i c h implement a T / 3 F S L E whose inputs are taken from the A / D at the s a m p l i n g rate of 38.88 M H z , a n d the o u t p u t s are c o m p u t e d at the s y m b o l rate of 12.96 M H z . T h e second block consists of a first-in-first-out ( F I F O ) chip and a D S P chip from L u c e n t Technologies called D S P 1 6 . These devices are used to implement the tap u p d a t i n g algorithms at a rate w h i c h is m u c h lower t h a n the s y m b o l rate. T h e i n p u t of the F I F O chip is connected to the A / D w h i c h generates real w o r l d line samples at 38.88 M H z . T h e outputs of the F I F O chip are sent to the D S P 1 6 b o a r d w h i c h is monitored by a n I B M - c o m p a t i b l e computer. T h e filter taps are u p d a t e d i n the D S P 16 b o a r d w h i c h has a master clock of 6 0 ~ 8 0 M H z . T h e tap coefficients are then downloaded to the real-time F I R chips at a rate of 10 k H z . I n this chip, the o u t p u t of the equalizer, y n = c^r , n is c o m p u t e d at the s y m b o l rate of 12.96 M H z for 1 6 - C A P . These o u t p u t s of the F I R filter are sent to a n oscilloscope a n d a spectral analyzer to display the signal constellation a n d frequency response of the equalizer. 6.3.2 Experimental Results In these experiments, we have tested M M A i n several environments: M M A w i t h no additive noise, M M A w i t h a single tone R F interferer a n d M M A w i t h noise a n d w i t h D F E . F i r s t , w e tested M M A w i t h no additive noise. F i g s . 6.12 (a) t h r o u g h (e) show the e x p e r i m e n t a l results obtained w i t h this test. T h e i n i t i a l signal constellation w i t h o u t e q u a l i z a t i o n is shown i n F i g . 6.12 (a). F i g s . 6.12 (b) t h r o u g h F i g . 6.12 (d) show the constellations at 10 sec. intervals d u r i n g b l i n d convergence. F i g . 6.12 (e) gives the steady-state convergence w i t h the L M S a l g o r i t h m . Note that we use 10 secend interval i n order to take photos of convergence. E x p e r i m e n t s show that R C A has a similar performance to that of M M A , a n d these results are not shown here. It s h o u l d be pointed out that speed of convergence was slowed d o w n on purpose, so that good pictures could be 99 taken. T h e targeted convergence time for p r o d u c t s is less t h a n one second. T h e n we tested the M M A b l i n d a l g o r i t h m w i t h noise. A single tone R F interferer is injected into the channel as shown i n F i g . 6.11. F i g . 6.13 displays the spectra of the signal a n d this interference, when S N R « 0 d B a n d the noise is centered at 5 M H z . We tested two linear b l i n d equalization algorithms w i t h the single tone R F interferer. F i g . 6.14 (a) shows the signal constellation w i t h M M A at 10 sec. intervals a n d F i g . 6.14 (b) shows the steady-state performance. F i g . 6.14 (c) t h r o u g h F i g . 6.14 (e) show the convergence w i t h R C A at 10 sec. intervals. C o m p a r i n g the two groups of tests w i t h M M A and R C A , we can see that M M A has a faster convergence rate and has better convergence performance. It shows that M M A can achieve more reliable convergence t h a n R C A i n the presence of noise. However, these results also demonstrate that a n F S L E is not well e q u i p p e d to handle R F interference as c a n be seen from the b a d steady-state eye openings i n F i g . 6.14. T h i s explains the need to use a decision feedback equalizer ( D F E ) consisting of a feedforward linear equalizer and a feedback filter. T h e details of operation of the D F E are given i n [30]. T h e tap u p d a t i n g a l g o r i t h m uses M M A for the feedforward filter a n d a 16-point slicer for the feedback filter. W e show the b l i n d convergence performance i n F i g . 6.15 (a) t h r o u g h F i g . 6.15 (b). F i g . 6.15 (c) shows the steady-state convergence w h e n the equalizer uses the L M S a l g o r i t h m a n d the D F E . C o m p a r i n g Figs. 6.12 (e) a n d F i g . 6.15 (c), we can see that almost the same convergence performance is achieved, where the former figure shows M M A w i t h no noise a n d the latter one shows M M A w i t h D F E i n the presence of a single tone R F interferer. N o results are shown for R C A , because R C A is not able to converge w h e n the D F E is used. 6.4 Remarks Various M M A a l g o r i t h m s have been tested for several applications. W e conclude from these numerous tests that M M A a n d its generalized a l g o r i t h m s can achieve i m p r o v e d b l i n d convergence. We first made a convergence comparison between R C A a n d M M A . For the A T M L A N a p p l i c a t i o n , the equalizer converges faster w i t h M M A t h a n w i t h R C A . M M A is very well suited to difficult applications, such as applications using high-order constellations. I n contrast, the use of the four- 100 (e) F i g u r e 6.12: D S P test: M M A w i t h o u t noise 101 F i g u r e 6.13: T r a n s m i t t e d signal w i t h R F interference point constellation l i m i t s the use of R C A to simple applications. M M A ' s usefulness has been demonstrated for the 6 4 - C A P A T M L A N , 1 6 - C A P F T T C a n d C - C A P A D S L applications, and w i l l be incorporated i n future systems for these applications. Table 6.2 gives our recommendations for the type of b l i n d equalization algorithms that should be used for various C A P applications. T w o more comments w o u l d be pointed out as following. One comment is about applications. I n this thesis, the use of M M A is l i m i t e d to C A P applications, however, the a l g o r i t h m is also appliable to Q A M applications i n terms of b l i n d start-up. A n o t h e r comment is given regarding to ISI. We 102 103 4-CAP 16-CAP 32-CAP 64-CAP 128-CAP 256-CAP 512-CAP RCA MMA MMA MMA/WMMA* MMA GMMA GMMA * W M M A s h o u l d be used i f speed of convergence has to be improved. Table 6.2: Choices of b l i n d e q u a l i z a t i o n algorithms have proved ISI free for M M A i n C h a p t e r 3. G M M A a n d W M M A also have ISI free property a n d the proofs are not i n c l u d e d i n this thesis. 104 F i g u r e 6.15: D S P test: M M A w i t h R F interference and D F E 105 106 Chapter 7 Conclusions In this thesis, we have proposed a n i m p r o v e d b l i n d a l g o r i t h m , called M M A , a n d several other algorithms w h i c h are extensions of M M A . T h e contents of C h a p t e r 3 t h r o u g h C h a p t e r 5 give a detailed study of these algorithms, a n d C h a p t e r 6 provides computer s i m u l a t i o n a n d e x p e r i m e n t a l results w h i c h confirm the theoretical results o b t a i n e d i n the previous chapters. I n this chapter, we summarize the contributions, present the e x i s t i n g problems, a n d suggest further work. 7.1 Contributions Several b l i n d algorithms have been studied. T h e most c o m m o n l y used are R C A a n d C M A . However, b o t h algorithms cause some problems. R C A is simple to implement, but it often converges to wrong solutions, whereas C M A is i m m u n e to most w r o n g solutions but is expensive because it requires the a d d i t i o n of a rotator i n the steady-state mode of operation. B a s e d on these considerations, we have proposed a new a l g o r i t h m called M M A to achieve better convergence r e l i a b i l i t y t h a n R C A , a n d less c o m p l e x i t y t h a n C M A . T h e m a i n feature of M M A is the use of m u l t i p l e m o d u l i w h i c h makes it much more flexible t h a n R C A a n d C M A to accommodate a variety of different signal constellations. In this thesis, we have used m u l t i p l e m o d u l i for two different reasons. F i r s t , several m o d u l i are required for nonsquare constellations, for w h i c h different subsets of symbols have different statistics. M u l t i p l e m o d u l i are also required for applications w i t h high-order constellations w h e n one constant is not sufficient to represent the statistics of the symbols i n a meaningful way. I n summary, the use of m u l t i p l e m o d u l i provides a means to solve problems w h i c h c o u l d not be h a n d l e d by t r a d i t i o n a l b l i n d algorithms. W e summarize the contributions of the thesis as follows. 1. A n i m p r o v e d b l i n d equalization a l g o r i t h m , called M M A , has been proposed [29] [30]. For most s t a n d a r d b l i n d algorithms, such as R C A a n d C M A , o n l y one m o d u l u s is used d u r i n g b l i n d convergence. M M A makes use of several m o d u l i w h i c h allows it to deal w i t h more c o m p l i c a t e d applications t h a n is feasible w i t h s t a n d a r d b l i n d algorithms. T h e use of m u l t i p l e m o d u l i is more effective for nonsquare constellations, w h e n the t r a n s m i t t e d symbols have different d i s t r i b u t i o n s , a n d leads to a r e d u c t i o n of w r o n g solutions, such as the 144-point s o l u t i o n for the 1 2 8 - C A P a p p l i c a t i o n [30]. E v e n for square constellations, the use of M M A has some advantages. I n c o m p a r i s o n to R C A , M M A is more reliable a n d provides a better speed of convergence because it uses higher-order statistics. E v e n t h o u g h the i m p l e m e n t a t i o n of the a l g o r i t h m is more c o m p l i c a t e d t h a n that of R C A , the cost can be reduced i f a power-of-two m u l t i p l i e r c a n be used [6]. A l s o , M M A is more powerful t h a n C M A , because it c a n compensate for linear phase, w h i c h cannot be done w i t h C M A . A l t h o u g h M M A provides more r e l i a b i l i t y for i n i t i a l convergence t h a n R C A , the p r o b a b i l i t y of converging to w r o n g solutions s t i l l exists, T h i s can be i m p r o v e d by using other techniques w h i c h are less expensive to implement t h a n the rotator required by C M A [30]. 2. T h e usage of M M A requires the c a l c u l a t i o n of a constant R, w h i c h is a statistical function of the symbols a . n is tedious. R c a n be d i r e c t l y c o m p u t e d from the symbols a , n but this approach I n this thesis, we have derived a closed-form expression for the constant R as a function of the number m of s y m b o l levels. T h i s makes the c a l c u l a t i o n of R very simple. Details o n the c o m p u t a t i o n of s y m b o l moments a n d the constants R used for R C A , C M A , and M M A are p r o v i d e d i n A p p e n d i x B . These closed-form expressions for R make the a n a l y t i c a l investigations of cost functions easier. 3. A n analysis of the cost functions used for b l i n d algorithms has been presented. There is a major difference between the behavior of the L M S a l g o r i t h m a n d the b l i n d algorithms discussed here. T h e error used i n the L M S tap u p d a t i n g a l g o r i t h m essentially goes to zero for 107 a long-enough equalizer and w h e n there is l i t t l e noise i n t r o d u c e d i n the channel. A s a result, the cost function m i n i m i z e d by the L M S a l g o r i t h m , i.e. the M S E , also goes to zero. With b l i n d equalization, the error used by the tap u p d a t i n g a l g o r i t h m a n d the m i n i m u m of the corresponding cost function do b o t h not go to zero. T h e result is that the values of the tap coefficients keep fluctuating even i n steady-state operation. These tap fluctuations introduce r a n d o m noise at the output of the equalizer a n d affect the q u a l i t y of the eye opening. O u r research has shown that the q u a l i t y of the eye o p e n i n g achievable w i t h b l i n d equalizat i o n is a direct function of the m i n i m u m value of the corresponding cost function. T h a t is, s m a l l values of this m i n i m u m result i n good eye openings a n d large values results i n b a d eye openings. It has also been found that the m i n i m u m value of the cost function is a n increasing function of the number of s y m b o l levels used i n the signal constellation, a n d this holds for a l l the b l i n d e q u a l i z a t i o n algorithms discussed here. T h e preceding results led to the design of new, enhanced M M A cost functions h a v i n g s m a l l m i n i m u m values even for a large number of s y m b o l levels. 4. T h e cost function analysis led us to the p r o p o s a l of G M M A as a means to improve the equalizer's b l i n d convergence performance for applications using a high-order signal constellation. T h i s is done by u s i n g several constants R i n the cost function rather t h a n just one. The dispersion of subsets of output samples of the equalizer a r o u n d each of the m o d u l i R is then m i n i m i z e d . B y p r o p e r l y choosing the various m o d u l i it is possible to significantly reduce the m i n i m u m of the cost function, even for high-order signal constellation. A n iterative a l g o r i t h m , w h i c h uses a n equal-energy type of c r i t e r i o n , has been proposed to compute the o p t i m u m values for the various constants R. T h e convergence performance of G M M A has been tested for the 2 5 6 - C A P a p p l i c a t i o n , a n d the computer s i m u l a t i o n results have demonstrated the v a l i d i t y of the concept. 5. T h e last enhancements of M M A proposed i n this thesis are various forms of windowed algor i t h m s called W M M A . These algorithms also use cost functions w h i c h have reduced m i n i m u m values. W M M A o n l y uses one constant R i n the cost function, as is done w i t h standard M M A , 108 but the a l g o r i t h m does not use a l l the o u t p u t samples of the equalizer. I n one i m p l e m e n t a t i o n of W M M A , o n l y the outer half of the signal constellation is u t i l i z e d . In a n alternative approach, o n l y the edge points of the signal constellation are u t i l i z e d . B o t h approaches provide convergence improvements over the standard M M A for the 6 4 - C A P a p p l i c a t i o n . For denser constellations, W M M A , especially edge-point W M M A , suffers from the fact that o n l y infrequent tap updates are performed, a n d convergence time can be unacceptably long. 7.2 Future W o r k B l i n d e q u a l i z a t i o n algorithms face two major problems, w h i c h are: a) to provide a g o o d i n i t i a l eye o p e n i n g so that the receiver can s w i t c h r e l i a b l y to the L M S algorithm, and b) to avoid converging the equalizer to w r o n g solutions. 1. T h i s thesis has m o s t l y concentrated o n issue a) above, a n d several new b l i n d equalization algorithms, w h i c h achieve the desired goal for signal constellations w i t h up to 256 points, have been presented, analyzed, a n d tested t h r o u g h computer simulations. However, even G M M A , the most powerful a l g o r i t h m , has not been very effective w i t h transceivers u s i n g signal constellations w i t h more t h a n 512 points. Investigating cost functions w h i c h can be used for these very dense signal constellations is one possible topic of future work, 2. Issue b) above has o n l y been briefly mentioned i n this thesis, but has also been the subject of intense research, w h i c h is documented elsewhere [30]. M M A is more reliable t h a n R C A , but occasionally it can s t i l l converge the equalizer to w r o n g solutions. C o m p u t e r simulations have shown t h a t the technique proposed i n [30] solves this p r o b l e m . However, no a n a l y t i c a l investigations have been conducted so far to provide some theoretical foundations for the techniques. T h i s c o u l d be another topic for future work. 3. T h e relationship between the steady-state M M A cost function a n d the M S E has been discussed i n A p p e n d i x C . Some s i m p l i f y i n g assumptions were made i n the analysis presented 109 there. O n e possible research topic is a more general analysis w h i c h does not use some of the assumptions. 4. O u r study of b l i n d e q u a l i z a t i o n has shown that m a n y factors influence the i n i t i a l speed of convergence of the equalizer. T y p i c a l examples are: type of b l i n d algorithms; order of the statistics used by the a l g o r i t h m , equalizer structures; equalizer design parameters, such as step size, number of taps, a n d type of signal constellation; type of channel i m p a i r m e n t s a n d additive interference; and so forth. G i v e n a l l these variables, the s t u d y of the i n i t i a l convergence of b l i n d equalizers is believed to be a major u n d e r t a k i n g , a n d it is not s u r p r i s i n g that this topic has not been addressed yet i n the literature. However, it c o u l d , potentially, be a very fruitful research topic. 5. T h e M M A a l g o r i t h m has been implemented o n two e x p e r i m e n t a l setups i n the lab. T h i s w i l l allow real-time testing of the a l g o r i t h m under channel i m p a i r m e n t and noise conditions w h i c h cannot be easily s i m u l a t e d o n the computer. Some new research topics may evolve from these experiments. 110 Appendix A: Shaping Filter T h e A T M L A N 6 4 - C A P s t a n d a r d specifies square-root raised cosine shaping filters for the transm i t t e r [1]. T h e i m p u l s e response g(t) of a square-root raised cosine baseband filter is given by . . 9 { t ) where t' = t/T. a)t'} + 4at' sin[ir(l - COS[TT(1 + a)t'} l n . 1 ^ [ 1 - (4a*') ] = 2 T h e corresponding transfer f u n c t i o n is given by 0 < | / | < 2^(1 - a ) G(f) = { 2T(l - a) < | / | < ^ ( l + a) ^ ^ l - s i n f (f-± I V2 where the excess b a n d w i d t h is a = 0.15 a n d the s y m b o l rate is 1 / T = 25.92 M b a u d . T h e s a m p l e d values of the i m p u l s e responses of the in-phase a n d quadrature passband s h a p i n g filters are given by s(iT') = g(iT') COS(2TTf iT') s(iT') = g{iT') s i n ( 2 7 r / i T ' ) c where the center frequency is f c c (0.2) = 15 M H z , a n d the s a m p l i n g rate is 1 / T ' = 77.76 M H z . T h e impulse responses for the two s h a p i n g filters are p l o t t e d i n F i g . 1.9. F i g . 1.10(a) shows the filters' frequency response i n baseband, a n d F i g . 1.10(b) gives the filters' frequency response i n passband. Ill Appendix B: Calculation of the Constant R " T h i s a p p e n d i x presents the derivation of closed-form expressions for the various constants R used i n the R C A , C M A , a n d M M A algorithms. A s w i l l be shown, these expressions c a n be conveniently expressed as a function o f the number m of s y m b o l levels. T h e general approach used to compute the constant R w i l l be explained for the M M A a l g o r i t h m . Constant R T h e generalized form of M M A uses t h e following cost function . CF = E[{\y \ -R ) L L + (\y \ -R ) ]] 2 L n where y and y n n and b n a n d y , we have i £ [ | l / | ' ] = £ J [ | y | ] . F o r t w o - d i m e n s i o n a l C A P systems, i n n (0.3) 2 represent the equalizer's o u t p u t samples, a n d L is a positive integer. A s s u m i n g the same statistics for y a L n n L n n represent the t r a n s m i t t e d symbols for the in-phase a n d quadrature phase channels, respectively. W h e n a n equalizer converges, y —> a a n d y —> b , a n d t h e cost function becomes n CF = E[(\a \ n n n - R ) + {\b \ - R ) }] L L n 2 L L (0.4) 2 n A s s u m i n g the same statistics for a a n d b , we have £ J [ | a | ] = Ufl&nl ']. I n the following, only the L n n 1 n analysis for the in-phase channel w i l l be p r o v i d e d . T h e same analysis applies to the quadrature phase channel. F o r the in-phase d i m e n s i o n , the gradient of the cost function i n (0.3) w i t h respect to t h e real t a p vector was previously given i n (3.24), a n d is repeated here V = 2LE[(\y \ - R )\y \ - y r ] L c L l n n (0.5) 2 n n T h e constant R c a n now be evaluated b y assuming a perfect equalization , i.e., y n —> a , a n d by n setting the gradient V to zero. A l s o , i f we assume that different symbols are uncorrelated, we get c E[a r ] n n = k-Eja ,], where k is a fixed vector whose entries are a function o f the channel. W e then 2 get from (0.5) E[(\a \ L n - R )|a | - a r ] = 0 L L J 2 n n n k*£?[(|a | -ii )| | - a2] = 0 i n L a n 112 L 2 (0.6) (0.7) E[(\a \ \a \ - a L n L 2 - R \a \ - a ] 2 n L n E[(\a \ \a \ - a ] L n S o l v i n g for R L L 2 2 = 0 2 n - R E[\a \ - a ] 2 n L n L n L n 2 2 n (0.8) = 0 (0.9) we get _ E[\a \ ^ a ] 2 L U m 2 n m _ 2 n E[\a \^al] a E[af] E[\a \L] n ^ n B y using the same m e t h o d , we o b t a i n the following expression for the constant R L i U j used for gener- alized C M A _ L c m E[\A \ ] 2L n t E[\A \ ] a L ' [ n a n d for R C A Rrea = i^] - (0 12) N o t e that R C A is a second-order statistics a l g o r i t h m , a n d does not have a generalized form. T h e constant R has been derived for three b l i n d algorithms. I n practice, L = 2 is c o m m o n l y chosen, i n w h i c h case the constants R are given by c m E[\A \ } a 2 ' ( n o2 _ E \ n] a l n 1 4 \ E[a \ n -m We see that the constants R are the statistical functions of the symbols A <ai5) n Square or a. n Constellations T h e expressions derived for the constants R i n the previous section are functions of the moments of the symbols A n and a . n These moments can be c o m p u t e d o n a n i n d i v i d u a l basis, a l t h o u g h this could be tedious. For the u s u a l case where the symbols have o d d integer values it is possible to derive simple closed-form expressions for the constants as a function of the number of s y m b o l levels. A s s u m e that the symbols takes the following values used by C - C A P system, {a } = { ± l , ± 3 , . . . , ± ( 2 m - l ) } • n 113 (0.16) where m indicates the number of s y m b o l levels. If C indicates the n u m b e r of constellation points, m can be d i r e c t l y derived from m = — (0.17) T h e following s u m m a t i o n s can be found i n [12] 2 77T (0.18) J]*. = - m ( m + l) = - m ( m + l)(2m + l) (0.19) ^A; 2 m E* 3 jfc=i m 6 * = iM^ + = fc=i i"^(^ i)] (0.20) 2 + l)(2m + l)(3m + 3 m - l ) (0.21) 2 6 U These s u m m a t i o n s do not a p p l y d i r e c t l y to sums of powers of o d d integer, b u t can be used to derive closed-form expressions for these types of s u m m a t i o n s . For example, we can w r i t e 2m—1 m £(2*-l)= £ m—1 *-2£fc = m 2 where the two sums i n the m i d d l e have been evaluated from (0.18). S i m i l a r s u m m a t i o n m a n i p u l a tions can be used for other sums o f powers of o d d integers, a n d we get m £ > n | = £(2A:-l) = m (0.22) 2 m J24 £|a„| 3 = £ ( 2 * - l ) = £ = y(4m -l) 2 2 ( (2A; - l ) = m ( 2 m - 1) 3 0. ) 2 3 (0.24) 2 k=l m E f l n = £(2A;-l) 4 = ^(4m -l)(12m -7) 2 k=i l 2 (0.25) b For square constellations, the p r o b a b i l i t y of occurence of each s y m b o l level is the same, i.e., ^ , so that the moments of the s y m b o l levels become E i n] a = ^E\ n\ Q 114 (0-26) For C M A , the constant R is a function of the moments of the complex symbols A . n the symbols a n and b n A s s u m i n g that are uncorrelated, it is easily verified that E[\A \ } = 2E[a \; 2 2 n n E[\A \ } = 2E[a ] + 2[E[a }} 4 2 n n 2 n (0.27) U s i n g the above results, the constants R for the three b l i n d algorithms can be expressed i n the following simple way as a function of m E[\A \ } _ 5 6 m 2 £[|A | ] 15 4 2 n 2 n -26 E[a ] _ 1 2 m - 7 2 2 m n m £;[a ] a _ ^ c a 5 2 _ g[a ] 2 __4m -l J5[|a„|]- 2 • 3 T h e constants R can be easily calculated for any given n u m b e r of s y m b o l levels m . 115 Appendix C: Cost Function and the Eye Opening In this a p p e n d i x we present a steady-state analysis o f the effect of the m i n i m u m value o f the M M A cost function o n the q u a l i t y o f the eye o p e n i n g or, equivalently, the M S E . T h e analysis w i l l be made for the o u t p u t of the in-phase filter c„ o f the adaptive equalizer. I n order to c a r r y t h r o u g h the analysis, we w i l l have to make some s i m p l i f y i n g assumptions. F i r s t , we w i l l assume that the receiver has knowledge of the o p t i m u m tap vector Co w h i c h eliminates ISI. T h u s , i f r n is the vector of A / D samples i n the t a p p e d delay line i n s y m b o l p e r i o d n T , the receiver can c o m p u t e c£r = a n where a n (0.28) n is the (ISI-free) s y m b o l received i n s y m b o l p e r i o d nT. I n a d d i t i o n , we assume that the receiver uses the result i n (0.28) to c o m p u t e the correction t e r m for the M M A tap u p d a t i n g a l g o r i t h m a n d then adds this t e r m to the o p t i m u m tap vector Co, so that c„ = c + / i ( a - R )a r 2 + 1 (0.29) 2 0 n n T h e o u t p u t o f the in-phase filter i n s y m b o l p e r i o d ( n + 1 ) T is t h e n c o m p u t e d as Vn+i = c£ r i + 1 (0.30) n + = c?r +v(a -R )a r r i = a 2 n+1 2 n (0.31) T n n+ + / i ( a - R )a T r 2 n+1 n (0.32) T n n+l T h e t e r m o n the right is a noisy t e r m i n t r o d u c e d by the t a p u p d a t i n g a l g o r i t h m i n (0.29), a n d is called tap a d a p t a t i o n noise. T h e process is then repeated. T h a t is, i n s y m b o l p e r i o d ( n -I- 1 ) T the receiver computes (0.28) a n d (0.29) a n d then uses (0.32) to c o m p u t e the o u t p u t sample y 2 N+ in s y m b o l p e r i o d (n -I- 2)"T. T h e scenario considered here is somewhat o p t i m i s t i c , because it assumes that the correction t e r m i n the t a p u p d a t i n g a l g o r i t h m c a n be c o m p u t e d w i t h the s y m b o l a a n d c a n t h e n be added to the n o p t i m u m tap vector C o - I n practice, the equalizer's o u t p u t sample y n t a p vector c n have to be u t i l i z e d . a n d the previously u p d a t e d T h i s more general case does not seem to be amenable to a 116 meaningful analysis. However, the results obtained w i t h the simplified analysis presented here are consistent w i t h the computer s i m u l a t i o n results. U s i n g (0.32), the M S E i n the steady-state mode of o p e r a t i o n c a n be w r i t t e n as MSE = E[(y - a )} = 2 n+1 n+1 £[(a 2 M W e now assume that the terms i n the dot product r £ r - R ) a (r£r ) ] 2 2 2 2 (0.33) 2 n n+1 i w h i c h are correlated w i t h the s y m b o l a n + n make a s m a l l c o n t r i b u t i o n t o the value o f the dot product. T h i s is generally true i f the equalizer has a large enough number o f taps. T h e M S E i n (0.33) then becomes MSE = v E[{a 2 2 n (0.34) R ) a ]E[{T T ) ] 2 2 T 2 2 n n n+l where the t e r m o n the right is a channel-dependent constant. Since we have 2m — 1 = M > \a \ > 1, n it i m m e d i a t e l y follows that M E[(a 2 2 - R ) ] > E[(a - R ) a ) 2 n 2 2 2 2 > E[(a 2 n 2 n - R)] 2 n (0.35) 2 R e p l a c i n g (0.35) i n (0.34) we get the following upper a n d lower bounds for the M S E : nM E[{a 2 2 - R ) ]E[{T r ) } 2 n 2 T > MSE > » E[(a 2 n 2 n+l 2 n - fl ) ]£[(r£r ) ] 2 2 2 n+1 (0.36) T h e following discussion w i l l concentrate o n the lower b o u n d o f the M S E . M i n i m i z a t i o n o f the expression o n the right i n (0.36) c a n be done b y decreasing either the step size /u or the quantity E[{a - R ) ], 2 2 2 n w h i c h is the m i n i m u m of the M M A cost function. T h e other t e r m i n (0.36) i n the p r o d u c t is not dependent o n the design parameters o f the M M A a l g o r i t h m , a n d thus cannot be m a n i p u l a t e d to m i n i m i z e the M S E . T h i s term, w h i c h is the dot p r o d u c t of vectors of A / D samples, can be considered to be a constant, because the receiver uses a n A G C . T h i s is not the case for the other terms. A n expression for the value o f the m i n i m u m of the M M A cost function is given i n (4.14) w h i c h is repeated here E[(a 2 -i? ) ] = ^(12m -19m 75 2 n 2 4 2 + 7) (0.37) where m is the number of levels ( i n magnitude) of the symbols a . T h i s is obviously a n increasing n function of m . T h u s , i f m increases the lower b o u n d for the M S E i n (0.36) also increases i f the step 117 size / i stays constant. O n e way of keeping the b o u n d constant w o u l d be to make /J, variable and equal to H = BE- [{a -R ) ] 2 l 2 2 ' 2 n where /3 is a constant. (0.38) S u c h a choice is not desirable or feasible for large m , as shown i n Table 0.1, w h i c h gives the value of the step size w h i c h keeps the M S E constant. F i r s t notice that the C-CAP 4-CAP 16-CAP 64-CAP 256-CAP 1024-CAP m 1 2 4 8 16 0 26.24 592 10,228 166,736 - 3.0 x 1 0 - - 2" E[(a 2 n R)) 2 2 1.7 x 1 0 ~ 2 2~ 5 9 3 9.8 x 1 0 ~ 2 5 6.0 x 1 0 ~ 6 2-17 -13 T a b l e 0.1: Step sizes for C - C A P m i n i m u m of the M M A cost function takes very large values w h e n m becomes large. N o t i c e also that there is a difference of almost four orders of m a g n i t u d e between the step sizes required for 1 6 - C A P a n d 1 0 2 4 - C A P i f one wants to keep the b o u n d o n the M S E constant. Speed of convergence of the equalizer is (roughly) p r o p o r t i o n a l to the value of the step size. T h u s , i f it takes about one second to converge w i t h 1 6 - C A P , it w o u l d take minutes to achieve the same w i t h 1 0 2 4 - C A P , w h i c h is unacceptable. T h e last row i n the table gives the power of two \i* w h i c h is the closest to the c o m p u t e d value of \x. N o t i c e that this q u a n t i t y decreases from 2 - 5 for 1 6 - C A P to 2 ~ 1 7 for 1 0 2 4 - C A P . I n practice, this means that the d i g i t a l precision required for the 1 0 2 4 - C A P tap u p d a t i n g a l g o r i t h m w o u l d be about 12 bits larger t h a n w h a t is required for 1 6 - C A P . T h i s , again, w o u l d not be acceptable for m a n y applications. 118 119 Bibliography [1] "The A T M 155.52 Mb/s Physical Layer Specification for Category-3 Unshielded Twisted Pair", ATM Forum Spefication, 1995 [2] Benveniste, A., and Goursat, M . , "Blind Equalizers", IEEE Trans. Commun., Vol. 32. No. 8, pp. 871-883, 1984 [3] Benvenuto, N . , and Goeddel, T. W. "Classification of Voiceband Data Signal Using the Constellation Magnitude", IEEE Trans. Commun., Vol. 43. No. 11, pp. 2759-2770, 1995 [4] Chen, W. Y., Im G. H. and Werner J. J., "Design of Digital Carrierless A M / P M Transceiver", ANSI Contribution T1E1.4/92-149, Aug. 1995 [5] "Lower Layer Protocol and Physical Interferace", DAVIC 1.0 Specification Part 08 [6] Duttweiler, D. L., "Adaptive Filter Performance with Nonlinear in the Correlation Multiplier", IEEE Trans. Acoustic, Speech and Signal Processing, Vol. ASSP. 30, No. 4, 1982 [7] Foschini, G. J., "Equalizing without Altering or Detecting Data", AThT Tech. J., Vol. 64, No. 8, pp. 1885-1911, Oct. 1985 [8] Gitlin, R. D., and Werner, J. J., "Blind Equalizer Tap-Adjustment Algorithm for Quadrature Amplitude Modulation Data Transmission", Bell Laboratories Engineer's Notes, Oct. 19, 1979 [9] Gitlin R. D., Hayes, J. F., and Weinstein, S. B., Data Communications Principles, Plenum Press, 1992 [10] G o d a r d , D . N . , " M e t h o d a n d Device for T r a i n i n g a n A d a p t i v e E q u a l i z e r by M e a n s of a n U n k n o w n D a t a S i g n a l i n a Q A M T r a n s m i s s i o n S y s t e m " , U.S. Patent 4 227 152, O c t . 7, 1980 [11] G o d a r d , D . N . , "Self-Recovering E q u a l i z a t i o n a n d C a r r i e r T r a c k i n g i n T w o - D i m e s i o n a l D a t a C o m m u n i c a t i o n S y s t e m " , IEEE Trans. Commun., V o l . 28, N o . 11, p p . 1867-1875, N o v , 1980 [12] G r a d s h t e y n , I. S. a n d R y z h i k , I. M . Table of Integrals, Series, and Products, A c a d e m i c Press, 1994 [13] H a r m a n , D . D . , H u a n g , G . , N g u y e n , M - H . , Werner, J . J . , a n d W o n g , M . K . , " L o c a l D i s t r i b u t i o n C A P for I M T V " , IEEE Multimedia, V o l . 2, N o . 3, p p . 14-23, 1995 [14] H a y k i n , S., Communication Systems, J o h n W i l e y & Sons,1994 [15] H a y k i n , S., Adaptive Filter Theory, Prentice H a l l , 1996 [16] H a y k i n , S., Blind Equalization, Prentice H a l l , 1996 [17] I m , G . H . , H a r m a n D . D . , H u a n g , G , M a n d z i k , A . V . , N g u y e n , M . - H . , a n d Werner, J . J . , "51.84 M b / s 1 6 - C A P A T M L A N S t a n d a r d " , IEEE J. Selected Areas Commun., V o l . 13, N o . 4 , pp. 620-632, 1995 [18] I m , G . H . a n d Werner, J . J . , "Bandwidth-Efficient D i g i t a l T r a n s m i s s i o n over U n s h i e l d e d T w i s t e d - P a i r W i r i n g " , IEEE J. Selected Areas Commun., V o l . 13, N o . 9 , p p . 1643-1655, 1995 [19] J a b l o n , N . K . , "Joint B l i n d E q u a l i z a t i o n , C a r r i e r Recovering, a n d T i m i n g Recovery for H i g h O r d e r Q A M S i g n a l C o n s t e l l a t i o n s " , IEEE Trans. Signal Processing, V o l . 40, N o . 6, p p . 13831398, 1992 [20] K e n n e d y , R . A . a n d D i n g Z . , " B l i n d A d a p t i v e Equalizers for Q A M C o m m u n i c a t i o n Systems Based o n C o n v e x C o s t F u n c t i o n s " , Opt. Eng. V o l . 31, p p . 1189-1199, J u n e , 1992 [21] Lee, E . A . a n d Meserschmitt D . G . , Digital Communication, K l u w e r A c a d e m i c Publishers, 1994 120 [22] M u e l l e r , K . H . a n d Werner, J . J . " A Hardware Efficient P a s s b a n d E q u a l i z e r S t r u c t u r e for D a t a T r a n s m i s s i o n " , IEEE J. Trans. Commun. V o l . C O M - 3 0 , p p . 538-541, 1982 [23] P r o a k i s , J . G . , Communication Systems Engineering, P r e n t i c e - H a l l , 1994 [24] Sato, Y . , " A M e t h o d o f Self-Recovering E q u a l i z a t i o n for M u l t i l e v e l A m p l i t u d e - M o d u l a t i o n Systems", IEEE Trans. Commun., pp. 679-682, J u n e 1975 [25] S h a l v i , O . , a n d W e i n s t e i n , E . , " N e w C r i t e r i a for B l i n d D e c o n v o l u t i o n of N o n m i n i m u m Phase Systems (Channels)", IEEE Trans, on Information Theory, V o l . 36, N o . 2, M a r . , 1990 [26] Tugnait, J . K . , "Identification o f L i n e a r Stochastic Systems v i a Second a n d Fourth-order C u mulant M a t c h i n g " , IEEE Trans. Inform. Theory, V o l . I T - 3 3 , p p , 393-407, M a y 1987 [27] Werner, J . J.,Tutorial on Carrierless AM/PM-Part II, A N S I C o n t r i b u t i o n T1E1.4/93-058, 1993 [28] W i d r o w B . a n d S t r e a m s S. D . , Adaptive Signal Processing. P r e n t i c e - H a l l Inc., 1991 [29] Y a n g , J . , Werner, J . J . a n d D u m o n t G . A . , " T h e M u l t i m o d u l u s B l i n d E q u a l i z a t i o n A l g o r i t h m " , Accepted for publication at DSP97, S a n t o r i n i , Greece, 1997 [30] Y a n g , J . , Werner, J . J . , " B l i n d E q u a l i z a t i o n " , Technical Memorandum, B e l l M a y 1996 121 Laboratories,
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Multimodulus algorithms for blind equalization
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Multimodulus algorithms for blind equalization Yang, Jian 1997
pdf
Page Metadata
Item Metadata
Title | Multimodulus algorithms for blind equalization |
Creator |
Yang, Jian |
Date Issued | 1997 |
Description | In bandwidth-efficient digital transmission, the training of a receiver requires a start-up procedure. This start-up includes the three steps of setting the automatic gain control, recovering timing, and converging the adaptive filters. For many applications, start-up is facilitated by using a known training sequence, which can be used as an ideal reference by the receiver. However, sometimes the use of a training sequence is not feasible or not desirable. In this case, start-up has to be done blindly. The most challenging aspect of blind start-up is the convergence of the adaptive equalizer. This function is called blind equalization. Without ideal reference, the receiver has to make decisions about what data have been transmitted. Normally we use a decision device to make the assumptions on the input signals. This decision device is also called a slicer. These decisions are highly unreliable because the received data are corrupted by intersymbol interference due to distortion introduced by the communication link. As a result, the equalizer does not converge with the conventional least mean square (LMS) algorithm because the probability of wrong decisions is too high. The requirement for reducing wrong decisions leads to the development of blind algorithms. Several algorithms were developed in the past for blind equalization. The two most common ones are the constant modulus algorithm (CMA) and the reduced constellation algorithm (RCA). Both algorithms have been successfully used in many practical applications in data communications. However, improved blind algorithms are still in demand in order to meet the requirements of high data rate communications, where the implementation of blind equalization is required to be simple and reliable. RCA is simple to implement but is not very reliable. CMA is very reliable but has a high complexity., In this thesis, an improved blind algorithm, called multimodulus algorithm (MMA), is proposed. This new algorithm is more reliable than RCA and less complex than CMA. Blind algorithms, such as RCA or CMA, do not take full advantage of the knowledge of the statistics of the data signal, because they only use one statistical quantity, called modulus, during blind convergence. In contrast, MMA makes better usage of the knowledge of the statistics of the data signal and employs multiple moduli to achieve initial convergence. The use of multiple moduli makes MMA very flexible and easily adaptable to applications using two-dimensional transmission schemes with nonsquare or very dense signal constellations. Both RCA and CMA are not very effective for these types of applications. Most blind equalization algorithms minimize a cost function. Our investigation has shown that the minimum (residual) value of this cost function has a great influence on the reliability and speed of convergence of the corresponding blind algorithm. For example, for CMA, RCA and MMA, this residual value increases when the bandwidth efficiency of the transmission system increases, and the blind algorithms suffer a corresponding decrease in performance. Two generalized versions of MMA are proposed to circumvent the above problem. One is called generalized MMA (GMMA). The basic version of MMA uses multiple moduli primarily for nonsquare constellations when nonuniform symbol distributions are utilized. Multiple moduli are also used with GMMA but the additional purpose there is to decrease the residual value of the cost function. A similar effect is achieved by using another blind algorithm, called windowed MMA (WMMA). With WMMA, only one modulus is used, but the tap coefficients of the filter are only updated with some of the data, which leads to a reduction of the residual value of the cost function. The new MMA algorithm has been extensively tested with computer simulations. Most simulation results presented here were obtained with the 155 Mb/s 64-CAP transceiver specified in the ATM LAN standard for category 3 unshielded-twisted-pair office wiring. However, our results are equally applicable to other applications, such as the 52 Mb/s 16-CAP transceiver defined in DAVIC's specification for fiber-to-the-curb networks. Some preliminary experimental results obtained in the laboratory with such a 16-CAP transceiver are presented in this thesis. The computer simulations and laboratory experiments have confirmed that the basic MMA and its generalized algorithms show improved blind convergence performance or complexity savings when compared to previously available algorithms. MMA will likely be incorporated in future broadband access systems from Lucent Technologies, and will replace RCA and CMA, which were previously used, or eliminate the need for a training sequence. |
Extent | 7392887 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-04-17 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065314 |
URI | http://hdl.handle.net/2429/7307 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1997-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1997-251918.pdf [ 7.05MB ]
- Metadata
- JSON: 831-1.0065314.json
- JSON-LD: 831-1.0065314-ld.json
- RDF/XML (Pretty): 831-1.0065314-rdf.xml
- RDF/JSON: 831-1.0065314-rdf.json
- Turtle: 831-1.0065314-turtle.txt
- N-Triples: 831-1.0065314-rdf-ntriples.txt
- Original Record: 831-1.0065314-source.json
- Full Text
- 831-1.0065314-fulltext.txt
- Citation
- 831-1.0065314.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065314/manifest