今、FFT（高速フーリエ変換）の原理を整理しています。勉強のための書籍としてすでに紹介の記事を書きました。
分かりやすく素晴らしい本ですが、どこからビットリバースがでてくるのか、については触れていません。ビットリバースとは……2進数で例えば
という数に対し、並びを逆転して
という2進数を作る操作のことです。FFTの話には大抵これが出てきます。FFTで計算する途中で（というか、最後に）ビットリバースが必要になるのです。具体的にどんな感じなのか説明しておきましょう。FFTというのは先の記事でも書いたとおり、DFT（離散フーリエ変換）という周期信号の処理に、高速化の工夫を施したロジックです。データ数は2の累乗に限られます。ごめんなさい、FFTに触れたことのない方は以下、意味不明かも。
8個のデータ、
から8個の離散フーリエ係数、
を求めるのがFFTの仕事です。離散フーリエ係数はデータに含まれるいろいろな周波数成分の、言わば「多さ」を表しているのでした。
FFTの本ではよく次のような図が出てきます。n=8（データ数）のときのFFTの図です。
もとの8個のデータを、添え字0～3、4～7の2グループに分け、事前処理を施してn=4のFFTを2回実行します。するとn=8のFFTの結果が求まりますが、得られる離散フーリエ係数の添え字は番号順、0,1,2,3,4,5,6,7 にはなっていません。
が得られるのです。不思議なことに、添え字の 0,4,2,6,1,5,3,7 はそれぞれ、0,1,2,3,4,5,6,7 を3桁の2進数で表してからビットリバースしたものです。例えば
なので、ビットリバースして
というように！！
どうしてこんなことが起こるのでしょうか。そういう風になるんだからいいでしょ、というのもまあ姿勢のひとつではありますが、これを「気持ち悪い」と思う人もいることでしょう。「n=16のときも、n=32でも成立する」と断言はできないわけです。この点（なぜ出力される離散フーリエ係数の添え字はもとの添え字のビットリバースになるのか）について分かりやすく解説している書籍は見かけません（存在するのかも知れませんが、FFTの本は多くて、全部は確認できません……）。
厳密には数学的帰納法などで示せるでしょう。あるいはそうまでしなくても、n=8のFFTで何が起こっているのか把握できれば「ああ、これで数学的帰納法の証明のポイントは見えた！」と納得できます。その説明のなかで使う基本的な事実が次です。
ｍ = 0, 1, 2, 3 を3桁の2進数で表してビットリバースするとそれぞれ m' = 0, 4, 2, 6 になるが、このとき m + 4 を3桁の2進数で表してビットリバースするとそれぞれ（m + 4）' = 1, 5, 3, 7 になる
当然と言えば当然。ｍに4を加えるとは、2進数で3桁目を1にすること。ビットリバースすれば2進数で末位は1になる（もとの偶数0, 4, 2, 6 より1大きい奇数、1, 5, 3, 7 になる）のです。例えば m = 2 だとすると
ビットリバースすると
になる、ということです。
まとまったら「どうしてFFTの最後でビットリバースが必要なのか」みたいな記事を書きます。
