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

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

Namespace Prefixes

PrefixIRI
dcthttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n13https://global.dbpedia.org/id/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
freebasehttp://rdf.freebase.com/ns/
n8http://infoscience.epfl.ch/record/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Prime-factor_FFT_algorithm
rdf:type
yago:Abstraction100002137 yago:YagoPermanentlyLocatedEntity yago:Procedure101023820 yago:Activity100407535 yago:Rule105846932 yago:Algorithm105847438 yago:WikicatFFTAlgorithms yago:PsychologicalFeature100023100 yago:Event100029378 yago:Act100030358
rdfs:label
互質因子算法 Алгоритм Гуда — Томаса Prime-factor FFT algorithm
rdfs:comment
互質因子算法（Prime-factor FFT algorithm, PFA），又稱為Good-Thomas算法，是一種快速傅立葉變換（FFT），把N = N1N2大小的離散傅立葉變換重新表示為N1 * N2大小的二維離散傅立葉變換，其中N1與N2需互質。變成N1和N2大小的傅立葉變換後，可以繼續遞迴使用PFA，或用其他快速傅立葉變換算法來計算。 較流行的Cooley-Tukey算法經由mixed-radix一般化後，也是把N = N1N2大小的離散傅立葉變換分割為N1和N2大小的轉換，但和互質因子算法 (PFA)作法並不相同，不應混淆。Cooley-Tukey算法的N1與N2不需互質，可以是任何整數。然而有個缺點是比PFA多出一些乘法，和單位根twiddle factors相乘。相對的，PFA的缺點則是N1與N2需互質 (例如N 是2次方就不適用)，而且要藉由中國剩餘定理來進行較複雜的re-indexing。互質因子算法 (PFA)可以和mixed-radix Cooley-Tukey算法相結合，前者將N 分解為互質的因數，後者則用在重複質因數上。 PFA也與nested Winograd FFT算法密切相關，後者使用更為精巧的二維摺積技巧分解成N1 * N2的轉換。因而一些較古老的論文把Winograd算法稱為PFA FFT。 Алгоритм Гуда — Томаса — алгоритм вычисления быстрого преобразования Фурье, применяющийся к последовательностям, длина которых равна произведению двух взаимно простых чисел. Алгоритм Гуда — Томаса не следует путать с алгоритмом Кули — Тьюки, где делители длины преобразования не обязаны быть взаимно простыми. Алгоритм Гуда — Томаса ограничен этим условием, а также задействует более сложную схему переиндексации, чем алгоритм Кули — Тьюки, но при этом не требует промежуточного умножения на комплексные множители и потому несколько проще с точки зрения вычислений. The prime-factor algorithm (PFA), also called the Good–Thomas algorithm (1958/1963), is a fast Fourier transform (FFT) algorithm that re-expresses the discrete Fourier transform (DFT) of a size N = N1N2 as a two-dimensional N1×N2 DFT, but only for the case where N1 and N2 are relatively prime. These smaller transforms of size N1 and N2 can then be evaluated by applying PFA recursively or by using some other FFT algorithm.
dct:subject
dbc:FFT_algorithms
dbo:wikiPageID
241490
dbo:wikiPageRevisionID
1117514792
dbo:wikiPageWikiLink
dbr:Euler's_totient_function dbr:Power_of_two dbr:Group_isomorphism dbr:Chinese_remainder_theorem dbr:Twiddle_factor dbr:Discrete_Fourier_transform dbr:Cyclic_group dbr:Winograd_FFT_algorithm dbr:Principal_root_of_unity dbr:Relatively_prime dbr:Automorphism dbr:Bluestein's_FFT_algorithm dbr:Fast_Fourier_transform dbr:Central_idempotent dbr:Recursion dbr:Tensor_product dbr:I._J._Good dbr:Algebra_homomorphism dbr:Rader's_FFT_algorithm dbc:FFT_algorithms dbr:Additive_group dbr:Tensor_product_of_algebras dbr:Cooley–Tukey_FFT_algorithm
dbo:wikiPageExternalLink
n8:59946
owl:sameAs
dbpedia-zh:互質因子算法 freebase:m.01k0zt wikidata:Q7243214 n13:4tUzC yago-res:Prime-factor_FFT_algorithm dbpedia-ru:Алгоритм_Гуда_—_Томаса
dbp:wikiPageUsesTemplate
dbt:Short_description dbt:Cite_journal dbt:JSTOR dbt:Use_American_English dbt:Reflist dbt:Cite_book
dbo:abstract
Алгоритм Гуда — Томаса — алгоритм вычисления быстрого преобразования Фурье, применяющийся к последовательностям, длина которых равна произведению двух взаимно простых чисел. Алгоритм Гуда — Томаса не следует путать с алгоритмом Кули — Тьюки, где делители длины преобразования не обязаны быть взаимно простыми. Алгоритм Гуда — Томаса ограничен этим условием, а также задействует более сложную схему переиндексации, чем алгоритм Кули — Тьюки, но при этом не требует промежуточного умножения на комплексные множители и потому несколько проще с точки зрения вычислений. The prime-factor algorithm (PFA), also called the Good–Thomas algorithm (1958/1963), is a fast Fourier transform (FFT) algorithm that re-expresses the discrete Fourier transform (DFT) of a size N = N1N2 as a two-dimensional N1×N2 DFT, but only for the case where N1 and N2 are relatively prime. These smaller transforms of size N1 and N2 can then be evaluated by applying PFA recursively or by using some other FFT algorithm. PFA should not be confused with the mixed-radix generalization of the popular Cooley–Tukey algorithm, which also subdivides a DFT of size N = N1N2 into smaller transforms of size N1 and N2. The latter algorithm can use any factors (not necessarily relatively prime), but it has the disadvantage that it also requires extra multiplications by roots of unity called twiddle factors, in addition to the smaller transforms. On the other hand, PFA has the disadvantages that it only works for relatively prime factors (e.g. it is useless for power-of-two sizes) and that it requires more complicated re-indexing of the data based on the additive group isomorphisms. Note, however, that PFA can be combined with mixed-radix Cooley–Tukey, with the former factorizing N into relatively prime components and the latter handling repeated factors. PFA is also closely related to the nested , where the latter performs the decomposed N1 by N2 transform via more sophisticated two-dimensional convolution techniques. Some older papers therefore also call Winograd's algorithm a PFA FFT. (Although the PFA is distinct from the Cooley–Tukey algorithm, Good's 1958 work on the PFA was cited as inspiration by Cooley and Tukey in their 1965 paper, and there was initially some confusion about whether the two algorithms were different. In fact, it was the only prior FFT work cited by them, as they were not then aware of the earlier research by Gauss and others.) 互質因子算法（Prime-factor FFT algorithm, PFA），又稱為Good-Thomas算法，是一種快速傅立葉變換（FFT），把N = N1N2大小的離散傅立葉變換重新表示為N1 * N2大小的二維離散傅立葉變換，其中N1與N2需互質。變成N1和N2大小的傅立葉變換後，可以繼續遞迴使用PFA，或用其他快速傅立葉變換算法來計算。 較流行的Cooley-Tukey算法經由mixed-radix一般化後，也是把N = N1N2大小的離散傅立葉變換分割為N1和N2大小的轉換，但和互質因子算法 (PFA)作法並不相同，不應混淆。Cooley-Tukey算法的N1與N2不需互質，可以是任何整數。然而有個缺點是比PFA多出一些乘法，和單位根twiddle factors相乘。相對的，PFA的缺點則是N1與N2需互質 (例如N 是2次方就不適用)，而且要藉由中國剩餘定理來進行較複雜的re-indexing。互質因子算法 (PFA)可以和mixed-radix Cooley-Tukey算法相結合，前者將N 分解為互質的因數，後者則用在重複質因數上。 PFA也與nested Winograd FFT算法密切相關，後者使用更為精巧的二維摺積技巧分解成N1 * N2的轉換。因而一些較古老的論文把Winograd算法稱為PFA FFT。 儘管PFA和Cooley-Tukey算法並不相同，但有趣的是Cooley和Tukey在他們1965年發表的有名的論文中，沒有發覺到高斯和其他人更早的研究，只引用Good在1958年發表的PFA作為前人的FFT結果。剛開始的時候人們對這兩種作法是否不同有點困惑。
prov:wasDerivedFrom
wikipedia-en:Prime-factor_FFT_algorithm?oldid=1117514792&ns=0
dbo:wikiPageLength
9583
foaf:isPrimaryTopicOf
wikipedia-en:Prime-factor_FFT_algorithm