检索结果-内蒙古大学图书馆

A cooley-tukey algorithm for the Slant Transform

International Journal of Computer Mathematics 1975年第1-4期5卷 331-338页

作者： Ahmed, N. Department of Electrical Engineering Kansas State University Manhattan Kansas 66506 United States Department of Computer Science Kansas State University Manhattan Kansas 66506 1100 NASA Road 1 Houston Texas 77058 United States

A cooley-tukey algorithm for the slant transform and its inverse is developed. It is shown that using this algorithm, one can compute the slant transform by means of a simple modification of the same cooley-tukey algorithm which is used to compute the Hadamard ordered Walsh-Hadamard transform. © 1975, Taylor & Francis Group, LLC. All rights reserved.

关键词： cooley-tukey algorithm Hadamard ordered Walsh-Hadamard transform slant transform

来源：评论

学校读者我要写书评

暂无评论

Composite Cyclotomic Fourier Transforms With Reduced Complexities

引用

IEEE TRANSACTIONS ON SIGNAL PROCESSING 2011年第5期59卷 2136-2145页

作者： Wu, Xuebin Wagh, Meghanad Chen, Ning Wang, Ying Yan, Zhiyuan Lehigh Univ Dept Elect & Comp Engn Bethlehem PA 18015 USA QUALCOMM Inc New Jersey Res Ctr Bridgewater NJ 08807 USA

Discrete Fourier transforms (DFTs) over finite fields have widespread applications in digital communication and storage systems. Hence, reducing the computational complexities of DFTs is of great significance. Recently proposed cyclotomic fast Fourier transforms (CFFTs) are promising due to their low multiplicative complexities. Unfortunately, there are two issues with CFFTs: (1) they rely on efficient short cyclic convolution algorithms, which have not been sufficiently investigated in the literature and (2) they have very high additive complexities when directly implemented. To address both issues, we make three main contributions in this paper. First, for any odd prime p, we reformulate a p-point cyclic convolution as the product of a (p - 1) x (p - 1) Toeplitz matrix and a vector, which has well-known efficient algorithms, leading to efficient bilinear algorithms for p-point cyclic convolutions. Second, to address the high additive complexities of CFFTs, we propose composite cyclotomic Fourier transforms (CCFTs). In comparison to previously proposed fast Fourier transforms, our CCFTs achieve lower overall complexities for moderate to long lengths and the improvement significantly increases as the length grows. Third, our efficient algorithms for p-point cyclic convolutions and CCFTs allow us to obtain longer DFTs over larger fields, e. g., the 2047-point DFT over GF(2(11)) and 4095-point DFT over GF(2(12)), which are first efficient DFTs of such lengths to the best of our knowledge. Finally, our CCFTs are also advantageous for hardware implementations due to their modular structure.

关键词： cooley-tukey algorithm cyclotomic fast Fourier transforms discrete Fourier transforms finite fields prime-factor algorithm

来源：评论

学校读者我要写书评

暂无评论

A GENERALIZATION OF FAST FOURIER TRANSFORM

引用

IEEE TRANSACTIONS ON COMPUTERS 1970年第2期C 19卷 105-+页

作者： GLASSMAN, JA Hughes Aircraft Company Canoga Park CA USA

A procedure for factoring of the N×N matrix representing the discrete Fourier transform is presented which does not produce shuffled data. Exactly one factor is produced for each factor of N, resulting in a fast Fourier transform valid for any N. The factoring algorithm enables the fast Fourier transform to be implemented in general with four nested loops, and with three loops if N is a power of two. No special logical organization, such as binary indexing, is required to unshuffle data. Included are two sample programs, one which writes the equations of the matrix factors employing the four key loops, and one which implements the algorithm in a fast Fourier transform for N a power of two. The algorithm is shown to be most efficient for Na power of two.

关键词： cooley-tukey algorithm discrete Fourier transform fast Fourier transform mixed radix spectral analysis.

来源：评论

学校读者我要写书评

暂无评论

Fast Fourier optimization Sparsity matters

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2012年第1期4卷 53-69页

作者： Vanderbei, Robert J. Princeton Univ Dept Operat Res & Financial Engn Princeton NJ 08544 USA

