如何在DSP上实现二进制数折半查找算法

　　折半查找是采用跳跃跃方式先将顺序数列中的“中间值”与所查询值进行比较，然后按照比值大于或小于“中间值”来判断所查找数的甩在区域。文章给出了将折半算法应用于数字信号处理器上以实现二进制数的查找算法的一种具体方法。并给出了采用这种方法的软件程序。

　　1 折半查找的基本原理

　　近十几年来，随着各类集成化单片数字信号处理器（DSP，Digital Signal Processor）性能的不断改时，相庆的软件和开发工具日臻完善，价格也迅速下降。它们所具有的功能强、集成度高、应用灵活及性能价格比高的优点使其信息处理（如语音与图像各种的处理）、通信、多媒体、综合网络、控制、消费电子、医疗设备、测试与仪器等诸多领域得到了极为广泛的。有一种看法认为：单片机是事物处理型的处理器，如开关的通断或逻辑操作等；数字信号处理器是数据处理型的处理器，如进行大量的包括FFT在内的数据运行等。这种看法在某种程序上是有一定道理的。一般地说，DSP应用系统要处理的数据多、运算量大而且实时性要求较高，研究DSP本身（包括硬件方面和软件方面）的优势对快速有效地执行某种算法有着重要的实用价值。

　　查找是智能系统经常用到的操作，实现查找的方法有多种，如顺序查找、折半查找和分块查找等。在这些方法中，如果按顺序存储结构组织的查找表中的所有数据元素按关键字有序，则可以执行折半查找（或称二分查找）。它的基本思想是：由于查找表中的数据按关键字有序（假设递增有序），则在查找时不必逐个顺序比较，而可以采用跳跃式方式先与“中间位置”的记录关键字比较，若相同，则查找成功，若给定值大于“中间位置”的关键字，则在后半部分进行折半查找，否则在前半部进行折半查找。

　　2 折音查找算法在DSP上的实现

　　二进制折半查找算法（Binary Search Algorithm）在DSP上实现并不难，但是一般查找程序都未能充发利用DSP内部先进的结构和指令集，从而使得程序运行的时间未能缩至最短。这在某些时候不会防碍系统效率，但在系统数据量较大而且实时性要求较高的情况下，则必须尽一切可能提高程序的效率。本文以TMS320C50为例给出了一个二进制查找算法的子程序，该程序可使系统的查找效率得到较大提高。

　　程序中充分利用了TMS320C50的位反址寻址指令，该指令可以在每一个测试过程中使搜寻的工作减半并释放累加器以进行其它工作。此外，该程序利用了条件执行指令（XC），而不是使用传统的条件转换指令，这样一来便节省了指令周期并提高了效率。具体的TMS320C50的指令集可以参考其它文献[1]。

　　本文介绍的二进搜寻程序是在有序状态下进行的。它假设表格中的数据按由低到高的次序排列，最大数在存储器中的地址最大。当然，反之（最小数在地址的最高位）亦是如此。此外，程序还假设数据中的最大个数是2的幂次方，在下面给出的源程序中个数2 11个。

　　TMS320C50的源程序：

　　.bss NTABLE，800h ；2的11次幂的数据空间（按由低到高排列）

　　.bss LOOK，1 ；要查找的数

　　.mmregs

　　.text

　　.

　　.

　　.

　　call bsearch

　　.

　　.

　　.

　　；***********************

　　；二进制查找子程序

　　；程序名：binsearch

　　；入口参数： （ACC）所要查找的二进制数

　　；出口参数：（ACC）所要查找的二进制数的地址（数据被找到）

　　（ACC）=0(数据未找到)

　　；***********************

　　bin-search lar AR0，#0800h ；AR0数据的总数目

　　mar *，AR0

　　mar *BR0+ ，AR3 ；总数目的一半

　　lar AR3， #NTABLE；AR3指向数更的开始

　　lacl #11 ；重复2的N次方，数列数据的个数为2的N次方

　　samm BRCR ；重复次数存放在BRCR中

　　ldp #LOOK

　　lace LOOK ；要查找数据存放在ACC中

　　sub * ；与AR3所指的存储单元的数据相减

　　bcnd nothere ， LT ；ACC值小于0，要查找的数据不在本数列中

　　rptd nothere-1

　　bend found，EQ ；打到数据

　　xc 1， GT ；若ACC中的数据较大

　　mar *0+， AR0 ；

　　xc 1， LT ；若ACC中的数据较小

　　mar *0-， AR0 ；

　　mar *BR0+， AR3 ；查找空间减半

　　lacc LOOK

　　sub *

　　；***********************

　　；未找到，将ACC置0后返回

　　；***********************

　　nothere retd

　　zac

　　nop

　　；***********************

　　；找到数据，将数据地址存放在ACC中返回

　　；***********************

　　found ldp #0

　　apl #0fffeh，PMST ；复位PMST位

　　retd

　　lamm AR3 ；存数据地址

　　nop　　3 辅助说明

　　程序中较为详细的介绍了每个步骤所需完成的功能，下面就一些关键的地方进行一些说明。

　　（1）程序如果找到查找的数据则返回数据所在的地址，未找到则送0至ACC寄存器。

（2）程序中的mar BR0+，AR3是将当前AR（辅助寄存器）指定的数据存储器的内容按逆向进位方式加