A Study On The Multi-dimensional DCT/IDCT Stereo Similar Butterfly Algorithm And Its Unit Pipeline Architectures

The rapid development of theory and practical application in communication and computer technology provide a good environment for the research of signal transform application. Therefore, efficient methods of signal processing transform become the critical point in hot research. DCT algorithm is simple, its transform effects are efficient, its performance is the most close to the best optimal transform, which of these characteristics lay the foundation for its core position in transform domain.Although various research on DCT algorithm mature increasingly, has limitation on range of adaptability. For example, most algorithms can only adapt to the transform with a certain block size, or a certain dimension(usually 1D, 2D, or 3D), or can adapt to the forward transform or its inverse only in the algorithm architectures. Little research on the compatible algorithm with block size, dimension, forward and inverse transform, and its architectures are mentioned rarely. The reason is a mathematical method required to multi-dimensional extension from one dimension to complete the DCT algorithm multidimensional operation efficiently, in addition, the algorithm and its architectures should also be regularity and feasibility.Firstly, in this paper, we put forward a kind of multi-dimensional DCT/IDCT algorithm according to the basic algorithm, the mathematical core of which is "tensor product" operation. We analysis algorithm operational process from the view of mathematics, and deduce a kind of butterfly signal flow figure with butterfly units, permutation units and multipliers units. The algorithm has characteristics, such as different block size transform methods consistency,multidimensionality, forward and inverse transform involves only input and output in a different order, etc.Secondly, we put forward a kind of unit architectures consist of delayers,selectors and adders based on the DCT algorithm principle and butterfly form proposed above by decomposing it in units form. We applied the architectures cooperate with multipliers units to the whole algorithm to from a pipeline architecture consist of delayers, selectors, adders and multipliers, and the units cascade connection each other in this architectures.Thirdly, we put forward a kind of compatible pipeline architecture use DCT algorithm with block scale variable, multi-dimensional transform, forward and inverse transform by analyzing the characteristics and connections of the DCT/IDCT pipeline unit architectures in different block scale, one and multi-dimension, forward and inverse transform.Fourthly, in order to solve the problems of using a lot of delayers and selectors independently and different block scale are not easy to integrate in our algorithm architectures, we invest and improve our unit pipeline architectures by establishing integrated models of delayers and selectors to save devices.Finally, we build multi-dimensional models to test performance of our n-D DCT/IDCT stereo type algorithm. Furthermore, we apply this algorithm to video compression coding.We summarized the following conclusion by studing the multi-dimensional DCT/IDCT stereo similar butterfly algorithm and its unit pipeline architectures in this paper.(1)It is shown that the thinking of tensor product operation as the core of deduction from one dimension to multi-dimension is simple, intuitional, the connection among dimensions is easy.(2)The inspiration of stereo similar butterfly from based on the form of FFT algorithm, stereo butterfly is equivalent to the one dimensional butterfly should "multidimensional" process, expressed the essence of complex formulas of our algorithm in this article intuitively.(3)We put forward the stereo similar butterfly not only solve the problemof visualization of the complex formulas, but also to study the architectures of our algorithm principle expediently. The main units of architectures of our algorithm are delayers, selectors and adders, these units are consistent. These units cascade connection with multipliers to consist of unit pipeline architectures, the architectures expressed the algorithm principle intuitively. Our stereo similar butterfly algorithm and its unit pipeline architectures achieved the compatible characteristics of block scale variable, multi-dimensional transform, forward and inverse transform.(4)We established integrated models to solve the problem of wasting a lot of devices which are disposable by reusing delayers with selectors in order to achieve the purpose of increasing the service efficiency of the devices.Experimental results are shown that the unit pipeline architectures of device-saving proposed can achieve the purpose of saving devices, and saving effect in the large scale block signal processing is more obvious.(5)From the perspective of practical application, we test n-D DCT/IDCT the performances of stereo similar butterfly algorithm by experiments. Results are shown that our algorithm proposed have lower complexity, high compression ratio, short time consuming, and high EPE of each component in the multiple perspectives of YUV video. The optimal compatibility features make algorithm in practical application with advantages, which provides guidance algorithm for dynamic DCT transform such as dimension and scale block.From the above, the n-D DCT/IDCT stereo similar butterfly algorithm and its unit pipeline architectures which put forward in this paper have the characteristics of block scale variable, multi-dimensional transform, forward and inverse transform. The architectures consist of delayers, selectors, adders,multipliers units. Our algorithm and its architectures put forward in this paper provide a new referential study direction for DCT and other transform algorithms,and also provide a referential method of multidimensional transform processing in video signal and other application field.