快速r循環(huán)分塊Jacket變換*

劉桂波，羅大庸，郭　迎

中南大學信息科學與工程學院，長沙410083

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0582-07

?

快速r循環(huán)分塊Jacket變換*

劉桂波+，羅大庸，郭迎

中南大學信息科學與工程學院，長沙410083

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0582-07

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61379153, 61401519, Z201510120620003 (國家自然科學基金); the New Century Excellent Talent Foundation from MOE of China under Grant No. NCET-11-0510 (教育部新世紀優(yōu)秀人才支持計劃).

Received 2015-12,Accepted 2016-02.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2016-02-26, http://www.cnki.net/kcms/detail/11.5602.TP.20160226.0948.002.html

摘要：由中心權(quán)重哈達瑪變換發(fā)展而來的Jacket變換，因其正交性、求逆簡單和擁有快速算法等特點逐漸受book=583,ebook=137到關(guān)注。Jacket變換可應(yīng)用于信號與圖像處理、數(shù)字移動通信、量子編碼、大數(shù)據(jù)處理等領(lǐng)域。為了進一步豐富Jacket變換理論，提出了一種通用的循環(huán)分塊Jacket變換（r-circulant block Jacket transform，r-CBJT）。同時基于基本的r循環(huán)分塊矩陣的性質(zhì)，給出了任意階r循環(huán)分塊Jacket變換矩陣的構(gòu)造方法。隨后進一步推導了任意階r循環(huán)分塊Jacket變換矩陣的快速構(gòu)造與分解算法，該快速算法可表示為單位矩陣與低階Jacket矩陣連續(xù)克羅內(nèi)克積的迭代形式。相比直接計算算法，該快速算法擁有更高的計算效率，且該快速算法也可應(yīng)用于具有類似結(jié)構(gòu)的其他類型的r循環(huán)分塊Jacket變換。

關(guān)鍵詞：哈達瑪變換；r循環(huán)分塊Jacket變換；克羅內(nèi)克積；構(gòu)造與分解；快速算法

1　引言

哈達瑪變換、哈爾變換、離散傅里葉變換以及它們的變體都是離散正交變換，且已經(jīng)廣泛應(yīng)用于信號與圖像處理、移動通信等領(lǐng)域[1-4]。受中心權(quán)重哈達瑪變換的啟發(fā)而提出來的Jacket變換是一種特殊的變換[5]，其對應(yīng)的逆變換矩陣可以由正向變換矩陣的元素或分塊逆來獲得[6]。Jacket變換也可應(yīng)用于信號與數(shù)據(jù)處理[1]、數(shù)字無線通信[7]、加解密[8]、編碼設(shè)計[9]等領(lǐng)域。同時，許多常見的矩陣，譬如哈達瑪矩陣、離散傅里葉矩陣、斜矩陣、某些循環(huán)（分塊）矩陣，都屬于Jacket變換矩陣家族。除此之外，Jacket變換矩陣還與常用的酉矩陣、埃爾米特矩陣等有著密切的聯(lián)系。

有關(guān)離散正交矩陣及其變換的文獻主要涉及探索新的正交變換以及拓展各種變換的實際應(yīng)用等方面。分塊Jacket變換已應(yīng)用于量子信號處理[10]、大數(shù)據(jù)處理[11]、新一代移動通信等。新的正交變換，諸如復哈達瑪變換[12-14]、分式哈達瑪或Jacket變換[15]、參數(shù)化變換[16-18]、混雜變換[7]、更一般的正交變換等[14]，逐漸被提出并不斷地豐富著正交變換家族。

最近，出現(xiàn)了有關(guān)分塊Jacket變換及其應(yīng)用的文獻。其中，文獻[19]首次提出了快速可逆分塊Jacket變換，且實現(xiàn)了N=2k或3k的一維和二維可逆分塊Jacket變換矩陣的快速算法。隨后，相關(guān)文獻又提出了中心權(quán)重分塊Jacket變換，且基于稀疏矩陣分解原理設(shè)計了該類Jacket變換矩陣的快速算法。此后，文獻[6]基于量子信息系統(tǒng)里常見的泡利矩陣定義了一種通用的分塊Jacket變換，同時給出了該類分塊Jacket變換矩陣的快速構(gòu)造和分解算法。但據(jù)了解，至今未有涉及循環(huán)分塊Jacket變換理論及其應(yīng)用的文獻。

