Method and apparatus for soft bit computation in MIMO decoders

Abstract

Forward Error Correction (FEC) is an essential component of most digital communication systems. The decoders for the FEC perform better when working in soft-decision mode using the Log Likelihood Ratios (LLRs) as the input. Spatial Multiplexing (SM) with Multiple Input Multiple Output (MIMO) is used in many systems for providing high data rate. When SM-MIMO is used in conjunction with FEC, it is important for SM-MIMO decoders to provide soft channel bits to the FEC decoder. The complexity of the SM-MIMO decoders is generally very high, especially when LLRs need to be generated for each bit of the decoded symbol. Conventional methods for LLR generation in SM-MIMO decoders require the storage and sorting of partial and cumulative distance. A method and apparatus are disclosed that compute the LLRs on the fly without requiring extensive storage or sorting of partial and cumulative distance metrics.

Claims

1. A method for decoding first and second signals received at a same antenna in a multiple input multiple output (MIMO) communication system, wherein the first signal includes a symbol-1 to which K1 bits are mapped from a constellation point of a first modulation constellation formed by M1=2.sup.K1 first constellation points representative respectively of M1 symbols-M/1 used by the MIMO system, wherein each first constellation point is associated with a codeword having K1 bits b.sub.0, b.sub.1, . . . , b.sub.K1-1, and wherein the second signal includes a symbol-2 to which K2 bits are mapped from a constellation point of a second modulation constellation formed by M2=2.sup.K2 second constellation points representative respectively of M2 symbols-M/2 used by the MIMO system, wherein each second constellation point is associated with a codeword having K2 bits b.sub.0, b.sub.1, . . . , b.sub.K2-1, the method comprising: controlling, by a processing device, a first stage of distance computations, in which the first stage of distance computations includes: (I) performing first minimum distance computations for first symbols S.sub.a, S.sub.b, S.sub.c, and S.sub.d corresponding to respective first constellation points of the first constellation, wherein the first minimum distance computations include: generating, using distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d respectively of the first symbols S.sub.a, S.sub.b, S.sub.c and S.sub.d determined with respect to a transformation of the first received signal having a symbol representation according to the first constellation, minimum distance values respectively corresponding to the bits b.sub.0, b.sub.1, b.sub.2 and b.sub.3, in which: (i) a minimum of the distance metrics DS.sub.a and DS.sub.b determined by a first comparator circuit is input to a first input of a second comparator circuit, (ii) a minimum distance value for the bit b.sub.0=0 stored at a first register is input to a second input of the second comparator circuit, and (iii) a minimum of the first input and the second input of the second comparator circuit is determined by the second comparator circuit, output from an output of the second comparator circuit to an input of the first register and stored by the first register as the stored minimum distance value for the bit b.sub.0=0, (i) a minimum of the distance metrics DS.sub.c and DS.sub.d determined by a third comparator circuit is input to a first input of a fourth comparator circuit, (ii) a minimum distance value for the bit b.sub.0=1 stored at a second register is input to a second input of the fourth comparator circuit, and (iii) a minimum of the first input and the second input of the fourth comparator circuit is determined by the fourth comparator circuit, output from an output of the fourth comparator circuit to an input of the second register and stored by the second register as the stored minimum distance value for the bit b.sub.0=1, (i) a minimum of the distance metrics DS.sub.a and DS.sub.d determined by a fifth comparator circuit is input to a first input of a sixth comparator circuit, (ii) a minimum distance value for the bit b.sub.1=0 stored at a third register is input to a second input of the sixth comparator circuit, and (iii) a minimum of the first input and the second input of the sixth comparator circuit is determined by the sixth comparator circuit, output from an output of the sixth comparator circuit to an input of the third register and stored by the third register as the stored minimum distance value for the bit b.sub.1=0, (i) a minimum of the distance metrics DS.sub.b and DS.sub.c determined by a seventh comparator circuit is input to a first input of a eighth comparator circuit, (ii) a minimum distance value for the bit b.sub.1=1 stored at a fourth register is input to a second input of the eighth comparator circuit, and (iii) a minimum of the first input and the second input of the eighth comparator circuit is determined by the eighth comparator circuit, output from an output of the eighth comparator circuit to an input of the fourth register and stored by the fourth register as the stored minimum distance value for the bit b.sub.1=1, (i) a minimum of the distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d determined by a ninth comparator circuit is input to a first input of a tenth comparator circuit, (ii) a minimum distance value for the bit b.sub.2=0 stored at a fifth register is input to a second input of the tenth comparator circuit, and (iii) a minimum of the first input and the second input of the tenth comparator circuit is determined by the tenth comparator circuit, output from an output of the tenth comparator circuit to an input of the fifth register and stored by the fifth register as the stored minimum distance value for the bit b.sub.2=0, and (i) the minimum of the distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d from the ninth comparator circuit is input to a first input of an eleventh comparator circuit, (ii) a minimum distance value for the bit b.sub.3=0 stored at a sixth register is input to a second input of the eleventh comparator circuit, and (iii) a minimum of the first input and the second input of the eleventh comparator circuit is determined by the eleventh comparator circuit, output from an output of the eleventh comparator circuit to an input of the sixth register stored by the sixth register as the stored minimum distance value for the bit b.sub.3=0; (II) performing second minimum distance computations for second symbols S.sub.e, S.sub.f, S.sub.g, and S.sub.h corresponding to respective first constellation points of the first constellation, wherein the second minimum distance computations include: generating, using distance metrics DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h respectively of the second symbols S.sub.e, S.sub.f, S.sub.g and S.sub.h determined with respect to the transformation of the first received signal, the minimum distance values respectively corresponding to the bits b.sub.0, b.sub.1, b.sub.2 and b.sub.3, in which: (i) a minimum of the distance metrics DS.sub.e and DS.sub.f determined by a twelfth comparator circuit is input to a first input of a thirteenth comparator circuit, (ii) the minimum distance value for the bit b.sub.0=0 stored at a seventh register is input to a second input of the thirteenth comparator circuit, and (iii) a minimum of the first input and the second input of the thirteenth comparator circuit is determined by the thirteenth comparator circuit, output from an output of the thirteenth comparator circuit to an input of the seventh register and stored by the seventh register as the stored minimum distance value for the bit b.sub.0=0, (i) a minimum of the distance metrics DS.sub.g and DS.sub.h determined by a fourteenth comparator circuit is input to a first input of a fifteenth comparator circuit, (ii) the minimum distance value for the bit b.sub.0=1 stored at an eighth register is input to a second input of the fifteenth comparator circuit, and (iii) a minimum of the first input and the second input of the fifteenth comparator circuit is determined by the fifteenth comparator circuit, output from an output of the thirteenth circuit to an input of the eighth register and stored by the eighth register as the stored minimum distance value for the bit b.sub.0=1, (i) a minimum of the distance metrics DS.sub.e and DS.sub.h determined by a sixteenth comparator circuit is input to a first input of a seventeenth comparator circuit, (ii) the minimum distance value for the bit b.sub.1=0 stored at a ninth register is input to a second input of the seventeenth comparator circuit, and (iii) a minimum of the first input and the second input of the seventeenth comparator circuit is determined by the seventeenth comparator circuit, output from an output of the seventeenth comparator circuit to an input of the ninth register and stored by the ninth register as the stored minimum distance value for the bit b.sub.1=0, (i) a minimum of the distance metrics DS.sub.f and DS.sub.g determined by an eighteenth comparator circuit is input to a first input of a nineteenth comparator circuit, (ii) the minimum distance value for the bit b.sub.1=1 stored at a tenth register is input to a second input of the nineteenth comparator circuit, and (iii) a minimum of the first input and the second input of the nineteenth comparator circuit is determined by the nineteenth comparator circuit, output from an output of the nineteenth comparator circuit to an input of the tenth register and stored by the tenth register as the stored minimum distance value for the bit b.sub.1=1, (i) a minimum of the distance metrics DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h determined by a twentieth comparator circuit is input to a first input of a twenty-first comparator circuit, (ii) a minimum distance value for the bit b.sub.2=1 stored at an eleventh register is input to a second input of the twenty-first comparator circuit, and (iii) a minimum of the first input and the second input of the twenty-first comparator circuit is determined by the twenty-first comparator circuit, output from an output of the twenty-first comparator circuit to an input of the eleventh register and stored by the eleventh register as the stored minimum distance value for the bit b.sub.2=1, and (i) the minimum of the distance metrics DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h from the twentieth comparator circuit is input to a first input of an twenty-second comparator circuit, (ii) a minimum distance value for the bit b.sub.3=1 stored at a twelfth register is input to a second input of the twenty-second comparator circuit, and (iii) a minimum of the first input and the second input of the twenty-second comparator circuit is determined by the twenty-second comparator circuit, output from an output of the twenty-second comparator circuit to an input of the twelfth register and stored by the twelfth register as the stored minimum distance value for the bit b.sub.3=1; controlling, by the processing device, performing a second stage of distance computations including: for each of L of the symbols-M/1, wherein L is less than M1, generating, using all of the symbols-M/2 represented in the second constellation, a minimum distance value respectively corresponding to the bits b.sub.0, b.sub.1, b.sub.2 and b.sub.3 with respect to a transformation of the second received signal having a symbol representation according to the second constellation, wherein the L symbols correspond to symbols represented in the first constellation having L lowest minimum distance metrics as determined from the first stage of distance computations, and when a minimum distance value corresponding to a given bit equal to one or zero for the L symbols is determined not to be available after the generating of the minimum distance values for each of the L symbols with all of the symbols-M/2, the minimum distance value corresponding to the given bit equal to one or zero determined in the first stage of distance computations is stored as the minimum distance value of the given bit equal to one or zero as determined by the second stage of distance computations; and controlling, by the processing device, after the first and second stages of distance computations are performed, determining, for each bit b, a Log-Likelihood Ratio (LLR) by subtracting the minimum distance value for the bit b being equal to 1 from the minimum distance value for the bit b being equal to 0, and transmitting the LLR for the each bit b to a Forward Error Correction (FEC) decoder.

