基于旋转算术的正交变换快速分解算法

Fast decomposition algorithms of orthogonal transform based on rotation arithmetic

传统上都采用“乘加算术”实现正交变换，鲁棒性差。该文基于新的快速“旋转算术”，提出了各种正交变换包括重叠正交变换快速分解算法与运算结构。它们可以结合使用，将各种正交变换快速分解为Ｇｉｖｅｎｓ旋转序列，用快速旋转器硬件有效地进行运算，使整个变换所需“右移—加”运算次数大大减少，以至于其计算复杂度与传统的“乘加算术”可比，从而可以用在一类新型的以快速旋转器为内核实现各种正交变换的ＶＬＳＩ微处理器中。为此还按照所提出的算法开发了一个与微处理器相应的、能够产生高效控制代码的编译器。

Orthogonal transforms are traditionally realized by “multiplication addition arithmetic” with less robustness. The fast decomposition algorithms and computation architectures for various orthogonal transforms including lapped orthogonal transform based on the new “fast rotation arithmetic” are proposed, which can be used combinationally. Fastly decomposing different orthogonal transforms to Givens rotation sequences and then effectively performing the computation by using the fast rotation hardware make the number of the “shift addition” needed by the whole transform greatly decreased so that its computation complexity is lowered down and comparable with the traditional “multiplication additioan arithmetic”. It can be used in a new VLSI microprocessor to realize various orthogonal transforms with the fast rotator as the core. A compiler coresponding to both the algorithms and the microprocessor is developed for generation of highly effective control codes.