计算机中的加法
计算机的记数制系统及实验在使用C语言和Verilog HDL 设计信号处理电路的实验过程中， 把理论算法模型 使用编程语言映射到目标平台上是一个难点。 在教科书和仿真工具中， 大部分数学模型都是采用 浮点格式数据进行描述和仿真。 然而， 由于芯片成本和计算速度的限制， 对于目标器件而言， 整数定点格式应用的更为广泛。 为了让选课同学更好的理解计算机平台上的定点小数格式， 本文抛砖引玉，希望能对定点小数处理进行一点肤浅的介绍， 同时本文在Github上提供了2个简单的参考代码， 以供同学们进行实验。
人类对数字的认识和使用， 最早源自于远古时期对生产和生活资料的积累与分配， 在古代结绳记事的年代 正整数已经可以完全满足我们的日常需要。 随着生产力的发展， 更加复杂与精细的测量系统和数字表示方法被 逐渐使用， 从而用于满足更加复杂的使用需求。
所谓记数制（Numeral System）系统，是指用来表示数字的方法， 以及所采取的相应计算法则。 这里尤其需要关注的是， 数值的表示形式 和和其计算方法严格对应的。 举例来说：
从上面的例子可以看到， 虽然都是在某个数值的基数上增加 1000， 但是计算的方法却迥然不同。 所以， 我们在 使用计算机解决实际问题时也同样需要注意， 不但需要用正确的格式表示数据， 还需要对数据采用正确的计算法则。
计算机是人类最重要的发明之一， 在计算机的存储和运算过程中， 所有信息均用数字来表示。 现代计算机通常采用分层的存储结构， 需要处理的数据被存放于主存储器（RAM）中， 中央处理器（CPU） 把数据逐个从RAM中读取到CPU的寄存器（Register）中， 然后由算术逻辑单元（ALU）对寄存器中的数据进行计算， 计算的结果又会被写回到寄存器中， 然后再被写出到主存储器里。
下图给出了一个简化的计算机中执行整数加法的过程。 两个存放于RAM中的数字， 4 和 9 ， 被分别加载到寄存器R1 和 R2 中， 由 算术单元 ALU 执行相加的操作， 加法的结果被输出到寄存器 R3 中， 随后写出到 RAM里。
|
计算机中的加法 |
使用计算机进行数据处理中的另一个重要概念是字长， 所谓字长， 是指CPU一次运算操作能够处理的最长的二进制位数。 当前的主流处理器字长通常为32甚至为64。 早期的计算机的字长为8， 即 CPU 中寄存器的数据宽度为 8 个比特， ALU 运算单元一次只能完成 8比特宽度的数值计算。 下图示意了寄存器中的两个8比特数值被ALU单元相加生成一个8比特结果。
 8比特数据加法 |
