查看“︁复底数进制”︁的源代码

{{NoteTA
|T=zh-hans:复底数进制; zh-hant:複底數進位;
|1=zh-hans:复底数进制; zh-hant:複底數進位;
|G1=Math
}}
'''複底数进制'''是指[[底数 (进制)|底數]]為[[虛數]]或[[复数 (数学)|複數]]的[[进位制]]系統。
其中，底數為[[虛數]]的进位制系統最早由[[高德纳]]於1955年提出<ref name="Knuth1">{{cite journal |last=Knuth |first=D.E. |title=An Imaginary Number System |journal=Communications of the ACM |year=1960 |volume=3 |issue=4 |pages=245–247 |doi=10.1145/367177.367233|s2cid=16513137 }}</ref><ref name="Knuth2">{{cite book |last=Knuth |first=Donald |authorlink=Donald Knuth |title=The art of computer programming |publisher=Addison-Wesley |location=Boston |year=1998 |volume=2 |edition=3rd |pages=205 |isbn=0-201-89684-2 |chapter=Positional Number Systems |oclc=48246681}}</ref>；底數為[[复数 (数学)|複數]]的进位制系統於1964年由所羅門·I·赫梅利尼克（Solomon I. Khmelnik）<ref name="Khmelnik1">{{cite journal |last=Khmelnik |first=S.I. |title=Specialized digital computer for operations with complex numbers
|journal=Questions of Radio Electronics (In Russian)|volume=XII |issue=2 |year=1964}}</ref>和1965年由沃爾特·F·彭尼（Walter F. Penney）提出<ref name="Penney0">W. Penney, A "binary" system for complex numbers, JACM 12 (1965) 247-248.</ref><ref name="Penney1">{{cite journal |last=Jamil |first=T. |year=2002 |title=The complex binary number system |journal=IEEE Potentials |volume=20 |pages=39–41 |doi=10.1109/45.983342 |issue=5}}</ref><ref name="Penney2">{{cite arXiv
 |last=Duda |first=Jarek
 |date=2008-02-24
 |title=Complex base numeral systems
 |eprint=0712.1309
 |class=math.DS }}</ref>。

