文件名重復(fù)-167674(已修改)
2024-10-14 03:04 本頁面
【正文】 167。 N是組合數(shù)的 FFT算法 方法一：將 x (n)補零，使 N成為 2的整數(shù)冪。例 N?=30 可以加 2點， N =32=25 ； N?=1000可以加 24點，即 N =1024=210。 如果要獲得準(zhǔn)確的 N點 DFT，可以用任意基的 FFT算法。 其基本思路還是將大點 DFT盡可能分解為小點的 DFT， 充分利用小點 DFT的周期性。 對 N不是 2的整數(shù)冪的情況，有兩種處理方法。 N是組合數(shù)的 FFT算法 以時間抽取法為例，討論 N是組合數(shù)的 FFT算法。 ? ?? ?? ?? ????????????111111prpxrpxrpxnx?1,1,0 1 ?? qr ?設(shè) N=p1p2???pm pi —— 均為素數(shù) N=p1q1 令 q1=p2???pm 先將 N點 DFT分解為 p1個 q1點的 DFT。即將 x(n)分為 p1組，每組 q1個元素。 ? ?lrpx ?1? ? ? ? nkNNnWnxkX ????10將分組后的 一般式 ? ? ? ? ? ? ????? ??????? krpNqrrkpNqrWrpxWrpx 111011011111??1 ??2? ?1p? ? ? ? kprpNqrWprpx 111101111 ??????? ??r= 0,1,??? q1?1 l= 0,1,??? p1?1 ，對每個 k值有 (p1?1)次復(fù)乘） (共有 p1個 ? ? ? ? ? ? rkpNqrlkNplnkNNnWlrpxWWnxkX 1111101010??? ?????????? ? ? ? rkqqrlkNplrkpNqrlkNplWlrpxWWlrpxW11111111010/11010???? ????????????? ?kGW lqrlkNpl???????101011? ? ? ? rkqqrl WlrpxkG 11110?? ???其中 有 (p1?1)次復(fù)乘 q1點的 DFT ? ? ? ? 2111 1 qppNm F ???1qvpppq ?432 ?221 qpq ?1q 2p 2q再分 繼續(xù)對 計算量： 次復(fù)乘 總的合成 X(k)的復(fù)乘次數(shù) （ 6103） 令： 每 點的 DFT。 個 個點 DFT又可以分解為 p1個 q1點的 DFT復(fù)乘 p1(q1)2 每一個 X(k)值有 (p1?1)次復(fù)乘， N個 X(k)值有 N (p1?1) ? ? ? ? ? ?? ?2222111 11 qppqppNm F ?????? ? ? ? 2221112111 1 qppqppqppN ????? Nqp ?11?? ? ? ? ? ? 222121 11 qpppNpN ?????? ? ? ? 222121 2 qppppN ????? ? ? ? 22221 1 qppq ??mp一直分解到最后一個素數(shù) 代入（ 6103） 合成 q1點的 DFT復(fù)乘 ? ? ? ? 22121 mmmF qpppvpppNm ?? ??????1?mq? ? NvpppN m ?????? ?21? ?121 ?????? mpppN m?? ?mpppN m ????? ?21? ? mppppppmpppNNmmm ????????? ??? 2121212計算效率： 最后總的計算量（類推） 5315 ???N? ?nx則 可分為三組，每組 5點，即 ? ?? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ?? ? ? ? ? ? ? ? ? ? ? ?????????2314,11,8,5,21313,10,7,4,1312,9,6,3,0rxxxxxxrxxxxxxrxxxxxxnx4,1,0 ??r? ?lrx ?3一般項為 舉例 p= q=5 ? ? ? ? ? ? rkrlkNlnkNnWlrxWWnxkX 540201403 ??? ??????? ? ? ? ? ? ? ?kGWkGWkGkGW kklrlkl22151
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1