ビット反転アルゴリズム

2020年11月19日Delphi,Programing,アルゴリズム

数年前にFFTライブラリのためにビット反転処理を書いた。
ただ、FFTサンプル数を増やしたときに崩壊してしまっていたので、サンプル数に制限をかけてたわけですが
一思いにこの辺の処理を一新することにした。

Contents

1. ビット反転とは
2. ビット反転アルゴリズムについて
3. Delphiで書く

ビット反転とは

2進数で表した数字の上位、下位ビットをまんまひっくり返す処理のこと。
例えば4Bitだと

10進数	2進数	ビット反転
0	0000	0000
1	0001	1000
2	0010	0100
：	：	：
14	1110	0111
15	1111	1111

てな具合。各ビットを単純にNotするわけではないので、ひと工夫が必要。

ビット反転アルゴリズムについて

FFTサンプル数分のビット反転をしたいので、FFTサンプル数=Nは2のべき乗であるとします。
ここでN=8の場合
1. 0からスタートし、0は反転しても0
　これを配列として記録していくと[0]
2. 配列の各要素にN/2を足したものを追加する
　現在、要素は[0]のみなので0+N/2、つまり0+8/2=4となる
　今の配列は[0,4]
3. 配列の各要素にN/4を足したものを追加する
　[0,4]にN/4=2を足す
　今の配列は[0,4,2,6]
4. 配列の各要素にN/8を足したものを追加する
　今の配列は[0,4,2,6,1,5,3,7]
これでビット反転が完了している。
結果を確認する。
N=8で、8=2^3なので3ビットである。

10進数	2進数	ビット反転	ビット反転10進数
0	000	0000	0
1	001	100	4
2	010	010	2
3	011	110	6
4	100	001	1
5	101	101	5
6	110	011	3
7	111	111	7

と、処理結果と一致している。

つまり、
0を基準として、N/2^XがN/Nとなるまで、各要素にN/2^Xを足したものを追加していくだけでいい。

Delphiで書く

上記の処理をプログラムとして落とし込むとこうなる。

procedure BitRevers(FFTSample:UInt32);
var
I, X : Integer;
point : UInt32;
BitRevArray    : Array
of UInt32;
PowerN         : UInt16;
begin
PowerN     := Floor(Ln(FFTSample) / Ln(2));
SetLength(BitRevArray, FFTSample);
BitRevArray[0] := 0;
for I := 1
to PowerN do
begin
point := Floor(Power(2,I));
for X := (point div
2) to point -1
do
BitRevArray[X] := BitRevArray[X - (point div
2)] + (FFTSample div point);
end;
end;