== 概述 ==
令<math>D</math>為[[整环]]<math>\subset \C</math>和<math>|\cdot|</math>為[[绝对赋值#绝对赋值的类型|（阿基米德）绝对赋值]]。

數<math>X\in D</math>在[[进位制]]系統中可以表示為：
: <math> X = \pm \sum_{\nu}^{ } x_\nu \rho^\nu,</math>
其中
: {| class="table left"
|-
| <math>\rho \in D</math> || || 為[[底数 (进制)|底數]]，並滿足<math>|\rho| > 1</math>，
|-
| <math>\nu \in \Z</math> || || 是[[冪|指數]]，代表各個位數，
|-
| <math>x_\nu</math> || || 是进制中每個位數，來自有限的位數數碼[[集合 (数学)|集合]]<math>Z \subset D</math>，通常滿足<math>|x_\nu| < |\rho|.</math>
|}
其[[势_(数学)|势]]<math>R:=|Z|</math>稱為分解程度（level of decomposition）

[[进位制]]系統或'''編碼系統'''是一對二元組：
: <math>\left\langle \rho, Z \right\rangle</math>
包括了其底數<math>\rho</math>和位數數碼集合<math>Z</math>。通常會將有<math>R</math>個位數數碼的位數數碼集合表示為：
: <math>Z_R := \{0, 1, 2,\dotsc, {R-1}\}.</math>
理想的[[进位制]]系統或'''編碼系統'''具有以下特性：
*任何在环<math>D</math>內的數如整數<math>\Z</math>、[[高斯整數]]<math>\Z[\mathrm i]</math>或环<math>\Z\left[\tfrac{-1+\mathrm i\sqrt7}2\right]</math>的整數可以表達為為唯一的編碼，並可能帶有[[性質符號|正負號]]±。
*任何在[[分式環]]<math>K:=\operatorname{Quot}(D)</math>內的數，或者再取[[完備化]]（<math>|\cdot|</math>[[度量空間|度量]]的意義下）所得的<math>K:=\R</math>或<math>K:=\C</math>內的數，皆可以表示為在<math>|\cdot|</math>下，於<math>\nu \to -\infty</math>收斂的無窮級數<math>X</math>，且不只一種表示方式之數的集合[[测度]]為0。後者要求集合<math>Z</math>最小，即對於實數<math>R=|\rho|</math>、對於複數<math>R=|\rho|^2</math>。

== 實數 ==
在這種表示法中，一般常見的標準[[十进制]]表示為：
:<math>\left\langle 10, Z_{10} \right\rangle,</math>
標準[[二进制]]系統表示為：
:<math>\left\langle 2, Z_2 \right\rangle,</math>
負二进制系統表示為：
:<math>\left\langle -2, Z_2 \right\rangle,</math>
[[平衡三進位]]系統表示為<ref name="Knuth2"/>：
:<math>\left\langle 3, \{-1,0,1\} \right\rangle.</math>
上述這幾個[[进位制]]系統在<math>\Z</math>和<math>\R</math>中都具有上述的特性。後兩個不需要使用正負號。

== 複數 ==
較廣為人知的複底数[[进位制]]系統包括下列幾個进位制系統（其中<math>\mathrm i</math>表示[[虛數單位]]）：
* <math>\left\langle\sqrt{R},Z_R\right\rangle</math>，例如<math>\left\langle\pm \mathrm i \sqrt{2},Z_2\right\rangle</math> <ref name="Knuth1"/>（<math>\mathrm i \sqrt{2}</math>进制）和
:<math>\left\langle\pm 2\mathrm i,Z_4\right\rangle</math><ref name="Knuth2"/>，即[[2i进制]]，由[[高德纳]]於1995年提出。
* <math>\left\langle\sqrt{2}e^{\pm \tfrac{\pi}2 \mathrm i}=\pm \mathrm i\sqrt{2},Z_2\right\rangle</math>和
:<math>\left\langle\sqrt{2}e^{\pm \tfrac{3 \pi}4 \mathrm i}=-1\pm\mathrm i,Z_2\right\rangle</math><ref name="Khmelnik1"/><ref name="Penney1"/>（參見下方[[#−1_±_i进制|{{math|−1 ± i}}进制]]一節）
* <math>\left\langle\sqrt{R}e^{\mathrm i\varphi},Z_R\right\rangle</math>，其中<math>\varphi=\pm \arccos{(-\beta/(2\sqrt{R}))}</math>、 <math>\beta<\min(R, 2\sqrt{R})</math>且<math>\beta_{ }^{ }</math>是一個正整數，在給定的<math>R</math>可以取多個值<ref name="Khmelnik2">{{cite journal |last=Khmelnik |first=S.I. |title=Positional coding of complex numbers
|journal=Questions of Radio Electronics (In Russian)|volume=XII |issue=9 |year=1966}}</ref>。 比如<math>\beta=1</math>且<math>R=2</math>是指
:<math>\left\langle\tfrac{-1+\mathrm i\sqrt7}2,Z_2\right\rangle</math>进位制系統。（<math> \tfrac{-1+\mathrm i\sqrt7}2</math>进制）
* <math>\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</math><ref name="Khmelnik3">{{cite book |last=Khmelnik |first=S.I. |title=Coding of Complex Numbers and Vectors (in Russian) |publisher=Mathematics in Computer |location=Israel |isbn=978-0-557-74692-7 |year=2004 |url=http://mic34.com/Magazine/94846.pdf |access-date=2022-11-03 |archive-date=2022-11-10 |archive-url=https://web.archive.org/web/20221110205056/http://mic34.com/Magazine/94846.pdf |dead-url=no }}</ref>。
* <math>\left\langle-R,A_R^2\right\rangle</math>，其中，集合<math>A_R^2</math>由複數<math>r_\nu=\alpha_\nu^1+\alpha_\nu^2\mathrm i</math>組成，且數<math>\alpha_\nu^{ } \in Z_R</math>，例如
:<math>\left\langle -2, \{0,1,\mathrm i,1+\mathrm i\}\right\rangle</math><ref name="Khmelnik3"/>。

* <math>\left\langle\rho=\rho_2,Z_2\right\rangle</math>，其中<math>\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}</math>&nbsp;<ref name="Khmelnik4">{{cite book |last=Khmelnik |first=S.I. |title=Method and system for processing complex numbers |url=http://worldwide.espacenet.com/publicationDetails/biblio?DB=EPODOC&adjacent=true&locale=en_EP&FT=D&date=20030814&CC=US&NR=2003154226A1&KC=A1 |publisher=Patent USA, US2003154226 (A1) |year=2001 |access-date=2022-11-03 |archive-date=2023-01-09 |archive-url=https://web.archive.org/web/20230109170033/https://worldwide.espacenet.com/publicationDetails/biblio?DB=EPODOC&adjacent=true&locale=en_EP&FT=D&date=20030814&CC=US&NR=2003154226A1&KC=A1 |dead-url=no }}</ref>

== 二元系統 ==
[[複數 (數學)|複數]]的二元系統是僅使用兩個[[數碼]]——0和1的[[进位制]]系統，即位數數碼集合為<math>Z_2=\{0,1\}</math>的[[进位制]]系統，這類[[記數系統]]具有較實際的用途<ref name="Khmelnik4"/>。
下表列出了一些<math>\langle \rho, Z_2 \rangle</math>的[[进位制]]系統（皆為上述[[进位制]]系統的特例），並用其表達{{math|−1, 2, −2, '''i'''}}。
同時也列出標準的[[二进制]]（下表的第一列）和「負二进制」（下表的第二列）供比較。這兩個进位制無法真正地表達出虛數單位{{math|'''i'''}}。
{| class="wikitable" style="text-align: right;"
|+ 部分的[[进位制]]系統和一些數的表達<ref name="Gilbert">{{Cite journal | author=William J. Gilbert | title=Arithmetic in Complex Bases | journal=Mathematics Magazine | volume=Vol. 57 | number=No. 2 | date=1984-03 | url=http://www.math.uwaterloo.ca/~wgilbert/Research/ArithCxBases.pdf | access-date=2022-11-03 | archive-date=2022-11-03 | archive-url=https://web.archive.org/web/20221103035241/https://www.math.uwaterloo.ca/~wgilbert/Research/ArithCxBases.pdf | dead-url=no }}</ref>
|-
! style="text-align: right;" | 底數
! style="text-align: left;" | –1 ←
! style="text-align: left;" | 2 ←
! style="text-align: left;" | –2 ←
! style="text-align: left;" |{{math|'''i'''}} ←
! style="text-align: center;" colspan="2" | 多種表示形式的數
|-
| [[二进制|2]] || {{進制|2|-1}} || {{進制|2|2}} || {{進制|2|-2}} ||{{math|'''i'''}} || style="border-right: white" | 1 ← || 0.<span style="text-decoration: overline;">1</span> = 1.<span style="text-decoration: overline;">0</span>
|-
| –2 || {{進制|-2|-1}} || {{進制|-2|2}} || {{進制|-2|-2}} || {{math|'''i'''}} || {{sfrac|1|3}} ← || 0.<span style="text-decoration: overline;">01</span> = 1.<span style="text-decoration: overline;">10</span>
|-
|<math>\mathrm i\sqrt{2}</math> || {{進制|{{計算|sqrt(-2)}}|-1}} || {{進制|{{計算|sqrt(-2)}}|2}} || {{進制|{{計算|sqrt(-2)}}|-2}} || {{進制|{{計算|sqrt(-2)}}|i| precision=9}}...<ref group=註 name="infinite">無限不循環小數</ref> ||  <math>\frac{1}{3}+\frac{1}{3}\mathrm i \sqrt{2}</math> ← || 0.<span style="text-decoration: overline;">0011</span> = 11.<span style="text-decoration: overline;">1100</span>
|-
| <math>\frac{-1 + \mathrm{i}\sqrt{7}}{2}</math> || 111 || 1010 || 110 || 11.110001100...<ref group=註 name="infinite" /> || <math>\frac{3+\mathrm i\sqrt{7}}{4}</math> ← || 1.<span style="text-decoration: overline;">011</span> = 11.<span style="text-decoration: overline;">101</span> = 11100.<span style="text-decoration: overline;">110</span>
|-
| <math> \rho_2 </math> || 101 || 10100 || 100 || 10 || {{sfrac|1|3}}&thinsp;+&thinsp;{{sfrac|1|3}}{{math|'''i'''}} ← || 0.<span style="text-decoration: overline;">0011</span> = 11.<span style="text-decoration: overline;">1100</span>
|-
| –1+{{math|'''i'''}} || {{進制|-1+i|-1}} || {{進制|-1+i|2}} || {{進制|-1+i|-2}} || {{進制|-1+i|i}} || {{sfrac|1|5}}&thinsp;+&thinsp;{{sfrac|3|5}}{{math|'''i'''}} ← || 0.<span style="text-decoration: overline;">010</span> = 11.<span style="text-decoration: overline;">001</span> = 1110.<span style="text-decoration: overline;">100</span>
|-
| [[2i进制|2{{math|'''i'''}}]] || {{進制|2i|-1}} || {{進制|2i|2}} || {{進制|2i|-2}} || {{進制|2i|i}} || {{sfrac|1|5}}&thinsp;+&thinsp;{{sfrac|2|5}}{{math|'''i'''}} ← || 0.<span style="text-decoration: overline;">0033</span> = 1.<span style="text-decoration: overline;">3003</span> = 10.<span style="text-decoration: overline;">0330</span> = 11.<span style="text-decoration: overline;">3300</span>
|}
與所有具有[[绝对赋值#绝对赋值的类型|阿基米德绝对赋值]]的[[进位制]]系統一樣，有些數字具有多種表示形式。此類數字的範例顯示在表格的右欄中。這些數都是循環小數，其循環節以上標水平線標記。

== 进制轉換 ==
若要將一[[高斯整數]]<math>z</math>轉換為一個以高斯整數<math>b</math>為[[底数 (进制)|底數]]的[[进位制]]<math>\left\langle b, Z_R \right\rangle</math>可以將[[數]]分成一個可被底數整除的高斯整數和一個位於位數數碼集合內的數，並將可被底數整除的高斯整數部分除以底數當作商，位於位數數碼集合內的數當作餘數，並用商數繼續計算，並重複以上步驟，直到商為零，一系列的餘數部分即為轉換完成的結果。<ref name="article piche2002complex">{{citation
  |title=Complex Bases, Number Systems and Their Application to Fractal-Wavelet Image Coding
  |author=Piché, Daniel Guy
  |year=2002
  |url=https://www.collectionscanada.gc.ca/obj/s4/f2/dsk3/OWTU/TC-OWTU-243.pdf
  |publisher=University of Waterloo
  |accessdate=2022-11-03
  |archive-date=2022-11-10
  |archive-url=https://web.archive.org/web/20221110205046/https://www.collectionscanada.gc.ca/obj/s4/f2/dsk3/OWTU/TC-OWTU-243.pdf
  |dead-url=no
  }}</ref>{{rp|41}}

:<math>z_{\,}=q_1b+a_0</math>
:<math>q_1=q_2b+a_1</math>
:<math>q_2=q_3b+a_2</math>
:<math>\quad\quad\vdots</math>
:<math>q_t=0_{\,}b+a_t</math>
其中，<math>q_1</math>、<math>q_2</math>、<math>q_3</math>……<math>q_t</math>為高斯整數，<math>a_1</math>、<math>a_2</math>、<math>a_3</math>……<math>a_t</math>為位於位數數碼集合內的數，

則<math>z=\left(a_t\cdots a_2a_1a_0\right)_b</math>。

以5+12i轉換成-2+i进制（<math>\left\langle -2+\mathrm i, \{0,1,2,3,4\}\right\rangle</math>）為例：<ref name="article piche2002complex"/>{{rp|42}}
:{| class="table left"
|-
|align=right| <math>5+12\mathrm i</math> || <math>=</math> ||align=right| <math>\left(2-5\mathrm i\right)\left(-2+\mathrm i\right) + 4</math>
|-
|align=right| <math>2-5\mathrm i</math> || <math>=</math> ||align=right| <math>\left(-1+2\mathrm i\right)\left(-2+\mathrm i\right) + 2</math>
|-
|align=right| <math>-1+2\mathrm i</math> || <math>=</math> ||align=right| <math>\left(2\right)\left(-2+\mathrm i\right) + 3</math>
|-
|align=right| <math>2</math> || <math>=</math> ||align=right| <math>\left(0\right)\left(-2+\mathrm i\right) + 2</math>
|}
故5+12i<sub>(10)</sub>轉換成-2+i进制為{{進制|-2+i|5+12i|sub=1}}。

== {{math|−1 ± ''i''}}进制 ==
{{Anchor|-1+i进制|−1+i进制|-1-i进制|−1−i进制|-1±i进制|−1±i进制}}[[Image:ComplexTwindragon.svg|thumb|right|290px|在{{math|−1+''i''}}進位制系統中整數部分全為零的複數]]
較常被討論的複底数进制是[[2i进制]]和{{math|−1 ± i}}进制（[[-1+i进制|{{math|−1 + ''i''}}进制]]和{{math|−1 − ''i''}}进制），因為其皆可不使用正負號有限地表達所有[[高斯整數]]。

{{math|−1 ± ''i''}}进制以0和1为基本數碼，其於1964年由所羅門·I·赫梅利尼克（Solomon I. Khmelnik）<ref name="Khmelnik1"/>和1965年由沃爾特·F·彭尼（Walter F. Penney）提出<ref name="Penney0"/><ref name="Penney2"/>。

{| class=wikitable
|+ {{math|−1±''i''}}進制與相關進制比較
|-
![[十進制]]
![[二進制]]
![[2i進制]]
!{{math|−1+''i''}}進制
!{{math|−1−''i''}}進制
|-
| 0 || {{進制|2|0}} || {{進制|2i|0}} || {{進制|-1+i|0}} || {{進制|-1-i|0}}
|-
| 1 || {{進制|2|1}} || {{進制|2i|1}} || {{進制|-1+i|1}} || {{進制|-1-i|1}}
|-
| 2 || {{進制|2|2}} || {{進制|2i|2}} || {{進制|-1+i|2}} || {{進制|-1-i|2}}
|-
| −1 || {{進制|2|-1}} || {{進制|2i|-1}} || {{進制|-1+i|-1}} || {{進制|-1-i|-1}}
|-
| −2 || {{進制|2|-2}} || {{進制|2i|-2}} || {{進制|-1+i|-2}} || {{進制|-1-i|-2}}
|-
| {{math|''i''}} || {{math|''i''}} || {{進制|2i|i}} || {{進制|-1+i|i}} || {{進制|-1-i|i}}
|-
| {{math|2''i''}} || {{math|{{進制|2|2}}''i''}} || {{進制|2i|2i}} || {{進制|-1+i|2i}} || {{進制|-1-i|2i}}
|-
| {{math|3''i''}} || {{math|{{進制|2|3}}''i''}} || {{進制|2i|3i}} || {{進制|-1+i|3i}} || {{進制|-1-i|3i}}
|-
| {{math|−''i''}} || {{math|−''i''}} || {{進制|2i|-i}} || {{進制|-1+i|-i}} || {{進制|-1-i|-i}}
|-
| {{math|−2''i''}} || {{math|{{進制|2|-2}}''i''}} || {{進制|2i|-2i}} || {{進制|-1+i|-2i}} || {{進制|-1-i|-2i}}
|-
| {{math|−3''i''}} || {{math|{{進制|2|-3}}''i''}} || {{進制|2i|-3i}} || {{進制|-1+i|-3i}} || {{進制|-1-i|-3i}}
|-
| {{math|1+''i''}} || {{math|1+''i''}} || {{進制|2i|1+i}} || {{進制|-1+i|1+i}} || {{進制|-1-i|1+i}}
|-
| {{math|1−''i''}} || {{math|1−''i''}} || {{進制|2i|1-i}} || {{進制|-1+i|1-i}} || {{進制|-1-i|1-i}}
|-
| {{math|−1+''i''}} || {{math|−1+''i''}} || {{進制|2i|-1+i}} || {{進制|-1+i|-1+i}} || {{進制|-1-i|-1+i}}
|-
| {{math|−1−''i''}} || {{math|−1−''i''}} || {{進制|2i|-1-i}} || {{進制|-1+i|-1-i}} || {{進制|-1-i|-1-i}}
|}

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

由此，複矩形
: <math>[-\tfrac8{15},\tfrac2{15}]\times[-\tfrac4{15},\tfrac1{15}]\mathrm i</math>
透過[[单射]]
: <math>\textstyle \sum_{k\geq 1}x_k (\mathrm i-1)^{-k} \mapsto \sum_{k\geq 1}x_k b^{-k}</math>
映入實數[[區間]]<math>[0, 1)</math>，其中<math>b > 2</math><ref group=註>不能取底數<math>b = 2</math>，因為<math>\textstyle 2^{-1} = 0.1_{\text{bin}} = 0.5_{\text{dec}} </math>且<math>\textstyle \sum_{k\geq 2} 2^{-k} = 0.0\overline{1}_{\text{bin}} = 0.1_{\text{bin}} = 0.5_{\text{dec}}</math>。 然而，<math>\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</math>不等於<math>\textstyle \sum_{k\geq 2} (\mathrm i-1)^{-k} = 0.1_{\text{dec}} +0.3_{\text{dec}} \mathrm i </math>。</ref>。

此外，還有兩個映射
:<math>\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}</math>
和
:<math>\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}</math>
兩者皆[[满射]]，也就是產生了一個滿射（空間填充）的映射
:<math>[0,1) \qquad \to \qquad S </math>
然而，其並不連續，因此不是空間填充曲線。但是一個類似的曲線——戴維斯-高德納龍（Davis-Knuth dragon），是連續的空間填充曲線。

== 註釋 ==
{{Reflist|group=註}}

== 參考文獻 ==
{{Reflist}}

{{Pns}}

[[Category:非标准进制系统]]
[[Category:分形]]
[[Category:複數]]
[[Category:環論]]