Delay-Doppler Channel Estimation with Almost Linear Complexity

A. Fish, S. Gurevich, R. Hadani, A. Sayeed, O. Schwartz

Abstract

A fundamental task in wireless communication is Channel Estimation: Compute the channel parameters a signal undergoes while traveling 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 sequence of length $N$, and, in case of non-trivial relative velocity between transmitter and receiver, its computational complexity is $O(N^2\log (N))$. In this paper we introduce a novel approach of designing sequences that allow faster channel estimation. Using group representation techniques we construct sequences, 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(mN\log (N))$ operations, for channel of sparsity $m$. We discuss applications of the flag method to GPS, radar system, and mobile communication as well.