A fundamental task in wireless communication is channel estimation: Compute the channel parameters a signal undergoes while travelling from a transmitter to a receiver. In the case of delay-Doppler channel, a widely used method is the matched filter algorithm. It uses a pseudo-random waveform of length N; and, in case of non-trivial relative velocity between transmitter and receiver, its arithmetic complexity is O(N2log(N)). We introduce a novel approach of designing waveforms that allow much faster channel estimation. Using Heisenberg-Weil representation we construct waveforms, which enable us to introduce a new algorithm, called the flag method, that significantly improves the matched filter algorithm. The flag method finds the channel parameters in O(mNlog(N)) operations (in certain applications N << 1000), for channel of sparsity m. We discuss applications of the flag method to mobile communication of fast moving users, and GPS.
This is a joint work with Gurevich (UW-Madison), Hadani (UT-Austin), Sayeed (UW-Madison), and Schwartz (UC-Berkeley).