数字逻辑层

USB总线显卡等高速设备是十分适合通过PCI/PCIe连入计算机的。但对于键盘、鼠标等设备而言，如果每个设备都占用1个PCI/PCIe的“席位”，那么代价就会较昂贵。于是IBM、Intel、微软等公司联手设计了一种将低速设备连入计算机的方案，于1998年正式发布，称为通用串行总线(USB)。USB设备无需复杂的跳线和插槽、安装设备无需重启，单机可接入127个设备(采用7位的设备地址)，设备直接由数据线供电。USB经过多年的版本迭代，从USB1.0时的1.5Mbps带宽发展到目前USB3.2 Gen2的10Gbps带宽。 USB由接入系统总线(PCI/PCIe)的USB根集线器实现，根集线器可接入设备或扩展集线器，扩展集线器可提供更多接口用于接入设备，故其拓扑结构类似于以根集线器为根的树结构，具体如上图所示。… 阅读全文

接口电路接口电路是指计算机之间，计算机与外围设备之间，计算机内部部件之间起连接作用的电路。一般由寄存器组、专用存储器和控制电路几部分组成，当前的控制指令、通信数据、以及外部设备的状态信息等分别存放在专用存储器或寄存器组中。 接口电路这4个字容易令人望文生义，联想到PCIe接口、USB接口。实际上接口电路一定程度上与总线这个概念平行，并且有部分的重合。接口电路强调两个部件直连，总线强调多个部件用公共的总线互连。接口电路强调信号和数据形式的转换，总线更注重可扩展性、灵活性、规范化。接口与总线有时也不加区分，合称为总线接口。通常接口电路是连入计算机系统总线的，比如INTEL 8255A接口电路芯片。 上图是个类似INTEL 8255A的接口电路芯片引脚图，是种并行IO接口(PIO)芯片。右边3×8根IO信号线可用于连接各种支持它的IO设备，可以是键盘，开关等。左边包括接入总线的D0-D7信号线，WR/WD的写信号线/读信号线，RESET充值信号线，A0-A1的地址信号线，CS片选信号线。该PIO接口芯片可通过3位的配置寄存器配置，来设置3个Port的输入输出，而每个Port都会对应一个8位锁存器用来暂存数据。… 阅读全文

二进制数据的检错纠错 计算机在用“高低电平”的方式传输和表示数据的时候，会因为电平毛刺等导致某些位出错，这时就需要相应的数据纠错检错的机制。比如多用于服务器的ECC内存，其同时具备纠错和检错功能。而普通PC内存通常只有检错功能。计算机电路结构使数据出错时不会出现“多位或少位”的情况，只会出现“位值”的错误，并且多个位中的每个位是否出错可看作是概率独立的。 目前主要的纠错检错机制是纠错码，其核心是在原字(数据位)额外加若干位(校验位)，新数据称为码字(用于和字区分)，码字同样是定长的，实际传输数据会传输码字而不是字。下面通过汉明距离给出编码方案与纠错检错能力间的关系，汉明距离的定义之前在<算法>中讨论过： 1) 若两两合法码字的汉明距离是\(d+1\)且错误不大于\(d\)位则必可检错。因为到合法码字汉明距离为\(1-d\)的所有数据中，不可能有合法码字；… 阅读全文

字符 大多数计算机中的数据和指令都是二进制位形式的。注意这里区分一下二进制位和二进制数，二进制数是数学概念，而机器本身是“无法理解”数学概念的，只能按照人类规定的范式处理二进制位。只有人类规定好相关范式，计算机才能把二进制位当作数来处理。之后可能不去区分二进制位和二进制数的概念。 想要让计算机存储和表示字符，需要用公认和权威的标准，建立其与二进制位的映射关系，否则计算机间很难交互。这种映射称为字符编码。其由国际机构或国家机构制定。可分为如下2部分： 1) 字符集：规定了语言包含的所有字符和标点符号等。但语言是比较复杂的，比方说让大陆、香港、台湾、日本出具一份汉字的字符集，那它们可能出的不一样。所以汉语这“一种语言”就有国际、大陆、台湾等的多个版本的字符集； 2) 编码：编码是指给定字符集中的字符的区分和表示的方案，对于非计算机有莫尔斯电码的方案，计算机则通常用定长或变长的二进制数来做编码。考虑到二进制数表示字符常需要较多的位，以及机器中数据的位数常以字节为倍数，在很多时候又会用十六进制来表示二进制的编码；… 阅读全文

整数的带余除法定理 余数在计算机中非常重要，二进制计算机只能用有限数目的二进制位处理和表示数据。当数据超出这个限制时，会被截断。这个特点可以用余数描述，而余数本身是由整数除法定义的。在小中学阶段就会学习余数，但主要是学习如何求余数，没有提到除法和余数的严格定义，以及对整数的严格定义。这部分内容属于数学中的整数理论。整数集中的除法和余数是由如下事实定义的，其本身也是一个定理，是整数理论的重要基础： a) 整数的带余除法定理：设\(a,b(b>0)\)为任意整数，存在唯一整数对\(q,r\)，使\(a=bq+r\)，其中\(0\leq r < b\)； 其中\(q,r\)是商和余数，计做\(a\div b = q……r\)，读作a除以b等于q余r。需注意的是上述定义包含了被除数为负的情况，而小中学阶段没有讨论过这种情况。另外这种除法和平时做数学计算的除法有一些区别：… 阅读全文

