Journal of Frontiers of Computer Science and Technology ›› 2016, Vol. 10 ›› Issue (4): 582-588.DOI: 10.3778/j.issn.1673-9418.1601008

Previous Articles     Next Articles

Fast r-Circulant Block Jacket Transform

LIU Guibo+, LUO Dayong, GUO Ying   

  1. School of Information Science and Engineering, Central South University, Changsha 410083, China
  • Online:2016-04-01 Published:2016-04-01


刘桂波+,罗大庸,郭  迎   

  1. 中南大学 信息科学与工程学院,长沙 410083

Abstract: Jacket transform, inspired by the well-known Hadamard transform, has been attracting more and more attentions due to its orthogonality, simplicity of matrix inversion and existence of fast algorithm. Jacket transform is applied to signal and image processing, digital mobile communication, quantum coding and big-data processing, etc. To further enrich the theory of Jacket transform, this paper proposes a generalized r-circulant block Jacket transform (r-CBJT). Meanwhile, this paper suggests an approach for the elegant construction of the r-circulant block Jacket matrices (r-CBJMs) with any size by using the structure of the permutation matrices. After that, fast construction and decomposition algorithms of r-CBJMs are designed with the Kronecker product of corresponding identity matrices and relative lower order Jacket matrices in a successively iterative form. They have less computation complexity compared to direct calculation approach. Furthermore, the proposed approach can be employed to other r-CBJTs with similar characteristics.

Key words: Hadamard transform; r-circulant block Jacket transform, Kronecker product, construction and decomposition, fast algorithm

摘要: 由中心权重哈达玛变换发展而来的Jacket变换,因其正交性、求逆简单和拥有快速算法等特点逐渐受到关注。Jacket变换可应用于信号与图像处理、数字移动通信、量子编码、大数据处理等领域。为了进一步丰富Jacket变换理论,提出了一种通用的循环分块Jacket变换(r-circulant block Jacket transform,r-CBJT)。同时基于基本的r循环分块矩阵的性质,给出了任意阶r循环分块Jacket变换矩阵的构造方法。随后进一步推导了任意阶r循环分块Jacket变换矩阵的快速构造与分解算法,该快速算法可表示为单位矩阵与低阶Jacket矩阵连续克罗内克积的迭代形式。相比直接计算算法,该快速算法拥有更高的计算效率,且该快速算法也可应用于具有类似结构的其他类型的r循环分块Jacket变换。

关键词: 哈达玛变换, r循环分块Jacket变换, 克罗内克积, 构造与分解, 快速算法