Title of Invention  A METHOD FOR DERIVING AN ESTIMATE OF A WIRELESS CHANNEL IN A WIRELESS COMMUNICATION SYSTEM 

Abstract  ..A method for detivlng an estimate of a wireless channel in a wireless communication system Abstract Techniques to derive a channel estimate using substantially fewer number of complex multiplications than with a bruteforce method to derive the same channel estimate. In one method, an intermediate vector B is initially derived based on K subvectors of a vector H for a channel frequency response estimate and at least two DFT submatrices for a DFT matrix W , where K > 1. An intermediate matrix for A the DFT matrix W is also obtained. A least square channel impulse response estimate is then derived based on the intermediate vector B and the intermediate matrix A . In one implementation, the intermediate vector B is obtained by first computing DFTs of a matrix HTXL , which is formed based on the vector H, to provide a matrix GLXL. Inner products between the columns of a base DFT submatrix Wl and the rows of the matrix GLXL are then computed to obtain the entries of the intermediate vector B . (Fig. 4) 
Full Text  This application claims the benefit of U.S. Provisional Patent Application Serial No. 60/427,896, filed November 19,2002, which are incorporated herein by reference in its entirety. BACKGROUND /. FieU The present invention relates generally to data communication, and more specifically to techniques for performing channel estimation with reduced complexity. //. Background Wireless communication systems are widely deployed to provide various types of communication such as voice, packet data, and so on. These systems may be multipleaccess systems capable of supporting communication with multiple users by sharing the available system resources. Examples of such multipleaccess systems include code division multiple access (CDMA) systems, time division multiple access (TDMA) systems, and orthogonal frequency division multiple access (OFDMA) systems. Orthogonal firequency division multiplexing (OFDM) effectively partitions the overall system bandwidth into a number of (N) orthogonal subbands. These subbands are also referred to as tones, frequency bins, and frequency subchannels. With OFDM, each subband is associated with a respective subcarrier upon which data may be modulated. Each subband may thus be viewed as an independent transmission channel that may be used to transmit data. In a wireless communication system, an RJP modulated signal from a transmitter may reach a receiver via a number of propagation paths. For an OFDM system, the N subbands may experience different effective channels due to different effects of fading and multipath and may consequently be associated with different complex channel gains. An accurate estimate of the response of the wireless channel between the transmitter and the receiver is normally needed in order to effectively transmit data on the available subbands. Channel estimation is tj^ically performed by sending a pilot from the transmitter and measuring the pilot at the receiver. Since the pilot is made up of symbols that are known a priori by the receiver, the channel response can be estimated as the ratio of the received pilot symbol over the transmitted pilot symbol for each subband used for pilot transmission. Pilot transmission represents overiiead in a wireless communication system. Thus, it is desirable to minimize pilot transmission to the extent possible. However, because of noise and other artifacts in the wireless channel, a sufficient amount of pilot needs to be transmitted in order for the receiver to obtain a reasonably accurate estimate of the channel response. Moreover, the pilot transmission needs to be repeated to account for variations in the channel over time due to fading and changes in the multipath constituents. Consequently, channel estimation normally consumes a noticeable portion of the system resources. In an OFDM system, to reduce the amount of overhead for pilot, a pilot transmission may be sent on a group of designated subbands, which may be only a subset of the available subbands. An initial estimate of the channel response may be obtained for the designated subbands based on the pilot transmission. Signal processing may then be performed to obtain an enhanced channel response for a group of desired subbands, which typically includes the subbands to be used for data transmission. The signal processing may further perform noise averaging to obtain a more accurate estimate of the channel response. As described in detail below, depending on the number of designated subbands used for pilot transmission and the impulse response of the channel, the signal processing may be computationally intensive and require a large number of complex multiplications. There is therefore a need in the art for techniques to more efficiently derive an estimate of the channel response in a wireless communication system, such as an OFDM system. SUMMARY Techniques are provided herein to derive a channel estimate using substantially fewer numbers of complex multiplications than with a bruteforce method to derive the same channel estimate. This channel estimate may be a least square estimate of the impulse response of a wireless channel, which may be derived based on an initial frequency response estimate ft of the wireless channel. As described in detail below, the least square channel impulse response estimate may be derived by a matrix multiplication between the vector ft and a matrix W , which is derived based on a discrete Fourier transform (DFT) matrix W. The structure of the matrix W can be exploited to decompose the matrix multiplication W H into a sum of matrix multiplications between smaller submatrices of W and smaller subvectors of ft. The properties of the submatrices of W can be exploited to simplify the computation. The net result is fewer number of complex multiplications required to obtain the least square channel impulse response estimate. In one embodiment, a method is provided for deriving an estimate of a wireless channel in a wireless communication system (e.g., an OFDM system). In accordance with the method, an intermediate vector B is initially obtained, which is derived based on K subvectors of the vector ft for a first channel estimate (e.g., a channel frequency response estimate) and at least two DFT submatrices for the DFT matrix W, where K is an integer greater than one. An intermediate matrix A for the DFT matrix W is also obtained, A second channel estimate (e.g., a least square channel impulse response estimate) is then derived based on the intermediate vector B and the intermediate matrix A. In one implementation, the intermediate vector B is obtained by first computing DFTs of a first matrix HT^L. which is formed based on the vector ft, to provide a second matrix G^XL • Inner products between the columns of a base DFT submatrix W, and the rows of the second matrix G^^L are then computed to obtain the entries of the intermediate vector B. Details of this implementation are described below. Various aspects and embodiments of the invention are described in further detail below. BRIEF DESaUPTION OF THE DRAWINGS The features, nature, and advantages of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like reference characters identify correspondingly throughout and wherein: FIG. 1 shows an OFDM subband structure; FIG. 2A shows the relationship between the frequency response and the impulse response of a wireless channel; FIG. 2B graphically shows a DFT matrix W; FIG. 3 A graphically shows the relationship between DFT matrices W and W; FIG. 3B graphically shows the partitioning of the vector H into K subvectors ind the DFT matrix W into K submatrices; FIG. 3C graphically shows the relationship between the matrices YLict ^nd STXL FIGS. 4 and 5 show two processes for deriving the least square channel impulse ssponse estimate using a low complexity least square method; and FIG. 6 shows a block diagram of an access point and a terminal in a wireless ommunication system. DETAILED DESCRIPTION The channel estimation techniques described herein may be used for any communication system with multiple subbands. For clarity, these techniques arc described specifically for an OFDM system. FIG. 1 shows a subband structure 100 that may be used for an OFDM system. The OFDM system has an overall system bandwidth of W MHz, which is partitioned into N orthogonal subbands using OFDM. Each subband has a bandwidth of W/N MHz. In a typical OFDM system, only M of the N total subbands are used for data transmission, where M as guard subbands to allow the OFDM system to meet spectral mask requirements. The M usable subbands include subbands F through F+M 1. For OFDM, the data to be transmitted on each subband is first modulated (i.e., symbol mapped) using a particular modulation scheme selected for use for that subband. Signal values of zero are provided for the N M unused subbands. For each symbol period, the M modulation symbols and N M zeros for all N subbands are transformed to the time domain using an inverse fast Fourier transform (IFFT) to obtain a "transformed" symbol that includes N timedomain samples. The duration of each transformed symbol is inversely related to the bandwidth of each subband. For example, if the system bandwidth is W = 20 MHz and N = 256, then the bandwidth of each subband is 78.125 KHz (or W/N MHz) and the duration of each transformed symbol is 12.8 jisec (or N/W xsec). , ,, . The N subbands of the OFDM system may experience different channel conditions (e.g., different effects due to fading and raultipath) and may be associated with different complex channel gains. An accurate estimate of the channel response is normally needed in order to properly process (e.g., decode and demodulate) data at the receiver. For clarity, in the following description, lowercase letters are used for indices, uppercase letters are used for constants, and bolded and underlined lower and upper¬case letters are used for vectors and matrices. The wireless channel in the OFDM system may be characterized by either a timedomain channel impulse response, Ii> or a corresponding frequencydomain channel frequency response, H. The channel frequency response H is the discrete Fourier transform (DFT) of the channel impulse response h. This relationship may be expressed in matrix forai, as follows: H = Wh , Eq(l) where h is an (Nxl) vector for the impulse response of the wireless channel between a transmitter and a receiver in the OFDM system; H is an (N x 1) vector for the frequency response of the wireless channel; and W is an (NxN) DFT matrix used to perform the DFT on the vector h to obtain the vector H. The DFT matrix W is defined such that the (n,m) th entry, wJJJ„, is given as: where n is a row index and m is a column index. The vector h includes one nonzero entry for each tap of the channel impulse response. Thus, if the channel impulse response includes L taps, where L FIG. 2A graphically shows the relationship between the channel frequency response H and the channel impulse response h. The vector h includes N timedomain values for the impulse response of the wireless channel from the transmitter to the receiver, where some of the entries in h may be zeros. This vector h can be transformed to the frequency domain by premultiplying it with the matrix W. The vector H includes N frequencydomain values for the complex channel gains of the N subbands. FIG. 2B graphically shows the matrix W, which is an (NxN) matrix comprised of the elements w^„, for n = {1... N and m = {l ... N}, which are defined in equation (2). The superscript " '^" is not shown in FIG. 2B for clarity. Each row of the matrix W corresponds to one of the N total subbands. The impulse response of the wireless channel can be characterized by L taps, where L is typically much less than the number of total subbands (i.e., L Because only L taps are needed for the channel impulse response, the channel frequency response H lies in a subspace of dimension L (instead of N). More specifically, the frequency response of the wireless channel may be fully characterized based on the channel gains for as few as L appropriately selected subbands, instead of all N subbands. Even if more than L channel gains are available, an enhanced estimate of the frequency response of the wireless channel may be obtained by suppressing the noise components outside this subspace. 7 In one channel estimation technique, a more accurate estimate of the frequency response of a wireless channel is obtained based on a 3step process. In the first step, an initial estimate of the channel frequency response, H, is obtained based on the received and transmitted pilot symbols for each of S designated subbands, where S is an integer selected such that L 5 S :£ M. The S designated subbands may include all or only a subset of the M usable subbands. The initial channel frequency response estimate, H, may be expressed as: fi = r,/x,=a+n./x. , Eq(3) where r, is a "receive" vector with S entries for the symbols received on the S designated subbands; X, is a "transmit" vector with S entries for the symbols transmitted on the S designated subbands; H, is an (Sxl) vectors that includes only S entries of the (Nxl) vector H for the S designated subbands; n, is a vector with S entries for additive white Gaussian noise (AWGN) received on the S designated subbands; and Bj / b, = [flj / &, a^lb2 ... ajh^f, which includes S ratios for the S designated subbands. In the second step, a least square estimate of the impulse response of the wireless channel, h , is obtained based on the following optimization: fi'=minjHWhJ^ . Eq(4) fly where h^ is an QLx 1) vector for a hypothesized impulse response of the channel; W is an (SxL) submatrix of the (NxN) matrix W; and h is an (L X1) vector for the least square channel impulse response estimate. FIG. 3A graphically shows the relationship between the matrices W and W. The S rows of the matrix W are the S rows of the matrix W corresponding to the S designated subbands. The L columns of the matrix W are the first L columns of the matrix W. s The solution to equation (4) that results in the minimum mean square error (or more specifically, the minimum Euclidean norm) may be expressed as: h' ^(W"W)'YI"^='W'E . Eq(5) wheie W*' is an (LxS) matrix defined as W* = (W" W)"'w'. In the third step, an enhanced estimate of the fi^quency response of the wireless channel, H , is obtained based on the least square channel impulse response estimate, {i , as follows: j> b _L, * Is H =Wh , Eq(6) where W is a (QxL) submatrix of the (NxN) matrix W; and H[ is a (Q X1) vector for the enhanced channel frequency response estimate for Q desired subbands. The Q rows of the matrix W are the Q rows of the matrix W corresponding to the Q subbands for which the enhanced channel frequency response estimate is desired. In general, the matrix may include any number and any combination of rows of the matrix W. For example, the matrix W may include only the S rows of the matrix ^, the S rows of the matrix W plus one or more additional rows, the M rows of the matrix W for the M usable subbands, and so on. The group of S designated subbands may thus be the same or different from the group of Q desired subbands. Equation (6) indicates that the enhanced channel firequency response estimate fi may be obtained for Q desired subbands based on the least square channel impulse y>& response estimate h that includes only L entries, where L is typically less than S and Q and may be much less than S and Q. ^^^' The 3step channel estimation technique is described in further detail in U.S. Patent Application Serial No. [Attorney Docket No. PD020718], entitled "Channel Estimation for OFDM Communication Systems," filed October 29, 2002. The reduced complexity channel estimation techniques described herein may also be used in conjunction with pilot transmission schemes described in U.S. Patent Application Serial No. 10/340,507, entitled "Uplink Pilot and Signaling Transmission in Wireless Communication Systems," filed October 29,2002. Both of these patent applications are assigned to the assignee of the present application and incorporated herein by reference. ^ An OFDM system may be designed with a relatively large number of subbands. For example, an OFDM system may be designed with 256 total subbands (i.e., N a 256) and 224 usable subbands (i.e., M = 224). In an example design, S may be selected to be equal to 224 for the downlink (i.e., S^, = 224) and equal to 32 for the uplink (i.e., S„, = 32). The number of total subbands may be given with respect to L such that N = L ■ T. The number of designated subbands may also be given with respect to L such that S = K L. For the example design described above with L = 16 and T = 16, K would be equal to 14 for the downlink and to 2 for the uplink (i.e., S^=14LandS„, =2L). A straightforward or bruteforce method for deriving the estimate h using equation (5) would require C^f «L'S complex multiplications for the matrix multiply between the (LxS) matrix W and the (Sxl) vector H. This is because each of the L elements of the vector h requires S complex multiplications for the inner product "Is A between one row of the matrix W and the vector H. For the example OFDM system described above, the number of complex multiplications required to derive the estimate h can be given as C^f = L • L • K = 16 • 16 • K = 256K, where K = 14 for the downlink and K = 2 for the uplink, A large number of complex multiplications may thus be required to derive the estimate h , especially for the downlink. Techniques are provided herein to derive the estimate h using substantially fewer nunibers of complex multiplications than with the bruteforce method. The structure of the matrix W can be exploited to decompose the matrix multiplication W'H in equation (5) into a sum of K matrix multiplications between smaller submatrices of ^ and smaller subvectors of H. The properties of the submatrices of W can be exploited to simplify the computation. The net result is fewer number of )0 complex multiplications required to obtain the estimate h , as described in detail below. The (Sxl) vector H, where S = K • L, can be partitioned into K smaller (Lxl) subvectors, as follows: & Eq(7) M HK. H = Each subvector g^, for fc = {1... K}, may be expressed as: Hit = [^F+(iti)L ^F+(ti)L+i ••• ^F+fcLil > Eq (8) where ^F+(i_j)L+j is the estimated channel gain for subband F+(fcl)L+y, which may be obtained as shown in equation (3); F is the index for the first usable subband, as shown in PIG. 1; and " ^ " denotes the transpose. The (SxL) matrix W, where S = K 'L, can also be partitioned into K smaller (LxL) submatrices, as follows: M .WKJ W = Eq(9) Each submatrix W^, for ^ = {1... K}, is formed based on a different set of L rows of the matrix V^, The concatenation of the K submatrices W^, for fc = {1... K}, would make up the matrix ]ffi. 11 FIG. 3B graphically shows the partitioning of the vector K[ into K subvectors Hj, for ^ = {1 ... K}, and the partitioning of the matrix W into K submatrices W^^, forfc = {l... K}. It can be shown that the K submatrices V^^ are related to each other by the following relationship: W, = W,S, ,for*={2...K}, Eq(lO) where S^ is an (LxL) diagonal matrix that may be given as: Zt^diag le ^ g ^ ... e " Eq(lla) which may be rewritten as: S*=diag .j2„itdl jirtitM .j2„it=Mdl' le T g ^ ...e ^ • Eq(llb) As shown in equation (10), the K submatrices ^^^, for ^ = {1 ... K}, are related to each 6ther, and the matrices H*, for A: = {2 ... K}, may each be derived based on the "base" submatrix Wj. It is observed that the diagonal elements of each matrix 2,^ 'for *^ = (1 — ^1» constitute a "generalized" column of a (TxT) DFT matrix whose elements are defined as shown in equation (2), except that N is replaced by T. For a (TxT) DFT matrix, the row index n and the column index m each run from 1 to T. However, for a generalized column of the (TxT) DFT matrix, the row index n can take on any integer value, and the elements of the generalized column would simply be repeated if and when the row index n exceeds T. In equation (1 lb), L may or may not be equal to T. The row index n for an (LxT) DFT matrix may then extend past the row dimension of the (TxT) DFT matrix if L > T, which would then result in the generalized column. A lowcomplexity least square (LCLS) method may be used to derive the least square channel impulse response estimate h . For the LCLS method, equation (5) is first rewritten using the subvectors jH^ and the submatrices W^, for k = {l ... K}, as follows: ^2 Eq(12) Equation (12) may be expressed as the matrix product of an (LxL) matrix A and an (Lxl) vector B. The matrix A may be expressed as: A«[^twfW,l =(W"W)' . Eq(13) Since the matrix A does not depend on the vector H, it can be computed offline (i.e., precomputed) and stored in a memory unit. The vector S may be expressed as: K Eq (14) B=2:B^rfi,. M Using the relationship for the submatrices W^, for k = {l ... K}, shovm in equation (10), the vector g may be rewritten as: "l 0 A 0 Eq(15) M w,'H, 0 al A M M M O 0 .JlLSit. 0 A 0 «^ where w„ is the mth column of the submatrix ^i; cx^ =e ^ ,for w = {l ... L};and """ denotes the conjugate transpose. Equation (15) may be simplified as follows: K W^} "[t""'^'] B = Eq(16) U WL yj As shown in equation (16), the vector B includes L inner products for the L entries of this vector. Each inner product is computed between the vector w^ and the quantity ]^afj&fc to obtain yv" S^ffi* ■ For each inner product, the quantity V.fc=l J Kk'i J ; computed using one (TxT) DFT, as described below. A (TxT) DFT can be computed using a radix2 fast Fourier transform (FFT), which requires CT_^JI^ = (TlogjT)/! complex multiplications. If the radix2 FFT is used to compute for the vector g based on equation (16), then the number of required complex multiplications is Cg =L'[(Tlog2T)/2+L], where the second L (inside the bracket on the right side of the equation) is for the L complex multiplications needed for /'K the inner product between w" and ^I'^H* , and the first L (on the right side of the equation but outside the bracket) is for the L inner products for the vector B. C^ may also be expressed as Cg = L^ + L • T • logjT / 2. The number of complex multipUcations needed for the matrix multiply of the matrix Ji with the vector B is C^g = L ■ L = L^. The total number of complex multiplications needed to compute the estimate fi using the LCLS method and radix2 FFT and based on equation (16) may then be expressed as: C««u.dix2=C^+C,=2L^+LT.log,T/2 . Eq(17) For the example OFDM system described above, L = 16, T = 16, and K = 14 for the downlink. The total number of complex multiplications needed to compute the estimate h using the bruteforce method based on equation (5) is Cbf =161614 = 3,584. The total number of complex multiplications needed to compute the estimate fi' using the LCLS method with radix2 FFT and based on equation (16) is C,^^Ln.^^ =216^+1616logjie/2 = 1024. This represents a reduction of 71.42% in the number of complex multiplications required to compute the estimate h . The (TxT) DFT can also be computed using a radix4 FFT, which requires CTjadix4 =((T/4l)/(T/2)(Tlog2T) complex multiplications. The total number of /^ complex multiplications needed to compute the estimate fi using the LCLS method and radix4 FFT and based on equation (16) is ^m,LnMxi = 16 ■ 16 +16 • [(3/8)(16 • Iogjl6) +16] = 896. This represents a reduction of 75% in the number of complex multiplications required to compute the estimate fi . Table 1 lists the number of complex multiplications required to compute the channel impulse response estimate h using (1) the bruteforce method and (2) the LCLS method with radix2 and radix4 FFTs. also shows the percentage savings achieved by the LCLS method over the bruteforce method. Table 1 Number of complex multiplications Savings (%) Bruteforce (Cbf) LCLS (Ctotal) Radix2 FFT 3,584 1,024 71.42 Radix4 FFT 3,584 896 75.00 FIG. 4 is a flow diagram of an embodiment of a process 400 for deriving a least square channel impulse response estimate using the low complexity least square method described above. In the following description, the inputs to the process are as follows: • Number of taps for the channel impulse response: L; • Number of total subbands: N = L'T; • Number of designated subbands: S = L • K; and • Initial channel frequency response estimate H with channel gains for the S AAA A ^ designated subbands: H = [Hp Hp+j ... HF+LK_I] • The output of the process is the least square channel impulse response estimate, A> Is A A A • h =[ft, h, ...hj. foitially, the S entries of the (Sxl) vector H are arranged into a (TxL) matrix HTXL (step 412), as follows: )b ^ ^F+Ll ^ ■^F+IL1 0 M ^ "F+LK1 A 0 0 STXL ~ "F+L "F+L+l M M •"F+(L.1)K "F+OLDK+I 0 0 0 0 A Eq(18) As shown in equation (18), the S entries of the vector j& are written rowwise into the matrix fiTxL. starting in the first row and going from left to right. Each row of the H. The matrix H^XL thus matrix HjxL includes L consecutive entries of the vector H. effectively partitions the vector 6 into K (Lxl) subvectors H^, for fc = {l... K}, where each subvector ft;t corresponds to one row of the matrix %iyx^. The matrix jgxxL includes N entries for the N total subbands. Since S is typically less than N, only the first K rows of the matrix H^XL include nonzero values from the vector H and the last (N S) entries in the matrix H^XL are filled with zeros, as shown in equation (18). An (LxT) DPT matrix WL^T is next formed (step 414), The (n,m)th entry, wj„, of the matrix W^fr is defined as: ,^(nlXml) yvl„=e ^ ,forn = {l... L}andm = {l... T}. Eq(19) Each column of the matrix WL^T corresponds to a generalized column of a (TxT) DFT matrix. The mth column of the matrix YLi.,a thus includes L entries that correspond to the diagonal elements of the matrix Z^ shown in equation (lib), where k=m for m = 1 through K. Since the index k for the matrices S* runs from 1 through K but the index m for the columns of the matrix WU Tpoint DFTs of the columns of the matrix ^TXL are then computed using the matrix WLXT (step 416). The DFTs may be expressed as: GLXL' ■ JQLujjHjxL = ii M LML. Eq (20) where g^, for m = {1 ... L}, is an (Lxl) rowvector for the m th row of the matrix Each rowvector g includes L entries, where each entry is obtained based on a Tpoint DPT of one row of the matrix \V,jj^ and one column of the matrix H^XL. as shown in FIG. 3C. Equation (20) essentially performs the computation for the L summations shown in equation (16), isuch that S,„=Z The matrix WLXT includes T columns for T generalized rows of a (TxT) DFT matrix. However, only the first K columns of the matrix W^XT are used for the K matrices 2^, for k = {l ... K}. The last (TK) columns of WLXT are not used, since these columns are multiplied with the last (TK) rows of zeros in the matrix jft^xL • Each of the L entries of the vector B is then obtained by computing an inner product between conjugate transpose of a vector w„ and a corresponding rowvector g (step 418). This inner product may be expressed as: K=ydgl=i„yLn .form = {l...L}, Eq(22) where w„ is the mth column of the (LxL) submatrix Wj, and " * " denotes a conjugate. The submatrix W, is defined such that the (n,m)th entry, wl^„, is given as: •jZit w^ —e , forn = {1... L} and /n = {1 ... L}. The result of step 418 is the vector B = [&, h^ ... h^f. Eq (23) J7 The (LxL) matrix 4 may be precomputed as shown in equation (13) and stored in a memory unit (step 420). The least square channel impulse response estimate A Is h may then be computed by performing a matrix multiply of the matrix A vvith the vector S (step 422). This matrix multiplication may be expressed as: h'=AB . Eq(24) BIG. 5 is a flow diagram of another embodiment of a process 500 for deriving a least square channel impulse response estimate using the low complexity least square method. 19 Initially, an intermediate vector is derived based on (1) K subvectors of a vector for a first channel estimate and (2) at least two DFT submatrices for a DFT matrix (step 512). The intermediate vector may be B, the K subvectors may be jHt, for fc{l... K}, the vector for the first channel estimate may be H, the first channel estimate may be the initial channel frequency response estimate, the at least two DFT submatrices may be W^, for k~{l... K}, and the DFT matrix may be W. The intermediate vector B may then be obtained by (1) performing a matrix multiply of each of the K subvectors with a corresponding one of the K DFT submatrices to obtain a corresponding intermediate subvector W^A^, and (2) accumulating K intermediate subvectors Wffifc, for * = {1... K}, to obtain the intermediate vector ' B, as shown in equation (14). 1 Altematively, the at least two DFT submatrices may be W^^ and W,. The intermediate vector B may then be obtained by (1) computing DFTs of a first matrix HTXL 1 formed based on the vector H for the first channel estimate, to provide a second matrix SLXL . a" vector B, as shown in equations (21) and (22). ^n An intermediate matrix is then obtained, which is derived for the DFT matrix corresponding to the vector for the initial frequency response estimate (step 514). The intcamediate matrix may be the matrix A, which may be derived as shown in equation /^ (13). Again, the matrix A may be precomputed, stored in a memory unit, and retrieved when needed. A second response estimate is then derived based on the intermediate vector and the intermediate matrix (step 516). The second response estimate may be a least square channel impulse response estimate. In the above description, the structure of the matrix W is exploited to greatly reduce the complexity of the derivation of the least square channel impulse response estimate. The reduced complexity channel estimation techniques described herein may also be used to derive other channel estimates. For example, these techniques may possibly be used to derive the enhanced channel frequency response estimate shown in equation (6). In general, these techniques may be used for any problem where multiplication by a submatrix of the DFT matrix is involved. However, the gains achieved by these techniques may be dependent on the setup of the problem. As noted above, the channel estimation techniques described herein may be used for any communication system with multiple subbands, such as OFDM systems. Moreover, these techniques may be used for multipleinput multipleoutput (MIMO) systems that employ multiple (N^.) transmit antennas and multiple (NR) receive antennas for data transmission. For a MEMO system that utilizes OFDM, the response of a wireless MIMO channel may be given as H(k), for ^ = {1 ... N}. Each matrix U.{k) is an (N^XNT) matrix with entries H,^, for i = {l ... N^} and j = {l... N^}, where H^j is the channel gain between the jtransmit antenna and the I'th receive antenna. The techniques described herein may be used to derive the channel response of each transmit/receive antenna pair. FIG. 6 is a block diagram of an embodiment of an access point 600 and a terminal 650, which are capable of deriving the channel estimate using the techniques described herein. On the downlink, at access point 600, traffic data is provided to a TX data processor 610, which formats, codes, and interieaves the traffic data to provide coded data. An OFDM modulator 620 then receives and processes the coded data and pilot symbols to provide a stream of OEDM symbols. The processing by OFDM modulator 620 may include (1) symbol mapping the coded data to form modulation symbols, (2) multiplexing the modulation symbols with pilot symbols, (3) transforming the )1 modulation symbols and pilot symbols to obtain transformed symbols, and (4) appending a cyclic prefix to each transformed symbol to form a corresponding OFDM symbol. For the downlink, the pilot symbols may be multiplexed with the modulation symbols using, for example, time division multiplexing (TDM). For TDM, the pilot symbols and modulation symbols are transmitted on different time slots. The pilot symbols may be transmitted on Sjj designated subbands, where S^ may include all or a subset of the M usable subbands. A transmitter unit (TMTR) 622 then receives and converts the stream of OFDM symbols into one or more analog signals and further conditions (e.g., amplifies, filters, and frequency upconverts) the analog signals to generate a downlink modulated signal suitable for transmission over the wireless channel. The downlink modulated signal is then transmitted via an antenna 624 to the terminals. At terminal 650, the downlink modulated signal is received by antenna 652 and provided to a receiver unit (RCVR) 654. Receiver unit 654 conditions (e.g., filters, amplifies, and frequency downconverts) the received signal and digitizes the conditioned signal to provide samples. An OFDM demodulator 656 then removes the cyclic prefix appended to each OFDM symbol, transforms each recovered transformed symbol using an FFT, and demodulates the recovered modulation symbols to provide demodulated data. An RX data processor 658 then decodes the demodulated data to recover the transmitted traffic data. The processing by OFDM demodulator 656 and RX data processor 658 is complementary to that performed by OFDM modulator 620 and TX data processor 610, respectively, at access point 600. OFDM demodulator 656 may further determine an initial frequency response estimate fij„ for the downlink channel, or provide the received pilot symbols that may be used to derive 6^. A processor 670 receives K^ (or equivalent information) and may derive a least square impulse response estimate h^^ of the wireless channel based on Hjn and using the low complexity least square method described above. Processor 670 may further obtain an enhanced frequency response estimate H^n for the downlink channel based on hj„. The enhanced estimate ^ may thereafter be used for uplink data transmission and/or sent back to the access point for use for downlink data transmission. 2^ On the uplink, traffic data is processed by a TX data processor 682 and provided to an OFDM modulator 684, which also receives pilot symbols. OFDM modulator 684 may then process die coded data and pilot symbols similar to that described for OFDM modulator 620. For the uplink, the pilot symbols may also be multiplexed with the modulation symbols using TDM. Moreover, the pilot symbols may be transmitted on only S„p_, subbands that have been assigned to terminal 650 for pilot transmission. A transmitter unit 686 then receives and processes the stream of OFDM symbols to generate an uplink modulated signal suitable for transmission over the wireless channel. The modulated signal is then transmitted via an antenna 652 to the access point. At access point 600, the uplink modulated signal is processed by a receiver unit 642 to provide samples. These samples are then processed by an OFDM demodulator 644 to provide demodulated data, which are further processed by an RX data processor 646 to recover the transmitted traffic data. OFDM demodulator 644 may determine the initial frequency response estimate H„p, for the uplink channel for each active terminal or provide the received pilot symbols that may be used to obtain H^_,. A processor 630 receives H„p, (or equivalent information) for each active terminal, determines the least square channel impulse response estimate Q^,,, for the active terminal based on j&„p_, and using the low complexity least square method, and further obtains the enhanced channel frequency response estimate H„p, based on h„p_,. The enhanced estimate H„p^, may thereafter be used for downlink data transmission to the terminal and/or sent back to the terminal for use for uplink data transmission. Processors 630 and 670 direct the operation at the access point and terminal, respectively. Memory units 632 and 672 provide storage for program codes and data used by controllers 630 and 670, respectively. Processors 630 and 670 may be designed to perform the computation described above to derive estimates of the uplink and downlink channels, respectively. The reduced complexity channel estimation techniques described herein may be implemented by various means. For example, these techniques may be implemented in 21 hardware, software, or a combination thereof. For a hardware implementation, the elements used to implement any one or a combination of the techniques may be implemented' within one or more application specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (EPGAs), processors, controllers, microcontrollers, microprocessors, other electronic units designed to praform the functions described herein, or a combination thereof. For a software implementation, the channel estimation techniques may be implemented with modules (e.g., procedures, functions, and so on) that perform the functions described herein. The software codes may be stored in a memory unit (e.g., memory units 632 or 672 in FIG. 6) and executed by a processor (e.g., processor 630 or 670). The memory unit may be implemented within the processor or external to the processor, in which case it can be communicatively coupled to the processor via various means as is known in the art. The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein. 2^' WE CLAIM: 1. A method for deriving an estimate of a wireless channel in a wireless communication system, comprising the steps of: obtaining an intermediate vector based on K subvectors of a vector for a first channel estimate and at least two discrete Fourier transform (DFT) submatrices for a DFT matrix, wherein the DFT matrix corresponds to the vector for the first channel estimate and K is an integer greater than one; obtaining an intermediate matrix for the DFT matrix; and deriving a second channel estimate based on the intermediate vector and the intermediate matrix. 2. The method as claimed in claim 1, wherein the first channel estimate is a channel frequency response estimate and the second channel estimate is a channel impulse response estimate for the wireless channel. 3. The method as claimed in claim 1, wherein comprising the step of determining the intermediate vector based on where B is the intermediate vector, Wyt is a /tth DFT submatrix among K DFT submatrices of the DFT matrix, H_i^ is a k\h. subvector among the K subvectors for the first channel estimate, and " is a conjugate transpose. 4. The method as claimed in claim 1, wherein the at least two DFT submatrices has K DFT submatrices corresponding to the K subvectors, and wherein the obtaining the intermediate vector comprises performing a matrix multiply of each of the K subvectors with a corresponding one of the K DFT submatrices to obtain a corresponding intermediate subvector, and accumulating K intermediate subvectors, obtained from the matrix multiply of the K subvectors with the K DFT submatrices, to obtain the intermediate vector. 23 5. The method as claimed in claim 1, wherein the obtaining the intermediate vector comprises computing discrete Fourier transforms of a first matrix, formed based on the vector for the first channel estimate, to provide a second matrix, and computing inner products between columns of a base DFT submatrix and rows of the second matrix to obtain the intermediate vector. 6. The method as claimed in claim 5, wherein the DFT of the first matrix is computed using a radix2 fast Fourier transform. 7. The method as claimed in claim 5, wherein the DFT of the first matrix is computed using a radix4 fast Fourier transform. 8. The method as claimed in claim 1, wherein comprising the step of determining the intermediate matrix based on A = f '^ V' where A is the intermediate matrix, W^ is a kXh DFT submatrix among K DFT submatrices of the DFT matrix, and '^ is a conjugate transpose. 9. The method as claimed in claim 1, wherein the intermediate matrix is precomputed. 10. The method as claimed in claim 1, wherein the second channel estimates is a least square estimate based on the first channel estimate, and wherein the intermediate vector and the intermediate matrix are two parts of the least square estimate. 11. The method as claimed in claim 2, comprising: deriving an enhanced channel frequency response estimate based on the channel impulse response estimate. 24 12. The method as claimed in claim 11, wherein the channel frequency response estimate covers a first group of subbands and the enhanced channel frequency response estimate covers a second group of subbands. 13. The method as claimed in claim 12, wherein the first group comprises a subset of the subbands in the second group. 14. The method as claimed in claim 1, wherein the wireless communication system is an orthogonal frequency division multiplexing (OFDM) communication system. 15. The method as claimed in claim 1 comprising the step of: obtaining an intermediate matrix derived based on the K DFT submatrices. 16. A method for deriving an estimate of a wireless channel in an orthogonal frequency division multiplexing (OFDM) communication system, comprising: forming a first matrix for an initial frequency response estimate of the wireless channel; computing discrete Fourier transforms (DFTs) of the first matrix to obtain a second matrix; computing inner products between a base DFT submatrix and the second matrix to obtain an intermediate vector; obtaining an intermediate matrix derived for a DFT matrix for the initial frequency response estimate; and deriving a channel impulse response estimate based on the intermediate vector and the intermediate matrix. 17. The method as claimed in claim 16, comprising: deriving an enhanced frequency response estimate for the wireless channel based on the channel impulse response estimate. 25 18. A wireless communication system for performing the method as claimed in any one of the preceding claims. 

0934chenp2005 power of attorney.pdf
0934chenp2005 complete specification as granted.pdf
0934chenp2005 correspondence po.pdf
0934chenp2005 correspondence others.pdf
0934chenp2005 description(complete).pdf
Patent Number  235236  

Indian Patent Application Number  934/CHENP/2005  
PG Journal Number  29/2009  
Publication Date  17Jul2009  
Grant Date  26Jun2009  
Date of Filing  16May2005  
Name of Patentee  QUALCOMM INCORPORATED  
Applicant Address  5775 MOREHOUSE DRIVE, SAN DIEGO, CALIFORNIA 92121  
Inventors:


PCT International Classification Number  H04B  
PCT International Application Number  PCT/US03/36232  
PCT International Filing date  20031112  
PCT Conventions:
