复底数进制

複底数进制是指底數為虛數或複數的进位制系統。 其中，底數為虛數的进位制系統最早由高德纳於1955年提出^[1][2]；底數為複數的进位制系統於1964年由所羅門·I·赫梅利尼克（Solomon I. Khmelnik）^[3]和1965年由沃爾特·F·彭尼（Walter F. Penney）提出^[4][5][6]。

概述

令${\displaystyle D}$ 為整环${\displaystyle \subset \mathbb {C} }$ 和${\displaystyle |\cdot |}$ 為（阿基米德）绝对赋值。

數${\displaystyle X\in D}$ 在进位制系統中可以表示為：

${\displaystyle X=\pm \sum _{\nu }^{}x_{\nu }\rho ^{\nu },}$ 

其中

${\displaystyle \rho \in D}$		為底數，並滿足${\displaystyle |\rho |>1}$ ，
${\displaystyle \nu \in \mathbb {Z} }$		是指數，代表各個位數，
${\displaystyle x_{\nu }}$		是进制中每個位數，來自有限的位數數碼集合${\displaystyle Z\subset D}$ ，通常滿足${\displaystyle |x_{\nu }|<|\rho |.}$

其势${\displaystyle R:=|Z|}$ 稱為分解程度（level of decomposition）

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

${\displaystyle \left\langle \rho ,Z\right\rangle }$ 

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

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

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

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

實數

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

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

標準二进制系統表示為：

${\displaystyle \left\langle 2,Z_{2}\right\rangle ,}$ 

負二进制系統表示為：

${\displaystyle \left\langle -2,Z_{2}\right\rangle ,}$ 

平衡三進位系統表示為^[2]：

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

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

複數

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

• ${\displaystyle \left\langle {\sqrt {R}},Z_{R}\right\rangle }$ ，例如${\displaystyle \left\langle \pm \mathrm {i} {\sqrt {2}},Z_{2}\right\rangle }$  ^[1]（${\displaystyle \mathrm {i} {\sqrt {2}}}$ 进制）和

${\displaystyle \left\langle \pm 2\mathrm {i} ,Z_{4}\right\rangle }$ ^[2]，即2i进制，由高德纳於1995年提出。

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

${\displaystyle \left\langle {\sqrt {2}}e^{\pm {\tfrac {3\pi }{4}}\mathrm {i} }=-1\pm \mathrm {i} ,Z_{2}\right\rangle }$ ^[3][5]（參見下方−1 ± i进制一節）

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

${\displaystyle \left\langle {\tfrac {-1+\mathrm {i} {\sqrt {7}}}{2}},Z_{2}\right\rangle }$ 进位制系統。（${\displaystyle {\tfrac {-1+\mathrm {i} {\sqrt {7}}}{2}}}$ 进制）

• ${\displaystyle \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 }$ ^[8]。
• ${\displaystyle \left\langle -R,A_{R}^{2}\right\rangle }$ ，其中，集合${\displaystyle A_{R}^{2}}$ 由複數${\displaystyle r_{\nu }=\alpha _{\nu }^{1}+\alpha _{\nu }^{2}\mathrm {i} }$ 組成，且數${\displaystyle \alpha _{\nu }^{}\in Z_{R}}$ ，例如

${\displaystyle \left\langle -2,\{0,1,\mathrm {i} ,1+\mathrm {i} \}\right\rangle }$ ^[8]。

• ${\displaystyle \left\langle \rho =\rho _{2},Z_{2}\right\rangle }$ ，其中${\displaystyle \rho _{2}={\begin{cases}(-2)^{\tfrac {\nu }{2}}&{\text{if }}\nu {\text{ even,}}\\(-2)^{\tfrac {\nu -1}{2}}\mathrm {i} &{\text{if }}\nu {\text{ odd.}}\end{cases}}}$  ^[9]

二元系統

複數的二元系統是僅使用兩個數碼——0和1的进位制系統，即位數數碼集合為${\displaystyle Z_{2}=\{0,1\}}$ 的进位制系統，這類記數系統具有較實際的用途^[9]。 下表列出了一些${\displaystyle \langle \rho ,Z_{2}\rangle }$ 的进位制系統（皆為上述进位制系統的特例），並用其表達−1, 2, −2, i。 同時也列出標準的二进制（下表的第一列）和「負二进制」（下表的第二列）供比較。這兩個进位制無法真正地表達出虛數單位i。

