Maximum-Likelihood Noncoherent OSTBC Detection with Polynomial Complexity

We prove that maximum-likelihood (ML) noncoherent sequence detection of orthogonal space-time block coded signals can always be performed in polynomial time with respect to the sequence length for static Rayleigh, correlated (in general) channels. Moreover, using recent results on efficient maximization of rank-deficient quadratic forms over finite alphabets, we develop an algorithm that performs ML noncoherent sequence detection with polynomial complexity. The order of the polynomial complexity of the proposed receiver equals two times the rank of the covariance matrix of the vectorized channel matrix. Therefore, the lower the Rayleigh channel covariance rank the lower the receiver complexity. Instead, for Ricean channel distribution, we prove that polynomial complexity is attained through the proposed receiver as long as the mean channel vector is in the range of the covariance matrix of the vectorized channel matrix. Hence, full-rank channel correlation is desired to guarantee polynomial ML noncoherent detection complexity for the case of static Ricean fading. Our results are presented for the general case of block-fading Rayleigh or Ricean channels where we provide conditions under which ML noncoherent sequence detection can be performed in polynomial time through our algorithm.