Abstract

A multidimensional fast Fourier transform (FFT) algorithm is presented for signals with arbitrary symmetries and periodic on arbitrary lattices. Applications that can benefit from such an algorithm include Volterra filtering and analysis of x-ray diffraction data. The presented algorithm exploits signal redundancy to achieve a computational complexity of N log N, where N is the number of independent samples. To the authors’ knowledge, this is the only FFT that makes the frequency domain computation of Volterra filtering more convenient than the time domain approach.

© 1999 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. J. Cooley, J. W. Tukey, “An algorithm for the machine computation of the complex Fourier series,” Math. Comput. 19, 297–301 (1965).
    [CrossRef]
  2. G. Sicuranza, “Quadratic filters for signal processing,” Proc. IEEE 80, 1262–1285 (1992).
    [CrossRef]
  3. R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A fast convolution technique for Volterra filtering,” in Proceedings of the Workshop on Nonlinear Digital Signal Processing (Neos Marmaras, Halkidiki, Greece, 1995), pp. 363–366.
  4. V. Kucera, Discrete Linear Control: The Polynomial Equation (Wiley, New York, 1979).
  5. D. Dudgeon, R. Mersereau, Multidimensional Digital Signal Processing (Prentice-Hall, Englewood Cliffs, N.J., 1984).
  6. P. Vaidyanathan, Multirate Systems and Filter Banks (Prentice-Hall, Englewood Cliffs, N.J., 1993).
  7. N. Jacobson, Basic Algebra I (Freeman, New York, 1985).
  8. R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A new multidimensional FFT based on one-dimensional decompositions,” submitted to IEEE Trans. Circuits Syst. II.
  9. R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A new technique for twiddle-factors elimination in multidimensional FFT,” IEEE Trans. Signal Process. 42, 2176–2178 (1994).
    [CrossRef]

1994 (1)

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A new technique for twiddle-factors elimination in multidimensional FFT,” IEEE Trans. Signal Process. 42, 2176–2178 (1994).
[CrossRef]

1992 (1)

G. Sicuranza, “Quadratic filters for signal processing,” Proc. IEEE 80, 1262–1285 (1992).
[CrossRef]

1965 (1)

J. Cooley, J. W. Tukey, “An algorithm for the machine computation of the complex Fourier series,” Math. Comput. 19, 297–301 (1965).
[CrossRef]

Bernardini, R.

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A new technique for twiddle-factors elimination in multidimensional FFT,” IEEE Trans. Signal Process. 42, 2176–2178 (1994).
[CrossRef]

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A fast convolution technique for Volterra filtering,” in Proceedings of the Workshop on Nonlinear Digital Signal Processing (Neos Marmaras, Halkidiki, Greece, 1995), pp. 363–366.

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A new multidimensional FFT based on one-dimensional decompositions,” submitted to IEEE Trans. Circuits Syst. II.

Cooley, J.

J. Cooley, J. W. Tukey, “An algorithm for the machine computation of the complex Fourier series,” Math. Comput. 19, 297–301 (1965).
[CrossRef]

Cortelazzo, G. M.

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A new technique for twiddle-factors elimination in multidimensional FFT,” IEEE Trans. Signal Process. 42, 2176–2178 (1994).
[CrossRef]

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A fast convolution technique for Volterra filtering,” in Proceedings of the Workshop on Nonlinear Digital Signal Processing (Neos Marmaras, Halkidiki, Greece, 1995), pp. 363–366.

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A new multidimensional FFT based on one-dimensional decompositions,” submitted to IEEE Trans. Circuits Syst. II.

Dudgeon, D.

D. Dudgeon, R. Mersereau, Multidimensional Digital Signal Processing (Prentice-Hall, Englewood Cliffs, N.J., 1984).

Jacobson, N.

N. Jacobson, Basic Algebra I (Freeman, New York, 1985).

Kucera, V.

V. Kucera, Discrete Linear Control: The Polynomial Equation (Wiley, New York, 1979).