本文組織結(jié)構(gòu)如下：第2章給出r循環(huán)分塊Jacket變換矩陣的數(shù)學定義；第3章推導了任意階r循環(huán)分塊Jacket變換存在的條件，該條件間接地提供了構(gòu)造相應(yīng)變換矩陣的方法；第4章設(shè)計實現(xiàn)了r循環(huán)分塊Jacket變換的快速構(gòu)造與分解算法；相比直接計算算法，該快速算法的復雜度分析將在第5章詳細給出；最后是全文的結(jié)論。

2　r-CBJT矩陣的結(jié)構(gòu)

若分塊矩陣[R]n=N/p（符號[?]表示分塊矩陣，下標代表單行或單列包含的子矩陣或子塊矩陣的個數(shù)）擁有如下形式的結(jié)構(gòu)，則稱該類型矩陣是r循環(huán)分塊矩陣：

其中，Rin是序號為i∈(0, 1,…, n-1)且矩陣元素可為實數(shù)或復數(shù)的p×p的子矩陣，r為非零實數(shù)。如果p=1，則n×n維r循環(huán)分塊矩陣是n×n維r循環(huán)矩陣。

同時，對于矩陣JN，定義其相關(guān)矩陣JRTN由原矩陣JN的元素交換行列下標并求倒數(shù)來獲得。也即，矩陣JRTN的(k,i)位置的元素等于矩陣JN的(i, k)位置元素的倒數(shù)。

定義2（r-CBJT矩陣）若矩陣元素為p×p子矩陣的r循環(huán)分塊矩陣[R]n=N/p是Jacket矩陣，則稱矩陣[R]n=N/p是r循環(huán)分塊Jacket矩陣。特別地，若p=1，則[R]n=N/p是r循環(huán)Jacket矩陣。

例1給定非零常量r，如下條件若成立：

則矩陣J2是r循環(huán)分塊Jacket矩陣：

例2假定ω是單位1的復三次根，且如下等式成立：

則矩陣J3也是r循環(huán)分塊Jacket矩陣：

以上列舉的兩個r循環(huán)矩陣都是r-CBJT矩陣的特例。若r=1，則兩個r循環(huán)Jacket矩陣為循環(huán)Jacket矩陣；若r=-1，則兩個r循環(huán)Jacket矩陣即為反循環(huán)Jacket矩陣。

本章給出了r循環(huán)分塊Jacket矩陣結(jié)構(gòu)的數(shù)學描述，同時為了更清晰地描述，列舉了幾個例子。下文將推導r循環(huán)分塊Jacket矩陣的一般存在性條件及其構(gòu)造方法。

3　r-CBJT矩陣的構(gòu)造方法

本章將結(jié)合基本r循環(huán)分塊矩陣的性質(zhì)與r-CBJT矩陣的特殊結(jié)構(gòu)，推導任意階r循環(huán)分塊Jacket矩陣的一般性構(gòu)造方法。

定理1假定n×n維矩陣具有如下形式：

其中符號?x ?表示“向下取整”，或者說“向下舍入”，即取不大于x的最大整數(shù)。

證明假定一個基本的n×n維r循環(huán)矩陣表示為如下形式：

則有Πn=rIn和Π0=In。于是，[R]n[R]RTn可轉(zhuǎn)換為：

因此，若[R]n[R]RTn=In?npIp，當且僅當如下條件必須成立：

其中i∈{1, 2,…, n-1}。因此定理1得證。□

推論1假定2×2維r循環(huán)分塊矩陣表示為如下形式：

其中，子矩陣都是Jacket矩陣，則該矩陣是Jacket矩陣，當且僅當如下等式成立：

證明根據(jù)式（7），令n=2，由式（13）可直接獲得式（13）。因此推論1成立。□

推論2假定n×n維的r循環(huán)分塊矩陣表示為如下形式：