上文例子中 两个加数分别是 110 和 30 ， 结果 是 140，这些数字均小于 8比特二进数能够表示的最大数值 255（十进制）， 即： 1111 1111 (二进制) = 255(十进制) 。 于是，善于质疑的读者会提出问题， 如果两个加数均不超过255， 但是加法和大于 255 ， 将会得到怎样的结果？ 比如十进制的 130 和 150 相加， 理论上的结果是280。 但是8比特字长无法承载280这个数据。 实际上CPU在遇到这种情况时，会在8比特的结果寄存器中保留数值 24 （即10进制的280换算成2进制数 1 0001 1000 的低8位）， 然后 会将一个特殊的寄存器的某个标志位的值设为1， 通常是中断标志（Interrupt Flag）寄存器的溢出（Overflow）标志位， 这会引发一个 “硬件异常 （hardware exception）”， 导致处理器发生指令跳转并执行异常处理的程序代码。
关于有限字长问题， 历史上曾经有过两次著名事件， 分别是“千年虫”问题和 欧洲航天局的阿丽亚娜火箭爆炸事件。 千年虫问题由于日期数据格式的字长不足，年份数据仅有2位10进制数据，从而导致计算机无法正确计算跨越公元2000年前后的时间长度， 例如计算一笔从1999年到2001年的存款利息，会出现不正确的巨大数值。 千年虫问题最终由计算机工业的各个分支机构共同修正软件和数据格式得以解决， 最终没有造成巨大的社会危害。 阿丽亚娜火箭爆炸事件， 被称为有史以来最昂贵的软件错误， 由于软件测试工作的疏漏， 该火箭控制飞行姿态的处理器使用的16比特字长数据发生了溢出， 最终导致价值上亿美元的火箭和卫星载荷的飞行姿态异常发生自爆。
在计算机系统中， 最常用的是整数运算是加法和减法， 其次是乘法，最复杂的整数计算是除法。 对于不同的计算机处理器而言， 其加、减法的操作均使用 算数运算单元 ALU 中的硬件电路来完成。 低端的处理器如果没有配备硬件的整数乘法电路，通常使用软件的方法，用多次的加法来完成乘法计算。 除法的情况和乘法类似， 如果处理器没有硬件除法电路， 也可以使用软件编程 通过多次的数值比较和整数减法来实现除法运算。
在计算机系统中， 最简单的是正整数运算，并且结果仍然是正整数的情况。 比如， 正整数的加法和乘法。
在进行加法和乘法计算时， 最需要注意的是字长问题。 这里需要引入动态范围（dynamic range）的概念， 所谓动态范围是指变量数值变化范围的边界值。 例如：
以十进制数举例：
 十进制正整数的乘加运算 |
在计算机中， 上图中的过程，以二进制表示的计算过程如下图所示， 图中也根据计算结果先行扩展了计算数据的高位字长。
 二进制正整数的乘加运算 |
上文内容中，正整数的乘加运算是记数制系统中最简单的情况， 只要合理规划好字长， 就可以得到相应的正确结果。 然而， 计算机系统中还需要能够表示“负数”和 “减法”这一常用的记数形式及运算法则。
我们在小学数学的速算训练时， 会遇到所谓“补数”这种概念。 “补数”可以通过加法来计算减法。 例如：
对于十进制的补数而言， 上面的例子似乎对加速计算的帮助有限。但是在二进制中，情况则大不一样， 补码格式大有用处。
二进制的补码（2's Complement Code）， 简称 2补码， 是计算机系统中用来表示负数的方法， 从而用负数的形式把减法转化成加法。 2补码数据的格式定义为： 最高位是符号位， 从次高位到末位是数值位。 请注意， 该定义隐含的表达了一个意思， 就是要先确定数据的字长， 否则2补码无从谈起。
下图给出了 4比特字长二进制数据的2补码的2进制和十进制表示对应关系， 图中可见， 4比特2补码可以表示从 -8 到 +7 共 16个整数。
 4比特字长 2 补码数值 |
