The discrete Fourier transformation

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, pp. 45-49 | 1 | 2 |

Section 1.3.2.7. The discrete Fourier transformation

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. The discrete Fourier transformation

| top | pdf |

1.3.2.7.1. Shannon's sampling theorem and interpolation formula

| top | pdf |

Let $[\varphi \in {\scr E} ({\bb R}^{n})]$ be such that $[\Phi = {\scr F}[\varphi]]$ has compact support K. Let φ be sampled at the nodes of a lattice $[\Lambda^{*}]$ , yielding the lattice distribution $[R^{*} \times \varphi]$ . The Fourier transform of this sampled version of φ is $[{\scr F}[R^{*} \times \varphi] = | \det {\bf A}| (R * \Phi),]$ which is essentially Φ periodized by period lattice $[\Lambda = (\Lambda^{*})^{*}]$ , with period matrix A.

Let us assume that Λ is such that the translates of K by different period vectors of Λ are disjoint. Then we may recover Φ from $[R * \Phi]$ by masking the contents of a `unit cell' $[{\scr V}]$ of Λ (i.e. a fundamental domain for the action of Λ in $[{\bb R}^{n}]$ ) whose boundary does not meet K. If $[\chi _{\scr V}]$ is the indicator function of $[{\scr V}]$ , then $[\Phi = \chi_{\scr V}\times (R * \Phi).]$ Transforming both sides by $[\bar{\scr F}]$ yields $[\varphi = \bar{\scr F}\left[\chi_{\scr V}\times {1 \over |\det {\bf A}|} {\scr F}[R^{*} \times \varphi]\right],]$ i.e. $[\varphi = \left({1 \over V} \bar{\scr F}[\chi_{\scr V}]\right) * (R^{*} \times \varphi)]$ since $[|\det {\bf A}|]$ is the volume V of $[{\scr V}]$ .

This interpolation formula is traditionally credited to Shannon (1949), although it was discovered much earlier by Whittaker (1915). It shows that φ may be recovered from its sample values on $[\Lambda^{*}]$ (i.e. from $[R^{*} \times \varphi]$ ) provided $[\Lambda^{*}]$ is sufficiently fine that no overlap (or `aliasing') occurs in the periodization of Φ by the dual lattice Λ. The interpolation kernel is the transform of the normalized indicator function of a unit cell of Λ containing the support K of Φ.

If K is contained in a sphere of radius $[1/\Delta]$ and if Λ and $[\Lambda^{*}]$ are rectangular, the length of each basis vector of Λ must be greater than $[2/\Delta]$ , and thus the sampling interval must be smaller than $[\Delta /2]$ . This requirement constitutes the Shannon sampling criterion.

1.3.2.7.2. Duality between subdivision and decimation of period lattices

| top | pdf |

1.3.2.7.2.1. Geometric description of sublattices

| top | pdf |

Let $[\Lambda_{\bf A}]$ be a period lattice in $[{\bb R}^{n}]$ with matrix A, and let $[\Lambda_{\bf A}^{*}]$ be the lattice reciprocal to $[\Lambda_{\bf A}]$ , with period matrix $[(A^{-1})^{T}]$ . Let $[\Lambda_{\bf B}, {\bf B}, \Lambda_{\bf B}^{*}]$ be defined similarly, and let us suppose that $[\Lambda_{\bf A}]$ is a sublattice of $[\Lambda_{\bf B}]$ , i.e. that $[\Lambda_{\bf B} \supset \Lambda_{\bf A}]$ as a set.

The relation between $[\Lambda_{\bf A}]$ and $[\Lambda_{\bf B}]$ may be described in two different fashions: (i) multiplicatively, and (ii) additively.

