# US 10,771,947 B2 · Methods and apparatus for twiddle factor generation for use with a programmable mixed-radix DFT/IDFT processor

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,771,947 B2
- Document ID: US10771947B2
- Status: Granted
- Kind: B2
- Application number: 16/506,820
- Filed: 2019-07-09
- Published: 2020-01-02
- Granted: 2020-09-08
- Earliest claimed: 2015-12-31
- Assignees: Cavium, Inc.
- Applicants: Cavium, LLC
- Inventors: Yuanbin Guo; Hong Jik Kim
- Web page: https://patentgrep.com/patent/US10771947B2

## CPC

- H04W 4/80: Services using short range communication, e.g. near-field communication [NFC], radio-frequency identification [RFID] or low energy communication
- G06F 17/142: {Fast Fourier transforms, e.g. using a Cooley-Tukey type algorithm}
- H04L 27/2636: {with FFT or DFT modulators, e.g. standard single-carrier frequency-division multiple access [SC-FDMA] transmitter or DFT spread orthogonal frequency division multiplexing [DFT-SOFDM]}
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Twiddle factor generation for use with a programmable mix-radix vector processor (“PVP”) capable of calculating discrete Fourier transform (“DFT/IDFT”) values. In an exemplary embodiment, an apparatus includes look-up table logic that receives twiddle control factors and outputs a selected twiddle factor scaler value (TFSV), a base vector generator that generates a base vector values based on the selected TFSV, and a twiddle column generator that generates a twiddle vector from the base vector.

## Claims

### Claim 1

A device containing a programmable vector processor (PVP) able to process data for network communication, comprising:
a state machine configured to generate twiddle factor control (TFC) signals, scaling control signals, and radix engine control signals;
a twiddle factor generator coupled to the state machine and able to provide twiddle factor data in accordance with the TFC signals;
a scaling unit coupled to the state machine and operable to scale pipeline vector data based on the scaling control signals; and
a mixed radix engine coupled to the state machine and configured to generate a first radix result via radix factorization in response to the radix engine control signals.

### Claim 2 (depends on 1)

The device of claim 1, wherein the mixed radix engine is configured to perform iteration in accordance with the radix engine control signals by calculating a second radix result in response to the first radix result.

### Claim 3 (depends on 1)

The device of claim 1, wherein the mixed radix engine is programmed to facilitate generation of a discrete Fourier transform (DFT) output in response to the first radix result.

### Claim 4 (depends on 1)

The device of claim 1, wherein the mixed radix engine is programmed to facilitate generation of an inverse discrete Fourier transform (IDFT) output in response to the first radix result.

### Claim 5 (depends on 1)

The device of claim 1, further comprising a look-up table (LUT) coupled to twiddle factor generator and configured to store a set of radix twiddle coefficients and configured to receive twiddle control factors.

### Claim 6 (depends on 5)

The device of claim 5, wherein the LUT facilitates to output a selected twiddle factor scaler value (TFSV) in accordance with the twiddle control factors and one or more radix twiddle coefficients.

### Claim 7 (depends on 6)

The device of claim 6, further comprising a base vector generator coupled to the LUT and configured to generate a base vector value in accordance with the selected TFSV.

### Claim 8 (depends on 1)

The device of claim 1, wherein the LUT stores TFSVs for radix 3 and radix 6.

### Claim 9 (depends on 1)

The device of claim 1, wherein the LUT is configured to store TFSVs for radix 4 and radix 5.

### Claim 10 (depends on 1)

The device of claim 1, wherein the twiddle vector generator includes a vector cross multiplier that iteratively multiplies the base vector to generate the twiddle vector.

### Claim 11 (depends on 10)

The device of claim 10, wherein the twiddle vector generator includes step coefficients to compute twiddle vectors for a last radix stage.

### Claim 12 (depends on 1)

The device of claim 1, wherein the twiddle vector is output to a twiddle multiplication unit in a vector pipeline that carries up to 12 samples per cycle.

### Claim 13

A method of generating twiddle values for a programmable vector processor (PVP) for network communication, the method comprising:
providing twiddle factor control (TFC) signals by a state machine to a twiddle factor generator for generating twiddle factor data;
sending scaling control signals via the state machine to a scaling unit for scaling pipeline vector data;
forwarding radix engine control signals from the state machine to a mixed radix engine for computing an intermediate radix result in response to the twiddle factor data and the pipeline vector data; and
storing the intermediate radix result in a memory bank for next iteration for determining a discrete Fourier transform (DFT) result.

### Claim 14 (depends on 13)

The method of claim 13, further comprising receiving twiddle control factors, by look-up table (“LUT”) logic, containing information relating to twiddle factor.

### Claim 15 (depends on 13)

The method of claim 13, further comprising
searching an LUT to identify at least one radix twiddle coefficient in accordance with the twiddle control factors; and
obtaining a selected twiddle factor scaler value (TFSV) in response to the radix twiddle coefficient.

### Claim 16 (depends on 15)

The method of claim 15, further comprising generating a base vector value based on the TFSV and generating a twiddle vector from the base vector.

### Claim 17 (depends on 15)

The method of claim 15, further comprising generating an address associated with the received twiddle control factors.

### Claim 18

A method of generating twiddle values via multiple iterations in a programmable vector processor (PVP), the method comprising:
forwarding vector data from a memory to a vector mixed-radix engine via a vector data-path pipeline;
computing by the vector mixed-radix engine an intermediate radix result in accordance with the vector data;
storing the intermediate radix result in the memory for next iteration;
reconfiguring the vector mixed-radix engine based on a next radix factor; and
outputting a final radix result by the vector mix-radix engine in response to the intermediate radix result retrieved from the memory passing through the vector data-path pipeline.

### Claim 19 (depends on 18)

The method of claim 18, wherein forwarding vector data from a memory to a vector mixed-radix engine further includes providing twiddle factor control (TFC) signals by a state machine to a twiddle factor generator for generating twiddle factor data.

### Claim 20 (depends on 18)

The method of claim 18, wherein forwarding vector data from a memory to a vector mixed-radix engine further includes sending scaling control signals via the state machine to a scaling unit for scaling pipeline vector data.