A decoder generates distance and label metrics associated with each label of a coset transmitted in a multi-input multi-output communication system having Mt transmit antennas and Mr receive antennas by performing 2(“u+n”)(Mt−1) searches, where n is the number of encoded bits used to identify one of 2u cosets at the transmitting end and u is the number of unencoded bits used to select one of 2u labels at the transmitting end. The decoder forms an intermediate vector quantity associated with one of the transmit antennas to compute the metrics associated with each of the remaining transmit antennas. The decoder then forms a second intermediate vector quantity to compute the metrics associated with the transmit antenna that was used to form the first intermediate variable. The metrics so computed are used by a Viterbi decoder to identify the coset and the most likely transmitted label in that coset.