고속 푸리에 변환

개요

주기함수가 아닌 함수에 적용할 수 있는 스펙트럼 분석을 위한 개념은 푸리에 변환(Fourier transform)이라 불리는 것이다. 이 경우 함수는 연속적인 스펙트럼을 갖게 된다. 이는 푸리에 급수가 주기함수에 대한 스펙트럼 분석, 즉 악기의 소리나 원자의 스펙트럼과 같은 이산적인 스펙트럼 구조를 갖는 것과 대비된다. 이 푸리에 변환의 개념은 20세기에 컴퓨터의 계산 능력과 만나 인간의 삶에 더욱 넓고 큰 영향을 끼치게 되는데, 고속 푸리에 변환(Fast Fourier Transform)의 발견이 그것이다.

1963년 미국과 소련의 핵실험 금지 협정의 비준 문제가 심각하게 논의될 무렵, 미국의 고민은 소련을 방문하지 않고도 핵실험을 탐지할 수 있는 방법의 개발 여부에 있었다. 한 가지 방법은 소련의 주변국의 연안에서의 지질활동 관측 데이터를 이용하는 것이었다. 지질활동의 관측 데이터는 위에서 얘기한 시계열 자료에 해당한다. 이를 분석하기 위해 푸리에 변환을 사용하면 되겠지만, 현실적인 문제는 푸리에 변환을 위해서는 많은 양의 계산이 필요하다는 것이었다. 존 투키는 대통령 과학 자문 위원회의 일원으로서 소련의 핵실험 여부를 탐지할 방법을 논의하는 회의에 참석하기도 했는데 이 고민의 과정에서 쿨리와 함께 오늘날 디지털 시대를 떠받칠 세기의 알고리즘인 일명 FFT '고속 푸리에 변환(Fast Fourier Transform)' 을 탄생시키게 된다.[Cooley1987]

탄생의 순간부터 핵실험의 탐지, 잠수함의 탐지, X-선 결정학과 같은 분야에의 응용을 목적으로 하였던 고속 푸리에 변환은 이후 컴퓨터의 발달에 발맞추어 음향학, 생의학 영상공학, 레이더, 신호 처리, 분광학, 통신 등 수많은 분야로 응용 범위를 넓혀 왔다. 2000년 초 발간된 한 저널에서는 20세기의 알고리즘 10개를 선정하여 발표하였는데, 여기엔 투키와 쿨리의 고속 푸리에 변환이 포함되기도 하였다.[DS2000]

사용예

• 흑점 데이터

• 다음의 그림을 얻는데, 고속 푸리에 변환을 사용하였다

메모

• The Top Ten Algorithms of the Century
• The Best of the 20th Century: Editors Name Top 10 Algorithms", by Barry A. Cipra
• http://www.cosmolearning.com/video-lectures/complex-matrices-fast-fourier-transform/
• 소음진동공학회 http://www.ksnve.or.kr/search-2_1.htm?UID=195&query=&keywordTitle=&keyword=&sort=&key=&keye=
• How the FFT Gained Acceptance, Cooley

관련된 항목들

• 푸리에 변환
• 유한아벨군과 푸리에변환

사전 형태의 자료

• http://ko.wikipedia.org/wiki/
• http://en.wikipedia.org/wiki/Fast_Fourier_transform
• http://en.wikipedia.org/wiki/Cooley-Tukey_FFT_algorithm
• http://en.wikipedia.org/wiki/John_Tukey
• http://en.wikipedia.org/wiki/James_Cooley
• http://en.wikipedia.org/wiki/Richard_L._Garwin

관련논문

• [DS2000]Jack Dongarra and Francis Sullivan, “Guest Editors' Introduction: The Top 10 Algorithms,” Computing in Science and Engineering, 2000.doi:10.1109/MCISE.2000.814652
• D.N. Rockmore, “The FFT: an algorithm the whole family can use,” Computing in Science & Engineering 2, no. 1 (2000): 60-64. http://dx.doi.org/10.1109/5992.814659
• [Cooley1987]J.W. Cooley, "The Re-Discovery of the Fast Fourier Transform Algorithm," Mikrochimica Acta, Vol. 3, 1987, pp. 33-45. http://dx.doi.org/10.1007/BF01201681
• J.W. Cooley, P.A.W. Lewis, and P.D. Welch, “Historical notes on the fast Fourier transform,” Proceedings of the IEEE 55, no. 10 (1967): 1675-1677. http://dx.doi.org/10.1109/PROC.1967.5959
• http://www.ams.org/journals/mcom/1965-19-090/S0025-5718-1965-0178586-1/home.html

