Linear transformation circuits

• US 7,133,463 B1
• Filed: 08/25/2005
• Issued: 11/07/2006
• Est. Priority Date: 08/25/2005
• Status: Expired due to Fees

• Current Assignee: Rambus Inc., Board of Trustees of the Leland Stanford Junior University (Stanford University)
• Original Assignee: Rambus Inc.
• Inventors: Alon, Elad, Horowitz, Mark A., Stojanovic, Vladimir, Amirkhany, Amir, Zerbe, Jared LeVan
• Primary Examiner(s): Barnie, Rexford
• Assistant Examiner(s): NGUYEN, KHAI M
• Application Number:
  US11/213,352
• Time in Patent Office: 439 Days
• Field of Search: 370/210, 370/366, 370/419, 370/535, 375/261, 375/295, 375/298
• US Class Current: 375/295
• CPC Class Codes: G06F 17/141 Discrete Fourier transforms
• CPC Class Codes: G06J 1/005 for correlation; for convolution; for Z or Fourier Transform

Abstract

A transform circuit includes a first circuit and a second circuit. The first circuit and the second circuit implement first and second mappings that together generate a pre-defined transform of N digital data symbols. The first circuit maps a set of N digital data symbols from N parallel data streams to N analog data symbols by generating N sets of weighted sums of the N digital data symbols. Each respective weighted sum is defined by a respective set of pre-determined weighting values in a first matrix. The second circuit maps the N analog data symbols to a sequence of N output signals over N time intervals. Each of the N output signals corresponds to a respective weighted sum of the N analog data symbols. Each respective weighted sum is defined by a respective set of pre-determined weighting values in a second matrix.

Claims

1. A transform circuit, comprising:

a first circuit to map a set of N digital data symbols from N parallel data streams to N analog data symbols by generating N sets of first weighted sums of the N digital data symbols, each respective first weighted sum defined by a respective set of pre-determined first weighting values in a first matrix; and

a second circuit to map the N analog data symbols to a sequence of N output signals over N time intervals, each of the N output signals corresponding to a respective second weighted sum of the N analog data symbols, each respective second weighted sum defined by a respective set of pre-determined second weighting values in a second matrix;

wherein the first circuit and the second circuit together generate a pre-defined transform of the N digital data symbols.

2. The transform circuit of claim 1, wherein the pre-defined transform is an inverse discrete Fourier transform (IDFT).

3. The transform circuit of claim 1, wherein N is an integer greater than 3.

4. The transform circuit of claim 1, including a serial to parallel converter to process a first data stream to produce the N parallel data streams.

5. The transform circuit of claim 1, wherein the second circuit includes:

multiplier circuitry for multiplying the N analog data symbols by the second matrix of pre-determined second weighting values, including circuitry for multiplying the N analog data symbols by successive respective subsets of the pre-determined second weighting values during N successive time intervals to produce N successive sets of multiplication results; and

a summation circuit for combining each successive set of multiplication results from the second circuit to produce a respective output signal during each of the N successive time intervals.

6. The transform circuit of claim 1, wherein a summation of each row in the first matrix equals a first value and a summation of each column in the first matrix equals the first value.

7. The transform circuit of claim 1, wherein the first circuit includes first and second parallel sub-circuits, each sub-circuit including a plurality of fixed gain drivers and connections for coupling a subset of the N digital data symbols to a respective set of the fixed gain drivers thereby multiplying the subset of the N digital data symbols by a corresponding subset of the pre-determined first weighting values in the first matrix.

8. The transform circuit of claim 1, further comprising a finite state machine, wherein the second circuit includes a plurality of fixed gain drivers and a connection matrix controlled by the finite state machine for multiplying the N analog data symbols by respective pre-determined second weighting values associated with the fixed gain drivers.

9. The transform circuit of claim 1, further comprising a finite state machine, wherein the second circuit includes N programmable gain drivers and the finite state machine provides respective pre-determined second weighting values for multiplying the N analog data symbols.

10. The transform circuit of claim 1, further comprising a finite state machine, wherein the first circuit includes a plurality of fixed gain drivers and a connection matrix controlled by the finite state machine for multiplying the N digital data symbols by respective pre-determined first weighting values associated with the fixed gain drivers.

11. The transform circuit of claim 1, further comprising a finite state machine, wherein the first circuit includes N programmable gain drivers and the finite state machine provides respective pre-determined first weighting values for multiplying the N digital data symbols.

12. The transform circuit of claim 1, wherein the digital data symbols are complex, having an in-phase component and an out-of-phase component, and wherein the first circuit uses multiplication in a complex domain to generate first weighted sums of combinations of in-phase components and out-of-phase components of the N digital data symbols and the second circuit uses multiplication in a complex domain to generate second weighted sums of combinations of in-phase components and out-of-phase components of the N analog data symbols.

