復底數進位

複底數進位是指底數為虛數或複數的進位制系統。

其中，底數為虛數的進位制系統最早由高德納於1955年提出；底數為複數的進位制系統於1964年由所羅門·I·赫梅利尼克（Solomon I. Khmelnik）和1965年由沃爾特·F·彭尼（Walter F. Penney）提出。

## 概述

令$D$為整環$\subset \C$和$|\cdot|$為（阿基米德）絕對賦值。

數$X\in D$在進位制系統中可以表示為：

$$X = \pm \sum_{\nu}^{ } x_\nu \rho^\nu,$$

其中

$\rho \in D$｜為底數，並滿足$|\rho| > 1$。

$\nu \in \Z$｜是指數，代表各個位數。

$x_\nu$｜是進位中每個位數，來自有限的位數數碼集合$Z \subset D$，通常滿足$|x_\nu| < |\rho|.$

其勢$R:=|Z|$稱為分解程度（level of decomposition）

進位制系統或編碼系統是一對二元組：

$$\left\langle \rho, Z \right\rangle$$

包括了其底數$\rho$和位數數碼集合$Z$。通常會將有$R$個位數數碼的位數數碼集合表示為：

$$Z_R := \{0, 1, 2,\dotsc, {R-1}\}.$$

理想的進位制系統或編碼系統具有以下特性：

- 任何在環$D$內的數如整數$\Z$、高斯整數$\Z[\mathrm i]$或環$\Z\left[\tfrac{-1+\mathrm i\sqrt7}2\right]$的整數可以表達為為唯一的編碼，並可能帶有正負號±。
- 任何在分式環$K:=\operatorname{Quot}(D)$內的數，或者再取完備化（$|\cdot|$度量的意義下）所得的$K:=\R$或$K:=\C$內的數，皆可以表示為在$|\cdot|$下，於$\nu \to -\infty$收斂的無窮級數$X$，且不只一種表示方式之數的集合測度為0。後者要求集合$Z$最小，即對於實數$R=|\rho|$、對於複數$R=|\rho|^2$。

## 實數

在這種表示法中，一般常見的標準十進位表示為：

$$\left\langle 10, Z_{10} \right\rangle,$$

標準二進位系統表示為：

$$\left\langle 2, Z_2 \right\rangle,$$

負二進位系統表示為：

$$\left\langle -2, Z_2 \right\rangle,$$

平衡三進位系統表示為：

$$\left\langle 3, \{-1,0,1\} \right\rangle.$$

上述這幾個進位制系統在$\Z$和$\R$中都具有上述的特性。後兩個不需要使用正負號。

## 複數

較廣為人知的複底數進位制系統包括下列幾個進位制系統（其中$\mathrm i$表示虛數單位）：

- $\left\langle\sqrt{R},Z_R\right\rangle$，例如$\left\langle\pm \mathrm i \sqrt{2},Z_2\right\rangle$ （$\mathrm i \sqrt{2}$進位）和

$\left\langle\pm 2\mathrm i,Z_4\right\rangle$，即2i進位，由高德納於1995年提出。

- $\left\langle\sqrt{2}e^{\pm \tfrac{\pi}2 \mathrm i}=\pm \mathrm i\sqrt{2},Z_2\right\rangle$和

$\left\langle\sqrt{2}e^{\pm \tfrac{3 \pi}4 \mathrm i}=-1\pm\mathrm i,Z_2\right\rangle$（參見下方−1 ± i進位一節）

- $\left\langle\sqrt{R}e^{\mathrm i\varphi},Z_R\right\rangle$，其中$\varphi=\pm \arccos{(-\beta/(2\sqrt{R}))}$、 $\beta<\min(R, 2\sqrt{R})$且$\beta_{ }^{ }$是一個正整數，在給定的$R$可以取多個值。比如$\beta=1$且$R=2$是指

$\left\langle\tfrac{-1+\mathrm i\sqrt7}2,Z_2\right\rangle$進位制系統。（$\tfrac{-1+\mathrm i\sqrt7}2$進位）