Many interesting and fundamentally practical optimization problems, ranging from optics, to signal processing, to radar and acoustics, involve constraints on the Fourier transform of a function. It is well-known that the fast Fourier transform (fft) is a recursive algorithm that can dramatically improve the efficiency for computing the discrete Fourier transform. However, because it is recursive, it is difficult to embed into a linear optimization problem. In this paper, we explain the main idea behind the fast Fourier transform and show how to adapt it in such a manner as to make it encodable as constraints in an optimization problem. We demonstrate a realworld problem from the field of high-contrast imaging. On this problem, dramatic improvements are translated to an ability to solve problems with a much finer grid of discretized points. As we shall show, in general, the "fast Fourier" version of the optimization constraints produces a larger but sparser constraint matrix and therefore one can think of the fast Fourier transform as a method of sparsifying the constraints in an optimization problem, which is usually a good thing.

关键词： Linear programming Fourier transform Interior-point methods High-contrast imaging Fast Fourier transform (fft) Optimization cooley-tukey algorithm

来源：评论

学校读者我要写书评

暂无评论

Double coset decompositions and computational harmonic analysis on groups

引用

JOURNAL OF FOURIER ANALYSIS AND APPLICATIONS 2000年第4期6卷 349-388页

作者： Maslen, DK Rockmore, DN Susquehanna Partners GP Bala Cynwyd PA 19004 USA Dartmouth Coll Dept Math Hanover NH 03755 USA

In this paper we introduce new techniques for the efficient computation of a Fourier transform on a finite group. We use the decomposition of a group into double cosets and a graph theoretic indexing scheme to derive algorithms that generalize the cooley-tukey FFT to arbitrary finite groups. We apply our general results to special linear groups and low rank symmetric groups, and obtain new efficient algorithms for harmonic analysis on these classes of groups, as well as the two-sphere.

关键词： generalized Fourier transform Bratteli diagram Gel'fand-Tsetlin basis cooley-tukey algorithm

来源：评论

学校读者我要写书评

暂无评论

BERKELEY ARRAY PROCESSOR

引用

IEEE TRANSACTIONS ON COMPUTERS 1970年第5期C 19卷 444-&页

作者： DERE, WY SAKRISON, DJ IEEE

The Berkeley array processor is a special-purpose computer designed to perform the operations of correlation, convolution, recursive filtering, matrix multiplication, as well as a variant of the cooley-tukey algorithm... 详细信息

关键词： Array processor convolution cooley-tukey algorithm correlation digital filtering Fourier transform special- purpose computer time series analysis.

来源：评论

学校读者我要写书评

暂无评论

Fast Acquisition of GPS Signal using FFT Decomposition 4

Fast Acquisition of GPS Signal using FFT Decomposition

引用

4th International Conference on Recent Trends in Computer Science and Engineering (ICRTCSE)

作者： Ahamed, Shaik Fayaz Rao, G. Sasibhushana Ganesh, L. VR Siddhartha Engn Coll Dept Elect & Commun Engn Vijayawada India Andhra Univ Dept Elect & Commun Engn Visakhapatnam Andhra Pradesh India ANITS Dept Elect & Commun Engn Visakhapatnam Andhra Pradesh India

Acquisition in Global Positioning System (GPS) is primary and important step to measure the code phase of Pseudo Random Noise (PRN) code and Doppler shift in carrier frequency of received GPS signal. The performance of a GPS receiver system depends on the fast and accurate measure of the code phase and Doppler shift in the recived signal. A new GPS signal acquisition method based on decomposition of FFT is proposed to improve the acquisition performance. Conventional GPS receivers use Fast Fourier Transform (FFT) to carry out correlation in the acquisition process. However, this paper proposes a new method that reduces the complexity of FFT computation. The proposed algorithm is implemented, validated and compared the performance with conventional serial search and radix2 FFT search algorithms using Intermediate Frequency (IF) GPS signal. Acquisition algorithms are implemented on 1.25MHz signal data of one millisecond period, sampled at 5MHz. For the sampled data, the proposed algorithm uses 5000 samples insted of number of samples raised to nearest power of 2 i.e. 8192 samples as in the case of radix2 FFT search method to compute FFT. Performance of the algorithms are compared based on computational time and correlation peak magnitude. (C) 2016 The Authors. Published by Elsevier B.V.

关键词： GPS acquisition FFT Radix2 FFT cooley-tukey algorithm WFTA

来源：评论

学校读者我要写书评

暂无评论

