## 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.

This paper is available as a pdf (1640kB) file.

 Tuesday, October 16, 2012