ダメもとで試した
Decimal⟺DPD変換 で、10 進数 3 桁を BCD（二進化十進数：4 ビットで 1 桁）にしてから 0x888 のマスク値から符号化処理が必要になった。
マスク値を除数 9（を選択した理由は後述）での剰余を調べたら
>>> [m % 9 for m in (0x000, 0x008, 0x080, 0x800, 0x880, 0x808, 0x088, 0x888)]
[0, 8, 2, 5, 7, 4, 1, 6]
範囲(0〜8：3 を除く)で 1 対 1 （単射）になった。
任意のビット位置のマスク値に対してもいけそうな気がするので値を変えて試す。
>>> [m % 9 for m in (0x000, 0x001, 0x010, 0x100, 0x110, 0x101, 0x011, 0x111)]
[0, 1, 7, 4, 2, 5, 8, 3]
>>> [m % 9 for m in (0x000, 0x001, 0x020, 0x400, 0x420, 0x401, 0x021, 0x421)]
[0, 1, 5, 7, 3, 8, 6, 4]
どうやら大丈夫らしい。本当か？
任意ビット n 個のマスク値と（2ⁿ+1）での剰余
任意ビット $n$ 個のマスク値に対する $\left(D = 2^n + 1 \right)$ での剰余が
\begin{eqnarray}
D & = & 2^n+1 \\
X & \equiv & 2^{c_1} b_1 + 2^{c_2} b_2 + \cdots + 2^{c_n} b_n \pmod D \\
b_{i} & = & \{ 0, 1 \} \\
c_{i} & \ne & c_{j} \left( i \ne j\ の場合 \right) \\
\\
0 & \leq & X \leq 2^n+1 \\
\end{eqnarray}
で単射になるかが気になります。まず、
r_i \equiv 2^{c_i} \pmod D \\
\left( r_i < D \right)
とすると
\begin{eqnarray}
X & \equiv & 2^{c_1} b_1 + 2^{c_2} b_2 + \cdots + 2^{c_n} b_n \pmod D \\
& \equiv & b_1 r_1 + b_2 r_2 + \cdots + b_n r_n \pmod D \\
\end{eqnarray}
となります（この形が頭を過ったので、マスク値 0x888 に対して除数 9 を選択した）。
この時点では単射になるのかわかりません（のでダメもとで試してみた）。
単射にならない場合
i ≠ j のとき、 ri と rj が同じ
$i \ne j$ のとき、$r_i$ と $r_j$ が同じ場合は、カーマイケルの $\lambda$ 関数を用いると
\begin{eqnarray}
i & \ne & j \\
r_i & \equiv & 2^{c_i} \pmod D \\
r_j & \equiv & 2^{c_j} \pmod D \\
2^{c_i} & \equiv & 2^{c_j} \pmod D \\
2^{c_j - c_i} & \equiv & 1 \pmod D \cdots \{ c_i \lt\ c_j \} \\
2^{c_j - c_i} & \equiv & 2^{\lambda\left(D\right)} \pmod D \\
\end{eqnarray}
とすることができます。具体的に $n=\{ 2,3,\cdots,8 \}$ での $\lambda\left(D\right)$ は
\begin{eqnarray}
\lambda \left( 2^2 + 1 \right) & = & 4 \\
\lambda \left( 2^3 + 1 \right) & = & 6 \\
\lambda \left( 2^4 + 1 \right) & = & 16 \\
\lambda \left( 2^5 + 1 \right) & = & 10 \\
\lambda \left( 2^6 + 1 \right) & = & 12 \\
\lambda \left( 2^7 + 1 \right) & = & 42 \\
\lambda \left( 2^8 + 1 \right) & = & 256 \\
\end{eqnarray}
になるようです。(Mathematica の Table[CarmichaelLambda[2^n + 1], {n, 2, 8}] より)
$\left( n = 3 \right)$ のとき、$\left( c_j - c_i \right)$ が $6$ の倍数ではダメらしいので、0x821,0x8108 のマスク値で試すと
>>> [m % 9 for m in (0x000, 0x001, 0x020, 0x800, 0x820, 0x801, 0x021, 0x821)]
[0, 1, 5, 5, 1, 6, 6, 2]
>>> [m % 9 for m in (0x0000, 0x0008, 0x0100, 0x8000, 0x8100, 0x8008, 0x0108, 0x8108)]
[0, 8, 4, 8, 3, 7, 3, 2]
単射にならないことを確認できました。
条件 $r_i \ne r_j$ を満たすには
マスク ビット位置の差 $c_i - c_j$
（$i,j$ は総当たり）
が
$\lambda\left(D\right)$ の倍数
とならないようにする。
例えば、$\left( n = 3 \right)$ では、$\lambda\left( 2^3+1 \right) = 6$ ビットで区切って、列方向では一カ所だけマスクを設定できます。
マスクが 0x888 の場合（単射になる）
| +0 | +1 | +2 | +3 | +4 | +5 | |
|---|---|---|---|---|---|---|
| 0 | ○ | |||||
| 6 | ○ | ○ |
0x888 のビット位置は 3,7,11 で列の重複なし。
マスクが 0x421 の場合（単射になる）
| +0 | +1 | +2 | +3 | +4 | +5 | |
|---|---|---|---|---|---|---|
| 0 | ○ | ○ | ||||
| 6 | ○ |
0x421 のビット位置は 0,5,10 で列の重複なし。
マスクが 0x821 の場合（単射にならない）
| +0 | +1 | +2 | +3 | +4 | +5 | |
|---|---|---|---|---|---|---|
| 0 | ○ | × | ||||
| 6 | × |
0x821 のビット位置は 0,5,11 で 5,11 が列で重複する。
マスクが 0x8108 の場合（単射にならない）
| +0 | +1 | +2 | +3 | +4 | +5 | |
|---|---|---|---|---|---|---|
| 0 | × | |||||
| 6 | ○ | |||||
| 12 | × |
0x8108 のビット位置は 3,8,15 で 3,15 が列で重複する。
上記問題を避けた場合
マスクを 0x1111 $\left( n=4 \right)$とすると、除数 $D$ は $\left( 2^4+1 = 17\right)$ となります。試すと
>>> [m % 17 for m in [0x0000, 0x0001, 0x0010, 0x0011,
... 0x0100, 0x0101, 0x0110, 0x0111,
... 0x1000, 0x1001, 0x1010, 0x1011,
... 0x1100, 0x1101, 0x1110, 0x1111]]
[0, 1, 16, 0, 1, 2, 0, 1, 16, 0, 15, 16, 0, 1, 16, 0]
となって単射になりません。列の重複問題は
$\lambda \left( 2^4 + 1 \right) = 16$
なので発生していませんが $r_i$ は
>>> [m % 17 for m in [0x0001, 0x0010, 0x0100, 0x1000]]
[1, 16, 1, 16]
となって重複しています。
まず、$\left( 2^k \lt D \right)\{k=0,1,\cdots\}$ では
\begin{eqnarray}
2^k & = & 2^k \pmod D \\
2^k & \lt & D \\
\{ k & = & 0,1,\cdots \} \\
\end{eqnarray}
となります。次に、$\left( 2^k \ge D \right)$ の範囲で
1 \equiv 2^k \pmod D
となる k を考えると
\begin{eqnarray}
2^k & = & D \times m + 1 \\
\frac{2^k - 1}{m} & = & D \\
\end{eqnarray}
と表せるので、メルセンヌ数 $\left( 2^k - 1 \right)$ と $D$ に共通因子があると、ビット位置の差は $\lambda\left(D\right)$ より小さいくなるようです。
メルセンヌ数 M を素因数分解すると
| k | M | |
|---|---|---|
| $2$ | $3$ | $3$ |
| $3$ | $7$ | $7$ |
| $4$ | $15$ | $3 \times 5$ |
| $5$ | $31$ | $31$ |
| $6$ | $63$ | $3^2 \times 7$ |
| $7$ | $127$ | $127$ |
| $8$ | $255$ | $3 \times 5 \times 17$ |
| $9$ | $511$ | $7 \times 73$ |
| $10$ | $1023$ | $3 \times 11 \times 31$ |
| $11$ | $2047$ | $23 \times 89$ |
| $12$ | $4095$ | $3^2 \times 5 \times 7 \times 13$ |
| $13$ | $8191$ | $8191$ |
| $14$ | $16383$ | $3 \times 43 \times 127$ |
| $15$ | $32767$ | $7 \times 31 \times 151$ |
| $16$ | $65535$ | $3 \times 5 \times 17 \times 257$ |
だから、ビット位置の差が
$D=2^4+1=17$ の場合は $8$
$D=2^7+1=129$ の場合は $14$
$D=2^8+1=257$ の場合は $16$
で $r_i$ が重複する条件となるようです。
上にある $n=\{ 2,3,\cdots,8 \}$ での $\lambda\left(D\right)$ 表に、上の条件を加味して
\begin{eqnarray}
\lambda \left( 2^2 + 1 \right) & = & 4 \\
\lambda \left( 2^3 + 1 \right) & = & 6 \\
\lambda \left( 2^4 + 1 \right) & = & 16 \to 8 \\
\lambda \left( 2^5 + 1 \right) & = & 10 \\
\lambda \left( 2^6 + 1 \right) & = & 12 \\
\lambda \left( 2^7 + 1 \right) & = & 42 \to 14 \\
\lambda \left( 2^8 + 1 \right) & = & 256 \to 16 \\
\end{eqnarray}
にビット区切り幅が変更されます。ビット区切り幅は $2n$ となるようです。
2^{2n} - 1 = \left( 2^n - 1 \right) \left( 2^n + 1 \right)
ここまでの問題を避けた場合
$r_i$ の重複がなくても
$r_i + r_j \equiv r_j + r_k \pmod D$
となどが考えられます。
お詫び：合同式を弄って説明を作りたかったのですが、力不足で作れていません。
単射確認支援ツールで、どのマスクでも単射できる除数 $D$ を探せると思います。
単射確認支援ツールは「規則性の低い数列表に対する無検索逆引き」に進化しました。
単射確認支援ツール
プログラム
コマンド ライン引数にマスク値を指定すると各種結果が出力されます。
オプションで以下のことができます。
- 除数 $\left( D = 2^n + N \right)$ の $N$ を変更
- 除数 $D$ を変更
- 単射となる除数を初期値から奇数化後に $\{ 2,4,6,\cdots \}$ を追加して探す
#!/usr/bin/env python3
import argparse
def format_base10(n): return '%%%dd' % len('%d' % n)
def format_base16(n): return '0x%%0%dx' % len(hex(mask)[2:])
def format_list(data, *, width=16, prefix='',
datafmt='%s', msgfmt='%#s', separator=',', space=1, suffix='\n'):
fmtdata = [datafmt % d for d in data]
msgfmt = msgfmt.replace('#', ('%d' % max([len(s) for s in fmtdata])))
msglist = [(msgfmt % d) + separator for d in fmtdata]
return (suffix.join([prefix + (' ' * space).join(msglist[i:min(i+width, len(msglist))])
for i in range(0, len(msglist), width)]) + suffix)
def to_int(s):
m = {'0b': 2, '0o': 8, '0x': 16}
if len(s) >= 2 and s[:2] in m:
return int(s, m[s[:2]])
return int(s)
def gcd(m, n): return n and gcd(n, m % n) or m
def eulerphi(n): return sum(int(gcd(m + 1, n) == 1) for m in range(n))
parser = argparse.ArgumentParser(description='マスク値に対する単射条件を確認の支援道具です')
parser.add_argument('-a', '--divisor-offset', metavar='N', help='除数 D=(pow(2,n)+N) の N を指定します')
parser.add_argument('-d', '--divisor', metavar='D', help='除数 D を指定します')
parser.add_argument('-D', '--auto-divisor', action='store_true', help='単射となる除数 D を加算方式で探します')
parser.add_argument('MASK', help='計算の元となるマスク値')
args = parser.parse_args()
mask = to_int(args.MASK)
base = tuple(filter((lambda d: d),
((mask & (1 << i)) for i in range(mask.bit_length()))))
index_bits = len(base)
index_length = 1 << index_bits
element = tuple(sum([(base[b] if (i & (1 << b)) else 0)
for b in range(index_bits)])
for i in range(index_length))
divisor = (args.divisor and to_int(args.divisor) or
(index_length + (args.divisor_offset and to_int(args.divisor_offset) or 1)))
while True:
remain = tuple(n % divisor for n in element)
re_map = {(n % divisor): n for n in element}
used = set(re_map)
injective = (len(used) == index_length)
if injective or not args.auto_divisor:
break
divisor += 2
divisor |= 1
unused = set(range(divisor)) - used
mask_format = format_base16(mask)
remain_format = format_base10(max(remain))
res_format = '%s:%s' % (mask_format, remain_format)
bit = tuple(res_format % (element[i], remain[i]) for i in [1 << b for b in range(index_bits)])
res = tuple(res_format % (element[i], remain[i]) for i in range(index_length))
stab = tuple(('%s:%s' % (remain_format, mask_format)) % (i, re_map[i]) for i in used)
utab = tuple((remain_format + ':%s') % (i, (i in used) and '*' or '-') for i in range(divisor))
indent = ' ' * 4
print('マスク値： MASK=' + (mask_format % mask))
print('ビット数： n=%d' % index_bits)
print('除数 ： D=%d' % divisor)
print('単射 ： %s' % injective)
print()
print('（序数：有無）の表\n' + format_list(utab, width=8, prefix=indent)[:-2])
if injective:
print('（剰余：被除数）の表\n' + format_list(stab, width=4, prefix=indent)[:-2])
print('（被除数：剰余）の表\n' + format_list(res, width=4, prefix=indent)[:-1])
print('（各ビット：剰余）の表\n' + format_list(bit, width=4, prefix=indent)[:-1])
print()
print(('使用序数の表（最大 %d 個中 %d 個）\n' % (index_length, len(used))) + format_list(used, prefix=indent)[:-2])
print(('未使用序数の表（%d 個）\n' % len(unused)) + format_list(unused, prefix=indent)[:-2])
print()
テスト
マスク：0x888
$ python3 chkinj.py 0x888
マスク値： MASK=0x888
ビット数： n=3
除数 ： D=9
単射 ： True
（序数：有無）の表
0:*, 1:*, 2:*, 3:-, 4:*, 5:*, 6:*, 7:*,
8:*
（剰余：被除数）の表
0:0x000, 1:0x088, 2:0x080, 4:0x808,
5:0x800, 6:0x888, 7:0x880, 8:0x008
（被除数：剰余）の表
0x000:0, 0x008:8, 0x080:2, 0x088:1,
0x800:5, 0x808:4, 0x880:7, 0x888:6,
（各ビット：剰余）の表
0x008:8, 0x080:2, 0x800:5,
使用序数の表（最大 8 個中 8 個）
0, 1, 2, 4, 5, 6, 7, 8
未使用序数の表（1 個）
3
マスク：0x821
デフォルトでは単射にならないことが分かっている。
$ python3 chkinj.py 0x821
マスク値： MASK=0x821
ビット数： n=3
除数 ： D=9
単射 ： False
（序数：有無）の表
0:*, 1:*, 2:*, 3:-, 4:-, 5:*, 6:*, 7:-,
8:-
（被除数：剰余）の表
0x000:0, 0x001:1, 0x020:5, 0x021:6,
0x800:5, 0x801:6, 0x820:1, 0x821:2,
（各ビット：剰余）の表
0x001:1, 0x020:5, 0x800:5,
使用序数の表（最大 8 個中 5 個）
0, 1, 2, 5, 6
未使用序数の表（4 個）
8, 3, 4, 7
オプション '-D' を追加して試す。
$ python3 chkinj.py 0x821 -D
マスク値： MASK=0x821
ビット数： n=3
除数 ： D=15
単射 ： True
（序数：有無）の表
0:*, 1:*, 2:*, 3:*, 4:-, 5:-, 6:-, 7:-,
8:*, 9:*, 10:*, 11:*, 12:-, 13:-, 14:-
（剰余：被除数）の表
0:0x000, 1:0x001, 2:0x020, 3:0x021,
8:0x800, 9:0x801, 10:0x820, 11:0x821
（被除数：剰余）の表
0x000: 0, 0x001: 1, 0x020: 2, 0x021: 3,
0x800: 8, 0x801: 9, 0x820:10, 0x821:11,
（各ビット：剰余）の表
0x001: 1, 0x020: 2, 0x800: 8,
使用序数の表（最大 8 個中 8 個）
0, 1, 2, 3, 8, 9, 10, 11
未使用序数の表（7 個）
4, 5, 6, 7, 12, 13, 14
これで、論理やシフト処理の塊から少しは脱却できるかも？