从上图中可以看到， 正数的最高位总是 “0”， 负数的最高位总是“1”。
对于 N比特2进制数 A， 其表示方法为：
实际应用中， 正数和负数之间的2补码可以有更简便的计算方法。 例如： 若 已知数 A ， 求它的相反数 -A， 则可以把数 A 按照比特位取反， 然后在最低位加上1。 举例如下：
从上面的例子可以看到， 2 补码数值的符号取反过程计算复杂度不大， 仅需要进行位取反和加法操作， 计算机系统由此可以把整数减法计算转换为整数符号取反和加法运算。举例来说：
从上面的例子可以看出， 在2补码的格式下， 整数的加减法可以统一成2补码的符号取反和加法运算， 这对于简化处理器的数字电路设计很有帮助。
符号扩展（Sign Extension） 是补码系统中最重要的话题之一。 如前文所述， 2补码数据的含义是定义于字长的前提下的。
下面表格中给出了若干数值在不同字长时的二进制格式
| 数值 | 4比特字长 | 8比特字长 | 16比特字长 |
|---|---|---|---|
| 1 | 0011 | 0000 0011 | 0000 0000 0000 0011 |
| 2 | 0010 | 0000 0010 | 0000 0000 0000 0010 |
| 3 | 0011 | 0000 0011 | 0000 0000 0000 0011 |
| 4 | 0100 | 0000 0100 | 0000 0000 0000 0100 |
| -1 | 1111 | 1111 1111 | 1111 1111 1111 1111 |
| -2 | 1110 | 1111 1110 | 1111 1111 1111 1110 |
| -3 | 1101 | 1111 1101 | 1111 1111 1111 1101 |
| -4 | 1100 | 1111 1100 | 1111 1111 1111 1100 |
符号扩展的含义是， 当把一个2补码数值，扩展为更长的字长时，需要在多出来的高位比特位置上， 填充上该数值原来的符号位。 从表格中可以看到：
至此， 需要回顾上一节中的加法问题，
但是， 如果计算 -3 - 6 ，其理论上的结果是 -9， 但是 -9 已经超出了 4比特2补码的表示范围，结果又会如何？
本来想要 -9， 现在却得到 7 ，出现这样的结果，究其原因是因为， 没有扩展字长。 上面的计算过程， 为了得到正确的结果， 需要先把字长扩展到5比特， 按照如下过程计算：
另外， 值得注意的是， 2补码格式还有一个优良的累加溢出性质： 当多个2补码数据相加时， 如果加法的中间结果溢出， 但是如果理论上的最终结果是不溢出的， 则2补码数的加法结果也不会溢出。 举例如下：
以上这种累加溢出特性， 在进行信号处理和数值分析等科学计算任务时非常有用， 可以先通过理论分析出计算结果的最大字长， 然后以之作为累加器字长， 对于大规模计算任务能够节省资源提高效率。
在数值计算中， 我们经常需要使用小数。 虽然在计算机中使用二进制来表示小数系统， 但是其含义和数学中的十进制小数系统是类似的。 下图给出了十进制和二进制小数系统的对比示意。
 十进制与二进制小数对比图 |
接下来， 计算机系统需要解决如何表示小数点的问题，在数学中，有2种小数的表示方法
以上两种表示方法， 在计算机系统中均有使用， 前者发展成为浮点数格式， 后者发展成定点数表示方法。
为了表示小数， 计算机工业制定了 IEEE754标准， 被称为 “浮点数标准”。 为了适应不同的需要， IEEE754标准定义了 16、32 、64 、 128 比特 多种字长的小数表示方法 。 其中最常用的是 32比特字长的小数格式，即，float 单精度浮点。 下图给出了 32比特 单精度浮点数的格式， 各部分数值的含义， 以及一个计算样例
 IEEE 32bit 单精度浮点数格式及计算样例 |
