Implementation Of Two Dimensional Fast Hadamard Tranform For FPGA

Being the key part of digital signal processing, mathematical transformation effects the performance of whole system. In addition, the increase of the amount of information and signal dimension cause a demand of simpler transform algorithm and a more proper system design for transformation. Walsh-Hadamard transform is a kind of non-sinusoidal transform with easy structure, and it has four advantages which make Hadamard transform a promising prospect:(a)only involves real numbers, (b)non-multiplication calculations, (c)inverse transform is convenient, (d)exists fast algorithm and easy implement in hardware. FPGA is a applicable platform to achieve signal processing problems for the merits of high flexibility and parallel processing method. However, at present researches of implementations of Hadamard transform for FPGA usually focus on one-dimension and low points. In practice, images are saved in the form of two-dimensional signal, the premise of image processing is the transformation of the 2D image signal. Under such condition, this thesis pay attention to (a)two dimensional and high points implementation for FPGA based on traditional "row and column"(RC) method, (b)a novel block splitting(BS) technique’implementation and the discussion of realization for high points FPGA implementation.Firstly, the background of Hadamard transform is introduced, which includes the research significance of implementation, its current situation and future development prospect. Then the key technologies of using FPGA platform to implement transform algorithm and digital signal problems are describe.Secondly, this paper begins with Walsh functions, deduces 1D and 2D transformation formula based on the theoretical characteristics of Hadamard matrix which is the transform kernel. To one dimensional transform, by using sparse matrix to simplify the transform kernel, we obtain the fast algorithm of 1D Hadamard transform. To two dimensional transform, fast algorithms of "RC" method and "BS" technique are proposed. "RC" is a kind of fast algorithm by decomposing 2D transform to two 1D fast transforms. "BS" achieves the algorithm by the splitting idea that constantly quartering the operation matrix.Based on the theory mentioned above, the research for "RC" and "BS" of implementation of 2D Hadamard transform for FPGA platform are considered. The designs and simulations are operating through Quartus II and Modelsim platform respectively, and verify the validity on Matlab and its real-time capability. For RC method, the transform system is applied to the research of image processing, and for BS method, it gives the hardware expand expectation for the future high points realization. Last, the comparisons in hardware resource and running time are made between the two methods.Research results shows that, the FHT designs based on "RC" and "BS" method for FPGA realized the algorithm for two dimensional and high points input requirement, at the same time meet the accuracy demand successfully.