部分的进位制系統和一些數的表達^[10]

底數	–1 ←	2 ←	–2 ←	i ←	多種表示形式的數
2	−1	10	−10	i	1 ←	0.1 = 1.0
–2	11	110	10	i	1/3 ←	0.01 = 1.10
${\displaystyle \mathrm {i} {\sqrt {2}}}$	101	10100	100	10.101010100...^[註 1]	${\displaystyle {\frac {1}{3}}+{\frac {1}{3}}\mathrm {i} {\sqrt {2}}}$  ←	0.0011 = 11.1100
${\displaystyle {\frac {-1+\mathrm {i} {\sqrt {7}}}{2}}}$	111	1010	110	11.110001100...^[註 1]	${\displaystyle {\frac {3+\mathrm {i} {\sqrt {7}}}{4}}}$  ←	1.011 = 11.101 = 11100.110
${\displaystyle \rho _{2}}$	101	10100	100	10	1/3 + 1/3i ←	0.0011 = 11.1100
–1+i	11101	1100	11100	11	1/5 + 3/5i ←	0.010 = 11.001 = 1110.100
2i	103	2	102	10.2	1/5 + 2/5i ←	0.0033 = 1.3003 = 10.0330 = 11.3300

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

进制轉換

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

${\displaystyle z_{\,}=q_{1}b+a_{0}}$ 

${\displaystyle q_{1}=q_{2}b+a_{1}}$ 

${\displaystyle q_{2}=q_{3}b+a_{2}}$ 

${\displaystyle \quad \quad \vdots }$ 

${\displaystyle q_{t}=0_{\,}b+a_{t}}$ 

其中，${\displaystyle q_{1}}$ 、${\displaystyle q_{2}}$ 、${\displaystyle q_{3}}$ ……${\displaystyle q_{t}}$ 為高斯整數，${\displaystyle a_{1}}$ 、${\displaystyle a_{2}}$ 、${\displaystyle a_{3}}$ ……${\displaystyle a_{t}}$ 為位於位數數碼集合內的數，

則${\displaystyle z=\left(a_{t}\cdots a_{2}a_{1}a_{0}\right)_{b}}$ 。

以5+12i轉換成-2+i进制（${\displaystyle \left\langle -2+\mathrm {i} ,\{0,1,2,3,4\}\right\rangle }$ ）為例：^[11]:42

${\displaystyle 5+12\mathrm {i} }$	${\displaystyle =}$	${\displaystyle \left(2-5\mathrm {i} \right)\left(-2+\mathrm {i} \right)+4}$
${\displaystyle 2-5\mathrm {i} }$	${\displaystyle =}$	${\displaystyle \left(-1+2\mathrm {i} \right)\left(-2+\mathrm {i} \right)+2}$
${\displaystyle -1+2\mathrm {i} }$	${\displaystyle =}$	${\displaystyle \left(2\right)\left(-2+\mathrm {i} \right)+3}$
${\displaystyle 2}$	${\displaystyle =}$	${\displaystyle \left(0\right)\left(-2+\mathrm {i} \right)+2}$

故5+12i₍₁₀₎轉換成-2+i进制為2324_(−2+i)。

−1 ± i进制

 

在−1+i進位制系統中整數部分全為零的複數

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

−1 ± i进制以0和1为基本數碼，其於1964年由所羅門·I·赫梅利尼克（Solomon I. Khmelnik）^[3]和1965年由沃爾特·F·彭尼（Walter F. Penney）提出^[4][6]。

−1±i進制與相關進制比較

十進制	二進制	2i進制	−1+i進制	−1−i進制
0	0	0	0	0
1	1	1	1	1
2	10	2	1100	1100
−1	−1	103	11101	11101
−2	−10	102	11100	11100
i	i	10.2	11	111
2i	10i	10	1110100	100
3i	11i	20.2	1110111	110011
−i	−i	0.2	111	11
−2i	−10i	1030	100	1110100
−3i	−11i	1030.2	110011	1110111
1+i	1+i	11.2	1110	111010
1−i	1−i	1.2	111010	1110
−1+i	−1+i	113.2	10	110
−1−i	−1−i	103.2	110	10

