复底数进制

复底数进制是指底数为虚数或复数的进位制系统。

其中，底数为虚数的进位制系统最早由高德纳于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），是连续的空间填充曲线。