 10-D Prime Factor Algorithm

Presentation on theme: " 10-D Prime Factor Algorithm"— Presentation transcript:

1  10-D Prime Factor Algorithm
[Ref] A. V. Oppenheim, Discrete-Time Signal Processing, London: Prentice-Hall, 3rd ed., 2010. N 可以是任意整數 If P1, P2, …, PM are small integers and prime to each other the powers k1, k2, …, kM are small then using the prime factor FFT to implement the N-point DFT may require fewer real multiplications.

2 3-point DFT butterfly: Needs 4 complex multiplications (12 real multiplications) N–point DFT butterfly: needs 3(N1)(N1) real multiplications 然而，可以使用特殊的方法，讓 N–point DFT 的乘法量大幅減少 (即使 N  2k) 例如 pages 290, 297 x[0] x[1] x[2] X[0] X[1] X[2]

3  Detail of the implementation method of the prime factor algorithm
n = 0, 1, …., N −1, m = 0, 1, …., N −1 Case 1: 假設 N = P1  P2 ， P1 is prime to P2 拆成 P2 個 P1-point DFTs，和 P1 個 P2-point DFTs 令 n = ((n1P1 + n2P2)) N m = ((m1P1 + m2P2)) N (( ))N : 除以 N 的餘數 n1, m1 = 0, 1, …., P2 −1, n2, m2 = 0, 1, …., P1 −1 當 P1, P2 互值時，每一個 n1, n2 對應到唯一一個 n

4 例子：當 N = 15, P1 = 3, P2 = 5, 0 = ((0· P1 + 0·P2)) = ((0· P1 + 2·P2))15 1 = ((2· P1 + 2·P2)) = ((2· P1 + 1·P2))15 2 = ((4· P1 + 1·P2)) = ((4· P1 + 0·P2))15 3 = ((1· P1 + 0·P2)) = ((1· P1 + 2·P2))15 4 = ((3· P1 + 2·P2)) = ((3· P1 + 1·P2))15 5 = ((0· P1 + 1·P2))15 6 = ((2· P1 + 0·P2))15 7 = ((4· P1 + 2·P2))15 8 = ((1· P1 + 1·P2))15 9 = ((3· P1 + 0·P2))15

5 Step 2 Step 3 n1, m1 = 0, 1, …., P2 −1, n2, m2 = 0, 1, …., P1 −1

6 Step 1 令 Step 2 固定 n2，對 n1 做 P2-point DFT n2 有 P1 個值，所以有 P1 個 P2-point DFTs Step 3 固定 m3，對 n2 做 P1-point DFT m3 有 P2 個值，所以有 P2 個 P1-point DFTs m3 = 0, 1, …., P2 −1, m4 = 0, 1, …., P1 −1 Step 4 其中 ((m1P1))P2 = m3, ((m2P2))P1 = m4,

7 n = 0, 1, …., N −1, m = 0, 1, …., N −1 Case 2: 假設 N = P1  P2 ， P1 is not prime to P2 令 n = n1P1 + n m = m1 + m2P2 n1, m1 = 0, 1, …., P2 −1, n2, m2 = 0, 1, …., P1 −1

8 Step 2 Step 3 Step 4 被稱為 twiddle factor，需要額外的乘法 n1, m1 = 0, 1, …., P2 −1, n2, m2 = 0, 1, …., P1 −1

9 Step 1 令 Step 2 固定 n2，對 n1 作 P2-point DFT n2 有 P1 個值，所以有 P1 個 P2-point DFTs Step 3 Step 4 固定 m1，對 n2 作 P1-point DFT Step 5

10  10-E FFT 的乘法量的計算 假設 N = P1  P2 ， P1 is prime to P2
P1-point DFT 的乘法量為 B1， P2-point DFT 的乘法量為 B2 則 N-point DFT 的乘法量為 P2B1 + P1B2 假設 P1, P2, …., PK 彼此互質 Pk-point DFT 的乘法量為 Bk 則 N-point DFT 可分解成 (N/P1) 個 P1-point DFTs (N/P2) 個 P2-point DFTs : (N/PK) 個 PK-point DFTs 總乘法量為

