ビット反転順列
0から255までの整数とそのビット反転を座標とするハマースリー集合

応用数学において、ビット反転順列とは、 2のべき乗である の要素の列の順列である。これは、列の要素を からまでの数値でインデックス化し、これらの数値をそれぞれ2進表現（長さがちょうど になるようにパディング）で表し、各項目を、同じビットを逆順に表す項目にマッピングすることで定義される。 n{\displaystyle n}n＝2け{\displaystyle n=2^{k}}0{\displaystyle 0}n−1{\displaystyle n-1}け{\displaystyle k}

同じ順列を 2 回繰り返すと、項目の元の順序に戻るため、ビット反転順列は反転です。

この順列は、単純なインデックス計算のみを実行することで、任意のシーケンスに線形時間で適用できます。これは、低矛盾シーケンスの生成や高速フーリエ変換の評価に応用されています。

例

8つの文字からなるシーケンスabcdefgh を考えてみましょう。これらのインデックスは2進数で000、001、010、011、100、101、110、111です。これを反転すると、000、100、010、110、001、101、011、111となります。したがって、位置000の文字aは同じ位置（000）にマッピングされ、位置001の文字bは5番目の位置（100番目の文字）にマッピングされます。以下同様に、新しいシーケンスaecgbfdhが生成されます。この新しいシーケンスに対して同じ順列を繰り返すと、開始シーケンスに戻ります。

インデックス番号を10進数で書くと（ただし、順列の開始位置は1から始まるのが一般的だが、上述と同様に0から始まる）、 の項目のビット反転順列は次のようになる。[ 1 ]n＝2け{\displaystyle n=2^{k}}け＝0、1、2、3、…{\displaystyle k=0,1,2,3,\dots }

け{\displaystyle k}n＝2け{\displaystyle n=2^{k}}順列
010
120 1
240 2 1 3
380 4 2 6 1 5 3 7
4160 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

この数列の各順列は、2つの数列を連結することによって生成できます。1つは前の順列の値を2倍にしたもの、もう1つは前の数列の各値を1ずつ増やしたものです。例えば、長さ4の順列0 2 1 3を2倍にすると0 4 2 6、1を加えると1 5 3 7になります。そして、これら2つの数列を連結すると、長さ8の順列0 4 2 6 1 5 3 7が得られます。[ 2 ]

一般化

基数 表現への一般化、すなわち、 、 への一般化は、各要素のインデックスの基数桁を反転させて、置換後のインデックスを得る桁反転順列である。同じ考え方は、混合基数数体系にも一般化できる。このような場合、桁反転順列は、各項目の桁と数体系の基数を同時に反転させ、反転後の各桁がその基数によって定義された範囲内に収まるようにする必要がある。[ 3 ]b{\displaystyle b}b>2{\displaystyle b>2}n＝bけ{\displaystyle n=b^{k}}b{\displaystyle b}

ビット反転順列を一般化し、そのインデックスのバイナリ表現内で連続するビットブロックを反転する順列は、2つの等しい長さのデータシーケンスをその場でインターリーブするために使用できます。[ 4 ]

ビット反転順列には、任意長のシーケンスへの拡張が2つあります。これらの拡張は、長さが2のべき乗であるシーケンスのビット反転と一致し、シーケンス内の隣接する要素を分離してKaczmarzアルゴリズムを効率的に動作させることを目的とします。最初の拡張は効率的な順序付けと呼ばれ、[ 5 ]合成数に適用され、数を素数に分解することを基盤としています。

2つ目の拡張はEBR（拡張ビット反転）と呼ばれ、ビット反転と原理的には似ています。サイズ の配列が与えられると、EBRは範囲内の数値の順列を線形時間で配列に格納します。順列内の連続する数値は、少なくとも の位置で区切られます。[ 6 ]n{\displaystyle n}0…n−1{\displaystyle 0\ldots n-1}⌊n/4⌋{\displaystyle \lfloor n/4\rfloor }

アプリケーション

ビット反転は基数2のCooley-Tukey FFTアルゴリズムにおいて最も重要であり、アルゴリズムの再帰段階はインプレースで動作し、入力または出力のビット反転を伴う。同様に、混合基数Cooley-Tukey FFTでは、混合基数桁反転が発生する。[ 7 ]

ビット反転順列は分散計算における下限値を考案するためにも使われてきた。 [ 8 ]

単位区間内の数値の低矛盾シーケンスである Van der Corput シーケンスは、ビット反転順列のインデックスを二項有理数の固定小数点 2 進表現として再解釈することによって形成されます。

ビット反転順列は、動的データ構造の下限値を求める際によく用いられる。例えば、特定の仮定のもと、これらの値を持つ任意の二分探索木において、とを含む整数を検索するコストは、これらの数値をビット反転順に検索した場合である。この上限は、アクセスごとにノードの順序を変更できるスプレー木のような木にも適用される。 [ 9 ]0{\displaystyle 0}n−1{\displaystyle n-1}Ω（nログ⁡n）{\displaystyle \Omega (n\log n)}

アルゴリズム

高速フーリエ変換アルゴリズムの重要性から、ビット反転順列をシーケンスに適用するための効率的なアルゴリズムが数多く考案されてきた。[ 2 ]