The Design of a Class of Fast Fourier Transform Computers

引用

IEEE Transactions on Computers 1971年第6期C-20卷 617-623页

作者： Corinthios, Michael J. Department of Electrical Engineering University of Toronto Toronto Ont Canada

The design of a class of special-purpose computers for time-series analysis by Fourier transformation is described. The computers are sequential machines which implement machine-oriented fast Fourier transform algorithms obtained by factoring the discrete Fourier transform to an arbitrary radix. A choice of the degree of parallelism in machine architecture is made possible by selecting a proper radix r for implementation. Throughout the iterations these algorithms call for accessing or storing data which are always N/r words apart, where N is the record size. Thus it is possible to partition the data into r queues, to the tops of which the arithmetic unit is hard-wired. Moreover, two of the implemented algorithms yield properly ordered Fourier coefficients without the need for pre- or post-ordering data. This is accomplished by including a simple shuffle operation as an inherent part of the feedback of each iteration. The processing speed and maximum sampling frequency for realtime operation are specified. It is shown that, with present day technology, a radix-4 machine would perform real-time spectrum analysis of 4096 point records sampled continuously at a rate of one million samples per second. © 1971, IEEE. All rights reserved.

关键词： Convolution cooley-tukey algorithm correlation digital filtering discrete Fourier transform special-purpose computer spectrum analysis time-series analysis

来源：评论

学校读者我要写书评

暂无评论

Speeding Up RSA Encryption Using GPU Parallelization 5

Speeding Up RSA Encryption Using GPU Parallelization

引用

5th International Conference on Intelligent Systems, Modelling and Simulation (ISMS)

作者： Lin, Chu-Hsing Liu, Jung-Chun Li, Cheng-Chieh Tunghai Univ Dept Comp Sci Taichung 40704 Taiwan

ISBN: (纸本)9781479938575

Due to the ever-increasing computing capability of high performance computers today, in order to protect encrypted data from being cracked, the bit number used in RSA, a common and practicable public-key cryptosystem, is also getting longer, resulting in increasing operation time spent in executing the RSA algorithm. We also note that while the development of CPU has reached limits, the graphics processing unit (GPU), a highly parallel programmable processor, has become an integral part of today's mainstream computing systems. Therefore, it is a savvy choice to take advantage of GPU computing to accelerate computation of the RSA algorithm and enhance its applicability as well. After analyzing the RSA algorithm, we find that big number operations consume most parts of computing resources. As the benefit acquired from combining Montgomery with GPU-based parallel methods is not high enough, we further introduce the Fourier transform and Newton's method to design a new parallel algorithm to accelerate the computation of big numbers.

关键词： RSA Montgomery method CUDA Fast Fourier Transform Newton's method cooley-tukey algorithm big number operation

来源：评论

学校读者我要写书评

暂无评论

SonicFFT: A system architecture for ultrasonic-based FFT acceleration 22

SonicFFT: A system architecture for ultrasonic-based FFT acc...

引用

27th Asia and South Pacific Design Automation Conference (ASP-DAC)

作者： Patel, Darayus Adil Bui, Viet Phuong Chai, Kevin Tshun Chuan Lal, Amit Aly, Mohamed M. Sabry Nanyang Technol Univ Singapore Singapore ASTAR Inst High Performance Comp Singapore Singapore ASTAR Inst Microelect Singapore Singapore Cornell Univ Ithaca NY USA

ISBN: (纸本)9781665421355

Fast Fourier Transform (FFT) is an essential algorithm for numerous scientific and engineering applications. It is key to implement FFT in a high-performance and energy-efficient manner. In this paper, we leverage the properties of ultrasonic wave propagation in silicon for FFT computation. We introduce SonicFFT: A system architecture for ultrasonic-based FFT acceleration. To evaluate the benefits of SonicFFT, a compact-model based simulation framework that quantifies the performance and energy of an integrated system comprising of digital computing components interfaced with an ultrasonic FFT accelerator has been developed. We also present mapping strategies to compute 2D FFT utilizing the accelerator. Simulation results show that SonicFFT achieves a 2317x system-level energy-delay product benefits-a simultaneous 117.69x speedup and 19.69x energy reduction-versus state-of-the-art baseline all-digital configuration.

关键词： FFT accelerator ultrasonic computation compact-modelling cooley-tukey algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：