2. The method of claim 1, wherein the first symbols are selected such that minimum distance values respectively corresponding to the K1 bits of a codeword for a given symbol corresponding to a given first constellation point of the first constellation can be generated without using each of stored minimum distance values respectively corresponding to the K1 bits of the codeword.

3. The method of claim 1, wherein, for each of the bits b, the stored minimum distance value for a given bit b being each of equal to one and zero is initialized to a maximum value according to a bit-width of a given register in which the stored minimum distance value is stored.

4. The method of claim 1, wherein the first and second symbols are selected such that, after minimum distance computations are performed to generate minimum distance values corresponding to the K1 bits for all symbols represented in the first constellation remaining unprocessed after the first and second minimum distance computations are performed, the stored minimum distance value for each of the bits b being equal to zero and one is other than an original initialized value.

5. The method of claim 4, wherein the minimum distances values are generated for a given selected set of four symbols of the remaining unprocessed symbols by performing the first or second minimum distance computations, according to whether representation of the four symbols of the given selected set in the first constellation corresponds to the representation of the first symbols or the second symbols in the first constellation.

6. The method of claim 1, wherein the first minimum distance computations for the first symbols are performed without generating the minimum distance values for the bit b.sub.2=1 and the bit b.sub.3=1, and wherein the second minimum distance computations for the second symbols are performed without generating the minimum distance values for the bit b.sub.2=0 and the bit b.sub.3=0.

7. The method of claim 1, wherein, when K1 is greater than four, (i) the performing the first minimum distance computations for the first symbols S.sub.a, S.sub.b, S.sub.c and S.sub.d includes generating minimum distance values for each bit b.sub.i=4 to K1-1 equal to zero, in which a minimum of (a) the minimum of the distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d and (b) a stored minimum distance value for the bit b.sub.i=0, is determined and stored as the stored minimum distance value for the bit b.sub.i=0; and (ii) the performing the second minimum distance computations for the second symbols S.sub.e, S.sub.f, S.sub.g and S.sub.h includes generating minimum distance values for each bit b.sub.i=4 to K1-1 equal to one, in which a minimum of (a) the minimum of the distance metrics DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h and (b) a stored minimum distance value for the bit b.sub.i=1, is determined and stored as the stored minimum distance value for the bit b.sub.i=1.

