劉桂波，羅大庸，郭　迎

中南大學(xué)信息科學(xué)與工程學(xué)院，長(zhǎng)沙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變換*

劉桂波+，羅大庸，郭迎

中南大學(xué)信息科學(xué)與工程學(xué)院，長(zhǎng)沙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 (國(guó)家自然科學(xué)基金); the New Century Excellent Talent Foundation from MOE of China under Grant No. NCET-11-0510 (教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃).

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

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

1　引言

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

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

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

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

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

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

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

同時(shí)，對(duì)于矩陣JN，定義其相關(guān)矩陣JRTN由原矩陣JN的元素交換行列下標(biāo)并求倒數(shù)來(lái)獲得。也即，矩陣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的復(fù)三次根，且如下等式成立：

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

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

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

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

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

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

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

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

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

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

其中i∈{1, 2,…, n-1}。因此定理1得證?！?/p>

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

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

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

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

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

證明根據(jù)式（7），易驗(yàn)證該推論也成立?！?/p>

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

4　快速算法

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

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

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

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

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

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

當(dāng)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的快速實(shí)現(xiàn)方法。

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

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

證明因該過(guò)程是快速構(gòu)造過(guò)程的逆過(guò)程，故定理3顯然成立?！?/p>

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

同時(shí)，其對(duì)應(yīng)的信號(hào)流程圖如圖1所示。

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

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

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

5　復(fù)雜度比較分析

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

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

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算法復(fù)雜度比較分析

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

6　結(jié)束語(yǔ)

新定義的r循環(huán)分塊Jacket矩陣擁有一般Jacket矩陣的良好結(jié)構(gòu)與性質(zhì)。由推導(dǎo)獲得的r-CBJT矩陣一般性存在條件可以間接地構(gòu)造出任意階循環(huán)、反循環(huán)或r循環(huán)（分塊）Jacket矩陣?；谙∈杈仃嚪纸獾姆椒梢栽O(shè)計(jì)實(shí)現(xiàn)r-CBJT矩陣的快速構(gòu)造和分解算法，該快速算法表現(xiàn)為單位矩陣與低階（分塊）Jacket矩陣連續(xù)克羅內(nèi)克積的迭代形式。相比r-CBJT矩陣的直接計(jì)算算法，新提出的快速算法具有更低的計(jì)算復(fù)雜度，且該算法可以應(yīng)用于其他類似擁有r-CBJT結(jié)構(gòu)的Jacket矩陣的快速計(jì)算。其他類型的r-CBJT矩陣及其諸如此類矩陣的實(shí)際應(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—），男，湖南邵陽(yáng)人，中南大學(xué)信息科學(xué)與工程學(xué)院博士研究生，主要研究領(lǐng)域?yàn)檎蛔儞Q，信號(hào)與圖像處理等。

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—），男，湖南長(zhǎng)沙人，中南大學(xué)信息科學(xué)與工程學(xué)院博士生導(dǎo)師，主要研究領(lǐng)域?yàn)樾盘?hào)與圖像處理，控制理論與應(yīng)用等。發(fā)表學(xué)術(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年于上海交通大學(xué)電子工程學(xué)院獲得博士學(xué)位，現(xiàn)為中南大學(xué)信息科學(xué)與工程學(xué)院博士生導(dǎo)師，主要研究領(lǐng)域?yàn)榱孔油ㄐ?，網(wǎng)絡(luò)安全等。發(fā)表學(xué)術(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

文獻(xiàn)標(biāo)志碼：A

中圖分類號(hào)：TP301

doi:10.3778/j.issn.1673-9418.1601008