On joint ML detection and decoding for linear block codes

We consider joint maximum-likelihood (ML) detection and decoding in multiple-input multiple-output (MIMO) systems. The information data is encoded by a linear block error-correcting code and then transmitted across the MIMO channel in AWGN. Geometrically, the transmitted symbol is a point in a high-dimensional lattice. The received symbol is the lattice point perturbed by an additive noise. The joint detection and decoding problem is equivalent to the search for the closest lattice point that is an admissible codeword. We propose an algorithm which performs a search constrained by a sphere centered at the observed point. The radius of the sphere is determined according to the statistics of the noise. Thus the computational complexity of the algorithm is a random variable. We quantify it by means of its first moment which, for binary codes, we And analytically. The expected complexity of the proposed algorithm is polynomial in the length of the uncoded information word over a wide range of SNRs