不韋 呂 / UIT_FFT_Real

FFT for real data using decimation-in-frequency algorithm. 実データに対するFFT．周波数間引きアルゴリズムを使用． このライブラリを登録した際のプログラム： Demo_FFT_IFFT

Dependents:   UIT2_SpectrumAnalyzer F746_SpectralAnalysis_NoPhoto F746_FFT_Speed F746_RealtimeSpectrumAnalyzer ... more

fftReal.cpp@3:dc123081d491, 2020-01-13 (annotated)

Committer:
MikamiUitOpen
Date:
Mon Jan 13 08:54:18 2020 +0000
Revision:
3:dc123081d491
Parent:
2:9649d0e2bb4a
Child:
4:0b4975fffc90
4

Who changed what in which revision?

UserRevisionLine numberNew contents of line
MikamiUitOpen 0:982a9acf3a07 1 //------------------------------------------------------------------------------
MikamiUitOpen 3:dc123081d491 2 // データが実数の場合の FFT class
MikamiUitOpen 3:dc123081d491 3 // FFT 複素共役になる部分は計算しない
MikamiUitOpen 3:dc123081d491 4 // IFFT 複素共役の部分を除いた値から計算する
MikamiUitOpen 3:dc123081d491 5 //
MikamiUitOpen 3:dc123081d491 6 // 2020/01/13, Copyright (c) 2020 MIKAMI, Naoki
MikamiUitOpen 0:982a9acf3a07 7 //------------------------------------------------------------------------------
MikamiUitOpen 0:982a9acf3a07 8
MikamiUitOpen 0:982a9acf3a07 9 #include "fftReal.hpp"
MikamiUitOpen 0:982a9acf3a07 10
MikamiUitOpen 0:982a9acf3a07 11 namespace Mikami
MikamiUitOpen 0:982a9acf3a07 12 {
MikamiUitOpen 3:dc123081d491 13 // コンストラクタ
MikamiUitOpen 0:982a9acf3a07 14 FftReal::FftReal(int16_t n)
MikamiUitOpen 3:dc123081d491 15 : N_FFT_(n), N_INV_(1.0f/n), wTable_(n/2), bTable_(n), u_(n)
MikamiUitOpen 0:982a9acf3a07 16 {
MikamiUitOpen 3:dc123081d491 17 // __clz(): リーディング 0 の数を取得する命令に対応
MikamiUitOpen 0:982a9acf3a07 18 uint32_t shifted = n << (__clz(n)+1);
MikamiUitOpen 0:982a9acf3a07 19
MikamiUitOpen 3:dc123081d491 20 MBED_ASSERT(shifted == 0);
MikamiUitOpen 3:dc123081d491 21
MikamiUitOpen 3:dc123081d491 22 // 回転子の表を作成
MikamiUitOpen 0:982a9acf3a07 23 Complex arg = Complex(0, -6.283185f/N_FFT_);
MikamiUitOpen 0:982a9acf3a07 24 for (int k=0; k<N_FFT_/2; k++)
MikamiUitOpen 0:982a9acf3a07 25 wTable_[k] = exp(arg*(float)k);
MikamiUitOpen 0:982a9acf3a07 26
MikamiUitOpen 3:dc123081d491 27 // ビット逆順のための表を作成
MikamiUitOpen 0:982a9acf3a07 28 uint16_t nShift = __clz(n) + 1;
MikamiUitOpen 0:982a9acf3a07 29 for (int k=0; k<n; k++)
MikamiUitOpen 3:dc123081d491 30 // __rbit(k): ビットの並びを逆にする命令に対応
MikamiUitOpen 3:dc123081d491 31 bTable_[k] = __rbit(k) >> nShift;
MikamiUitOpen 0:982a9acf3a07 32 }
MikamiUitOpen 0:982a9acf3a07 33
MikamiUitOpen 3:dc123081d491 34 // FFT の実行
MikamiUitOpen 3:dc123081d491 35 // 有効な部分 y[0] ～ y[N_FFT_/2]
MikamiUitOpen 3:dc123081d491 36 // それ以外の部分は複素共役になるので，計算をしていない
MikamiUitOpen 0:982a9acf3a07 37 void FftReal::Execute(const float x[], Complex y[])
MikamiUitOpen 0:982a9acf3a07 38 {
MikamiUitOpen 0:982a9acf3a07 39 for (int n=0; n<N_FFT_; n++) u_[n] = x[n];
MikamiUitOpen 0:982a9acf3a07 40
MikamiUitOpen 3:dc123081d491 41 // 最終ステージを除いた部分
MikamiUitOpen 1:559a63853f3f 42 ExcludeLastStage();
MikamiUitOpen 0:982a9acf3a07 43
MikamiUitOpen 3:dc123081d491 44 // 最終ステージ
MikamiUitOpen 0:982a9acf3a07 45 y[0] = u_[0] + u_[1];
MikamiUitOpen 0:982a9acf3a07 46 y[N_FFT_/2] = u_[0] - u_[1];
MikamiUitOpen 3:dc123081d491 47 for (int k=2; k<N_FFT_; k+=2) u_[k] = u_[k] + u_[k+1];
MikamiUitOpen 0:982a9acf3a07 48
MikamiUitOpen 3:dc123081d491 49 // ビット逆順の並べ替え
MikamiUitOpen 3:dc123081d491 50 for (int k=1; k<N_FFT_/2; k++) y[k] = u_[bTable_[k]];
MikamiUitOpen 0:982a9acf3a07 51 }
MikamiUitOpen 0:982a9acf3a07 52
MikamiUitOpen 3:dc123081d491 53 // IFFT の実行
MikamiUitOpen 3:dc123081d491 54 // このクラスで計算された FFT の結果の IFFT を計算する
MikamiUitOpen 3:dc123081d491 55 // 実行結果 x[0] ～ x[N_FFT_]
MikamiUitOpen 0:982a9acf3a07 56 void FftReal::ExecuteIfft(const Complex y[], float x[])
MikamiUitOpen 0:982a9acf3a07 57 {
MikamiUitOpen 0:982a9acf3a07 58 int half = N_FFT_/2;
MikamiUitOpen 0:982a9acf3a07 59
MikamiUitOpen 0:982a9acf3a07 60 for (int n=0; n<=half; n++) u_[n] = y[n];
MikamiUitOpen 0:982a9acf3a07 61 for (int n=half+1; n<N_FFT_; n++)
MikamiUitOpen 3:dc123081d491 62 u_[n] = conj(y[N_FFT_-n]); // 後半は複素共役になっているものとする
MikamiUitOpen 0:982a9acf3a07 63
MikamiUitOpen 3:dc123081d491 64 // 最終ステージを除いた部分
MikamiUitOpen 1:559a63853f3f 65 ExcludeLastStage();
MikamiUitOpen 0:982a9acf3a07 66
MikamiUitOpen 3:dc123081d491 67 // 最終ステージとビット逆順の並べ替え処理
MikamiUitOpen 0:982a9acf3a07 68 x[0] = N_INV_*(u_[0].real() + u_[1].real());
MikamiUitOpen 0:982a9acf3a07 69 x[half] = N_INV_*(u_[0].real() - u_[1].real());
MikamiUitOpen 0:982a9acf3a07 70
MikamiUitOpen 0:982a9acf3a07 71 for (int n=2; n<N_FFT_; n+=2)
MikamiUitOpen 0:982a9acf3a07 72 {
MikamiUitOpen 0:982a9acf3a07 73 float un = u_[n].real();
MikamiUitOpen 0:982a9acf3a07 74 float un1 = u_[n+1].real();
MikamiUitOpen 0:982a9acf3a07 75 x[Index(n)] = N_INV_*(un + un1);
MikamiUitOpen 0:982a9acf3a07 76 x[Index(n+1)] = N_INV_*(un - un1);
MikamiUitOpen 0:982a9acf3a07 77 }
MikamiUitOpen 0:982a9acf3a07 78 }
MikamiUitOpen 0:982a9acf3a07 79
MikamiUitOpen 3:dc123081d491 80 // 最終ステージを除いた処理
MikamiUitOpen 1:559a63853f3f 81 void FftReal::ExcludeLastStage()
MikamiUitOpen 0:982a9acf3a07 82 {
MikamiUitOpen 0:982a9acf3a07 83 uint16_t nHalf = N_FFT_/2;
MikamiUitOpen 0:982a9acf3a07 84 for (int stg=1; stg<N_FFT_/2; stg*=2)
MikamiUitOpen 0:982a9acf3a07 85 {
MikamiUitOpen 0:982a9acf3a07 86 uint16_t nHalf2 = nHalf*2;
MikamiUitOpen 0:982a9acf3a07 87 for (int kp=0; kp<N_FFT_; kp+=nHalf2)
MikamiUitOpen 0:982a9acf3a07 88 {
MikamiUitOpen 0:982a9acf3a07 89 uint16_t kx = 0;
MikamiUitOpen 0:982a9acf3a07 90 for (int k=kp; k<kp+nHalf; k++)
MikamiUitOpen 0:982a9acf3a07 91 {
MikamiUitOpen 0:982a9acf3a07 92 // Butterfly operation
MikamiUitOpen 0:982a9acf3a07 93 Complex uTmp = u_[k+nHalf];
MikamiUitOpen 0:982a9acf3a07 94 u_[k+nHalf] = (u_[k] - uTmp)*wTable_[kx];
MikamiUitOpen 0:982a9acf3a07 95 u_[k] = u_[k] + uTmp;
MikamiUitOpen 0:982a9acf3a07 96 kx = kx + stg;
MikamiUitOpen 0:982a9acf3a07 97 }
MikamiUitOpen 0:982a9acf3a07 98 }
MikamiUitOpen 0:982a9acf3a07 99 nHalf = nHalf/2;
MikamiUitOpen 0:982a9acf3a07 100 }
MikamiUitOpen 0:982a9acf3a07 101 }
MikamiUitOpen 3:dc123081d491 102 }