Subexponential-complexity exact sequence detection in the presence of frequency and phase uncertainty

The problem of joint data detection and frequency/phase estimation is considered in this work. The traditional belief regarding exact generalized-likelihood-based joint detection and estimation is that its complexity is exponential in the sequence length N. This belief is justified due to the memory imposed on the transmitted sequence by the lack of knowledge of the auxiliary channel parameters. In this paper, we show that the exact solution can be performed with O(N⁵) worst-case complexity regardless of the operating signal-to-noise ratio. In addition, based on the exact solution, we propose an approximate algorithm with O(N³) complexity and demonstrate its performance through simulations.