Mersereau, R.

D. Dudgeon, R. Mersereau, Multidimensional Digital Signal Processing (Prentice-Hall, Englewood Cliffs, N.J., 1984).

Mian, G. A.

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A new technique for twiddle-factors elimination in multidimensional FFT,” IEEE Trans. Signal Process. 42, 2176–2178 (1994).
[CrossRef]

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A fast convolution technique for Volterra filtering,” in Proceedings of the Workshop on Nonlinear Digital Signal Processing (Neos Marmaras, Halkidiki, Greece, 1995), pp. 363–366.

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A new multidimensional FFT based on one-dimensional decompositions,” submitted to IEEE Trans. Circuits Syst. II.

Sicuranza, G.

G. Sicuranza, “Quadratic filters for signal processing,” Proc. IEEE 80, 1262–1285 (1992).
[CrossRef]

Tukey, J. W.

J. Cooley, J. W. Tukey, “An algorithm for the machine computation of the complex Fourier series,” Math. Comput. 19, 297–301 (1965).
[CrossRef]

Vaidyanathan, P.

P. Vaidyanathan, Multirate Systems and Filter Banks (Prentice-Hall, Englewood Cliffs, N.J., 1993).

IEEE Trans. Signal Process. (1)

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A new technique for twiddle-factors elimination in multidimensional FFT,” IEEE Trans. Signal Process. 42, 2176–2178 (1994).
[CrossRef]

Math. Comput. (1)

J. Cooley, J. W. Tukey, “An algorithm for the machine computation of the complex Fourier series,” Math. Comput. 19, 297–301 (1965).
[CrossRef]

Proc. IEEE (1)

G. Sicuranza, “Quadratic filters for signal processing,” Proc. IEEE 80, 1262–1285 (1992).
[CrossRef]

Other (6)

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A fast convolution technique for Volterra filtering,” in Proceedings of the Workshop on Nonlinear Digital Signal Processing (Neos Marmaras, Halkidiki, Greece, 1995), pp. 363–366.

V. Kucera, Discrete Linear Control: The Polynomial Equation (Wiley, New York, 1979).

D. Dudgeon, R. Mersereau, Multidimensional Digital Signal Processing (Prentice-Hall, Englewood Cliffs, N.J., 1984).

P. Vaidyanathan, Multirate Systems and Filter Banks (Prentice-Hall, Englewood Cliffs, N.J., 1993).

N. Jacobson, Basic Algebra I (Freeman, New York, 1985).

R. Bernardini, G. M. Cortelazzo, G. A. Mian, “A new multidimensional FFT based on one-dimensional decompositions,” submitted to IEEE Trans. Circuits Syst. II.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (5)

Fig. 1
Fig. 1

Example of a two-dimensional lattice Λ. The points of Λ are displayed with large black circles, the points of Z2 are displayed with small black circles, and two vectors making a basis for Λ are shown as arrows.

Fig. 2
Fig. 2

By applying to (a) a one-dimensional signal of period 8 a butterfly of width 4, one obtains (b) a one-dimensional signal of period 4 and (c) a weighted-periodic signal of period 4.

Fig. 3
Fig. 3

Frequency view of the signal decomposition shown in Fig. 2: the periodic signal of period 4 is equal to zero for odd frequencies (a), while the weighted-periodic signal is equal to zero for even frequencies (b).

Fig. 4
Fig. 4

Example of URG decomposition. (a) Two-dimensional signal, periodic on (2ν, 2ν), where ν is an integer. If the signal in (a) is processed with a horizontal butterfly, one obtains the two output signals shown in (b) and (c). The former is periodic, while the latter is weighted periodic. By applying a vertical butterfly to signals (b) and (c), one obtains the signals shown in (d)–(g).

Fig. 5
Fig. 5

