Butterfly diagram (original) (raw)
蝶形結或蝶形網路（英語：Butterfly diagram）是快速傅立葉轉換演算法中的組成單位，將原本的較大點數的離散傅立葉運算，拆成較小點數的離散傅立葉運算組合，反之亦然(將原本點數較小的離散傅立葉運算，組合成較大點數的離散傅立葉運算組合)，其中蝶形結架構的n點離散傅立葉轉換並不一定需要滿足為點數 n = 2 p 的條件。蝶形結其名來自於底數為2的信號流成圖形似蝴蝶外觀(圖表一)。這個詞最早是由1969年一份MIT的技術性報告提到，類似的架構也出現於維特比演算法中，用於尋找隱匿層中最有可能的序列。 而蝶形結此詞彙仍最常使用於庫利－圖基快速傅立葉變換演算法中，利用遞迴的方式將n點離散傅立葉運算中的n點輸入分解為 n = r x m，轉換輸入信號為r點的m組信號分別進行r點離散傅立葉運算(換句话說就是r點DFT做m次)，而r點的離散傅立葉運算基本上為轉換後的輸入信號乘上旋轉因子以蝶形結架構做加法運算。(前述為時域抽取法的運算方式，逆向操作先進行蝶形結架構做加法運算，再乘上旋轉因子，則為頻域抽取法運算方式)
| Property | Value |
|---|---|
| dbo:abstract | In the context of fast Fourier transform algorithms, a butterfly is a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa (breaking a larger DFT up into subtransforms). The name "butterfly" comes from the shape of the data-flow diagram in the radix-2 case, as described below. The earliest occurrence in print of the term is thought to be in a 1969 MIT technical report. The same structure can also be found in the Viterbi algorithm, used for finding the most likely sequence of hidden states. Most commonly, the term "butterfly" appears in the context of the Cooley–Tukey FFT algorithm, which recursively breaks down a DFT of composite size n = rm into r smaller transforms of size m where r is the "radix" of the transform. These smaller DFTs are then combined via size-r butterflies, which themselves are DFTs of size r (performed m times on corresponding outputs of the sub-transforms) pre-multiplied by roots of unity (known as twiddle factors). (This is the "decimation in time" case; one can also perform the steps in reverse, known as "decimation in frequency", where the butterflies come first and are post-multiplied by twiddle factors. See also the Cooley–Tukey FFT article.) (en) Ein Schmetterlingsgraph (englisch butterfly graph) zeigt, wie aus der Grundfunktion (der Schmetterling) der Fourier-Transformation ein schneller Fouriertransformator (FFT, schnelle Fourier-Transformation) aufgebaut wird. Der Begriff Schmetterling leitet sich im Datenflussdiagramm von der Darstellung der beiden Dreiecke ab, die bei der Darstellung des Grundelementes (time decimation butterfly) der schnellen Fouriertransformation entstehen. Ein Schmetterling bewerkstelligt (jeweils komplex) eine Multiplikation, eine Subtraktion und eine Addition im Rahmen des FFT-Algorithmus von Cooley und Tukey. Durch die Linien wird angezeigt, dass die beiden Ausgänge und von den beiden Eingängen und abhängen. Im einfachsten Fall (radix-2 Cooley und Tukey FFT-Algorithmus) besteht der Schmetterlingsgraph nur aus den dargestellten zwei Ein- und Ausgängen: Der allgemeine Fall mit Eingängen resultiert in einer Anzahl von an Schmetterlingsgraphen mit den Bezügen: mit , dem Index und der imaginären Einheit . (de) Бабочка — элементарный шаг в алгоритме Кули-Тюки (англ. Cooley–Tukey FFT) вычисления быстрого преобразования Фурье. Время работы шага Бабочка определяет длительность вычисления преобразования Фурье. В простейшем варианте (Radix-2 butterfly) является двухточечным преобразованием. Формула для вычисления «Бабочки»: Обозначения: , – исходные точки; , – точки результата, – комплексный коэффициент. Для БПФ данных размером , требуется произвести вычислений операции 2-Radix «Бабочка». Иногда используются операции бабочка более высокого порядка: Radix-4, Radix-8. Radix-4 является примерно на 20% более эффективным для преобразования Фурье большого количества данных. Операция большего порядка чем 8 практически не используется из-за незначительных приростов производительности и трудностей в реализации (ресурсоемкости). Сходная структура может применяться в реализациях алгоритма Витерби (операция ACS - Add-Compare-Select). (ru) 蝶形結或蝶形網路（英語：Butterfly diagram）是快速傅立葉轉換演算法中的組成單位，將原本的較大點數的離散傅立葉運算，拆成較小點數的離散傅立葉運算組合，反之亦然(將原本點數較小的離散傅立葉運算，組合成較大點數的離散傅立葉運算組合)，其中蝶形結架構的n點離散傅立葉轉換並不一定需要滿足為點數 n = 2 p 的條件。蝶形結其名來自於底數為2的信號流成圖形似蝴蝶外觀(圖表一)。這個詞最早是由1969年一份MIT的技術性報告提到，類似的架構也出現於維特比演算法中，用於尋找隱匿層中最有可能的序列。 而蝶形結此詞彙仍最常使用於庫利－圖基快速傅立葉變換演算法中，利用遞迴的方式將n點離散傅立葉運算中的n點輸入分解為 n = r x m，轉換輸入信號為r點的m組信號分別進行r點離散傅立葉運算(換句话說就是r點DFT做m次)，而r點的離散傅立葉運算基本上為轉換後的輸入信號乘上旋轉因子以蝶形結架構做加法運算。(前述為時域抽取法的運算方式，逆向操作先進行蝶形結架構做加法運算，再乘上旋轉因子，則為頻域抽取法運算方式) (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Butterfly-FFT.png?width=300 |
| dbo:wikiPageExternalLink | http://www.cmlab.csie.ntu.edu.tw/cml/dsp/training/coding/transform/fft.html https://web.archive.org/web/20060423170713/http:/www.relisoft.com/science/Physics/fft.html |
| dbo:wikiPageID | 2707212 (xsd:integer) |
| dbo:wikiPageLength | 5977 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1111230153 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Root_of_unity dbr:Cooley–Tukey_FFT dbc:Diagrams dbr:Massachusetts_Institute_of_Technology dbr:Mathematical_diagram dbr:Cooley–Tukey_FFT_algorithm dbr:Composite_number dbr:Viterbi_algorithm dbr:Butterfly dbr:Fast_Fourier_transform dbr:Signal-flow_graph dbr:Recursion dbc:FFT_algorithms dbr:Zassenhaus_lemma dbr:Discrete_Fourier_transform dbr:Twiddle_factor dbr:File:Butterfly-FFT.png dbr:File:DIT-FFT-butterfly.svg |
| dbp:wikiPageUsesTemplate | dbt:About |
| dct:subject | dbc:Diagrams dbc:FFT_algorithms |
| rdf:type | yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:WikicatAlgorithms yago:WikicatFFTAlgorithms |
| rdfs:comment | 蝶形結或蝶形網路（英語：Butterfly diagram）是快速傅立葉轉換演算法中的組成單位，將原本的較大點數的離散傅立葉運算，拆成較小點數的離散傅立葉運算組合，反之亦然(將原本點數較小的離散傅立葉運算，組合成較大點數的離散傅立葉運算組合)，其中蝶形結架構的n點離散傅立葉轉換並不一定需要滿足為點數 n = 2 p 的條件。蝶形結其名來自於底數為2的信號流成圖形似蝴蝶外觀(圖表一)。這個詞最早是由1969年一份MIT的技術性報告提到，類似的架構也出現於維特比演算法中，用於尋找隱匿層中最有可能的序列。 而蝶形結此詞彙仍最常使用於庫利－圖基快速傅立葉變換演算法中，利用遞迴的方式將n點離散傅立葉運算中的n點輸入分解為 n = r x m，轉換輸入信號為r點的m組信號分別進行r點離散傅立葉運算(換句话說就是r點DFT做m次)，而r點的離散傅立葉運算基本上為轉換後的輸入信號乘上旋轉因子以蝶形結架構做加法運算。(前述為時域抽取法的運算方式，逆向操作先進行蝶形結架構做加法運算，再乘上旋轉因子，則為頻域抽取法運算方式) (zh) In the context of fast Fourier transform algorithms, a butterfly is a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa (breaking a larger DFT up into subtransforms). The name "butterfly" comes from the shape of the data-flow diagram in the radix-2 case, as described below. The earliest occurrence in print of the term is thought to be in a 1969 MIT technical report. The same structure can also be found in the Viterbi algorithm, used for finding the most likely sequence of hidden states. (en) Ein Schmetterlingsgraph (englisch butterfly graph) zeigt, wie aus der Grundfunktion (der Schmetterling) der Fourier-Transformation ein schneller Fouriertransformator (FFT, schnelle Fourier-Transformation) aufgebaut wird. Im einfachsten Fall (radix-2 Cooley und Tukey FFT-Algorithmus) besteht der Schmetterlingsgraph nur aus den dargestellten zwei Ein- und Ausgängen: Der allgemeine Fall mit Eingängen resultiert in einer Anzahl von an Schmetterlingsgraphen mit den Bezügen: mit , dem Index und der imaginären Einheit . (de) Бабочка — элементарный шаг в алгоритме Кули-Тюки (англ. Cooley–Tukey FFT) вычисления быстрого преобразования Фурье. Время работы шага Бабочка определяет длительность вычисления преобразования Фурье. В простейшем варианте (Radix-2 butterfly) является двухточечным преобразованием. Формула для вычисления «Бабочки»: Обозначения: , – исходные точки; , – точки результата, – комплексный коэффициент. Для БПФ данных размером , требуется произвести вычислений операции 2-Radix «Бабочка». Сходная структура может применяться в реализациях алгоритма Витерби (операция ACS - Add-Compare-Select). (ru) |
| rdfs:label | Schmetterlingsgraph (de) Butterfly diagram (en) Бабочка (БПФ) (ru) 蝶形结 (zh) |
| owl:sameAs | freebase:Butterfly diagram yago-res:Butterfly diagram wikidata:Butterfly diagram dbpedia-de:Butterfly diagram http://ml.dbpedia.org/resource/ബട്ടർഫ്ലൈ_ഡയഗ്രം dbpedia-ru:Butterfly diagram dbpedia-zh:Butterfly diagram https://global.dbpedia.org/id/X6qv |
| prov:wasDerivedFrom | wikipedia-en:Butterfly_diagram?oldid=1111230153&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/DIT-FFT-butterfly.svg wiki-commons:Special:FilePath/Butterfly-FFT.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Butterfly_diagram |
| is dbo:wikiPageDisambiguates of | dbr:Butterfly_(disambiguation) |
| is dbo:wikiPageRedirects of | dbr:Butterfly_(FFT_algorithm) |
| is dbo:wikiPageWikiLink of | dbr:Butterfly_(FFT_algorithm) dbr:Butterfly_(disambiguation) dbr:List_of_numerical_analysis_topics dbr:Mathematical_diagram dbr:Split-radix_FFT_algorithm dbr:Timeline_of_solar_astronomy dbr:Cooley–Tukey_FFT_algorithm dbr:1904_in_science dbr:Butterfly_network dbr:Fast_Fourier_transform dbr:Boolean_function dbr:Twiddle_factor |
| is foaf:primaryTopic of | wikipedia-en:Butterfly_diagram |