8. An apparatus for decoding first and second signals received at a same antenna in a multiple input multiple output (MIMO) communication system, wherein the first signal includes a symbol-1 to which K1 bits are mapped from a constellation point of a first modulation constellation formed by M1=2.sup.K1 first constellation points representative respectively of M1 symbols-M/1 used by the MIMO system, wherein each first constellation point is associated with a codeword having K1 bits b.sub.0, b.sub.1, . . . , b.sub.K1-1, and wherein the second signal includes a symbol-2 to which K2 bits are mapped from a constellation point of a second modulation constellation formed by M2=2.sup.K2 second constellation points representative respectively of M2 symbols-M/2 used by the MIMO system, wherein each second constellation point is associated with a codeword having K2 bits b.sub.0, b.sub.1, . . . , b.sub.K2-1, the apparatus comprising: circuitry configured to control: a first stage of distance computations, in which the first stage of distance computations includes: (I) performing first minimum distance computations for first symbols S.sub.a, S.sub.b, S.sub.c, and S.sub.d corresponding to respective first constellation points of the first constellation, wherein the first minimum distance computations include: generating, using distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d respectively of the first symbols S.sub.a, S.sub.b, S.sub.c and S.sub.d determined with respect to a transformation of the first received signal having a symbol representation according to the first constellation, minimum distance values respectively corresponding to the bits b.sub.0, b.sub.1, b.sub.2 and b.sub.3, in which: (i) a minimum of the distance metrics DS.sub.a and DS.sub.b determined by a first comparator circuit is input to a first input of a second comparator circuit, (ii) a minimum distance value for the bit b.sub.0=0 stored at a first register is input to a second input of the second comparator circuit, and (iii) a minimum of the first input and the second input of the second comparator circuit is determined by the second comparator circuit, output from an output of the second comparator circuit to an input of the first register and stored by the first register as the stored minimum distance value for the bit b.sub.0=0, (i) a minimum of the distance metrics DS.sub.c and DS.sub.d determined by a third comparator circuit is input to a first input of a fourth comparator circuit, (ii) a minimum distance value for the bit b.sub.0=1 stored at a second register is input to a second input of the fourth comparator circuit, and (iii) a minimum of the first input and the second input of the fourth comparator circuit is determined by the fourth comparator circuit, output from an output of the fourth comparator circuit to an input of the second register and stored by the second register as the stored minimum distance value for the bit b.sub.0=1, (i) a minimum of the distance metrics DS.sub.a and DS.sub.d determined by a fifth comparator circuit is input to a first input of a sixth comparator circuit, (ii) a minimum distance value for the bit b.sub.1=0 stored at a third register is input to a second input of the sixth comparator circuit, and (iii) a minimum of the first input and the second input of the sixth comparator circuit is determined by the sixth comparator circuit, output from an output of the sixth comparator circuit to an input of the third register and stored by the third register as the stored minimum distance value for the bit b.sub.1=0, (i) a minimum of the distance metrics DS.sub.b and DS.sub.c determined by a seventh comparator circuit is input to a first input of a eighth comparator circuit, (ii) a minimum distance value for the bit b.sub.1=1 stored at a fourth register is input to a second input of the eighth comparator circuit, and (iii) a minimum of the first input and the second input of the eighth comparator circuit is determined by the eighth comparator circuit, output from an output of the eighth comparator circuit to an input of the fourth register and stored by the fourth register as the stored minimum distance value for the bit b.sub.1=1, (i) a minimum of the distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d determined by a ninth comparator circuit is input to a first input of a tenth comparator circuit, (ii) a minimum distance value for the bit b.sub.2=0 stored at a fifth register is input to a second input of the tenth comparator circuit, and (iii) a minimum of the first input and the second input of the tenth comparator circuit is determined by the tenth comparator circuit, output from an output of the tenth comparator circuit to an input of the fifth register and stored by the fifth register as the stored minimum distance value for the bit b.sub.2=0, and (i) the minimum of the distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d from the ninth comparator circuit is input to a first input of an eleventh comparator circuit, (ii) a minimum distance value for the bit b.sub.3=0 stored at a sixth register is input to a second input of the eleventh comparator circuit, and (iii) a minimum of the first input and the second input of the eleventh comparator circuit is determined by the eleventh comparator circuit, output from an output of the eleventh comparator circuit to an input of the sixth register stored by the sixth register as the stored minimum distance value for the bit b.sub.3=0; (II) performing second minimum distance computations for second symbols S.sub.e, S.sub.f, S.sub.g, and S.sub.h corresponding to respective first constellation points of the first constellation, wherein the second minimum distance computations include: generating, using distance metrics DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h respectively of the second symbols S.sub.e, S.sub.f, S.sub.g and S.sub.h determined with respect to the transformation of the first received signal, the minimum distance values respectively corresponding to the bits b.sub.0, b.sub.1, b.sub.2 and b.sub.3, in which: (i) a minimum of the distance metrics DS.sub.e and DS.sub.f determined by a twelfth comparator circuit is input to a first input of a thirteenth comparator circuit, (ii) the minimum distance value for the bit b.sub.0=0 stored at a seventh register is input to a second input of the thirteenth comparator circuit, and (iii) a minimum of the first input and the second input of the thirteenth comparator circuit is determined by the thirteenth comparator circuit, output from an output of the thirteenth comparator circuit to an input of the seventh register and stored by the seventh register as the stored minimum distance value for the bit b.sub.0=0, (i) a minimum of the distance metrics DS.sub.g and DS.sub.h determined by a fourteenth comparator circuit is input to a first input of a fifteenth comparator circuit, (ii) the minimum distance value for the bit b.sub.0=1 stored at an eighth register is input to a second input of the fifteenth comparator circuit, and (iii) a minimum of the first input and the second input of the fifteenth comparator circuit is determined by the fifteenth comparator circuit, output from an output of the thirteenth circuit to an input of the eighth register and stored by the eighth register as the stored minimum distance value for the bit b.sub.0=1, (i) a minimum of the distance metrics DS.sub.e and DS.sub.h determined by a sixteenth comparator circuit is input to a first input of a seventeenth comparator circuit, (ii) the minimum distance value for the bit b.sub.1=0 stored at a ninth register is input to a second input of the seventeenth comparator circuit, and (iii) a minimum of the first input and the second input of the seventeenth comparator circuit is determined by the seventeenth comparator circuit, output from an output of the seventeenth comparator circuit to an input of the ninth register and stored by the ninth register as the stored minimum distance value for the bit b.sub.1=0, (i) a minimum of the distance metrics DS.sub.f and DS.sub.g determined by an eighteenth comparator circuit is input to a first input of a nineteenth comparator circuit, (ii) the minimum distance value for the bit b.sub.1=1 stored at a tenth register is input to a second input of the nineteenth comparator circuit, and (iii) a minimum of the first input and the second input of the nineteenth comparator circuit is determined by the nineteenth comparator circuit, output from an output of the nineteenth comparator circuit to an input of the tenth register and stored by the tenth register as the stored minimum distance value for the bit b.sub.1=1, (i) a minimum of the distance metrics DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h determined by a twentieth comparator circuit is input to a first input of a twenty-first comparator circuit, and (ii) a minimum distance value for the bit b.sub.2=1 stored at an eleventh register is input to a second input of the twenty-first comparator circuit, and (iii) a minimum of the first input and the second input of the twenty-first comparator circuit is determined by the twenty-first comparator circuit, output from an output of the twenty-first comparator circuit to an input of the eleventh register and stored by the eleventh register as the stored minimum distance value for the bit b.sub.2=1, and (i) the minimum of the distance metrics DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h from the twentieth comparator circuit is input to a first input of an twenty-second comparator circuit, and (ii) a minimum distance value for the bit b.sub.3=1 stored at a twelfth register is input to a second input of the twenty-second comparator circuit, and (iii) a minimum of the first input and the second input of the twenty-second comparator circuit is determined by the twenty-second comparator circuit, output from an output of the twenty-second comparator circuit to an input of the twelfth register and stored by the twelfth register as the stored minimum distance value for the bit b.sub.3=1; wherein the circuitry is configured to control performing a second stage of distance computations including: for each of L of the symbols-M/1, wherein L is less than M1, generating, using all of the symbols-M/2 represented in the second constellation, a minimum distance value respectively corresponding to the bits b.sub.0, b.sub.1, b.sub.2 and b.sub.3 with respect to a transformation of the second received signal having a symbol representation according to the second constellation, wherein the L symbols correspond to symbols represented in the first constellation having L lowest minimum distance metrics as determined from the first stage of distance computations, and when a minimum distance value corresponding to a given bit equal to one or zero for the L symbols is determined not to be available after the generating of the minimum distance values for each of the L symbols with all of the symbols-M/2, the minimum distance value corresponding to the given bit equal to one or zero determined in the first stage of distance computations is stored as the minimum distance value of the given bit equal to one or zero as determined by the second stage of distance computations; and wherein the circuitry is configured to control, after the first and second stages of distance computations are performed, determining, for each bit b, a Log-Likelihood Ratio (LLR) by subtracting the minimum distance value for the bit b being equal to 1 from the minimum distance value for the bit b being equal to 0, and transmitting the LLR for the each bit b to a Forward Error Correction (FEC) decoder.

9. The apparatus of claim 8, wherein the first symbols are selected such that minimum distance values respectively corresponding to the K1 bits of a codeword for a given symbol corresponding to a given first constellation point of the first constellation can be generated without using each of stored minimum distance values respectively corresponding to the K1 bits of the codeword.

10. The apparatus of claim 8, wherein the first and second symbols are selected such that, after minimum distance computations are performed to generate minimum distance values corresponding to the K1 bits for all symbols represented in the first constellation remaining unprocessed after the first and second minimum distance computations are performed, the stored minimum distance value for each of the bits b being equal to zero and one is other than an original initialized value.

11. The apparatus of claim 10, wherein the minimum distances values are generated for a given selected set of four symbols of the remaining unprocessed symbols by performing the first or second minimum distance computations, according to whether representation of the four symbols of the given selected set in the first constellation corresponds to the representation of the first symbols or the second symbols in the first constellation.

12. The apparatus of claim 8, wherein, when K1 is greater than four, (i) the performing the first minimum distance computations for the first symbols S.sub.a, S.sub.b, S.sub.c and S.sub.d includes generating minimum distance values for each bit b.sub.i=4 to K1-1 equal to zero, in which a minimum of (a) the minimum of the distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d and (b) a stored minimum distance value for the bit b.sub.i=0, is determined and stored as the stored minimum distance value for the bit b.sub.i=0; and (ii) the performing the second minimum distance computations for the second symbols S.sub.e, S.sub.f, S.sub.g and S.sub.h includes generating minimum distance values for each bit b.sub.i=4 to K1-1 equal to one, in which a minimum of (a) the minimum of the distance metrics DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h and (b) a stored minimum distance value for the bit b.sub.i=1, is determined and stored as the stored minimum distance value for the bit b.sub.i=1.

