ビットの反転
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/08 05:20 UTC 版)
上記の説明で、 N = Q k ( P = Q k − 1 ) {\displaystyle N=Q^{k}(P=Q^{k-1})} の場合、N = Qk 個のデータ f ( q Q k − 1 + p ) {\displaystyle f(qQ^{k-1}+p)} から、N = Qk 個の計算結果 f 1 ( p , r ) = exp ( − 2 π i p r Q k ) ∑ q = 0 Q − 1 f ( q Q k − 1 + p ) exp ( − 2 π i r q Q ) {\displaystyle f_{1}(p,r)=\exp \left(-2\pi i{\frac {pr}{Q^{k}}}\right)\sum _{q=0}^{Q-1}f(qQ^{k-1}+p)\exp \left(-2\pi i{\frac {rq}{Q}}\right)} を計算する場合に、メモリの節約のため、0 ≤ q ≤ Q − 1 と 0 ≤ r ≤ Q − 1 を利用し、計算結果 f 1 ( p , r ) {\displaystyle f_{1}(p,r)} を元データ f ( r Q k − 1 + p ) {\displaystyle f(rQ^{k-1}+p)} のあった場所に格納することが多い。これが次の次数 Qk − 1 でも繰り返されるため、 p = q 2 Q k − 2 + p 2 {\displaystyle p=q_{2}Q^{k-2}+p_{2}} とすると、次の次数の計算結果 f 2 ( p 2 , q 2 , q ) {\displaystyle f_{2}(p_{2},q_{2},q)} は f ( q Q k − 1 + q 2 Q k − 2 + p 2 ) {\displaystyle f(qQ^{k-1}+q_{2}Q^{k-2}+p_{2})} のあった場所に格納される。繰り返せば、 t = q 1 Q k − 1 + q 2 Q k − 2 + ⋯ + q k {\displaystyle t=q_{1}Q^{k-1}+q_{2}Q^{k-2}+\cdots +q_{k}} とすると、計算結果 f k ( p k , q k , q k − 1 , … , q 2 , q 1 ) {\displaystyle f_{k}(p_{k},q_{k},q_{k-1},\dots ,q_{2},q_{1})} は f ( q 1 Q k − 1 + q 2 Q k − 2 + ⋯ + q k − 1 Q + p k ) {\displaystyle f(q_{1}Q^{k-1}+q_{2}Q^{k-2}+\cdots +q_{k-1}Q+p_{k})} のあった場所に格納される。 一方、 F ( s Q + r ) = ∑ p = 0 Q k − 1 − 1 exp ( − 2 π i s p Q k − 1 ) f 1 ( p , r ) {\displaystyle F(sQ+r)=\sum _{p=0}^{Q^{k-1}-1}\exp \left(-2\pi i{\frac {sp}{Q^{k-1}}}\right)f_{1}(p,r)} を、r を固定し s を変数とした Qk − 1 次離散フーリエ変換と見なして、 s = s 2 Q + r 2 {\displaystyle s=s_{2}Q+r_{2}} とすると、 F ( s 2 Q 2 + r 2 Q + r ) = ∑ p 2 = 0 Q k − 2 − 1 exp ( − 2 π i s 2 p 2 Q k − 2 ) f 2 ( p 2 , r 2 , r ) {\displaystyle F(s_{2}Q^{2}+r_{2}Q+r)=\sum _{p_{2}=0}^{Q^{k-2}-1}\exp \left(-2\pi i{\frac {s_{2}p_{2}}{Q^{k-2}}}\right)f_{2}(p_{2},r_{2},r)} となる。繰り替えせば、 F ( s k Q k + r k Q k − 1 + ⋯ + r 2 Q + r 1 ) = ∑ p k = 0 Q k − k − 1 exp ( − 2 π i s k p k Q k − k ) f k ( p k , r k , r k − 1 , … , r 2 , r 1 ) {\displaystyle F(s_{k}Q^{k}+r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1})=\sum _{p_{k}=0}^{Q^{k-k}-1}\exp \left(-2\pi i{\frac {s_{k}p_{k}}{Q^{k-k}}}\right)f_{k}(p_{k},r_{k},r_{k-1},\dots ,r_{2},r_{1})} となるが、左辺について s k Q k + r k Q k − 1 + ⋯ + r 2 Q + r 1 < Q k {\displaystyle s_{k}Q^{k}+r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1}<Q^{k}} より sk = 0, また右辺について Q k − k − 1 = 0 {\displaystyle Q^{k-k}-1=0} より pk = 0。このため、 F ( r k Q k − 1 + ⋯ + r 2 Q + r 1 ) = f k ( 0 , r k , r k − 1 , … , r 2 , r 1 ) . {\displaystyle F(r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1})=f_{k}(0,r_{k},r_{k-1},\dots ,r_{2},r_{1}).} これは f ( r 1 Q k − 1 + r 2 Q k − 2 + ⋯ + r k − 1 Q + r k ) {\displaystyle f(r_{1}Q^{k-1}+r_{2}Q^{k-2}+\cdots +r_{k-1}Q+r_{k})} のあった場所に格納されている。 このように、求める解 F ( r k Q k − 1 + ⋯ + r 2 Q + r 1 ) {\displaystyle F(r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1})} が f ( r 1 Q k − 1 + r 2 Q k − 2 + ⋯ + r k − 1 Q + r k ) {\displaystyle f(r_{1}Q^{k-1}+r_{2}Q^{k-2}+\cdots +r_{k-1}Q+r_{k})} のあった場所に格納されていることを、ビット反転と言う。これは、Q 進法で表示した場合、 r k Q k − 1 + ⋯ + r 2 Q + r 1 {\displaystyle r_{k}Q^{k-1}+\cdots +r_{2}Q+r_{1}} は ( r k r k − 1 … r 2 r 1 ) Q {\displaystyle (r_{k}r_{k-1}\dots r_{2}r_{1})_{Q}} となるのに対し、 r 1 Q k − 1 + r 2 Q k − 2 + ⋯ + r k − 1 + r k {\displaystyle r_{1}Q^{k-1}+r_{2}Q^{k-2}+\cdots +r_{k-1}+r_{k}} は逆から読んだ ( r 1 r 2 … r k − 1 r k ) Q {\displaystyle (r_{1}r_{2}\dots r_{k-1}r_{k})_{Q}} となるためである。
※この「ビットの反転」の解説は、「高速フーリエ変換」の解説の一部です。
「ビットの反転」を含む「高速フーリエ変換」の記事については、「高速フーリエ変換」の概要を参照ください。
- ビットの反転のページへのリンク
