二進(jìn)制數折半查找算法在DSP上的實(shí)現

作者：時(shí)間：2010-12-22 來(lái)源：網(wǎng)絡(luò )

加入技術(shù)交流群
- 掃碼加入
  和技術(shù)大咖面對面交流
  海量資料庫查詢(xún)

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

本文引用地址：http://dyxdggzs.com/article/151158.htm

關(guān)鍵詞：折半查找二進(jìn)制 DSP

1 折半查找的基本原理

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

查找是智能系統經(jīng)常用到的操作,實(shí)現查找的方法有多種,如順序查找、折半查找和分塊查找等。在這些方法中,如果按順序存儲結構組織的查找表中的所有數據元素按關(guān)鍵字有序,則可以執行折半查找（或稱(chēng)二分查找）。它的基本思想是：由于查找表中的數據按關(guān)鍵字有序（假設遞增有序）,則在查找時(shí)不必逐個(gè)順序比較,而可以采用跳躍式方式先與“中間位置”的記錄關(guān)鍵字比較,若相同,則查找成功,若給定值大于“中間位置”的關(guān)鍵字,則在后半部分進(jìn)行折半查找,否則在前半部進(jìn)行折半查找。

2 折音查找算法在DSP上的實(shí)現

二進(jìn)制折半查找算法（Binary Search Algorithm）在DSP上實(shí)現并不難,但是一般查找程序都未能充發(fā)利用DSP內部先進(jìn)的結構和指令集,從而使得程序運行的時(shí)間未能縮至最短。這在某些時(shí)候不會(huì )防礙系統效率,但在系統數據量較大而且實(shí)時(shí)性要求較高的情況下,則必須盡一切可能提高程序的效率。本文以TMS320C50為例給出了一個(gè)二進(jìn)制查找算法的子程序,該程序可使系統的查找效率得到較大提高。

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

本文介紹的二進(jìn)搜尋程序是在有序狀態(tài)下進(jìn)行的。它假設表格中的數據按由低到高的次序排列,最大數在存儲器中的地址最大。當然,反之（最小數在地址的最高位）亦是如此。此外,程序還假設數據中的最大個(gè)數是2的冪次方,在下面給出的源程序中個(gè)數2 11個(gè)。

TMS320C50的源程序：

.bss NTABLE,800h ;2的11次冪的數據空間（按由低到高排列）

.bss LOOK,1 ;要查找的數

.mmregs

.text

call bsearch

;***********************

;二進(jìn)制查找子程序

;程序名：binsearch

;入口參數：（ACC）所要查找的二進(jìn)制數

;出口參數：（ACC）所要查找的二進(jìn)制數的地址（數據被找到）