13. A wireless communication device comprising: a receiver to receive a signal in a multiple input multiple output (MIMO) communication system; and a processing device and a memory including instructions which, when executed by the processing device, control decoding first and second signals received at a same antenna of the wireless communication device, wherein the first signal includes a symbol-1 to which K1 bits are mapped from a constellation point of a first modulation constellation formed by M1=2.sup.K1 first constellation points representative respectively of M1 symbols-M/1 used by the MIMO system, wherein each first constellation point is associated with a codeword having K1 bits b.sub.0, b.sub.1, . . . , b.sub.K1-1, wherein the second signal includes a symbol-2 to which K2 bits are mapped from a constellation point of a second modulation constellation formed by M2=2.sup.K2 second constellation points representative respectively of M2 symbols-M/2 used by the MIMO system, wherein each second constellation point is associated with a codeword having K2 bits b.sub.0, b.sub.1, . . . , b.sub.K2-1, and wherein the instructions, when executed by the processing device, control: a first stage of distance computations, in which the first stage of distance computations includes: (I) performing first minimum distance computations for first symbols S.sub.a, S.sub.b, S.sub.c, and S.sub.d corresponding to respective first constellation points of the first constellation, wherein the first minimum distance computations include: generating, using distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d respectively of the first symbols S.sub.a, S.sub.b, S.sub.c and S.sub.d determined with respect to a transformation of the first received signal having a symbol representation according to the first constellation, minimum distance values respectively corresponding to the bits b.sub.0, b.sub.1, b.sub.2 and b.sub.3, in which: (i) a minimum of the distance metrics DS.sub.a and DS.sub.b determined by a first comparator circuit is input to a first input of a second comparator circuit, (ii) a minimum distance value for the bit b.sub.0=0 stored at a first register is input to a second input of the second comparator circuit, and (iii) a minimum of the first input and the second input of the second comparator circuit is determined by the second comparator circuit, output from an output of the second comparator circuit to an input of the first register and stored by the first register as the stored minimum distance value for the bit b.sub.0=0, (i) a minimum of the distance metrics DS.sub.c and DS.sub.d determined by a third comparator circuit is input to a first input of a fourth comparator circuit, (ii) a minimum distance value for the bit b.sub.0=1 stored at a second register is input to a second input of the fourth comparator circuit, and (iii) a minimum of the first input and the second input of the fourth comparator circuit is determined by the fourth comparator circuit, output from an output of the fourth comparator circuit to an input of the second register and stored by the second register as the stored minimum distance value for the bit b.sub.0=1, (i) a minimum of the distance metrics DS.sub.a and DS.sub.d determined by a fifth comparator circuit is input to a first input of a sixth comparator circuit, (ii) a minimum distance value for the bit b.sub.1=0 stored at a third register is input to a second input of the sixth comparator circuit, and (iii) a minimum of the first input and the second input of the sixth comparator circuit is determined by the sixth comparator circuit, output from an output of the sixth comparator circuit to an input of the third register and stored by the third register as the stored minimum distance value for the bit b.sub.1=0, (i) a minimum of the distance metrics DS.sub.b and DS.sub.c determined by a seventh comparator circuit is input to a first input of a eighth comparator circuit, (ii) a minimum distance value for the bit b.sub.1=1 stored at a fourth register is input to a second input of the eighth comparator circuit, and (iii) a minimum of the first input and the second input of the eighth comparator circuit is determined by the eighth comparator circuit, output from an output of the eighth comparator circuit to an input of the fourth register and stored by the fourth register as the stored minimum distance value for the bit b.sub.1=1, (i) a minimum of the distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d determined by a ninth comparator circuit is input to a first input of a tenth comparator circuit, (ii) a minimum distance value for the bit b.sub.2=0 stored at a fifth register is input to a second input of the tenth comparator circuit, and (iii) a minimum of the first input and the second input of the tenth comparator circuit is determined by the tenth comparator circuit, output from an output of the tenth comparator circuit to an input of the fifth register and stored by the fifth register as the stored minimum distance value for the bit b.sub.2=0, and (i) the minimum of the distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d from the ninth comparator circuit is input to a first input of an eleventh comparator circuit, (ii) a minimum distance value for the bit b.sub.3=0 stored at a sixth register is input to a second input of the eleventh comparator circuit, and (iii) a minimum of the first input and the second input of the eleventh comparator circuit is determined by the eleventh comparator circuit, output from an output of the eleventh comparator circuit to an input of the sixth register stored by the sixth register as the stored minimum distance value for the bit b.sub.3=0; (II) performing second minimum distance computations for second symbols S.sub.e, S.sub.f, S.sub.g, and S.sub.h corresponding to respective first constellation points of the first constellation, wherein the second minimum distance computations include: generating, using distance metrics DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h respectively of the second symbols S.sub.e, S.sub.f, S.sub.g and S.sub.h determined with respect to the transformation of the first received signal, the minimum distance values respectively corresponding to the bits b.sub.0, b.sub.1, b.sub.2 and b.sub.3, in which: (i) a minimum of the distance metrics DS.sub.e and DS.sub.f determined by a twelfth comparator circuit is input to a first input of a thirteenth comparator circuit, (ii) the minimum distance value for the bit b.sub.0=0 stored at a seventh register is input to a second input of the thirteenth comparator circuit, and (iii) a minimum of the first input and the second input of the thirteenth comparator circuit is determined by the thirteenth comparator circuit, output from an output of the thirteenth comparator circuit to an input of the seventh register and stored by the seventh register as the stored minimum distance value for the bit b.sub.0=0, (i) a minimum of the distance metrics DS.sub.g and DS.sub.h determined by a fourteenth comparator circuit is input to a first input of a fifteenth comparator circuit, (ii) the minimum distance value for the bit b.sub.0=1 stored at an eighth register is input to a second input of the fifteenth comparator circuit, and (iii) a minimum of the first input and the second input of the fifteenth comparator circuit is determined by the fifteenth comparator circuit, output from an output of the thirteenth circuit to an input of the eighth register and stored by the eighth register as the stored minimum distance value for the bit b.sub.0=1, (i) a minimum of the distance metrics DS.sub.e and DS.sub.h determined by a sixteenth comparator circuit is input to a first input of a seventeenth comparator circuit, (ii) the minimum distance value for the bit b.sub.1=0 stored at a ninth register is input to a second input of the seventeenth comparator circuit, and (iii) a minimum of the first input and the second input of the seventeenth comparator circuit is determined by the seventeenth comparator circuit, output from an output of the seventeenth comparator circuit to an input of the ninth register and stored by the ninth register as the stored minimum distance value for the bit b.sub.1=0, (i) a minimum of the distance metrics DS.sub.f and DS.sub.g determined by an eighteenth comparator circuit is input to a first input of a nineteenth comparator circuit, (ii) the minimum distance value for the bit b.sub.1=1 stored at a tenth register is input to a second input of the nineteenth comparator circuit, and (iii) a minimum of the first input and the second input of the nineteenth comparator circuit is determined by the nineteenth comparator circuit, output from an output of the nineteenth comparator circuit to an input of the tenth register and stored by the tenth register as the stored minimum distance value for the bit b.sub.1=1, (i) a minimum of the distance metrics DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h determined by a twentieth comparator circuit is input to a first input of a twenty-first comparator circuit, (ii) a minimum distance value for the bit b.sub.2=1 stored at an eleventh register is input to a second input of the twenty-first comparator circuit, and (iii) a minimum of the first input and the second input of the twenty-first comparator circuit is determined by the twenty-first comparator circuit, output from an output of the twenty-first comparator circuit to an input of the eleventh register and stored by the eleventh register as the stored minimum distance value for the bit b.sub.2=1, and (i) the minimum of the distance metrics DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h from the twentieth comparator circuit is input to a first input of an twenty-second comparator circuit, (ii) a minimum distance value for the bit b.sub.3=1 stored at a twelfth register is input to a second input of the twenty-second comparator circuit, and (iii) a minimum of the first input and the second input of the twenty-second comparator circuit is determined by the twenty-second comparator circuit, output from an output of the twenty-second comparator circuit to an input of the twelfth register and stored by the twelfth register as the stored minimum distance value for wherein the instructions, when executed by the processing device, control performing a second stage of distance computations including: for each of L of the symbols-M/1, wherein L is less than M1, generating, using all of the symbols-M/2 represented in the second constellation, a minimum distance value respectively corresponding to the bits b.sub.0, b.sub.1, b.sub.2 and b.sub.3 with respect to a transformation of the second received signal having a symbol representation according to the second constellation, wherein the L symbols correspond to symbols represented in the first constellation having L lowest minimum distance metrics as determined from the first stage of distance computations, and when a minimum distance value corresponding to a given bit equal to one or zero for the L symbols is determined not to be available after the generating of the minimum distance values for each of the L symbols with all of the symbols-M/2, the minimum distance value corresponding to the given bit equal to one or zero determined in the first stage of distance computations is stored as the minimum distance value of the given bit equal to one or zero as determined by the second stage of distance computations; and wherein the instructions, when executed by the processing device, control, after the first and second stages of distance computations are performed, determining, for each bit b, a Log-Likelihood Ratio (LLR) by subtracting the minimum distance value for the bit b being equal to 1 from the minimum distance value for the bit b being equal to 0, and transmitting the LLR for the each bit b to a Forward Error Correction (FEC) decoder.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 illustrates a conventional mobile wireless communication system.