从上图中可以看出， 浮点数采用的是类似科学记数法的表示方式， 即整个数据字长被分为 符号位、指数、小数（尾数）三部分。 其中，尾数被折算为一个介于1和2之间的数据， 然后根据折算出来的指数再确定小数点的位置。 由于小数点的位置是随着数据内容动态确定的， 浮点数也因此而得名。 浮点数的优点是能够有效的利用数据字长， 由于采用了指数方法， 这种格式能够有效的表示较大和较小的数值。
计算机系统中， 浮点数的计算比整数计算需要消耗更多资源， 浮点数的乘法较为容易，只需要对尾数做乘法，以及对指数做加法， 如果计算结果出现数量级的变化， 则还需调整指数， 以规范化尾数数值。
以十进制为例
浮点数做加法较为困难， 因为需要先调整加数的指数， 把运算的两个加数的小数点对齐， 运算完毕后还需要再次调整指数数据， 以把尾数的计算的结果进行规范化， 使得尾数部分介于1和2之间。
以十进制为例，
从上面的例子可以看出， 当加数的指数不一致时， 需要把小的数据向大的数据看齐。 当尾数相加产生了数量级变化时， 需要调整指数， 重新把尾数调整回规定的范围。
同样的过程也发生在二进制系统中，处理器中的浮点运算单元因为需要动态处理指数，以及动态的对尾数进行规范化，从而使其成为一个复杂的部件。 IEEE754 浮点数 是由 编译器和语法关键字来支持的， 例如 C语言中的 float 和 double 类型的变量， 会被编译器映射为IEEE754的数据格式， 由浮点运算单元对其进行处理。 如果处理器中没有浮点运算单元， 该处理器仍可以使用整数运算单元对浮点数进行运算， 代价是需要更多的指令周期，从而导致较长的计算时间。
如前文所述，虽然浮点数能够有效的表示较大和较小的数值， 但是由于其运算过程复杂，会消耗较多的计算资源。 于是在计算机系统中还会采用一种“定点小数 （fixed point fraction）” 的小数表示方法。 和浮点数不同的是， 定点数格式， 是数值计算代码开发人员在程序代码中自定义的一种小数格式。 在定点格式中，小数点对编译器是透明的， 即编译器并不知道小数的存在， 编译器输入的所有变量都是整数类型， 只有程序员知道小数点的存在。
同样， 仍以十进制为例 ：
但是，在上述格式下， 无法表示 20.1 * 5 = 100.5 ， 以及 0.01 * 0.1 = 0.001 也无法表示。 如果出现定点格式数据容量不够大， 或者精度不够的情况， 说明该定点格式没有经过充分考虑， 无法充分适应计算过程中的数据动态范围或是精度。
仍以十进制为例， 需要注意
于是，鉴于上面的现象， 通常设计定点字长的时候， 采用以下依据
在下文中， 定点数格式的表示方法被记为SI(N)F(M)，S表示为有符号数， N比特整数位， M比特小数位。 例如：SI9F7表示：有符号数，9比特整数位，7比特小数位。
理论模型中的各种数据均为浮点类型， 有时需要把理论模型中的数据变量转化为定点小数类型， 例如，一个数字滤波器中的滤波系数常数，最简单的浮点转为定点的方法是乘以缩放因子，即：
当需要把定点计算的结果代入回理论计算模型时， 需要将其转换回浮点格式， 则有
两个定点数相加，设其定点格式分别为 SI(N1)F(M1) 和 SI(N2)F(M2)， 设 N1 > N2, M1 > M2。
注：所谓算术右移是指对高位数据进行符号扩展的右移操作， 而逻辑右移操作仅对高位补零。 不同的编程语言中算术右移的实现方式不同， 请参考相关资料。
两个定点数相加，设其定点格式分别为 SI(N1)F(M1) 和 SI(N2)F(M2)，设 N1 > N2, M1 > M2。
注意负临界值 ，在二补码系统中， 最高位为1， 其余为为0 是一种特殊的情况， 表示负边界值。 以4比特系统举例，
上述情况对于字长有限的信号处理系统中需要额外注意， 因为在信号处理系统中负极值出现的概率很小， 一个小概率的数值结果，占用1比特字长会降低6分贝的信噪比，这很不经济。 但是另一方面，如果出现溢出则对系统是灾难性的后果。 因此，如果为了提高量化精度，同时又避免溢出， 会采用技术手段把负极值替换为负次极值。 例如，在一个SI1F3格式的定点系统中， 使用代码逻辑， 如果探测到 -1 就用-0.875进行替换。 如果定点数值中的负极值被剔除， 则乘法的结果就总是有2比特符号位， 于是仅保留1比特的符号位即可， 从而能够提高1比特的有效数据位，增加系统的精度。
下图是一个定点系统中被乘法缩放过的16比特定点正弦波信号， 从图中可见， 该信号的高3位数据总是相同， 如果需要从该信号中截取8比特数据给后级处理， 则通常会抛弃比特15和14 这两位多余的符号位， 取出从比特13开始8位数据作为有效数据。
 缩放后的 16 bit 量化正弦波形 |
