いぬおさんのおもしろ数学実験室

おいしい紅茶でも飲みながら数学、物理、工学、プログラミング、そして読書を楽しみましょう

FFTに関連して、ビットリバース(2進数の並びを逆転する)についての事実をひとつ

 今、FFT高速フーリエ変換)の原理を整理しています。勉強のための書籍としてすでに紹介の記事を書きました。

www.omoshiro-suugaku.com

分かりやすく素晴らしい本ですが、どこからビットリバースがでてくるのか、については触れていません。ビットリバースとは……2進数で例えば

f:id:Inuosann:20220215124813p:plain

という数に対し、並びを逆転して

f:id:Inuosann:20220215124845p:plain

という2進数を作る操作のことです。FFTの話には大抵これが出てきます。FFTで計算する途中で(というか、最後に)ビットリバースが必要になるのです。具体的にどんな感じなのか説明しておきましょう。FFTというのは先の記事でも書いたとおり、DFT(離散フーリエ変換)という周期信号の処理に、高速化の工夫を施したロジックです。データ数は2の累乗に限られます。ごめんなさい、FFTに触れたことのない方は以下、意味不明かも。

 8個のデータ、

f:id:Inuosann:20220215131429p:plain

から8個の離散フーリエ係数、

f:id:Inuosann:20220215131521p:plain

を求めるのがFFTの仕事です。離散フーリエ係数はデータに含まれるいろいろな周波数成分の、言わば「多さ」を表しているのでした。

 FFTの本ではよく次のような図が出てきます。n=8(データ数)のときのFFTの図です。

f:id:Inuosann:20220215131115p:plain

もとの8個のデータを、添え字0~3、4~7の2グループに分け、事前処理を施してn=4のFFTを2回実行します。するとn=8のFFTの結果が求まりますが、得られる離散フーリエ係数の添え字は番号順、0,1,2,3,4,5,6,7 にはなっていません。

f:id:Inuosann:20220215132253p:plain

が得られるのです。不思議なことに、添え字の 0,4,2,6,1,5,3,7 はそれぞれ、0,1,2,3,4,5,6,7 を3桁の2進数で表してからビットリバースしたものです。例えば

f:id:Inuosann:20220215132647p:plain

なので、ビットリバースして

f:id:Inuosann:20220215132720p:plain

というように!!

 どうしてこんなことが起こるのでしょうか。そういう風になるんだからいいでしょ、というのもまあ姿勢のひとつではありますが、これを「気持ち悪い」と思う人もいることでしょう。「n=16のときも、n=32でも成立する」と断言はできないわけです。この点(なぜ出力される離散フーリエ係数の添え字はもとの添え字のビットリバースになるのか)について分かりやすく解説している書籍は見かけません(存在するのかも知れませんが、FFTの本は多くて、全部は確認できません……)。

 厳密には数学的帰納法などで示せるでしょう。あるいはそうまでしなくても、n=8のFFTで何が起こっているのか把握できれば「ああ、これで数学的帰納法の証明のポイントは見えた!」と納得できます。その説明のなかで使う基本的な事実が次です。

 

m = 0, 1, 2, 3 を3桁の2進数で表してビットリバースするとそれぞれ m' = 0, 4, 2, 6 になるが、このとき m + 4 を3桁の2進数で表してビットリバースするとそれぞれ(m + 4)' = 1, 5, 3, 7 になる

 

当然と言えば当然。mに4を加えるとは、2進数で3桁目を1にすること。ビットリバースすれば2進数で末位は1になる(もとの偶数0, 4, 2, 6 より1大きい奇数、1, 5, 3, 7 になる)のです。例えば m = 2 だとすると

f:id:Inuosann:20220215135559p:plain

ビットリバースすると

f:id:Inuosann:20220215135936p:plain

になる、ということです。

 

まとまったら「どうしてFFTの最後でビットリバースが必要なのか」みたいな記事を書きます。