(2) FIG. 2 illustrates an example SM-MIMO wireless communication system with two transmit chains at the transmit entity and two receive chains at the receive entity, which may be employed with aspects of the disclosure described herein.

(3) FIG. 3 illustrates the constellation of 16-QAM, which may be employed with aspects of the disclosure described herein.

(4) FIG. 4 illustrates the partitioning of 16-QAM constellation for Log-Likelihood Ratio computation which may be employed with aspects of the disclosure described herein.

(5) FIG. 5 illustrates the QPSK, 16-QAM, and 64-QAM constellations which may be employed with aspects of the disclosure described herein.

(6) FIG. 6 illustrates a particular subset of four symbols chosen from the 16-QAM constellation for distance computation and for minimum distance metric computation according to the aspects of the present disclosure.

(7) FIG. 7 illustrates the computation of minimum distances for each bit from the computed distance metrics for the selected subset of four symbols from the 16-QAM constellation according to the aspects of the present disclosure.

(8) FIG. 8 illustrates another particular subset of four symbols chosen from the 16-QAM constellation for distance computation and for minimum distance metric computation according to the aspects of the present disclosure.

(9) FIG. 9 illustrates the computation of minimum distances for each bit from the computed distance metrics for another selected subset of four symbols from the 16-QAM constellation according to the aspects of the present disclosure.

(10) FIG. 10 illustrates a particular subset of four symbols chosen from the 64-QAM constellation for distance computation and for minimum distance metric computation according to the aspects of the present disclosure.

(11) FIG. 11 illustrates the computation of minimum distances for each bit from the computed distance metrics for the selected subset of four symbols from the 64-QAM constellation according to the aspects of the present disclosure.

(12) FIG. 12 illustrates another particular subset of four symbols chosen from the 64-QAM constellation for distance computation and for minimum distance metric computation according to the aspects of the present disclosure.

(13) FIG. 13 illustrates the computation of minimum distances for each bit from the computed distance metrics for another selected subset of four symbols from the 64-QAM constellation according to the aspects of the present disclosure.

(14) FIG. 14 illustrates the particular subset of symbols chosen from first stage processing for distance computation in the next stage of processing.

(15) FIG. 15 illustrates the LLR computation method according to the aspects of the present disclosure for the case of tree search based SM-MIMO decoder with missing distance metrics for the counter-hypotheses.

(16) FIG. 16 illustrates a wireless mobile station diagram, which may be employed with aspects of the disclosure described herein.

(17) FIG. 17 illustrates an application processor subsystem for a wireless mobile station, which may be employed with aspects of the disclosure described herein.

(18) FIG. 18 illustrates a baseband subsystem for a wireless mobile station, which may be employed with aspects of the disclosure described herein.

(19) FIG. 19 illustrates an RF subsystem for a wireless mobile station, which may be employed with aspects of the disclosure described herein.

DETAILED DESCRIPTION

(20) The foregoing aspects, features and advantages of the present disclosure will be further appreciated when considered with reference to the following description of exemplary embodiments and accompanying drawings, wherein like reference numerals represent like elements. In describing the exemplary embodiments of the disclosure illustrated in the appended drawings, specific terminology will be used for the sake of clarity. However, the aspects of the disclosure are not intended to be limited to the specific terms used.

(21) The tree search methods perform the decoding of the symbol vector one symbol at a time in successive stages. The partial distance metrics computed at each stage are used in subsequent stages for computing cumulative distance metrics. For each stage of the processing, multiple distance metrics may be computed at any given instance of time for high throughput. A method and apparatus are disclosed that explores multiple hypotheses and multiple counter-hypotheses in parallel as the distance metric for each of the candidate symbol vectors is computed at each stage. Without loss of generality, the method is illustrated first for the case of 16-QAM and 22 SM-MIMO system.

(22) To illustrate the aspects of the disclosure, the received signal at the receiver in FIG. 2 may be expressed in matrix form as follows:

(23) $\begin{array}{cc}\left[\begin{array}{c}{x}_0\\ x_1\end{array}\right]=\left[\begin{array}{cc}{h}_{0,0}& h_{0,1}\\ h_{1,0}& h_{1,1}\end{array}\right]\left[\begin{array}{c}{s}_0\\ s_1\end{array}\right]+\left[\begin{array}{c}{n}_0\\ n_1\end{array}\right]& \left(5\right)\end{array}$

(24) As illustrated in FIG. 2, s.sub.0 and s.sub.1 are the transmitted SM-MIMO encoded signals, h.sub.i,j are the channel responses for the four propagation paths where i={0,1} and j={0,1} correspond to antenna indices, x.sub.0 and x.sub.1 are the received SM-MIMO encoded signals at the receiver, and n.sub.0 and n.sub.1 are the additive white Gaussian noise signals for each of the two receive antennas respectively.

(25) After applying QR decomposition to EQ. (5), the following equivalent system of equations, suitable for tree search methods, is obtained:

(26) $\begin{array}{cc}\left[\begin{array}{c}{y}_0\\ y_1\end{array}\right]=\left[\begin{array}{cc}{r}_{0,0}& r_{0,1}\\ 0& r_{1,1}\end{array}\right]\left[\begin{array}{c}{s}_0\\ s_1\end{array}\right]+\left[\begin{array}{c}{w}_0\\ w_1\end{array}\right]& \left(6\right)\\ \mathrm{where}& \\ y=\left[\begin{array}{c}{y}_0\\ y_1\end{array}\right],R=\left[\begin{array}{cc}{r}_{0,0}& r_{0,1}\\ 0& r_{1,1}\end{array}\right],\mathrm{and}w=\left[\begin{array}{c}{w}_0\\ w_1\end{array}\right]\mathrm{are}\mathrm{transformed}\mathrm{versions}\mathrm{of}\left[\begin{array}{c}{x}_0\\ x_1\end{array}\right],\left[\begin{array}{cc}{h}_{0,0}& h_{0,1}\\ h_{1,0}& h_{1,1}\end{array}\right],\mathrm{and}\left[\begin{array}{c}{n}_0\\ n_1\end{array}\right]& \end{array}$
respectively after QR decomposition.

(27) For the first stage distance computations in EQ. (6), the last row corresponding to a single non-zero entry in the matrix R is evaluated for all possible values of s.sub.1 from the constellation using the following distance metric computation:
D.sub.s1=|y.sub.1r.sub.1,1s.sub.1|.sup.2(7)

(28) The transformed received signal y.sub.1 and the element r.sub.1,1 of the matrix R are complex and in general can have any value within the specified resolution of the data type of a particular variable. The modulation symbol s.sub.1 is chosen from a fixed set of constellation symbols. For example, from FIG. 3, in case of 16-QAM there are only 16 different values a symbol can take.

