PreprintAlmost linear complexity methods for delayDoppler channel estimationAlexander Fish, Shamgar GurevichAbstractA 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 delayDoppler channel, i.e., a signal undergoes only delay and Doppler shifts, a widely used method to compute delayDoppler parameters is the pseudorandom method. It uses a pseudorandom sequence of length \(N\); and, in case of nontrivial 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 delayDoppler 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 triplechirp and doublechirp 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.