其中，所有子矩陣都是Jacket矩陣。r循環(huán)分塊矩陣[R]n是r-CBJT矩陣，當且僅當如下等式成立：

證明根據(jù)式（7），易驗證該推論也成立。□

該推論為任意階r循環(huán)Jacket矩陣的構(gòu)造提供了一種間接的方法。換而言之，已有的循環(huán)或反循環(huán)（分塊）Jacket變換矩陣都可間接地基于式（7）來構(gòu)建。也即，新提出的r-CBJT矩陣是一種通用的Jacket變換矩陣。另一方面，隨著實際應(yīng)用中Jacket變換矩陣的維數(shù)不斷增加，如何快速地構(gòu)造或分解相對高階r-CBJT矩陣是一個值得研究的問題。

4　快速算法

基于定理1，可以構(gòu)造任意相對高階r-CBJT矩陣。該類矩陣可潛在應(yīng)用于大數(shù)據(jù)處理、新一代移動通信等領(lǐng)域。研究相對高階r-CBJT矩陣的快速算法具有理論和實際意義。

定理2假定n×n維r-CBJT矩陣表示為[R]n=qkpj，此處省略指示子矩陣維數(shù)的標號。矩陣[R]n=qkpj可按照如下方式快速構(gòu)建：

其中p和q互為素數(shù)。矩陣[R]p和[R]q可根據(jù)定理1來構(gòu)造。

證明該定理的證明可以分兩步。首先通過歸納法推導如下等式成立：

若k=1，式（17）可變換為：

式（18）顯然成立。若令k=L，式（17）成立，則可得如下等式：

當k=L+1，利用克羅內(nèi)克積的性質(zhì)可得：

結(jié)合式（19）和（20），式（17）成立。同理可得：

將式（20）和（21）代入式（22），定理2即可得證。□

該定理間接提供了快速構(gòu)建r-CBJT矩陣的方法。譬如r-CBJT矩陣[R]n=72=([I]8?[R]9)([R]9?[I]8)，又[R]8=23

={[R]2?[I]2?[I]2}{[I]2?[R]2?[I]2}{[I]2?[I]2?[R]2}且[R]9=32={[R]3?[I]3}{[I]3?[R]3}。因此交替使用定理1和定理2，最終可獲得矩陣[R]n=72的快速實現(xiàn)方法。

矩陣變換在實際應(yīng)用中常會涉及前后向矩陣，譬如信號圖像處理、編碼設(shè)計、加解密、數(shù)字移動通信等。因此進一步研究r-CBJT矩陣的快速分解同樣具有重要意義。

定理3假定r-CBJT矩陣[R]n=qkpj可分解為互為素數(shù)維數(shù)的Jacket矩陣[R]q和[R]p，則該矩陣可根據(jù)式（16）來快速分解。

證明因該過程是快速構(gòu)造過程的逆過程，故定理3顯然成立。□

例如，令r-CBJT矩陣[R]15的子矩陣是具體的數(shù)，而非矩陣，則其對應(yīng)的分解過程可表示為：

同時，其對應(yīng)的信號流程圖如圖1所示。

Fig.1 Signal flow graph for fast decomposing a r-CBJM with size 15圖1　15階r循環(huán)Jacket矩陣的快速分解信號流程圖

由圖1可知，[R]15的分解包含兩個步驟。其中，第一層包含5個相對獨立的計算單元，而第二層有3個獨立的計算單元。換而言之，快速分解過程得益于分解過程中出現(xiàn)的許多稀疏矩陣。為了后續(xù)研究查詢的方便，表1梳理了20階以內(nèi)的r-CBJT矩陣的快速分解過程。其中第二列表示20以內(nèi)整數(shù)的素數(shù)分解，第三列表示r-CBJT矩陣的快速分解算法。

Table 1 Fast decomposition approaches of r-CBJMs with size from 1 to 20表1　20階以內(nèi)r-CBJT矩陣的快速分解方法

5　復雜度比較分析