- $\left\langle 2e^{\tfrac{\pi}3 \mathrm i},A_4:=\left\{0,1,e^{\tfrac{2 \pi}3 \mathrm i},e^{-\tfrac{2 \pi}3 \mathrm i}\right\}\right\rangle$。
- $\left\langle-R,A_R^2\right\rangle$，其中，集合$A_R^2$由複數$r_\nu=\alpha_\nu^1+\alpha_\nu^2\mathrm i$組成，且數$\alpha_\nu^{ } \in Z_R$，例如

$\left\langle -2, \{0,1,\mathrm i,1+\mathrm i\}\right\rangle$。

- $\left\langle\rho=\rho_2,Z_2\right\rangle$，其中$\rho_2=\begin{cases} <pre> (-2)^{\tfrac{\nu}2} & \text{if } \nu \text{ even,}\\ (-2)^{\tfrac{\nu-1}2}\mathrm i & \text{if } \nu \text{ odd.} </pre> \end{cases}$

## 二元系統

複數的二元系統是僅使用兩個數碼——0和1的進位制系統，即位數數碼集合為$Z_2=\{0,1\}$的進位制系統，這類記數系統具有較實際的用途。

下表列出了一些$\langle \rho, Z_2 \rangle$的進位制系統（皆為上述進位制系統的特例），並用其表達−1, 2, −2, i。

同時也列出標準的二進位（下表的第一列）和「負二進位」（下表的第二列）供比較。這兩個進位制無法真正地表達出虛數單位i。

底數｜–1 ←｜2 ←｜–2 ←｜i ←｜多種表示形式的數

2｜2｜2｜2｜i｜1 ←｜0.1 = 1.0

–2｜-2｜-2｜-2｜i｜1 ←｜0.01 = 1.10

$\mathrm i\sqrt{2}$｜...｜$\frac{1}{3}+\frac{1}{3}\mathrm i \sqrt{2}$ ←｜0.0011 = 11.1100

$\frac{-1 + \mathrm{i}\sqrt{7}}{2}$｜111｜1010｜110｜11.110001100...｜$\frac{3+\mathrm i\sqrt{7}}{4}$ ←｜1.011 = 11.101 = 11100.110

$\rho_2$｜101｜10100｜100｜10｜1 + 1i ←｜0.0011 = 11.1100

–1+i｜-1+i｜-1+i｜-1+i｜-1+i｜1 + 3i ←｜0.010 = 11.001 = 1110.100

2i｜2i｜2i｜2i｜2i｜1 + 2i ←｜0.0033 = 1.3003 = 10.0330 = 11.3300

與所有具有阿基米德絕對賦值的進位制系統一樣，有些數字具有多種表示形式。此類數字的範例顯示在表格的右欄中。這些數都是循環小數，其循環節以上標水平線標記。

## 進位轉換

若要將一高斯整數$z$轉換為一個以高斯整數$b$為底數的進位制$\left\langle b, Z_R \right\rangle$可以將數分成一個可被底數整除的高斯整數和一個位於位數數碼集合內的數，並將可被底數整除的高斯整數部分除以底數當作商，位於位數數碼集合內的數當作餘數，並用商數繼續計算，並重複以上步驟，直到商為零，一系列的餘數部分即為轉換完成的結果。

$$z_{\,}=q_1b+a_0$$

$$q_1=q_2b+a_1$$

$$q_2=q_3b+a_2$$

$$\quad\quad\vdots$$

$$q_t=0_{\,}b+a_t$$

其中，$q_1$、$q_2$、$q_3$……$q_t$為高斯整數，$a_1$、$a_2$、$a_3$……$a_t$為位於位數數碼集合內的數。

則$z=\left(a_t\cdots a_2a_1a_0\right)_b$。

以5+12i轉換成-2+i進位（$\left\langle -2+\mathrm i, \{0,1,2,3,4\}\right\rangle$）為例：

$5+12\mathrm i$｜$=$｜$\left(2-5\mathrm i\right)\left(-2+\mathrm i\right) + 4$

$2-5\mathrm i$｜$=$｜$\left(-1+2\mathrm i\right)\left(-2+\mathrm i\right) + 2$

$-1+2\mathrm i$｜$=$｜$\left(2\right)\left(-2+\mathrm i\right) + 3$

$2$｜$=$｜$\left(0\right)\left(-2+\mathrm i\right) + 2$

故5+12i(10)轉換成-2+i進位為-2+i。

## −1 ± i進位

<image>