ビット反転順列は反転であるため、要素のペアを交換するだけで（データを別の配列にコピーすることなく）、簡単にインプレースで実行できます。アルゴリズム解析で一般的に使用されるランダムアクセスマシンでは、入力順にインデックスをスキャンし、スキャン中に反転値がより大きな数値であるインデックスに遭遇するたびに交換する単純なアルゴリズムで、線形回数のデータ移動を実行できます。[ 10 ]しかし、各インデックスの反転を計算するには、一定ではないステップ数が必要になる場合があります。代替アルゴリズムでは、単純なインデックス計算のみを使用して、ビット反転順列を線形時間で実行できます。[ 11 ]ビット反転順列は計算の一部として複数回繰り返される可能性があるため、順列を表すために使用されるインデックスデータを計算するアルゴリズムのステップ（たとえば、倍加と連結法を使用する）と、この計算の結果を使用してデータを順列化するステップ（たとえば、データインデックスを順番にスキャンし、スワップされた位置が現在のインデックスよりも大きい場合はスワップを実行するか、より高度なベクトルスキャッターギャザー演算を使用する）を分離すると便利な場合があります。[ 2 ]

これらのアルゴリズムの性能にとってさらに重要なもう一つの考慮事項は、メモリ階層が実行時間に与える影響です。この影響により、メモリのブロック構造を考慮したより洗練されたアルゴリズムは、この単純なスキャンよりも高速になる可能性があります。 [ 2 ] [ 10 ]これらの手法の代替として、メモリに通常順序とビット反転順序の両方でアクセスできる特殊なコンピュータハードウェアがあります。[ 12 ]

高性能コンピューティングの分野では、ビット反転演算の性能向上に大きな注目が集まっています。アーキテクチャを考慮したアルゴリズムの開発は、キャッシュ、TLB、マルチコアプロセッサなどのハードウェアおよびシステムソフトウェアリソースを最適に活用するために不可欠です。[ 13 ]

参考文献

  1. ^ Sloane, N. J. A. (編)、「シーケンス A030109」、整数シーケンスのオンライン百科事典、OEIS Foundation
  2. ^ a b c d Karp, Alan H. (1996)、「ユニプロセッサ上のビット反転」、SIAM Review、38 (1): 1– 26、CiteSeerX 10.1.1.24.2913、doi : 10.1137/1038001、MR 1379039  Karp 氏は、1965 年から 1996 年に彼の調査が発表されるまでの間に開発された、ビット反転のための 30 種類の異なるアルゴリズムを調査し、比較しています。
  3. ^ Elster, Anne C. (1989)、「高速ビット反転アルゴリズム」、IEEE 国際音響・音声・信号処理会議、ICASSP '89、スコットランド、グラスゴー、1989年5月23日～26日、pp.  1099– 1102、doi : 10.1109/ICASSP.1989.266624、S2CID 15028026 
  4. ^ Yang, Qingxuan; Ellis, John; Mamakani, Khalegh; Ruskey, Frank (2013)、「反転を用いたインプレース置換と完全シャッフル」、Information Processing Letters、113 ( 10– 11): 386– 391、arXiv : 1204.1958、doi : 10.1016/j.ipl.2013.02.017、MR 3037467、S2CID 14672841  。
  5. ^ Herman, Gabor T. (2009), 『コンピュータ断層撮影の基礎』（第2版）, ロンドン: Springer, p.  209 , ISBN 978-1-85233-617-2
  6. ^ゴードン、ダン（2017年6月）、「広範囲のランダムサンプリングレートにわたる帯域制限信号の回復のためのデランダム化アプローチ」、数値アルゴリズム、77（4）：1141– 1157、doi：10.1007/s11075-017-0356-3、S2CID 254889989 
  7. ^ B. Gold、CM Rader著『Digital Processing of Signals』（ニューヨーク：McGraw-Hill、1969年）。
  8. ^ Frederickson, Greg N.; Lynch, Nancy A. (1984)、「同期通信がリングのリーダー選出問題に与える影響」（PDF）、第16回ACMコンピューティング理論シンポジウム（STOC '84）の議事録、pp.  493– 503、doi : 10.1145/800057.808719、ISBN 978-0897911337。
  9. ^ウィルバー、ロバート (1989)、「回転による二分探索木へのアクセスの下限値」、第27回コンピュータサイエンスの基礎に関する年次シンポジウム (sfcs 1986)、pp.  61– 70、doi : 10.1109/SFCS.1986.28、ISBN 0-8186-0740-8。
  10. ^ a b Carter, Larry; Gatlin, Kang Su (1998)、「最適なビット反転順列プログラムに向けて」、第39回コンピュータサイエンスの基礎に関する年次シンポジウム (FOCS) の議事録、pp.  544– 553、CiteSeerX 10.1.1.46.9319、doi : 10.1109/SFCS.1998.743505、ISBN  978-0-8186-9172-0、S2CID  14307262。
  11. ^ Jeong, Jechang; Williams, WJ (1990)、「高速再帰ビット反転アルゴリズム」、国際音響・音声・信号処理会議 (ICASSP-90)、第3巻、pp.  1511– 1514、doi : 10.1109/ICASSP.1990.115695、S2CID 122373780 。
  12. ^ Harley, TR; Maheshwaramurthy, GP (2004)、「ビット反転順序で配列をマッピングするためのアドレスジェネレータ」、IEEE Transactions on Signal Processing、52 (6): 1693– 1703、Bibcode : 2004ITSP...52.1693H、doi : 10.1109/TSP.2004.827148、S2CID 10043478 。
  13. ^ Zhang, Zhao; Zhang, Xiaodong (2000)、「ユニプロセッサと共有メモリ型マルチプロセッサにおける高速ビット反転」、SIAM Journal on Scientific Computing、22 (6): 2113– 2134、doi : 10.1137/S1064827599359709、MR 1856305 
「 https://en.wikipedia.org/w/index.php?title=Bit-reversal_permutation&oldid=1320745042」から取得