本章對r-CBJT變換的快速算法與直接計算算法進行了復雜度比較分析。對于任何N維r-CBJT矩陣，其直接計算算法和快速算法分別需要N(N-1)和kpk(p-1)次算術(shù)加法運算，同時分別需要N2和kpk(p-1)2次算術(shù)乘法運算。表2歸納總結(jié)了算法復雜度的一般性描述公式，其中FCA和DCA分別表示快速算法和直接計算算法。基于表2的結(jié)論，可以獲得任意階r-CBJT矩陣的兩種算法所需要的計算支出。譬如，矩陣[R]27=33，直接計算算法分別需要702次和709次算術(shù)加法和乘法運算，而快速算法僅需162和108次算術(shù)加法和乘法運算。為了更直觀地呈現(xiàn)，圖2比較了20階以內(nèi)r-CBJT矩陣快速算法和直接計算算法分別需要的計算支出。

Table 2 Complexity comparison analysis between fast and direct calculation algorithms of r-CBJMs表2　r-CBJT矩陣的快速算法與直接計算算法復雜度比較分析

Fig.2 Complexity comparison analysis between fast and direct calculation algorithms of r-CBJMs with size from 2 to 20圖2　2到20維r-CBJT矩陣FCA和DCA算法復雜度比較分析

很明顯，直接計算算法的復雜度隨著矩陣階數(shù)的增加呈二次遞增趨勢。而快速算法隨著矩陣階數(shù)的增加上下波動。對于矩陣維數(shù)可以表示為互為素數(shù)積形式的r-CBJT矩陣，快速算法優(yōu)勢明顯。

6　結(jié)束語

新定義的r循環(huán)分塊Jacket矩陣擁有一般Jacket矩陣的良好結(jié)構(gòu)與性質(zhì)。由推導獲得的r-CBJT矩陣一般性存在條件可以間接地構(gòu)造出任意階循環(huán)、反循環(huán)或r循環(huán)（分塊）Jacket矩陣。基于稀疏矩陣分解的方法可以設(shè)計實現(xiàn)r-CBJT矩陣的快速構(gòu)造和分解算法，該快速算法表現(xiàn)為單位矩陣與低階（分塊）Jacket矩陣連續(xù)克羅內(nèi)克積的迭代形式。相比r-CBJT矩陣的直接計算算法，新提出的快速算法具有更低的計算復雜度，且該算法可以應(yīng)用于其他類似擁有r-CBJT結(jié)構(gòu)的Jacket矩陣的快速計算。其他類型的r-CBJT矩陣及其諸如此類矩陣的實際應(yīng)用將在后續(xù)工作中開展。

References:

[1] Kyochi S, Tanaka Y. General factorization of conjugatesymmetric Hadamard transforms[J]. IEEE Transactions on Signal Processing, 2014, 62(13): 3379-3392.

[2] Liu Guibo, Huang Dazu, Luo Dayong, et al. Fast Jacket-Haar transform with any size[J]. Mathematical Problems in Engineering, 2015. doi:10.1155/2015/628642.

[3] Tao Ran, Li Yanlei, Wang Yue. Short-time fractional Fourier transform and its applications[J]. IEEE Transactions on Signal Processing, 2010, 58(5): 2568-2580.

[4] Ahmed N, Rao K R. Orthogonal transforms for digital signal processing[M]. New York: Springer, 1975.

[5] Lee M H. The center weighted Hadamard transform[J]. IEEE Transactions on Circuits and Systems, 1989, 36(9): 1247-1249.

[6] Zeng Guihua, Lee M H. A generalized reverse block Jacket transform[J]. IEEE Transactions on Circuits and Systems, 2008, 55(6): 1589-1600.

[7] Lee M H, Khan H A, Kim K J, et al. A fast hybrid Jacket-Hadamard matrix based diagonal block-wise transform[J]. Signal Processing Image Communication, 2014, 29(1): 49-65.

[8] Aung A, Ng B P, Rahardja S. A robust watermarking scheme using sequency-ordered complex Hadamard transform[J]. Journal of Signal Processing Systems, 2011, 64(3): 319-333.

[9] Song Wei, Lee M H, Matalgah M M, et al. Quasi-orthogonal space-time block codes designs based on Jacket transform[J]. Journal of Communications and Networks, 2010, 12(3):240-245.

