まずδswap. 下の図のxはビット列で, そのブロックAとC, BとDを交換し, x''としたい. 交換するブロックの長さはそれぞれ等しく, ブロック間の距離δはすべて等しい. その方法は, まずxを右にδ桁シフトしxと排他和をとり, 右側のブロックの形111...1でマスクし, yとする. ABA⊕Bのこと. xとyの排他和をx'とする. yを左にδ桁シフトしx'と排他和をとりx''とする. これをδswapという.
TAOCPではこの話題の前に, ビット列のi番目とj番目を交換したい. 本書の解を見る前に自分の方法を考えよとある. 私の考えはこれと同じであった.
この方法で64ビットのビット列を反転するには, 左右32ビットずつをそれぞれ反転し, 32ビットのブロックを交換する. それには032132のマスクがいる(0が32個並び1が32個並ぶパターンをこう書く). となり同士のビット交換には, ...010101のマスクがいる.
2kビットの0と2kビットの1で出来た(つまり...02k12k)長さ2dビットのマスクをμd,kと書く. 上の32ビットごとのマスクはμ6,5であり, ...010101はμ6,0である. ...010101は...111111を3で割ればよい. ...00110011は...11111111を5で割る. つまりμd,k=22d-1/22k+1である. これはパラメトロン計算機の頃からの常識である. この応用で1/3は二進法では0.010101..., 十進法の0.1は二進法では0.0001100110011...なのが分かる.
さて64ビットのビット列の任意の置換は, 適切なマスクθk, θ'kを用い,
k=0,1,...,5について x←θkによるxの2kswap.
k=4,3,...,0について x←θ'kによるxの2kswap.
で出来ると書いてある. 64ビットの反転はこの前半だけでよい.
この応用が演習問題52である. 次の各場合の置換のためのθk, θ'kを求めるのだ. もとの各ビット位置をj=(j5j4...j0)2とする.
a)完全シャッフル
jπ=(j0j5j4...j1)2
b)8×8ビット行列の転置
jπ=(j2j1j0j5j4j3)2
c)4×16ビット行列の転置
jπ=(j1j0j5j4j3j2)2
d)FFT(Fast Fourier Transform)に出てくるパターン
jπ=(j0j1j2j3j4j5)2
例を示すのに64ビットに名前をつける．RFC1341のBase64 Alphabetを用い
とする．左端Aの位置が111111, 右端/の位置が000000, 中央fが100000, gが011111である. 従ってa)の場合はgのj5の0が右端へ移動し111110に変わり，62になるからAの右に来る．そう考えると
にしたいのだ．
今は理解が先だから，まず解答を見てみる．
a) 0<=k<5についてθk=μ6,k＆μ6,5, θ'k=μ6,k＆(μ6,k+1⊕μ6,k-1);
θ5=θ4,θ-1=0
と書いてある．
ではやってみよう．64文字はブログの画面では長すぎるので, 32文字のところで分割する. 各マスクの右はシフト数である．
一体どうなったか. まず32ビットシフトの直前までは, 右半分32ビットの反転である. これは簡単. そこで左, 右の32ビットの落ち着き先をみると, Aは63, fは1, /は0, gは62なので, 63-1(奇数のみ) 0-62(偶数のみ)である. 63-1 0-62 と書く. それぞれのブロックを中央で分けると, 落ち着き先は
63-33 31-1 0-30 32-62 [3 2 1 0]. 右の[と]の中はブロック番号. ブロック2と0を交換すると
63-31 32-62 0-30 31-1 になる. クイックソートと同じで, 今後中央を越えての移動はない.
またそれぞれを半分にする.
63-49 47-31 32-46 48-62 0-14 16-30 31-17 15-1 [7 6 5 4 3 2 1 0]
ブロック6と4, 3と1を交換. 左半分は右半分のほとんど鏡像だから, 右半分に注目.
31-17 16-30 0-14 15-1 になる. 半分にする.
31-25 23-17 16-22 24-30 0-6 8-14 15-9 7-1 [7 6 5 4 3 2 1 0]
6と4, 3と1を交換. 右半分に注目.
15-9 8-14 0-6 7-1
半分にする.
15-13 11-9 8-10 12-14 0-2 4-6 7-5 3-1 [7 6 5 4 3 2 1 0]
交換. 右半分を見ると
7-5 4-6 0-2 3-1
で, 文字では cd98/+ef. 次はdと8, /とeを交換 (2)
7 6 4 5 3 2 0 1 になる. c89de+/f
dと9, /とfを交換 (1) 7 6 5 4 3 2 1 0 になった.
とまぁこういうことをやったのである.
他の場合については別の機会に.
0 件のコメント:
コメントを投稿