High performance digital signal processing in software radios

• US 8,627,189 B2
• Filed: 12/03/2009
• Issued: 01/07/2014
• Est. Priority Date: 12/03/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Tan, Kun, Zhang, Jiansong, Zhang, Yongguang, Liu, He
• Primary Examiner(s): MCCARTHY, CHRISTOPHER S
• Application Number:
  US12/630,774
• Publication Number:
  US 20110138259A1
• Time in Patent Office: 1,496 Days
• Field of Search: None
• US Class Current: 714/795
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/41 using the Viterbi algorithm or Viterbi processors
• CPC Class Codes: H03M 13/4169 using traceback H03M13/4192 takes precedence
• CPC Class Codes: H03M 13/6527 IEEE 802.11 [WLAN]
• CPC Class Codes: H04B 1/0039 using DSP [Digital Signal Processor] quadrature modulation and demodulation
• CPC Class Codes: H04L 1/0043 Realisations of complexity reduction techniques, e.g. use of look-up tables
• CPC Class Codes: H04L 1/0052 Realisations of complexity reduction techniques, e.g. pipelining or use of look-up tables
• CPC Class Codes: H04L 1/0054 Maximum-likelihood or sequential decoding, e.g. Viterbi, Fano, ZJ algorithms
• CPC Class Codes: H04L 1/0066 Parallel concatenated codes
• CPC Class Codes: H04L 1/1607 Details of the supervisory signal
• CPC Class Codes: H04L 1/1829 Arrangements specially adapted for the receiver end

Abstract

An extensive use of look-up table (LUT) and single instruction multiple data (SIMD) in different algorithms in a software-defined radio (SDR) system is described. In particular, the LUT is used during spreading modulation, mapping and spreading, scrambling, de-scrambling, soft demapping, and the like. The SIMD is executed by a multi-core processor during implementation of a “min” operation to find an optimal path in a Trellis diagram for a Viterbi decoder.

Claims

1. A method implemented on a computing device—

in a software defined radio (SDR) system—

by a processor configured to execute instructions that, when executed by the processor, direct the computing to device to perform acts comprising;

receiving an array of data bits;

loading a set of bits of the array of data bits;

performing a “

min”

operation to find an optimal path in a Trellis diagram of a Viterbi decoder, wherein the “

min”

operation includes;

starting from a known state in the Trellis diagram; and

updating a data structure for each expansion in the Trellis diagram relative to the known state, the data structure containing a path metric embedded in most significant bits to define a minimal value for each state in the expansion, and a path index embedded in least significant bits to define link information for the minimal value; and

tracing back the minimal values relative to an end state of the Trellis diagram to obtain the optimal path.

2. The method of claim 1, wherein the array of data bits includes one or more soft values from a soft demapper in the SDR system.

3. The method of claim 2, wherein the soft demapper further comprises:

receiving a sequence of data;

quantizing the sequence of data into in-phase (I) component and quadrature phase (Q) component, wherein the I component and the Q component are combined to form an I-Q pair input;

using the I-Q pair input in a look-up table (LUT) that provides the one or more soft values for the I component and the Q component, wherein the LUT is shared and used by the I component and the Q component, which are computed separately; and

outputting the one or more soft values for the I-Q pair input.

4. The method of claim 1, wherein the SDR system further includes a finite impulse response (FIR) filter, which comprises:

receiving an array of input samples, wherein the array of input samples includes an in-phase (I) sample and a quadrature phase (Q) sample, wherein the coefficient arrays include a first coefficient array for the I sample and a second coefficient array for the Q sample;

loading the I sample and the Q sample;

multiplying the I sample with the first coefficient array to provide a first product, multiplying the Q sample with the second coefficient array to provide a second product, wherein the first product and the second product are stored in a temporal accumulative sum, wherein the temporal accumulative sum includes a summation of the first product for the I sample and summation of the second product for the Q sample; and

outputting the temporal accumulative sum for the I sample and the Q sample; and

wherein the FIR filter includes a memory layout that contains;

one or more rows forming a packed-vector of “

m”

components for single input multiple data (SIMD) operations;

a coefficient vector that is replicated in each of “

m”

columns in a zigzag layout; and

an “

n”

temporary variables containing accumulated sum for each FIR filter tap for the I sample and the Q sample;