(29) For the case of 16-QAM constellation, in the first stage of a tree search SM-MIMO decoder, there are 16 distance metrics to be computed. Depending on implementation architecture, these distance metrics may be computed in parallel. For example, four distance metrics corresponding to four symbols from the 16-QAM constellation may be computed in parallel.

(30) According to an aspect of the present disclosure, the symbols chosen for distance computation in a given computation cycle are such that the symmetry of the constellation is used to reduce the actual number of multiplications and additions/subtractions to perform the distance computations as shown in FIG. 6, where four symbols denoted as S.sub.a, S.sub.b, S.sub.c, and S.sub.d are used in a first subset of symbol for distance computations. Also, the symbols are chosen such that the binary codeword for each symbol is such that the multiple parallel hypotheses for minimum distance can be performed in parallel without requiring multi-port access to each of the registers holding the minimum distance metric for any of the bits as shown in FIG. 7.

(31) According to an aspect of the present disclosure, using the four distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d, corresponding to the four selected symbols S.sub.a, S.sub.b, S.sub.c, and S.sub.d from the constellation in FIG. 6, four minimum distance metrics corresponding to bits b.sub.0, b.sub.1, b.sub.2, and b.sub.3 being equal to zero are generated by the set of comparators Min2 in FIG. 7. At the same time four minimum distance metrics corresponding to bits b.sub.0, b.sub.1, b.sub.2, and b.sub.3 being equal to one are generated by the using the same comparators.

(32) According to an aspect of the present disclosure, for bit b.sub.0, in the chosen subset of four symbols, there are only two symbols S.sub.a and S.sub.b with bit b.sub.0=0 as illustrated in FIG. 6. Therefore, the minimum of the distances DS.sub.a and DS.sub.b is the minimum distance metric for bit b.sub.0=0. Specifically, the comparator Min2 702 accepts two input distance metric values DS.sub.a and DS.sub.b and outputs smaller of the two values and becomes one of the inputs to the comparator Min2 704. The second input to the comparator Min2 704 is from the minimum distance holding register 706 for the bit b.sub.0=0. The output of the comparator Min2 704 is stored back into the holding register 706. Similarly, there are only two symbols S.sub.c and S.sub.d with bit b.sub.0=1. Therefore, the minimum of the distances DS.sub.c and DS.sub.d is the minimum distance metric for bit b.sub.0=1. Similar type of processing is performed on the two input distance metric values DS.sub.c and DS.sub.d using the comparators 708 and 710 and the holding register 712 for the bit b.sub.0=1.

(33) According to an aspect of the present disclosure, for bit b.sub.1, in the chosen subset of four symbols, there are only two symbols S.sub.a and S.sub.d with bit b.sub.1=0. Therefore, the minimum of the distances DS.sub.a and DS.sub.d is the minimum distance metric for bit b.sub.1=0. Similarly, there are only two symbols S.sub.b and S.sub.c with bit b.sub.1=1. Therefore, the minimum of the distances DS.sub.b, and DS.sub.c is the minimum distance metric for bit b.sub.1=1. Similar processing is performed for bit b.sub.1 using the four distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d as input and the four comparators 714, 716, 720, and 722 and the two holding registers 718 and 724.

(34) According to an aspect of the present disclosure, for bit b.sub.2, in the chosen subset of four symbols, all four symbols have bit b.sub.2=0 and no symbol with bit b.sub.2=1. Therefore, the minimum of all the four distances is the minimum distance metric for bit b.sub.2=0. The output of the comparator 714 and the comparator 720 are input to the comparator 726 whose output provides the minimum over all four distance metrics. The output of the comparator is input to the comparator 728. The second input to the comparator 728 is the output of the minimum distance holding register 730 for the bit b.sub.2=0. The output of the comparator 728 is stored back into the holding register 730. Since there is no symbol with bit b.sub.2=1, the minimum distance metric for bit b.sub.2=1 cannot be updated. According to an aspect of the present disclosure, the comparator 732 may be disabled or unused when a subset of symbols, for example, the first subset is selected such that the selected subset may not contain any symbol with bit b.sub.2=1. This is shown by a dashed line input to the comparator 732 in FIG. 7.

(35) According to an aspect of the present disclosure, for bit b.sub.3, in the chosen subset of four symbols, all four symbols have bit b.sub.3=0 and no symbol with bit b.sub.3=1. Therefore, the minimum of all the four distances is the minimum distance metric for bit b.sub.3=0. The output of the comparator 726, which is the minimum over all four distance metrics, is input to the comparator 736. The second input to the comparator 736 is the output of the minimum distance holding register 738 for the bit b.sub.3=0. The output of the comparator 728 is stored back into the holding register 738. Since there is no symbol with bit b.sub.3=1, the minimum distance metric for bit b.sub.3=1 cannot be updated. According to an aspect of the present disclosure, the comparator 740 may be disabled or unused when a subset of symbols, for example, the first subset, is selected such that the selected subset may not contain any symbol with bit b.sub.3=1. This is shown by a dashed line input to the comparator 740 in FIG. 7.

(36) According to an aspect of the present disclosure, in the next processing cycle, a different subset of four symbols from the 16-QAM constellation denoted as S.sub.e, S.sub.f, S.sub.g, and S.sub.h is used as shown in FIG. 8. Four distance metrics DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h for these chosen symbols are computed first and then the minima are selected as described below.

(37) According to an aspect of the present disclosure, for bits b.sub.0 and b.sub.1 the processing remains the same as the processing for the first subset of four symbols as illustrated in FIG. 6 and FIG. 7.

(38) According to an aspect of the present disclosure, for bit b.sub.2, in the chosen subset of four symbols, all four symbols have bit b.sub.2=1 and no symbol with bit b.sub.2=0. Therefore, the minimum of all the four distances is the minimum distance metric for bit b.sub.2=1. Since there is no symbol with bit b.sub.2=0, the minimum distance metric for bit b.sub.2=0 cannot be updated. According to an aspect of the present disclosure, the comparator 728 may be disabled or unused when a subset of symbols, for example, the first subset, is selected such that the selected subset may not contain any symbol with bit b.sub.2=0. This is shown by a dashed line input to the comparator 728 in FIG. 9.

(39) According to an aspect of the present disclosure, for bit b.sub.3, in the chosen subset of four symbols, all four symbols have bit b.sub.3=1 and no symbol with bit b.sub.3=0. Therefore, the minimum of all the four distances is the minimum distance metric for bit b.sub.3=1. Since there is no symbol with bit b.sub.3=0, the minimum distance metric for bit b.sub.3=0 cannot be updated. According to an aspect of the present disclosure, the comparator 736 may be disabled or unused when a subset of symbols, for example, the first subset, is selected such that the selected may not contain any symbol with bit b.sub.3=0. This is shown by a dashed line input to the comparator 736 in FIG. 9.

(40) Note that FIG. 7 and FIG. 9 are identical except for the illustration of the metrics that may be updated and the metrics that may not be updated. Furthermore, the same exact hardware units may be used for the operations described in FIGS. 7 and 9.

(41) Note that for the first subset of four minimum distance metrics, the holding registers for each of the bits do not have any previous value with which to compare. According to an aspect of the present disclosure, at the beginning of processing for each stage of the tree search, the holding registers are initialized with a maximum value according to the bit-width of the register. This ensures that the first time the comparison is made with the holding register contents, the initial value is overwritten with the newly computed minimum distance metric.