无符号整数的机器级表示 计算机是通过二进制位存储和传输数据的。虽然这些二进制位适合表示二进制数，但还是有一定区别，比如寄存器和总线的位数通常是固定的，另外对于负号、小数点、分数等等都不能直接表示，需要规定一些规则计算机才能处理。这些规则中，最简单的就是对无符号整数的表示，无符号整数顾名思义就是没有符号的整数，也就是自然数。这种表示和数学上的表示几乎没有区别，只需要预先规定好占用的位数，并且需要高位补0，比如在4位无符号整数表示下，3要写作0011，而3对应的二进制数是11。 一般的k位无符号整数，能表示的十进制数范围是闭区间的\([0,2^k–1]\)。   无符号整数的加法 之前讨论行波进位加法器时，没有规定如何处理最低位进位输入、最高位进位输出，这里规定为“忽略最高位进位的输出，最低位进位输入始终保持0”。当两个\(k\)位无符号整数码输入到\(k\)位加法器(\(k\)个1位加法器组成的行波进位加法器)，若结果未超出\(k\)位，那么加法器的输出就是正确的和。但若超出\(k\)位(两个\(k\)位无符号整数码经过加法器最多只能超出1位)，则加法器会忽略掉最高位的进位，剩下的\(k\)位才是最终输出，这种情况称为加法器的溢出，可通过余数描述。在这种规定下，这种\(k\)位加法器就能做\(k\)位无符号整数码的加法，具体这样描述：… 阅读全文

有符号整数的机器级表示 使用二进制位表示能带负号的有符号整数时，需要额外占用1个位来表示正负。有如下3种公认的表示方案： 1) \(k\)位原码：最高的第\(k\)位表示符号，称为符号位。0表示正数，1表示负数。剩下的位称为数值位，按\(k-1\)位无符号整数的方式表示绝对值。注意在原码下0有两个码，比如在4位下0有0000和1000的2种表示。这时会定义前者为负的-0，后者为正的+0(也就是0分为正数和负数两个)。\(k\)位原码的取值范围是\([ -(2^{k-1}-1), 2^{k-1}-1 ]\)； 2) \(k\)位反码：正数(含+0)为其原码，负数(含-0)为其原码“符号位不变，其他位取反”。反码取值范围和原码一样； 3) \(k\)位补码：正数(含+0)为其原码，负数(含-0)为其反码+1。补码中的-0会溢出，比如4位反码1111的原码会溢出，使其变为0000，也就是-0和+0一样，所以补码无需区分-0与+0。这里还有个问题是补码1000的意义不明确，在补码中会直接规定其表示-8。故4位补码的能表示-8~7，其中只有1个补码表示0，一般的\(k\)位补码的取值范围是\([… 阅读全文

定点小数的机器级表示 前面讨论过用无符号整数码和补码表示整数，如果约定这两种码的固定位置有小数点，那这两种码也能表示这种数，称为定点数(定点小数)。这样一来整数就是定点小数的特例，整数可看作是小数点在最低位右边的定点小数。一般来说可以约定小数点在最高位之前(纯小数)到最低位之后(整数)的任意的\(k+1\)个位置上。 定点整数和数学中整数的区别不大，除了不能处理无穷。但定点小数和数学中的小数则有区别，定点小数的取值范围更像“以二进制0.1(\(2^{-1}\))、0.01(\(2^{-2}\))…为步长的整数”。比如1个4位的码1111，将其看作无符号整数码，表示15。将其看作小数点定在第2位之前的无符号小数码，表示\(15\times 2^{-2}\)。虽然计算机不直接存储小数点位置，为方便也可写作11.11。… 阅读全文

浮点数的机器级表示 （1） （2） 前面讨论的都是定点数，其特点是小数点位置静态不可变，且小数点位置本身没有硬件来存储。浮点数则是完全不同的结构，因为每个浮点数必须记录自身小数点的位置，“浮点”这个名字就是是指小数点位置可变。于是设计浮点数的表示方案会更复杂，而且小数的数学性质本身也更复杂一些，比如前面讨论过，小数进制转换天生就有精度丢失问题。 目前权威的浮点数方案是数值专家William Kahan主导的IEEE754，采用科学记数法以\((-1)^s\cdot M \cdot 2^N\)计数，科学记数法中的基数与指数在IEEE754中称为尾数与阶数。在计算机中会从高位到低位存储\(s,N,M\)，对\(s,N,M\)的具体规定如下： 1) \(s\)：符号位，表示浮点数的符号，规则是0正1负； 2) \(M\)：即尾数(指小数的尾数)；… 阅读全文