We study fast lattice decodability of space-time block codes for n transmit and receive antennas, written very generally as a linear combination Σi=12lsiAi, where the si are real information symbols and the Aiare n×n ℝ-linearly independent complex-valued matrices. We show that the mutual orthogonality condition AiAj* + AjAi* = 0 for distinct basis matrices is not only sufficient but also necessary for fast decodability. We build on this to show that for full-rate (l = n2) transmission, the decoding complexity can be no better than |S|(n2+1), where |S| is the size of the effective real signal constellation. We also show that for full-rate transmission, g-group decodability, as defined by Jithamithra and Rajan, is impossible for any g ≥ 2. We then use the theory of Azumaya algebras to derive bounds on the maximum number of groups into which the basis matrices can be partitioned so that the matrices in different groups are mutually orthogonal-a key measure of fast decodability. We show that in general, this maximum number is of the order of only the 2-adic value of n. In the case where the matrices Aiarise from a division algebra, which is most desirable for diversity, we show that the maximum number of groups is only 4. As a result, the decoding complexity for this case is no better than |S|⌈l/2⌉ for any rate l.

We study fast decodability for general rate space-time block codes. We derive bounds on the number of generators that can be in mutually orthogonal groups and use these to show that that the ML decoding complexity of a full-rate n × n space-time block code is unfortunately quite high: at least of the order of |S|n2+1, where S is the effective real constellation. We also show that g-group decodability is not possible for full-rate codes.

Perfect space-time codes are codes for the coherent multiple-input multiple-output (MIMO) channel. They have been called so since they satisfy a large number of design criteria that makes their performances outmatch many other codes. In this correspondence, we discuss the existence of such codes (or more precisely, the existence of perfect codes with optimal signal complexity).