example 3-24.c

《基于TI DSP的通用算法实现》程序代码

;Example 3 - 24. Generation Index Tab C Listing for a Bit Reversion Function

/*=============================================================	*/
/* TEXAS INSTRUMENTS, INC.                                       		*/
/*	NAME: bitrev_index                                            		*/
/* USAGE                                                            		*/
/*	This function has the prototype:                             		*/
/* 		void bitrev_index(short *index, int n);              		*/
/*      	index[sqrt(n)] : Pointer to index table that is 		*/
/*								returned by the routine.            	*/
/*      	n: Number of complex array elements to bit-reverse. 	*/
/*	DESCRIPTION                                                           */
/* 		This routine calculates the index table for performing a	*/
/* 		complex bit reversal of an array of length n. The length	*/
/*		of the index table is 2^(2*ceil(k/2)) where n = 2^k. In 	*/
/*		other words, the length of the index tab is sqrt(n) for	*/
/*		even powers of radix.											*/
/*=============================================================	*/
                                                                          
void bitrev_index(short *index, int n) 
{                                                                   
    int   i, j, k, radix = 2; 
    short nbits, nbot, ntop, ndiff, n2, raddiv2; 
                      
    nbits = 0; i = n;     
    while (i > 1){       
        i = i >> 1;  nbits++;   
    }                                                               
             
    raddiv2 = radix >> 1;              
    nbot    = nbits >> raddiv2;                    
    nbot    = nbot << raddiv2 - 1;            
    ndiff   = nbits & raddiv2;             
    ntop    = nbot + ndiff;                  
    n2      = 1 << ntop;                    
                                           
    index[0] = 0;                          
    for ( i = 1, j = n2/radix + 1; i < n2 - 1; i++){                                                               
        index[i] = j - 1;                       
                                               
        for (k = n2/radix; k*(radix-1) < j; k /= radix) 
            j -= k*(radix-1);           
                                     
        j += k;            
    }                 
    index[n2 - 1] = n2 - 1;   
}