Efficient conjugate gradient based channel estimator
In forming a current channel estimate from a received signal y, the received signal y is decoded to form data s, a convolution matrix Ŝis formed from a first portion of the data s, a matrix F 1 is formed from a second portion the data s such that the second portion of the data s includes data that is less recent that the data in the first portion of the data s, a matrix F 2 is formed from a third portion the data s such that the third portion of the data s includes data that is more recent than the data in the first portion of the data s, a predicted channel estimate h pred is determined, and a conjugate gradient algorithm is performed to determine the current channel estimate. The conjugate gradient algorithm is based on the received signal y, the matrix Ŝ, the matrices F 1 and F 2 , the predicted channel estimate h pred , and a previous channel estimate h 1 .
1. A method of processing a received signal y to produce a current channel estimate from one or more past channel estimates that include a previous channel estimate h 1 comprising:
(a) decoding the received signal y to form data s;
(b) forming a convolution matrix Ŝ from a first portion of the data s;
(c) forming a matrix F 1 from a second portion the data s, wherein the second portion of the data s includes data that is less recent than the data in the first portion of the data s;
(d) forming a matrix F 2 from a third portion the data s, wherein the third portion of the data s includes data that is more recent than the data in the first portion of the data s;
(e) determining a predicted channel estimate h pred based on the one or more past channel estimates; and,
(f) performing a conjugate gradient algorithm to determine the current channel estimate, wherein the conjugate gradient algorithm is based on the received signal y, the matrix Ŝ, the matrices F 1 and F 2 , the predicted channel estimate h pred , and the previous channel estimate h 1 .
2. The method of claim 1 wherein the determining of a predicted channel estimate comprises extrapolating the predicted channel estimate h pred from k of the past channel estimates.
3. The method of claim 2 wherein k≧2.
4. The method of claim 1 wherein the received signal y, the matrix Ŝ, the matrices F 1 and F 2 , the predicted channel estimate h pred , and the previous channel estimate h 1 are related according to the following equation:
ŷ=y−F 1 h 1 −F 2 h pred .
5. The method of claim 4 wherein the conjugate gradient algorithm is performed to solve the following equation:
ŷ=Sh
wherein h comprises the current channel estimate.
6. The of claim 4 wherein the performing of a conjugate gradient algorithm to determine the current channel estimate comprises performing the following algorithm:
(1) ŷ=y−F 1 h 1 −F 2 h pred ,
r 1 =Ŝ T ŷ−Ŝ T Ŝh 1
(2) For k=1 to n, iteratively calculate
(a) d k =r k +β k d k−1
(b) h k+1 =h k +α k d k
(c) r k+1 =r k −α k q k−1
where β 1 =0,
β
k
≥
2
=
r
k
T
·
r
k
r
k
-
1
T
·
r
k
-
1
,
where
α
k
=
r
k
T
·
r
k
d
k
·
q
k
,
and where q k =S T Sd k .
7. The method of claim 6 wherein q k is determined by forming a first FFT of the matrix Ŝ, by forming a second FFT of the matrix Ŝ T , by forming a third FFT of d k , by multiplying the first, second, and third FFTs to produce a multiplication result, and by forming an inverse FFT of the multiplication result.
8. The method of claim 6 wherein the forming of a matrix Ŝ from the data s comprises:
forming a matrix S from the data s, wherein the matrix S contains the first, second, and third portions of the data s; and,
forming the matrix Ŝ from the matrix S by setting the second and third portions of the data s to zero;
wherein the forming of a matrix F 1 from the data s comprises:
forming the matrix F 1 from the matrix S by setting the first and third portions of the data s to zero; and,
wherein the forming of a matrix F 2 from the data s comprises:
forming the matrix F 2 from the matrix S by setting the first and second portions of the data s to zero.
9. The method of claim 8 wherein q k is determined by forming a first FFT of the matrix Ŝ, by forming a second FFT of the matrix Ŝ T , by forming a third FFT of d k , by multiplying the first, second, and third FFTs to produce a multiplication result, and by forming an inverse FFT of the multiplication result.
10. The method of claim 1 wherein the performing of a conjugate gradient algorithm comprises determining a quantity q k according to the following equation:
q k =Ŝ T Ŝd k ,
wherein d k is dependent upon the received signal y, the matrix Ŝ, and the matrices F 1 and F 2 , and wherein q k is determined by forming a first FFT of the matrix Ŝ, by forming a second FFT of the matrix Ŝ T , by forming a third FFT of d k , by multiplying the first, second, and third FFTs to produce a multiplication result, and by forming an inverse FFT of the multiplication result.
11. The method of claim 1 wherein the forming of a matrix Ŝ from the data s comprises:
forming a matrix S from the data s, wherein the matrix S contains the first, second, and third portions of the data s; and,
forming the matrix Ŝ from the matrix S by setting the second and third portions of the data s to zero;
wherein the forming of a matrix F 1 from the data s comprises:
forming the matrix F 1 from the matrix S by setting the first and third portions of the data s to zero; and,
wherein the forming of a matrix F 2 from the data s comprises:
forming the matrix F 2 from the matrix S by setting the first and second portions of the data s to zero.
12. The method of claim 11 wherein the performing of a conjugate gradient algorithm comprises determining a quantity q k according to the following equation:
q k =Ŝ T Ŝd k ,
wherein d k is dependent upon the received signal y, the matrix Ŝ, and the matrices F 1 and F 2 , and wherein q k is determined by forming a first FFT of the matrix Ŝ, by forming a second FFT of the matrix Ŝ T , by forming a third FFT of d k , by multiplying the first, second, and third FFTs to produce a multiplication result, and by forming an inverse FFT of the multiplication result.
13. A method of processing a received signal y to produce a current channel estimate from one or more past channel estimates that include a previous channel estimate h 1 comprising:
(a) decoding the received signal y to form data s;
(b) forming a convolution matrix Ŝ from a first portion of the data s;
(c) forming a matrix F 1 from a second portion the data s, wherein the second portion of the data s includes data that is less recent than the data in the first portion of the data s;
(d) forming a matrix F 2 from a third portion the data s, wherein the third portion of the data s includes data that is more recent than the data in the first portion of the data s;
(e) determining a predicted channel estimate h pred based on the one or more past channel estimates; and,
(f) performing a conjugate gradient algorithm to determine the current channel estimate, wherein the conjugate gradient algorithm is based on the received signal y, the matrix Ŝ, the matrices F 1 and F 2 , the predicted channel estimate h pred , and the previous channel estimate h 1 , wherein the conjugate gradient algorithm includes (i) forming FFTs based on the received signal y, the matrix Ŝ, and the matrices F 1 and F 2 , (ii) multiplying the FFTs to form a multiplication product, and (iii) forming an inverse FFT of the multiplication product.
14. The method of claim 13 wherein the determining of a predicted channel estimate h pred comprises extrapolating the predicted channel estimate from k ones of the past channel estimates.
15. The method of claim 14 wherein k≧2.
16. The method of claim 13 wherein the received signal y, the matrix Ŝ, the matrices F 1 and F 2 , the predicted channel estimate h pred , and the previous channel estimate h 1 are related according to the following equation:
ŷ=y−F 1 h 1 −F 2 h pred .
17. The method of claim 16 wherein the conjugate gradient algorithm is performed to solve the following equation:
ŷ=Sh
wherein h comprises the current channel estimate.
18. The method of claim 16 wherein the performing of a conjugate gradient algorithm to determine the current channel estimate comprises performing the following algorithm:
(1) ŷ=y−F 1 h 1 −F 2 h pred ,
r 1 =Ŝ T ŷ−Ŝ T Ŝh 1
(2) For k=1 to n, iteratively calculate
(a) d k =r k +β k d k−1
(b) h k+1 =h k +α k d k
(c) r k+1 =r k −α k q k−1
where β 1 =0,
β
k
≥
2
=
r
k
T
·
r
k
r
k
-
1
T
·
r
k
-
1
,
where
α
k
=
r
k
T
·
r
k
d
k
·
q
k
,
where q k =S T Sd k .
19. The method of claim 18 wherein q k is determined by forming a first FFT of the matrix Ŝ, by forming a second FFT of the matrix Ŝ T , by forming a third FFT of d k , by multiplying the first, second, and third FFTs to produce a multiplication result, and by forming an inverse FFT of the multiplication result.
20. The method of claim 18 wherein the forming of a matrix Ŝ from the data s comprises:
forming a matrix S from the data s, wherein the matrix S contains the first, second, and third portions of the data s; and,
forming the matrix Ŝ from the matrix S by setting the second and third portions of the data s to zero;
wherein the forming of a matrix F 1 from the data s comprises:
forming the matrix F 1 from the matrix S by setting the first and third portions of the data s to zero; and,
wherein the forming of a matrix F 2 from the data s comprises:
forming the matrix F 2 from the matrix S by setting the first and second portions of the data s to zero.
21. The method of claim 20 wherein q k is determined by forming a first FFT of the matrix S, by forming a second FFT of the matrix Ŝ T , by forming a third FFT of d k , by multiplying the first, second, and third FFTs to produce a multiplication result, and by forming an inverse FFT of the multiplication result.
22. The method of claim 13 wherein the performing of a conjugate gradient algorithm comprises determining a quantity q k according to the following equation:
q k =Ŝ T Ŝd k ,
wherein d k is dependent upon the received signal y, the matrix Ŝ, and the matrices F 1 and F 2 , and wherein q k is determined by forming a first FFT of the matrix Ŝ, by forming a second FFT of the matrix Ŝ T , by forming a third FFT of d k , by multiplying the first, second, and third FFTs to produce a multiplication result, and by forming an inverse FFT of the multiplication result.
23. The method of claim 13 wherein the forming of a matrix Ŝ from the data s comprises:
forming a matrix S from the data s, wherein the matrix S contains the first, second, and third portions of the data s; and,
forming the matrix Ŝ from the matrix S by setting the second and third portions of the data s to zero;
wherein the forming of a matrix F 1 from the data s comprises:
forming the matrix F 1 from the matrix S by setting the first and third portions of the data s to zero; and,
wherein the forming of a matrix F 2 from the data s comprises:
forming the matrix F 2 from the matrix S by setting the first and second portions of the data s to zero.
24. The method of claim 23 wherein the performing of a conjugate gradient algorithm comprises determining a quantity q k according to the following equation:
q k =Ŝ T Ŝd k ,
wherein d k is dependent upon the received signal y, the matrix Ŝ, and the matrices F 1 and F 2 , and wherein q k is determined by forming a first FFT of the matrix Ŝ, by forming a second FFT of the matrix Ŝ T , by forming a third FFT of d k , by multiplying the first, second, and third FFTs to produce a multiplication result, and by forming an inverse FFT of the multiplication result.