Research On Cordic-based Fast Algoritms And Implementations Of Discrete Trigonometric Transforms

Discrete trigonometric transforms (DTTs) play a very important role in information processing, especially for video and image processing. Therefore, their fast algorithms and VLSI hardware implementations have been hot research field. After the new video compression standard H.265/HEVC published, conventional fast algorithms of the DTTs have been unable to meet the application requirements, large-point (especially for2n-points) and variable-point fast algorithms will become research hot.In video and image processing applications, the hardware implementation architectures for accurately calculating the DTTs have been mature. Approximate calculating instead of accurate calculating will become another way to improve the computing speed. Using a single compression coding cannot meet people’s increasing demands in video and image processing. Therefore, developing the hybrid compression coding methods and their corespording unified-architectures for a variety of orthogonal transforms are urgent problem.For the above hot research problems, the research work will focus on the large point (e.g.,2n-points) fast algorithms of the DTTs, the unfolded CORDIC based approximation implementation for DTT computation and the unified architectures of the DTTs.The major contribution of the work includes:1. The CORDIC-based radix-2fast algorithms of the DTTs are studied. In this paper, the CORDIC algorithm is used as the transform kernel function and the fast algorithms for any2n-point DCT-II and DST-II are developed using odd-even decomposition method. On this basis, any2n-point DCT-III and DST-III fast algorithms and their signal-flows are deduced according to the principle of duality of the orthogonal transforms. Thus, new CORDIC-based radix-2fast algorithms of the DTTs are proposed. The proposed fast algorithms are better than the existing algorithms in hardware complexity, scalability, pipelinablity and modularity. Furthermore, the proposed algorithms also have some distinguish advantages, such as suitable for any2n-point and various types of DTTs, low hardware complexity and suitable for VLSI implementation, arithmetic-sequence rotation angles of the CORDICs, uniform scaling factor and regular data flow, suitable for pipelineability and supporting in-place operation and so on.2. The hardware implementation for the proposed fast algorithms of the DTTs are studied. Firstly, in order to solve the problem between the iterations and the computation precision in the traditional non-overlap CORDIC algorithm, an improved non-overlap CORDIC algorithm (MCORDIC) is developed. This improved algorithm can reduce the iteration number of the unfolded CORDIC by50%at a little cost of accuracy. Secondly, since the rotation angles of the CORDIC in proposed algorithms are arithmetic sequence, the required number and types of the CORDIC can be significantly reduced by using modular design and reusable design. Theoretically speaking, any2n-point DTT can be achieved using only one type of CORDIC. Then an novel approach for designing the systolic array of the DTTs is developed. The proposed systolic array is superior to other similar structures in lantency, throughput, pipelinable and hardware complexity. Besides, this design approach can be used to solve the traditional problems of the DTT systolic arrays. Moreover, using row-column decomposition we propose a hardware utilization efficiency2-D DCT-II/DCT-III structure.3. The intrinsic relationship among proposed CORDIC-based DTTs is used to deduce a universal design approach for the DTT computation by taking full advantage of the nature of trigonometric functions. This approach uses the characteristic, which is that the same point DTTs have identical CORDIC cells, to achieve the computation of different DTTs by controlling dataflow. This design approach is suitable for any2n-point DTTs and any combination among four kinds of DTTs. Moreover, the proposed approach not only have unique transform kernel function, simple control circuit, but also has higher hardware reusing rate. Afterwards, several representative unified architectures are designed. The proposed unified architectures of the DTTs are superior to the existing unified architectures in hardware complexity, control complexity, throughput, scalability, modularity and pipelinability. In addition, we also develop the DWHT/DCT-II and Haar-DWT/DCT-II unified architecture design approach.4. The architecture for data-dependent compression coding is studied based on the Haar-DWT/DCT-II unified architecture. The JND is used as the threshold for selecting the compressing modes. To solve problems of the conventional JND algorithm, a approximated JND based on Haar-DWT is proposed. Though the proposed JND algorithm only obtain the approximated value of the JND, it sharply reduces the arithmetic complexity. Reuseable DCT-II architecture can be used to work in two oporating modes (approximate calculation mode and accurate calculation mode). Then, the control scheme is studied, and the referenced position and the JND threshold value of operate modes are slectected based on a lot of experiments. The proposed architecture for data-based compression coding is approved. The proposed architecture has very low hardware complexity without complicated arithmetic elements, so it is very suitable for the VLSI implementation.This paper proposes fast algorithms of the DTTs that use the CORDIC as kernel transfer function, which provides novel research ideas and methods for researching the fast algorithms of the DTT. In video, image compression field, the proposed alogorihms and architectures meet the requirements of the application and future development direction. As the Cooley-Tukey FFT puts forward the DFT in practical applications, the DTTs will be more widely used in the field of digital signal processing due to the fast algorithms that have the similar characteristics with the FFT. Therefore, these studies not only have theoretical prospective, but also have the practical application value.