ディジタル信号処理 デザイン情報学科 メディア情報設計 河原英紀 2002.6.27 ディジタル信号処理 1 本日の予定 レポートから 課題の解答 高速Fourier変換 FFT(Fast Fourier Transform) 2002.6.27 なぜFFTは重要か FFTでどれだけ早くなるか どうしてFFTで早くなるのか ディジタル信号処理 2 レポートから 今日の授業は資料に書き込めたので理解しやす かった 窓関数が良く理解できなかった 窓関数は分かったがDFTの性質が分らない 窓関数はなぜ『窓』というのか? 授業の資料をダウンロードせずに見ることができ るようにして欲しい ようやくデモで見たアニメーションの意味が分 かった 2002.6.27 ディジタル信号処理 3 レポートから 以前のテストの解答を忘れないうちに見たい 課題の解答に時間を割いたのが良かった 全くついて行けなくなった。分らないところも分ら ない 授業のスピードがまだ早い 授業のスピードはちょうど良く、内容もちょうど良 かった 授業の資料を学科事務に置いて欲しい 講義室が寒すぎた FFTが早い理由が分らない 2002.6.27 ディジタル信号処理 4 レポートから 課題の前に例題で具体的に解いて欲しい 最近は何となく授業の内容が分るようになって来 た PowerPointの授業は見やすくて分かりやすい。し かし、ノートが取れないのでプリント配付が理想 ←??プリントは配付していますが?? 2002.6.27 ディジタル信号処理 5 DFTの性質 線形性 ax[n] by[n] aX(k) bY(k) 対称性 X(N k) X (k) 推移定理 DFT * x[n] R x[n m] WN DFT km X(k) 回転子 2002.6.27 ディジタル信号処理 6 DFTの性質 循環畳込みとDFT N1 y[n] h[l]x[n l] l0 Y(k) H(k)X(k) DFT 2002.6.27 ディジタル信号処理 7 窓関数の必要性 x[n] cosn のDFTはどうなるか? 2k N の場合には、複数の成分が非零になる 周期が不一致の場合、不連続が発生 2002.6.27 ディジタル信号処理 8 様々な窓関数 Hamming窓 hanning窓 Blackman窓 2002.6.27 2n w[n] 0.54 0.46cos N 1 2n w[n] 0.5 0.5cos N 1 2n w[n] 0.42 0.5cos N 1 4n 0.08cos N 1 ディジタル信号処理 9 課題 周期をM=N-1として、前のページで定義された Hamming窓、hanning窓、Blackman窓のDFTを 求めよ。また、以下の信号をhanning窓によって 切り出した信号のDFTを求めよ。 (ヒント:窓のDFTは、絶対値と位相を用いて 表した方が容易に解ける。推移定理を利用して 簡単化すること。) 6n x[n] cos M 2002.6.27 ディジタル信号処理 10 課題の解答例:Hamming Hamming窓 2n w[n] 0.54 0.46cos N 1 周期M=N-1であるから、n=0からM-1までのw[n]について DFTを計算する。混乱を避けるため、Mを用いてHamming 窓を表しておく。 2n w[n] 0.54 0.46cos M 求めるべきDFTは、次式となる。 M 1 W (k) w[n]W kn M n 0 2002.6.27 ディジタル信号処理 11 課題の解答例 M 1 W (k) w[n]W kn M n 0 2n kn 0.54 0.46cos WM M n 0 M 1 2 n 2 n j j M 1 M M e e kn 0.54 0.46 W M 2 n 0 2002.6.27 ディジタル信号処理 12 課題の解答例 2 n 2n 2 kn j j j M M M W (k) 0.54 0.23e 0.23e e n 0 M 1 2 kn 2 n(1 k ) 2 n(1 k ) j j j M M M 0.54e 0.23e 0.23e n 0 M 1 0.54M 0.23M 0 2002.6.27 k 0 失礼!配付プリントに 誤りがありました。 k 1,1 k 1,0,1 ディジタル信号処理 13 課題の解答例:hanning hanning窓の場合は、係数が異なるだけで同形であるので、 ただちに次が得られる。 2 n(1 k ) 2 n(1k ) j 2Mkn j j M M W (k) 0.5e 0.25e 0.25e n 0 M 1 0.5M 0.25M 0 2002.6.27 失礼!配付プリントに 誤りがありました。 k0 k 1,1 k 1,0,1 ディジタル信号処理 14 課題の解答例:Blackman Blackman窓の場合は、まず、Mを用いて次式のように 書き換える 2 n 4 w[n] 0.42 0.5cos M 0.08cos n M 第三項をEulerの公式を用いて変形することで、ただちに 以下が得られる 0.42M 0.25M W (k) 0.04M 0 2002.6.27 k0 k 1,1 k 2,2 k 2,1,0,1,2 ディジタル信号処理 15 課題の解答例 6n x[n] cos M 2n w[n] 0.5 0.5cos M これらの積のDFTを求める M 1 Y(k) x[n]w[n]W kn N n 0 6n 2n kn cos 0.54 0.46cos WN M M n 0 M 1 2002.6.27 ディジタル信号処理 16 課題の解答例 方法1: 展開してCOSの加法定理を用いて整理し、Eulerの公式 を用いて複素指数関数の和とする 方法2: 畳込み法則を用いて、窓関数のDFTと、信号のDFTか ら求める N 1 1 x1[n]x 2[n] N DFT X (l)X [((k l)) 1 2 N ] l 0 Nを法とする剰余の略記法(一般的ではない) 2002.6.27 ディジタル信号処理 17 課題の解答例 j 6 n M j 6n e e x[n] cos M 2 k 3,3 0.5M X(k) k 3,3 0 6 n M 0.5M k 0 Wha nning (k) 0.25M k 1,1 k 1,0,1 0 2002.6.27 ディジタル信号処理 18 課題の解答例 畳込み法則に代入すると直ちに次を得る k 3,3 0.25M Y(k) 0.125M k 4,2,2,4 k 4,3,2,2,3,4 0 2002.6.27 ディジタル信号処理 19 なぜFFTは重要か? DFTを高速に求めることができる 畳込みを高速化することができる 信号のFFT: X(k) インパルス応答のFFT:H(k) 両者の積:Y(k)=X(k)H(k)を求める Y(k)の逆FFTを求める 2002.6.27 信号の長さをN, インパルス応答の長さをM とすると、畳込みの計算にはNM回の積和が 含まれる FFTを介することで、NlogMの オーダーに積和が減少する ディジタル信号処理 20 FFTでどれだけ早くなるか 計算時間 Nが素数の場合 Nが2個の 素数の積の場合 N=2000 付近で DFTは 約140ms 2002.6.27 ディジタル信号処理 N 21 FFTでどれだけ早くなるか 前のページ の拡大図 N=2048の 場合には 1.4ms 100倍 早くなる 2002.6.27 ディジタル信号処理 22 DFTの計算 N 1 X(k) x[n]W kn N k 0,1, ,N 1 W e n 0 N=8の例 x[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7] この積和の回数を 組織的に削減する 2002.6.27 j X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 64回の複素数の積 ディジタル信号処理 23 2 N DFTの計算 N 1 X(k) x[n]W kn N k 0,1, ,N 1 n 0 (N / 2)1 x[2n]W (N / 2)1 2kn N n 0 x[2n 1]W k (2n 1) N n 0 (N / 2)1 (N / 2)1 n 0 n 0 2kn k x[2n]W W N N 2kn x[2n 1]W N DFTの形に類似している 2002.6.27 ディジタル信号処理 24 高速Fourier変換の仕組み (N / 2)1 X(k) x[2n]W (N / 2)1 n 0 ここで 右の関係を利用 W 2kn N k N WN e 22 j N W e (N / 2)1 x[2n]W 2 j (N / 2) e WN / 2 (N / 2)1 kn N/2 W k N n 0 2002.6.27 n 0 2 j N 2 N X(k) x[2n 1]W 2kn N x[2n 1]W kn N /2 n 0 ディジタル信号処理 25 高速Fourier変換の仕組み (N / 2)1 X(k) x[2n]W n 0 G(k) (N / 2)1 kn N/2 W (N / 2)1 k N x[2n 1]W kn N /2 n 0 x[2n]W nk N /2 n 0 H(k) を用いて整理 (N / 2)1 x[2n 1]W nk N/2 n 0 X(k) H(k) W G(k) k N 2002.6.27 ディジタル信号処理 26 高速Fourier変換の仕組み X(k) H(k) W G(k) k N WN(N / 2)k e ここで 右の関係を利用して 整理 2 (( N / 2) k ) j N j e j e 2 k N 2 k j N e W Nk k X(k) G(k) W N H (k) X N k G(k) W k H (k) k 0,1, , N 1 N 2 2 2002.6.27 ディジタル信号処理 27 高速Fourier変換の仕組み x[0] x[2] x[4] x[6] x[1] x[3] x[5] x[7] 2002.6.27 X(0) X(1) X(2) X(3) G H W W W -1 -1 -1 -1 W 複素数の積和の回数が36回に減少 ディジタル信号処理 X(4) X(5) X(6) X(7) 28 高速Fourier変換の仕組み x[0] x[4] x[0] x[4] x[2] x[6] DFT (N=2) x[1] x[5] x[3] x[7] DFT (N=2) 2002.6.27 DFT (N=2) DFT (N=2) W W W W ディジタル信号処理 -1 -1 -1 -1 W G(0) G(1) G(2) G(3) -1 H(0) H(1) H(2) H(3) 29 課題 DFTの畳込み法則を、定義と推移法則等を用い て導くこと 実数の信号x[n]とy[n]がある。 x[n]+j y[n] のDFTであるS(k)を、 x[n]のDFTであるX(k)とy[n] のDFTであるY(k)を用いて表せ。 実数の信号のDFTの実部は偶関数、虚部は奇 関数となる。このことを利用して、 x[n]+j y[n]の DFTであるS(k)を用いて、 x[n]のDFTであるX(k) とy[n]のDFTであるY(k)を表せ。 2002.6.27 ディジタル信号処理 30
© Copyright 2024 ExpyDoc