(42) When the next subset of minimum distance metrics are computed, some of the holding registers may already have minimum distance metrics from a previous subset of four distance metrics. Therefore, the holding register may be updated only if one of the new subset of four distance metrics is lower than a previously stored minima. This process of determining minimum distances metrics for respective subsets of four symbols continues until all 16 distance metrics are processed. In case of 16-QAM constellation, this requires four steps, with four distances computed in each step. Note that as shown in FIG. 7, for the first subset of symbols, the minimum distance holding registers for bit b.sub.2=1 and bit b.sub.3=1 are not updated. These registers will retain the original initialized value. When the second subset of four distance metrics are computed, the minimum distance holding registers for bit b.sub.2=1 and bit b.sub.3=1 are updated. This method ensures that the global minimum for each of the bit value equal to zero and equal to one are available after all the symbols in the constellation are processed. The selection of the next subset of four symbols from the constellation is done in such a way that the same set of scenarios as described above for the first or second subset of symbols applies for the minimum distance metric computations. In this manner, the minimum distance metric for each bit being equal to 0 and being equal to 1 is obtained after four steps in case of 16-QAM constellation.

(43) In a tree search algorithm for the 16-QAM constellation embodiment, to reduce complexity, for subsequent stages of processing as described below, a subset of symbols comprising L symbols (LM), from the first stage of processing corresponding to L globally smallest values of distance metric D.sub.s1 may be considered, i.e., smallest distance metrics without considering whether a particular bit is equal to 0 or 1. To facilitate selection of the subset of L symbols, for each processing cycle of a subset of symbols, the subset of distance metrics computed may be input to the processing block 744 (see FIGS. 7 and 9), which may store the distance metrics for all the constellation points when distance metrics are generated, such as at each clock cycle, for a given transformed received signal. After the distance metrics for all the symbols in a constellation are generated and input to the processing block 744, a search may be performed and an output of L smallest distance metrics and the symbol indices respectively associated therewith may be generated. The processing block 744 may search for L smallest distance metrics on an incremental basis when a subset of distance metrics are input to the block, and may output the final L smallest distance metrics and the symbol indices respectively associated therewith after distance metrics for all constellation points for the given transformed received signal have been input.

(44) According to an aspect of the present disclosure, for the case of 64-QAM constellation, a similar procedure as that of 16-QAM may be followed. According to an aspect of the present disclosure, FIG. 10 shows the subset of four symbols chosen for computing distance metrics for the first step. According to an aspect of the present disclosure, FIG. 11 shows how the four distance metrics are used to compute the minimum distances for bits b.sub.0 through b.sub.5 being equal to 0 and being equal to 1. For the subset of four symbols illustrated in FIG. 10, it includes symbols with bit b.sub.0=0 and b.sub.0=1. Similarly, the subset includes symbols with bit b.sub.1=0 and b.sub.1=1. For the bits b.sub.2, b.sub.3, b.sub.4, and b.sub.5, the set of symbols is such that only the value of 0 is possible. Therefore, the minimum distances corresponding to bits b.sub.2, b.sub.3, b.sub.4, and b.sub.5 being equal to 1 may not be updated. According to an aspect of the present disclosure, similarly as described above for 16-QAM constellation, the comparators 1132, 1140, 1148 and 1156 may be disabled or unused when a subset of symbols is selected such that the selected subset may not contain any symbol with bit b.sub.2=1, b.sub.3=1, b.sub.4=1, and b.sub.5=1 respectively. This is illustrated in FIG. 11 by dashed input lines to the comparators 1132, 1140, 1148 and 1156 for the bits b.sub.2, b.sub.3, b.sub.4, and b.sub.5 being equal to 1. The rest of the processing remains similar to the case of 16-QAM illustrated in FIG. 7.

(45) According to an aspect of the present disclosure, FIG. 12 shows a different subset of four symbols chosen for computing distance metrics for the next step of 64-QAM constellation. FIG. 13 shows how the four distance metrics are used to compute the minima for bits b.sub.0 through b.sub.5 being equal to 0 and being equal to 1. For the subset of four symbols illustrated in FIG. 12, it includes symbols with bit b.sub.0=0 and b.sub.0=1. Similarly, it includes symbols with bit b.sub.1=0 and b.sub.1=1. For the bits b.sub.2, b.sub.3, b.sub.4, and b.sub.5, the set of symbols is such that only value of 1 is possible. Therefore, the minimum distances corresponding to bits b.sub.2, b.sub.3, b.sub.4, and b.sub.5 being equal to 0 may not be updated. According to an aspect of the present disclosure, the comparators 1128, 1136, 1144 and 1152 may be disabled or unused when a subset of symbols is selected such that the selected subset may not contain any symbol with bit b.sub.2=0, b.sub.3=0, b.sub.4=0, and b.sub.5=0 respectively. This is illustrated in FIG. 13 by dashed input lines to the comparators 1128, 1136, 1144 and 1152 for the bits b.sub.2, b.sub.3, b.sub.4, and b.sub.5 being equal to 0. The rest of the processing remains similar to the case of 16-QAM illustrated in FIG. 9.

(46) Note that FIG. 11 and FIG. 13 are identical except for the illustration of the metrics that may be updated and the metrics that may not be updated. The same exact hardware units may be used for the operations described in FIGS. 11 and 13. According to an aspect of the present disclosure, the same exact hardware may be used for QPSK, 16-QAM, and 64-QAM constellation with the selection of subsets of symbols according to the aspects of the present disclosure. In case the hardware illustrated in FIG. 11 or 13 is used for QPSK or 16-QAM constellations, some portion of the hardware may remain unused.

(47) These steps of computing four distance metrics and from these distance metrics computing the minimum distance for each bit being equal to 0 and being equal to 1, are repeated eight times to compute distance metrics for all 64 symbols in the 64-QAM constellation and the global minimum distance metrics for each bit being equal to 0 and being equal to 1.

(48) In a tree search algorithm for the 64-QAM constellation embodiment, to reduce complexity, for subsequent stages of processing, a subset of symbols comprising L symbols (LM), from the first stage of processing corresponding to L globally smallest values of distance metric D.sub.s1 may be considered, i.e., smallest distance metrics without considering whether a particular bit is equal to 0 or 1. To facilitate selection of the subset of L symbols, for each processing cycle of a subset of symbols, the subset of distance metrics computed may be input to the processing block 1160 (see FIGS. 11 and 13), which may store the distance metrics for all the constellation points when distance metrics are generated, such as for each clock cycle for a given transformed received signal. After the distance metrics for all the symbols in a constellation are generated and input to the processing block 1160, a search may be performed and an output of L smallest distance metrics and the symbol indices respectively associated therewith may be generated. The processing block 1160 may search for L smallest distance metrics on an incremental basis when a subset of distance metrics are input to it and may output the final L smallest distance metrics and the symbol indices respectively associated therewith after distance metrics for all constellation points for the given transformed received signal have been input.

(49) In the tree search algorithms, all the symbols in the constellation are used for distance computations in a first stage, such as described above for the 16- and 64-QAM in connection with the text accompanying the descriptions of FIGS. 7 and 9 and FIGS. 11 and 13, respectively. However, to reduce complexity, for subsequent stages of processing only a few, say L, of the symbols from the first stage of distance computation processing corresponding to L smallest values of distance metric D.sub.s1 may be considered. In case of two multiplexed data streams in 22 SM-MIMO with 64-QAM in both streams, for example, only the top eight symbols with the lowest distance metrics from the first stage of processing may be considered in conjunction with a second stage of distance computation processing. Therefore, instead of computing all 6464=4096 cumulative distance metrics, only 648=512 cumulative distance metrics may need to be computed. The L symbols from the first stage of processing to be used for the second stage processing may be determined by searching for the symbols corresponding to the smallest distance metric D.sub.s1 from the distance metrics for all the symbols of a given constellation. This search for the L symbols from the first stage with the smallest distance metric D.sub.s1 may be performed according to the method described in U.S. application Ser. No. 14/925,006, filed Oct. 28, 2015, incorporated by reference herein. The search for the L symbols from the first stage with the smallest distance metric D.sub.s1 may be performed in parallel to the search for the minimum distance metrics corresponding to bits associated with symbols being equal to zero or one. The same set of distance metrics DS.sub.a, DS.sub.b, DS.sub.c and DS.sub.d or DS.sub.e, DS.sub.f, DS.sub.g and DS.sub.h may be input to both the search units.

