Research On First-order Moments-based Fast Algorithms For Computations With Convolution Form And Their Hardware Structures

With the rapid development of information technology,electronic technology and computer,the digital signal processing technology has been widely used in many different fields.As the basic operations in digital signal processing,cyclic convolution,discrete Fourier transform(DFT)and finite impulse response(FIR)filtering have very important research value.By studying their fast algorithms and effective hardware structures,their computational complexity can be reduced and their computational efficiency can be improved,thus bringing new changes in their application fields.Since cyclic convolution,DFT and FIR filtering in essence are inner product computations,their hardware structures usually contain plenty of memories or multipliers,which take up many hardware resources,and have high power consumption with limited computation speed.To avoid the requirements for plenty of memories or multipliers in hardware structures of computations with inner product form,Jianguo Liu et al.proposed a series of first-order moments-based fast algorithms and hardware structures.The main research work of this thesis is to design fast algorithms and high-efficient hardware structures for three kinds of convolution computations,which are cyclic convolution,prime-length DFT and FIR filtering,by using the fast algorithm and hardware structures for first-order moment.For this purpose,firstly,two kinds of new hardware structures for first-order moment are proposed respectively from the perspectives of serial and parallel computation,which take up less hardware resources.The new parallel computation structure for first-order moment has higher computational performance and greater advantage in applications of parallel computation.In the next step,cyclic convolution is converted into the form of first-order moment,and a novel fast first-order moment-based algorithm for cyclic convolution is proposed by use of the fast algorithm for first-order moment and the proposed decomposition strategy on convolution kernel.Base on the new algorithm,and combined with the proposed preprocessing scheme on convolution sub-kernel and the inherent characteristic of parallel processing of the algorithm,two kinds of efficient general hardware structures for cyclic convolution is designed by using the serial computation structure for first-order moment as the basic computing unit.Later on,by converting the prime-length DFT into the main form of cyclic convolution and further convert the cyclic convolution into the form of shifting-accumulating of multiple first-order moments,a fast first-order moment-based algorithm for a prime-length DFT is proposed.Since the convolution kernel derived from a given prime-length DFT is fixed,two specific modules for first-order moment conversion are designed.The final dedicated hardware structure for a prime-length DFT is mainly composed by either one of the first-order moment conversion modules and the new parallel computation structures for first-order moments.In the end,by applying the fast algorithm for first-order moment into FIR filtering operations,a novel fast first-order moment-based algorithm for FIR filtering is proposed.And due to the high-degree of overlap among the required input data-flows in sequential filtering results,a general hardware structure for FIR filtering is designed by following the design ideas of time-efficient structure for cyclic convolution discussed previously,which can be used to calculate any number of sequential filtering results in parallel.The theoretical analysis on fast algorithms shows that,there are no multiplication operations existed in each new fast algorithm.Compared with the existing first-order moments-based fast algorithms,the addition operations existed in each new fast algorithm are significantly decreased.Therefore,these new fast algorithms have the possibility to be rapidly realized.The theoretical analysis on hardware structures shows that,there are no multipliers and not many adders and memory cells existed in each new hardware structure.Therefore,these new hardware structures have the possibility to be high-efficiently implemented.The performance analysis on each new hardware structure with its logic implementation shows that,by selecting appropriate hardware structure for first-order moment and setting structural parameters as their optimal values under specific application requirements,it can achieve higher comprehensive performance.In addition,multiple groups of comparison experiments and analysises conducted between the new general hardware structures and comparative structures further demonstrate the effectiveness and superiority of each new general hardware structure as well.