Signal decoding methods and apparatus

• US 20050094742A1
• Filed: 09/14/2004
• Published: 05/05/2005
• Est. Priority Date: 10/03/2003
• Status: Active Grant

• Current Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation)
• Inventors: Yee, Mong Suan
• Granted Patent: US 7,424,063 B2
• Time in Patent Office: Days
• US Class Current: 375/267
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H04L 1/0048 in conjunction with detection of multiuser or interfering signals, e.g. iteration between CDMA or MIMO detector and FEC decoder for spatial equalizer H04L25/03286
• CPC Class Codes: H04L 1/005 Iterative decoding, including iteration between signal detection and decoding operation
• CPC Class Codes: H04L 1/04 using frequency diversity
• CPC Class Codes: H04L 1/0631 Receiver arrangements
• CPC Class Codes: H04L 2025/0342 QAM
• CPC Class Codes: H04L 2025/03426 transmission using multiple-input and multiple-output channels
• CPC Class Codes: H04L 25/03242 Methods involving sphere decoding
• CPC Class Codes: H04L 25/067 providing soft decisions, i.e. decisions together with an estimate of reliability H04L25/068 and H04L25/069 take precedence; sequence estimation techniques H04L25/03178
• CPC Class Codes: H04L 27/38 Demodulator circuits; Receiver circuits

Abstract

This invention is generally concerned with methods, apparatus and processor control code for decoding signals, in particular by means of sphere decoding. A method of decoding a transmitted signal encoded as a string of symbols and received over a channel as a received signal, each transmitted symbol having one of a plurality of values, the method comprising: searching for one or more candidate strings of symbols, a candidate string of symbols comprising a string of candidate symbols, by searching for candidate symbols of said string within a region of a multi-dimensional lattice determined by said channel response, said lattice having one dimension associated with each of said symbols of said string, said region being defined by distance from said received signal; and decoding a said string of symbols for said received signal by selecting one or more of said candidate strings of symbols; wherein said searching for candidate symbols comprises selecting candidate values for said transmitted symbols and testing whether a part of said lattice defined by a selected said candidate is within a bounding distance from said received signal; and wherein said searching is stopped after a limiting number of candidate symbol tests

Claims

1. A method of decoding a transmitted signal encoded as a string of symbols and received over a channel as a received signal, each transmitted symbol having one of a plurality of values, the method comprising:

searching for one or more candidate strings of symbols, a candidate string of symbols comprising a string of candidate symbols, by searching for candidate symbols of said string within a region of a multi-dimensional lattice determined by said channel response, said lattice having one dimension associated with each of said symbols of said string, said region being defined by distance from said received signal; and

decoding a said string of symbols for said received signal by selecting one or more of said candidate strings of symbols;

wherein said searching for candidate symbols comprises selecting candidate values for said transmitted symbols and testing whether a part of said lattice defined by a selected said candidate is within a bounding distance from said received signal; and

wherein said searching is stopped after a limiting number of candidate symbol tests.

2. A method as claimed in claim 1 wherein a said candidate symbol test comprises a test to determine which of three categories said candidate symbol belongs to, a first category wherein said part of said lattice defined by symbol is inside said bounding distance, a second category wherein said part of said lattice defined by symbol is outside said bounding distance, and a third category wherein said symbol comprises a last symbol of an estimated said string.

3. A method as claimed in claim 1 wherein said decoding further comprises providing a linear estimate of said transmitted string of symbols when said searching fails to locate a said candidate string of symbols.

4. A method as claimed in claim 3 wherein said linear estimate comprises a zero-forcing estimate.

5. A method as claimed in claim 3 wherein a said symbol of said string comprises one or more bits, and wherein said decoding provides a soft output comprising a likelihood value for each bit of each symbol of said string, the method further comprising deriving said bit likelihood values from said linear estimate.

6. A method as claimed in claim 1 wherein said decoding provides a soft output determined responsive to distance metrics for selected ones of said candidate strings of symbols, a said distance metric being dependent upon a distance of a said candidate string of symbols from said received signal.

7. A method as claimed in claim 6 wherein said soft output is determined responsive to distance metrics for all said candidate strings of symbols found by said searching.

8. A method as claimed in claim 1 wherein each symbol has one or more bits, whereby said string of symbols defines a string of bits, and wherein said decoding further comprises providing a probability value for each bit of said string of bits.

9. A method as claimed in claim 8 wherein a probability value for a said bit is determined using a first set of symbols of said one or more candidate strings of symbols in which the bit has a first logic value and a second set of symbols of said one or more candidate strings of symbols in which the bit has a second logic value different to said first logic value, by taking a ratio of first and second likelihood values determined using said first and second sets of symbols, and further comprising providing a default probability value for a said bit when one of said first and second sets is empty.

10. A method as claimed in claim 1 wherein said searching for candidate symbols proceeds in order of increasing distance from said initial estimate.

11. A method as claimed in claim 1 wherein said string of symbols is transmitted over a MIMO (multiple-input multiple-output) channel using a plurality of transmit antennas, and wherein said received signal is received by a plurality of receive antennas.

12. A method as claimed in claim 1 wherein said signal is encoded using a space-time block code.

13. Processor control code to, when running, implement the method of any one of claims 1 to 12.

14. A carrier carrying the processor control code of claim 13.

15. A decoder for decoding a transmitted signal encoded as a string of symbols and received over a channel as a received signal, each transmitted symbol having one of a plurality of values, the decoder comprising:

means for searching for one or more candidate strings of symbols, a candidate string of symbols comprising a string of candidate symbols, by searching for candidate symbols of said string within a region of a multi-dimensional lattice determined by said channel response, said lattice having one dimension associated with each of said symbols of said string, said region being defined by distance from said received signal; and

means for decoding a said string of symbols for said received signal by selecting one or more of said candidate strings of symbols;

wherein said means for searching for candidate symbols is configured to select candidate values for said transmitted symbols and to test whether a part of said lattice defined by a selected said candidate is within a bounding distance from said received signal; and

wherein said searching is stopped after a limiting number of candidate symbol tests.

16. A receiver including the decoder of claim 15.

17. A decoder for decoding a received signal comprising a string of symbols transmitted over a channel, the decoder comprising:

a sphere decoder to search for candidate transmitted symbol strings within a radius of said received signal by determining distances from said received signal in received signal space of candidate symbols for said string, and to provide a decoded data output; and

a sphere decoder controller to count said distance determinations and to control said sphere decoder to stop searching responsive to said count.

18. A decoder as claimed in claim 17 wherein said channel is a MIMO channel.