[10] Shi Ronghua, Guo Ying, Lee M H. Quantum codes based on fast pauli block transforms in the finite field[J]. Quantum Information Processing, 2010, 9(5): 611-628.

[11] Li Jun, Yan Yier, Duan Wei, et al. Tensor decomposition of Toeplitz Jacket matrices for big data processing[C]//Proceedings of the 2015 International Conference on Big Data and Smart Computing, Jeju, Korea, Feb 9-11, 2015. Piscataway, USA: IEEE, 2015: 11-14.

[12] Aung A, Ng B P, Rahardja S. Sequency-ordered complex Hadamard transform: properties, computational complexity and applications[J]. IEEETransactions on Signal Processing, 2008, 56(8): 3562-3571.

[13]Wu Jiasong, Wang Lu, Yang Guanyu, et al. Sliding conjugate symmetric sequency-ordered complex Hadamard transform: fast algorithm and applications[J]. IEEE Transactions on Circuits and Systems, 2012, 59(6): 1321-1334.

[14] Pei S C, Wen C C, Ding J J. Sequency-ordered generalized Walsh-Fourier transform[J]. Signal Processing, 2013, 93(4): 828-841.

[15] Mao Yun, Peng Jun, Guo Ying, et al. On the fast fractional Jacket transform[J]. IEEE Transactions on Circuits Systems and Signal Processing, 2014, 33(5): 1491-1505.

[16] Bouguezel S, Ahmad M O, Swamy M N S. A new class of reciprocal-orthogonal parametric transforms[J]. IEEE Transactions on Circuits and Systems, 2009, 56(4): 795-805.

[17] Bouguezel S, Ahmad M O, Swamy M N S. New parametric discrete Fourier and hartley transforms, and algorithms for fast computation[J]. IEEE Transactions on Circuits and Systems, 2011, 58(3): 562-575.

[18] Lee M H, Zhang Xiaodong, Jiang Xueqin. Fast parametric reciprocal-orthogonal Jacket transforms[J]. EURASIP Journal on Advances in Signal Processing, 2014. doi: 10.1186/ 1687-6180-2014-149.

[19] Lee M H, Hou Jia. Fast block inverse Jacket transform[J]. IEEE Signal Processing Letters, 2006, 13(8): 461-464.

LIU Guibo was born in 1981. He is a Ph.D. candidate at Central South University. His research interests include orthogonal transforms and signal and image processing, etc.

劉桂波（1981—），男，湖南邵陽人，中南大學信息科學與工程學院博士研究生，主要研究領(lǐng)域為正交變換，信號與圖像處理等。

LUO Dayong was born in 1944. He is a Ph.D. supervisor at Central South University. His research interests include signal and image processing, control theories and application, etc.

羅大庸（1944—），男，湖南長沙人，中南大學信息科學與工程學院博士生導師，主要研究領(lǐng)域為信號與圖像處理，控制理論與應(yīng)用等。發(fā)表學術(shù)論文70多篇，其中SCI檢索20余篇。

GUO Ying was born in 1975. He received the Ph.D. degree in electronic engineering from Shanghai Jiao Tong University in 2006. Now he is a Ph.D. supervisor at Central South University. His research interests include quantum communication and network security, etc.

郭迎（1975—），男，山東曲阜人，2006年于上海交通大學電子工程學院獲得博士學位，現(xiàn)為中南大學信息科學與工程學院博士生導師，主要研究領(lǐng)域為量子通信，網(wǎng)絡(luò)安全等。發(fā)表學術(shù)論文100多篇，其中SCI檢索70余篇，EI檢索30余篇。

Fast r-Circulant Block Jacket Transform?

LIU Guibo+, LUO Dayong, GUO Ying
School of Information Science and Engineering, Central South University, Changsha 410083, China

+ Corresponding author: E-mail: lgbtrs2006@126.com

LIU Guibo, LUO Dayong, GUO Ying. Fast r-circulant block Jacket transform. Journal of Frontiers of Computer Science and Technology, 2016, 10(4)：582-588.

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

文獻標志碼：A

中圖分類號：TP301

doi:10.3778/j.issn.1673-9418.1601008