 IV. Implementation IV-A Method 1: Direct Implementation 以 STFT 為例

Presentation on theme: "IV. Implementation IV-A Method 1: Direct Implementation 以 STFT 為例"— Presentation transcript:

IV. Implementation IV-A Method 1: Direct Implementation 以 STFT 為例
Converting into the Discrete Form t = nt, f = mf,  = pt Suppose that w(t)  0 for |t| > B, B/ t = Q Problem：對 Gabor transform 而言，Q = ?

 Constraint for t (The only constraint for the direct implementation method)
To avoid the aliasing effect, t < 1/2,  is the bandwidth of ? There is no constraint for f when using the direct implementation method.

Four Implementation Methods
(1) Direct implementation Complexity: 假設 t-axis 有 T 個 sampling points, f-axis 有 F 個 sampling points (2) FFT-based method Complexity: (3) FFT-based method with recursive formula Complexity: (4) Chirp-Z transform method Complexity:

(A) Direct Implementation

IV-B Method 2: FFT-Based Method
Constraints： tf = 1/N, N = 1/(tf) ≧ 2Q +1: (tf 是整數的倒數) Note that the input of the FFT has less than N points (others are set to zero). Standard form of the DFT , q = p(nQ) → p = (nQ)+q where for 0  q  2Q, x1(q) = for 2Q < q < N.

m = f/ f page 99 m1 = mod(m, N)+1

IV-C Method 3: Recursive Method
A very fast way for implementing the rec-STFT (n 和n1有recursive的關係) (1) Calculate X(min(n)t, mf) by the N-point FFT , n0 = min(n), for q  2Q, x1(q) = 0 for q > 2Q (2) Applying the recursive formula to calculate X(nt, mf), n = n0 +1~ max(n) T點 F點

IV-D Method 4: Chirp Z Transform
For the STFT Step 1 multiplication Step 2 convolution Step 3 multiplication

Question: Step 2 要用多少點的 DFT?
n-Q  p  n+Q Step 2 Step 3 Step 2 在計算上，需要用到 linear convolution 的技巧 Question: Step 2 要用多少點的 DFT?

 Illustration for the Question on Page 104
 Case 1 When length(x[n]) = N, length( h[n]) = K, N and K are finite, length(y[n]) = N+K1, Using the (N+K1)-point DFTs (學信號處理的人一定要知道的常識)  Case 2 x[n] has finite length but h[n] has infinite length ????

 Case 2 x[n] has finite length but h[n] has infinite length
x[n] 的範圍為 n  [n1, n2]，範圍大小為 N = n2 − n1 + 1 h[n] 無限長 　　　　　　　　　　　y[n] 每一點都有值 (範圍無限大）　　　　　　　　 但我們只想求出 y[n] 的其中一段 希望算出的 y[n] 的範圍為 n  [m1, m2]，範圍大小為 M = m2 − m1 + 1 h[n] 的範圍 ? 要用多少點的 FFT ?

m1 − n2 m1 − n1 m1−n2+1 m1−n1+1 m1−n2+2 m1−n1+2 n = m1 時　 n − s 的範圍　 n = m1 +1 時　 n − s 的範圍　 m2−n2 m2−n1 n = m1 +2 時　 n − s 的範圍　 n = m2 時　 n − s 的範圍　 有用到的 h[k] 的範圍：k  [m1 − n2, m2 − n1]

IV-E Unbalanced Sampling for STFT and WDF

When (1) f = 1/N, (2) N = 1/(f) > 2Q +1: (f只要是整數的倒數即可)
(3)  < 1/2,  is the bandwidth of i.e., when | f | >  令 q = p  (nSQ) → p = (nSQ) + q for 0  q  2Q, x1(q) = for 2Q < q < N.

= c0S, (c0S+S) , (c0S+2S) , ……, [c0S+ (C-1)S] , f = m0 f, (m0+1) f, (m0+2) f, ……, (m0+F-1) f  = n0 , (n0+1) , (n0+2) , ……, (n0+T-1) , S = t/  Step 1: Calculate c0, m0, n0, C, F, T, N, Q Step 2: n = c0 Step 3: Determine x1(q) Step 4: X1(m) = FFT[x1(q)w((Q-q) )] Step 5: Convert X1(m) into X( nt, mf) Step 6: Set n = n+1 and return to Step 3 until n = c0+ C -1. Complexity = ?

IV-F Non-Uniform t (A) 先用較大的 t (B) 如果發現 和 之間有很大的差異

Gabor transform of a music signal
 = 1/44100 (總共有  sec + 1 = 點

(A) Choose t =  running time = out of memory (B) Choose t = 0.01 = 441 (1.6/ = 161 points) running time = sec (2008年) (C) Choose the sampling points on the t-axis as t = 0, 0.05, 0.1, 0.15, 0.2, 0.4, 0.45, 046, 0.47, 0.48, 0.49, 0.5, 0.55, 0.6, 0.8, 0.85, 0.9, 0.95, 0.96, 0.97, 0.98, 0.99, 1, 1.05, 1.1, 1.15, 1.2, 1.4, 1.6 (29 points) running time = sec