Abstract:
A technique for the blind equalization of digital communications channels relies on the iterative minimization of a cost function known as the J-divergence between a known or assumed probability density function (PDF) of the source data signal and an estimated PDF of a receiver decision output signal derived from the equalizer output signal by minimum-distance mapping. The J-divergence function is defined in terms of the Kullback-Leibler distance between the two PDFs. Minimization is achieved by continually updating both an equalizer tap coefficient vector and the estimated PDF of the decision output signal using a stochastic gradient algorithm applied to the J-divergence cost function.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     Not Applicable 
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
     Not Applicable 
     BACKGROUND OF THE INVENTION 
     The present invention is related to the field of digital communications, and more particularly to techniques for equalizing channel effects in digital communication systems. 
     Digital communications suffers from a particular form of distortion known as intersymbol interference (ISI). ISI has been recognized as the major obstacle to high speed data transmission over mobile radio channels. Digital communications systems use an operation known as &#34;equalization&#34; to minimize ISI. This minimization is often achieved by minimizing a cost function which is a suitably chosen function of the data. 
     There are generally two approaches to equalization: conventional equalization and &#34;blind&#34; equalization. In systems employing conventional equalization, a training sequence is transmitted over the channel prior to the transmission of any useful data. The training sequence is a data sequence that is a priori known to the receiver. The receiver uses the relationship between the known training sequence and the sequence it actually receives to construct an approximation of the inverse transfer function for the channel. The equalizer is then configured to use the inverse transfer function and thereby induce minimal ISI. 
     Conventional equalization is problematic in some communication systems, such as mobile and multi-point communications systems, because the training sequences use up scarce bandwidth resources that could otherwise be used to transmit useful data. Such systems therefore often use blind equalization, which is a form of equalization that does not require the use of a training sequence. 
     There have been several approaches to the problem of blind equalization including a popular technique known as the Godard algorithm. These algorithms generally employ cost functions that measure the expected value of a function of the equalizer output. For example, the Godard algorithm uses a functional called the dispersion of order p (where p is a positive integer) as the cost function. 
     It is desirable to improve the ability of digital communications systems to minimize ISI, including communications systems employing blind equalization. Systems achieving such reduced ISI are capable of achieving reduced data error rates at prevailing data transmission rates, or can obtain higher data transmission rates without sacrificing data integrity, in order to obtain better overall system performance. 
     BRIEF SUMMARY OF THE INVENTION 
     A blind equalization method is disclosed that achieves improved ISI performance over prior blind equalization techniques. The disclosed method uses a cost function that measures dissimilarity between an assumed or known probability density function (PDF) of a source data signal and a continually-estimated PDF of an equalized data signal recovered by a decision function coupled to the equalizer output. The measure of dissimilarity used is akin to a &#34;distance&#34; as that term is used in topology or communications theory. One such cost function, termed the J-divergence of the two PDFs, measures the cross entropy between two PDFs. A set of tap coefficients used to realize the equalizer, along with the estimated PDF of the equalized data signal, are continually updated in a manner tending to minimize the J-divergence, so that the statistics of the equalized signal are made to closely match those of the source signal. A stochastic gradient algorithm for performing this minimizing updating is disclosed. The disclosed equalization technique generally converges to a lower level of ISI than do prior techniques such as the Godard algorithm. 
    
    
     BRIEF DESCRIPTION OF THE SEVERAL VIEWS OF THE DRAWING 
     An embodiment of the invention is described below with respect to the accompanying drawing, in which: 
     FIG. 1 is a block diagram of an exemplary digital communications system in accordance with the principles of the present invention; 
     FIG. 2 is a block diagram of a receiver in the communications system of FIG. 1; 
     FIG. 3 is a map of data elements stored in memory in the receiver of FIG. 2 during operation thereof; and 
     FIG. 4 is a flow diagram of the operation of the receiver of FIG. 2. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In FIG. 1 a source 10 such as a modem emits a source signal {x k  } that is transmitted over a channel 12. The signal {y k  } received from the channel is provided to a receiver 14, which as shown includes an equalizer 16 and a decision function 18. The output of the equalizer is referred to as {z k  }, and the output of the decision function is referred to as {z k  }. 
     In general, the signal {x k  } is an amplitude-modulated digital communications signal, either pulse- or quadrature-amplitude modulated. If the signal {x k  } is pulse-amplitude modulated, it is a real-valued M-ary signal and is known as an M-PAM signal. An M-PAM signal {x k  } takes on signalling values that are symbols in an M-ary symbol alphabet A given by: 
     
         A={-(M-1)d, . . . -3d, -d, d, 3d, . . . (M-1)d}, 
    
     where M is the number of discrete levels in the alphabet and 2d is the amplitude difference between adjacent levels. 
     If {x k  } is quadrature-amplitude modulated, it contains real and imaginary M-ary component signals and is known as an M-QAM signal. The M-QAM case is not described in detail herein; however, the disclosed techniques upon suitable modification are likewise applicable to M-QAM systems. 
     The symbols appearing in the signal {x k  } are a priori known or assumed to be distributed according to a probability density function (PDF) p x  (). In one case for which results are given herein, the samples x k  of the signal {x k  } are assumed to be statistically independent of each other and to be equally likely to be any of the M possible symbols in A. In this special case the samples x k  are said to be &#34;independent and identically distributed&#34; or i.i.d. random variables. However, the techniques described herein are generally applicable to source signals having different PDFs. 
     The channel 12 is assumed to be a linear finite impulse (FIR) response filter. The equalizer 16 is realized as a FIR filter with adjustable coefficients. The decision function 18 resolves each sample z k  of the equalizer output signal {z k  } to the closest corresponding symbol from the alphabet A using a minimum-distance function. The decision output signal {z k  } is available to a data recipient not shown in FIG. 1, and is also fed back to the equalizer 16 for use in the adaptive equalization algorithm as described below. 
     FIG. 2 shows a block diagram of the equalizer 16 of FIG. 1. A processor 20 is adapted to receive the signal {y k  } and to output the equalized data signal {z k  }. The processor 20 may be a general purpose digital signal processor, or other suitable processing means such as are known in the art. The equalizer 16 also uses memory 22 to store various parameters, signals, and intermediate results during execution of the equalization algorithm. 
     FIG. 3 illustrates some of the key data components appearing in memory 22. A first component K (23) is used during initialization as described below. Y k  (24) is a regressor of inputs to the equalizer 16, and is expressed as: 
     
         Y.sub.k [y.sub.k+N . . . y.sub.k . . . y.sub.k-N ].sup.T 
    
     where [ ] T  denotes vector transposition. 
     The component θ k  (26) is a vector of tap coefficients used in the equalizer 16, and θ k+1  (28) is a tap coefficient vector being calculated during each sampling interval for use in the next sampling interval. These vectors are expressed as: 
     
         θ=[θ.sub.-N . . . θ.sub.0 . . . θ.sub.N ] 
    
     Components 30 and 32 represent current and next values, respectively, of an estimated PDF of the signal {z k  }, these PDFs being denoted p z   k  () and p z   k+1  (). The characteristics of these PDFs are described in greater detail below. 
     The Cost Function 
     The equalizer 16 employs a cost function based on a value known as the Kullback-Leibler (KL) distance between two PDFs p 1  and p 2 . This value is denoted KL(p 1 , p 2 ) and is given by the expression: ##EQU1## where E 1  { } indicates expectation with respect to p 1  (). 
     The KL distance is used to construct a function called the J-divergence having topological properties, in particular the property of symmetry, that make it suitable for use in the manner described herein. The J-divergence is defined as: 
     
         Jdiv(p.sub.1,p.sub.2)=KL(p.sub.1,p.sub.2)+KL(p.sub.2,p.sub.1) 
    
     The cost function used in the illustrated embodiment is denoted J(θ), and is generally given by: 
     
         J(θ)=Jdiv(p.sub.2, p.sub.x) 
    
     In the case where {x k  } is an M-PAM, i.i.d. signal, J(θ) is given by: ##EQU2## The Stochastic Gradient Algorithm 
     The equalizer 16 employs a stochastic gradient algorithm in order to minimize the J-divergence between the PDFs p x  () and p z  (). The general form of this algorithm used in the equalizer 16 is as follows: 
     
         VAR.sup.k+1 =VAR.sup.k -γ∇.sub.VAR J(θ) 
    
     where ∇ is the gradient operator and γ is the iteration step size. The equalizer 16 employs the stochastic gradient algorithm in two ways: (1) to update the tap coefficient vector θ, and (2) to update the PDF p z  (). In each use of the algorithm the variable being updated is substituted for VAR in the above equation. It can be shown that, for the case of {x k  } being M-PAM and i.i.d., the algorithm for each use reduces to the following: ##EQU3## where γ and α are the step sizes of the respective updates. 
     FIG. 4 shows the flow of blind adaptive equalization processing carried out by the processor 20 of FIG. 2. In step 40 the equalizer 16 is initialized as an all-pass filter. The order of the equalizer is given as (2N+1), and thus the initial equalizer tap coefficient vector θ is: 
     
         [0 . . . 0 1 0 . . . 0] 
    
     where the single &#34;1&#34; is the (N+1) th  element of the vector. This equalizer configuration sets the signal {z k  } equal to the signal {y k  } during an initial period. 
     In step 42, the process waits for an initial period of K samples. During this initial period, an initial regressor Y k  is collected in the equalizer 16, and the first K samples of {z k  } are collected. 
     In step 44, the first K samples of {z k  } are used to create an initial estimate of the PDF p z  (). This PDF is estimated by generating a histogram from the initial samples or by fitting a gaussian kernel to the samples, and then normalizing the resulting PDF over the finite support. The normalized PDF is used as the initial estimate of the PDF p z  (). 
     At step 46 of FIG. 4, an index variable k is set equal to K+1, and then the process enters a loop of steps 48-56 which are repeated for each new sample y k  of the received data signal. 
     In step 48 an equalizer output value z k  is calculated from the regressor Y k  and the vector θ k . This calculation is a FIR filter as follows: 
     
         z.sub.k =Y.sub.k.sup.T θ 
    
     As shown, the data output symbols {z k  } emerging from the receiver 14 are created by the continued iterations of step 48 in conjunction with the decision function 18 of FIG. 3. 
     In step 52, the next tap coefficient vector θ k+1  (28) is calculated using the J-divergence function and the stochastic gradient algorithm as described above. 
     In step 54, the next estimated PDF p z   k+1  (z k ) (32) is calculated also using the J-divergence function and the stochastic gradient algorithm as described above. 
     In step 56, the PDF p z  () and the vector θ are updated by substituting the new values p z   k+1  (32) and θ k+1  (28) respectively for p z   k  (30) and θ k  (26). Then the index variable k is incremented, and the top of the loop (step 48) is re-entered. 
     While the invention has been described with reference to an embodiment in which the source signal {x k  } is M-PAM, it can be readily shown that the blind equalization method can also be used with a quadrature-amplitude-modulated (M-QAM) source signal. Also other cost functions can be employed, one such alternative being the mean square function. In addition, it will be appreciated by those skilled in the art that other modifications to and variations of the disclosed blind equalization method are possible without departing from the innovative concepts contained herein. Accordingly the invention herein disclosed is not to be viewed as limited except as by the scope and spirit of the appended claims below.