Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

A method and device for generating fast Fourier transform codes

A Fourier transform and generating device technology, applied in the computer field, can solve problems such as high development threshold, low production efficiency, and difficult optimization of FFT codes

Active Publication Date: 2021-08-20
XFUSION DIGITAL TECH CO LTD
View PDF3 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, the existing solutions have the following deficiencies in the implementation of the FFT library: it is necessary to manually implement specific high-performance codes for different CPU architectures, the development threshold is high, the production efficiency is low, and different architectures or the same architecture but different specifications are required. The CPU implements different high-performance codes, and when the hardware platform changes, it is difficult to optimize the generated FFT code

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • A method and device for generating fast Fourier transform codes
  • A method and device for generating fast Fourier transform codes
  • A method and device for generating fast Fourier transform codes

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0088] For ease of understanding, the specific process of the embodiment of the present application is described below, please refer to image 3 , an embodiment of the fast Fourier transform code generation method in the embodiment of the present application includes:

[0089] 301. Acquire a data sequence that requires fast Fourier transform (FFT) and the length of the data sequence.

[0090] Wherein, the length N of the obtained data sequence may be determined in advance, and according to the length N, a data sequence containing N data that needs to be subjected to fast Fourier transform FFT can be obtained, and the data in the data sequence is usually a discrete digital signal.

[0091] 302. Determine the FFT decomposition mode of the data sequence according to the length of the data sequence, and obtain one or more stages of the butterfly network corresponding to the FFT decomposition mode, and each level corresponds to a butterfly basis.

[0092] The FFT decomposition met...

Embodiment 2

[0114] Based on the foregoing embodiments, this embodiment specifically introduces the butterfly code and the mixed templates and atomic templates included in the butterfly code. see Figure 4A , another embodiment of the fast Fourier transform code generation method in the embodiment of the present application includes:

[0115] 401. Acquire a data sequence that requires fast Fourier transform (FFT) and the length of the data sequence.

[0116] 402. Determine the FFT decomposition mode of the data sequence according to the length of the data sequence, and obtain one or more stages of the butterfly network corresponding to the FFT decomposition mode, and each level corresponds to a butterfly basis.

[0117] Steps 401 to 402 are similar to steps 301 to 302, and details are not repeated here.

[0118] 403. Determine the butterfly code that needs to be called in each level and the number of times the butterfly code is called according to the base of the butterfly corresponding ...

Embodiment 3

[0406] Based on the above examples, see Figure 6 , another embodiment of the fast Fourier transform code generation method in the embodiment of the present application includes:

[0407] 601. Acquire a data sequence requiring fast Fourier transform (FFT) and the length of the data sequence.

[0408] 602. Determine an FFT decomposition mode of the data sequence according to the length of the data sequence, and obtain one or more stages of a butterfly network corresponding to the FFT decomposition mode, and each level corresponds to a butterfly basis.

[0409] 603. Determine the butterfly code that needs to be called in each level and the number of times the butterfly code is called according to the base of the butterfly corresponding to each level.

[0410] 604. Generate the codes of each stage step by step according to the butterfly codes in each stage and the number of times the butterfly codes in each stage are called, so as to obtain FFT codes for performing fast Fourier ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

This application discloses a fast Fourier transform code generation method and device, which are used to generate fast Fourier transform FFT codes, decompose the FFT codes into multiple atomic templates, facilitate subsequent optimization of the atomic templates, and further improve the FFT code performance. The method comprises: obtaining the data sequence that needs to be subjected to fast Fourier transform FFT and the length of the data sequence; determining the FFT decomposition mode of the data sequence according to the length of the data sequence, and obtaining one or more stages of the butterfly network corresponding to the FFT decomposition mode, Each level corresponds to a butterfly base; determine the butterfly code that needs to be called in each level and the calling times of the butterfly code in each level according to the butterfly base corresponding to each level; according to each level The butterfly codes in the stages and the number of times the butterfly codes in each stage are called generate the codes of each stage step by stage to obtain the FFT codes for fast Fourier transforming the data sequence.

Description

technical field [0001] The present application relates to the field of computers, in particular to a method and device for generating fast Fourier transform codes. Background technique [0002] Fast Fourier transform (fast Fourier transform, FFT) is a fast algorithm for computing discrete Fourier transform (DFT) or its inverse operation. It is widely used in engineering, science and mathematics, such as signal Decomposition, digital filtering, image processing, etc. Through Fourier analysis, the source data will be transformed from the original domain (usually time or space) to the frequency domain representation or vice versa. In order to adapt to numerical calculations performed on a computer, it is necessary to discretize the Fourier transform, which is called the discrete Fourier transform DFT, and its mathematical expression is formula (1): [0003] [0004] Compared with the traditional algorithm, the FFT algorithm can reduce the algorithm complexity of calculatin...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Patents(China)
IPC IPC(8): G06F8/30G06F17/14
CPCG06F8/31G06F17/142
Inventor 李志豪齐霁张邵敏景玉超贾海鹏
Owner XFUSION DIGITAL TECH CO LTD
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com