Rader's algorithm (1968), named for Charles M. Rader of MIT Lincoln Laboratory, is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re-expressing the DFT as a cyclic convolution (the other algorithm for FFTs of prime sizes, Bluestein's algorithm, also works by rewriting the DFT as a convolution). Since Rader's algorithm only depends upon the periodicity of the DFT kernel, it is directly applicable to any other transform (of prime order) with a similar property, such as a number-theoretic transform or the discrete Hartley transform.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - レーダーのFFTアルゴリズム (ja)
- Rader's FFT algorithm (en)
- 雷德演算法 (zh)
|
| rdfs:comment
| - 雷德演算法（英語：Rader's algorithm）是一種於1968年由麻省理工學院林肯實驗室之查爾斯·M·雷德（Charles M. Rader）提出的快速傅立葉轉換演算法。當訊號的資料點數量為質數時，此演算法可藉由將離散傅立葉轉換重新表示為圓周摺積，快速計算出該訊號之離散傅立葉轉換結果。另一種稱為布魯斯坦演算法的作法也是透過類似的方式將離散傅立葉轉換改寫為摺積完成轉換，且同樣限制訊號長度需為質數。 由於雷德演算法之運作原理只依賴於具有週期性的離散傅立葉轉換核，故它也可直接套用於其它具有類似特性的轉換（惟訊號長度需為質數），例如數論轉換或離散哈特利轉換。 當所欲轉換的訊號資料皆為實數時，可透過重新索引或排列將原轉換拆成兩個長度為一半的實數循環摺積，如此稍微修改後的雷德演算法可進一步使運算時間減半；另一種快速計算實數訊號之離散傅立葉轉換的方法則是使用離散哈特利轉換。 進一步延伸了雷德演算法，使其也可用於長度為質數之次方數 的訊號之離散傅立葉轉換；也因此，雷德演算法亦可被視為威諾格拉德快速傅立葉轉換演算法（亦稱為乘法性傅立葉轉換演算法）的特例之一，其中後者可用的訊號長度範圍較廣。然而，當訊號長度為合數（如質數之次方數）時，使用庫利－圖基快速傅立葉轉換演算法更加簡單且實作上也較容易，故雷德演算法一般只用於庫利－圖基演算法之遞迴拆解下較大質數之基本情況。 (zh)
- Rader's algorithm (1968), named for Charles M. Rader of MIT Lincoln Laboratory, is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re-expressing the DFT as a cyclic convolution (the other algorithm for FFTs of prime sizes, Bluestein's algorithm, also works by rewriting the DFT as a convolution). Since Rader's algorithm only depends upon the periodicity of the DFT kernel, it is directly applicable to any other transform (of prime order) with a similar property, such as a number-theoretic transform or the discrete Hartley transform. (en)
- レーダーのアルゴリズムとは、MITのリンカーン研究所のチャールズ・M・レーダーにより考案された高速フーリエ変換のアルゴリズムである。このアルゴリズムではサイズが素数の離散フーリエ変換（DFT）を巡回畳み込みに置き換えることで計算コストを減らす（Bluestein のアルゴリズムもまたDFTを巡回畳み込みと置き換えるアルゴリズムである)。 レーダーのアルゴリズムはDFTカーネルの周期性のみを利用しているので、このアルゴリズムは同様の特徴をもつ（素数サイズの） やに対しても適用することができる。 このアルゴリズムはデータの並び変えを少し変更し、実数データに対して更なる高速化が可能である。また、実数データについてに対する別の最適化として、 によって示された離散ハートレイ変換を用いたアルゴリズムがある。 (ja)
|
| foaf:depiction
| |
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| thumbnail
| |
| has abstract
| - Rader's algorithm (1968), named for Charles M. Rader of MIT Lincoln Laboratory, is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re-expressing the DFT as a cyclic convolution (the other algorithm for FFTs of prime sizes, Bluestein's algorithm, also works by rewriting the DFT as a convolution). Since Rader's algorithm only depends upon the periodicity of the DFT kernel, it is directly applicable to any other transform (of prime order) with a similar property, such as a number-theoretic transform or the discrete Hartley transform. The algorithm can be modified to gain a factor of two savings for the case of DFTs of real data, using a slightly modified re-indexing/permutation to obtain two half-size cyclic convolutions of real data; an alternative adaptation for DFTs of real data uses the discrete Hartley transform. Winograd extended Rader's algorithm to include prime-power DFT sizes , and today Rader's algorithm is sometimes described as a special case of Winograd's FFT algorithm, also called the multiplicative Fourier transform algorithm (Tolimieri et al., 1997), which applies to an even larger class of sizes. However, for composite sizes such as prime powers, the Cooley–Tukey FFT algorithm is much simpler and more practical to implement, so Rader's algorithm is typically only used for large-prime base cases of Cooley–Tukey's recursive decomposition of the DFT. (en)
- レーダーのアルゴリズムとは、MITのリンカーン研究所のチャールズ・M・レーダーにより考案された高速フーリエ変換のアルゴリズムである。このアルゴリズムではサイズが素数の離散フーリエ変換（DFT）を巡回畳み込みに置き換えることで計算コストを減らす（Bluestein のアルゴリズムもまたDFTを巡回畳み込みと置き換えるアルゴリズムである)。 レーダーのアルゴリズムはDFTカーネルの周期性のみを利用しているので、このアルゴリズムは同様の特徴をもつ（素数サイズの） やに対しても適用することができる。 このアルゴリズムはデータの並び変えを少し変更し、実数データに対して更なる高速化が可能である。また、実数データについてに対する別の最適化として、 によって示された離散ハートレイ変換を用いたアルゴリズムがある。 ウィノグラードはレーダーのアルゴリズムを拡張し、素数の冪乗のサイズのDFTに適用できるアルゴリズムを考案した (ja)
- 雷德演算法（英語：Rader's algorithm）是一種於1968年由麻省理工學院林肯實驗室之查爾斯·M·雷德（Charles M. Rader）提出的快速傅立葉轉換演算法。當訊號的資料點數量為質數時，此演算法可藉由將離散傅立葉轉換重新表示為圓周摺積，快速計算出該訊號之離散傅立葉轉換結果。另一種稱為布魯斯坦演算法的作法也是透過類似的方式將離散傅立葉轉換改寫為摺積完成轉換，且同樣限制訊號長度需為質數。 由於雷德演算法之運作原理只依賴於具有週期性的離散傅立葉轉換核，故它也可直接套用於其它具有類似特性的轉換（惟訊號長度需為質數），例如數論轉換或離散哈特利轉換。 當所欲轉換的訊號資料皆為實數時，可透過重新索引或排列將原轉換拆成兩個長度為一半的實數循環摺積，如此稍微修改後的雷德演算法可進一步使運算時間減半；另一種快速計算實數訊號之離散傅立葉轉換的方法則是使用離散哈特利轉換。 進一步延伸了雷德演算法，使其也可用於長度為質數之次方數 的訊號之離散傅立葉轉換；也因此，雷德演算法亦可被視為威諾格拉德快速傅立葉轉換演算法（亦稱為乘法性傅立葉轉換演算法）的特例之一，其中後者可用的訊號長度範圍較廣。然而，當訊號長度為合數（如質數之次方數）時，使用庫利－圖基快速傅立葉轉換演算法更加簡單且實作上也較容易，故雷德演算法一般只用於庫利－圖基演算法之遞迴拆解下較大質數之基本情況。 (zh)
|
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is Wikipage redirect
of | |
| is Wikipage disambiguates
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
