Title of Invention  REDUCED COMPLEXITY EQUALIZATION SCHEMES FOR ZERO PADDED OFDM SYSTEMS 

Abstract  This invention relates to a novel Equalization method for use in Zero padded OFDM systems and an equalizer system for carrying out zero forcing equalization. This method will be called the MinMax Equalization method. In particular, it relates to a reduced complexity equalization method and an equalizer for Orthogonal Frequency Division Multiplexing (OFDM) systems employing zero padding. 
Full Text  This invention relates to a novel Equalization method for use in Zero padded OFDM systems and an equalizer system for carrying out zero forcing equalization. This method will be called the MinMax Equalization method. In particular, it relates to a reduced complexity equalization method and an equalizer for Orthogonal Frequency Division Multiplexing (OFDM) systems employing zero padding. Description of Prior Art: Orthogonal Frequency Division Multiplexing: Orthogonal Frequency Division Multiplexing (OFDM), a special Multicarrier modulation scheme, which uses a large number of subcarriers, with the subcarrier spacing determined by the system design. The data bits are converted to symbols using Quadrature Amplitude Modulation (QAM) or Mary Phase Shift Keying (MPSK) or Differential Phase Shift Keying (DPSK). The resulting symbols specify the amplitude and phase of a subcarrier. This multicarrier modulation is effected in baseband by Discrete Fourier Transform (DFT) and implemented using the Inverse Fast Fourier Transform algorithm. The subcarriers are modulated in parallel thereby reducing the data rate on each of the subcarriers. This reduction in data rate on each of the subcarriers offers immunity to channel fades, impulse noise and such other impairments [1]. Further, the subcarriers overlap in frequency domain thereby utilizing the bandwidth more efficiently than the ordinary frequency division multiplexing systems. Data recovery is undertaken by imposing orthogonality to the subcarriers in time domain. OFDM is a block based technique, with each block containing the symbols modulating the various subcarriers and additional symbols used for channel estimation, synchronization and mitigation of Interblock Interference (IBI). The transmission medium or the channel usually distorts the spectrum of the transmitted signal. When such a distortion is frequency dependent, we have a Frequency Selective channel which is modelled as Finite Impulse Response (FIR) function in discrete domain. When OFDM is employed on such channels, IBI is introduced. Further, the orthogonality of the subcarriers are lost. These impairments result in a very complex data recovery process. In order to negate/ mitigate the effect of frequency selective channels and simplify the data recovery, algorithms known as Equalizers are used at the receiver. To aid the process of equalization, redundancy is added to the transmitted signal in the form of appending a few more symbols to the output of the IFFT operation. The received signal is corrupted by undesired signals emanating from components at the receiver frontend etc. These undesired components are termed as noise. As a result, the output of the equalizer is also corrupted by noise. This corrupted output is fed into a data detector, which normally uses a Maximum Likelihood (ML) decoding rule to decide on the most likely transmitted data. OFDM offers potential advantages over serial transmissions [1], [2]. It has also been adopted as a standard in applications like Cable Modems, DSL modems, Digital Audio Broadcast, Digital Video Broadcast to name a few. Equalizers for Orthogonal Frequency Division Multiplexing: OFDM uses Block Equalization techniques [2] wherein the equalizer works on present block of data. As mentioned earlier, to aid the process of equalization, a few more symbols are appended to the output of the IFFT. The number of symbols thus appended should, at least, be equal to the channel length [2]. If appended symbols are Zeros, the system is called a Zero Padded OFDM. If the last few symbols are added as a Prefix, the system is called as Cyclic Prefix OFDM. While Cyclic Prefix based OFDM systems require a very simple equalizer, symbol recovery is not guaranteed, even in the absence of noise, when the chaimel has a zero at any of the sub carrier firequencies. Equalizers which guarantee symbol recovery irrespective of the channel coefficients are called Zero Forcing Equalizers (ZFE) [2]. Clearly, the equalizers for Cyclic Prefix based OFDM systems are not ZFE. Further, their performance is poor when the channel has a zero near any of the subcarrier frequencies due to excessive enhancement of noise by the equalizer. On the other hand, the Psuedo inverse equalizer for Zero padded OFDM system [2] guarantees symbol recovery irrespective of the chaimel coefficients and also has a performance much better than that of an equalizer for Cyclic Prefix based OFDM system [3]. However, such an equalizer has a very high complexity which limits its use in practical systems [2], [4]. However, in order to improve the performance of Cyclic Prefix based OFDM systems without enhancing the complexity, there exists a need to obtain reduced complexity ZFE for Zero padded OFDM. SUMMARY OF THE INVENTION: A reduced complexity Zero Forcing Equalization method and an Equalizer based on Minimum Maximum phase factorization of the channel for use in Zero padded OFDM receiver is provided. The channel is modelled as a FIR filter and adequate zeros are padded to each OFDM block by the transmitter. The presented equalizer achieves symbol recovery in two stages, each stage involving a set of linear equations. At each stage, the set of linear equations are solved by backsubstitutions, thereby avoiding matrix inversions. Further, undue noise enhancement is minimized by the performing the equalization for the minimum phase and the maximum phase parts of the channel separately (in two stages). Accordingly, it is an object of the present invention to provide the following: Reduced complexity equalization method for the zero padded transmission that guarantees zero forcing equalization for all non zero channels, thereby providing for channel independent data recovery. Simpler equalization results in a lower complexity receiver. The receivers can handle a larger data rate, provided the system allows it. BRIEF DESCRIPTION OF THE DRAWINGS: Figure 1 Depicts a communication system employing Zero padded OFDM; Figure 2 Depicts the simplified discrete baseband equivalent of a Zero padded OFDM system; Figure 3 Depicts the Minimum Maximum Phase Decomposition of a channel with associated input and output for serial transmission; Figure 4 Depicts the Minimum Maximum Phase Decomposition of a channel with associated input and output for block transmission; and Figure 5 Depicts the proposed equalizer. Figure 6 depicts the steps in the equalization method, disclosed in the present invention DETAILED DESCRIPTION: Figure 1 details a Zero padded OFDM System. The discrete time baseband equivalent of the channel is assumed to have order L (length L +1) with coefficients {hn}Ln=0 transfer function H(z). The transmitter has the knowledge of L but has no knowledge of the channel coefficients. The transmitter contains a data source which outputs scrambled data to the Modulator. Scrambling is xmdertaken to prevent long runs of identical data and induce transitions. The modulator maps the data to the signal points chosen from a predetermined signal constellation. The signal points so chosen are complex valued in general. Let s{k) modulation onto the carrier signal. The vector x(i) is usually called the OFDM symbol. Depending upon the system requirements, additional symbols are appended to every OFDM symbol for the purpose of channel estimation and synchronization. These are not shown in Figure 1 for the sake of brevity. The resulting symbols are passed through the D/ A converter and then modulated onto the carrier of specified frequaicy. The channel is assximed to be frequency selective with L +i paths. The receiver is assumed to have a perfect knowledge of the chaimel coefficients. Further, the receiver is also assumed to be synchronized with the transmitter. These can, for example, be achieved by using pilot symbols or preamble. The received signal is downcoverted and sampled to yield the bitstream>?^w^. The S/P converter blocks N samples of y(n) at ' instance to yield j^(/) = [y{iN\ yiiN +1),..,, yiiN h AT 1)]. The equalizer uses y(i) and Figure 2 shows the simplified equivalent discrete time baseband model for a zero padded OFDM system. Note that we have not considered the IFFT and FFT operations as they are unitary and hence do not affect the noise power or the equalization. The matrices H^ and fT can be obtained fi'om [2], Due to the zero pad, the output is firee of IBI and hence the input output relation for the Zero Padded OFDM system is given by [2] MinMax Equalizer which is based on factorization of channel based on the zeros of its transfer function followed by a sequential equalization for each of the chosen factors. The complexity of this equalization is lower than the PseudoInverse based Equalizer. This equalizer has been derived in a recently published paper by the same authors [6] wherein its performance and complexity are detailed. We motivate this scheme for (1) Channel having no zeros on the unit circle, (2) A^ ?£ 0. equalization is viable only when H(z) is minimum phase. If H(z) is maximum phase, time reversed filtering is effected by a judicious choice of its input and output (see later section for details). This time reversed filtering converts the maximum phase part to minimum phase part. Hence, an approach similar to the minimum phase equalization can be used with the timereversed channel to obtain the timereversed input. This does not result in excess noise amplification as encountered in the equalization by H01 . The idea therefore is to split the channel into maximum and minimum phase parts and equalize for each of them. In the following section we shall explain the necessary details for implementing the sequential equalization. We begin by presenting the system model when channel is factorized into maximum and minimum phase parts. System Model for Factorized Channels: Comparing the z transform of unblocked signals on either side of equations (4) and (1) (noisefree case) and noting that H(z) = Hmax(z) Hmin(Z) it can be shown that, the output of the system separated into maximum and minimum phase as above {y (/)) and the one without it {y(i)) are same. Hence we use the notation y(i) instead of yout (z). From equation (4), we see the need to equalize for the minimum phase part first and then for the maximum phase part. These operations are detailed below. Equalizer for minium phase part: The order of equalization can be interchanged and equalizers for the new order can be similarly obtained. Unless specified otherwise, the order is as detailed above. Zeros on Unit circle: Adding zeros on the unit circle (say Lz of them) to Hmin or/ and Hmin(z) does not change the nonzero property of the resulting g0 and/Lmax . Hence the earlier process can max be used with modified Zmin /Zmax. This proves the Zero Forcing Equalization property of this scheme for all channels. We club the Lz zeros on unit circle to the maximum phase part. Henceforth, maximum phase part refers to the factors with zeros on or outside the unit circle and Lmin refers to the number of such zeros. Note that the other altemative, i.e. to club zeros on unit circle with minimxmi phase part is also possible. In such a case, minimum phase part refers to the factors with zeros on or inside the unit circle and Z^ refers to the number of such zeros. Proposed MinMax Equalizer: Using the trarismission model of figure 4, we now propose the Minmax equalization scheme. From figure 4, we see that the effect of channel can be mitigated by mitigating the effects of its maximum phase and minimum phase parts sequentially This sequential equalizer is detailed in figure 5. Figure 6 is a flowchart, which describes a novel equalization method for use in Zero padded OFDM systems, disclosed in the present invention. In figure 6, 1 gives the channel coefficients. These can be obtained by channel sounding (use of pilots). Different algorithms can be used to obtain channel coefficients. The present invention focuses on the equalization, as a result of which, algorithms for obtaining channel coefficients are not described. The present invention uses the channel coefficients computed at the receiver using any of the algorithms available in priorart. In 2, the channel polynomial is factorized into three parts i.e. Maximimi Phase part. Minimum Phase part and zeros on unit circle. The factorization involves separating the factors of the channel polynomial corresponding with roots inside and outside (and on) unit circle respectively. There exist various methods to undertake the factorization. We use the standard method based on finding the roots of the channel polynomial (Rooting based method). The factor for zeros on unit circle is grouped with either the Maximum Phase part or the Minimum Phase part. Technically, maximum phase part polynomial contains roots strictly outside the unit circle. Similarly, the minimtmi phase part polynomial contains roots strictly inside the unit circle. This technically correct definition is used in the Factorization of 2 leading to 3 5. In this patent, we club 5 the polynomial containing zeros on the unit circle with 4 that containing zeros outside the unit circle (depicted by the convolution in 6). For the ease of presentation, we continue to call the resulting polynomial as maximum phase polynomial 7. Hence, 3 presents the minimum phase polynomial Hmin(z) and 7 presents the maximum phase part Hmax(z) so that H(z)=Hmax(z) Hmin(z). Let the orders of Hmin(z) and Hmax(z) be Lmin and Lmax respectively with LLmax Lmin. In 8 and 10, matrix formation is carried to obtain the two matrices 9 H and 11 H .as mentioned in the earlier sections. In 12, max mm ' the received signal (after downconversion and sampling) is considered for processing. This signal undergoes 13 the deletion of its last Lmin entries. Then 14, back substitution using 11 H .is carried out. In 15, the first Lmax entries of the output of Minimum phase equalizer are deleted and 16 back substitution using H is carried out. In the absence of noise, this process recovers the max transmitted symbol exactly, thereby resulting in a zero forcing equalizer, Thxxs, 11 to 14 fonn the Zero Forcing Equalization for the minimum phase part, while 9,15 and 16 form the Zero Forcing Equalization for the maximum phase part. 2 to 16 form the MinMax Zero Forcing Equalizer. . In 17, the Maximum Likelihood decoder detects 18 the most likely transmitted signal. Change in the order of equalization: It is possible to change the order of equalization by equalizing first for the maximum phase channel and then for the minimum phase. This is accomplished by the following steps. Obtain y (i) from 7(i)=H y (i) through back substitution where y(i) is :lmin ^ — maX —mm aP+Lmin length vector containing the last P+Lmin entries of y(i) and Hmax is a (P +Lmin) X (P + Lmin) Upper Triangular matrix with the first row being Obtain u(i) from y (i) = H . u(i) through back substitution where y . (i) is aP — :1mm ' min mm lengdi vector containing the first P entries of y . (f) and H . is a P x P Lower Triangular matrix with the first column being [go,g1..gLmin..0,0...0]T px1 While the MinMax Equalizer is derived for a Zero pad OFDM system, it can be used'for any Block Transmission system (be it single carrier or multiple carriers) which employs Zero padding for combating IBL REFERENCES: [1] L. J. Cimini, http://dLcomsoc,org/cocoon/comsoc/html/50.htm"Analvsis and Simulation of a Digital Mobile Channel Using Orthogonal Frequency Division Multiplexing", IEEE Transactions on Communications, vol. 33, no. 7, July 1985 pp. 665 675. [2] G. B.Giannakis, Z. Wang, "Wireless Multicarrier Communications  Where Fourier meets Shannon," IEEE Signal Processing Magazine, pp. 29—48, May 2000. [3] B. Muquet, M.de Courville, G. B. Giannakis, Z, Wang and P. Duhamel, "Reduced Complexity Equalizers for ZeroPadded OFDM Transmissions," Proc. of lCASSP, vol 5, pp. 29732976, Istanbul, 2000. [4] G. H Golub, C.F. Van Loan, "Matrix Computations," The Johns Hopkins University Press, London 1996. [5] A, V. Oppenheim, R, W. Schaffer, "Discrete Time Signal Processing," Prentice Hall India, New Delhi. [6] M. R. Bhavani Shankar, K. V. S. Hari, "Reduced Complexity Equalization Schemes for Zero padded OFDM Systems," IEEE Signal Processing Letters, September 2004. We Claim: 1. A novel Equalization method for use in Zero padded OFDM systems, where the equalizer is provided with complete channel information, comprising the steps of: a. obtaining the signal distorted by the channel in a predetermined format; factorizing the channel polynomial into three parts corresponding to the Maximum Phase part, Minimum Phase part and zeros on the unit circle, the Maximum Phase part or the Minimum phase part being clubbed with the factor corresponding to zeros on unit circle, the resulting factors will continued to be called as Maximum Phase part and the Minimum Phase part; b. obtaining the channel coefficients corresponding to these factors through convolution and forming the matrices Hmin and Hmax using these coefficients; and c. performing the sequential equalization by: i) deleting the last Lmin entries of the received signal and performing equalization for the Minimum phase part using back substitution; ii) deleting the first Lmin entries of the output of the Minimum phase equalizer and performing equalization for the Maximum phase part using back substitution which yields a Zero Forcing Equalizer; iii) detecting the most likely transmitted signal from the equalized signal by using a Maximum Likelihood Decoder. 2. The Equalization method as claimed in claim 1, wherein said equalization Method yields a low complexity ZFE for any block transmission based communication system (Single carrier or Multiple carriers), which uses Zero Padding to combat IBL 3. The Equalization method as claimed in claim 1, wherein the sequence of equalization presented in the steps d(i), d(ii) and d(iii) being changed by equalizing first for the maximum phase part and then for the minimum phase part by carrying out the following steps: i) Deleting the first Lmin entries of the received signal and performing equalization for the Maximum phase part using back substitution; ii) deleting the last Lmin entries of the output of the maxim\rai phase equalizer and performing equalization for the Minimum phase part using back substitution, which yields a Zero Forcing Equalizer; iii) detecting the most likely transmitted signal from the equalized signal by using a Maximum Likelihood Decoder. 4. A method for zero padded transmission with zero forcing equalization for all non zero channels using the equalization method claimed in any one of claims 1 to 4. 5. An equalizer system for carrying out zero forcing equalization comprising of a processing unit and a data storage having Machine language instructions stored therein, said processing unit having (i) means for generating a known signal and generating the channel coefficients, (ii) means for obtaining the roots of the channel as eigenvalues of the companion matrix generated from the channel, sorting the roots based on their amplitude and generating the coefficients corresponding to the minimum and maximum phase components (the factor corresponding to zeros on imit circle are absorbed into one of them) and (iii) means for performing equalization sequentially by choosing the appropriate input through back substitution. 

Patent Number  211817  

Indian Patent Application Number  834/CHE/2003  
PG Journal Number  52/2007  
Publication Date  28Dec2007  
Grant Date  09Nov2007  
Date of Filing  16Oct2003  
Name of Patentee  M/S. INDIAN INSTITUTE OF SCIENCE  
Applicant Address  BANGALORE 560 012.  
Inventors:


PCT International Classification Number  H 04 L 27/00  
PCT International Application Number  N/A  
PCT International Filing date  
PCT Conventions:
