2.6 FFT(Fast Fourier Transform 2.6. T g(t g(t 2 a 0 + { a m b m 2 T T 0 2 T T 0 (a m cos( 2π T mt + b m sin( 2π mt ( T m 2π g(t cos( T mtdt m 0,, 2,... 2π g(t sin( T mtdt m, 2, 3... (2 g(t T 0 < t < T t 0 < t < t 0 + T m a m, b m : T 0, T, 2 T,... 2.6.2 e i 2π T mt cos( 2π T mt ( e i 2π T mt + e i 2π mt T (3 2 sin( 2π T mt 2i ( e i 2π T mt e i 2π T mt (4 ( a m cos( 2π T mt + b m sin( 2π T mt a m (3 + b m (4 2 (a m ib m e i 2π T mt + 2 (a m + ib m e i 2π T mt C m e i 2π T mt + B m e i 2π T mt C m 2 (a m ib m B m 2 (a m + ib m C m B m ( ( g(t a 0 2 + m ( C m e i 2π T mt + B m e i 2π T mt (5 C 0 a 0 2 C me i 2π T mt m0 (6
(5 B m e i 2π T mt m m B m e i 2π T mt m m B m e i 2π T mt B m (m < 0 C m m (6 (7 (5 g(t C 0 + m C m e i 2π T mt (7 C m e i 2π T mt + m m C m e i 2π T mt C m e i 2π T mt (8 C m B m B m C m C m C m (9 C m (2 C m 2 (a m ib m (0 C m T T T 0 T 0 g(t(cos( 2π mt i sin(2π T T mtdt g(te i 2π T mt dt ( C m T T 0 g(t cos( 2π T mtdt i T g(t sin( 2π T 0 T mtdt Cm e imt Cm b m /2 C-m C-m e -imt φ m a m /2 : C m C m 2: C m a m, b m (0 a m, b m ( ( 2 { C m Re(C m 2 a m C m Im(C m 2 b m 2
( ( g(t 2 a 0 + sin φ m m ( 2π a m2 + b 2 m sin T mt + φ m b m am2 + b, cos φ a m m 2 2 m am2 + b m { C m a m2 + b m 2 m T arg C m φ m 2.6.3 ( ω m 2mπ T 2 T C m T T 2 T 2 g(te iωmt dt G(ω m T C m G(ω m T 2 T 2 g(te iω mt dt T ( 2π 0 T G(ω g(te iωt dt g < ω < 2.6.4 (DFT, Discrete Foureir Transform 3 T T ( T 2π T ( ( S r / N T N 3
g 0 t T T : 3: T T g(k g k 0 k (N- N T 4: 4 ( C m T ( g(k e i 2π T mk g(k g k ( k T ( g k e i 2π T mk /T /N C m N g k e i 2π N mk m (, (2 (DFT DFT G m G m NC m G m NC m (m g k e i 2π N mk m (, (3 m G m T S r g(t S r 2 2 m T 2 T N N 2 m N 2 4
( m (, m G m 0 DFT G m g k e i 2π N mk N 2 m N 2 (4 (4 W N e i 2π N G m g k W N mk G m G m km g k W N g k (W N km g k (e i 2π N km g k W N km G m G m G m G m a m + b m i G m a m + b m i G m G m a m a m ( b m b m ( 5 N DFT 0 N 2 G N/2 0 N/2 5: DFT G m (m (W N N (e i 2π N N e i2π (W N n+n (W N n (W N N (W N n (W N n (W N mod(n,n G m+n G m+n k g k W N (N+mk G m 5
N 2 m < 0 G m N 2 m < N G m. N G m g k W N km m 0,..., N m N 2 G m G m N (m N. G m N G m (m N 2 G m g k N g k W N km m0 (m 0,,..., N (5 G m W km N (k 0,,..., N (6 2 DFT (IDFT, Inverse Discrete Fourier Transform g k g(k (8 t k g k g(k m C m e i 2π T mk m0 N G me i 2π N mk N m0 G m W km N Gm C m N G m /T /N 8 DFT N DFT N DFT N 8 G 0, G G 2 G 0 G 7 7 g k W 0 k 8 g k W k 8 7 g k W8 0 7 g k W8 k 7 g k g 0 + g + g 2 + + g 7 G 2 g 0 W 0 8 + g W 8 + g 2 W 2 8 + g 3 W 3 8 + g 4 W 4 8 + g 5 W 5 8 + g 6 W 6 8 + g 7 W 7 8 g 0 + g e i π 4 + g2 e i π 2 + g3 e i 3π 4 + g4 e iπ + g 5 e i 5π 4 + g6 e i 3π 2 + g7 e i 7π 4 2 2 2 2 g 0 + g ( 2 i 2 + g 2( i + g 3 ( 2 i 2 2 2 2 2 +g 4 + g 5 ( 2 + i 2 + g 6i + g 7 ( 2 + i 2 7 g k W 2 k 8 g 0 W8 2 0 + g W8 2 + g 2 W8 2 2 + g 3 W8 2 3 + g 4 W8 2 4 + g 5 W8 2 5 + g 6 W8 2 6 + g 7 W8 2 7 g 0 W8 0 + g W8 2 + g 2 W8 4 + g 3 W8 6 + g 4 W8 8 + g 5 W8 0 + g 6 W8 2 + g 7 W8 4 6
N 6 2 < m < N G m G m N (G m G m N ḠN m 6 N 8 4 < m < 8 G 5 G 3 Ḡ3 G 6 G 2 Ḡ2 G 7 G Ḡ G 4 G, G 2, G 3 G 5, G 6, G 7 0 2 3 4 5 6 7-3 -2 - Hz 0 2 3 4 5 6 7-3 -2 - Hz 0 2 3 4 5 6 7-3 -2 - Hz 0 2 3 4 5 6 7-3 -2 - Hz 0 2 3 4 5 6 7-3 -2 - Hz 0 2 3 4 5 6 7-3 -2 - Hz 0 2 3 4 5 6 7-3 -2 - Hz 0 2 3 4 5 6 7-3 -2 - Hz 6: DFT (f 0 Hz; 8Hz 2.6.5 FFT (Fast Fourier Transform DFT FFT DFT 7
N 4 G 0 G G 2 G 3 3 3 3 3 g k W 0k 4 g 0 W 4 0 + g W 4 0 + g 2 W 4 0 + g 3 W 4 0 g k W k 4 g W 4 0 + g W 4 + g 2 W 4 2 + g 3 W 4 3 g k W 2k 4 g W 4 0 + g W 4 2 + g 2 W 4 4 + g 3 W 4 6 g k W 3k 4 g W 4 0 + g W 4 3 + g 2 W 4 6 + g 3 W 4 9 G 0 W4 0 W4 0 W4 0 W4 0 G G 2 W4 0 W4 W4 2 W4 3 W4 0 W4 2 W4 4 W4 6 g 0 g g 2 (7 G 3 W 0 4 W 3 4 W 6 4 W 9 4 g 3 G m 4 3 G m 4 4 4 3 N DFT N 2 N(N FFT (N/2(log 2 (N N log 2 N 2 FFT N 2 N 2 2 4 N 2 0 024 N 2 G 0 g 0 W 0 2 + g W 0 2 g 0 + g G g 0 W 0 2 + g W 2 g 0 g G 0 W2 0 W2 0 G W2 0 W2 g 0 g 2 2 W 2 W2 0 W2 0 W 2 W2 0 W2 7 g0 g - G0 G 7: 2 FFT 8
N 4 ( (7 m 0,, 2, 3 G m. m 2 2. 3. 0 m m 2 m 0 00 00 0 0 0 2 2 0 0 3 3 (7 G i m G 0 W4 0 W4 0 W4 0 W4 0 g 0 G 2 G W4 0 W4 2 W4 4 W4 6 g W4 0 W4 W4 2 W4 3 g 2 G 3 W4 0 W4 3 W4 6 W4 9 g 3 G m FFT FFT 4 4 W 4 W4 0 W4 0 W4 0 W4 0 W 4 W4 0 W4 2 W4 4 W4 6 W4 0 W4 W4 2 W4 3 W4 0 W4 3 W4 6 W4 9 W4 0 W4 0 W4 0 W4 0 W 4 W4 0 W4 2 W4 4 W 6 4 A B W4 0 W4 W4 2 W4 3 C D W4 0 W4 3 W4 6 W4 9 A, B, C, D W4 0 W4 0 A W4 0 W4 2 B W 0 4 W 0 4 W 4 4 W 6 4 W 0 4 W 0 4 W 0 4 W 2 4 A (e i 2π N 2k (e WN 2k i 2π W4 2 W2 A B W2 0 W2 0 W2 0 W2 W 2 9 N/2 k WN/2 k W 4 0 W2 0
C W4 0 W4 W4 0 W4 3 W2 0 W2 0 W2 0 W2 W4 0 W4 0 W4 0 0 W4 0 W4 2 0 W4 W4 0 0 W 0 W4 2 V 2 V 2 W 0 4 0 0 W 4 D W 2 4 W 3 4 W 6 4 W 9 4 W 2 4 W 3 4 W 2 4 W 5 4 W 2 4 W 0 4 W 4 W 0 4 W 3 4 W 2 4 C W 2 V 2 W 2 W 2 W 4 W 2 V 2 W 2 V 2 W 2 O 2 O 2 W 2 I 2 O 2 O 2 V 2 I 2 I 2 I 2 I 2 O 2 2 2 I 2 2 2 G 0 G 2 G W 2 O 2 O 2 W 2 I 2 O 2 O 2 V 2 I 2 I 2 I 2 I 2 g 0 g g 2 G 3 g 3 g 0 g g 2 g 3 I 2 O 2 I 2 I 2 O 2 V 2 I 2 I 2 G 0 G 2 G G 3 W 2 O 2 O 2 W 2 g 0 g g 2 g 3 g 0 g g 2 g 3 2 FFT G 0 W 2 g 0 G 2 G W 2 g g 2 G 3 g 3 G 0 G 2 G G 3 W 2 W 2 W 0 4 W 4 0 0 0 0 0 0 0 0 g 0 g g 2 g 3 0
g0 g g2 g3 - - W 0 4 W 4 W2 W2 G0 G2 G G3 8: 4 FFT W 2 2 FFT 0 8 N 2 3 8 8 FFT 4 FFT 4 FFT m 2 m 0 000 000 0 00 00 4 2 00 00 2 3 0 0 6 4 00 00 5 0 0 5 6 0 0 3 7 7 m G i G 0 G 4 G 2 G 6 G G 5 G 3 W 4 O 4 O 4 W 4 I 4 O 4 O 4 V 4 I 4 I 4 I 4 I 4 g 0 g g 2 g 3 g 4 g 5 g 6 G 7 g 7 W 4 O 4 O 4 W 4 O 4 0 W8 W 8 O 4 W 2 8 W 3 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 g 0 g g 2 g 3 g 4 g 5 g 6 g 7 9 FFT FFT 0 N FFT log 2 N N/2 2
g0 g g2 g3 g4 g5 g6 g7 - - - - W 0 8 W 8 W 2 8 W 3 8 W4 W4 G0 G4 G2 G6 G G5 G3 G7 9: 8 FFT W 4 4 FFT - W i N 0: log 2 N N 2 2 N log 2 N WN i 2 FFT log 2 N N/2 (log 2 N N 2 2.6.6 (DCT, Discrete Cosine Transform (DCT DFT DCT DFT DCT N N g 0, g,..., g g 0, g,..., g g, g N 2,..., g 0 g, g N 2,..., g 0, g 0, g,..., g N, N +,...,, 0,,..., N g k g N, g N+, g N+2,..., g, g 0, g,..., g g k (5 (6 G m G m g k k N 2 g kw mk (8 m N G mw km (9
: DCT (8 G m g kw mk + k N g kw mk k 0,..., N g k g k g k W mk 2 k k k 0,..., N g k g k 2 0 k 0 k g k W m( k g k W m( k k k g k W m( k G m G m g k (W mk + W m( k g k W 2 m (W m(k+ 2 + W m( k 2 g k W 2 m (e i 2π m(k+ 2 + e W 2 m g k 2 cos( π N m(k + 2 2π i m(k+ 2 G m G m 2 W 2 m G m (20 G m g k cos mπ(2k + (2 3
G m N DCT G m (2 k 0 N m N N m N G N W 2 ( N g k 2 cos( π N ( N(k + 2 W N 2 g k 2 cos( π(k + 2 0 G N G N 0 G m W 2 ( m g k 2 cos( π N ( m(k + 2 W 2 m g k 2 cos( π N ( m(k + 2 G m (9 (2 g k (9 g k ( g k k 0,,..., N g k m N G mw km Σ m N G mw km G N W kn + G 0W 0 + G mw km + m G N W kn + G 0 + G mw km + m m N m N+ 0 2 (20 G mw km G mw km G 0 2G 0 3 (G m G m (2W m 2 ( 2 W m 2 G m m G mw km (2W m 2 ( 2 W m 2 G mw km m (2W m 2 m m G mw km 2G m W m(k+ 2 4 m m 3 G m G m 4
m G km m W m G mw km (2W m 2 ( 2 W m 2 G mw km m (2W m 2 2 W m 2 m m m 2G m W m 2 W km 2G m W m(k+ 2 G mw km G m G m G m g k (2G 0 + 2G m (W m(k+ 2 + W m(k+ 2 m 2 N ( 2 G 0 + G m cos m mπ(2k + N G m g k cos mπ(2k + (m 0,,..., N DCT DCT g k g k 2 N ( 2 G mπ(2k + 0 + G m cos (k 0,,..., N m G m g k DCT 2.6.7 FFT/DCT FFT IDFT DCT 5
MPEG (Moving Picture Coding Experts Group 6