Cooley–Tukey FFT algorithm (original) (raw)
L'algorisme de Cooley–Tukey és l'algorisme de transformada ràpida de Fourier (FFT) més freqüent. Per tal d'aplicar la FFT, re-expressa la transformada discreta de Fourier (DFT) d'un compost arbitrari n = n1n₂ en termes de n1 DFTs de mida n₂, recursivament, per reduir el temps computacional a O(n log n).
| Property | Value |
|---|---|
| dbo:abstract | L'algorisme de Cooley–Tukey és l'algorisme de transformada ràpida de Fourier (FFT) més freqüent. Per tal d'aplicar la FFT, re-expressa la transformada discreta de Fourier (DFT) d'un compost arbitrari n = n1n₂ en termes de n1 DFTs de mida n₂, recursivament, per reduir el temps computacional a O(n log n). (ca) The Cooley–Tukey algorithm, named after J. W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re-expresses the discrete Fourier transform (DFT) of an arbitrary composite size in terms of N1 smaller DFTs of sizes N2, recursively, to reduce the computation time to O(N log N) for highly composite N (smooth numbers). Because of the algorithm's importance, specific variants and implementation styles have become known by their own names, as described below. Because the Cooley–Tukey algorithm breaks the DFT into smaller DFTs, it can be combined arbitrarily with any other algorithm for the DFT. For example, Rader's or Bluestein's algorithm can be used to handle large prime factors that cannot be decomposed by Cooley–Tukey, or the prime-factor algorithm can be exploited for greater efficiency in separating out relatively prime factors. The algorithm, along with its recursive application, was invented by Carl Friedrich Gauss. Cooley and Tukey independently rediscovered and popularized it 160 years later. (en) Algorytm Cooleya-Tukeya – algorytm szybkiej transformacji Fouriera (FFT). Wyraża dyskretną transformację Fouriera (DFT) o dowolnej złożonej wielkości w członach mniejszych DFT wielkości i rekurencyjnie, w celu ograniczenia czasu obliczeń do szczególnie w przypadku będącego liczbą wysoce złożoną (liczbą gładką). Ze względu na znaczenie algorytmu, poszczególne warianty i style implementacji są znane pod własnymi nazwami, jak opisano poniżej. Algorytm został nazwany imieniem J.W. Cooleya i Johna Tukeya. Ponieważ algorytm Cooleya-Tukeya rozbija DFT na mniejsze DFT, może być połączony arbitralnie z dowolnym innym algorytmem DFT. Na przykład algorytm Rädera lub Bluesteina może obsługiwać duże czynniki pierwsze, które nie mogą być rozkładane przez algorytm Cooley-Tukeya lub można wykorzystać algorytm czynników pierwszych dla większej wydajności wydzielania względnie pierwszych czynników. (pl) Алгоритм Ку́ли — Тью́ки — наиболее часто используемый алгоритм вычисления быстрого преобразования Фурье. Алгоритм позволяет выразить дискретное преобразование Фурье длины, равной произвольному составному числу , через определённое количество преобразований меньшей длины с помощью рекурсии, понижая таким образом сложность вычислений до для гладких . Назван в честь Дж. Кули и Дж. Тьюки. (ru) Алгоритм Кулі — Тьюкі — найбільш поширений алгоритм швидкого перетворення Фур'є (ШПФ), запропонований та названий на честь американських математиків та Джона Тьюкі. Пізніше було з'ясовано, що алгоритм було винайдено Гаусом ще 160 років до цього. На відміну від дискретного перетворення Фур'є (ДПФ), у якому для обчислення потрібно O(N2) арифметичних операцій, алгоритм дозволяє обчислити той самий результат з невеликою похибкою за O(N log N) операцій, тому й отримав популярність в апаратній та програмній обробці сигналів. (uk) 库利－图基快速傅里叶变换算法（英語：Cooley–Tukey FFT algorithm）是最常見的快速傅里葉變換算法。這一方法以分治法為策略遞歸地將長度為N = N1N2的DFT分解為長度分別為N1和N2的兩個較短序列的DFT，以及與旋轉因子的複數乘法。這種方法以及FFT的基本思路在1965年詹姆斯·庫利和約翰·圖基合作發表《An algorithm for the machine calculation of complex Fourier series》之後開始為人所知。但後來發現，實際上這兩位作者只是重新發明了高斯在1805年就已經提出的算法（此算法在歷史上數次以各種形式被再次提出）。 库利－图基算法最有名的應用，是將序列長為N的DFT分割為兩個長為N/2的子序列的DFT，因此這一應用只適用於序列長度為2的冪的DFT計算，即基2-FFT。實際上，如同高斯和库利與图基都指出的那樣，库利－图基算法也可以用於序列長度N為任意因數分解形式的DFT，即混合基FFT，而且還可以應用於其他諸如分裂基FFT等變種。儘管库利－图基算法的基本思路是採用遞歸的方法進行計算，大多數傳統的算法實現都將顯示的遞歸算法改寫為非遞歸的形式。另外，因為库利－图基算法是將DFT分解為較小長度的多個DFT，因此它可以同任一種其他的DFT算法聯合使用。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/DIT-FFT-butterfly.svg?width=300 |
| dbo:wikiPageExternalLink | http://en.dsplib.org/content/fft_dec_in_time.html http://ru.dsplib.org/content/fft_dec_in_time/fft_dec_in_time.html http://www.librow.com/articles/article-10 http://en.dsplib.org/content/fft_dec_in_freq.html http://ru.dsplib.org/content/fft_dec_in_freq/fft_dec_in_freq.html https://github.com/mborgerding/kissfft https://web.archive.org/web/20171031023423/http:/en.dsplib.org/content/fft_dec_in_time.html https://web.archive.org/web/20171114115729/http:/en.dsplib.org/content/fft_dec_in_freq.html |
| dbo:wikiPageID | 352702 (xsd:integer) |
| dbo:wikiPageLength | 36866 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1122438390 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Carl_David_Tolmé_Runge dbr:Carl_Friedrich_Gauss dbr:Power_of_two dbr:Princeton_University dbr:Processor_register dbr:Butterfly_(FFT_algorithm) dbr:Binary_numeral_system dbr:History_of_computing_hardware dbr:John_Tukey dbr:List_of_trigonometric_identities dbr:Permutation dbr:Richard_Garwin dbr:Depth-first_search dbr:Cornelius_Lanczos dbr:Analog-to-digital_converter dbr:SIMD dbr:Split-radix_FFT_algorithm dbr:GitHub dbc:Divide-and-conquer_algorithms dbr:Roots_of_unity dbr:Cache-oblivious_algorithm dbr:Cache_(computing) dbr:Composite_number dbr:Prime-factor_FFT_algorithm dbr:Stride_of_an_array dbc:Articles_with_example_pseudocode dbr:CPU_cache dbr:Transpose dbr:G._C._Danielson dbr:James_Cooley dbr:2_Pallas dbr:3_Juno dbr:Adding_machine dbr:E_(mathematical_constant) dbr:Breadth-first_search dbr:Bluestein's_FFT_algorithm dbr:Fast_Fourier_transform dbr:Floating_point dbr:Lemma_(mathematics) dbr:Rader's_FFT_algorithm dbr:Recursion dbr:Helium-3 dbr:International_Business_Machines dbr:Array_data_structure dbr:Asteroid dbr:Chinese_Remainder_Theorem dbr:Bit-reversal_permutation dbc:FFT_algorithms dbr:Discrete_Fourier_transform dbr:Divide_and_conquer_algorithm dbr:Butterfly_diagram dbr:Soviet_Union dbr:Dataflow_diagram dbr:I._J._Good dbr:In-place_algorithm dbr:Smooth_number dbr:Twiddle_factor dbr:IBM_7094 dbr:New_Latin dbr:Pseudocode dbr:Human_computer dbr:Row-major_order dbr:Linearithmic dbr:Breadth-first dbr:Relatively_prime dbr:Nuclear_testing dbr:Column-major_order dbr:CPU_pipeline dbr:Depth-first dbr:Memory_locality dbr:Out-of-core dbr:File:DIT-FFT-butterfly.svg dbr:File:Row_and_column_major_order.svg dbr:File:Cooley-tukey-general.png |
| dbp:wikiPageUsesTemplate | dbt:GitHub dbt:Cite_web dbt:Radic dbt:Reflist dbt:Short_description dbt:Use_American_English dbt:What? |
| dcterms:subject | dbc:Divide-and-conquer_algorithms dbc:Articles_with_example_pseudocode dbc:FFT_algorithms |
| rdf:type | yago:WikicatLemmas yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Communication100033020 yago:Event100029378 yago:Lemma106751833 yago:Message106598915 yago:Procedure101023820 yago:Proposition106750804 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:Statement106722453 yago:WikicatFFTAlgorithms |
| rdfs:comment | L'algorisme de Cooley–Tukey és l'algorisme de transformada ràpida de Fourier (FFT) més freqüent. Per tal d'aplicar la FFT, re-expressa la transformada discreta de Fourier (DFT) d'un compost arbitrari n = n1n₂ en termes de n1 DFTs de mida n₂, recursivament, per reduir el temps computacional a O(n log n). (ca) Алгоритм Ку́ли — Тью́ки — наиболее часто используемый алгоритм вычисления быстрого преобразования Фурье. Алгоритм позволяет выразить дискретное преобразование Фурье длины, равной произвольному составному числу , через определённое количество преобразований меньшей длины с помощью рекурсии, понижая таким образом сложность вычислений до для гладких . Назван в честь Дж. Кули и Дж. Тьюки. (ru) Алгоритм Кулі — Тьюкі — найбільш поширений алгоритм швидкого перетворення Фур'є (ШПФ), запропонований та названий на честь американських математиків та Джона Тьюкі. Пізніше було з'ясовано, що алгоритм було винайдено Гаусом ще 160 років до цього. На відміну від дискретного перетворення Фур'є (ДПФ), у якому для обчислення потрібно O(N2) арифметичних операцій, алгоритм дозволяє обчислити той самий результат з невеликою похибкою за O(N log N) операцій, тому й отримав популярність в апаратній та програмній обробці сигналів. (uk) 库利－图基快速傅里叶变换算法（英語：Cooley–Tukey FFT algorithm）是最常見的快速傅里葉變換算法。這一方法以分治法為策略遞歸地將長度為N = N1N2的DFT分解為長度分別為N1和N2的兩個較短序列的DFT，以及與旋轉因子的複數乘法。這種方法以及FFT的基本思路在1965年詹姆斯·庫利和約翰·圖基合作發表《An algorithm for the machine calculation of complex Fourier series》之後開始為人所知。但後來發現，實際上這兩位作者只是重新發明了高斯在1805年就已經提出的算法（此算法在歷史上數次以各種形式被再次提出）。 库利－图基算法最有名的應用，是將序列長為N的DFT分割為兩個長為N/2的子序列的DFT，因此這一應用只適用於序列長度為2的冪的DFT計算，即基2-FFT。實際上，如同高斯和库利與图基都指出的那樣，库利－图基算法也可以用於序列長度N為任意因數分解形式的DFT，即混合基FFT，而且還可以應用於其他諸如分裂基FFT等變種。儘管库利－图基算法的基本思路是採用遞歸的方法進行計算，大多數傳統的算法實現都將顯示的遞歸算法改寫為非遞歸的形式。另外，因為库利－图基算法是將DFT分解為較小長度的多個DFT，因此它可以同任一種其他的DFT算法聯合使用。 (zh) The Cooley–Tukey algorithm, named after J. W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re-expresses the discrete Fourier transform (DFT) of an arbitrary composite size in terms of N1 smaller DFTs of sizes N2, recursively, to reduce the computation time to O(N log N) for highly composite N (smooth numbers). Because of the algorithm's importance, specific variants and implementation styles have become known by their own names, as described below. (en) Algorytm Cooleya-Tukeya – algorytm szybkiej transformacji Fouriera (FFT). Wyraża dyskretną transformację Fouriera (DFT) o dowolnej złożonej wielkości w członach mniejszych DFT wielkości i rekurencyjnie, w celu ograniczenia czasu obliczeń do szczególnie w przypadku będącego liczbą wysoce złożoną (liczbą gładką). Ze względu na znaczenie algorytmu, poszczególne warianty i style implementacji są znane pod własnymi nazwami, jak opisano poniżej. Algorytm został nazwany imieniem J.W. Cooleya i Johna Tukeya. (pl) |
| rdfs:label | Algorisme de Cooley–Tukey (ca) Cooley–Tukey FFT algorithm (en) Algorytm Cooleya-Tukeya (pl) Алгоритм Кули — Тьюки (ru) Алгоритм Кулі — Тьюкі (uk) 库利－图基快速傅里叶变换算法 (zh) |
| owl:sameAs | freebase:Cooley–Tukey FFT algorithm wikidata:Cooley–Tukey FFT algorithm dbpedia-ca:Cooley–Tukey FFT algorithm dbpedia-he:Cooley–Tukey FFT algorithm dbpedia-pl:Cooley–Tukey FFT algorithm dbpedia-ru:Cooley–Tukey FFT algorithm dbpedia-sr:Cooley–Tukey FFT algorithm dbpedia-uk:Cooley–Tukey FFT algorithm dbpedia-zh:Cooley–Tukey FFT algorithm https://global.dbpedia.org/id/4iJyZ |
| prov:wasDerivedFrom | wikipedia-en:Cooley–Tukey_FFT_algorithm?oldid=1122438390&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Row_and_column_major_order.svg wiki-commons:Special:FilePath/Cooley-tukey-general.png wiki-commons:Special:FilePath/DIT-FFT-butterfly.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Cooley–Tukey_FFT_algorithm |
| is dbo:wikiPageRedirects of | dbr:Cooley-Tukey_FFT dbr:Cooley_Tukey_Algorithm dbr:Cooley_Tukey_algorithm dbr:Cooley–Tukey_FFT dbr:Danielson-Lanczos_lemma dbr:Cooley-Tukey_FFT_algorithm dbr:Danielson–Lanczos_lemma |
| is dbo:wikiPageWikiLink of | dbr:Carl_Friedrich_Gauss dbr:List_of_algorithms dbr:List_of_examples_of_Stigler's_law dbr:Cooley-Tukey_FFT dbr:Cooley_Tukey_Algorithm dbr:Cooley_Tukey_algorithm dbr:Cooley–Tukey_FFT dbr:John_Tukey dbr:Richard_Garwin dbr:List_of_harmonic_analysis_topics dbr:List_of_lemmas dbr:List_of_numerical_analysis_topics dbr:Cornelius_Lanczos dbr:Mathematical_diagram dbr:Schönhage–Strassen_algorithm dbr:Split-radix_FFT_algorithm dbr:Timeline_of_algorithms dbr:Cache-oblivious_algorithm dbr:Chirp_Z-transform dbr:Computer_engineering_compendium dbr:Parallel_computing dbr:Prime-factor_FFT_algorithm dbr:1965_in_science dbr:Trigonometric_interpolation dbr:Divide-and-conquer_algorithm dbr:G._C._Danielson dbr:James_Cooley dbr:List_of_Brown_University_alumni dbr:FFTW dbr:Fourier_analysis dbr:Parity_of_zero dbr:Danielson-Lanczos_lemma dbr:Fast_Fourier_transform dbr:Rader's_FFT_algorithm dbr:HPC_Challenge_Benchmark dbr:Bit-reversal_permutation dbr:Mixed_radix dbr:Discrete_Fourier_transform dbr:Discrete_Hartley_transform dbr:Discrete_cosine_transform dbr:Butterfly_diagram dbr:Cooley-Tukey_FFT_algorithm dbr:Danielson–Lanczos_lemma dbr:Kronecker_product dbr:Bruun's_FFT_algorithm dbr:Smooth_number dbr:Twiddle_factor dbr:Vector-radix_FFT_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Cooley–Tukey_FFT_algorithm |
