FFTのFPGAによる実装

[←]　[↑]　[→]

---

Cooley-TukeyのアルゴリズムをFPGAに実装することを考える。ただし全RTLコードを書くと長くなるので、ポイントとなるインデックス生成部を説明する。

◇

構造は、バタフライ演算器(butterfly)が1個だけの最も簡単な場合を考え、作業領域のデュアルポートRAM(data_ram)、係数ROM(coef_rom)、インデックス生成部(index_generator)を設ける。

動作は、次のようになる。

(1) 入力データをビットリバース順に並べ替えながらRAMに書き込む。

書き込みがビットリバース順で、最初のステージの読み出しは自然順なので、(N/2+1)ワード以上入力するまでは最初のステージは開始できない。簡単にするには、全ワードを書き込んだ後に最初のステージを開始すればよい。

(2) 各ステージでは、RAMからデータを読み出して、バタフライ演算器を通して、RAMの同じアドレスへ書き戻す。

バタフライ演算は2ワードの演算であるのに対して、RAMは1ワードずつしかアクセスできないのでバッファリングが必要になるが、詳細は後で説明する。また、アドレス生成もステージごとに異なり複雑なので後で説明する。現ステージの読み出しが終わったら次ステージに読み出しを開始する。実際にはRAMの読み出しから書き込みまでレイテンシがあるので、次ステージの読み出しをすぐに開始してよいのか気になるが、フローグラフを見るとわかるように各ステージでの最後の書き込みアドレスは先頭から(N/2)番目であり、読み出しは先頭アドレスから開始するので、レイテンシ＜(N/2)であれば書き込みと読み出しのアドレスが重なることはない。

(3) 最終ステージの読み出しが終わったら、RAMから自然順にデータを読み出してそのまま出力する。

◇◇

次に、バタフライ演算器の入出力をバッファリングする方法を説明する。

バタフライ演算は2ワードの演算であるのに対して、RAMは1ワードずつしかアクセスできないので、順に読み出した2ワードをバッファリングする必要がある。回路は次のようにすればよく、

タイミングチャートを書くと、RAMから読み出した0番目と1番目のワードが横から縦になって、バタフライ演算後に縦から横に戻る様子がわかる。なお、読み出しから書き込みまでのレイテンシは、(バタフライ演算器のレイテンシ)+2になるので、ライト側の制御信号は、リード側の制御信号をこの分だけ遅らせる必要がある。

◇◇◇

最後に、いちばん面倒なインデックス生成方法を説明する。

まず、データ入力時はビットリバース順に並べ替えるが、ソフトウェアと違ってFPGAではアドレスのビットを並び替えて書けばよいので簡単である。

/* データ入力数のカウンタ */

always @(posedge clk or negedge rst_n) begin

  if(~rst_n)

    din_count[M-1:0] <= {M{1'd0}};

  else

    din_count[M-1:0] <= (din_en)? din_count+1'b1 : {M{1'd0}};

end

/* RAMのライトアドレス */

assign wadr = (din_en)?

    {din_count[0],din_count[1],...,din_count[M-1]}

   : (演算時のradrを遅らせたもの);

次に、各ステージでは、前項のインデックスnをビットリバース順から自然な順番に振り直したフローグラフで考えればよい。

これの漸化式は1次元配列に直して次のように書けた。

この漸化式のインデックスをよく見ると、nとkを１つのカウンタ

の上位と下位として

と対応づければよいことに気づく。

こうすると、係数のインデックスは

データのインデックスは

となり、2^mのビットは0,1を繰り返すサブインデックス(subidx)とすればよい。このサブインデックスは上記のバタフライ演算器のsel信号にもなる。

N=8だと小さすぎてわかりにくいので、N=16,M=log₂16=4の場合についてVerilogでコードを書くと、次のとおりになる。

/* インデックスのカウンタ */

always @(posedge clk or negedge rst_n) begin

  if(~rst_n) begin

    subidx <= 1'd0;

    idx <= 'd0;

  end else if(演算中) begin

    subidx <= ~subidx;

    idx <= (subidx==1'b1)? idx + 1'b1 : idx;

  end else begin

    subidx <= 1'd0;

    idx <= 'd0;

  end

end

/* 係数ROMのアドレス */

assign coef_adr = rom_idx(stage,idx);

function[2:0] rom_idx(input[1:0] stage,input[3:0] idx);

  case(stage)

  2'd0: rom_idx = 3'd0;

  2'd1: rom_idx = {idx[0],2'd0};

  2'd2: rom_idx = {idx[1:0],1'd0};

  2'd3: rom_idx = {idx[2:0]};

  endcase

endfunction

/* データRAMのアドレス */

assign radr = ram_idx(stage,idx);

function[3:0] ram_idx(input[1:0] stage,input[3:0] idx);

  case(stage)

  2'd0: ram_idx = {idx[2:0],subidx};

  2'd1: ram_idx = {idx[2:1],subidx,idx[0]};

  2'd1: ram_idx = {idx[2],subidx,idx[1:0]};

  2'd3: ram_idx = {subidx,idx[2:0]};

  endcase

endfunction

◇◇◇◇

N点のFFTの回路ができると、これを使ってN/2点のFFTを実行するのは簡単で、データを2個とびに間引けばよいので上記のインデックスのカウンタidxのステップを1から2に変更するだけでよい。N/4点のFFTを実行するのも同様にしてできる。

---

[←]　[↑]　[→]