## Almost linear complexity methods for delay-Doppler channel estimation

### Alexander Fish, Shamgar Gurevich

#### 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, i.e., a signal undergoes only delay and Doppler shifts, a widely used method to compute delay-Doppler parameters is the pseudo-random method. 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 logN)$$ arithmetic operations. In [1] the ﬂag method was introduced to provide a faster algorithm for delay-Doppler channel estimation. It uses specially designed flag sequences and its complexity is $$O(rN logN)$$ for channels of sparsity $$r$$. In these notes, we introduce the incidence and cross methods for channel estimation. They use triple-chirp and double-chirp sequences of length $$N$$, correspondingly. These sequences are closely related to chirp sequences widely used in radar systems. The arithmetic complexity of the incidence and cross methods is $$O(N logN+r^3)$$, and $$O(N logN+r^2)$$, respectively.

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

 Friday, September 27, 2013