관련도서

• E. O. Brigham, The fast Fourier transform and its applications, Prentice Hall Signal Processing Series, Englewood Clis, NJ 1988.

노트

말뭉치

1. Various fast DFT computation techniques known collectively as the fast Fourier transform, or FFT.
2. Fast Fourier Transform, or FFT, is a computational algorithm that reduces the computing time and complexity of large transforms.
3. The most commonly used FFT algorithm is the Cooley-Tukey algorithm, which was named after J. W. Cooley and John Tukey.
4. Other FFT algorithms include the Rader’s algorithm, Winograd Fourier transform algorithm, Chirp Z-transform algorithm, etc.
5. The reason the Fourier transform is so prevalent is an algorithm called the fast Fourier transform (FFT), devised in the mid-1960s, which made it practical to calculate Fourier transforms on the fly.
6. Ever since the FFT was proposed, however, people have wondered whether an even faster algorithm could be found.
7. this week, a group of MIT researchers will present a new algorithm that, in a large range of practically important cases, improves on the fast Fourier transform.
8. Like the FFT, the new algorithm works on digital signals.
9. Strictly speaking, the FFT is an optimized algorithm for the implementation of the "Discrete Fourier Transformation" (DFT).
10. This changed in 1965 with the development of the fast Fourier transform (FFT).
11. By using the FFT algorithm to calculate the DFT, convolution via the frequency domain can be faster than directly convolving the time domain signals.
12. FFT convolution uses the overlap-add method shown in Fig.
13. Figure 18-2 shows an example of how an input segment is converted into an output segment by FFT convolution.
14. Because of the importance of the FFT in so many fields, Python contains many standard tools and wrappers to compute this.
15. For the moment, though, let's leave these implementations aside and ask how we might compute the FFT in Python from scratch.
16. As the name implies, the Fast Fourier Transform (FFT) is an algorithm that determines Discrete Fourier Transform of an input significantly faster than computing it directly.
17. More information and examples can be found in the application note titled FFT Applications for TDS Oscilloscopes.
18. A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT).
19. In the presence of round-off error, many FFT algorithms are much more accurate than evaluating the DFT definition directly or indirectly.
20. His method was very similar to the one published in 1965 by James Cooley and John Tukey, who are generally credited for the invention of the modern generic FFT algorithm.
21. Between 1805 and 1965, some versions of FFT were published by other authors.
22. The Cooley-Tukey algorithm came to be known as the fast fourier transform or FFT.
23. The value of the FFT was quickly realized all over the world.
24. Corporations were founded to exploit the FFT.
25. One of those corporations, Federal Scientific, used the FFT to analyze the famous 18 minute gap in the recordings made by Richard Nixon in 1973.
26. The FFT size defines the number of bins used for dividing the window into equal strips, or bins.
27. A discrete Fourier transform can be computed using an FFT by means of the Danielson-Lanczos lemma if the number of points is a power of two.
28. The Cooley-Tukey FFT algorithm first rearranges the input elements in bit-reversed order, then builds the output transform (decimation in time).
29. The discovery of the Fast Fourier transformation (FFT) is attributed to Cooley and Tukey, who published an algorithm in 1965.
30. But in fact the FFT has been discovered repeatedly before, but the importance of it was not understood before the inventions of modern computers.
31. Some researchers attribute the discovery of the FFT to Runge and König in 1924.
32. The basic idea of the FFT is to apply divide and conquer.
33. Compute the 2-dimensional FFT of a real array.
34. Compute the 2-dimensional inverse FFT of a real array.
35. Compute the FFT of a signal that has Hermitian symmetry, i.e., a real spectrum.
36. The FFT input signal is inherently truncated.
37. given by A fast Fourier transform (FFT) is an efficient way to compute the DFT.
38. By using FFT instead of DFT, the computational complexity can be reduced from O( ) to O(n log n).
39. Note that the input signal of the FFT in Origin can be complex and of any size.
40. The result of the FFT contains the frequency data and the complex transformed result.
41. A class of these algorithms are called the Fast Fourier Transform (FFT).
42. The main idea of FFT algorithms is to decompose an N-point DFT into transformations of smaller length.
43. The fast Fourier transform is a mathematical method for transforming a function of time into a function of frequency.
44. The following illustrations describe the sound of a London police whistle both in the time domain and in the frequency domain (by means of the FFT).
45. Three periods were chosen for the FFT this time, resulting in a main peak at position 3.
46. The FFT shows the two distinct frequencies of the individual pipes.
47. The FFT, or Fast Fourier Transform, provides a very fast way to transform data between the two domains.
48. The speed benefits of the FFT transform require an even power of two for the number of data points.
49. In most applications, you perform FFT and spectral analysis only on real-valued, discrete-time sequences.
50. The time-domain signal shown in Figure 3 demonstrates the three methods by which FFT results can be displayed graphically.
51. To graphically display the results of the FFT, wire the output arrays to the waveform graph, as shown in Figure 4.
52. The FFT integral, shown in equation 1, has a frequency range of .
53. Fast Fourier Transform (FFT) converts a time domain signal to frequency domain or vice-versa.
54. There are many ways you might compute an FFT within SIMION.
55. You could export the data to a text file and perform the FFT in another program like Matlab/Octave.
56. See Data Record periodically, with constant size time steps, possibly for FFT for how to acquire data with fixed periods, suitable for FFT analysis.
57. To calculate an FFT (Fast Fourier Transform), just listen.
58. Their work led to the development of a program known as the fast Fourier transform.
59. The fast Fourier transform (FFT) is a computationally efficient method of generating a Fourier transform.
60. The main advantage of an FFT is speed, which it gets by decreasing the number of calculations needed to analyze a waveform.
61. Fast Fourier Transform (FFT) is an efficient implementation of DFT and is used, apart from other fields, in digital image processing.
62. Fast Fourier Transform is applied to convert an image from the image (spatial) domain to the frequency domain.
63. This document will not go into the theory of FFT but will address the implementation of the algorithm in converting a 2D image to the frequency domain and back to the image domain (Inverse FFT).
64. FFT turns the complicated convolution operations into simple multiplications.
65. The Fast Fourier Transform (FFT) is commonly used to transform an image between the spatial and frequency domain.
66. Unlike other domains such as Hough and Radon, the FFT method preserves all original data.
67. Plus, FFT fully transforms images into the frequency domain, unlike time-frequency or wavelet transforms.
68. The FFT decomposes an image into sines and cosines of varying amplitudes and phases, which reveals repeating patterns within the image.
69. The Fast Fourier Transform (FFT) is used to transform an image from the spatial domain to the frequency domain, most commonly to reduce background noise from the image.
70. Below is the original image of M-51 galaxy (left) and inverse-FFT-transformed image (right).
71. The FFT LogiCORE™ IP core provides four different architectures along with system level fixed point C-models, and reduces typical implementation time from between 3-6 months to the push of a button.
72. FFT LogiCORE expands the focus on increased dynamic range by increasing data and phase factor width support up to 34 bits and supporting IEEE single precision floating point data type.
73. The Fast Fourier Transform (FFT) is a way to reduce the complexity of the Fourier transform computation from \(O(n^2)\) to \(O(n\log n)\), which is a dramatic improvement.
74. To verify that we have the correcdt results, we can execute the FFT algorithm using the fft() function in R, which computes a univariate FFT.
75. Fast Fourier transform algorithms use a divide-and-conquer strategy to factorize the matrix into smaller sub-matrices, corresponding to the integer factors of the length .
76. For a radix-2 FFT this gives an operation count of .
77. All the FFT functions offer three types of transform: forwards, inverse and backwards, based on the same mathematical definitions.
78. The inputs and outputs for the complex FFT routines are packed arrays of floating point numbers.

메타데이터

위키데이터

• ID : Q623950