基-4高維離散傅立葉變換PM向量編碼算法

徐 妍,楊齊琪,余 玲

(北京服裝學院 材料科學與工程學院，北京 100029)

?

基-4高維離散傅立葉變換PM向量編碼算法

徐 妍,楊齊琪,余 玲

(北京服裝學院 材料科學與工程學院，北京 100029)

離散傅立葉變換是數字信號處理中一種很重要的數學工具，它可以描述離散信號的時域與頻域的關系，在數字信號處理中有著重要的地位，應用十分廣泛[文獻1-3]。本文提出的基-4PM向量編碼算法是結合PM算法[文獻4]和向量編碼算法[文獻5-6]創造出的新算法。在采樣點數相同的情況下，與現行的幾種算法相比，該算法在計算量和運算時間上都有不同程度的降低，從而提高了運算效率。這在實際應用中具有重要的意義。

離散傅立葉變換;行列算法;PM算法;向量編碼算法;PM向量編碼算法

1 引言

高維離散Fourier變換 (DFT) 的一般形式為

(1)

對高維DFT的計算通常采用行列算法，即將m維DFT化為m個一維DFT計算：

X(a1，a2,…,am)

(2)

對每個一維DFT采用Cooley-Tukey的快速算法計算。行列算法是目前最為常用的計算高維DFT的算法，它的計算效率取決于一維DFT的計算效率。這種算法雖然程序結構較其他算法簡單，但就高維DFT變換的特點來說，算法的運算量還是可以進一步減少的。

本文討論的基-4 PM向量編碼算法，是將高維PM離散傅立葉變換的快速算法(Plus-Minus Fast Discrete Fourier Transform Algorithm)與向量編碼算法相結合，得到一種新的FFT算法，在采樣點數相同的情況下，能夠減少執行高維DFT的位碼倒序、同址運算和蝶形運算所消耗的時間，與現行的行列算法相比，計算的結構復雜度大大降低，減少了計算量，從而有效的提高了算法的運算效率。

2 高維PM向量編碼算法

為了使問題簡化，假定各維的采樣點數相同，即N1=N2=…=Nm=N，則(1)式可表示為：

X(a1，a2,…,am)

(3)

X(a1，a2,…,am)

(4)

∴(4)式可寫作：

X(a1,a2,…,am)

(5)

在(5)式中，將：

設a(b1,b2,…,bm)

(6)

對每一個整數序列(b1,b2,…,m)，該和式可看作是一個m維的u×u×…×u點DFT。在(6)式中，隨著ik(1,2,…,m)是不同取值，可得到不同的輸入序列，將全部輸出結果，記為向量形式：

a(b1,b2,…,bm)

={aq1q2…qm(b1,b2,…,bm):qk=0,1,…,u-1,

k=1,2,…,m}

(7)

可以看出

所以有：

aq1q2…qk…qm(b1,b2,…,bm)

=aq1q2…qk+u…qm(b1,b2,…,bm)

其中：

qk=akmodu

(qk=0,1,…,u-1,k=1,2,…,m)。

因此，將新的輸入向量代入到(5)式中，就有：

X(a1,a2,…,am)

會來的。一定會來的。信里講了會來，就一定會來。何牦深信無疑。他隨身帶了一張凳子，每天坐在街口等歐陽橘紅，怕她找不到竹溪街47號。

(8)

設q=q1,q2,…,qm，則(8)式可改寫為：

X(a1,a2,…,am)

(9)

(10)

∴ (10)式可寫作：

(11)

對應輸入向量aq(b1,b2,…,bm)，記輸出向量為Ap(b1,b2,…,bm)，則輸出向量為：

A(a1,a2,…,am)

={Aj1j2…jm(a1,a2,…,am)；jk=0,1,…,u-1,k=1,2,…,m}

(12)

則(11)式可被等價的表示為：

Ap(a1,a2,…,am)

(13)

(14)

類似地，可給出IDFT的定義式，這里就不再進行詳細的討論了。

3 基-4算法

γ(0)=(0,0,…,0,0)γ(1)=(0,0,…,0,1)

γ(2)=(0,0,…,0,2)γ(3)=(0,0,…,0,3)

γ(4)=(0,0,…,1,0)…

γ(4m-1)=(3,3,…,3,3)

例如：當m=2時，

(0,0),(0,1),(0,2),(0,3),

(1,0),(1,1),(1,2),(1,3),

(2,0),(2,1),(2,2),(2,3),

(3,0),(3,1),(3,2),(3,3),

共有4×4=16個基-4向量。

τ=40τ0+41τ1+42τ2+…+4n-1τn-1

(15)

例如：

17=40×1+41×0+42×1

42=40×2+41×2+42×2

則其展開式為：τ=(17,42)=40(1,2)+41(0,2)+42(1,2)

又如：

2=40×2+41×0+42×0

7=40×3+41×1+42×0

50=40×2+41×0+42×3

則其展開式為：τ=(2,7,50)=40(2,3,2)+41(0,1,0)+42(0,0,3)

稱(15)式為按基-4向量的編碼。

(16)

由(16)式，可將(14)式中的Ap(α)記為：

Ap(α)=Ap(α0,α1,…,αw-1)，

aq(β)=αp(β0,β1,…,βw-1)

(17)

將(16)式代入到(14)式中，由向量點積和數量乘法，則有：

(18)

對?k=0,1,…,w-1，∵u=2t且u的取值為能整除N的較小的整數， ∴w-1>t

(19)

∵4w+t=N

(20)

(21)

(22)

對?k=0,1,…,w-1

(23)

∵4t=u

(24)

因此，

(25)

由(21)、(25)式有：

(26)

將(26)式代入到(14)式中，則得到基-4高維DFT的PM向量編碼快速算法：

Ap(α)=Aq(α1,α1,…,αw-1)

(27)

當u=4即t=1時，(27)式可寫成：

Ap(α)=Ap(α1,α1,…,αw-1)

(28)

其中αq(β0,β1,…,βw-1)的計算由(6)式得到。即：

αq(β0,β1,…,βw-1)=αq(b0,b1,…,bm)

(29)

(28)式即為u=4(t=1)時的高維基-4PM向量編碼算法，(29)式為PM向量編碼算法的輸入向量，此輸入算法可由向量編碼算法得到。

[1]蔣增榮，曾泳泓，余品能 . 快速算法[M]. 北京：國防科技大學出版社，1998.

[2]DuraisamySundararajan，M.OmairAhmad，M.N.S.Swamy.VectorComputationoftheDiscreteFourierTransform，IEEETransactionsonCircuitsandSystems-Ⅱ:AnalogandDigitalSignalProcessing，1998，45(4)：449～461.

[3]陳兆斗，張志剛 . 高維離散Fourier變換的一種快速算法[J]. 自然科學進展，1999，9(9)：780～782.

[責任編輯：張懷濤]

2015-12-06

北京市科研訓練項目(編號：BKSP02150202/009)

徐妍,女，主要從事應用數學方面的研究。

O

A

1671-5330(2016)05-0066-05