Properties of the discrete Fourier transform

Bricogne, G.

doi:10.1107/97809553602060000551

International
Tables for
Crystallography
Volume B
Reciprocal space
Edited by U. Shmueli

pdf | chapter contents | chapter index | related articles

International Tables for Crystallography (2006). Vol. B. ch. 1.3, p. 49 | 1 | 2 |

Section 1.3.2.7.5. Properties of the discrete Fourier transform

G. Bricogne^a

^a MRC Laboratory of Molecular Biology, Hills Road, Cambridge CB2 2QH, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France

1.3.2.7.5. Properties of the discrete Fourier transform

| top | pdf |

The DFT inherits most of the properties of the Fourier transforms, but with certain numerical factors (`Jacobians') due to the transition from continuous to discrete measure.

(1) Linearity is obvious.
(2) Shift property. If $[(\tau_{{\bf {\scr a}}} \psi) ({\scr k}) = \psi ({\scr k} - {\bf {\scr a}})]$ and $[(\tau_{{\bf {\scr a}}^{*}} \Psi) ({\scr k}^{*}) =]$ $[\Psi ({\scr k}^{*} - {\bf {\scr a}}^{*})]$ , where subtraction takes place by modular vector arithmetic in $[{\bb Z}^{n}/{\bf N} {\bb Z}^{n}]$ and $[{\bb Z}^{n}/{\bf N}^{T}{\bb Z}^{n}]$ , respectively, then the following identities hold: $[\eqalign{\bar{\scr F}({\bf N}) [\tau_{\bf \scr k} \psi] ({\bf \scr k}^{*}) &= \exp [+ 2 \pi i{\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})] \bar{\scr F}({\bf N})[\psi]({\bf \scr k}^{*}) \cr {\scr F}({\bf N})[\tau_{{\bf \scr k}^{*}} \Psi]({\bf \scr k}) &= \exp [- 2 \pi i{\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})] {\scr F}({\bf N})[\Psi]({\bf \scr k}).}]$
(3) Differentiation identities. Let vectors ψ and Ψ be constructed from $[\varphi^{0} \in {\scr E}({\bb R}^{n})]$ as in Section 1.3.2.7.3, hence be related by the DFT. If $[D^{{\bf p}} \boldpsi]$ designates the vector of sample values of $[D_{\bf x}^{{\bf p}} \varphi^{0}]$ at the points of $[\Lambda_{\bf B}/\Lambda_{\bf A}]$ , and $[D^{{\bf p}} \boldPsi]$ the vector of values of $[D_{\boldxi}^{{\bf p}} \Phi^{0}]$ at points of $[\Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}]$ , then for all multi-indices $[{\bf p} = (p_{1}, p_{2}, \ldots, p_{n})]$ $[\eqalign{(D^{{\bf p}} \boldpsi) ({\bf \scr k}) &= \bar{\scr F}({\bf N}) [(+ 2 \pi i{\bf \scr k}^{*})^{{\bf p}} \boldPsi] ({\bf \scr k}) \cr (D^{{\bf p}} \boldPsi) ({\bf \scr k}^{*}) &= {\scr F}({\bf N}) [(- 2 \pi i{\bf \scr k})^{{\bf p}} \boldpsi] ({\bf \scr k}^{*})}]$ or equivalently $[\eqalign{{\scr F}({\bf N}) [D^{{\bf p}} \boldpsi] ({\bf \scr k}^{*}) &= (+ 2 \pi i{\bf \scr k}^{*})^{{\bf p}} \boldPsi ({\bf \scr k}^{*}) \cr \bar{\scr F}({\bf N}) [D^{{\bf p}} \boldPsi] ({\bf \scr k}) &= (- 2 \pi i{\bf \scr k})^{{\bf p}} \boldpsi ({\bf \scr k}).}]$
(4) Convolution property. Let $[\boldvarphi \in W_{\bf N}]$ and $[\boldPhi \in W_{\bf N}^{*}]$ (respectively ψ and Ψ) be related by the DFT, and define $[\eqalign{(\boldvarphi * \boldpsi) ({\bf \scr k}) &= \textstyle\sum\limits_{{\bf \scr k}' \in {\bb Z}^{n}/{\bf N} {\bb Z}^{n}} \boldvarphi ({\bf \scr k}') \boldpsi ({\bf \scr k} - {\bf \scr k}') \cr (\boldPhi * \boldPsi) ({\bf \scr k}^{*}) &= \textstyle\sum\limits_{{\bf \scr k}^{*'} \in {\bb Z}^{n}/{\bf N}^{T} {\bb Z}^{n}} \boldPhi ({\bf \scr k}^{*'}) {\boldPsi} ({\bf \scr k}^{*} - {\bf \scr k}^{*'}).}]$ Then $[\eqalign{\bar{\scr F}({\bf N}) [\boldPhi * \boldPsi] ({\bf \scr k}) &= |\det {\bf N}| \boldvarphi ({\bf \scr k}) \boldpsi ({\bf \scr k}) \cr {\scr F}({\bf N}) [\boldvarphi * \boldpsi] ({\bf \scr k}^{*}) &= \boldPhi ({\bf \scr k}^{*}) \boldPsi ({\bf \scr k}^{*})}]$ and $[\eqalign{\bar{\scr F}({\bf N}) [\boldvarphi \times \boldpsi] ({\bf \scr k}^{*}) &= {1 \over |\det {\bf N}|} (\boldPhi * \boldPsi) ({\bf \scr k}^{*}) \cr {\scr F}({\bf N}) [\boldPhi \times \boldPsi] ({\bf \scr k}) &= (\boldvarphi * \boldpsi) ({\bf \scr k}).}]$ Since addition on $[{\bb Z}^{n}/{\bf N}{\bb Z}^{n}]$ and $[{\bb Z}^{n}/{\bf N}^{T} {\bb Z}^{n}]$ is modular, this type of convolution is called cyclic convolution .
(5) Parseval/Plancherel property. If φ, ψ, Φ, Ψ are as above, then $[\eqalign{({\scr F}({\bf N}) [\boldPhi], {\scr F}({\bf N}) [\boldPsi])_{W} &= {1 \over |\det {\bf N}|} (\boldPhi, \boldPsi)_{W^{*}} \cr (\bar{\scr F}({\bf N}) [\boldvarphi], \bar{\scr F}({\bf N}) [\boldpsi])_{W} &= {1 \over |\det {\bf N}|} (\boldvarphi, \boldpsi)_{W}.}]$
(6) Period 4. When N is symmetric, so that the ranges of indices $[{\scr k}]$ and $[{\scr k}^{*}]$ can be identified, it makes sense to speak of powers of $[{\scr F}({\bf N})]$ and $[\bar{\scr F}({\bf N})]$ . Then the `standardized' matrices $[(1/|\det {\bf N}|^{1/2}){\scr F}({\bf N})]$ and $[(1/|\det {\bf N}|^{1/2}) \bar{\scr F}({\bf N})]$ are unitary matrices whose fourth power is the identity matrix (Section 1.3.2.4.3.4); their eigenvalues are therefore $[\pm 1]$ and $[\pm i]$ .