11 假設 N = P c, P is a prime number
若 N1 = P a 的乘法量為 B1, N2 = P b 的乘法量為 B2, a + b = c, 且 n1n2 當中 (n1 = 0, 1, …., N1 −1, n2 = 0, 1, …., N2 −1) 有 D1 個值不為 N/12 及 N/8 的倍數 有 D2 個值為 N/12 或 N/8 的倍數，但不為 N/4 的倍數 則 N-point DFT 的乘法量為 N2B1 + N1B2 + 3D1 + 2D2 Note: a  exp(j )，當 a 為 complex，需要 3 個乘法 然而，當  = /4，只需 2個乘法 當  = /3，只需 2 個乘法

12 例子： 16-point DFT, 16 = 8  2 , 乘法量 = 2     2 = 24 16 = 4  4 乘法量 = 4     4 = 20

13  10-F Goertzel Algorithm
DFT: 優點： Hardware 最為精簡 缺點： 運算時間較長 x[n] = f [Nn], n = 1, 2, …., N F[m] = y[N] x[n] y[n]

14  10-G Chirp Z Transform 適合於計算 FT 當 sampling interval 不為 t f  1/N 時
Continuous Fourier transform: 取 t = n t, f = m f, 當 t f = 1/N, 將可以用 DFT 以及 FFT來對上式作implementation。 當 t f  1/N 的時候  採用 CZT

15  10-H Winograd Algorithm for DFT Implementation
331  10-H Winograd Algorithm for DFT Implementation Basic idea: Except for the 1st row and the 1st column, the N-point DFT is equivalent to the (N−1)-point circular convolution when N is a prime number. Example: 5-point DFT ,  = exp[j72],

16 332 將 3rd and 4th rows, 3rd and 4th columns 作交換 變成 circular convolution 的型態 Circular Convolution Circular Convolution with time inverse

17 333

18 334 當 N 為其他的 prime numbers 時，也可以運用 permutation 和 circular convolution來計算 prime-number DFTs (Step 1) Delete the 1st row and the 1st column. (Step 2) Perform the row and column permutations. Rows 和 columns 的順序相同 (a) 找出一個 primitive root a, 使得 ak mod N  1 when k = 1, 2, …., N−2, aN−1 mod N  1 （Primitive root 的概念，會在後面講到數論時複習） (b) Rows 和 columns 的順序，以 p[n] 來表示， p[n] = an mod N, n = 0, 1, …., N−2 (Step 3) 變成 circular convolution 的型態 則 N-point DFT 可以用(N−1)-point DFTs 來 implementation

19 335 重要理論： Any N-point DFT can be implemented by the 2k-point DFTs whatever the value of N is. 7-point DFT 123-point DFT

20 XI. Discrete Fourier Transform 的替代方案
 11-A Why Should We Use Other Operations? Discrete Fourier Transform (DFT): 優點： 有 fast algorithm (complexity 為 O(Nlog2N)). 適合做頻譜分析和 convolution implementation 問題： (1) complex output (2) The exponential function is not of the binary form.

21 Applications of the DFT:  Spectrum analysis  Performing the convolution
For spectrum analysis, the DFT can be replaced by: (1) DCT, (2) DST, (3) DHT, (4) Walsh (Hadamard) transform, (5) Haar transform, (6) orthogonal basis expansion, (including orthogonal polynomials and CDMA), (7) wavelet transform, (8) time-frequency distribution When performing the convolution, the DFT can be replaced by: (1) DCT, (2) DST, (3) DHT, (4) Directly Computing, (5) Sectioned DFT convolution, (6) Winograd algorithm, (7) Walsh (Hadamard) transform, (8) number theoretic transform (NTT)

22  11-B Discrete Sinusoid Transforms
DCT (discrete cosine transform) has 8 types DST (discrete sine transform) has 8 types DHT (discrete Hartley transform) has 4 types 共通的特性：皆為 real, 且和 DFT 密切相關 Reference  N. Ahmed, T. Natarajan, and K. R. Rao, “Discrete cosine transform,” IEEE Trans. Comput., vol. C-23, pp , Jan 1974.  Z. Cvetkovic and M. V. Popovic, “New fast recursive algorithms for the computation of discrete cosine and sine transforms,” IEEE Trans. Signal Processing, vol. 40, pp , Aug  R. N. Bracewell, The Hartley Transform, New York, Oxford University Press, 1986.  S. C. Chan and K. L. Ho, “Prime factor real-valued Fourier, cosine and Hartley transform,” Proc. Signal Processing VI, pp , 1992.