(i) We may write $[{\bf A} = {\bf BN}]$ for some non-singular matrix N with integer entries. N may be viewed as the period matrix of the coarser lattice $[\Lambda_{\bf A}]$ with respect to the period basis of the finer lattice $[\Lambda_{\bf B}]$ . It will be more convenient to write $[{\bf A} = {\bf DB}]$ , where $[{\bf D} = {\bf BNB}^{-1}]$ is a rational matrix (with integer determinant since det $[{\bf D} = \det {\bf N}]$ ) in terms of which the two lattices are related by $[\Lambda_{\bf A} = {\bf D} \Lambda_{\bf B}.]$
(ii) Call two vectors in $[\Lambda_{\bf B}]$ congruent modulo $[\Lambda_{\bf A}]$ if their difference lies in $[\Lambda_{\bf A}]$ . Denote the set of congruence classes (or `cosets') by $[\Lambda_{\bf B} / \Lambda_{\bf A}]$ , and the number of these classes by $[[\Lambda_{\bf B} : \Lambda_{\bf A}]]$ . The `coset decomposition' $[\Lambda_{\bf B} = \bigcup_{{\boldell} \in \Lambda_{\bf B} / \Lambda_{\bf A}} ({\boldell} + \Lambda_{\bf A})]$ represents $[\Lambda_{\bf B}]$ as the disjoint union of $[[\Lambda_{\bf B} : \Lambda_{\bf A}]]$ translates of $[\Lambda_{\bf A} .\; \Lambda_{\bf B} / \Lambda_{\bf A}]$ is a finite lattice with $[[\Lambda_{\bf B} : \Lambda_{\bf A}]]$ elements, called the residual lattice of $[\Lambda_{\bf B}]$ modulo $[\Lambda_{\bf A}]$ .

The two descriptions are connected by the relation $[[\Lambda_{\bf B} : \Lambda_{\bf A}] = \det {\bf D} = \det {\bf N}]$ , which follows from a volume calculation. We may also combine (i) and (ii) into
$[\displaylines{\quad({\rm iii})\hfill \Lambda_{\bf B} = \bigcup_{{\boldell} \in \Lambda_{\bf B} / \Lambda_{\bf A}} ({\boldell} + {\bf D} \Lambda_{\bf B})\hfill}]$ which may be viewed as the n-dimensional equivalent of the Euclidean algorithm for integer division: $[\boldell]$ is the `remainder' of the division by $[\Lambda_{\bf A}]$ of a vector in $[\Lambda_{\bf B}]$ , the quotient being the matrix D.

1.3.2.7.2.2. Sublattice relations for reciprocal lattices

| top | pdf |

Let us now consider the two reciprocal lattices $[\Lambda_{\bf A}^{*}]$ and $[\Lambda_{\bf B}^{*}]$ . Their period matrices $[({\bf A}^{-1})^{T}]$ and $[({\bf B}^{-1})^{T}]$ are related by: $[({\bf B}^{-1})^{T} = ({\bf A}^{-1})^{T} {\bf N}^{T}]$ , where $[{\bf N}^{T}]$ is an integer matrix; or equivalently by $[({\bf B}^{-1})^{T} = {\bf D}^{T} ({\bf A}^{-1})^{T}]$ . This shows that the roles are reversed in that $[\Lambda_{\bf B}^{*}]$ is a sublattice of $[\Lambda_{\bf A}^{*}]$ , which we may write:

$[\displaylines{\quad({\rm i})^*\hfill \Lambda_{\bf B}^{*} = {\bf D}^{T} \Lambda_{\bf A}^{*}\hfill}]$
$[\displaylines{\quad({\rm ii})^*\hfill\Lambda_{\bf A}^{*} = \bigcup_{{\boldell}^{*} \in \Lambda_{\bf A}^{*} / \Lambda_{\bf B}^{*}} ({\boldell}^{*} + \Lambda_{\bf B}^{*}).\hfill}]$ The residual lattice $[\Lambda_{\bf A}^{*} / \Lambda_{\bf B}^{*}]$ is finite, with $[[\Lambda_{\bf A}^{*}: \Lambda_{\bf B}^{*}] =]$ $[ \det {\bf D} = \det {\bf N} = [\Lambda_{\bf B}: \Lambda_{\bf A}]]$ , and we may again combine $[(\hbox{i})^{*}]$ and $[(\hbox{ii})^{*}]$ into
$[\displaylines{\quad({\rm iii})^*\hfill\Lambda_{\bf A}^{*} = \bigcup_{{\boldell}^{*} \in \Lambda_{\bf A}^{*} / \Lambda_{\bf B}^{*}} ({\boldell}^{*} + {\bf D}^{T} \Lambda_{\bf A}^{*}).\hfill}]$

1.3.2.7.2.3. Relation between lattice distributions

| top | pdf |

The above relations between lattices may be rewritten in terms of the corresponding lattice distributions as follows: $[\displaylines{\quad (\hbox{i}) \hfill R_{\bf A} = {1 \over |\det {\bf D}|} {\bf D}^{\#} R_{\bf B}^{*} \;\hfill\cr \quad (\hbox{ii}) \hfill R_{\bf B} = T_{{\bf B} / {\bf A}} * R_{\bf A}\qquad \hfill\cr \quad (\hbox{i})^{*} \hfill \;\;R_{\bf B}^{*} = {1 \over |\det {\bf D}|} ({\bf D}^{T})^{\#} R_{\bf A}^{*} \hfill\cr \quad (\hbox{ii})^{*} \hfill R_{\bf A}^{*} =T_{{\bf A} / {\bf B}}^{*} * R_{\bf B}^{*} \qquad\;\;\hfill}]$ where $[T_{{\bf B} / {\bf A}} = {\textstyle\sum\limits_{{\boldell} \in \Lambda_{\bf B} / \Lambda_{\bf A}}} \delta_{({\boldell})}]$ and $[T_{{\bf A}/{\bf B}}^{*} = {\textstyle\sum\limits_{{\boldell}^{*} \in \Lambda_{\bf A}^{*} / \Lambda_{\bf B}^{*}}} \delta_{({\boldell}^{*})}]$ are (finite) residual-lattice distributions. We may incorporate the factor $[1/|\det {\bf D}|]$ in (i) and $[(\hbox{i})^{*}]$ into these distributions and define $[S_{{\bf B}/{\bf A}} = {1 \over |\det {\bf D}|} T_{{\bf B}/{\bf A}},\quad S_{{\bf A}/{\bf B}}^{*} = {1 \over |\det {\bf D}|} T_{{\bf A}/{\bf B}}^{*}.]$

Since $[|\det {\bf D}| = [\Lambda_{\bf B}: \Lambda_{\bf A}] = [\Lambda_{\bf A}^{*}: \Lambda_{\bf B}^{*}]]$ , convolution with $[S_{{\bf B}/{\bf A}}]$ and $[S_{{\bf A}/{\bf B}}^{*}]$ has the effect of averaging the translates of a distribution under the elements (or `cosets') of the residual lattices $[\Lambda_{\bf B}/\Lambda_{\bf A}]$ and $[\Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}]$ , respectively. This process will be called `coset averaging'. Eliminating $[R_{\bf A}]$ and $[R_{\bf B}]$ between (i) and (ii), and $[R_{\bf A}^{*}]$ and $[R_{\bf B}^{*}]$ between $[(\hbox{i})^{*}]$ and $[(\hbox{ii})^{*}]$ , we may write: $[\displaylines{\quad (\hbox{i}')\hfill \! R_{\bf A} = {\bf D}^{\#} (S_{{\bf B}/{\bf A}} * R_{\bf A})\;\;\;\hfill\cr \quad (\hbox{ii}')\hfill \! R_{\bf B} = S_{{\bf B}/{\bf A}} * ({\bf D}^{\#} R_{\bf B})\;\;\;\;\hfill\cr \quad (\hbox{i}')^{*}\hfill R_{\bf B}^{*} = ({\bf D}^{T})^{\#} (S_{{\bf A}/{\bf B}}^{*} * R_{\bf B}^{*}) \hfill\cr \quad (\hbox{ii}')^{*}\hfill R_{\bf A}^{*} = S_{{\bf A}/{\bf B}}^{*} * [({\bf D}^{T})^{\#} R_{\bf A}^{*}]. \;\hfill}]$ These identities show that period subdivision by convolution with $[S_{{\bf B}/{\bf A}}]$ (respectively $[S_{{\bf A}/{\bf B}}^{*}]$ ) on the one hand, and period decimation by `dilation' by $[{\bf D}^{\#}]$ on the other hand, are mutually inverse operations on $[R_{\bf A}]$ and $[R_{\bf B}]$ (respectively $[R_{\bf A}^{*}]$ and $[R_{\bf B}^{*}]$ ).

1.3.2.7.2.4. Relation between Fourier transforms

| top | pdf |

Finally, let us consider the relations between the Fourier transforms of these lattice distributions. Recalling the basic relation of Section 1.3.2.6.5, $[\eqalign{{\scr F}[R_{\bf A}] &= {1 \over |\det {\bf A}|} R_{\bf A}^{*}\cr &= {1 \over |\det {\bf DB}|} T_{{\bf A}/{\bf B}}^{*} * R_{\bf B}^{*} \quad \quad \quad \quad \quad \quad \hbox{by (ii)}^{*}\cr &= \left({1 \over |\det {\bf D}|} T_{{\bf A}/{\bf B}}^{*}\right) * \left({1 \over |\det {\bf B}|} R_{\bf B}^{*}\right)}]$ i.e. $[\displaylines{\quad (\hbox{iv})\hfill {\scr F}[R_{\bf A}] = S_{{\bf A}/{\bf B}}^{*} * {\scr F}[R_{\bf B}]\hfill}]$ and similarly: $[\displaylines{\quad (\hbox{v})\hfill {\scr F}[R_{\bf B}^{*}] = S_{{\bf B}/{\bf A}} * {\scr F}[R_{\bf A}^{*}].\hfill}]$

Thus $[R_{\bf A}]$ (respectively $[R_{\bf B}^{*}]$ ), a decimated version of $[R_{\bf B}]$ (respectively $[R_{\bf A}^{*}]$ ), is transformed by $[{\scr F}]$ into a subdivided version of $[{\scr F}[R_{\bf B}]]$ (respectively $[{\scr F}[R_{\bf A}^{*}]]$ ).

The converse is also true: $[\eqalign{{\scr F}[R_{\bf B}] &= {1 \over |\det {\bf B}|} R_{\bf B}^{*}\cr &= {1 \over |\det {\bf B}|} {1 \over |\det {\bf D}|} ({\bf D}^{T})^{\#} R_{\bf A}^{*}\quad \quad \quad \quad \hbox{by (i)}^{*}\cr &= ({\bf D}^{T})^{\#} \left({1 \over |\det {\bf A}|} R_{\bf A}^{*}\right)}]$ i.e. $[\displaylines{\quad (\hbox{iv}')\hfill {\scr F}[R_{\bf B}] = ({\bf D}^{T})^{\#} {\scr F}[R_{\bf A}]\hfill}]$ and similarly $[\displaylines{\quad (\hbox{v}')\hfill {\scr F}[R_{\bf A}^{*}] = {\bf D}^{\#} {\scr F}[R_{\bf B}^{*}].\hfill}]$

Thus $[R_{\bf B}]$ (respectively $[R_{\bf A}^{*}]$ ), a subdivided version of $[R_{\bf A}]$ (respectively $[R_{\bf B}^{*}]$ ) is transformed by $[{\scr F}]$ into a decimated version of $[{\scr F}[R_{\bf A}]]$ (respectively $[{\scr F}[R_{\bf B}^{*}]]$ ). Therefore, the Fourier transform exchanges subdivision and decimation of period lattices for lattice distributions.

Further insight into this phenomenon is provided by applying $[\bar{\scr F}]$ to both sides of (iv) and (v) and invoking the convolution theorem: $[\displaylines{\quad (\hbox{iv}'')\hfill \!\! R_{\bf A} = \bar{\scr F}[S_{{\bf A}/{\bf B}}^{*}] \times R_{\bf B} \;\hfill\cr \quad (\hbox{v}'')\hfill R_{\bf B}^{*} = \bar{\scr F}[S_{{\bf B}/{\bf A}}] \times R_{\bf A}^{*}. \hfill}]$ These identities show that multiplication by the transform of the period-subdividing distribution $[S_{{\bf A}/{\bf B}}^{*}]$ (respectively $[S_{{\bf B}/{\bf A}}]$ ) has the effect of decimating $[R_{\bf B}]$ to $[R_{\bf A}]$ (respectively $[R_{\bf A}^{*}]$ to $[R_{\bf B}^{*}]$ ). They clearly imply that, if $[\boldell \in \Lambda_{\bf B}/\Lambda_{\bf A}]$ and $[\boldell^{*} \in \Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}]$ , then $[\eqalign{\bar{\scr F}[S_{{\bf A}/{\bf B}}^{*}] ({\boldell}) &= 1 \hbox{ if } {\boldell} = {\bf 0} \;\;\quad (i.e. \hbox{ if } {\boldell} \hbox{ belongs}\cr &{\hbox to 66pt{}}\hbox{to the class of } \Lambda_{\bf A}),\cr &= 0 \hbox{ if } {\boldell} \neq {\bf 0}\hbox{;}\cr \bar{\scr F}[S_{{\bf B}/{\bf A}}] ({\boldell}^{*}) &= 1 \hbox{ if } {\boldell}^{*} = {\bf 0} \quad (i.e. \hbox{ if } {\boldell}^{*} \hbox{ belongs}\cr &{\hbox to 60pt{}} \hbox{ to the class of } \Lambda_{\bf B}^{*}),\cr &= 0 \hbox{ if } {\boldell}^{*} \neq {\bf 0}.}]$ Therefore, the duality between subdivision and decimation may be viewed as another aspect of that between convolution and multiplication.

There is clearly a strong analogy between the sampling/periodization duality of Section 1.3.2.6.6 and the decimation/subdivision duality, which is viewed most naturally in terms of subgroup relationships: both sampling and decimation involve restricting a function to a discrete additive subgroup of the domain over which it is initially given.

1.3.2.7.2.5. Sublattice relations in terms of periodic distributions

| top | pdf |

The usual presentation of this duality is not in terms of lattice distributions, but of periodic distributions obtained by convolving them with a motif.

Given $[T^{0} \in {\scr E}\,' ({\bb R}^{n})]$ , let us form $[R_{\bf A} * T^{0}]$ , then decimate its transform $[(1/|\det {\bf A}|) R_{\bf A}^{*} \times \bar{\scr F}[T^{0}]]$ by keeping only its values at the points of the coarser lattice $[\Lambda_{\bf B}^{*} = {\bf D}^{T} \Lambda_{\bf A}^{*}]$ ; as a result, $[R_{\bf A}^{*}]$ is replaced by $[(1/|\det {\bf D}|) R_{\bf B}^{*}]$ , and the reverse transform then yields $[\displaylines{\hfill{1 \over |\det {\bf D}|} R_{\bf B} * T^{0} = S_{{\bf B}/{\bf A}} * (R_{\bf A} * T^{0})\hfill \hbox{by (ii)},}]$ which is the coset-averaged version of the original $[R_{\bf A} * T^{0}]$ . The converse situation is analogous to that of Shannon's sampling theorem. Let a function $[\varphi \in {\scr E}({\bb R}^{n})]$ whose transform $[\Phi = {\scr F}[\varphi]]$ has compact support be sampled as $[R_{\bf B} \times \varphi]$ at the nodes of $[\Lambda_{\bf B}]$ . Then $[{\scr F}[R_{\bf B} \times \varphi] = {1 \over |\det {\bf B}|} (R_{\bf B}^{*} * \Phi)]$ is periodic with period lattice $[\Lambda_{\bf B}^{*}]$ . If the sampling lattice $[\Lambda_{\bf B}]$ is decimated to $[\Lambda_{\bf A} = {\bf D} \Lambda_{\bf B}]$ , the inverse transform becomes $[\eqalign{{\hbox to 48pt{}}{\scr F}[R_{\bf A} \times \varphi] &= {1 \over |\det {\bf D}|} (R_{\bf A}^{*} * \Phi)\cr &= S_{{\bf A}/{\bf B}}^{*} * (R_{\bf B}^{*} * \Phi){\hbox to 58pt{}}\hbox{by (ii)}^{*},}]$ hence becomes periodized more finely by averaging over the cosets of $[\Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}]$ . With this finer periodization, the various copies of Supp Φ may start to overlap (a phenomenon called `aliasing'), indicating that decimation has produced too coarse a sampling of φ.

1.3.2.7.3. Discretization of the Fourier transformation

| top | pdf |

Let $[\varphi^{0} \in {\scr E}({\bb R}^{n})]$ be such that $[\Phi^{0} = {\scr F}[\varphi^{0}]]$ has compact support ( $[\varphi^{0}]$ is said to be band-limited). Then $[\varphi = R_{\bf A} * \varphi^{0}]$ is $[\Lambda_{\bf A}]$ -periodic, and $[\Phi = {\scr F}[\varphi] = (1/|\det {\bf A}|) R_{\bf A}^{*} \times \Phi^{0}]$ is such that only a finite number of points $[\lambda_{\bf A}^{*}]$ of $[\Lambda_{\bf A}^{*}]$ have a non-zero Fourier coefficient $[\Phi^{0} (\lambda_{\bf A}^{*})]$ attached to them. We may therefore find a decimation $[\Lambda_{\bf B}^{*} = {\bf D}^{T} \Lambda_{\bf A}^{*}]$ of $[\Lambda_{\bf A}^{*}]$ such that the distinct translates of Supp $[\Phi^{0}]$ by vectors of $[\Lambda_{\bf B}^{*}]$ do not intersect.

The distribution Φ can be uniquely recovered from $[R_{\bf B}^{*} * \Phi]$ by the procedure of Section 1.3.2.7.1, and we may write: $[\eqalign{R_{\bf B}^{*} * \Phi &= {1 \over |\det {\bf A}|} R_{\bf B}^{*} * (R_{\bf A}^{*} \times \Phi^{0})\cr &= {1 \over |\det {\bf A}|} R_{\bf A}^{*} \times (R_{\bf B}^{*} * \Phi^{0})\cr &= {1 \over |\det {\bf A}|} R_{\bf B}^{*} * [T_{{\bf A}/{\bf B}}^{*} \times (R_{\bf B}^{*} * \Phi^{0})]\hbox{;}}]$ these rearrangements being legitimate because $[\Phi^{0}]$ and $[T_{{\bf A}/{\bf B}}^{*}]$ have compact supports which are intersection-free under the action of $[\Lambda_{\bf B}^{*}]$ . By virtue of its $[\Lambda_{\bf B}^{*}]$ -periodicity, this distribution is entirely characterized by its `motif' $[\tilde{\Phi}]$ with respect to $[\Lambda_{\bf B}^{*}]$ : $[\tilde{\Phi} = {1 \over |\det {\bf A}|} T_{{\bf A}/{\bf B}}^{*} \times (R_{\bf B}^{*} * \Phi^{0}).]$

Similarly, φ may be uniquely recovered by Shannon interpolation from the distribution sampling its values at the nodes of $[\Lambda_{\bf B} = {\bf D}^{-1} \Lambda_{\bf A} (\Lambda_{\bf B}]$ is a subdivision of $[\Lambda_{\bf B}]$ ). By virtue of its $[\Lambda_{\bf A}]$ -periodicity, this distribution is completely characterized by its motif: $[\tilde{\varphi} = T_{{\bf B}/{\bf A}} \times \varphi = T_{{\bf B}/{\bf A}} \times (R_{\bf A}^{*} * \varphi^{0}).]$

Let $[{\boldell} \in \Lambda_{\bf B}/\Lambda_{\bf A}]$ and $[{\boldell}^{*} \in \Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}]$ , and define the two sets of coefficients $[\!\!\matrix{(1)& \tilde{\varphi} ({\boldell}) \hfill&= \varphi ({\boldell} + \boldlambda_{\bf A})\hfill&\hbox{for any } \boldlambda_{\bf A} \in \Lambda_{\bf A}\hfill&\cr &&&(\hbox{all choices of } \boldlambda_{\bf A} \hbox{ give the same } \tilde{\varphi}),\hfill&\cr (2)&\tilde{\Phi} ({\boldell}^{*}) \hfill&= \Phi^{0} ({\boldell}^{*} + \boldlambda_{\bf B}^{*})\hfill &\hbox{for the unique } \boldlambda_{\bf B}^{*} \hbox{ (if it exists)}\hfill&\cr &&&\hbox{such that } {\boldell}^{*} + \boldlambda_{\bf B}^{*} \in \hbox{Supp } \Phi^{0},\hfill&\cr &&= 0\hfill&\hbox{if no such } \boldlambda_{\bf B}^{*} \hbox{ exists}.\hfill}]$ Define the two distributions $[\omega = {\textstyle\sum\limits_{{\boldell} \in \Lambda_{\bf B}/\Lambda_{\bf A}}} \tilde{\varphi} ({\boldell}) \delta_{({\boldell})}]$ and $[\Omega = {\textstyle\sum\limits_{{\boldell}^{*} \in \Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}}} \tilde{\Phi} ({\boldell}^{*}) \delta_{({\boldell}^{*})}.]$ The relation between ω and Ω has two equivalent forms: $[\displaylines{\quad (\hbox{i})\hfill \quad R_{\bf A} * \omega = {\scr F}[R_{\bf B}^{*} * \Omega] \hfill\cr \quad (\hbox{ii})\hfill \bar{\scr F}[R_{\bf A} * \omega] = R_{\bf B}^{*} * \Omega.\quad\;\;\;\hfill}]$

By (i), $[R_{\bf A} * \omega = |\det {\bf B}| R_{\bf B} \times {\scr F}[\Omega]]$ . Both sides are weighted lattice distributions concentrated at the nodes of $[\Lambda_{\bf B}]$ , and equating the weights at $[\boldlambda_{\bf B} = \boldell + \boldlambda_{\bf A}]$ gives $[\tilde{\varphi} ({\boldell}) = {1 \over |\det {\bf D}|} {\sum\limits_{{\boldell}^{*} \in \Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}}} \tilde{\Phi} ({\boldell}^{*}) \exp [-2\pi i {\boldell}^{*} \cdot ({\boldell} + \boldlambda_{\bf A})].]$ Since $[\boldell^{*} \in \Lambda_{\bf A}^{*}]$ , $[\boldell^{*} \cdot \boldlambda_{\bf A}]$ is an integer, hence $[\tilde{\varphi} ({\boldell}) = {1 \over |\det {\bf D}|} {\sum\limits_{{\boldell}^{*} \in \Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}}} \tilde{\Phi} ({\boldell}^{*}) \exp (-2\pi i {\boldell}^{*} \cdot {\boldell}).]$

By (ii), we have $[{1 \over |\det {\bf A}|} R_{\bf B}^{*} * [T_{{\bf A}/{\bf B}}^{*} \times (R_{\bf B}^{*} * \Phi^{0})] = {1 \over |\det {\bf A}|} \bar{\scr F}[R_{\bf A} * \omega].]$ Both sides are weighted lattice distributions concentrated at the nodes of $[\Lambda_{\bf B}^{*}]$ , and equating the weights at $[{\boldlambda}_{\bf A}^{*} = \boldell^{*} + {\boldlambda}_{\bf B}^{*}]$ gives $[\tilde{\Phi} ({\boldell}^{*}) = {\textstyle\sum\limits_{{\boldell} \in \Lambda_{\bf B}/\Lambda_{\bf A}}} \tilde{\varphi} ({\boldell}) \exp [+2\pi i {\boldell} \cdot ({\boldell}^{*} + {\boldlambda}_{\bf B}^{*})].]$ Since $[\boldell \in \Lambda_{\bf B}]$ , $[\boldell \cdot {\boldlambda}^{*}_{\bf B}]$ is an integer, hence $[\tilde{\Phi} ({\boldell}^{*}) = {\textstyle\sum\limits_{{\boldell} \in \Lambda_{\bf B}/\Lambda_{\bf A}}} \tilde{\varphi} ({\boldell}) \exp (+2\pi i {\boldell} \cdot {\boldell}^{*}).]$

Now the decimation/subdivision relations between $[\Lambda_{\bf A}]$ and $[\Lambda_{\bf B}]$ may be written: $[{\bf A} = {\bf DB} = {\bf BN},]$ so that $[\eqalign{{\boldell} &= {\bf B}{\bf \scr k}\qquad\qquad\hbox{for } {\bf \scr k}\in {\bb Z}^{n}\cr {\boldell}^{*} &= ({\bf A}^{-1})^{T} {\scr k}^{*}\quad \hbox{ for } {\bf \scr k}^{*} \in {\bb Z}^{n}}]$ with $[({\bf A}^{-1})^{T} = ({\bf B}^{-1})^{T} ({\bf N}^{-1})^{T}]$ , hence finally $[{\boldell}^{*} \cdot {\boldell} = {\boldell} \cdot {\boldell}^{*} = {\scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k}).]$

Denoting $[\tilde{\varphi} ({\bf B{\scr k}})]$ by $[\psi ({\scr k})]$ and $[\tilde{\Phi}[({\bf A}^{-1})^{T} {\scr k}^{*}]]$ by $[\Psi ({\scr k}^{*})]$ , the relation between ω and Ω may be written in the equivalent form $[\displaylines{(\hbox{i})\quad\hfill \psi ({\bf \scr k}) = {1 \over |\det {\bf N}|} {\sum\limits_{{\bf \scr k}^{*} \in {\bb Z}^{n}/{\bf N}^{T}{\bb Z}^{n}}} \Psi ({\bf \scr k}^{*}) \exp [-2 \pi i {\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})] \hfill\cr (\hbox{ii})\hfill \Psi ({\bf \scr k}^{*}) = {\sum\limits_{{\scr k}\in {\bb Z}^{n}/{\bf N}{\bb Z}^{\rm n}}} \psi ({\bf \scr k}) \exp [+2 \pi i {\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})], \quad\;\qquad\hfill}]$ where the summations are now over finite residual lattices in standard form.

Equations (i) and (ii) describe two mutually inverse linear transformations $[{\scr F}({\bf N})]$ and $[\bar{\scr F}({\bf N})]$ between two vector spaces $[W_{\bf N}]$ and $[W_{\bf N}^{*}]$ of dimension $[|\det {\bf N}|]$ . $[{\scr F}({\bf N})]$ [respectively $[\bar{\scr F}({\bf N})]$ ] is the discrete Fourier (respectively inverse Fourier) transform associated to matrix N.

The vector spaces $[W_{\bf N}]$ and $[W_{\bf N}^{*}]$ may be viewed from two different standpoints:

(1) as vector spaces of weighted residual-lattice distributions, of the form $[\alpha ({\bf x}) T_{{\bf B}/{\bf A}}]$ and $[\beta ({\bf x}) T_{{\bf A}/{\bf B}}^{*}]$ ; the canonical basis of $[W_{\bf N}]$ (respectively $[W_{\bf N}^{*}]$ ) then consists of the $[\delta_{({\scr k})}]$ for $[{\scr k}\in {\bb Z}^{n}/{\bf N}{\bb Z}^{n}]$ [respectively $[\delta_{({\scr k}^{*})}]$ for $[{\scr k}^{*} \in {\bb Z}^{n}/{\bf N}^{T} {\bb Z}^{n}]$ ];
(2) as vector spaces of weight vectors for the $[|\det {\bf N}|\ \delta]$ -functions involved in the expression for $[T_{{\bf B}/{\bf A}}]$ (respectively $[T_{{\bf A}/{\bf B}}^{*}]$ ); the canonical basis of $[W_{\bf N}]$ (respectively $[W_{\bf N}^{*}]$ ) consists of weight vectors $[{\bf u}_{{\scr k}}]$ (respectively $[{\bf v}_{{\scr k}^{*}}]$ ) giving weight 1 to element $[{\scr k}]$ (respectively $[{\scr k}^{*}]$ ) and 0 to the others.

These two spaces are said to be `isomorphic' (a relation denoted ≅), the isomorphism being given by the one-to-one correspondence: $[\eqalign{\omega &= {\textstyle\sum\limits_{{\bf \scr k}}} \psi ({\bf \scr k}) \delta_{({\bf \scr k})} \qquad \leftrightarrow \quad \psi = {\textstyle\sum\limits_{{\bf \scr k}}} \psi ({\scr k}) {\bf u}_{{\bf \scr k}}\cr \Omega &= {\textstyle\sum\limits_{{\bf \scr k}^{*}}} \Psi ({\bf \scr k}^{*}) \delta_{({\bf \scr k}^{*})} \quad\; \leftrightarrow \quad \Psi = {\textstyle\sum\limits_{{\bf \scr k}^{*}}} \Psi ({\bf \scr k}^{*}) {\bf v}_{{\bf \scr k}^{*}}.}]$

The second viewpoint will be adopted, as it involves only linear algebra. However, it is most helpful to keep the first one in mind and to think of the data or results of a discrete Fourier transform as representing (through their sets of unique weights) two periodic lattice distributions related by the full, distribution-theoretic Fourier transform.

We therefore view $[W_{\bf N}]$ (respectively $[W_{\bf N}^{*}]$ ) as the vector space of complex-valued functions over the finite residual lattice $[\Lambda_{\bf B}/\Lambda_{\bf A}]$ (respectively $[\Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}]$ ) and write: $[\eqalign{W_{\bf N} &\cong L(\Lambda_{\bf B}/\Lambda_{\bf A}) \cong L({\bb Z}^{n}/{\bf N}{\bb Z}^{n}) \cr W_{\bf N}^{*} &\cong L(\Lambda_{\bf A}^{*}/\Lambda_{\bf B}^{*}) \cong L({\bb Z}^{n}/{\bf N}^{T} {\bb Z}^{n})}]$ since a vector such as ψ is in fact the function $[{\scr k} \;\longmapsto\; \psi ({\scr k})]$ .

The two spaces $[W_{\bf N}]$ and $[W_{\bf N}^{*}]$ may be equipped with the following Hermitian inner products: $[\eqalign{(\varphi, \psi)_{W} &= {\textstyle\sum\limits_{{\bf \scr k}}} \overline{\varphi ({\bf \scr k})} \psi ({\bf \scr k}) \cr (\Phi, \Psi)_{W^{*}} &= {\textstyle\sum\limits_{{\bf \scr k}}} \overline{\Phi ({\bf \scr k}^{*})} \Psi ({\bf \scr k}^{*}),}]$ which makes each of them into a Hilbert space. The canonical bases $[\{{\bf u}_{{\scr k}} | {\scr k}\in {\bb Z}^{n}/{\bf N} {\bb Z}^{n}\}]$ and $[\{{\bf v}_{{\scr k}^{*}} | {\scr k}^{*} \in {\bb Z}^{n}/{\bf N}^{T} {\bb Z}^{n}\}]$ and $[W_{\bf N}]$ and $[W_{\bf N}^{*}]$ are orthonormal for their respective product.

1.3.2.7.4. Matrix representation of the discrete Fourier transform (DFT)

| top | pdf |

By virtue of definitions (i) and (ii), $[\eqalign{{\scr F}({\bf N}) {\bf v}_{{\bf \scr k}^{*}} &= {1 \over |\det {\bf N}|} {\sum\limits_{{\bf \scr k}}} \exp [-2 \pi i {\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})] {\bf u}_{{\bf \scr k}} \cr \bar{\scr F}({\bf N}) {\bf u}_{{\bf \scr k}} &= {\sum\limits_{{\bf \scr k}^{*}}} \exp [+2 \pi i {\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})] {\bf v}_{{\bf \scr k}^{*}}}]$ so that $[{\scr F}({\bf N})]$ and $[\bar{\scr F}({\bf N})]$ may be represented, in the canonical bases of $[W_{\bf N}]$ and $[W_{\bf N}^{*}]$ , by the following matrices: $[\eqalign{[{\scr F}({\bf N})]_{{\bf {\bf \scr k}{\bf \scr k}}^{*}} &= {1 \over |\det {\bf N}|} \exp [-2 \pi i {\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})] \cr [\bar{\scr F}({\bf N})]_{{\bf \scr k}^{*} {\bf \scr k}} &= \exp [+2 \pi i {\bf \scr k}^{*} \cdot ({\bf N}^{-1} {\bf \scr k})].}]$

When N is symmetric, $[{\bb Z}^{n}/{\bf N} {\bb Z}^{n}]$ and $[{\bb Z}^{n}/{\bf N}^{T} {\bb Z}^{n}]$ may be identified in a natural manner, and the above matrices are symmetric.

When N is diagonal, say $[{\bf N} = \hbox{diag} (\nu_{1}, \nu_{2}, \ldots, \nu_{n})]$ , then the tensor product structure of the full multidimensional Fourier transform (Section 1.3.2.4.2.4) $[{\scr F}_{\bf x} = {\scr F}_{x_{1}} \otimes {\scr F}_{x_{2}} \otimes \ldots \otimes {\scr F}_{x_{n}}]$ gives rise to a tensor product structure for the DFT matrices. The tensor product of matrices is defined as follows: $[{\bf A} \otimes {\bf B} = \pmatrix{a_{11} {\bf B} &\ldots &a_{1n} {\bf B}\cr \vdots & &\vdots\cr a_{n1} {\bf B} &\ldots &a_{nn} {\bf B}\cr}.]$ Let the index vectors $[{\scr k}]$ and $[{\scr k}^{*}]$ be ordered in the same way as the elements in a Fortran array, e.g. for $[{\scr k}]$ with $[{\scr k}_{1}]$ increasing fastest, $[{\scr k}_{2}]$ next fastest, $[\ldots, {\scr k}_{n}]$ slowest; then $[{\scr F}({\bf N}) = {\scr F}(\nu_{1}) \otimes {\scr F}(\nu_{2}) \otimes \ldots \otimes {\scr F}(\nu_{n}),]$ where $[[{\scr F}(\nu_{j})]_{{\scr k}_{j}, \, {\scr k}_{j}^{*}} = {1 \over \nu_{j}} \exp \left(-2 \pi i {{\scr k}_{j}^{*} {\scr k}_{j} \over \nu_{j}}\right),]$ and $[\bar{\scr F}({\bf N}) = \bar{\scr F}(\nu_{1}) \otimes \bar{\scr F}(\nu_{2}) \otimes \ldots \otimes \bar{\scr F}(\nu_{n}),]$ where $[[\bar{\scr F}_{\nu_{j}}]_{{\scr k}_{j}^{*}, \, {\scr k}_{j}} = \exp \left(+2 \pi i {{\scr k}_{j}^{*} {\scr k}_{j} \over \nu_{j}}\right).]$

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]$ .

References

Shannon, C. E. (1949). Communication in the presence of noise. Proc. Inst. Radio Eng. NY, 37, 10–21.Google Scholar

Whittaker, E. T. (1915). On the functions which are represented by the expansions of the interpolation-theory. Proc. R. Soc. (Edinburgh), 35, 181–194.Google Scholar

International Tables for Crystallography (2006). Vol. B. ch. 1.3, pp. 45-49