唐 建 白雪飞

(中国科学技术大学 微电子学院， 合肥 230027)

计算思维自2006年提出以来，在计算机教育中得到了较深入的研究[1-9]，并逐步在中小学教育中得到了广泛重视[10-12]。计算思维是运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为，它包括了涵盖计算机科学之广度的一系列思维活动；而计算机科学在本质上源自数学思维，因为像所有的科学一样，其形式化基础建筑于数学之上；计算机科学又从本质上源自工程思维，因为我们建造的是能够与实际世界互动的系统，基本计算设备的限制迫使计算机学家必须计算性地思考，不能只是数学性地思考[1-2]。人类对计算本质的认识经历了三个阶段：计算手段器械化、计算描述形式化、计算过程自动化；P. J. Denning 将计算原理描述为运行原理和设计原理，其中运行原理归纳为八大要素：计算、抽象、自动化、设计、通信、协同、存储、评估[7]。

抽象和自动化被认为是计算思维的本质[4]。抽象包含的核心概念有：概念模型与形式模型、抽象层次；约简、嵌入、转化、分解、数据结构(如队列、栈、表和图等)、虚拟机等。自动化包含的核心概念有：算法到物理计算系统的映射，人的认识到人工智能算法的映射；形式化(定义、定理和证明)、程序、算法、迭代、递归、搜索、推理；强人工智能、弱人工智能等[6]。

数字信号处理(Digital Signal Processing)是利用计算机或专用处理设备，以数值计算的方法对信号进行采集、变换、综合、估值与识别等加工处理，借以达到提取信息和便于应用的目的，几乎所有的工程技术领域都要涉及信号处理和特征提取问题。数字信号处理总体上涉及理论、算法与实现三个方面。实时实现是一个重要考虑因素，因而在数字信号处理的发展史上快速算法和数字信号处理器(Digital Signal Processor，DSP芯片)起到了至关重要的作用。DSP芯片是专门为数字信号处理算法而设计的一种微处理器芯片[13]，分为定点DSP芯片和浮点DSP芯片两种，分别有利于定点数和浮点数的计算。定点DSP芯片运算快，价格便宜，在通信、媒体信息处理等领域中应用广泛。当然，定点DSP芯片也支持浮点运算。

DSP芯片是在计算机设计基础上发展而来的，充分体现了计算机技术对数字信号处理算法的大力支持。而算法设计也是紧密结合计算机的应用而发展和改进的。因此，实际上数字信号处理的发展史充分体现了计算思维的运用。

但是，结合数字信号处理教学训练学生计算思维的教学研究论文非常少见。无论多么复杂的计算或算法，都可以分解成基本的加减乘除运算。结合计算思维，分析了数字信号处理算法精度这一重要问题，为在数字信号处理教学中结合计算思维教学提供一个参考案例。侧重分析在定点DSP芯片中实现定点除法运算以及精度问题，涉及的计算比较小，但体现了计算思维若干特征。

1 有限字长与算法精度问题：问题引出

文献[6]给出了三层次的计算思维表述体系框架，“计算”是位于中心的第一层次(最里层)概念，“抽象、自动化和设计”是从不同方面对“计算”进行描述的往外延伸的第二层次概念，“通信、协作、记忆、评估”蕴含在“抽象、自动化和设计”之中，是仅次于“抽象、自动化和设计”的基础概念，是第三层次(最外层)概念。其中，“评估”包括对数据进行实验分析、统计分析、预测与评价等方面。根据实际问题，评估可能需要采取复杂的过程，也可能是相对比较简单的过程。

数字信号处理算法中由于有限字长而存在精度问题，因此不可避免地存在误差，主要包括数据和系数的量化误差、计算上的舍入误差。这些误差的存在，将对算法性能和系统实现产生影响，因此实际中需要对结果做评估以决定方案是否可行。

