On the sphere decoding complexity of high rate multigroup ML decodable STBCs

A Space-Time Block Code (STBC) is said to be multigroup ML decodable if the information symbols encoded by it can be partitioned into two or more groups, such that each group of symbols can be ML decoded independently of the other symbol groups. In this paper, we show that the upper triangular matrix R encountered during the sphere decoding of a linear dispersion STBC can be rank-deficient even when the rate of the code is less than the minimum of the number of transmit and receive antennas. We then show that all known families of high rate (rate greater than 1) multigroup ML decodable codes have rank-deficient R matrix, even when the rate is less than the number of transmit and receive antennas, and this rank-deficiency problem arises only when the number of receive antennas is strictly less than the number of transmit antennas. Unlike the codes with full-rank R matrix, the average sphere decoding complexity of the STBCs whose R matrix is rank-deficient is polynomial in the constellation size, and hence is high. We derive the sphere decoding complexity of most of the known high rate multigroup ML decodable codes, and show that for each code, the complexity is a decreasing function of the number of receive antennas.