教你在DSP上实现二进制数折半查找算法

Ferrya

教你在DSP上实现二进制数折半查找算法

* q' m7 j' q( X$ r

! c$ U3 H" f9 c5 k1 K  u( Z       折半查找是采用跳跃跃方式先将顺序数列中的“中间值”与所查询值进行比较，然后按照比值大于或小于“中间值”来判断所查找数的甩在区域。文章给出了将折半算法应用于数字信号处理器上以实现二进制数的查找算法的一种具体方法。并给出了采用这种方法的软件程序。
　　1 折半查找的基本原理
　　近十几年来，随着各类集成化单片数字信号处理器(DSP，Digital Signal Processor)性能的不断改时，相庆的软件和开发工具日臻完善，价格也迅速下降。它们所具有的功能强、集成度高、应用灵活及性能价格比高的优点使其信息处理(如语音与图像各种的处理)、通信、多媒体、综合网络、控制、消费电子、医疗设备、测试与仪器等诸多领域得到了极为广泛的。有一种看法认为：单片机是事物处理型的处理器，如开关的通断或逻辑操作等;数字信号处理器是数据处理型的处理器，如进行大量的包括FFT在内的数据运行等。这种看法在某种程序上是有一定道理的。一般地说，DSP应用系统要处理的数据多、运算量大而且实时性要求较高，研究DSP本身(包括硬件方面和软件方面)的优势对快速有效地执行某种算法有着重要的实用价值。
3 x; ^) n  _# }5 w, z+ Z, T3 K; Q  Y　　查找是智能系统经常用到的操作，实现查找的方法有多种，如顺序查找、折半查找和分块查找等。在这些方法中，如果按顺序存储结构组织的查找表中的所有数据元素按关键字有序，则可以执行折半查找(或称二分查找)。它的基本思想是：由于查找表中的数据按关键字有序(假设递增有序)，则在查找时不必逐个顺序比较，而可以采用跳跃式方式先与“中间位置”的记录关键字比较，若相同，则查找成功，若给定值大于“中间位置”的关键字，则在后半部分进行折半查找，否则在前半部进行折半查找。
& Q% e# Y) H4 r; f4 C0 k　　2 折音查找算法在DSP上的实现
1 o( a( h. O  c' }1 V/ Y　　二进制折半查找算法(Binary Search Algorithm)在DSP上实现并不难，但是一般查找程序都未能充发利用DSP内部先进的结构和指令集，从而使得程序运行的时间未能缩至最短。这在某些时候不会防碍系统效率，但在系统数据量较大而且实时性要求较高的情况下，则必须尽一切可能提高程序的效率。本文以TMS320C50为例给出了一个二进制查找算法的子程序，该程序可使系统的查找效率得到较大提高。
" w* N4 G0 `+ O9 V5 ?! P　　

游客，如果您要查看本帖隐藏内容请回复

青山绿水

回复看看