Abstract:
Shortening impulse response filters (SIRF) are disclosed that satisfy constraints in both the time and frequency domains. In addition, methods and apparatus are disclosed for determining the coefficient values for SIRF filters. The disclosed SIRF filters shorten the channel impulse response in the time domain while also providing a frequency response that does not attenuate or amplify the received signal. One or more sets define constraints that the SIRF filter must satisfy in the time domain, and one or more sets define constraints that the SIRF filter must satisfy in the frequency domain. By varying the sets utilized to define the time and frequency domain constraints, SIRF filters having a linear or non-linear phase response may be obtained. The intersection of the various sets defines the coefficients for the SIRF filters. Vector space projection methods are utilized to determine the intersection set.

Description:
FIELD OF THE INVENTION  
         [0001]    The present invention relates to techniques for shorting the impulse response of communication systems, such as discrete multi-tone (DMT) and orthogonal frequency division multiplexing (OFDM) communication systems, and more particularly, to methods and apparatus for designing a shortening impulse response filter (SIRF).  
         BACKGROUND OF THE INVENTION  
         [0002]    It is well known that most communication channels are dispersive in nature and introduce a number of distortions. Thus, signals arriving at a receiver are typically corrupted by intersymbol interference (ISI), crosstalk, echo, and other noise. Thus, receivers must jointly equalize the channel, to compensate for such intersymbol interference and other distortions, and decode the encoded signals at increasingly high clock rates.  
           [0003]    To overcome the effects of intersymbol interference, any two adjacent symbols in a conventional DMT or OFDM communication system are separated by a guard period (i.e., a cyclic prefix (CP)). In addition to providing a mechanism for frame synchronization, the guard interval insures that samples from one symbol block do not interfere with the samples of another block. The length of the impulse response of the physical channel determines the required length of the guard interval. Using a long guard interval, however, reduces the effective throughput of the transceiver. Thus, to avoid using a long guard interval, filters are employed to shorten the channel impulse response and thereby allowing the use of a shorter guard interval. More specifically, time domain linear filters, often referred to as shortening impulse response filters (SIRFs) or time domain equalizers (TDQs), are typically employed to shorten the channel impulse response.  
           [0004]    A number of techniques have been proposed or suggested for designing TDQ filters. For a detailed discussion of a number of such filter design techniques, see, for example, J. W. P. Melsa and R. C. Younce, “Impulse Response Shortening for Discrete Multitone Tranceivers,” IEEE Trans., COM-44, (12), 1662-1672 (1996); or N. Al-Dahir and J. M. Cioffi, “Stable Pole-Zero Modeling of Long FIR Filters With Application to the MMSE-DFE,” IEEE Trans., COM-45, (5) 508-513 (1997), each incorporated by reference herein. Generally, these filter design algorithms are typically based on least mean square (LMS) or eigenvector calculus. While these filter design algorithms are capable of producing very good TDQ filters, they suffer from a number of limitations, which if overcome, could greatly improve their ability to shorten the channel impulse response and otherwise improve system performance. Specifically, since these filter design algorithms have little, if any, control over the frequency response, they may produce a frequency response with nulls in the pass-band that degrade the signal-to-noise ratio (SNR) of the received signal, translating into a lower bit rate throughput. It has been found, however, that removing the nulls in the pass-band is a difficult problem, often requiring a trial and error solution. In addition to the null problem, the frequency response in unpredictable and severe attenuation and amplification variations could result from call to call.  
           [0005]    A need therefore exists for improved techniques for designing SIRF filters. A further need exists for SIRF filters that satisfy constraints in both the time and frequency domains to provide improved performance. Yet another need exists for methods and apparatus for determining coefficient values for SIRF filters that shorten the channel impulse response in the time domain while also providing a frequency response that does not attenuate the received signal.  
         SUMMARY OF THE INVENTION  
         [0006]    Generally, a method and apparatus are disclosed for determining parameters for SIRF filters. According to one aspect of the invention, filter coefficients for SIRF filters are determined that satisfy constraints in both the time and frequency domains to provide improved performance. More specifically, SIRF filters are disclosed that shorten the channel impulse response in the time domain while also providing a frequency response that does not attenuate or amplify the received signal.  
           [0007]    One or more sets are established to define constraints that the SIRF filter must satisfy in the time domain, and one or more sets are established to define constraints that the SIRF filter must satisfy in the frequency domain. An SIRF filter satisfying both frequency and time constraints is obtained by determining the intersection of the various sets. By varying the sets utilized to define the time and frequency domain constraints, SIRF filters having a linear or non-linear phase response may be obtained. Vector space projection method is an iterative algorithm applied to the sets until the algorithm converges to a solution, i.e., the intersection if the sets intersect, or to a point with minimum summing distance to all sets if the sets do not intersect. In the case of SIRF design, the solution of the algorithm is the filter coefficients.  
           [0008]    A more complete understanding of the present invention, as well as further features and advantages of the present invention, will be obtained by reference to the following detailed description and drawings. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0009]    [0009]FIG. 1 illustrates a variable shortening impulse response filter applied to a signal on a dispersive communication channel to shorten the channel impulse response in accordance with the present invention;  
         [0010]    [0010]FIG. 2 is a schematic block diagram illustrating a modem in which the present invention may be employed.  
         [0011]    [0011]FIG. 3 is a flow chart describing the filter coefficient determination process incorporating features of the present invention;  
         [0012]    [0012]FIGS. 4A through 4E, collectively, illustrate exemplary pseudo-code for generating a non-linear SIRF filter; and  
         [0013]    [0013]FIG. 5 illustrates the trajectory of iteration in VSPM for two sets until the algorithm converges to the intersection, i.e., the solution. 
     
    
     DETAILED DESCRIPTION  
       [0014]    [0014]FIG. 1 illustrates the use of a variable shortening impulse response filter  120  on a dispersive communication channel  110  to shorten the channel impulse response  130   a, b , in accordance with the present invention. According to one aspect of the present invention, the variable SIRF filter  120  can satisfy constraints in both the time and frequency domains to provide improved performance. Although described in connection with exemplary DMT and OFDM communication systems, it will be understood that the present invention is equally applicable to any environment where it is desirable to shorten an impulse response.  
       Vector Space Projection Methods (VSPM)  
       [0015]    According to one aspect of the present invention, vector space projection methods are employed to design SIRF filters. For a detailed discussion of vector space projection methods (VSPM), see, for example, L. M. Bregman, “Finding the Common Point of Convex Sets by the Method of Successive Projections, “Dokl. Akad. Nauk USSR, Vol. 162, No. 3, 487 (1965), incorporated by reference herein. VSPM techniques find a mathematical object (in this case a set of coefficients) in a proper vector space that satisfies multiple constraints. When all the constraint sets are convex and have a nonempty intersection, the VSPM becomes a powerful theory in finding the objects that satisfy all the constraints. As discussed further below, vector space projection methods employ an iterative algorithm that will converge to a set of finite impulse response (FIR) coefficients that satisfies constraints in the time domain (e.g., shortening the channel impulse response) and constraints in the frequency domain spectrum.  
         [0016]    Traditionally, VSPM techniques have been employed to design constrained FIR filters that are tailored to specific applications. See, K. C. Haddad, “Constrained FIR Filter Design by the Method of Vector Space Projections,” IEEE Trans. on Circuit and Systems II: Analog and Digital Signal Processing, Vol. 47, No. 8 (August 2000), incorporated by reference herein. In the context of the present invention, where VSPM techniques are employed to design an SIRF filter, two (or more) convex sets representing the constraints in time and frequency domains and corresponding projection operators have been mathematically formulated. A first convex set defines the constraints that the SIRF filter  120  must satisfy in the time domain, such that when the filter is convolved with the impulse response, the impulse response is shortened. Likewise, a second convex set defines the constraints that the SIRF filter  120  must satisfy in the frequency domain, such as a low, high or band pass band. P i  is defined to be the projection operator onto the set C i . Thus, to obtain an SIRF filter satisfying both frequency and time constraints, an intersection of both sets is required.  
       Designing the SIRF Filter  
       [0017]    Generally, the present invention designs a variable SIRF filter  120  having an impulse response, h, of length N to shorten the impulse response of a channel s, where  
           h =( h (0),  h (1), . . . ,  h ( N− 1)).  
         [0018]    In the frequency domain, h becomes:  
                 H        (   ω   )       =                    ∑   0     N   -   1              h        (   n   )                   -   jω                   n           =       A        (   ω   )                 jΦ        (   ω   )               ,   where                   A        (   ω   )       =                  ∑   0       N   /   2     -   1            2        h        (   n   )            cos        [       (     n   -       N   -   1     2       )        ω     ]                     and                                  Φ                   (   ω   )       =                  -                  N   -   1     2          ω                     (     for                 linear                 phase     )     .                                   
 
         [0019]    The transformations from the frequency domain to the time domain and vice versa are done using the fast Fourier transform and inverse fast Fourier transform, respectively, by discretizing ω.  
         [0020]    The pass-band and stop-band in the frequency domain are defined to be Ω p ≡{ω: ω p &lt;ω≦π and Ω s {ω: 0&lt;ω≦ω s }, respectively. As discussed more fully below, the sets involved in designing the SIRF filter  120  in an exemplary embodiment are (i) a time domain convex set, C 1 , representing the filters with linear phase; (ii) a frequency domain non-convex set, C 2  representing the non-linear phase filters with the appropriate constraints in the pass-band and stop-band; (iii) a frequency domain convex set, C 3 , representing the linear phase filters with the appropriate constraints in the pass-band and stop-band; (iv) a time domain convex set, C 4 , representing all the filters of length N; and (v) a time domain convex set, C 5  (n), for a specific range of values of n, (application dependent). Although C (n) consists of numerous convex sets, it is referred to hereinafter as C 5 . More specifically, C 5  represents additional constraints on the filter h in the time domain. Thus, the time domain sets, C 1 , C 4  and C 5 , are convex, while the frequency domain sets, C 2  and C 3 , are convex or non-convex for filters with linear or non-linear phase, respectively. The optional frequency domain set, C 3 , constrains the filter such that it will have linear phase.  
         [0021]    The sets may be defined mathematically as follows:  
                 C   1     ≡                {         h   ∈                  R   N     :     h        (   n   )           =     h        (     N   -   1   -   n     )         ,       for                 n     =   0     ,   1   ,   …              ,     N   -   1       }       ,                   C   2     ≡                {                        h   ∈                  R   N     :         1   -   α     ≤          H        (   ω   )            ≤     1   +     α                 for                 ω         ∈     Ω   p                           a                   n      d                          H        (   ω   )              ≤     β                 for                 ω       ∈     Ω   s             }       ,                   C   3     ≡                {               h   ∈                  R   N     :       1   -   α     ≤     A        (   ω   )       ≤     1   +   α                       and                   Φ        (   ω   )         =           -     ω        (     N   -   1     )         /   2                   for                 ω     ∈                            H        (   ω   )            ≤     β                 for                 ω       ∈     Ω   s       ,                Ω   p       ,     }       ,                   C   4     ≡                {     h   ∈                R   N       }       ,                   C   5          (   n   )       ≡                  {     h   ∈                  R   N     :       σ   n     ≤       (     s   *   h     )     n     ≤     ρ   n           }                     (     0   &lt;   n   &lt;     N   +   M   -   1       )                                   
 
         [0022]    where the vector s referenced in the definition for the set, C 5 , is the impulse response of the channel, * denotes convolution, (s*h) n  denotes the response at time n, and σ n  and ρ n  represent the desired lower and upper bounds, respectively. M is the size of the discrete channel impulse response, s. R N  is the Hilbert space of dimension N.  
         [0023]    P i  is defined to be the projection operator onto the set C i . For a more detailed discussion of the computation of the projection operators and the VSPM algorithm generally, see, Henry Stark, “Vector Space Projection: A Numerical Approach to Signal and Image Processing, Neural Nets, and Optics,” (Wiley, 1998), incorporated by reference herein. The two iterative algorithms proposed are:  
         [0024]    h k+1 =P 2 P 4 P 5 h k , where h 0  is arbitray and projection operators P 2 , P 4  and P 5  are projected onto sets C 2 , C 4 , C 5  to produce a non-linear phase filter; or  
         [0025]    h k+1 =P 1 P 3 P 5 h k , where h o  is arbitray and projection operators P 1 , P 3 , and P 5  are projected onto sets C 1 , C 3 , C 5  to produce a linear-phase filter.  
         [0026]    [0026]FIG. 2 is a schematic block diagram illustrating a modem  200  in which the present invention may be employed. As shown in FIG. 2, the modem  200  includes one or more communication ports  230  for receiving a signal from a communication channel  110 . As previously indicated, the received signal is applied to a variable SIRF filter  120  in accordance with the present invention, before being applied to a decoder  240  that decodes the signal in a known manner. The coefficients for the SIRF filter  120  are determined by a filter coefficient determination process  300 , discussed below in conjunction with FIG. 3.  
         [0027]    The filter coefficient determination process  300  may be stored in a data storage device  220  that could be implemented as an electrical, magnetic or optical memory, or any combination of these or other types of storage devices. Moreover, the term “memory” should be construed broadly enough to encompass any information able to be read from or written to an address in the addressable space accessed by a processor (not shown). Alternatively, the filter coefficient determination process  300  may be embodied on an application specific integrated circuit (ASIC).  
         [0028]    [0028]FIG. 3 is a flow chart describing the filter coefficient determination process  300  incorporating features of the present invention. As shown in FIG. 3, the filter coefficient determination process  300  receives the impulse response of the channel  110  as an input and then initializes the SIRF filter  120  to an arbitrary value during step  310  (to provide a starting point). Thereafter, the sets that specify the desired filter characteristics are defined during step  320 . As discussed above, sets C 2 , C 4 , C 5  specify the desired characteristics in the time and frequency domains for a non-linear filter, while sets C 1 , C 3 , C 5  specify the desired characteristics in the time and frequency domains for a linear filter.  
         [0029]    The corresponding projection operators P 2 , P 4 , P 5  or P 1 , P 3 , P 5  are defined during step  350 , and are then used to project onto the corresponding sets C 2 , C 4 , C 5  or C 1 , C 3 , C 5  during step  360 . As shown during step  370 , the projections are continued iteratively until an intersection is reached. The intersection defines the filter coefficients for the SIRF filter  120 , during step  380 . Program control then terminates.  
         [0030]    [0030]FIGS. 4A through 4E, collectively, illustrate exemplary pseudo-code  400  for generating a non-linear SIRF filter  120 . As shown in FIG. 4A, the pseudo-code  400  has an initialization section  410  that initializes a number of parameters and loading the impulse response for the channel  110 . Thereafter, a channel impulse response matrix is established in section  430 . The channel impulse response matrix is used for convolution needed for projection onto the set C 5  As shown in FIG. 4B, the pseudo-code  400  then determines the maximum energy of the channel impulse response in section  440 . The SIRF filter  120  is initialized to an arbitrary value in section  445 , and a number of additional parameters are initialized during step  450 .  
         [0031]    As shown in FIG. 4C, the first iterative procedure is performed during section  460  to project onto the set C 2  using the projection operator P 2 . The frequency-to-time transformation is then performed at the end of section  460  using an inverse Fourier transform. As shown in FIG. 4D, an iterative procedure is performed during section  470  to project onto the set C 4  using the projection operator P 4 . As shown in FIGS. 4D and 4E, an iterative procedure is performed during section  475  (comprised of sections  475 - 1  (FIG. 4D) and  475 - 2  (FIG. 4E) to project the projection operator P 5  onto the set C 5  defining additional time characteristics. The time-to-frequency transformation is then performed at the end of section  475 - 2  using a Fourier transform. Finally, the determined filter coefficients are applied to the SIRF filter  120  during section  480  (FIG. 4E).  
         [0032]    [0032]FIG. 5 illustrates the trajectory of iteration in VSPM for two exemplary sets, C 1  and C 2 , until the two sets converge to an intersecting set satisfying the constraints of both sets. The solution set C s  is the intersection region and x 0  is an arbitrary starting point from which the first set is projected onto the second set (at a point defined by P 1 X 0 ). Thereafter, the second set is projected onto the first set at a point x 1 , where x 1  equals P 2 P 1 x 0 .  
         [0033]    It is to be understood that the embodiments and variations shown and described herein are merely illustrative of the principles of this invention and that various modifications may be implemented by those skilled in the art without departing from the scope and spirit of the invention.