如何在DSP上實(shí)現(xiàn)二進(jìn)制數(shù)折半查找算法

　　折半查找是采用跳躍躍方式先將順序數(shù)列中的“中間值”與所查詢值進(jìn)行比較，然后按照比值大于或小于“中間值”來(lái)判斷所查找數(shù)的甩在區(qū)域。文章給出了將折半算法應(yīng)用于數(shù)字信號(hào)處理器上以實(shí)現(xiàn)二進(jìn)制數(shù)的查找算法的一種具體方法。并給出了采用這種方法的軟件程序。

　　1 折半查找的基本原理

　　近十幾年來(lái)，隨著各類集成化單片數(shù)字信號(hào)處理器（DSP，Digital Signal Processor）性能的不斷改時(shí)，相慶的軟件和開(kāi)發(fā)工具日臻完善，價(jià)格也迅速下降。它們所具有的功能強(qiáng)、集成度高、應(yīng)用靈活及性能價(jià)格比高的優(yōu)點(diǎn)使其信息處理（如語(yǔ)音與圖像各種的處理）、通信、多媒體、綜合網(wǎng)絡(luò)、控制、消費(fèi)電子、醫(yī)療設(shè)備、測(cè)試與儀器等諸多領(lǐng)域得到了極為廣泛的。有一種看法認(rèn)為：?jiǎn)纹瑱C(jī)是事物處理型的處理器，如開(kāi)關(guān)的通斷或邏輯操作等；數(shù)字信號(hào)處理器是數(shù)據(jù)處理型的處理器，如進(jìn)行大量的包括FFT在內(nèi)的數(shù)據(jù)運(yùn)行等。這種看法在某種程序上是有一定道理的。一般地說(shuō)，DSP應(yīng)用系統(tǒng)要處理的數(shù)據(jù)多、運(yùn)算量大而且實(shí)時(shí)性要求較高，研究DSP本身（包括硬件方面和軟件方面）的優(yōu)勢(shì)對(duì)快速有效地執(zhí)行某種算法有著重要的實(shí)用價(jià)值。

　　查找是智能系統(tǒng)經(jīng)常用到的操作，實(shí)現(xiàn)查找的方法有多種，如順序查找、折半查找和分塊查找等。在這些方法中，如果按順序存儲(chǔ)結(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í)候不會(huì)防礙系統(tǒng)效率，但在系統(tǒng)數(shù)據(jù)量較大而且實(shí)時(shí)性要求較高的情況下，則必須盡一切可能提高程序的效率。本文以TMS320C50為例給出了一個(gè)二進(jìn)制查找算法的子程序，該程序可使系統(tǒng)的查找效率得到較大提高。

　　程序中充分利用了TMS320C50的位反址尋址指令，該指令可以在每一個(gè)測(cè)試過(guò)程中使搜尋的工作減半并釋放累加器以進(jìn)行其它工作。此外，該程序利用了條件執(zhí)行指令（XC），而不是使用傳統(tǒng)的條件轉(zhuǎn)換指令，這樣一來(lái)便節(jié)省了指令周期并提高了效率。具體的TMS320C50的指令集可以參考其它文獻(xiàn)[1]。

　　本文介紹的二進(jìn)搜尋程序是在有序狀態(tài)下進(jìn)行的。它假設(shè)表格中的數(shù)據(jù)按由低到高的次序排列，最大數(shù)在存儲(chǔ)器中的地址最大。當(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ù)被找到）

　?。ˋCC）=0(數(shù)據(jù)未找到)

　??；***********************