# US 2013/0159368 A1 · Method and Apparatus for Calculating an N-Point Discrete Fourier Transform > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2013/0159368 A1 - Document ID: US20130159368A1 - Status: Published application - Kind: A1 - Application number: 13/767,894 - Filed: 2013-02-15 - Published: 2013-06-20 - Earliest claimed: 2008-12-18 - Assignees: LSI Corporation - Inventors: David Noeldner - Web page: https://patentgrep.com/patent/US20130159368A1 ## CPC - G06F 17/14: Fourier, Walsh or analogous domain transformations {, e.g. Laplace, Hilbert, Karhunen-Loeve, transforms (for correlation function computation G06F17/156; spectrum analysers G01R23/16)} - G06F 17/141: {Discrete Fourier transforms} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Described embodiments provide an apparatus for calculating an N-point discrete Fourier transform of an input signal having multiple sample values. The apparatus includes at least one input configured to receive the sample values and a counter to count sample periods. Also included are at least two parallel multipliers to multiply each sample value, with each of the multipliers having a corresponding multiplication factor. There is at least one multiplexer to select one of the at least two parallel multipliers. An adder sums the scaled sample values and an accumulator accumulates the summed sample values. N is an integer and the at least two parallel multipliers are selectable based upon the value of N and the value of the sample period count. ## Claims ### Claim at position 1 1-11. (canceled) ### Claim 12 An apparatus for calculating an N-point discrete Fourier transform having first input configured to receive an even quadrature sample value and an even Phase sample value in a sample period and a second input configured to receive an odd quadrature sample value and an odd phase sample value in a sample period, comprising: a) a counter to count the sample periods; b) an even sample value scaling circuit having a selectable even scaling factor; c) an odd sample value sealing circuit having a selectable odd scaling factor; d) an adder to sum the sealed even and odd quadrature sample values; e) an adder to sum the scaled even and odd phase sample values; f) an accumulator to accumulate the summed even and odd quadrature sample values; and g) an accumulator to accumulate the summed even and odd phase sample values; wherein N is selectable and is either 3 or 4, the even and odd scaling factors are selectable based upon the value of N and the value of the sample period count, and wherein when N is set to 3, the counter counts 3 sample periods, and wherein when N is set to 4, the counter counts 2 sample periods. ### Claim 13 (depends on 12) The apparatus of claim 12, wherein the even sample value scaling circuit further comprises: a) a first parallel multiplier having a multiplication factor equal to −1; b) a second parallel multiplier having a multiplication factor equal to 2; c) a parallel path including a multiplier having a multiplication factor equal to 2 in series with the first parallel multiplier to provide a third parallel multiplier having a multiplication factor equal to −2; d) zero input to provide a fourth parallel multiplier having a multiplication factor equal to 0; e) at least one multiplexer to select one of the parallel multipliers; and f) at least one series multiplier having a multiplication factor equal to 3.75, wherein the setting of the at least one multiplexer determines the even scaling factor for the sample value. ### Claim 14 (depends on 13) The apparatus of claim 13, wherein, when N is set to 3, in a first sample period the at least one multiplexer is configured to select the even scaling factor of 2 for the quadrature sample and of 0 for the phase sample; in a second sample period, the at least one multiplexer is configured to select the even scaling factor of −1 for the quadrature sample and of −7 for the phase sample; in a third sample period, the at least one multiplexer is configured to select the even scaling factor of −1 for the quadrature sample and of 7 for the phase sample. ### Claim 15 (depends on 13) The apparatus of claim 13, wherein, when N is set to 4, for the even quadrature and phase samples, in a first sample period the at least one multiplexer is configured to select the even scaling factor of 2 for the quadrature sample and of 0 for the phase sample; in a second sample period, the at least one multiplexer is configured to select the even scaling factor of −2 for the quadrature sample and of 0 for the phase sample. ### Claim 16 (depends on 12) The apparatus of claim 12, wherein the odd sample value scaling circuit further comprises: a) a first parallel multiplier having a multiplication factor equal to −1; b) a second parallel multiplier having a multiplication factor equal to 2; c) a parallel path including a multiplier having a multiplication factor equal to 2 in series with the first parallel multiplier to provide a third parallel multiplier having a multiplication factor equal to −2; d) a zero input to provide a fourth parallel multiplier having a multiplication factor equal to 0; e) at least one multiplexer to select one of the parallel multipliers; and f) at least one multiplexer to select a series multiplier having a multiplication factor equal to 3.75, wherein the setting of the multiplexers determines the odd scaling factor for the sample value. ### Claim 17 (depends on 16) The apparatus of claim 16, wherein, when N is set to 3, for the odd quadrature and phase samples, in a first sample period the at least one multiplexer is configured to select the odd scaling factor of −1 for the quadrature sample and of 7 for the phase sample; in a second sample period, the at least one multiplexer is configured to select the odd scaling factor of 2 for the quadrature sample and of 0 for the phase sample; in a third sample period, the at least one multiplexer is configured to select the odd scaling factor of −1 for the quadrature sample and of −7 for the phase sample. ### Claim 18 (depends on 16) The apparatus of claim 16, wherein, when N is set to 4, for the odd quadrature and phase samples, in a first sample period the at least one multiplexer is configured to select the odd scaling factor of 0 for the quadrature sample and of 2 for the phase sample; in a second sample period, the at least one multiplexer is configured to select the odd scaling factor of 0 for the quadrature sample and of −2 for the phase sample. ### Claim 19 (depends on 12) The apparatus of claim 12, further comprising a quantizer to sample the input signal at a rate fs. ### Claim 20 (depends on 13) The apparatus of claim 13, wherein the multipliers are shift registers. ### Claim 21 A method of calculating an N-point discrete Fourier transform, the method comprising: generating, by a quantizer based on a received signal, an even quadrature sample value and an even phase sample value of the received signal, and an odd quadrature sample value and an odd phase sample value of the received signal in a sample period of the quantizer; counting, by a counter, a number of sample periods of the quantizer; scaling, by at least one scaling circuit, the even quadrature sample value, even phase sample value the odd quadrature sample value, and the odd phase sample value by at least one sealing factor; adding, by a first adding circuit, the scaled even quadrature sample value and the scaled odd quadrature sample value; adding, by a second adding circuit, the scaled even phase sample value and the scaled odd phase sample value; accumulating, by a first accumulator, the added scaled even and odd quadrature sample values; accumulating, by a second accumulator, the added scaled even and odd phase sample values; wherein N is selectable and is either 3 or 4, the at least one scaling factor is selectable based upon the value of N and the number of sample periods, and wherein when N is set to 3, the counter counts 3 sample periods, and wherein when N is set to 4, the counter counts 2 sample periods. ### Claim 22 (depends on 21) The method of claim 21, wherein, for the method, an even scaling circuit of the at least one scaling circuit comprises: a first parallel multiplier having a multiplication factor equal to −1; a second parallel multiplier having a multiplication factor equal to 2; a parallel path including a multiplier having at multiplication factor equal to 2 in series with the first parallel multiplier to provide a third parallel multiplier having a multiplication factor equal to −2; a zero input to provide a fourth parallel multiplier having a multiplication factor equal to 0; at least one multiplexer to select one of the parallel multipliers; and at least one series multiplier having a multiplication factor equal to 3.75, wherein the setting of the at least one multiplexer determines an even scaling factor for the sample value. ### Claim 23 (depends on 22) The method of claim 22, wherein, when N is set to 3, the method further comprises: selecting, by the at least one multiplexer in a first sample period, an even scaling factor of 2 for the quadrature sample and of 0 for the phase sample; selecting, by the at least one multiplexer in a second sample period, an even scaling factor of −1 for the quadrature sample and of −7 for the phase sample; and selection, by the at least one multiplexer in a third sample period, an even scaling factor of −1 for the quadrature sample and of 7 for the phase sample. ### Claim 24 (depends on 22) The method of claim 22, wherein, when N is set to 4, the method further comprises: selecting, by the at least one multiplexer in a first sample period, an even scaling factor of 2 for the quadrature sample and of 0 for the phase sample; and selecting, by the at least one multiplexer in a second sample period, an even sealing factor of −2 for the quadrature sample and of 0 for the phase sample. ### Claim 25 (depends on 21) The method of claim 21, wherein, for the method, an odd sealing circuit of the at least one sealing circuit comprises: a first parallel multiplier having a multiplication factor equal to −1; a second parallel multiplier having a multiplication factor equal to 2; a parallel path including a multiplier having a multiplication factor equal to 2 in series with the first parallel multiplier to provide a third parallel multiplier having a multiplication factor equal to −2; a zero input to provide a fourth parallel multiplier having a multiplication factor equal to 0; at least one multiplexer to select one of the parallel multipliers; and at least one multiplexer to select a series multiplier having a multiplication factor equal to 3.75, wherein the setting of the multiplexers determines an odd scaling factor for the sample value. ### Claim 26 (depends on 25) The method of claim 25, wherein, when N is set to 3, the method further comprises: selecting, by the at least one multiplexer in a first sample period, an odd scaling factor of −1 for the quadrature sample and of 7 for the phase sample; selecting, by the at least one multiplexer in a second sample period, an odd scaling factor of 2 for the quadrature sample and of 0 for the phase sample; and selecting, by the at least one multiplexer in a third sample period, an odd scaling factor of −1 for the quadrature sample and of −7 for the phase sample. ### Claim 27 (depends on 25) The method of claim 25, wherein, when N is set to 4, the method further comprises: selecting, by the at least one multiplexer in a first sample period, an odd scaling factor of 0 for the quadrature sample and of 2 for the phase sample; and selecting, by the at least one multiplexer in a second sample period, an odd scaling factor of 0 for the quadrature sample and of −2 for the phase sample. ### Claim 28 (depends on 22) The method of claim 22, wherein, for the method, the multipliers are shift registers. ### Claim 29 (depends on 25) The method of claim 25, wherein, for the method, the multipliers are shift registers.