广义的进制系统

本页使用了标题或全文手工转换
维基百科,自由的百科全书

广义的进制系统非标准进制系统指的是可以简单地描述为进制系统但不完全符合标准进制系统的记数系统

在标准的进制系统中,底数b应为整数,并且这些与b不同的各个数字可以用来表达所有非负整数。标准进制在表示数字时使用0, 1, 2, 3...到b-1来表示各个位数,但其值根据该数字所在的位置进行加权。例如,以b为底的数字字符串pqrs的值可由多项式的形式给出:
上标表示底数在该位的
例如在十六进制(b=16)中,使用符号A表示10,B表示11等,数字字符串7A3F表示:
在常用的十进制表示法表示为31295。
若引入小数点“.”和负号“-”,则可以表达任意精度的实数。

本文总结了一些非标准进制系统的实际情况。在大多数情况下,用于描述标准进制系统中的多项式形式仍然适用。

一些历史上使用的数字系统可能被描述为非标准进制系统。例如六十进制巴比伦数字和中国的算筹,其分别可以归类为以60为底和以10为底的标准进制系统,而将表示零的空间计为数字的系统以及更具体地考虑到构成数字的原始重复字形,具有一元组成的混合底数系统,都可以归类为非标准进制系统。

然而,大多数的非标准进制系统都未用于一般用途,而是由数学家或工程师设计用于特殊的学术或技术用途。

双射记数系统

以b为双射记数系统使用b个不同的数字符号来表示所有非负整数。 其所使用的数字为1、2、3...并包括n,但不包括0,而零由空串表示。

一进制

一进制是一种以1为底数的双射记数系统,其仅使用一个符号来表达所有正整数[1]。一进制的数字字符串pqrs可由多项式的形式给出:

其可以直接简化为,因为对所有的n,在b=1时,始终为1。这个记数系统非标准的原因包括

  • 数字的值不取决于它所在的位置,因此其是否能视为一个进制常出现争议。
  • 该系统即使引入了小数点也无法表达非整数的数字
  • 其使用1来表示数字,而标准进位制最多仅能用到底数减一(b-1),而一进制b-1=0
  • 无法表示0(仅能隐含地使用空串表示)

有符号位数进制

部分进制使用正整数作为底数,但允许负值作为其单个位数。非相邻形式英语Non-adjacent form是底数为2的有符号位数进制的特有形式。在平衡三进制,即底数为3的有符号位数进制中,使用-1、0和1来表示数字。[2]

非正整数底数的进制

有些进制系统的底数不是正整数

负底数进制

负底数进制包括了负二进制、负三进制、负十进制等。[3]在-b进制中使用b个符号来表达数字。由于负的幂的特性会在正与负交替,因此负底数进制可以不使用正负号就表达正数与负数。

复底数进制

在纯虚数底数bi进制的系统中,需要由b2个数字来表示数,为0到b2-1,其中,b是大于1的整数,i是虚数单位。[4]其可以进一步的推广到任意复数的底数,即复底数进制。若一复底数进制的底数为b,则其需要个数字来表示数。[5]

非整数进制

在底数为非整数的进制系统中,用于表示数的符号个数显然不能是b(b为底数,此例底数不是整数),而是使用从0到的数字。例如黄金进制使用两个数字来表示数,分别为0和1。

混合底数进制

有时进制的各个位数的权值使用非1、 bb2b3......的几何级数之多项式形式更为方便。在混合底数的进制系统中,如阶乘进制,其各个位数的权值形成一个数列,数列每个权值都是前一项的整数倍,同时也允许每个位数有不同的符号个数,例如在阶乘进制中,权值为2!的位数使用2个符号(0、1)、权值为3!=6的位数使用3个符号(0、1、2)、权值为4!=24的位数使用4个符号(0、1、2、3)。

玛雅历法所使用的马雅数字系统就是一个混合底数进制系统的例子,因为要配合360日的历法,因此其有一个位数使用的底不是20而是18。此外以度、分、秒表示的角度或以天、小时、分钟、秒表示的时间都可以看做是混合底数的进制系统的一个例子。

也有一些进制各个位数的权值使用的不是每一项皆为前一项之整数倍的数列来表示数,但这种进制系统在表达整数时可能会使同一个数有多种表示方式。例如斐波那契进制斐波那契编码,其使用0和1来表示数,而各个位数的权值为斐波那契数列(1、 2、 3、 5、 8...... );这个进制系统可以透过避免使用连续的1来使每个数有唯一的表示方式。二进码十进数也是一种混合底数进制系统,其每四个位数是一组二进制数,底数为2,而四个位数与下四个位数之间有底数10,例如1001 0011较低的四个位数表示三,较高的四个位数表示九,这8个位数表示的数为九十三。在这8个位数中的权值为80、40、20、10、8、4、2和1。

非对称记数系统

非对称记数系统是在计算机科学中使用的一种记数系统,其不仅每个位数的底数不同(通常会是非整数的底数),甚至还可以是非均匀的,并以非对称的方式改变,以便更有效率地编码信息。其对所选用的符号非均匀的几率分布进行优化,以平均每个符号大致上的信息熵[6]

参考文献

  1. ^ Davis, Martin; Sigal, Ron; Weyuker, Elaine J., Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science, Computer Science and Scientific Computing 2nd, Academic Press: 117, 1994 [2023-01-18], ISBN 9780122063824, (原始内容存档于2023-01-21) .
  2. ^ Douglas W. Jones. Ternary Number Systems. 2013-10-15 [2023-01-18]. (原始内容存档于2023-01-21). 
  3. ^ Petkovšek, Marko, Ambiguous numbers are dense, The American Mathematical Monthly, 1990, 97 (5): 408–411, ISSN 0002-9890, JSTOR 2324393, MR 1048915, doi:10.2307/2324393 .
  4. ^ Herd, Philip. Imaginary Number Bases. arXiv. [2023-11-11]. doi:10.48550/ARXIV.1701.04506. (原始内容存档于2023-11-11). 
  5. ^ Gilbert, William J. Arithmetic in complex bases. Mathematics Magazine (Taylor & Francis). 1984, 57 (2): 77–81. 
  6. ^ Duda, Jarek and Tahboub, Khalid and Gadgil, Neeraj J and Delp, Edward J. The use of asymmetric numeral systems as an accurate replacement for Huffman coding. 2015 Picture Coding Symposium (PCS) (IEEE). 2015: 65–69 [2023-01-18]. (原始内容存档于2017-01-06).