Tables for
Volume B
Reciprocal space
Edited by U. Shmueli

International Tables for Crystallography (2010). Vol. B, ch. 1.3, pp. 51-52   | 1 | 2 |

Section Properties of the discrete Fourier transform

G. Bricognea

aGlobal Phasing Ltd, Sheraton House, Suites 14–16, Castle Park, Cambridge CB3 0AX, England, and LURE, Bâtiment 209D, Université Paris-Sud, 91405 Orsay, France 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 constr­ucted from [\varphi^{0} \in {\scr E}({\bb R}^{n})] as in Section[link], 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[link]); their eigenvalues are therefore [\pm 1] and [\pm i].

to end of page
to top of page