This HTML5 document contains 293 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbpedia-dahttp://da.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
n64https://www.karlsims.com/
n20http://www.fftw.org/
dbpedia-svhttp://sv.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
n19https://github.com/anthonix/
dbrhttp://dbpedia.org/resource/
n56https://www.slideshare.net/akliluw/
dbpedia-shhttp://sh.dbpedia.org/resource/
dbpedia-arhttp://ar.dbpedia.org/resource/
n35http://www.vosesoftware.com/ModelRiskHelp/index.htm%23Aggregate_distributions/
dbpedia-hehttp://he.dbpedia.org/resource/
n28http://groups.csail.mit.edu/netmit/sFFT/
n40http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
n13http://www.jjj.de/fxt/
dcthttp://purl.org/dc/terms/
dbpedia-cshttp://cs.dbpedia.org/resource/
rdfshttp://www.w3.org/2000/01/rdf-schema#
dbpedia-azhttp://az.dbpedia.org/resource/
n61http://www.virtins.com/doc/D1002/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n31http://d-nb.info/gnd/
n45http://dbpedia.org/resource/File:
dbphttp://dbpedia.org/property/
n41http://numericalmethods.eng.usf.edu/topics/
xsdhhttp://www.w3.org/2001/XMLSchema#
n57https://web.archive.org/web/20100430161231/http:/www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/
dbpedia-idhttp://id.dbpedia.org/resource/
dbpedia-ukhttp://uk.dbpedia.org/resource/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbohttp://dbpedia.org/ontology/
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/
n36http://www.akiti.ca/
n24http://www.alglib.net/fasttransforms/
dbchttp://dbpedia.org/resource/Category:
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-plhttp://pl.dbpedia.org/resource/
dbpedia-ruhttp://ru.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
n32http://d-nb.info/gnd/4136070-9/about/
n14http://ta.dbpedia.org/resource/
n48http://apps.nrbook.com/empanel/
wikidatahttp://www.wikidata.org/entity/
dbpedia-nlhttp://nl.dbpedia.org/resource/
n52https://global.dbpedia.org/id/
yago-reshttp://yago-knowledge.org/resource/
n55https://web.archive.org/web/20130928020959/http:/www.borgdesign.ro/
n43http://www.librow.com/articles/
n5http://hi.dbpedia.org/resource/
dbpedia-ithttp://it.dbpedia.org/resource/
dbpedia-cahttp://ca.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
n53http://cnx.org/content/col10550/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-kohttp://ko.dbpedia.org/resource/
n18http://www.dataphysics.com/
dbpedia-fahttp://fa.dbpedia.org/resource/
dbpedia-trhttp://tr.dbpedia.org/resource/
n15http://www.cs.pitt.edu/~kirk/cs1501/animations/
n49http://www.etti.unibw.de/labalive/experiment/fft/
dbpedia-eshttp://es.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbr:Fast_Fourier_transform
rdf:type
yago:WikicatFFTAlgorithms yago:Rule105846932 yago:PsychologicalFeature100023100 yago:Procedure101023820 yago:WikicatAlgorithms yago:Abstraction100002137 yago:Algorithm105847438 yago:YagoPermanentlyLocatedEntity yago:Act100030358 yago:Event100029378 yago:Activity100407535
rdfs:label
Transformada rápida de Fourier Trasformata di Fourier veloce Schnelle Fourier-Transformation Snabb fouriertransform 快速傅里叶变换 Transformasi Fourier cepat تحويل فوريي السريع Transformada rápida de Fourier Fast Fourier transform Rychlá Fourierova transformace Быстрое преобразование Фурье Transformada ràpida de Fourier Transformation de Fourier rapide Fast Fourier transform Szybka transformacja Fouriera 高速フーリエ変換 고속 푸리에 변환 Швидке перетворення Фур'є
rdfs:comment
La Transformada rápida de Fourier, conocida por la abreviatura FFT (del inglés Fast Fourier Transform) es un algoritmo eficiente que permite calcular la transformada de Fourier discreta (DFT) y su inversa. La FFT es de gran importancia en una amplia variedad de aplicaciones, desde el tratamiento digital de señales y filtrado digital en general a la resolución de ecuaciones en derivadas parciales o los algoritmos de multiplicación rápida de grandes enteros. Cuando se habla del tratamiento digital de señales, el algoritmo FFT impone algunas limitaciones en la señal y en el espectro resultante ya que la señal muestreada y que se va a transformar debe consistir de un número de muestras igual a una potencia de dos. La mayoría de los analizadores de FFT permiten la transformación de 512, 1024, 2 تحويل فوريي السريع (Fast Fourier Transformation) هي خوارزمية تمكن من حساب قيمة تحويل فوريي المتقطع بسرعة. تعود سرعة هذه الخوارزمية إلى أنها لا تقوم بحساب الأجزاء التي يساوي مجموعها صفرا في تحويل فوريي المتقطع. وتنسب الخوارزمية إلى جيمس كولي James W. Cooley John W. Tukey اللذان قاما بنشر الخوارزمية سنة 1965 وذلك بالصيغة المعروفة اليوم، إلا أن العالم الألماني كارل فريدرش غاوس قام بصياغة خوارزمية شبيهة سنة 1805 واستعملها في حساب مجرى المذنبات بالاس وجونو. كما تم تطوير بعض الحالات الخاصة من الخوارزمية قبل اكتشاف توكي لها (من قبل غود سنة 1960). La transformada ràpida de Fourier (o FFT, de l'anglès Fast Fourier transform), no és més que una forma molt ràpida i eficient de calcular la transformada discreta de Fourier (DFT) d'un senyal discret i la seva inversa, la (IDFT). D'aquí ve la seva importància pel desenvolupament de les telecomunicacions. Operacions que abans de la FFT podien desestimar-se per la seva complexitat, van començar-se a fer utilitzant aquesta nova transformada ràpida de Fourier. 快速傅里叶变换(英語:Fast Fourier Transform, FFT),是快速计算序列的离散傅里叶变换(DFT)或其逆变换的方法。傅里叶分析将信号从原始域(通常是时间或空间)转换到頻域的表示或者逆过来转换。FFT会通过把DFT矩阵分解为稀疏(大多为零)因子之积来快速计算此类变换。 因此,它能够将计算DFT的复杂度从只用DFT定义计算需要的 ,降低到 ,其中 为数据大小。 快速傅里叶变换广泛的应用于工程、科学和数学领域。这里的基本思想在1965年才得到普及,但早在1805年就已推导出来。 1994年美國數學家把FFT描述为“我们一生中最重要的数值算法”,它还被IEEE科学与工程计算期刊列入20世纪十大算法。 Швидке́ перетво́рення Фур'є́ (часто FFT від англ. Fast Fourier Transform) — швидкий алгоритм обчислення дискретного перетворення Фур'є. Якщо для прямого обчислення дискретного перетворення Фур'є з N точок даних потрібно O(N 2) арифметичних операцій, то FFT дозволяє обчислити такий же результат використовуючи O(N log N) операцій. Алгоритм FFT часто використовується для цифрової обробки сигналів для перетворення дискретних даних з часового у частотний діапазон. Szybka transformacja Fouriera (ang. Fast Fourier Transform, FFT) – algorytm wyznaczania dyskretnej transformaty Fouriera oraz transformaty do niej odwrotnej. Czasem, w odniesieniu do tej metody, używane jest też określenie szybka transformata Fouriera, które jednak nie jest prawidłowe, gdyż pojęcie transformacja oznacza przekształcenie, a transformata jest wynikiem tego przekształcenia. Niech będą liczbami zespolonymi, wtedy dyskretna transformata Fouriera jest określona wzorem: Obliczanie sum za pomocą powyższego wzoru wymaga wykonania operacji (zob. asymptotyczne tempo wzrostu). En snabb fouriertransform, på engelska fast Fourier transform (FFT), är en effektiv algoritm för att beräkna en diskret, begränsad fouriertransform. Vanligtvis kräver en diskret fouriertransform av en signal med sampelpunkter multiplikationer, men med hjälp av FFT sjunker denna siffra till i storleksordningen multiplikationer. Det finns olika FFT-algoritmer med egenskaper som passar för olika definitionsmängder. En av de vanligaste algoritmerna är där radix-2 DIT är det vanligaste fallet. La transformation de Fourier rapide (sigle anglais : FFT ou fast Fourier transform) est un algorithme de calcul de la transformation de Fourier discrète (TFD). Sa complexité varie en O(n log n) avec le nombre n de points, alors que la complexité de l’algorithme « naïf » s'exprime en O(n2). Ainsi, pour n = 1 024, le temps de calcul de l'algorithme rapide peut être 100 fois plus court que le calcul utilisant la formule de définition de la TFD. Быстрое преобразование Фурье (БПФ, FFT) — алгоритм ускоренного вычисления дискретного преобразования Фурье, позволяющий получить результат за время, меньшее чем (требуемого для прямого, поформульного вычисления). Иногда под быстрым преобразованием Фурье понимается один из алгоритмов, называемый алгоритмом прореживания по частоте — времени, имеющий сложность . Алгоритм применим к любым коммутативным ассоциативным кольцам с единицей, чаще применяют к полю комплексных чисел (c ) и к кольцам вычетов (которым, в частности, является компьютерный целый тип). Transformasi Fourier cepat (Bahasa Inggris: Fast Fourier Transform, biasa disingkat FFT) adalah suatu algoritme untuk menghitung transformasi Fourier diskrit (Bahasa Inggris: Discrete Fourier Transform, DFT) dengan cepat dan efisien. Transformasi Fourier Cepat diterapkan dalam beragam bidang, mulai dari , memecahkan persamaan diferensial parsial, dan untuk algoritme untuk mengalikan bilangan bulat besar. Misalkan ''x0, ...., xN-1 merupakan bilangan kompleks. Transformasi Fourier Diskret didefinisikan oleh rumus: Algoritme FFT yang paling awal dan karena itu paling populer adalah Rychlá Fourierova transformace (Fast Fourier transform, zkratkou FFT) je efektivní algoritmus pro spočtení diskrétní Fourierovy transformace (DFT) a její inverze. FFT je velmi důležitá v mnoha oblastech, od digitálního zpracování signálu a řešení parciálních diferenciálních rovnic až po rychlé násobení velkých celých čísel. Tento článek popisuje některé z mnoha algoritmů, více informací o samotné transformaci, jejích vlastnostech a aplikacích najdete v článku diskrétní Fourierova transformace. Nechť x0, ...., xN-1 jsou komplexní čísla. DFT je definována vzorcem In matematica, la trasformata di Fourier veloce, spesso abbreviata con FFT (dall'inglese Fast Fourier Transform), è un algoritmo ottimizzato per calcolare la trasformata discreta di Fourier (DFT) o la sua inversa. La FFT è utilizzata in una grande varietà di applicazioni, dall'elaborazione di segnali digitali alla soluzione di equazioni differenziali alle derivate parziali agli algoritmi per moltiplicare numeri interi di grandi dimensioni grazie al basso costo computazionale. A Transformada rápida de Fourier (em inglês fast Fourier transform, ou FFT) é um algoritmo eficiente para se calcular a Transformada discreta de Fourier (DFT) e a sua inversa. A análise de Fourier converte um sinal do seu domínio original para uma representação no domínio da frequência e vice-versa. Uma Transformada rápida de Fourier calcula rapidamente essas transformações fatorizando a matriz da Transformada discreta de Fourier em um produto de fatores esparsos (principalmente zero). Como resultado, ele consegue reduzir a complexidade de calcular a Transformada discreta de Fourier de O(n2), ou seja na ordem de n elevado ao quadrado, que surge se alguém simplesmente aplica a definição de Transformada discreta de Fourier, a O( n log n), onde n é o tamanho dos dados. 고속 푸리에 변환(高速 푸리에 變換, 영어: fast Fourier transform, FFT)은 이산 푸리에 변환(영어: discrete Fourier transform, DFT)과 그 역변환을 빠르게 수행하는 효율적인 알고리즘이다. FFT는 디지털 신호 처리에서 편미분 방정식의 근을 구하는 알고리즘에 이르기까지 많은 분야에서 사용한다. 이 복소수라고 가정할 때, DFT는 다음과 같이 정의한다. 이 식을 정의에 따라 계산하면 O(n2)의 연산이 필요하지만, FFT를 이용하면 O(n log n)의 연산만으로 가능하다. n이 합성수일 경우 그 소인수 분해를 이용하여 연산 횟수를 줄일 수는 있지만, FFT를 사용하면 n이 소수일 경우에도 O(n log n)번의 연산 횟수를 보장한다. In de numerieke wiskunde is een Fast Fourier transform (snelle fouriertransformatie, afgekort tot FFT) een algoritme voor het efficiënt berekenen van de discrete fouriertransformatie (DFT) van een discreet signaal waarvan de waarden bekend zijn in een eindig aantal equidistante punten. Terwijl directe berekening een efficiëntie heeft van , is de efficiëntie van een FFT . De daarmee gemoeide tijdwinst is aanzienlijk, zeker voor grote . 高速フーリエ変換(こうそくフーリエへんかん、英: fast Fourier transform, FFT)は、離散フーリエ変換(英: discrete Fourier transform, DFT)を計算機上で高速に計算するアルゴリズムである。高速フーリエ変換の逆変換を逆高速フーリエ変換(英: inverse fast Fourier transform, IFFT)と呼ぶ。 Die schnelle Fourier-Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der diskreten Fourier-Transformation (DFT). Mit ihr kann ein zeitdiskretes Signal in seine Frequenzanteile zerlegt und dadurch analysiert werden. Analog gibt es für die diskrete inverse Fourier-Transformation die inverse schnelle Fourier-Transformation (IFFT). Es kommen bei der IFFT die gleichen Algorithmen, aber mit konjugierten Koeffizienten zur Anwendung. A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. This operation is useful in many fields, but computing it directly from the definition is often too slow to be practical. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, it manages to reduce the complexity of computing the DFT from , which arises if one simply applies the definition of DFT, to , where is the data size. The difference
foaf:depiction
n40:Time_Signal_of_Five_Term_Cosine_Series.png
foaf:isPrimaryTopicOf
wikipedia-en:Fast_Fourier_transform
dbo:thumbnail
n40:Time_Signal_of_Five_Term_Cosine_Series.png?width=300
dct:subject
dbc:Discrete_transforms dbc:Digital_signal_processing dbc:FFT_algorithms
dbo:wikiPageID
11512
dbo:wikiPageRevisionID
985218283
dbo:wikiPageWikiLink
dbr:Dirichlet_series dbr:Numerical_analysis dbr:Root_mean_square dbr:MATLAB dbr:Coordinate_vector dbr:James_Cooley dbr:Convolution_theorem dbr:Convolution dbr:Group_theory dbr:Finite_field dbr:External_memory_algorithm dbr:Approximation_error dbr:Multidimensional_transform dbr:Multidimensional_discrete_convolution dbr:Hexagonal_fast_Fourier_transform dbr:Integrated_Performance_Primitives dbr:Prentice_Hall dbr:Approximation_theory dbr:Complex_number dbr:Root_of_unity dbr:Number_theory dbr:Academic_Press dbr:Chinese_remainder_theorem dbr:Matrix_decomposition dbr:Recurrence_relation dbr:Toeplitz_matrix dbr:Non-uniform_discrete_Fourier_transform dbr:Frank_Yates dbr:Gilbert_Strang dbr:John_F._Kennedy dbr:Even_and_odd_functions dbr:Shmuel_Winograd dbr:NumPy dbr:Matrix_(mathematics) dbr:Math_Kernel_Library dbr:Sparse_matrix dbr:Round-off_error dbr:Big_O_notation dbr:Recursion dbr:Polynomial dbr:Discrete_sine_transform dbr:Pipeline_(computing) dbr:MP3 dbr:R_(programming_language) dbr:G._C._Danielson dbr:CuFFT dbr:Coprime_integers dbr:JPEG dbr:McGraw-Hill_Education dbr:Additive_synthesis dbr:Generalized_distributive_law dbr:Generating_set_of_a_group dbr:Parallel_computing dbc:Discrete_transforms dbr:X-ray_crystallography dbr:Discrete_Fourier_transform_(general) dbr:Integer_factorization dbr:Quick_Fourier_transform_algorithm dbr:Composite_number dbr:Spectrum_analyzer dbr:Floating-point_arithmetic dbr:Fast_Fourier_sampling dbr:Fourier_transform_on_finite_groups dbr:Wavelet dbr:Divide-and-conquer_algorithm dbr:Computational_complexity_theory dbr:Numerical_stability dbr:Fast_Walsh–Hadamard_transform dbr:IEEE_Transactions_on_Signal_Processing dbr:Cornelius_Lanczos dbr:Cyclotomic_polynomial dbr:Frequency_domain dbr:GNU_Octave dbr:Fast_folding_algorithm dbr:MIT_Press dbr:Wilkinson_Microwave_Anisotropy_Probe dbr:Factorization dbr:Prime-factor_FFT_algorithm n45:DIT-FFT-butterfly.png dbr:Rader's_FFT_algorithm dbr:Fast_multipole_method dbr:Pairwise_summation dbr:Chirp_Z-transform dbr:LIGO dbr:Moving_Picture_Experts_Group dbr:Group_representation dbr:Thomas_J._Watson_Research_Center dbr:Spectral_music dbr:Sequence dbr:Time_series dbr:Prime_number dbr:John_Tukey dbr:C._Sidney_Burrus dbc:FFT_algorithms dbr:Trigonometric_tables dbr:OpenStax_CNX dbr:Asymptotically_optimal_algorithm dbr:Schönhage–Strassen_algorithm dbr:Graph_(discrete_mathematics) dbr:Proof_by_exhaustion dbr:Butterfly_diagram dbr:Odlyzko–Schönhage_algorithm dbr:Fourier_analysis dbr:3_Juno dbr:Discrete_cosine_transform dbr:Cooley–Tukey_FFT_algorithm dbr:Discrete_Hartley_transform dbr:Cache-oblivious_algorithm dbr:Christos_Papadimitriou dbr:Discrete_Fourier_transform dbr:Carl_Friedrich_Gauss dbr:Satisfiability_modulo_theories dbr:Overlap–add_method dbr:Goertzel_algorithm dbr:Cache_(computing) dbr:Floating-point_unit dbr:Overlap–save_method dbr:Quantum_Fourier_transform dbr:Fixed-point_arithmetic dbr:Victor_Pan dbr:Spectral_density_estimation dbr:FFTW dbr:Distributed_memory dbr:Transpose dbr:Group_(mathematics) dbr:DFT_matrix dbr:Mass_spectrometry dbc:Digital_signal_processing dbr:ALGLIB dbr:Wolfram_Mathematica dbr:FFTPACK dbr:Pitch_correction dbr:Central_processing_unit dbr:Joseph_Fourier dbr:Python_(programming_language) dbr:Markov_chain n45:FFT_of_Cosine_Summation_Function.svg dbr:Richard_Garwin dbr:Vector-radix_FFT_algorithm dbr:Cambridge_University_Press dbr:Power_of_two dbr:Bruun's_FFT_algorithm dbr:Steven_G._Johnson dbr:Split-radix_FFT_algorithm dbr:Trigonometric_functions dbr:Algorithm dbr:Twiddle_factor dbr:Julia_(programming_language) dbr:Circulant_matrix dbr:2_Pallas dbr:Institute_of_Electrical_and_Electronics_Engineers dbr:Spherical_harmonics
dbo:wikiPageExternalLink
n13: n15:FFT.html n18:30_Years_of_FFT_Analyzers_by_Sri_Welaratna.pdf n19:ffts n20:newsplit.pdf n20:links.html n24:fft.php n28: n35:Aggregate_modeling_-_Fast_Fourier_Transform_FFT_method.htm n36:FourierTransform.html n41:fft.html n43:article-10 n48:index.html%23pg=600 n49: n53: n55:fft.zip n56:fft-23703437 n57:fft.html n61:FFT_Basics_and_Case_Study_using_Multi-Instrument_D1002.pdf n64:fft.html
owl:sameAs
n5:त्वरित_फुरिअर_रूपान्तर dbpedia-it:Trasformata_di_Fourier_veloce dbpedia-fa:تبدیل_سریع_فوریه dbpedia-zh:快速傅里叶变换 n14:விரைவு_ஃபூரியே_உருமாற்றம் dbpedia-pt:Transformada_rápida_de_Fourier freebase:m.031v0 yago-res:Fast_Fourier_transform dbpedia-vi:Biến_đổi_Fourier_nhanh wikidata:Q623950 dbpedia-tr:Hızlı_Fourier_dönüşümü dbpedia-uk:Швидке_перетворення_Фур'є dbpedia-nl:Fast_Fourier_transform n31:4136070-9 n32:rdf dbpedia-az:Sürətli_Furye_çevirməsi dbpedia-sh:Brza_furijeova_transformacija dbpedia-ru:Быстрое_преобразование_Фурье dbpedia-fr:Transformation_de_Fourier_rapide dbpedia-ja:高速フーリエ変換 dbpedia-cs:Rychlá_Fourierova_transformace dbpedia-es:Transformada_rápida_de_Fourier dbpedia-pl:Szybka_transformacja_Fouriera n52:4ocyp dbpedia-ko:고속_푸리에_변환 dbpedia-de:Schnelle_Fourier-Transformation dbpedia-id:Transformasi_Fourier_cepat dbpedia-sr:Брза_Фуријеова_трансформација dbpedia-ca:Transformada_ràpida_de_Fourier dbpedia-da:Fast_Fourier_Transform dbpedia-ar:تحويل_فوريي_السريع dbpedia-sv:Snabb_fouriertransform dbpedia-he:FFT
dbp:wikiPageUsesTemplate
dbt:Mvar dbt:Radic dbt:Unsolved dbt:Short_description dbt:Nnbsp dbt:Reflist dbt:Main dbt:Use_American_English dbt:Redirect dbt:Fact dbt:Cite_book dbt:Cite_document dbt:Cite_journal
dbo:abstract
La transformation de Fourier rapide (sigle anglais : FFT ou fast Fourier transform) est un algorithme de calcul de la transformation de Fourier discrète (TFD). Sa complexité varie en O(n log n) avec le nombre n de points, alors que la complexité de l’algorithme « naïf » s'exprime en O(n2). Ainsi, pour n = 1 024, le temps de calcul de l'algorithme rapide peut être 100 fois plus court que le calcul utilisant la formule de définition de la TFD. C'est en 1965 que James Cooley et John Tukey publient l’article qui « lance » définitivement l'adoption massive de cette méthode en traitement du signal et dans les télécommunications. On a découvert par la suite que l'algorithme avait déjà été imaginé par Carl Friedrich Gauss en 1805, et adapté à plusieurs reprises (notamment par Lanczos en 1942) sous des formes différentes. Cet algorithme est couramment utilisé en traitement numérique du signal pour transformer des données discrètes du domaine temporel dans le domaine fréquentiel, en particulier dans les oscilloscopes numériques (les analyseurs de spectre utilisant plutôt des filtres analogiques, plus précis). Son efficacité permet de réaliser des filtrages en modifiant le spectre et en utilisant la transformation inverse (filtre à réponse impulsionnelle finie). Il est également à la base des algorithmes de multiplication rapide (Schönhage et Strassen, 1971), et des techniques de compression numérique ayant mené au format d'image JPEG (1991). La Transformada rápida de Fourier, conocida por la abreviatura FFT (del inglés Fast Fourier Transform) es un algoritmo eficiente que permite calcular la transformada de Fourier discreta (DFT) y su inversa. La FFT es de gran importancia en una amplia variedad de aplicaciones, desde el tratamiento digital de señales y filtrado digital en general a la resolución de ecuaciones en derivadas parciales o los algoritmos de multiplicación rápida de grandes enteros. Cuando se habla del tratamiento digital de señales, el algoritmo FFT impone algunas limitaciones en la señal y en el espectro resultante ya que la señal muestreada y que se va a transformar debe consistir de un número de muestras igual a una potencia de dos. La mayoría de los analizadores de FFT permiten la transformación de 512, 1024, 2048 o 4096 muestras. El rango de frecuencias cubierto por el análisis FFT depende de la cantidad de muestras recogidas y de la proporción de muestreo. La transformada rápida de Fourier es de importancia fundamental en el análisis matemático y ha sido objeto de numerosos estudios. La aparición de un algoritmo eficaz para esta operación fue un hito en la historia de la informática. A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. This operation is useful in many fields, but computing it directly from the definition is often too slow to be practical. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse (mostly zero) factors. As a result, it manages to reduce the complexity of computing the DFT from , which arises if one simply applies the definition of DFT, to , where is the data size. The difference in speed can be enormous, especially for long data sets where N may be in the thousands or millions. In the presence of round-off error, many FFT algorithms are much more accurate than evaluating the DFT definition directly or indirectly. There are many different FFT algorithms based on a wide range of published theories, from simple complex-number arithmetic to group theory and number theory. Fast Fourier transforms are widely used for applications in engineering, music, science, and mathematics. The basic ideas were popularized in 1965, but some algorithms had been derived as early as 1805. In 1994, Gilbert Strang described the FFT as "the most important numerical algorithm of our lifetime", and it was included in Top 10 Algorithms of 20th Century by the IEEE magazine Computing in Science & Engineering. The best-known FFT algorithms depend upon the factorization of N, but there are FFTs with O(N log N) complexity for all N, even for prime N. Many FFT algorithms only depend on the fact that is an N-th primitive root of unity, and thus can be applied to analogous transforms over any finite field, such as number-theoretic transforms. Since the inverse DFT is the same as the DFT, but with the opposite sign in the exponent and a 1/N factor, any FFT algorithm can easily be adapted for it. تحويل فوريي السريع (Fast Fourier Transformation) هي خوارزمية تمكن من حساب قيمة تحويل فوريي المتقطع بسرعة. تعود سرعة هذه الخوارزمية إلى أنها لا تقوم بحساب الأجزاء التي يساوي مجموعها صفرا في تحويل فوريي المتقطع. وتنسب الخوارزمية إلى جيمس كولي James W. Cooley John W. Tukey اللذان قاما بنشر الخوارزمية سنة 1965 وذلك بالصيغة المعروفة اليوم، إلا أن العالم الألماني كارل فريدرش غاوس قام بصياغة خوارزمية شبيهة سنة 1805 واستعملها في حساب مجرى المذنبات بالاس وجونو. كما تم تطوير بعض الحالات الخاصة من الخوارزمية قبل اكتشاف توكي لها (من قبل غود سنة 1960). Быстрое преобразование Фурье (БПФ, FFT) — алгоритм ускоренного вычисления дискретного преобразования Фурье, позволяющий получить результат за время, меньшее чем (требуемого для прямого, поформульного вычисления). Иногда под быстрым преобразованием Фурье понимается один из алгоритмов, называемый алгоритмом прореживания по частоте — времени, имеющий сложность . Алгоритм применим к любым коммутативным ассоциативным кольцам с единицей, чаще применяют к полю комплексных чисел (c ) и к кольцам вычетов (которым, в частности, является компьютерный целый тип). A Transformada rápida de Fourier (em inglês fast Fourier transform, ou FFT) é um algoritmo eficiente para se calcular a Transformada discreta de Fourier (DFT) e a sua inversa. A análise de Fourier converte um sinal do seu domínio original para uma representação no domínio da frequência e vice-versa. Uma Transformada rápida de Fourier calcula rapidamente essas transformações fatorizando a matriz da Transformada discreta de Fourier em um produto de fatores esparsos (principalmente zero). Como resultado, ele consegue reduzir a complexidade de calcular a Transformada discreta de Fourier de O(n2), ou seja na ordem de n elevado ao quadrado, que surge se alguém simplesmente aplica a definição de Transformada discreta de Fourier, a O( n log n), onde n é o tamanho dos dados. As Transformadas rápidas de Fourier são de grande importância em uma vasta gama de aplicações, de Processamento digital de sinais para a resolução de equações diferenciais parciais a algoritmos para multiplicação de grandes inteiros. Transformadas rápidas de Fourier são amplamente utilizadas para aplicações diversas em engenharia, ciência e matemática. As idéias básicas foram popularizadas em 1965, mas alguns algoritmos foram obtidos em 1805. Em 1994, Gilbert Strang descreveu a Transformada rápida de Fourier como "O algoritmo numérico mais importante da nossa vida." e foi incluída no Top 10 Algorithms of 20th Century pela revista IEEE Computing in Science & Engineering. Die schnelle Fourier-Transformation (englisch fast Fourier transform, daher meist FFT abgekürzt) ist ein Algorithmus zur effizienten Berechnung der diskreten Fourier-Transformation (DFT). Mit ihr kann ein zeitdiskretes Signal in seine Frequenzanteile zerlegt und dadurch analysiert werden. Analog gibt es für die diskrete inverse Fourier-Transformation die inverse schnelle Fourier-Transformation (IFFT). Es kommen bei der IFFT die gleichen Algorithmen, aber mit konjugierten Koeffizienten zur Anwendung. Die FFT hat zahlreiche Anwendungen (siehe auch ) im Bereich der Ingenieurwissenschaften, der Naturwissenschaften und der angewandten Mathematik. Außerdem kommt sie in Mobilfunktechnologien wie UMTS und LTE und bei der drahtlosen Datenübertragung zum Einsatz, etwa in der WLAN-Funknetztechnik. Die FFT gehört zu den Teile-und-herrsche-Verfahren, sodass – im Gegensatz zur direkten Berechnung – zuvor berechnete Zwischenergebnisse wiederverwendet und dadurch arithmetische Rechenoperationen eingespart werden können. Das bekannteste Verfahren wird James Cooley und John W. Tukey zugeschrieben, die es 1965 veröffentlichten. Genau genommen wurde eine Form des Algorithmus bereits 1805 von Carl Friedrich Gauß entworfen, der ihn zur Berechnung der Flugbahnen der Asteroiden (2) Pallas und (3) Juno verwendete. Zum ersten Mal publiziert wurde eine Variante des Algorithmus von Carl Runge im Jahre 1903 und 1905. Darüber hinaus wurden eingeschränkte Formen des Algorithmus mehrfach vor Cooley und Tukey entwickelt, so z. B. von Irving John Good (1960). Nach Cooley und Tukey hat es darüber hinaus zahlreiche Verbesserungsvorschläge und Variationen gegeben, so etwa von , und . In matematica, la trasformata di Fourier veloce, spesso abbreviata con FFT (dall'inglese Fast Fourier Transform), è un algoritmo ottimizzato per calcolare la trasformata discreta di Fourier (DFT) o la sua inversa. La FFT è utilizzata in una grande varietà di applicazioni, dall'elaborazione di segnali digitali alla soluzione di equazioni differenziali alle derivate parziali agli algoritmi per moltiplicare numeri interi di grandi dimensioni grazie al basso costo computazionale. Швидке́ перетво́рення Фур'є́ (часто FFT від англ. Fast Fourier Transform) — швидкий алгоритм обчислення дискретного перетворення Фур'є. Якщо для прямого обчислення дискретного перетворення Фур'є з N точок даних потрібно O(N 2) арифметичних операцій, то FFT дозволяє обчислити такий же результат використовуючи O(N log N) операцій. Алгоритм FFT часто використовується для цифрової обробки сигналів для перетворення дискретних даних з часового у частотний діапазон. 快速傅里叶变换(英語:Fast Fourier Transform, FFT),是快速计算序列的离散傅里叶变换(DFT)或其逆变换的方法。傅里叶分析将信号从原始域(通常是时间或空间)转换到頻域的表示或者逆过来转换。FFT会通过把DFT矩阵分解为稀疏(大多为零)因子之积来快速计算此类变换。 因此,它能够将计算DFT的复杂度从只用DFT定义计算需要的 ,降低到 ,其中 为数据大小。 快速傅里叶变换广泛的应用于工程、科学和数学领域。这里的基本思想在1965年才得到普及,但早在1805年就已推导出来。 1994年美國數學家把FFT描述为“我们一生中最重要的数值算法”,它还被IEEE科学与工程计算期刊列入20世纪十大算法。 Rychlá Fourierova transformace (Fast Fourier transform, zkratkou FFT) je efektivní algoritmus pro spočtení diskrétní Fourierovy transformace (DFT) a její inverze. FFT je velmi důležitá v mnoha oblastech, od digitálního zpracování signálu a řešení parciálních diferenciálních rovnic až po rychlé násobení velkých celých čísel. Tento článek popisuje některé z mnoha algoritmů, více informací o samotné transformaci, jejích vlastnostech a aplikacích najdete v článku diskrétní Fourierova transformace. Nechť x0, ...., xN-1 jsou komplexní čísla. DFT je definována vzorcem Přímé vyhodnocení těchto sum by zabralo O(n2) aritmetických operací. FFT naproti tomu poskytuje složitost pouze O(n log n) operací. Obecně jsou FFT algoritmy založeny na faktorizaci N, nicméně existují i FFT algoritmy se složitostí O(n log n) pro všechna N, tedy i pro prvočísla. Jelikož je inverzní DFT stejná jako DFT jen s rozdílem opačného znaménka v exponentu a koeficientu 1/N, kterýkoli algoritmus je možné snadno modifikovat i pro počítání inverzní DFT. 고속 푸리에 변환(高速 푸리에 變換, 영어: fast Fourier transform, FFT)은 이산 푸리에 변환(영어: discrete Fourier transform, DFT)과 그 역변환을 빠르게 수행하는 효율적인 알고리즘이다. FFT는 디지털 신호 처리에서 편미분 방정식의 근을 구하는 알고리즘에 이르기까지 많은 분야에서 사용한다. 이 복소수라고 가정할 때, DFT는 다음과 같이 정의한다. 이 식을 정의에 따라 계산하면 O(n2)의 연산이 필요하지만, FFT를 이용하면 O(n log n)의 연산만으로 가능하다. n이 합성수일 경우 그 소인수 분해를 이용하여 연산 횟수를 줄일 수는 있지만, FFT를 사용하면 n이 소수일 경우에도 O(n log n)번의 연산 횟수를 보장한다. En snabb fouriertransform, på engelska fast Fourier transform (FFT), är en effektiv algoritm för att beräkna en diskret, begränsad fouriertransform. Vanligtvis kräver en diskret fouriertransform av en signal med sampelpunkter multiplikationer, men med hjälp av FFT sjunker denna siffra till i storleksordningen multiplikationer. Det finns olika FFT-algoritmer med egenskaper som passar för olika definitionsmängder. En av de vanligaste algoritmerna är där radix-2 DIT är det vanligaste fallet. Szybka transformacja Fouriera (ang. Fast Fourier Transform, FFT) – algorytm wyznaczania dyskretnej transformaty Fouriera oraz transformaty do niej odwrotnej. Czasem, w odniesieniu do tej metody, używane jest też określenie szybka transformata Fouriera, które jednak nie jest prawidłowe, gdyż pojęcie transformacja oznacza przekształcenie, a transformata jest wynikiem tego przekształcenia. Niech będą liczbami zespolonymi, wtedy dyskretna transformata Fouriera jest określona wzorem: Obliczanie sum za pomocą powyższego wzoru wymaga wykonania operacji (zob. asymptotyczne tempo wzrostu). Algorytmy (jak algorytm Cooleya-Tukeya) obliczające szybką transformację Fouriera bazują na metodzie dziel i zwyciężaj, rekurencyjnie dzieląc transformatę wielkości na transformaty wielkości i z wykorzystaniem operacji mnożenia. Najpopularniejszą wersją algorytmu FFT jest FFT o podstawie 2. Jest on bardzo efektywny pod względem czasu realizacji, jednak wektor próbek wejściowych (spróbkowany sygnał) musi mieć długość gdzie to pewna liczba naturalna. Wynik otrzymuje się na drodze schematycznych przekształceń, opartych o tak zwane struktury motylkowe. Złożoność obliczeniowa szybkiej transformacji Fouriera wynosi w odróżnieniu od algorytmu wynikającego wprost ze wzoru określającego dyskretną transformatę Fouriera. Dzięki szybkiej transformacie Fouriera praktycznie możliwe stało się cyfrowe przetwarzanie sygnałów (DSP), a także zastosowanie dyskretnych transformat kosinusowych (DCT) do kompresji danych audio-wideo (JPEG, MP3, XviD itd.). 高速フーリエ変換(こうそくフーリエへんかん、英: fast Fourier transform, FFT)は、離散フーリエ変換(英: discrete Fourier transform, DFT)を計算機上で高速に計算するアルゴリズムである。高速フーリエ変換の逆変換を逆高速フーリエ変換(英: inverse fast Fourier transform, IFFT)と呼ぶ。 Transformasi Fourier cepat (Bahasa Inggris: Fast Fourier Transform, biasa disingkat FFT) adalah suatu algoritme untuk menghitung transformasi Fourier diskrit (Bahasa Inggris: Discrete Fourier Transform, DFT) dengan cepat dan efisien. Transformasi Fourier Cepat diterapkan dalam beragam bidang, mulai dari , memecahkan persamaan diferensial parsial, dan untuk algoritme untuk mengalikan bilangan bulat besar. Misalkan ''x0, ...., xN-1 merupakan bilangan kompleks. Transformasi Fourier Diskret didefinisikan oleh rumus: Menghitung ini secara langsung memerlukan operasi aritmetika sebanyak O(N2). Sebuah algoritme FFT hanya memerlukan operasi sebanyak O(N log N) untuk menghitung deret yang sama. Secara umum algoritme tersebut tergantung pada N. Setiap algoritme FFT, dengan penyesuaian, dapat diterapkan pula untuk menghitung DFT invers. Ini karena DFT invers adalah sama dengan DFT, namun dengan tanda eksponen berlawanan dan dikalikan dengan faktor 1/N. Algoritme FFT yang paling awal dan karena itu paling populer adalah In de numerieke wiskunde is een Fast Fourier transform (snelle fouriertransformatie, afgekort tot FFT) een algoritme voor het efficiënt berekenen van de discrete fouriertransformatie (DFT) van een discreet signaal waarvan de waarden bekend zijn in een eindig aantal equidistante punten. Terwijl directe berekening een efficiëntie heeft van , is de efficiëntie van een FFT . De daarmee gemoeide tijdwinst is aanzienlijk, zeker voor grote . Het algoritme is ontwikkeld door en John Tukey in 1965, en komt er in zijn oorspronkelijke vorm op neer dat een fouriertransformatie met lengte wordt gesplitst in twee transformaties met lengte , waarbij gebruikgemaakt wordt van de periodiciteit en symmetrie in de sinus en cosinus. Door deze opsplitsing recursief toe te passen ontstaat een verbetering van de orde . Voor bijvoorbeeld is dat al een factor 630. Voor de toepassing van een dergelijke recursie is vereist dat een macht van 2 is. Later is deze methode gegeneraliseerd naar een ontbinding in willekeurige priemfactoren, waardoor een meer algemene toepasbaarheid ontstond. Gebruik van grote priemfactoren kan echter zeer nadelige gevolgen hebben voor de rekentijd. Voor praktische toepassing zoals in signaalanalyse heeft de beperking tot machten van twee nauwelijks gevolgen. Wanneer een 3-dimensionale FFT wordt gebruikt, zoals in de kristallografie, kan het echter leiden tot bijna 8 keer meer geheugengebruik en 24 keer meer rekentijd dan strikt noodzakelijk. La transformada ràpida de Fourier (o FFT, de l'anglès Fast Fourier transform), no és més que una forma molt ràpida i eficient de calcular la transformada discreta de Fourier (DFT) d'un senyal discret i la seva inversa, la (IDFT). Es calcula de forma computacional a través d'un determinat algorisme. En termes d'eficiència, la DFT té un cost temporal d'O(n²) i la FFT d'O(nlog n). En transformades de poques mostres gairebé no s'aprecia la diferència. On sí que es pot apreciar és, per exemple, en una transformada de 1024 mostres. Fent la DFT es necessitarien aproximadament operacions i fent la FFT, en canvi, unes 5000. Per poder aplicar la transformada ràpida de Fourier, es necessiten dues condicions indispensables: que el senyal discret a transformar sigui periòdic i que el nombre de mostres sigui de l'ordre de , amb n essent un nombre enter positiu. Com més gran sigui n, millor serà la transformada. Generalment, n sol ser igual a 10. D'aquí ve la seva importància pel desenvolupament de les telecomunicacions. Operacions que abans de la FFT podien desestimar-se per la seva complexitat, van començar-se a fer utilitzant aquesta nova transformada ràpida de Fourier. La transformada ràpida de Fourier és d'importància fonamental en l'anàlisi matemàtica i ha estat objecte de nombrosos estudis. L'aparició d'un algorisme eficaç per a aquesta operació va ser una pedra angular en la història de la informàtica. Les principals aplicacions de la transformada ràpida de Fourier són múltiples. És la base de moltes operacions fonamentals que es troben en el , on té una àmplia utilització. També és important en el i la resolució d'equacions diferencials, entre d'altres aplicacions. A més, proporciona un mitjà convenient per millorar el rendiment dels algorismes per a un conjunt de problemes aritmètics comuns.
prov:wasDerivedFrom
wikipedia-en:Fast_Fourier_transform?oldid=985218283&ns=0
dbo:wikiPageLength
60230