13. The transform circuit of claim 1, wherein the second matrix includes a plurality of complex values, each having a component, wherein the component is selected from the set consisting of a first set of two distinct values of equal magnitude and a second set of two distinct values of equal magnitude.

14. The transform circuit of claim 1, wherein the second circuit includes a plurality of multipliers, at least one of which modulates the N analog data symbols using a carrier signal having a respective carrier signal frequency.

15. A transform mechanism, comprising:

a first means for mapping a set of N digital data symbols from N parallel data streams to N analog data symbols by generating N sets of first weighted sums of the N digital data symbols, each respective first weighted sum defined by a respective set of pre-determined first weighting values in a first matrix; and

a second means for mapping the N analog data symbols to a sequence of N output signals over N time intervals, each of the N output signals corresponding to a respective second weighted sum of the N analog data symbols, each respective second weighted sum defined by a respective set of pre-determined second weighting values in a second matrix,

wherein the first means and the second means together generate a pre-defined transform of the N digital data symbols.

16. A method of transforming data, comprising:

mapping a set of N digital data symbols from N parallel data streams to N analog data symbols by generating N sets of first weighted sums of the N digital data symbols, each respective first weighted sum defined by a respective set of pre-determined first weighting values in a first matrix; and

mapping the N analog data symbols to a sequence of N output signals over N time intervals, each of the N output signals corresponding to a respective second weighted sum of the N analog data symbols, each respective second weighted sum defined by a respective set of pre-determined second weighting values in a second matrix,

wherein the mappings together generate a pre-defined transform of the N digital data symbols.

17. A transform circuit, comprising:

a first circuit to map N analog signals to N sequences of N analog data symbols over N time intervals, each of the N sequences of N analog data symbols corresponding to a respective first weighted sum of a respective set of analog signals, each respective first weighted sum defined by a respective set of pre-determined first weighting values in a first matrix;

an integration circuit to integrate each of the N sequences of N analog data symbols for N time intervals producing N integrated sequences; and

a second circuit to map the N integrated sequences to N digital data symbols by generating a set of second weighted sums of the N integrated sequences, each respective second weighted sum defined by a respective set of pre-determined second weighting values in a second matrix,

wherein the first circuit and the second circuit together generate a pre-defined transform of the N analog signals.

18. A transform mechanism, comprising:

a first means for mapping N analog signals to N sequences of N analog data symbols over N time intervals, each of the N sequences of N analog data symbols corresponding to a respective first weighted sum of a respective set of analog signals, each respective first weighted sum defined by a respective set of pre-determined first weighting values in a first matrix;

an integration means for integrating each of the N sequences of N analog data symbols for N time intervals producing N integrated sequences; and

a second means for mapping the N integrated sequences to N digital data symbols by generating a set of second weighted sums of the N integrated sequences, each respective second weighted sum defined by a respective set of pre-determined second weighting values in a second matrix,

wherein the first means and the second means together generate a pre-defined transform of the N analog signals.

19. A method of transforming data, comprising:

mapping N analog signals to N sequences of N analog data symbols over N time intervals, each of the N sequences of N analog data symbols corresponding to a respective first weighted sum of a respective set of analog signals, each respective first weighted sum defined by a respective set of pre-determined first weighting values in a first matrix;

integrating each of the N sequences of N analog data symbols for N time intervals producing N integrated sequences; and

mapping the N integrated sequences to N digital data symbols by generating a set of second weighted sums of the N integrated sequences, each respective second weighted sum defined by a respective set of pre-determined second weighting values in a second matrix;

wherein the mappings together generate a pre-defined transform of the N analog signals.

20. A computer readable medium containing data that describes a transform circuit, wherein the transform circuit comprises:

a first circuit to map a set of N digital data symbols from N parallel data streams to N analog data symbols by generating N sets of first weighted sums of the N digital data symbols, each respective first weighted sum defined by a respective set of pre-determined first weighting values in a first matrix; and

a second circuit to map the N analog data symbols to a sequence of N output signals over N time intervals, each of the N output signals corresponding to a respective second weighted sum of the N analog data symbols, each respective second weighted sum defined by a respective set of pre-determined second weighting values in a second matrix,

wherein the first circuit and the second together generate a pre-defined transform of the N digital data symbols.

21. A computer readable medium containing data that describes a transform circuit, wherein the transform circuit comprises:

a first circuit to map N analog signals to N sequences of N analog data symbols over N time intervals, each of the N sequences of N analog data symbols corresponding to a respective first weighted sum of a respective set of analog signals, each respective first weighted sum defined by a respective set of pre-determined first weighting values in a first matrix;

an integration circuit to integrate each of the N sequences of N analog data symbols for N time intervals producing N integrated sequences; and

a second circuit to map the N integrated sequences to N digital data symbols by generating a set of second weighted sums of the N integrated sequences, each respective second weighted sum defined by a respective set of pre-determined second weighting values in a second matrix,

wherein the transform circuit generates a pre-defined transform of the N analog signals.