Implementation of Binary Number Half Search Algorithm on DSP

    Abstract: Half search uses a jumping method to first compare the "middle value" in the sequential sequence with the query value, and then determines the area of ​​the searched number based on whether the ratio is greater than or less than the "middle value". The article gives a specific method of applying the half algorithm to a digital signal processor to implement a binary number search algorithm. And a software program using this method is given.

    Keywords: Half search binary DSP

1 Basic principles of half search

In the past decade or so, with the continuous improvement of the performance of various integrated single-chip digital signal processors (DSPs, Digital Signal Processors), Xiangqing's software and development tools have become increasingly perfect, and their prices have also dropped rapidly. Their advantages of strong functions, high integration, flexible application and high cost performance make them suitable for information processing (such as voice and image processing), communications, multimedia, integrated networks, control, consumer electronics, medical equipment, Testing and instrumentation and many other fields have been extremely extensive. There is a view that the microcontroller is a transaction processing processor, such as switching on and off or logical operations; the digital signal processor is a data processing processor, such as performing a large number of data operations including FFT. This view makes some sense in some procedures. Generally speaking, DSP application systems have to process a lot of data, have a large amount of calculations, and have high real-time requirements. Studying the advantages of DSP itself (including hardware and software) has important practical value for quickly and effectively executing a certain algorithm.

Search is a frequently used operation in intelligent systems. There are many ways to implement search, such as sequential search, half search, and block search. In these methods, a binary search can be performed if all data elements in a lookup table organized in a sequential storage structure are ordered by key. Its basic idea is: since the data in the lookup table is ordered by keyword (assuming increasing order), it is not necessary to compare sequentially one by one during the search, but can be compared with the record keywords in the "middle position" in a jumping manner. , if they are the same, the search is successful. If the given value is greater than the keyword in the "middle position", a half search is performed in the second half, otherwise a half search is performed in the first half.

2 Implementation of the folding search algorithm on DSP

It is not difficult to implement the Binary Search Algorithm on a DSP, but general search programs fail to make full use of the advanced structure and instruction set inside the DSP, thus failing to minimize the program running time. This will not hinder system efficiency at certain times, but when the system data volume is large and real-time requirements are high, you must do everything possible to improve the efficiency of the program. This article takes TMS320C50 as an example to give a subroutine of a binary search algorithm, which can greatly improve the search efficiency of the system.

The program makes full use of the bit-reverse addressing instruction of TMS320C50, which can halve the search work during each test and release the accumulator for other work. In addition, the program utilizes conditional execution instructions (XC) instead of traditional conditional transition instructions, which saves instruction cycles and improves efficiency. For the specific instruction set of TMS320C50, please refer to other documents [1].

The binary search program introduced in this article is performed in an ordered state. It assumes that the data in the table is arranged from low to high, with the largest number at the largest address in memory. Of course, the opposite is also true (the smallest number is at the highest bit of the address). In addition, the program also assumes that the maximum number in the data is a power of 2. In the source program given below, the number is 2 11.

Source program of TMS320C50:

.bss NTABLE,800h; data space of 2 to the 11th power (arranged from low to high)

.bss LOOK,1; Number to be found

.mmregs

.text

.

.

.

call bsearch

.

.

.

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

;Binary search subroutine

;Program name: binsearch

; Entry parameter: (ACC) the binary number to be searched for

;Exit parameter: (ACC) the address of the binary number to be found (the data is found)

(ACC)=0(data not found)

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

bin-search lar AR0,#0800h ;The total number of AR0 data

mar*,AR0

mar *BR0+ ,AR3 ;Half of the total number

lar AR3, #NTABLE;AR3 points to the beginning of the update

lacl #11; Repeat 2 to the Nth power, the number of sequence data is 2 to the Nth power

samm BRCR; the number of repetitions is stored in BRCR

ldp #LOOK

lace LOOK ;The data to be found is stored in ACC

sub *; subtract from the data in the storage unit pointed to by AR3

bcnd nonethere, LT; ACC value is less than 0, the data to be found is not in this sequence

rptd nonethere-1

bend found,EQ; hit data

xc 1, GT; if the data in ACC is larger

mar *0+, AR0 ;

xc 1, LT; if the data in ACC is small

mar *0-, AR0 ;

mar *BR0+, AR3 ;The search space is halved

laccLOOK

sub *

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

; Not found, set ACC to 0 and return

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

noneretd

zac

nop

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

;Find the data, store the data address in ACC and return

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

foundldp #0

apl #0fffeh,PMST ;Reset PMST bit

retd

lamm AR3 ;store data address

nop

3 Auxiliary instructions

The program introduces the functions required for each step in more detail, and some key points are explained below.

(1) If the program finds the data it is looking for, it will return the address where the data is located. If it does not find it, it will send 0 to the ACC register.

(2) mar BR0+ and AR3 in the program add the contents of AR0 to the contents of the data memory specified by the current AR (auxiliary register) in reverse carry mode. Since there is a mar*, AR0 instruction before this instruction, this instruction specifies the auxiliary register of the next instruction. Therefore, when executing MAR BR0+, AR3, the auxiliary register AR0 is actually added to its own reverse phase:

(3) The samm BRCR instruction program execution is used in conjunction with the rptp nothere-1 instruction. The function of the Samm instruction is to store the value of the number of cycles (here 11) in BRCR. BRCR (Block Repeat Counter Register) is a 16-bit register used to store the number of program block repeat operations. The Rptp instruction is a repeated operation instruction. Its function is to repeatedly execute the next instruction to the program code within the address specified by the instruction. The number of repeated executions is determined by brcr. In the above program, the address specified by the RPTR instruction is nothere-1, that is to say: the program code repeatedly executed is from bcnd found to the previous instruction Sub* of nthere.

The usage of xc instruction is as follows:

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

K=1 or 2 in the instruction. COND1 and COND2 are conditions. The function of the xc instruction is to execute the K instructions below the instruction when the conditions are met. If K is 1, then one instruction is executed. If K is 2, two instructions are executed. If the conditions are not met, K NOP instructions are executed.

(4) The source program is written using the instruction set of TMS320C5X. If it is a DSP of the TMS320C5X series, the program given above can be used directly as a subroutine. For the TMS320C2XX series of DSPs, since the instructions of TMS320C5X are backward compatible with the instructions of TMS320C2XX, some modifications should be made when writing the half search program of TMS320C2XX. For example, the samm instruction in the program mentioned above is in TMS320C2XX. There is no such thing in the instruction set. In this way, if you want to use TMS320C2XX to implement the samm statement function in this example, you can store the number of repeated operations in the internal RAM, and then cooperate with the TMS320C2XX loop instructions to complete the functions of the samm and rptp instructions. But doing so will lead to a reduction in program execution efficiency. It can also be considered that the data processing capability of TMS320C2XX is weaker than that of TMS320C5X. The reason is mainly due to the difference in the instruction sets between the two.