在定点DSP芯片中快速实现高精度的除法运算非常重要[14]。一般的定点DSP没有除法器硬件支持，即使浮点DSP也未必都提供了除法硬件支持[15]。定点DSP需要一系列的移位和条件减法运算来实现除法运算。定点DSP除法操作时应考虑两个基本情形：商的绝对值是大于等于1还是小于1，并将据此选择具体的除法算法，前者的结果可以表示为整数商和余数，后者的结果是纯小数。事实上，还必须考虑被除数、除数、结果既非纯小数，又非纯整数的情况，且这种情况下能够得到较高小数位精度的结果非常重要。

由此可见，应根据实际需求采用具体的除法运算算法，需要事先做一定的算法评估。“评估”是计算思维表述体系框架的最外层里的一个概念。

2 定点DSP芯片数据表示：数据抽象

数据是计算加工的对象。更深层次地，文献[6]给出了对“计算”的理解：计算是执行一个算法的过程，甚至还可以进一步地认为都是符号串的转换，效率是计算问题的核心，计算包含的核心概念有：大问题的复杂性、效率、演化、按空间排序、按时间排序，以及计算的表示、表示的转换、状态和状态转换、可计算性、计算复杂性理论等。

数据通常是实际事物的抽象表示，且有时数据是需要转换的，因此数据转换也归入“抽象”的过程，这些可以统称数据抽象。抽象是计算的“精神”工具[6]。本节分析将数据抽象成Q整数——一种特殊的数据类型。在进行计算之前，将数据抽象成Q整数，再送入“计算”环节。

定点计算机中采用定点数表示纯整数和纯小数[16]，纯整数的小数点位置固定在数值位最低位的右边，纯小数的小数点位置固定在符号位与最高数值位之间，小数点不占据二进制位，是隐含的，无需硬件表示。浮点数由尾数和阶码构成。尾数为二进制纯小数，阶码为二进制定点整数。尾数的位数决定了所能表示的数值精度，阶码的位数决定了所能表示的数值范围。

在16-bit定点DSP芯片中，对于一般性实数(包括纯小数)，用C语言来编程时可以用float数据类型来表示，一般占据32 bit。为了用16-bit定点DSP来实现快速处理，可以将32-bit的float数据用一个16-bit整数形式数据类型来表示(但要保留指示其小数点的额外信息以便能够进一步处理)，实际上它还是一个实数。一种常用做法就是采用16-bit定点数的Q表示法。当然，一个问题是将浮点数转换成定点数以近似模拟实现浮点操作会导致精度上的损失。

将一般性实数(浮点数)x转换成Q定点数以得到整数形式数据xQ，转换关系如式(1)所示。式中16位取整操作表明xQ是一个整数，但这个整数是不同于普通意义上的整数，是有下标Q修饰的整数，下标Q暗示了小数点的位置，Q=0～15。

xQ=(int)x×2Q，x=(float)xQ×2-Q

(1)

为方便描述，本文定义按式(1)得到的整数为定点数“Q整数”。例如，实数0.3转换成Q15定点数对应的Q整数为int(0.3×215)=int(0.3×32768)=9830，该Q整数的二进制序列的低15位均是小数位。所以，定点数可以表示一般性实数，包括纯整数和纯小数，但在使用形式上是一个整数——Q整数。又如，如果一批实数可用Q13定点数表示，即这批数据有2-bit整数位，13-bit小数位，则这批数据可以通过先乘以213再取整来转换成Q13定点数对应的Q整数，如int(3.5×213)= 28672。按照这样的转换，得到的Q整数的范围是[-32768，32767]，就是16-bit寄存器能表示的有符号整数的范围。

3 定点DSP除法算法：计算、自动化

在将数据转换成Q整数后，就进入除法的“计算”环节。在此考虑“计算”的核心概念有：可计算性、效率、计算的表示、表示的转换等。效率是计算问题的核心之一。本例满足可计算性，计算规模较小。在周以真的论文中，认为计算是抽象的自动化[6]。这里的抽象不是数据的抽象，而是方法和算法的抽象。什么能被(有效地)自动化是计算学科的根本问题，自动化意味着需要某种计算机来解释抽象[6]。可见，自动化为设计程序和实现除法运算提供了先决条件。

