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 flag method was introduced to provide a faster algorithm for delay-Doppler channel estimation. It uses specially designed flag sequences and its complexity is $O(rNlogN)$ 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(NlogN+r^3)$, and $O(NlogN+r^2)$, respectively.