Efficient decoding of spatially-multiplexed signals

A method for communication, comprising:

• receiving a spatially-multiplexed signal using multiple receivers to produce multiple respective received signals, the spatially-multiplexed signal comprising multiple simultaneously-transmitted symbols, which are selected from respective sets of constellation symbols, each constellation symbol representing a respective set of values of a group of data bits;
• iteratively traversing combinations of the constellation symbols, wherein each combination comprises one constellation symbol from each of the sets of the constellation symbols and represents N data bits, and wherein each combination is traversed at most once, and searching the traversed combinations for a combination that matches the received signals;
• during traversal of the combinations of the constellation symbols, accumulating at least 2N measures of likelihood regarding the values of the data bits represented by each traversed combination;
• processing the accumulated measures of likelihood, which were computed by traversing each combination at most once, to produce soft bit metrics;
• and
• reconstructing the values of the data bits carried by the multiple transmitted symbols responsively to the soft bit metrics,
• wherein traversing the combinations comprises defining an order for traversing a first set of the constellation symbols starting at an initial constellation symbol, selecting a sequence of the constellation symbols from the first set in accordance with the order, and deriving the constellation symbols in the other sets of the constellation symbols from the selected constellation symbols of the first set to produce the combinations,
• wherein receiving the spatially-multiplexed signal comprises expressing the received signals in terms of a channel matrix operating on the simultaneously-transmitted symbols, and wherein deriving the constellation symbols in the other sets comprises decomposing the channel matrix by a QR decomposition process to produce a decomposed matrix, and deriving the constellation symbols in the other sets using the decomposed matrix, and
• wherein decomposing the channel matrix comprises extending the channel matrix with elements indicative of noise levels in the received signals, and decomposing the extended channel matrix.

A communication apparatus, comprising:

• multiple receivers, which are coupled to receive a spatially-multiplexed signal to produce multiple respective received signals, the spatially-multiplexed signal comprising multiple simultaneously-transmitted symbols, which are selected from respective sets of constellation symbols, each constellation symbol representing a respective set of values of a group of data bits;
• and
• a decoder, which is coupled to iteratively traverse combinations of the constellation symbols, wherein each combination comprises one constellation symbol from each of the sets of the constellation symbols and represents N data bits, and wherein each combination is traversed at most once, to search the traversed combinations for a combination that matches the received signals, to accumulate, during traversal of the combinations of the constellation symbols, at least 2N measures of likelihood regarding the values of the data bits represented by each traversed combination, to process the accumulated measures of likelihood, which were computed by traversing each combination at most once, so as to produce soft bit metrics, and to output the soft metrics so as to reconstruct the values of the data bits carried by the multiple transmitted symbols,
• wherein the decoder is coupled to terminate traversal of the combinations responsively to meeting a predefined stopping condition, and
• wherein the decoder is coupled to calculate for each traversed combination a first solution metric that is indicative of a distance between the traversed combination and the received signals and a second solution metric that is indicative of a distance between one of the constellation symbols in the traversed combination and one of the received signals, and to terminate the traversal when the second solution metric exceeds a best achieved value of the first solution metric by a predetermined threshold.

A communication apparatus, comprising:

• multiple receivers, which are coupled to receive a spatially-multiplexed signal to produce multiple respective received signals, the spatially-multiplexed signal comprising multiple simultaneously-transmitted symbols, which are selected from respective sets of constellation symbols, each constellation symbol representing a respective set of values of a group of data bits;
• and
• a decoder, which is coupled to iteratively traverse combinations of the constellation symbols, wherein each combination comprises one constellation symbol from each of the sets of the constellation symbols and represents N data bits, and wherein each combination is traversed at most once, to search the traversed combinations for a combination that matches the received signals, to accumulate, during traversal of the combinations of the constellation symbols, at least 2N measures of likelihood regarding the values of the data bits represented by each traversed combination, to process the accumulated measures of likelihood, which were computed by traversing each combination at most once, so as to produce soft bit metrics, and to output the soft metrics so as to reconstruct the values of the data bits carried by the multiple transmitted symbols,
• wherein the decoder is coupled to define an order for traversing a first set of the constellation symbols starting at an initial constellation symbol, to select a sequence of the constellation symbols from the first set in accordance with the order, and to derive the constellation symbols in the other sets of the constellation symbols from the selected constellation symbols of the first set to produce the combinations,
• wherein the decoder is coupled to express the received signals in terms of a channel matrix operating on the simultaneously-transmitted symbols, to decompose the channel matrix by a QR decomposition process to produce a decomposed matrix, and to derive the constellation symbols in the other sets using the decomposed matrix, and
• wherein the decoder is coupled to extend the channel matrix with elements indicative of noise levels in the received signals, and to decompose the extended channel matrix.