23  Case 1: 當 x[n] 為 even function，x[n] = x[N−n]
在做頻譜分析時， N-point DFT 可以被 (floor(N/2) +1)-point DCT (type 1) 取代 可以證明，當 x[n] 為 even， （運算量減少將近一半） Recover: 注意：和 JPEG 所用的 DCT (type 2) 並不相同

24 (Proof) When x[n] = x[N−n] ，N is even (The case where N is odd can be proved in the similar way)

25 half part of x[n] 25

26  Case 2: 當 x[n] 為 odd function， x[n] = −x[N−n]
在做頻譜分析時， N-point DFT 可以被 (N/2 −1)-point DST (type 1) 取代 , Q = N/2. 可以證明，當 x[n] 為 odd， (運算量減少將近一半) Recover:

27  Case 3: 當 x[n] 為 real function，在做頻譜分析時，
N-point DFT 可以被 N-point DHT (type 1) 取代 , where cas(k) = cos(k) + sin(k) 比較： exp(jk) = cos(k) + jsin(k) 可以證明，若 x[n] 為 real， (運算量減少將近一半) Recover:

28  大部分的 convolution 仍然使用 DFT。
y[n] = x[n]  h[n] y[n] = IDFT{ DFT(x[n]){DFT(h[n]) } 思考：何時適合用 DCT 做 convolution ？ 何時適合用 DST 做 convolution ？ 何時適合用 DHT 做 convolution ？

29 附錄十一：一般論文的格式以及 Office 編輯論文 的技巧
註：這裡指的是一般 journal papers 和 conference papers 的格式。 然而，不同的 journals 和 conferences，對於格式的規定，也會稍有不同。投稿前，還是要細讀相關的規定。 (1) 變數使用斜體，矩陣或向量使用粗體 f(x) = x2 + 3x (f, x 皆用斜體) (y, A 皆用粗體) (2) 段落的經常用「左右對齊」的格式 如果使用 Word 2007，可以按 常用  段落  對齊方式 左右對齊 或是按工具列中的

30 (3) Equation 的標號，經常用「定位點」的功能，讓標號的位置固定
如果使用 Word 2007，可以按 常用  段落  定位點 (在對話框左下角) ，再設定定位點的位置 (4) 至於 equations 本身，通常置於這一行的中間，例如 F = ma. (1) Equations 和前一行以及後一行，皆要有足夠的距離。而且，equations 的後方常常要加逗號或句號 (以下一行是否為新的句子而定)。 (5) 標題(包括 papers 的標題以及每個 chapters 和 sections的標題) 當中， 每個單字的開頭一定要大寫，除了 (a) 介係詞 (b) 連詞 (c) 冠詞 以外。 若為第一個單字，即使是介係詞 ， 連詞，或冠詞，也要大寫 The Applications of the Fourier Transform in Daily Life Fast Algorithms of the Wavelet Transform and JPEG2000

31 (6) 文章一定要包括 (a) Abstract, (b) Introduction (通常是第一個 section) (c) 內文 (d) Conclusions 或 Conclusions and Future Works (通常是最後一個 section) (e) References (7) 每一張圖 (figures)，每一張表 (tables) 都要編號，而且要附加文字說明。 如 Fig. 3 The result of the Fourier transform for a chirp signal. 若一張圖當中有很多個小圖，每個小圖也要編號 (a), (b), (c), (d) ….. (8) 同一個 equation，同一張圖，要放在同一頁，不分散於兩頁。

32 (9) 一般而言，Journal papers 的初稿，是 one column, double space 的格式。
在 Word 當中， double space 可以用後下的方法設定 常用  段落  行距  2倍行高 但有時， 2倍行高會讓初稿過於稀疏，在 Word 當中可以用 版面配置 版面設定  文件格線  沒有格線 來讓文件看起來不會那麼稀疏，且不易超過規定的頁數。 (10) Conference papers 是 two columns, one space 的格式。有時 Journal papers 被接受後，也會要求改成 two columns, one space 的格式。 在Word 2007 當中， two columns 可以用 版面配置  欄  二 (W) 來設定 (11) References 的編號，通常是按照在文章中出現的順序來排序 或者也可按照第一作者的 last name 的英文字母順序排序

33 (12) Reference 的寫法 (以 IEEE Transactions on Signal Processing 為例) (A) Journal papers and conference papers Authors (first name 或 middle name 只用一個字母代表), “title ,” name of the journal (縮寫為佳), vol. *, no. *, pp. **~**, month, year. 逗號在引號之前 使用縮寫 只有第一個字母、專有名詞開頭、和縮為用大寫 加句號 範例： S. Abe and J. T. Sheridan, “Optical operations on wave functions as the Abelian subgroups of the special affine Fourier transformation,” Opt. Lett., vol. 19, no. 22, pp , 1994.

34 (B) Books Authors (first name 或 middle name 只用一個字母代表), title (斜體, 字開頭大寫，不加引號), 第幾版 (非必需), 出版社, 出版地, year. 範例 H. M. Ozaktas, Z. Zalevsky, and M. A. Kutay, The Fractional Fourier Transform with Applications in Optics and Signal Processing, 1st Ed., John Wiley & Sons, New York, 2000. (C) Websites Authors, “title,” available in 範例 張智星, “Utility toolbox,” available in matlab/toolbox/utility/.

35 Office 編緝論文的小技巧 (1) 一些常用的字，可用「自動校正」功能 例如： parameter 這個字太長了
在 Word 2007 當中，可以選擇 (在左上方)  Word 選項 (在下方)  校訂 (在左方)  自動校正選項 在「取代」的部分輸入 para，在「成為」的部分輸入 parameter，再按「確定」 以後只要輸入 para 再按空白鍵，就會自動修正為 parameter 或者，也可以按「插入」 「 符號」 「其他符號」 「自動校正」(在左下方)，之後再選擇「純文字」，即可使用自動校正的功能

36 (2) 一些常用但鍵盤上找不到的符號 (像  ， )，也可以用「自動校正」或「快速鍵」的功能來輸入
在按「插入」 「 符號」 「其他符號」之後，注意左下方出現了「自動校正」以及「快速鍵」兩個按鈕。 例如，對於符號 ，我們可以按「自動校正」，然後再「取代」的地方輸入 ld，再按「確定」，以後只要輸入 ld 再按空白鍵，就會自動修正為  (註：這個功能只能在 Word 上使用)

37 (3) 常用的快捷鍵 Ctrl + C: 複製， Ctrl + X: 剪下， Ctrl + V: 貼上， Ctrl + S: 儲存 Ctrl + A: 全選， Ctrl + Z: 復原， Ctrl + Y: 取消復原 Ctrl + 等號: 下標， Ctrl + Shift + 加號 : 上標， Ctrl + B: 粗體， Ctrl + I: 斜體， Ctrl + Shift + C: 複製文字的格式， Ctrl + Shift + V: 貼上文字的格式 Ctrl + Enter: 換頁，Shift + Enter: 換行 Shift + F3: 改變大小寫，Ctrl + Shift + A: 全大寫， Ctrl + Shift + K: 全小寫 (4) F 鍵 F4: 可重覆剛才的動作， (重要功能) F1: Help， F5: 到，取代，以及尋找 (在 Powerpoint 中是放映)

38 (5) 群組 繪圖或 Powerpoint 製作時，要複製、剪下、移動、放大或縮小一組物件，可先將這些物件選取後，再按右鍵，選「群組物件」，再按「群組」，就可以將這些物件變成同一個群組，一同複製、剪下、移動、放大或縮小。 之後，若要處理個別的物件，只需按右鍵，選「群組物件」，再按「取消群組」即可。 (6) 微調 繪圖或 Powerpoint 製作時，若要微調一個物件的大小或位置，可以在調整的同時按 Alt 鍵。 (7) 可參考 Office 官方網站 直接用 Google 找尋相關輸入技巧 Office 的 Help