wherein a total number of the one or more rows is equivalent to a value of—

“

n”

plus “

m”

minus one—

the “

m” and

“

n”

are integers, and wherein the SIMD operations are used to accelerate processing in the FIR filter.

5. The method of claim 1, wherein the array of data bits are encoded using at least one of convolutional encoder or turbo encoder, the convolutional encoder and the turbo encoder each uses a look-up table (LUT) to reduce computational requirements for online processing and to speed up overall processing time.

6. The method of claim 5, wherein the LUT includes an input index that combines input bits with present bit-states in the convolutional encoder or the turbo encoder.

7. The method of claim 5, wherein the LUT includes an output that contains new bit-states and output bits, wherein the new bit-states are used to update the present bit-states.

8. The method of claim 1, wherein the “

min”

operation is implemented by at least one or more multi-core processors that execute single input multiple data (SIMD) instructions.

9. The method of claim 1, wherein the data structure is used during the trace back by tracing stored path index for each expansion.

10. The method of claim 1, wherein the embedding of the path index in the least significant bits of the data structure does not affect an output of the “

min”

operation.

11. A computer-readable storage device having computer-readable instructions thereon which, when executed by a computer in a software defined radio (SDR) system, implement a method comprising:

receiving an array of data bits;

loading a byte of the array of data bits;

performing an algorithm to find an optimal path in a Trellis diagram, wherein the algorithm includes;

starting from a known state in the Trellis diagram; and

updating a data structure for each expansion in the Trellis diagram relative to the known state, the data structure containing a path metric embedded in most significant bits to define a minimal value for each state in the expansion, and a path index embedded in least significant bits to define link information for the minimal value; and

tracing back the minimal values relative to an end state of the Trellis diagram, wherein the tracing back uses single input multiple data (SIMD) instructions to accelerate processing.

12. The computer-readable storage device of claim 11, wherein the array of data bits includes data bits that were transmitted using spreading modulation.

13. The computer-readable storage device of claim 12, wherein the spreading modulation uses a look-up table (LUT) as an optimization method, the LUT is used to map information bits directly to spread signal sequence.

14. The computer-readable storage device of claim 11, wherein the Trellis diagram is used in different algorithms employed in the SDR system.

15. The computer-readable storage device of claim 11, wherein the SDR system further comprises a finite impulse response (FIR) filter, which includes a memory layout that contains:

one or more rows forming a packed-vector of “

m”

components for single input multiple data (SIMD) operations;

a coefficient vector that is replicated in each of “

m”

columns in a zigzag layout; and

an “

n”

temporary variables containing accumulated sum for each FIR filter tap for in-phase (I) sample and quadrature phase (Q) sample;

wherein a total number for the one or more rows is equivalent to a value of—

“

n”

plus “

m”

minus one—

the “

m” and

“

n”

are integers, and wherein the SIMD operations are used to accelerate processing in the FIR filter.

16. The computer-readable storage device of claim 11, wherein SDR system further comprises at least one of:

a scrambler or a de-scrambler that use a look-up table (LUT) as an optimization method, wherein the LUT is constructed by combining input bits with present bit-states as an input index; and

an output for the LUT includes output bits and new bit-states.

17. The computer-readable storage device of claim 16, wherein the present bit-states are updated using the new-bit states.

18. A software-defined radio (SDR) stack comprising:

a memory; and

a multi-core processor coupled to the memory, which is configured to;

receive an array of data bits comprising one or more soft values from a soft-demapper that uses a look-up table (LUT) as an optimization method;

load a byte of the array of data bits;

perform an algorithm to find an optimal path in a Trellis diagram, wherein the algorithm includes;

starting from a known state in the Trellis diagram; and

updating a data structure for each expansion in the Trellis diagram relative to the known state, the data structure containing a path metric and a path index; and

trace back the optimal path relative to an end state of the Trellis diagram.

19. The SDR stack of claim 18, wherein the LUT is shared and used by in-phase (I) component and quadrature phase (Q) component, which are computed separately.

20. The SDR stack of claim 19, wherein the LUT includes an input of I-Q pair that is derived from a quantized received symbol, the quantized received symbol includes the I component and the Q component that are combined to provide the I-Q pair.