本节内容中， 我们用一个数字滤波器作为例子， 来讲述数字信号处理系统中定点小数的格式设计问题。 下图是一个简化了的使用数字滤波器对模拟信号进行滤波的例子。 该范例系统的工作描述如下：
 模拟信号的数字滤波 |
上面的系统中， 虽然数字滤波子系统的输入和输出数据格式都是8比特无符号整数格式， 但是这是为了和模拟数据转换器适配的结果。 在数字系统内部， 由于需要进行数值计算， 无符号整数的格式是无法和信号处理的理论公式匹配。 因此， 在信号处理系统的内部， 数据使用有符号数表示的。 图中在信号流图中的数字信号上用字母 A、B、C、D、E、F 标识出了不同种类的定点小数格式。
需要额外说明的是， 图中的数字信号处理子系统， 当使用处理器或是数字电路来实现时， 其字长方案是有所区别的。 因为对于处理器而言， 其字长必须以字节（byte）为单位， 所有的数据字长的比特数均是8的倍数。 而对于诸如FPGA这类数字器件而言， 由于其数据字长以比特位单位， 则其可以更加自由的设定数据格式。
在使用C语言编程实现定点数计算时， 有以下事项需要注意：
明确处理器对应的变量字长， 通常32位处理器上变量类型的字长配置如下
两个定点数相加时，需要将小数部分字长调整一致，例如
两个定点数相乘时，需要确保结果的字长不会溢出， 例如
浮点数转换为定点数，需要把浮点数乘以缩放因子然后取整， 例如
定点数转换为浮点数，需要把定点数除以缩放因子， 例如
本文提供的C语言格式的参考代码， 该演示了以下过程
 定点计算C代码 运行结果 |
Verilog HDL 设计语言和C不同， 它默认的信号变量类型是无符号变量， 对于 端口（input output），线网（wire）和 reg信号变量而言， 如果不声明为 signed 类型， 则电路编译器默认其是 无符号类型的信号变量。 由于 硬件电路的设计阶段需要使用多个工具， 比如仿真阶段使用ModelSim， 电路综合阶段使用 Quartus。 为了保证电路代码在不同EDA工具之间的行为一致性， 为保险起见，进行 加法或乘法运算的 两个信号以及运算的结果信号 ，最好同时声明为 signed 类型信号。
在Verilog代码中，进行字长处理，比如符号扩展和截取数据位时， 位拼接符和位寻址符， 使用的非常频繁， 例如：
由于 Verilog HDL设计语言可以精确设定比特级别的信号字长， 为了保持不同的EDA工具的行为一致性，有以下建议：
FPGA上的整数加法器的实现方法如下：
Verilog语言 如何实现定点乘法
定点乘法的信号流
乘法器在数字电路中是一个较为复杂的部件， 其内部由加法器阵列构成。在使用整数乘法器时一定要预先估计好资源预算。 如果FPGA芯片内嵌有硬件乘法器， 编译器会调用硬件乘法器来实现乘法电路， 否则使用逻辑单元 Logic Element来实现。
Verilog 语法支持 real 格式类型数据， 这是一种浮点类型， 该数据通常仅用来仿真验证。 在电路仿真中， 将定点数转换为浮点数来验证结果的正确性。 由于HDL仿真 是一种波形样点级别的仿真， 并不擅长验证带有复杂数学含义的批量数据， 所以复杂数据通常会在仿真的testbench中将数据导出，使用其他工具（比如Matlab）进行数学意义上的验证。
 定点Verilog 代码仿真波形 |
Matlab是一种高抽象层次的仿真工具， 主要用来验证算法和信号流图层面系统设计的正确性。 在设计和验证定点处理系统时， Matlab 工具的角色是 ：
获取本文提供的实验参考代码和作业， 请访问 Github 地址