二進制數折半查找算法在DSP上的實現

折半查找是采用跳躍躍方式先將順序數列中的“中間值”與所查詢值進行比較,然后按照比值大于或小于“中間值”來判斷所查找數的甩在區域。文章給出了將折半算法應用于數字信號處理器上以實現二進制數的查找算法的一種具體方法。并給出了采用這種方法的軟件程序。

??? 關鍵詞：折半查找 二進制 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（輔助寄存器）指定的數據存儲器的內容按逆向進位方式加AR0的內容。由于在該指令前有一條mar*,AR0指令,這條指令指定了下一條指令的輔助寄存器。因此在執行MAR BR0+,AR3時,實際上是輔助寄存器AR0與自身逆向相位相加：

??? 其結果是數據為原來的一半。實際上這條指令確定了折半查找算法中的“中間位置”。

（3）samm BRCR指令程序執行是是與rptp nothere-1指令配合使用的。Samm指令的功能是將循環次數的值（這里是11）存放在BRCR中。BRCR（Block Repeat Counter Register）是個16位的寄存器,用于存放程序塊重復操作的次數。Rptp指令是重復操作指令,它的功能是重復執行下一條指令到該指令指定的地址之內的程序代碼,重復執行的次數由brcr決定。在上面的程序中,RPTR指令指定的地址是nothere-1,也就是說：重復執行的程序代碼從bcnd found直到nthere的前一指令Sub*。

xc指令的用法如下：

xc K[,COND1][COND2][,…]

指令中的K=1或2。COND1、COND2是條件。xc指令功能是在條件滿足的情況下,執行該指令下面的K條指令,K為1,則執行一條指令,K為2則執行兩條指令。條件不滿足就執行K條NOP指令。

（4）該源程序是采用TMS320C5X的指令集編寫的,如果是TMS320C5X系列的DSP,則可以直接將上面給出的程序作為一個子程序來使用。而對于TMS320C2XX系列的DSP來說,由于TMS320C5X的指令對TMS320C2XX的指令是向下兼容的,所以在編寫TMS320C2XX的折半查找程序時應作一些修改,比如前面提到的程序中的samm指令,在TMS320C2XX指令集中就沒有。這樣,如果希望用TMS320C2XX來實現本例中的samm語句 功能,則可以將重復操作的次數存放在內部的RAM中,再配合TMS320C2XX循環指令來完成samm與rptp指令的功能。但這樣做將導致程序執行效率的降低。也可以認為TMS320C2XX的數據處理能力較TMS320C5X為弱,其原因主要是兩者指令集的差異。