(50) For the second stage distance computations, corresponding to first row in EQ. (6), the L selected symbols from the first stage corresponding to s.sub.1 are substituted one at a time into the EQ. (6). The first row of EQ. (6) is then evaluated for all possible values of s.sub.0 from the constellation. The cumulative distance metric (D.sub.s1+D.sub.s0) is then used to determine the transmitted symbol sequence (s.sub.0, s.sub.1). The distance metric D.sub.s0 for the first row of EQ. (6) is given as follows:
D.sub.s0=|y.sub.0r.sub.0,0s.sub.0r.sub.0,1s.sub.1|.sup.2(8)

(51) In EQ. (8) the transformed received signal y.sub.0 and the element r.sub.0,1 of the matrix R are complex and in general can have any value within the specified bit width for a variable. The modulation symbol s.sub.0 is chosen from a fixed set of values forming the constellation. The term r.sub.0,0 may be real based on QR decomposition. For each symbol s.sub.1, i.e., (r.sub.0,1s.sub.1), and all possible values s.sub.0, distance metric D.sub.s0 may be computed. The term (r.sub.0,1s.sub.1) may be computed only L times. Each value of (r.sub.0,1s.sub.1) may be reused with all possible values of (r.sub.0,0s.sub.0).

(52) According to an aspect of the present disclosure, when the cumulative distance computation for the second stage is performed, the minimum cumulative distance metrics for each of the bits of the symbols from the second stage may be selected according to the same method as described for the first stage. However, the subset of symbols used from the first stage for cumulative distance metrics for the second stage, may not have all the bit positions with values equal to 0 and equal to 1. For example, if the L=8 symbols from the first stage that are used in the second stage for cumulative distance metrics computations are as illustrated in FIG. 14, there are no symbols with the bits b.sub.1=1, b.sub.3=1, and b.sub.5=1. When this scenario occurs, the minimum cumulative distance metrics for bits b.sub.1=1, b.sub.3=1, and b.sub.5=1 retain the initialized maximum value when the second stage computation is performed. When such a scenario arises, if the LLRs are computed with the initialized maximum value in the holding register, the LLRs may not be reliable and may lead to inferior FEC decoding performance.

(53) The LLR computation is performed after all the minimum distances are computed for all the symbol vectors. FIG. 15 illustrates all the available minimum distances corresponding to all 12 bits b.sub.0 to b.sub.11 being equal to 0 or being equal to 1. The LLRs are obtained by subtracting the minimum distance for a particular bit being equal to 1 from the minimum distance for the same bit being equal to 0.

(54) According to an aspect of the present disclosure, for those bits for which the minimum cumulative distance metrics are not available in second stage processing of a tree search method, the LLRs are computed using the minimum distance metrics selected during the first stage of the processing. Since the first stage of processing considers all the symbols of a constellation for distance metric computations, the minimum distance metrics for all bits being equal to zero or equal to one are always available. The LLRs generated using this method are more reliable and may lead to improved FEC decoding performance.

(55) As noted above, some of the minimum distances corresponding to some bits from the first stage being equal to 0 or being equal to 1 may not be available. For example, if the L=8 symbols selected from first stage are as per the case illustrated in FIG. 14, the minimum distance metrics for the bits b.sub.1=1, b.sub.3=1, and b.sub.5=1 identified by holding registers 1502, 1504, and 1506 respectively may not be updated at all and may have the highest value to which the holding register may have been initialized at the beginning of second stage minimum distance computation. As per the aspects of the present disclosure described, when such a scenario occurs, the minimum distance metrics for the respective bits with the respective value from the first stage minimum distance metrics are used. Specifically, for the example case illustrated in FIG. 14, the second stage cumulative minimum distance metrics in holding registers 1502, 1504, and 1506 may be replaced by the values in the holding registers 1508, 1510, and 1512 respectively.

(56) Although the present disclosure exemplifies use of the same constellation for the two symbols in an SM-MIMO system at the transmitter and the receiver, the two symbols in an SM-MIMO system may use different constellations. For example, in FIG. 2, the symbol s.sub.0 may be drawn from a 16-QAM constellation and the symbol s.sub.1 may be drawn from a 64-QAM constellation.

(57) In accordance with such aspects of the present disclosure, the method of soft bit computation in MIMO decoders may be applied to various wireless communication systems such as systems based on the 3rd Generation Partnership Project (3GPP) Long Term Evolution (LTE) and LTE-Advanced, an IEEE 802.16 wireless communication standard, an IEEE 802.11 wireless communication standard, or any other wireless communication system that uses spatial multiplexing.

(58) In accordance with such aspects of the present disclosure, the method of soft bit computation in MIMO decoders may be used is a client terminal or a base station of a wireless communication system. The method disclosed herein enables reduced complexity SM decoding with soft bit computation which in turn leads to reduced silicon area in a semiconductor implementation such as an Application Specific Integrated Circuit (ASIC). The reduced complexity and reduced area may lead to reduced power consumption. The generation of reliable soft bits leads to improved SM-MIMO decoding performance.

(59) By way of example only, the above described method may be implemented in a receiver, e.g., a user device such as a wireless mobile station (MS) 12 as shown in FIG. 1.

(60) As shown in FIG. 16, MS 100 may include an application processor subsystem 101, baseband subsystem 102 and a radio frequency (RF) subsystem 104 for use with a wireless communication network. A display/user interface 106 provides information to and receives input from the user. By way of example, the user interface may include one or more actuators, a speaker and a microphone. In some mobile devices, certain combination of the application processor subsystem 101, the baseband subsystem 102 and the RF subsystem 104 are all integrated as one integrated chip.

(61) The application processor subsystem 101 as shown in FIG. 17 may include a controller 108 such as a microcontroller, another processor or other circuitry. The baseband subsystem 102 as shown in FIG. 18 may include a controller 118 such as a microcontroller or other processor. The RF subsystem 104 as shown in FIG. 19 may include a controller 128 such as a microcontroller, another processor or other circuitry. The controller 108 desirably handles overall operation of the MS 100. This may be done by any combination of hardware, software and firmware running on the controller 108. Such combination of hardware, software and firmware may embody any methods in accordance with the aspects of the present disclosure.

(62) In FIG. 18 the peripherals 114 such as a full or partial keyboard, video or still image display, audio interface, etc., may be employed and managed through the controller 108.

(63) Aspects of the present disclosure may be implemented in firmware of the controller 108 of the application processor and/or the controller 118 of the baseband subsystem as shown in FIG. 11. In another alternative, aspects of the present disclosure may also be implemented as a combination of firmware and hardware of the application processor subsystem 101 and/or the baseband subsystem 102. For instance, signal processing functionality of any or all of the FIG. 13 may be implemented in firmware and/or software, which is executed by the system hardware. It may be part of the baseband subsystem, the receiver subsystem or be associated with both subsystems. In one example, the controller 118 and/or the signal processor 110 may include or control the protocol entity circuitry. The software may reside in internal or external memory and any data may be stored in such memory. The hardware may be an application specific integrated circuit (ASIC), field programmable gate array (FPGA), discrete logic components or any combination of such devices. The terms controller and processor are used interchangeably herein.

(64) The consumer electronics devices that may use aspects of the disclosure may include smartphones, tablets, laptops, gaming consoles, cameras, video camcorders, TV, car entertainment systems, etc.

(65) Although aspects of the disclosure herein have been described with reference to particular embodiments, it is to be understood that these embodiments are merely illustrative of the principles and applications of the aspects of the present disclosure. It is therefore to be understood that numerous modifications may be made to the illustrative embodiments and that other arrangements may be devised without departing from the spirit and scope of the aspects of the present disclosure as defined by the appended claims. Aspects of each embodiment may be employed in the other embodiments described herein.