與twindragon關聯

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

由此，複矩形

${\displaystyle [-{\tfrac {8}{15}},{\tfrac {2}{15}}]\times [-{\tfrac {4}{15}},{\tfrac {1}{15}}]\mathrm {i} }$ 

透過单射

${\displaystyle \textstyle \sum _{k\geq 1}x_{k}(\mathrm {i} -1)^{-k}\mapsto \sum _{k\geq 1}x_{k}b^{-k}}$ 

映入實數區間${\displaystyle [0,1)}$ ，其中${\displaystyle b>2}$ ^{[註 2]}。

此外，還有兩個映射

${\displaystyle {\begin{array}{lll}Z_{2}^{\mathbb {N} }&\to &S\\\left(x_{k}\right)_{k\in \mathbb {N} }&\mapsto &\sum _{k\geq 1}x_{k}(\mathrm {i} -1)^{-k}\end{array}}}$ 

和

${\displaystyle {\begin{array}{lll}Z_{2}^{\mathbb {N} }&\to &[0,1)\\\left(x_{k}\right)_{k\in \mathbb {N} }&\mapsto &\sum _{k\geq 1}x_{k}2^{-k}\end{array}}}$ 

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

${\displaystyle [0,1)\qquad \to \qquad S}$ 

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

註釋

1. 無限不循環小數
2. 不能取底數${\displaystyle b=2}$ ，因為${\displaystyle \textstyle 2^{-1}=0.1_{\text{bin}}=0.5_{\text{dec}}}$ 且${\displaystyle \textstyle \sum _{k\geq 2}2^{-k}=0.0{\overline {1}}_{\text{bin}}=0.1_{\text{bin}}=0.5_{\text{dec}}}$ 。 然而，${\displaystyle \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} }$ 不等於${\displaystyle \textstyle \sum _{k\geq 2}(\mathrm {i} -1)^{-k}=0.1_{\text{dec}}+0.3_{\text{dec}}\mathrm {i} }$ 。

參考文獻

1. Knuth, D.E. An Imaginary Number System. Communications of the ACM. 1960, 3 (4): 245–247. S2CID 16513137. doi:10.1145/367177.367233. 
2. Knuth, Donald. Positional Number Systems. The art of computer programming 2 3rd. Boston: Addison-Wesley. 1998: 205. ISBN 0-201-89684-2. OCLC 48246681. 
3. Khmelnik, S.I. Specialized digital computer for operations with complex numbers. Questions of Radio Electronics (In Russian). 1964, XII (2). 
4. W. Penney, A "binary" system for complex numbers, JACM 12 (1965) 247-248.
5. Jamil, T. The complex binary number system. IEEE Potentials. 2002, 20 (5): 39–41. doi:10.1109/45.983342. 
6. Duda, Jarek. Complex base numeral systems. 2008-02-24. arXiv:0712.1309   [math.DS]. 
7. Khmelnik, S.I. Positional coding of complex numbers. Questions of Radio Electronics (In Russian). 1966, XII (9). 
8. Khmelnik, S.I. Coding of Complex Numbers and Vectors (in Russian) (PDF). Israel: Mathematics in Computer. 2004 [2022-11-03]. ISBN 978-0-557-74692-7. （原始内容 (PDF)于2022-11-10）. 
9. Khmelnik, S.I. Method and system for processing complex numbers. Patent USA, US2003154226 (A1). 2001 [2022-11-03]. （原始内容于2023-01-09）. 
10. William J. Gilbert. Arithmetic in Complex Bases (PDF). Mathematics Magazine. 1984-03,. Vol. 57 (No. 2) [2022-11-03]. （原始内容 (PDF)于2022-11-03）. 
11. Piché, Daniel Guy, Complex Bases, Number Systems and Their Application to Fractal-Wavelet Image Coding (PDF), University of Waterloo, 2002 [2022-11-03], （原始内容 (PDF)于2022-11-10）