The signal in (a) is symmetric with respect to a group {γ0=I,γ1,γ2} of order 3, where I is the identity element. Let r be a reduction vector. If one reduces the signal in (a) with a butterfly along r, one obtains the signals shown in (b) and (c). By reducing such signals with a butterfly along γ1r, one obtains the signals shown in (d)–(g). On such signals it is impossible to use a butterfly along γ2r because γ2r belongs to the periodicity lattice and it is not a reduction vector anymore.

Tables (5)

Tables Icon

Algorithm 1 (X)=Symm_FFT(x, N, w, p, Γ)

Tables Icon

Algorithm 2 (H)=Normal_Form(N, w)

Tables Icon

Table 1 Comparison between the Computational Complexity of the Proposed Algorithm (CS) and the Computational Complexity of the Mersereau FFT (CVR) and the Row–Column FFT (CRC) (M=2)

Tables Icon

Table 2 Same as Table 1 but for M=3

Tables Icon

Table 3 Same as Table 1 but for M=4

Equations (169)

Equations on this page are rendered with MathJax. Learn more.

Λ(n1,, nL)m:m=i=1Lniai, ai  Z.
v1=63,v2=06.
Λ(N)  {m: m=Na, aZL}.
Λ(n1,, nL)=Λ(t1, , tM).
N=N1H,
x(n)=x(n+Nk)
x(n)=x(n+Nm)mZM.
n=m+Nk,kZM.
X(f)  nINx(n)exp(-j2πftN-1n),fZM,
fSxX(f)=0.
x+(n)=x(n)+x(n+N/2),
x-(n)=x(n)-x(n+N/2),
x(n+L)=sx(n)
Sx+={0, 2,, N-2},
Sx-={1, 3,, N-1},
x(n)=12 [x+(n)+x-(n)],
x(n+m0)=sx(n)
x(n+km0)=skx(n)kZ.
x(n+pm0)=exp[-j2πp(w/p)]x(n)=x(n),
x(n+k0m0+k1m1)
=exp(-j2πw0k0/p)x(n+k1m1)=exp(-j2πw0k0/p)exp(-j2πw1k1/p)x(n)=exp[-j2π(w0k0+w1k1)/p]x(n).
expp(α)  exp(-j2πα/p)
x(n+[m0, m1]k)=expp(wtk)x(n).
x(n+Nk)=expp(wtk)x(n)n, kZM.
WPp(N, w)=WPp(NH, Htw).
expp(wtN-1m)=expp[(Htw)t(NH)-1m].
WPp(N, w)=WPp(N1, w1),
w1=(w1, 0,, 0)t,
Λ(N˜1)Λ(N˜).
Sx=w+Λ(N˜t).
y(n)  x(n)exp(-j2πwtN-1np)
y(n+Nm)=x(n+Nm)exp[-j2πwtN-1(Nm+n)/p]=x(n)exp(-j2πwtm)exp(-j2πwtm/p)exp(-j2πwtN-1n)=y(n).
prΛ(N),
rΛ(N),
expp[wtN-1(pr)]=1.
x(n+pr)=expp[wtN-1(pr)]x(n)=x(n),
x+(n)=x(n)+x(n+r),
x-(n)=x(n)-x(n+r),
2(0, 2ν-1)tΛ(diag(2ν, 2ν)),
(0, 2ν-1)tΛ(diag(2ν, 2ν)),
exp22(0 0)1/2ν001/2ν02ν-1=1.
exp22(0 1)1/2ν001/2ν-102ν-2=exp2(1)=-1
x(n1, n2)=x(n1, -n2),
x(n1, n2)=x(-n1, -n2),
x(n1, n2)=x(n2, n1),
x(n1, n2)=x(n2, -n1).
x(n)=x(γn),
γ=100-1,γ=-100-1,
γ=0110,γ=01-10.
x(γ1γ2n)=x(γ1n)=x(n),
x(γn)=x(n)
Γn  {m: m=γn, γΓ}.
n1n2γΓ: n1=γn2
x(γ-1n+Nm)=x(γ-1n)(periodicity)=x(n)(symmetry),
x(γ-1n+Nm)=x(γ(γ-1n+Nm))(symmetry),=x(n+γNm).
x(n)=x(n+γNm),
x(n)=x(n+Nm1+kγNm),m1ZM, kZ,
γN1mΛ(N1).
γNmΛ(N),NmΛ(N), γΓ,
γˆ  N-1γN
γIN  {m: m=γn, nIN}
x(γ(n+Nm))
=x(n+Nm)(symmetry)=expp(wtm)x(n)(weightedperiodicity),
x(γ(n+Nm))
=x(γn+γNm)=expp(wtN-1γNm)x(γn)(weightedperiodicity)
=expp(wtN-1γNm)x(n)(symmetry).
expp(wtm)x(n)=expp(wtN-1γNm)x(n).
wt=wtN-1γN(mod p)
expp(wtm)=expp(wtN-1γNm)mZM.
expp[wtN-1(2γr)]=expp[wt(N-1γN)N-1(2r)]=expp[wtN-1(2r)]=1,
Y(f)=X((N-1γN)tf).
Y(f)=nINy(n)exp(-j2πftN-1n)=nINx(γn)exp(-j2πftN-1n)=mγINx(m)exp(-j2πftN-1γ-1m)=mγINx(m)exp[-j2πft(N-1γ-1N)N-1m]=X((N-1γ-1N)tf)=X(γ*f).
Γr  {s: s=γr, γΓ}.
Γ  γ0=1001,γ1=-21-31,
γ2=1-13-2.
γ12=γ2,γ13=γ0.
8008-1-21-31 8008=-21-31Z22.
r1  γ1r=-8-12,r2  γ2r=412.
r0+r1+8008-10=40+-8-12+80=412=r2.
r0=i=1Lαiri+n0
r0-i=1Lαiri=n0Λ(N).
rn=i=1Lαiri+m0.
|B1| = |B2|,
ri=Nm+k=1i-1αkrk.
x0(n)=x(n)+(-1)0x(n+r1),
x1(n)=x(n)+(-1)1x(n+r1).
xi(n)=x(n)+(-1)ix(n+r1),i=0, 1.
x00(n)=x0(n)+(-1)0x0(n+r2),
x01(n)=x0(n)+(-1)1x0(n+r2).
x10(n)=x1(n)+(-1)0x1(n+r2),
x11(n)=x1(n)+(-1)1x1(n+r2).
x00(n)=x(n)+(-1)0x(n+r1)+(-1)0x(n+r2)+(-1)0(-1)0x(n+r1+r2),
x01(n)=x(n)+(-1)0x(n+r1)+(-1)1x(n+r2)+(-1)0(-1)1x(n+r1+r2),
x10(n)=x(n)+(-1)1x(n+r1)+(-1)0x(n+r2)+(-1)1(-1)0x(n+r1+r2),
x11(n)=x(n)+(-1)1x(n+r1)+(-1)1x(n+r2)+(-1)1(-1)1x(n+r1+r2).
xij(n)=x(n)+(-1)ix(n+r1)+(-1)jx(n+r2)+(-1)i(-1)jx(n+r1+r2),i, j=0, 1,
xij(n)=s=01t=01(-1)si+tjx(n+sr1+tr2)
xi(n)=s{0,1}2(-1)itsx(n+Ms),
xi(n)=s{0,1}L(-1)itsx(n+Ms),i{0, 1}L,
xj(n)=xi(γn).
j=γ¯i(mod 2),
xi(n)=k=0p-1 exp-j2π kipx(n+kr),
xi(n)=s{0,1}L exp-j2π itspx(n+Ms),
i{0,, p-1}L.
j=γ¯i(mod p),
N1  P00Q,
x+((n1, n2)t)  x(n1).
N+=N00I.
x2((n1, n2)t)  x+(H(n1, n2)t),
N1=HN00IK,
|det(P)| =q1,|det(Q)| =q2.
Nl=P1P2Pl,
N2=P00Q,
x2((n1, n2)t)=x2((ϕP(γ)n1, ϕQ(γ)n2)t).
ΓP  ϕP(Γ)={γP: γP=ϕP(γ), γΓ},
ΓQ  ϕQ(Γ)={γQ: γQ=ϕQ(γ), γΓ}
xn2(n1)=xγQn2(γPn1).
ϕP(Γˆ)={γP: γP=ϕP(γ), γΓ, ϕQ(γ)Stab(n2)}
Xn2(f1)=XγQn2(γP*f1).
Xf1(n2)=XγP*f1(γQn2).
(p-1)|det(N)|/|Γ|
logp[|det(N)|/|Γ|]
C(N, Γ)(p-1)|det(N)|/|Γ|logp[|det(N)|/|Γ|].
(p-1)|det(N)|logp[|det(N)|].
L+NhNhNhNhL-Nh0L0-N1L00-Nh.
p(r1+r2)=pr1+pr2Λ(N).
expp[wtN-1(pr1+pr2)]=expp[wtN-1(pr1)]×expp[wtN-1(pr2)]=1.
r1-r2Λ(N)
r1-r2=Nm,mZM.
r0-i=1Lαiri=0[mod Λ(N)].
prΛ(N),
pr=0[mod Λ(N)].
pq+ij=1
ij=1(modp).
(i+Zp)[r+Λ(N)]  (ir)+Λ(N).
(i+pk+Zp)[r+Nm+Λ(N)]=ir+pkr+(Zp)r+N(im)+N(pkm)+(Zp)Nm+iΛ(N)+pkΛ(N)+(Zp)Λ(N).
γ¯(r+Λ(N))  (γr)+Λ(N),
γ¯(r+Λ(N))=(γr)+γNm+Λ(N)=(γr)+Λ(N).
v+Λ(N)=γΓγrαγ+Λ(N),
γ¯1(v+Λ(N))=γΓγ1γrαγ+Λ(N).
αw1[1]=w1[k](mod p).
N1=N diag(p, 1, , 1).
m=N1n=Np11n1n2nM=Npn1n2nM.
x(n+N1n)=expp(w00)pn1n2nMx(n),=expp(pwn1)x(n)=x(n),
Λ(N)Λ(N2)Λ(N1)
k-m0=k-γn0Λ(N).
k-γn0Λ(N)n0IN.
k1-n0Λ(N)n0IN,
k-γn1Λ(N),k-γn2Λ(N),
n1n2,n1, n2IN.
k1-n1Λ(N),k1-n2Λ(N),
n1n2,n1, n2IN,
f(n)  Hn.
fˆ(n+Λ(diag(N, I)))  f(n)+Λ(diag(P, Q)).
x2((n1, n2)t)=x(f-1(n1, n2)t),
x2([n1,n2]t)=x(f-1(n1, n2)t)[byEq.(B13)] =x(γf-1(n1, n2)t)(bysymmetry) =x2(fγf-1(n1, n2)t)[byEq.(B13)],
fΓf-1={γˆ:γˆ=fγf-1, γΓ}.
γˆn10=γPn10.
γˆn1n2=γˆn10+0n2=γˆn10+γˆ0n2=γPn10+0γQn2=γPn1γQn2.
αn10=0[mod Λ(diag(P, Q))].
γˆαn10=αγˆn10=0[mod Λ(diag(P, Q))].
γˆn10=m1m2
αm1m2=αm1αm2=00,
γˆ0n2=0γQγn2.
γP=ϕP(γ)  θP-1fγf-1θP.
θP-1fγ-1f-1θP=γP-1,
θP-1f(γ1γ2)-1f-1θP=γP,1γP,2.
θP-1fγ-1f-1θPγP=θP-1fγ-1f-1θPθP-1fγf-1θP=θP-1fγ-1γf-1θP=I,
ϕP(ϕQ-1(Stab(n2))),

Metrics