To Solomon Golomb for the occasion of his 80 birthday mazal tov Delay-Doppler Channel Estimation in Almost Linear Complexity

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 the delay-Doppler parameters is thematched filter algorithm. It uses a pseudo-random sequence of length, and, in case of non-trivial relative velocity between transmitter and receiver, its computa-tional complexity is. 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 delay-Doppler parameters in operations. We discuss applications of the flag method to GPS, and radar systems. Index Terms—Channel estimation, fast matched filter, fast moving users, flag method, GPS, Heisenberg-Weil sequences, high-frequency communication, radar, sequence design, time-fre-quency shift problem. I