β変換から二進数への変換

1. β変換とは

普通の二進数展開は基数 2 を使います：

x = Σ_{k=1}^∞ d_k · 2^(−k),   d_k ∈ {0,1}

例：

0.101(2) = 1/2 + 0/4 + 1/8 = 0.625

β変換では基数を β（1 < β < 2） に変えます：

x = (β−1) Σ_{k=1}^∞ b_k · β^(−k),   b_k ∈ {0,1}

これが β展開 と呼ばれます。
β=2 のときは普通の二進展開に一致します。

---

2. β展開の生成手順（Greedy Algorithm）

ある値 x ∈ [0,1] を β展開するには次を繰り返します。

1. u₀ = x

2. k = 1,2,… として

   u_k = β·u_{k−1}
   b_k = floor(u_k)
   u_k = u_k − b_k
   

   b_k は 0 または 1 になる。

こうして βコード列 b₁,b₂,… が得られます。

---

3. βコード列から数値に戻す

有限長 L ビットまでで近似値を作ります：

x̂ = (β−1) Σ_{k=1}^L b_k · β^(−k)

誤差は最大で

|x − x̂| ≤ 1 / β^L

となります。

---

4. βコードを二進数に変換する方法

方法A：数値をいったん計算して丸める

1. βコード列から近似値 x̂ を計算。

2. Nビットの二進数にしたいとき：

   D = round( 2^N · x̂ )
   

3. D を二進表現に直すと、Nビットの二進コードになる。

---

方法B：逐次的に二進展開を作る

二進数展開は「x に 2 をかけて 1 を引く」作業の繰り返しです。

1. y₀ = x̂

2. k=1..N のステップで

   if y_{k−1} ≥ 0.5:
       d_k = 1
       y_k = 2·y_{k−1} − 1
   else:
       d_k = 0
       y_k = 2·y_{k−1}
   

3. 得られた d₁,d₂,… が二進数コード。

---

方法C：行列形式での計算

βコード列をベクトル b とすると

w = (β−1) [β^(−1), β^(−2), …, β^(−L)]^T
x̂ = w^T b

ここで得られた x̂ を 2^N 倍して丸めれば二進数化できる。

---

5. 実際の回路での注意点

• 増幅率やしきい値の誤差で、理論上の β と実際の β がズレる。
• 実効値 β_eff を測定して、それを式に使えば正しい二進コードが得られる。

---

6. 必要なビット長

β展開の L ビットで、二進数の N ビット精度を得るには

L > (N+1) / log₂(β)

例：β=1.83 の場合
10ビットの二進数を得るには

L ≈ (10+1)/log₂(1.83) ≈ 13

が必要。

---

7. まとめ

• β変換は「基数を2以外にした二進的展開」。
• βコード列を数値に戻し、2^N 倍して丸めれば二進コードになる。
• 誤差評価は 1/β^L、必要ビット数は (N+1)/log₂(β) で見積もれる。
• 実装では βのズレ補正が重要。

import math

# ============= Parameters =============
beta = 1.83     # 基数β (1 < β < 2)
x = 0.7         # 変換したい値 (0 <= x <= 1)
L = 15          # β展開のビット長
N = 10          # 出力する二進数のビット数

# ============= Step 1: β展開 (Greedy Algorithm) =============
u = x
b_seq = []  # βコード列
for k in range(L):
    u = beta * u
    b = math.floor(u)
    b_seq.append(b)
    u -= b

print("β-expansion sequence:", b_seq)

# ============= Step 2: β展開から数値に戻す =============
x_hat = (beta - 1) * sum(b_seq[k] * (beta ** (-(k+1))) for k in range(L))
print("Approximate value from β-expansion:", x_hat)

# ============= Step 3A: 方法A 丸めて二進数に変換 =============
D = round((2**N) * x_hat)
binary_A = format(D, f"0{N}b")
print("Binary (Method A):", binary_A)

# ============= Step 3B: 方法B 逐次展開法 =============
y = x_hat
binary_B = []
for k in range(N):
    y *= 2
    if y >= 1:
        binary_B.append(1)
        y -= 1
    else:
        binary_B.append(0)

print("Binary (Method B):", ''.join(map(str, binary_B)))

---

実行例（β=1.83, x=0.7, L=15, N=10）

β-expansion sequence: [1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1]
Approximate value from β-expansion: 0.699812...
Binary (Method A): 1011000110
Binary (Method B): 1011000110