本节结合计算机硬件资源计算条件讨论除法运算算法——除法运算抽象化，同时也是计算的依据。由于具有计算机的支持，所以本节的讨论同时也涉及了计算思维表述体系框架第二层概念中的“自动化”的概念。设计是利用学科中的抽象、模块化、聚合和分解等方法对一个系统、程序或者对象等进行组织，好的设计有正确性、速度、容错性、适应性等4个标准[6]。本节讨论为软件设计提供了充分准备，因此也涉及了计算思维表述体系框架第二层概念中的“设计”的概念。

我们知道，从数字信号处理的应用角度看，算法是一个核心概念，算法需要结合软件和硬件来实现。根据上述讨论，可见，数字信号处理算法联系了计算、抽象、自动化和设计，这些都是计算思维表述体系框架中的重要的基础概念。

3.1 移位竖式减法操作实现除法运算

考虑到溢出问题，累加器的位宽一般要高于2倍的操作数基本字长，如操作8-bit操作数的寄存器可以是8-bit的，但累加器要大于16-bit。在计算机中是用移位相减来实现除法的。执行除法操作的第一次减法是在累加器中被除数的最高有效位(bit 7)与除数的最低有效位(bit 0)对齐情况下进行的，如图1所示。设操作数均为整数或Q整数。有两种做法：①被除数位置固定而除数不断右移，②除数位置固定而被除数不断左移。如果采用做法①，除数最多可以右移7位，从而可以得到商的整数部分；如果还需要计算出商的一些小数部分，那么理论上应继续右移除数并执行减法，但再右移就有问题了，因为这将把除数移出寄存器而导致数据错误。做法②是可行的，由于累加器的位宽较宽，因此被除数在左移了7位(完成了8次减法)而求出了商的整数部分后，它还可以继续左移而仍在累加器中，从而可以求解出结果的小数部分。

图1 计算机除法操作数据初始对齐状态

3.2 0<被除数<除数时的情形分析

如果被除数绝对值小于除数绝对值，这时商是纯小数。这种情况下该如何做最合理呢？若仍按图1那样安排，被除数在左移7次后与除数相减仍小于零，这意味着已发生的8次相减操作都是负数，上商都是0，本文定义这些0为商的前缀0。

这些商的前缀0本质上属于商的整数部分，但是这些计算步骤是不必要做的，浪费了时间。之后的被除数左移却有可能使得相减结果为正，从此往后得到的上商(0或1)是所求的商——纯小数结果的数据位。为此，这种情况下，第一次相减操作时被除数的bit 0和除数的bit 1是对齐的。以3÷8为例，8次移位相减得到商01100000B，它是一个纯小数结果：0.01100000B，对应十进制数为0.375。可以想到，按此做法可通过继续左移被除数从而可以得到精度更高的纯小数结果。

根据上述分析和讨论，也充分体现了计算思维中的“效率”“评估”概念及其重要性。

4 定点DSP除法程序设计：算法抽象

程序设计属于软件开发范畴，软件开发除了具备计算思维中的自动化和设计概念，还涉及计算思维表述体系框架第三层概念中的通信、协作、记忆和评估。本文涉及的程序设计规模小，但也涉及上述基本概念。

陈国良等认为，计算思维并不是仅仅为计算机编程，而是在多个层次上抽象的思维，是一种以有序编码、机械执行和有效可行方式解决问题的模式[8]。程序设计是用计算机语言表达算法(算法抽象)，可以是高级语言或低级语言。

4.1 TMS320C54x定点除法程序

TMS320C54x使用40-bit的算术逻辑单元(ALU)和2个40-bit的累加器(A和B)一起来完成二进制补码的算术运算。累加器由3部分构成：低阶位(15～0)、高阶位(31～16)、保护位(39～32)。保护位是作为计算时的数据位余量，以防止溢出。除法操作可以使用条件减法指令SUBC。SUBC指令语法为：SUBC Smem src，执行情况是：

