Maximum likelihood decoding of trellis codes in fading channels with no receiver CSI is a polynomial-complexity problem

The problem of optimal decoding of a trellis coded sequence transmitted over a frequency nonselective, time-selective fading channel is considered in this paper. In particular, the case where the channel state information (CSI) is unknown to the receiver, thus Viterbi´s algorithm (VA) can not be employed to find the maximum a posteriori probability sequence detection (MAPSqD) solution with linear complexity in sequence length N. It is proved that for two-state trellis, the exact solution can indeed be obtained with only polynomial complexity in N for any signal-to-noise ratio.