図はn=8の場合だけど、3段(=log[2]8)のバタフライ (3回の計算)で処理してる。と言われた

図はn=8の場合だけど、3段(=log[2]8)のバタフライ
(3回の計算)で処理してる。と言われたのですが
3段(3回の計算)ではなく4段(4回の計算)ではないでしょうか？

赤で囲った部分がバタフライ演算の処理ですよね？
なぜ3段(3回の計算)なのでしょうか？

質問者からの補足コメント

• すいません。赤で囲った部分の画像です。
  赤で囲った部分が4つなので、4段(4回)の計算をしていると思っています。

  
    補足日時：2022/03/25 11:59

No.4 ベストアンサー 回答者： stomachman 回答日時： 2022/03/25 12:15

回答を丁寧に読みなさいよ。

ほら3段です。

この回答へのお礼

なるほど、nは処理前のデータの量で、nを8とした時のバタフライ数は4組で、頂いた画像のように3段(あるいは3回)(=log[2]8)のバタフライ演算だと解りました。

どうもありがとうございます。

お礼日時：2022/03/25 14:34

No.3 回答者： 都の西北我瀬駄の隣バカ田大学危機管理学科 回答日時： 2022/03/24 22:49

第1段目　N = 8　バタフライは1ブロック

第2段目　N = 4　バタフライは2ブロック
第3段目　N = 2　バタフライは4ブロック
※N = 2 の回転子は W^0 = 1 と -W^0 = -1 だけなので、掛け算なしのバタフライとなる。

No.2 回答者： Tacosan 回答日時： 2022/03/24 21:38

「赤で囲った部分」ってどこ? そして「4段(4回の計算)」と考えた根拠は何?

No.1 回答者： stomachman 回答日時： 2022/03/24 21:25

たとえばx(0)からX(5)に至る計路上で何回の演算が行われるか。

たどってみれば分かる通り、3回でしょ。同様に、どこからどこへ行くんでも3回です。