較常被討論的複底數進位是2i進位和−1 ± i進位（−1 + i進位和−1 − i進位），因為其皆可不使用正負號有限地表達所有高斯整數。

−1 ± i進位以0和1為基本數碼，其於1964年由所羅門·I·赫梅利尼克（Solomon I. Khmelnik）和1965年由沃爾特·F·彭尼（Walter F. Penney）提出。

十進制｜二進制｜2i進制｜−1+i進制｜−1−i進制

0｜2｜2i｜-1+i｜-1-i

1｜2｜2i｜-1+i｜-1-i

2｜2｜2i｜-1+i｜-1-i

−1｜2｜2i｜-1+i｜-1-i

−2｜2｜2i｜-1+i｜-1-i

i｜i｜2i｜-1+i｜-1-i

2i｜2i｜2i｜-1+i｜-1-i

3i｜2i｜2i｜-1+i｜-1-i

−i｜−i｜2i｜-1+i｜-1-i

−2i｜2i｜2i｜-1+i｜-1-i

−3i｜2i｜2i｜-1+i｜-1-i

1+i｜1+i｜2i｜-1+i｜-1-i

1−i｜1−i｜2i｜-1+i｜-1-i

−1+i｜−1+i｜2i｜-1+i｜-1-i

−1−i｜−1−i｜2i｜-1+i｜-1-i

### 與twindragon關聯

整數的捨入區域——即在這系統表達之下，共用整數部分的複數（非整數）集合$S$——在複平面中具有分形：twindragon。根據定義，集合$S$的所有點可以計為$\textstyle \sum_{k\geq 1}x_k (\mathrm i-1)^{-k}$，其中$x_k\in Z_2$。$S$可以分解成16塊$\tfrac14 S$。注意到，若$S$逆時針旋轉135°，則會得到兩個與$\tfrac{1}{\sqrt{2}}S$相等的相鄰集合，因為$(\mathrm i-1)S=S\cup(S+1)$。中心的矩形 R 在以下點逆時針地與坐標軸相交：$\tfrac2{15}\gets 0.\overline{00001100}$、$\tfrac1{15} \mathrm i\gets 0.\overline{00000011}$、$-\tfrac8{15}\gets 0.\overline{11000000}$和$-\tfrac4{15} \mathrm i\gets 0.\overline{00110000}$。因此，S 包含所有絕對值≤ 1的複數。

由此，複矩形

$$[-\tfrac8{15},\tfrac2{15}]\times[-\tfrac4{15},\tfrac1{15}]\mathrm i$$

透過單射

$$\textstyle \sum_{k\geq 1}x_k (\mathrm i-1)^{-k} \mapsto \sum_{k\geq 1}x_k b^{-k}$$

映入實數區間$[0, 1)$，其中$b > 2$

$b = 2$

$\textstyle 2^{-1} = 0.1_{\text{bin}} = 0.5_{\text{dec}}$

$\textstyle \sum_{k\geq 2} 2^{-k} = 0.0\overline{1}_{\text{bin}} = 0.1_{\text{bin}} = 0.5_{\text{dec}}$

$\textstyle (\mathrm i-1)^{-1} = -0.1_{\text{bin}} -0.1_{\text{bin}} \mathrm i = -0.5_{\text{dec}} -0.5_{\text{dec}} \mathrm i$

$\textstyle \sum_{k\geq 2} (\mathrm i-1)^{-k} = 0.1_{\text{dec}} +0.3_{\text{dec}} \mathrm i$。

此外，還有兩個映射

$$\begin{array}{lll} Z_2^\N & \to & S \\ \left(x_k\right)_{k\in\N} & \mapsto & \sum_{k\geq 1}x_k (\mathrm i-1)^{-k} \end{array}$$

和

$$\begin{array}{lll} Z_2^\N & \to & [0,1) \\ \left(x_k\right)_{k\in\N} & \mapsto & \sum_{k\geq 1}x_k 2^{-k} \end{array}$$

兩者皆滿射，也就是產生了一個滿射（空間填充）的映射

$$[0,1) \qquad \to \qquad S$$

然而，其並不連續，因此不是空間填充曲線。但是一個類似的曲線——戴維斯-高德納龍（Davis-Knuth dragon），是連續的空間填充曲線。