1 折半查找的基本原理
　　近十幾年來，隨著各類集成化單片數(shù)字信號處理器（DSP，Digital Signal Processor）性能的不斷改時(shí)，相慶的軟件和開發(fā)工具日臻完善，價(jià)格也迅速下降。它們所具有的功能強(qiáng)、集成度高、應(yīng)用靈活及性能價(jià)格比高的優(yōu)點(diǎn)使其信息處理（如語音與圖像各種的處理）、通信、多媒體、綜合網(wǎng)絡(luò)、控制、消費(fèi)電子、醫(yī)療設(shè)備、測試與儀器等諸多領(lǐng)域得到了極為廣泛的。有一種看法認(rèn)為：單片機(jī)是事物處理型的處理器，如開關(guān)的通斷或邏輯操作等;數(shù)字信號處理器是數(shù)據(jù)處理型的處理器，如進(jìn)行大量的包括FFT在內(nèi)的數(shù)據(jù)運(yùn)行等。這種看法在某種程序上是有一定道理的。一般地說，DSP應(yīng)用系統(tǒng)要處理的數(shù)據(jù)多、運(yùn)算量大而且實(shí)時(shí)性要求較高，研究DSP本身（包括硬件方面和軟件方面）的優(yōu)勢對快速有效地執(zhí)行某種算法有著重要的實(shí)用價(jià)值。
　　查找是智能系統(tǒng)經(jīng)常用到的操作，實(shí)現(xiàn)查找的方法有多種，如順序查找、折半查找和分塊查找等。在這些方法中，如果按順序存儲結(jié)構(gòu)組織的查找表中的所有數(shù)據(jù)元素按關(guān)鍵字有序，則可以執(zhí)行折半查找（或稱二分查找）。它的基本思想是：由于查找表中的數(shù)據(jù)按關(guān)鍵字有序（假設(shè)遞增有序），則在查找時(shí)不必逐個(gè)順序比較，而可以采用跳躍式方式先與“中間位置”的記錄關(guān)鍵字比較，若相同，則查找成功，若給定值大于“中間位置”的關(guān)鍵字，則在后半部分進(jìn)行折半查找，否則在前半部進(jìn)行折半查找。
　　2 折音查找算法在DSP上的實(shí)現(xiàn)
　　二進(jìn)制折半查找算法（Binary Search Algorithm）在DSP上實(shí)現(xiàn)并不難，但是一般查找程序都未能充發(fā)利用DSP內(nèi)部先進(jìn)的結(jié)構(gòu)和指令集，從而使得程序運(yùn)行的時(shí)間未能縮至最短。這在某些時(shí)候不會防礙系統(tǒng)效率，但在系統(tǒng)數(shù)據(jù)量較大而且實(shí)時(shí)性要求較高的情況下，則必須盡一切可能提高程序的效率。本文以TMS320C50為例給出了一個(gè)二進(jìn)制查找算法的子程序，該程序可使系統(tǒng)的查找效率得到較大提高。
　　程序中充分利用了TMS320C50的位反址尋址指令，該指令可以在每一個(gè)測試過程中使搜尋的工作減半并釋放累加器以進(jìn)行其它工作。此外，該程序利用了條件執(zhí)行指令（XC），而不是使用傳統(tǒng)的條件轉(zhuǎn)換指令，這樣一來便節(jié)省了指令周期并提高了效率。具體的TMS320C50的指令集可以參考其它文獻(xiàn)［1］。
　　本文介紹的二進(jìn)搜尋程序是在有序狀態(tài)下進(jìn)行的。它假設(shè)表格中的數(shù)據(jù)按由低到高的次序排列，最大數(shù)在存儲器中的地址最大。當(dāng)然，反之（最小數(shù)在地址的最高位）亦是如此。此外，程序還假設(shè)數(shù)據(jù)中的最大個(gè)數(shù)是2的冪次方，在下面給出的源程序中個(gè)數(shù)2 11個(gè)。
　　TMS320C50的源程序：
　　.bss NTABLE，800h ;2的11次冪的數(shù)據(jù)空間（按由低到高排列）
　　.bss LOOK，1 ;要查找的數(shù)
　　.mmregs
　　.text
　　。
　　。
　　。
　　call bsearch
　　。
　　。
　　。
　　;***********************
　　;二進(jìn)制查找子程序
　　;程序名：binsearch
　　;入口參數(shù)： （ACC）所要查找的二進(jìn)制數(shù)
　　;出口參數(shù)：（ACC）所要查找的二進(jìn)制數(shù)的地址（數(shù)據(jù)被找到）
　　（ACC）=0（數(shù)據(jù)未找到）
　　;***********************
　　bin-search lar AR0，#0800h ;AR0數(shù)據(jù)的總數(shù)目
　　mar *，AR0
　　mar *BR0+ ，AR3 ;總數(shù)目的一半
　　lar AR3， #NTABLE;AR3指向數(shù)更的開始
　　lacl #11 ;重復(fù)2的N次方，數(shù)列數(shù)據(jù)的個(gè)數(shù)為2的N次方
　　samm BRCR ;重復(fù)次數(shù)存放在BRCR中
　　ldp #LOOK
　　lace LOOK ;要查找數(shù)據(jù)存放在ACC中
　　sub * ;與AR3所指的存儲單元的數(shù)據(jù)相減
　　bcnd nothere ， LT ;ACC值小于0，要查找的數(shù)據(jù)不在本數(shù)列中
　　rptd nothere-1
　　bend found，EQ ;打到數(shù)據(jù)
　　xc 1， GT ;若ACC中的數(shù)據(jù)較大
　　mar *0+， AR0 ;
　　xc 1， LT ;若ACC中的數(shù)據(jù)較小
　　mar *0-， AR0 ;
　　mar *BR0+， AR3 ;查找空間減半
　　lacc LOOK
　　sub *
　　;***********************
　　;未找到，將ACC置0后返回
　　;***********************
　　nothere retd
　　zac
　　nop
　　;***********************
　　;找到數(shù)據(jù)，將數(shù)據(jù)地址存放在ACC中返回
　　;***********************
　　found ldp #0
　　apl #0fffeh，PMST ;復(fù)位PMST位
　　retd
　　lamm AR3 ;存數(shù)據(jù)地址
　　nop
　　3 輔助說明
　　程序中較為詳細(xì)的介紹了每個(gè)步驟所需完成的功能，下面就一些關(guān)鍵的地方進(jìn)行一些說明。
　　（1）程序如果找到查找的數(shù)據(jù)則返回?cái)?shù)據(jù)所在的地址，未找到則送0至ACC寄存器。
　　（2）程序中的mar BR0+，AR3是將當(dāng)前AR（輔助寄存器）指定的數(shù)據(jù)存儲器的內(nèi)容按逆向進(jìn)位方式加AR0的內(nèi)容。由于在該指令前有一條mar*，AR0指令，這條指令指定了下一條指令的輔助寄存器。因此在執(zhí)行MAR BR0+，AR3時(shí)，實(shí)際上是輔助寄存器AR0與自身逆向相位相加：其結(jié)果是數(shù)據(jù)為原來的一半。實(shí)際上這條指令確定了折半查找算法中的“中間位置”。
　　（3）samm BRCR指令程序執(zhí)行是是與rptp nothere-1指令配合使用的。Samm指令的功能是將循環(huán)次數(shù)的值（這里是11）存放在BRCR中。BRCR（Block Repeat Counter Register）是個(gè)16位的寄存器，用于存放程序塊重復(fù)操作的次數(shù)。Rptp指令是重復(fù)操作指令，它的功能是重復(fù)執(zhí)行下一條指令到該指令指定的地址之內(nèi)的程序代碼，重復(fù)執(zhí)行的次數(shù)由brcr決定。在上面的程序中，RPTR指令指定的地址是nothere-1，也就是說：重復(fù)執(zhí)行的程序代碼從bcnd found直到nthere的前一指令Sub*。
　　xc指令的用法如下：
　　xc K［，COND1］［COND2］［，…］
　　指令中的K=1或2。COND1、COND2是條件。xc指令功能是在條件滿足的情況下，執(zhí)行該指令下面的K條指令，K為1，則執(zhí)行一條指令，K為2則執(zhí)行兩條指令。條件不滿足就執(zhí)行K條NOP指令。
　　（4）該源程序是采用TMS320C5X的指令集編寫的，如果是TMS320C5X系列的DSP，則可以直接將上面給出的程序作為一個(gè)子程序來使用。而對于TMS320C2XX系列的DSP來說，由于TMS320C5X的指令對TMS320C2XX的指令是向下兼容的，所以在編寫TMS320C2XX的折半查找程序時(shí)應(yīng)作一些修改，比如前面提到的程序中的samm指令，在TMS320C2XX指令集中就沒有。這樣，如果希望用TMS320C2XX來實(shí)現(xiàn)本例中的samm語句 功能，則可以將重復(fù)操作的次數(shù)存放在內(nèi)部的RAM中，再配合TMS320C2XX循環(huán)指令來完成samm與rptp指令的功能。但這樣做將導(dǎo)致程序執(zhí)行效率的降低。也可以認(rèn)為TMS320C2XX的數(shù)據(jù)處理能力較TMS320C5X為弱，其原因主要是兩者指令集的差異。
?