不韋 呂 / 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@4:0b4975fffc90, 2020-12-12 (annotated)

Committer:
MikamiUitOpen
Date:
Sat Dec 12 03:20:09 2020 +0000
Revision:
4:0b4975fffc90
Parent:
3:dc123081d491 
5

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 4:0b4975fffc90 6 // 2020/12/12, 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 4:0b4975fffc90 18 uint32_t shifted = n << (__clz(n) + 1);
MikamiUitOpen 4:0b4975fffc90 19 MBED_ASSERT(shifted == 0); // n が 2 のべき乗であることをチェック
MikamiUitOpen 3:dc123081d491 20
MikamiUitOpen 3:dc123081d491 21 // 回転子の表を作成
MikamiUitOpen 0:982a9acf3a07 22 Complex arg = Complex(0, -6.283185f/N_FFT_);
MikamiUitOpen 0:982a9acf3a07 23 for (int k=0; k<N_FFT_/2; k++)
MikamiUitOpen 0:982a9acf3a07 24 wTable_[k] = exp(arg*(float)k);
MikamiUitOpen 0:982a9acf3a07 25
MikamiUitOpen 3:dc123081d491 26 // ビット逆順のための表を作成
MikamiUitOpen 0:982a9acf3a07 27 uint16_t nShift = __clz(n) + 1;
MikamiUitOpen 0:982a9acf3a07 28 for (int k=0; k<n; k++)
MikamiUitOpen 3:dc123081d491 29 // __rbit(k): ビットの並びを逆にする命令に対応
MikamiUitOpen 3:dc123081d491 30 bTable_[k] = __rbit(k) >> nShift;
MikamiUitOpen 0:982a9acf3a07 31 }
MikamiUitOpen 0:982a9acf3a07 32
MikamiUitOpen 3:dc123081d491 33 // FFT の実行
MikamiUitOpen 3:dc123081d491 34 // 有効な部分 y[0] ～ y[N_FFT_/2]
MikamiUitOpen 3:dc123081d491 35 // それ以外の部分は複素共役になるので，計算をしていない
MikamiUitOpen 0:982a9acf3a07 36 void FftReal::Execute(const float x[], Complex y[])
MikamiUitOpen 0:982a9acf3a07 37 {
MikamiUitOpen 0:982a9acf3a07 38 for (int n=0; n<N_FFT_; n++) u_[n] = x[n];
MikamiUitOpen 0:982a9acf3a07 39
MikamiUitOpen 3:dc123081d491 40 // 最終ステージを除いた部分
MikamiUitOpen 1:559a63853f3f 41 ExcludeLastStage();
MikamiUitOpen 0:982a9acf3a07 42
MikamiUitOpen 3:dc123081d491 43 // 最終ステージ
MikamiUitOpen 0:982a9acf3a07 44 y[0] = u_[0] + u_[1];
MikamiUitOpen 0:982a9acf3a07 45 y[N_FFT_/2] = u_[0] - u_[1];
MikamiUitOpen 3:dc123081d491 46 for (int k=2; k<N_FFT_; k+=2) u_[k] = u_[k] + u_[k+1];
MikamiUitOpen 0:982a9acf3a07 47
MikamiUitOpen 3:dc123081d491 48 // ビット逆順の並べ替え
MikamiUitOpen 3:dc123081d491 49 for (int k=1; k<N_FFT_/2; k++) y[k] = u_[bTable_[k]];
MikamiUitOpen 0:982a9acf3a07 50 }
MikamiUitOpen 0:982a9acf3a07 51
MikamiUitOpen 3:dc123081d491 52 // IFFT の実行
MikamiUitOpen 3:dc123081d491 53 // このクラスで計算された FFT の結果の IFFT を計算する
MikamiUitOpen 4:0b4975fffc90 54 // 実行結果 x[0] ～ x[N_FFT_-1]
MikamiUitOpen 0:982a9acf3a07 55 void FftReal::ExecuteIfft(const Complex y[], float x[])
MikamiUitOpen 0:982a9acf3a07 56 {
MikamiUitOpen 0:982a9acf3a07 57 int half = N_FFT_/2;
MikamiUitOpen 0:982a9acf3a07 58
MikamiUitOpen 0:982a9acf3a07 59 for (int n=0; n<=half; n++) u_[n] = y[n];
MikamiUitOpen 0:982a9acf3a07 60 for (int n=half+1; n<N_FFT_; n++)
MikamiUitOpen 3:dc123081d491 61 u_[n] = conj(y[N_FFT_-n]); // 後半は複素共役になっているものとする
MikamiUitOpen 0:982a9acf3a07 62
MikamiUitOpen 3:dc123081d491 63 // 最終ステージを除いた部分
MikamiUitOpen 1:559a63853f3f 64 ExcludeLastStage();
MikamiUitOpen 0:982a9acf3a07 65
MikamiUitOpen 3:dc123081d491 66 // 最終ステージとビット逆順の並べ替え処理
MikamiUitOpen 0:982a9acf3a07 67 x[0] = N_INV_*(u_[0].real() + u_[1].real());
MikamiUitOpen 0:982a9acf3a07 68 x[half] = N_INV_*(u_[0].real() - u_[1].real());
MikamiUitOpen 0:982a9acf3a07 69
MikamiUitOpen 0:982a9acf3a07 70 for (int n=2; n<N_FFT_; n+=2)
MikamiUitOpen 0:982a9acf3a07 71 {
MikamiUitOpen 0:982a9acf3a07 72 float un = u_[n].real();
MikamiUitOpen 0:982a9acf3a07 73 float un1 = u_[n+1].real();
MikamiUitOpen 0:982a9acf3a07 74 x[Index(n)] = N_INV_*(un + un1);
MikamiUitOpen 0:982a9acf3a07 75 x[Index(n+1)] = N_INV_*(un - un1);
MikamiUitOpen 0:982a9acf3a07 76 }
MikamiUitOpen 0:982a9acf3a07 77 }
MikamiUitOpen 0:982a9acf3a07 78
MikamiUitOpen 3:dc123081d491 79 // 最終ステージを除いた処理
MikamiUitOpen 1:559a63853f3f 80 void FftReal::ExcludeLastStage()
MikamiUitOpen 0:982a9acf3a07 81 {
MikamiUitOpen 0:982a9acf3a07 82 uint16_t nHalf = N_FFT_/2;
MikamiUitOpen 0:982a9acf3a07 83 for (int stg=1; stg<N_FFT_/2; stg*=2)
MikamiUitOpen 0:982a9acf3a07 84 {
MikamiUitOpen 0:982a9acf3a07 85 uint16_t nHalf2 = nHalf*2;
MikamiUitOpen 0:982a9acf3a07 86 for (int kp=0; kp<N_FFT_; kp+=nHalf2)
MikamiUitOpen 0:982a9acf3a07 87 {
MikamiUitOpen 0:982a9acf3a07 88 uint16_t kx = 0;
MikamiUitOpen 0:982a9acf3a07 89 for (int k=kp; k<kp+nHalf; k++)
MikamiUitOpen 0:982a9acf3a07 90 {
MikamiUitOpen 4:0b4975fffc90 91 // バタフライ演算
MikamiUitOpen 0:982a9acf3a07 92 Complex uTmp = u_[k+nHalf];
MikamiUitOpen 0:982a9acf3a07 93 u_[k+nHalf] = (u_[k] - uTmp)*wTable_[kx];
MikamiUitOpen 0:982a9acf3a07 94 u_[k] = u_[k] + uTmp;
MikamiUitOpen 0:982a9acf3a07 95 kx = kx + stg;
MikamiUitOpen 0:982a9acf3a07 96 }
MikamiUitOpen 0:982a9acf3a07 97 }
MikamiUitOpen 0:982a9acf3a07 98 nHalf = nHalf/2;
MikamiUitOpen 4:0b4975fffc90 99 }
MikamiUitOpen 0:982a9acf3a07 100 }
MikamiUitOpen 4:0b4975fffc90 101 }