If (src-Smem≪15)≥0

src=(src-Smem≪15)≪1+1

else

src=src≪1

src(源累加器A或B)中存放被减数(被除数)，Smem(16-bit单数据存储器操作数)中存放减数(除数)。根据减法结果，如果结果非负(够减)，则将该结果左移1位再加1后赋给源累加器(A或B)——加到LSB里的这个“1”就是要上商的“1”；如果结果为负(不够减)，则源累加器(A或B)中的数左移1位(作为下次的被减数)——加到LSB里的是“0”且作为上商“0”。

可以使用16次SUBC指令完成结果绝对值大于等于1的除法，得到整数商和余数。对于结果为纯小数的除法，需要重复15次SUBC指令以得到15个小数位，且不同于结果绝对值大于等于1的除法，这时被除数要加载到src的AH中而不是AL中。实现上是先执行两个数的绝对值的除法，最后再考虑商的符号位。

在汇编语言程序中不能直接写入十进制小数，需要利用式(1)将其转化成Q整数。对于除法操作0.3÷(-0.8)，将操作数转换成Q15定点数对应的Q整数的程序是：

.data

table: .word 3*32768/10

.word -8*32768/10

执行15次以SUBC指令为核心的代码(代码略)，最后的结果为0B000H，是一个负数，对应的二进制序列为1011000000000000B，对应的Q15格式定点数的Q整数是-12288，由式(1)得到对应的实数为：-12288/215=-0.375。

4.2 高精度商的快速计算

如果被除数远小于除数，纯小数结果的绝对值就很小，这意味着即使初始时将被除数的bit 0对准了除数的bit 1，但是在前面多次的相减结果仍然都是负数，上商的bit都是0，即都是商的前缀0，这不利于有限操作次数来快速得到高精度结果。

一种可能的做法是：当被除数绝对值大于除数绝对值时，可以左移除数使被除数绝对值不大于除数绝对值2倍以上。反之，当除数绝对值大于被除数绝对值时，可以左移被除数使除数绝对值不大于被除数绝对值2倍以上。然后可以用有限移位相减操作得到更多有效商位，从而提高精度。

例如，对于40÷3，商的绝对值大于1，且结果是一个无限循环数，只有得到的非零商位越多，才可能得到一个精度更高的商。按一般的除法程序得到整数商和余数，假设寄存器是8-bit的，累加器是16-bit的，8次相减操作得到的上商位的二进制序列是00001101B，即整数商是13(1101B)，另外余数是1。

如果执行除法前先将除数左移3-bit将其放大得到24，再结合特定的程序指令执行40÷24，执行8次移位相减得到二进制序列是11010101B；按约定，被除数不大于除数2倍以上，即有1位整数位，因此结果11010101B实际就是1.1010101B；为还原结果，需再将结果右移3位，即1101.0101B，它所对应的十进制数就是13.31。可见，通过8次移位相减得到了两位小数位宽除法结果。

上述做法实质上在进行除法操作前就限定了结果的取值区间(暗含了小数点的位置)，并根据事先分析得到的信息确定了被除数和除数进行移位相减时初始对齐位置，从而可以直接从有效商位开始计算。

上述分析深刻体现了计算思维的特征，它包括计算、抽象、自动化、设计、通信、协同、存储、评估，其中计算、自动化、通信、协同、存储是由硬件来支持的，抽象、设计、评估则需要人工程序设计来保障。抽象和自动化是计算思维的本质。

5 结语

分析了定点DSP芯片实现定点除法运算及其精度问题和除法运算程序设计，包括硬件计算资源、算法、数据转换、程序设计各个环节。整个过程隐含了计算思维的整体层次概念以及每个层次中的若干基础概念。

教育部高等学校大学计算机课程教学指导委员会主任委员李廉教授认为，在传统的教学中计算思维是隐藏在能力培养内容中的，要靠学生“悟”出来，现在要把这些明白地讲出来，让学生自觉地去学习，提高培养质量，缩短培养的时间[6]。