On the Duality of Discrete and Periodic Functions

Abstract

Although versions of Poisson’s Summation Formula (PSF) have already been studied extensively, there seems to be no theorem that relates discretization to periodization and periodization to discretization in a simple manner. In this study, we show that two complementary formulas, both closely related to the classical Poisson Summation Formula, are needed to form a reciprocal Discretization-Periodization Theorem on generalized functions. We define discretization and periodization on generalized functions and show that the Fourier transform of periodic functions are discrete functions and, vice versa, the Fourier transform of discrete functions are periodic functions.

1. Introduction

Versions of Poisson’s summation formula have already been the subject of many publications and it is clear that it plays a very central role in mathematics, physics and electrical engineering. Many publications describe the interaction of discretization (or sampling) and periodization. In some publications we find a clear statement that the Poisson’s Summation Formula (PSF) is linked to both discretization and periodization [1–3], and in rare cases we find that the PSF actually is a discretization-periodization theorem [4]. Despite the circumstance that PSF versions are commonly understood as discretization - periodization relationships, it appears to be difficult to find a simple statement on the special interrelation between discretization and periodization. In this paper, we show that two complementary formulas, very closely related to Poisson’s classical summation formula, are needed to form a complete, i.e., reciprocal, discretization-periodization theorem in the tempered distribution sense.

Most publications about discretization and periodization relationships are so far application driven. A comprehensive derivation of interactions between sampling (discretization) and periodization has already been performed for Gabor systems. Orr and Janssen initially covered the transition from continuous settings to discrete settings [5,6] and later Kaiblinger [7] covered the transition from discrete settings to continuous settings. Finally, Søndergaard summarized and complemented these results in [8] and, amongst other things, wrote a Poisson Summation Formula without sums but with sampling and periodization operators instead ([4], Theorem A.1), very similar to the derivation in this paper but in S₀(ℝ), Feichtinger’s algebra [9].

Another comprehensive treatment of interactions between discretization and periodization is given in Ozaktas [10], whereby discreteness and periodicity are characterized as Fourier duals such as translation and modulation. Amongst others, the notion of discrete functions is clarified as being Fourier duals of periodic functions. Other publications establish a connection between sampling and periodization, on the one hand, and Shannon’s Sampling Theorem on the other [11] without compelling necessity to mention Poisson’s summation formula in this context. There are even excellent signal processing textbooks that can manage without Poisson’s summation formula but not without describing its impacts, e.g., [12]. Poisson’s summation formula also plays an important role in wavelet theory [13–15], although only in proofs, because it provides transitions from continuous to discrete settings.

Lastly, Benedetto and Zimmermann investigated the validity of Poisson’s summation formula in several classical spaces in analysis including the space of tempered distributions [3,16]. They define sampling and periodization operators and, amongst others, characterize uniform sampling as the Fourier transform of periodization.

The Poisson Summation Formula is also honored as being the link between the classical Fourier transform and Fourier series in Girgensohn [17], Hunter and Nachtergaele [18] and Strichartz [19]. Indeed, we will see that this link is discretization, formally correct only in the sense of generalized functions, called distributions. Hence, in order to formally treat discrete functions correctly, we will need the theory of distributions, basically developed by Laurent Schwartz in [20,21], with contributions by Temple [22] and Lighthill [2], Gelfand and Schilow [23,24] and Zemanian [25]. For our purposes, it is especially convenient to show everything within the space of tempered distributions ${\mathcal{S}}^{\prime }$, because the Fourier transform of a tempered distribution is again a tempered distribution [21,26]. Note that the Fourier transform definition can even be more generalized to spaces larger than ${\mathcal{S}}^{\prime }$, see [27] for example, but extending these results accordingly is beyond the scope of this paper.

Conversely, results presented in this paper may also hold in less general settings. For engineering purposes, it often suffices to apply the definitions of both sampling and periodization and use their symbols, but neglect their tempered distribution nature, in order to simplify the already established formulas found in textbooks. A first impression of this technique is given in Section 5 that uses almost no generalized functions theory.

Section 2 will first familiarize the reader with the notations used throughout this article. Section 3 explains the proof method; readers familiar with distribution theory may skip this section. In Section 4 we define discretization and periodization as operations on suitable subspaces of tempered distributions and in Section 5 we hope to motivate the reader to apply them to already known results in textbooks. Section 6 provides calculation rules for both discretization and periodization, such that the proof of our theorem in Section 7 reduces to two lines. Finally, we summarize our results in Section 8 and provide an outlook in Section 9.

2. Notation

We mainly follow established notations as in Schwartz [21], including his Fourier transform definition Equation (1), Benedetto [3], Strichartz [26] and Walter [27], and we substantially follow Woodward [1] and Bracewell [28]. One of the primary goals of this paper is to extend Bracewell’s idea of establishing symbolic calculation rules in signal processing for educational purposes. His textbook Fourier Transform and its Applications is a highly recognized standard work in electrical engineering literature. By replacing Bracewell’s Shah symbol III by two Shah-like symbols $\perp \perp \perp$ and $\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }$ we achieve three things: (1) we are able to express the interrelation between discretization and periodization, (2) we are able to express the duality of both symbols and (3) we overcome difficulties that arise when conventional dissimilar symbols are used.

The application of a distribution $f\in {\mathcal{S}}^{\prime }$ to some test function $\phi \in \mathcal{S}$ is denoted as ⟨f, φ⟩ and, in particular, if f is a locally integrable function such that the following integral exists, we define it by

$$\langle f,\phi \rangle :={\displaystyle {\int }_{{ℝ}^n}f(t)\phi (t)d^{n}t.}$$

For singular distributions, e.g., $\delta \in {\mathcal{S}}^{\prime }$, it is required to write down their definition explicitly, i.e., ⟨δ, φ⟩ := φ(0). The Fourier Transform $ℱ$ for integrable functions φ ∈ L¹(ℝⁿ) is defined by

$$(ℱ\phi )(\sigma ):={\displaystyle {\int }_{{ℝ}^n}\phi (t)e^{-2\pi it\cdot \sigma }{d}^{n}t=\langle e^{-2\pi it\cdot \sigma },\phi \rangle }$$

(1)

where $i=\sqrt{-1}$ and t · σ is the usual scalar product in ℝⁿ. For generalized functions $f\in {\mathcal{S}}^{\prime }$ we define its Fourier transform by

$$\langle ℱf,\phi \rangle :=\langle f,ℱ\phi \rangle$$

(2)

i.e., $ℱ$ is “rolled off” to test functions φ, a standard technique for definitions in distribution theory. Defining the Fourier transform in that way implies that $ℱ$δ = 1 and $ℱ$1 = δ, see for example [21]. Also note that $ℱ$⁻¹ $ℱ$f = f and $ℱ$$ℱ$⁻¹ f = f for any $f\in {\mathcal{S}}^{\prime }$, see [21,26], and $ℱℱ\phi =\stackrel{⌣}{\phi }$ where $\stackrel{⌣}{\phi }(t):=\phi (-t)$ for test functions $\phi \in \mathcal{S}$. Furthermore, we define Fourier Series $ℱ$_S for integrable periodic functions f ∈ L¹(ℝⁿ) by

$$({ℱ}_{s}f)(\sigma ):={\displaystyle \sum _{k\in {\mathbb{Z}}^n}f(k)e^{-2\pi it\cdot \sigma }}.$$

(3)

The translation operator τ for some function $f:{ℝ}^n\mapsto ℂ$ and some constant a ∈ ℝⁿ is defined by (τ_af)(t) := f(t − a). For generalized functions it is defined by

$$\langle {\tau }_{a}f,\phi \rangle :=\langle f,{\tau }_{-a}\phi \rangle .$$

Additionally, we abbreviate τ_aδ:= δ_a for translated Dirac impulses δ. Often in the literature we find a Dirac impulse train, also Dirac comb as

$$\text{III}:={\displaystyle \sum _{k\in {\mathbb{Z}}^n}{\delta }_k.}$$

(4)

Instead of δ_k, we often use δ_kT where $T\in {ℝ}_{+}^n=\{t\in {ℝ}^n:0<t_{\nu },1⩽\nu ⩽n\}$. By kT we mean component-wise multiplication with k ∈ ℤⁿ. Note that $\text{III}\in {\mathcal{S}}^{\prime }$, see [2,26,29] for example.

As mentioned already, the Fourier transform of a tempered distribution is again a tempered distribution. So, for convenience, we stay in ${\mathcal{S}}^{\prime }$. Additionally, we sometimes need to restrict ourselves to several subspaces of ${\mathcal{S}}^{\prime }$ and would like to remind the reader that the following continuous embeddings of distribution spaces

$$\begin{array}{llll}\mathcal{D}\subset \mathcal{S}\hfill & \subset \dots \subset ℬ\hfill & \subset {\mathcal{O}}_M\hfill & \subset ℰ\hfill \\ \cap \cap \hfill & \hfill & \cap \hfill & \cap \hfill \\ {ℰ}^{\prime }\subset {\mathcal{O}}_C{}^{\prime }\hfill & \subset {{\mathcal{D}}^{\prime }}_{L^1}\subset \dots \hfill & \subset {\mathcal{S}}^{\prime }\hfill & \subset {\mathcal{D}}^{\prime }.\hfill \end{array}$$

have been investigated in [21]. We will need the space of test functions $ℰ:={\mathcal{C}}^{\infty }$, its dual space $ℰ$′, the space of infinitely differentiable functions with compact support $\mathcal{D}:={\mathcal{C}}_c^{\infty }$ and the space of bounded test functions $ℬ$ and its dual space ${{\mathcal{D}}^{\prime }}_{L^1}$, we need the Schwartz space $\mathcal{S}$ of rapidly decreasing, infinitely differentiable functions and its dual space, the space of tempered distributions ${\mathcal{S}}^{\prime }$ and exploit that $ℱ$ is an automorphism of $\mathcal{S}$, i.e., $ℱ(\mathcal{S})=\mathcal{S}$ and that this implies that $ℱ$ is an automorphism of ${\mathcal{S}}^{\prime }$, i.e., $ℱ({\mathcal{S}}^{\prime })={\mathcal{S}}^{\prime }$.

Additionally, we require the space of slowly increasing test functions ${\mathcal{O}}_M$ and the space of rapidly decreasing distributions to be the image of ${\mathcal{O}}_M$ in ${\mathcal{S}}^{\prime }$ with respect to $ℱ$, i.e., $ℱ({\mathcal{O}}_M)={\mathcal{O}}_C{}^{\prime }$ and $ℱ({\mathcal{O}}_C{}^{\prime })={\mathcal{O}}_M$. Recall that ${\mathcal{O}}_M$ and ${\mathcal{O}}_C{}^{\prime }$ are the spaces of multiplication operators in ${\mathcal{S}}^{\prime }$ and convolution operators in ${\mathcal{S}}^{\prime }$, respectively [21]. Finally, all those spaces X(ℝⁿ) we abbreviate to X, for functions $\phi :{ℝ}^n\to ℂ$ depending on t ∈ ℝⁿ we write φ instead of φ(t). For test functions in ${\mathcal{O}}_M$ we use α, β, for test functions in $\mathcal{S}$ we use φ, ψ and for generalized functions in ${\mathcal{O}}_C{}^{\prime }$ or ${\mathcal{S}}^{\prime }$ we use f, g.

3. Idea

In signal processing it is well-known that sampling a function means periodizing its spectrum. And, vice versa, periodizing a function means sampling its spectrum. Our goal is now, first, to formulate this in the simplest way and, secondly, to prove it the widest possible way. We are especially interested under which conditions these statements hold in the widest sense.

Denoting a generalized function as f and its spectrum as $ℱ$f, we additionally require a symbol for discretization, say $\perp \perp \perp$, and one for periodization, say $\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }$. We will then write a sampled function as $f_s=\perp \perp \perp f$ and a periodized function as $f_p=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }f$. This notation is deliberately chosen such that it reminds us of linear algebra notations like y = Ax. Having a symbol for discretization, we are now able to express the relationship between Fourier series $ℱ$_s and the Fourier transform as ${ℱ}_s(f)=ℱ(\perp \perp \perp f)$, i.e., first applying discretization and then $ℱ$ to f corresponds to what we know as the Fourier series of f, shortly ${ℱ}_s=ℱ\circ \perp \perp \perp$ where ◦ is concatenation. Now, coming back to the first two sentences in this section, our goal is to prove that $ℱ(\perp \perp \perp f)=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }(ℱf)$ and $ℱ(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }f)=\perp \perp \perp (ℱf)$ in the generalized functions sense if f satisfies suitable properties. But what do these properties look like, why do we need distribution theory and does this really have applications?

Properties. We will see that f must be an element in ${\mathcal{O}}_M\subset {\mathcal{S}}^{\prime }$ to fulfill the first equation, and an element in $ℱ({\mathcal{O}}_M)\subset {\mathcal{S}}^{\prime }$ to fulfill the second.

3.1. Distribution Theory

Indeed, the only way to prove these equations is using the theory of generalized functions (distribution theory) because sampling some function φ(t), often explained via definition

$${\displaystyle \int \delta (t)\phi (t)dt\stackrel{def}{=}}\phi (0)$$

is mathematically wrong. Either this integral would be zero according to the definition of δ or it contradicts the Lebesgue integral. Distribution theory has been developed to overcome this problem. Instead of the integral expression, we now write

$$\langle \delta ,\phi \rangle \stackrel{def}{=}\phi (0)$$

to apply δ to a function φ. The novelty is that arbitrarily defined “functions” f can now be applied to other functions φ without contradicting the Lebesgue integral. Hence, ⟨·, ·⟩ can be considered as a “generalized integral” but, equivalently, we must take care that ⟨f, φ⟩ < ∞ holds for all “functions” f operating on functions φ. This is secured by using spaces X of φ having certain properties and spaces X′ of f with complementary properties. So, for example, if f is slowly growing then φ must be rapidly decreasing. Vice versa, if f is rapidly decreasing then φ is allowed to be slowly growing. Coming back to our equations, we must show that if f ∈ X′ then the above equations, e.g., $ℱ(\perp \perp \perp f)=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }(ℱf)$, must hold in the sense that

$$\langle ℱ(\perp \perp \perp f),\phi \rangle =\langle \mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }(ℱf),\phi \rangle <\infty$$

for every test function φ ∈ X. Also, note that spaces of test functions are continuously embedded in spaces of generalized functions X ⊂ X′, such that test functions themselves are generalized functions. Moreover, in distribution theory every test function φ is required being infinitely differentiable $(\phi \in {\mathcal{C}}^{\infty })$ such that derivatives of generalized functions can always be found no matter whether their derivatives do exist in the conventional sense or not. Distribution theory is therefore also regarded as the completion of Fourier analysis [2] or of differential calculus [26].

3.2. Applications

As usually done in distribution theory, we will claim in the following, e.g., Equations (5), (7), (10), (17), (21) and (23), that all functions involved must be test functions, i.e., they are in ${\mathcal{C}}^{\infty }$. This is required in order to be able to roll-off the multiplication of functions with generalized functions to the multiplication of functions with test functions in definition ⟨αf, φ⟩ := ⟨f, αφ⟩ such that $\alpha \phi \in \mathcal{S}$ is secured for all $\phi \in \mathcal{S}$. The property of being infinitely differentiable is a pure technical requirement in distribution theory that does not restrict the theorem we prove for two reasons: (1) In distribution theory, every locally integrable function (considered as generalized function) is already infinitely differentiable and (2) distribution theory is connected to its applications via several approximation theorems (see e.g., [27,30]). For example, every continuous function but also every generalized function can be approximated by test functions, i.e., functions in the classical sense being infinitely differentiable. We therefore always operate (as usual) on either spaces of generalized functions or spaces of test functions.

3.3. Generality

The theorem we prove corresponds to the Fourier transform in ${\mathcal{S}}^{\prime }$, the widest possible comprehension of the Fourier transform as automorphism (according to Laurent Schwartz’ distribution theory [20,21]) and is, hence, most general in this sense. It comprises, moreover, several classical definitions of the Fourier transform. We note, for example, that there is no need to have a special Fourier transform $ℱ$_P designed for periodic functions. Also constants, in particular also being periodic functions, can be Fourier transformed without difficulties. Finally, all results presented in this paper can be used in pure symbolic calculations once they have been proven (in ${\mathcal{S}}^{\prime }$). Our theorem shows that discretization and periodization are intertwined by the Fourier transform, symbolically $ℱ(\perp \perp \perp \cdot )=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\cdot$ and $ℱ(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\cdot )=\perp \perp \perp \cdot$ where · is an operator argument placeholder.

4. Definitions

We often find the Shah symbol III in the literature (Bracewell [28], Feichtinger [31] and Lecture Notes, e.g., [32]) as an abbreviation for the Dirac impulse train Equation (4). It is convenient to only have one symbol because the Dirac impulse train can be used to both discretize and periodize functions: Multiplication with it yields discrete functions, convolution with it yields periodic functions [28]. Furthermore, having only one symbol avoids introducing a theory of operations on functions which is especially of advantage for reasons of brevity in engineering books. However, any interaction between discretization and periodization cannot be expressed via one symbol.

4.1. Discretization

A major difficulty in ${\mathcal{S}}^{\prime }$ is that the product of two tempered distributions is generally not defined. We will therefore use Laurent Schwartz’ [21] space of multiplication operators ${\mathcal{O}}_M$ in the following definition.

Definition 1 (Discretization). For slowly increasing functions$\alpha \in {\mathcal{O}}_M\subset {\mathcal{S}}^{\prime }$ and increments$T\in {ℝ}_{+}^n$ we claim that the tempered distribution defined by

$$\perp \perp {\perp }_T\alpha :={\displaystyle \sum _{k\in {\mathbb{Z}}^n}\alpha (kT){\delta }_{kT}}$$

(5)

converges in${\mathcal{S}}^{\prime }$ (Figure 1). The operation$\perp \perp {\perp }_T$ is called uniform discretization (or sampling) with increments T. We call$\perp \perp {\perp }_T\alpha$ the discrete (sampled) function of α discretized (sampled) with increments T. Discretization (sampling) is a linear continuous operator$\perp \perp {\perp }_T:{\mathcal{O}}_M\to {\mathcal{S}}^{\prime }$, $\alpha \mapsto \perp \perp {\perp }_T\alpha$. We abbreviate$\perp \perp \perp \alpha$, if α is discretized (sampled) with increments T_ν = 1 in all dimensions 1 ⩽ ν ⩽ n and identify$\perp \perp {\perp }_{T}1\equiv \perp \perp {\perp }_T$.

Discretization will be well-defined in this sense and it is clear that these series indeed converge in ${\mathcal{S}}^{\prime }$, see [26] for example. This definition corresponds in fact to the multiplication of function α with a Dirac comb ${\text{III}}_T\in {\mathcal{S}}^{\prime }$. It is today already a common engineering practice to model the sampling process by the multiplication with the Dirac comb [33]. However, an operator approach is much more advantageous as we will see later. It can already be found as comb_T (α) in [1], later re-published in [34].

4.2. Periodization

Analogous to discretization where the space of multiplication operators ${\mathcal{O}}_M$ in ${\mathcal{S}}^{\prime }$ is required, we will now need the space of convolution operators ${\mathcal{O}}_C{}^{\prime }$ in ${\mathcal{S}}^{\prime }$, again, introduced by Laurent Schwartz in [21].

Definition 2 (Periodization). For rapidly decreasing tempered distributions$f\in {\mathcal{O}}_C{}^{\prime }\subset {\mathcal{S}}^{\prime }$ and increments$T\in {ℝ}_{+}^n$ we claim that the tempered distribution defined by

$$\mathrm{\Delta }\mathrm{\Delta }{\mathrm{\Delta }}_{T}f:={\displaystyle \sum _{k\in {\mathbb{Z}}^n}{\tau }_{kT}f}$$

(6)

converges in${\mathcal{S}}^{\prime }$ (Figure 2). The operation$\mathrm{\Delta }\mathrm{\Delta }{\mathrm{\Delta }}_T$ is called periodization (replicating) or periodic continuation of f with periods T. Periodization (replicating) is a linear continuous operator$\mathrm{\Delta }\mathrm{\Delta }{\mathrm{\Delta }}_T:{\mathcal{O}}_C{}^{\prime }\to {\mathcal{S}}^{\prime }$, $f\mapsto \mathrm{\Delta }\mathrm{\Delta }{\mathrm{\Delta }}_{T}f$. We abbreviate$\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }f$ if f is periodically continued (replicated) with periods T_ν = 1 in all dimensions 1 ⩽ ν ⩽ n and identify$\mathrm{\Delta }\mathrm{\Delta }{\mathrm{\Delta }}_T\delta \equiv \mathrm{\Delta }\mathrm{\Delta }{\mathrm{\Delta }}_T$.

Again, it is clear that periodization is well-defined in this sense and that these series do converge in ${\mathcal{S}}^{\prime }$. In some textbooks, this operator can be found as rep_T f [1,34,35], as f^per [15], as ${\stackrel{\circ }{f}}_T$ [16], as Pf [26], as $\overline{f}$ [36] as _Tf [37] or as f_T [38]. However, $\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }$ is similar to $\perp \perp \perp$ and can, hence, be used for symbolic calculations as we will see later. We will in particular see that, by using $\perp \perp \perp$ and $\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }$, especially Poisson Summation Formulas reduce to something that is much easier to understand.

5. Motivation

The interaction of discretization and periodization is ubiquitous in many calculations that we find in today’s textbooks. In order to reveal these relations, in this section we use Equations (5) and (6), for the sake of simplicity, neglect considerations in the tempered distribution sense. We give three examples: first, we show that Fourier Series result from Fourier transforming discretized functions. Secondly, we develop periodized functions into Fourier series seeing that it is related to discretization. And, thirdly, we apply the definitions of Section 4 to known versions of Poisson’s summation formula found in the literature.

5.1. Fourier Series and Fourier Transform

Using our definition of discretization we verify that Fourier series actually correspond to a concatenation of discretization followed by Fourier transformation. Hence, having $ℱ$ and $\perp \perp \perp$, the definition of $ℱ$_S as given in Equation (3) is obsolete; we may now write $ℱ\perp \perp \perp$ instead of introducing Equation (3).

Lemma 1 (Fourier Series vs Fourier Transform). Let$\alpha \in {\mathcal{O}}_M$, then

$${ℱ}_s\alpha =ℱ(\perp \perp \perp \alpha )in{\mathcal{S}}^{\prime }.$$

(7)

Proof. We may apply $\perp \perp \perp$ to $\alpha \in {\mathcal{O}}_M$ and, accordingly, $\perp \perp \perp \alpha$ converges in ${\mathcal{S}}^{\prime }$ such that $ℱ(\perp \perp \perp \alpha )\in {\mathcal{S}}^{\prime }$. Due to the convergence of $\perp \perp \perp \alpha$ in ${\mathcal{S}}^{\prime }$ we may calculate term by term. Symbolically, we obtain

$$\begin{array}{l}ℱ(\perp \perp \perp \alpha )=ℱ({\displaystyle \sum _{k\in {\mathbb{Z}}^n}\alpha (k){\delta }_k})={\displaystyle \sum _{k\in {\mathbb{Z}}^n}\alpha (k)ℱ({\tau }_k\delta )={\displaystyle \sum _{k\in {\mathbb{Z}}^n}\alpha (k)e^{-2\pi ik\cdot \sigma }ℱ\delta }}\\ ={{\displaystyle \sum _{k\in {\mathbb{Z}}^n}\alpha (k)e}}^{-2\pi ik\cdot \sigma }={ℱ}_s\alpha .\end{array}$$

with equalities in the tempered distributions sense. □

A consequence is the following equality in the operations sense $\cdot :{\mathcal{O}}_M\to {\mathcal{S}}^{\prime }$

$${ℱ}_s=ℱ\circ \perp \perp \perp$$

(8)

where ○ is the concatenation of operations in ${\mathcal{S}}^{\prime }$. We will later come back to this result in Equation (25).

5.2. Fourier Series of Periodized Functions

For further motivation we show that a Discretization-Periodization Theorem for Schwartz functions $\phi \in \mathcal{S}$ can already be derived from the above definitions: We construct the Fourier series of a periodically continued function $\phi \in \mathcal{S}$ and see that it is indeed related to discretization. Note that every periodic function f can be written as $f=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\varphi$ for some function ϕ. Because $\phi \in \mathcal{S}\subset {\mathcal{O}}_C{}^{\prime }$ it follows that $\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\phi \in {\mathcal{S}}^{\prime }$ is a tempered distribution. As every periodic function can be developed into a sum of e_k(t) = e^{2πi t·k}, k ∈ ℤⁿ, we will now do this for $\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\phi$. Starting from

$$\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\phi (t)={\displaystyle \sum _{k\in {\mathbb{Z}}^n}{c}_k{e}_k(t)}$$

we finally arrive at (see [27,39,40] for example)

$$\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\phi (t)={\displaystyle \sum _{k\in {\mathbb{Z}}^n}\langle {\delta }_k,ℱ\phi \rangle e^{2\pi it\cdot k}}={ℱ}^{-1}({\displaystyle \sum _{k\in {\mathbb{Z}}^n}\langle {\delta }_k,ℱ\phi \rangle {\delta }_k}).$$

(9)

Inserting now the definition of discretization yields this important relationship, a formula being closely related to Poisson’s summation formula, between periodization and discretization

$$ℱ(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\phi )=\perp \perp \perp (ℱ\phi )\mathrm{in}{\mathcal{S}}^{\prime }$$

(10)

so far for Schwartz functions $\phi \in \mathcal{S}$. We note that $ℱ\phi \in \mathcal{S}\subset {\mathcal{O}}_M$ such that $\perp \perp \perp (ℱ\phi )$ is meaningful as well because $\perp \perp \perp$ requires functions in ${\mathcal{O}}_M$ according to Definition 1.

Indeed, Equation (10) can be more generalized and an inversion formula can be found. It will, moreover, be surprising to learn at this point that both operators in Equations (5) and (6) have already been defined in Woodward’s 1953 textbook [1] leading to Equations (28) and (29), meant on functions in $\mathcal{S}$. In Section 7, we will extend these results to generalized functions $f\in {\mathcal{O}}_C{}^{\prime }\supset \mathcal{S}$ and $\mathcal{S}\subset {\mathcal{O}}_M\ni ℱf$ (see also Appendix B).

5.3. Versions of Poisson Summation Formulas

In general, each Poisson Summation Formula is only one of two possible statements: It either turns discretization into periodization resulting in Equations (23) and (28) or it turns periodization into discretization resulting in Equations (24) and (29) via the Fourier transform. And special cases lead to Equations (16) and (27). This can be seen by applying Equations (5) and (6) to PSF versions found in the literature. In the following we distinguish a general version, a classical version, a symmetrical version and, finally, a special version.

For simplicity, let $\phi \in \mathcal{S}$ and T ∈ ℝ₊ (one-dimensional case) for now. Recall that PSF are valid on $\phi \in \mathcal{S}$, see e.g., [3,9]. In Section 7, we will extend these results to generalized functions $f\in {\mathcal{O}}_C{}^{\prime }\supset \mathcal{S}$ and $\mathcal{S}\subset {\mathcal{O}}_M\ni ℱf$ (see also Appendix B). We note that Equation (11) corresponds to Equations (24) and (29) in Section 7.

A general version of Poisson’s summation formula can be found for example as

$$T{\displaystyle \sum _{k\in \mathbb{Z}}\phi (t+kT)={\displaystyle \sum _{k\in \mathbb{Z}}(ℱ\phi )(k/T)}}{e}^{2\pi it\cdot k/T}$$

(11)

in Benedetto and Zimmermann [3] but also in [16,37,38,41–43]. Inserting Equations (5) and (6) and using Equation (9), this formula yields (29). A variation of (11) emerges if T = 1, e.g., in Gröchenig [39].

Now, let t ≡ 0, then Equation (11) reduces to the classical version of Poisson’s summation formula

$$T{\displaystyle \sum _{k\in \mathbb{Z}}\phi (kT)}={\displaystyle \sum _{k\in \mathbb{Z}}(ℱ\phi )(k/T)}$$

(12)

found in [1–3,43–45] for example.

Now, let T ≡ 1, then Equation (12) reduces to the symmetrical version of Poisson’s summation formula

$${\displaystyle \sum _{k\in \mathbb{Z}}\phi (k)}={\displaystyle \sum _{k\in \mathbb{Z}}\widehat{\phi }(k),}$$

(13)

where $\widehat{\phi }:=ℱ\phi$, e.g., found in Feichtinger and Strohmer [9], also in [37,46–48]. We note that the latter two Equations (12) and (13), especially the last one, look most elegant and one might guess that there would be some loss of information from top to bottom. But surprisingly, the deduction could also be done from bottom to top, first via argument substitution x ↦ xT, i.e., using Fourier transform rule $ℱ$(φ(xT)) = (1/T) ($ℱ$φ)(x/T) and then using argument substitution x ↦ t + x, i.e., using Fourier transform rule $ℱ$(φ(t + x)) = ($ℱ$φ)(x) e^2πit·x. Hence, Equations (11), (12) and (13) can be transferred into one another for$\phi \in \mathcal{S}$.

Now, let us assume that instead of $\phi \in \mathcal{S}\subset {\mathcal{S}}^{\prime }$, we indeed have some suitable $f\in {\mathcal{S}}^{\prime }$, let f ≡ δ, then Equation (11) is valid in ${\mathcal{S}}^{\prime }$ (known result) and reduces to the special version of Poisson’s summation formula

$$\begin{array}{l}T{\displaystyle \sum _{k\in \mathbb{Z}}{\delta }_{kT}}={\displaystyle \sum _{k\in \mathbb{Z}}(ℱ\delta )(k/T){ℱ}^{-1}}{\delta }_{k/T}\\ ℱ({\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }}_T\delta )=\frac{1}{T}{\perp \perp \perp }_{\frac{1}{T}}1=\frac{1}{T}\mathrm{\Delta }\mathrm{\Delta }{\mathrm{\Delta }}_{\frac{1}{T}}\delta \end{array}$$

(14)

also found very often in the literature, for example in [16,26,39,49] stating that the Fourier transform of a Dirac comb is a Dirac comb. Thus, Equation (11) with f ≡ δ yields (27). Additionally having T = 1 yields (16), found for example in [3,16,50,51]. Note that in Equation (14) we already use identity ${\perp \perp \perp }_{T}1\equiv {\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }}_T\delta$. Such rules will be treated in the next section.

Finally, by looking at the from bottom-to-top derivation above, we note that there is a certain degree of freedom on what side to move the Fourier transform. This allows us, in contrast to what is already done, to periodize $ℱ$f instead of f, resulting in the other two Equations (23) and (28) we will prove in Section 7. These formulas are, in contrast to Equations (24) and (29), very difficult to find in the literature. However, [52] is one of the rare sources where beside the classical Poisson Summation Equation (37.1) in [52] another dual formula Equation (37.2) in [52] can be found instead of only one; Equation (37.2) in [52] corresponds to Equations (23) and (28) and Equation (37.1) in [52] corresponds to Equations (24) and (29).

6. Calculation Rules

In order to present a concise proof of Theorem 1, we need to compile few important operator properties. We note that the Fourier transform of a Dirac comb within ${\mathcal{S}}^{\prime }$ is commonly known (e.g., [16,39]) whereas the (asymmetric) duality of multiplication and convolution within ${\mathcal{S}}^{\prime }$ is a more generalized case of commonly known (symmetric) versions (e.g., in $\mathcal{S}$), it can be found in [21].

Dirac Comb Identity. The first, maybe surprising observation by looking at the two definitions above is that both operations generate a Dirac impulse train by either sampling the function that is constantly 1 or by periodically repeating δ, symbolically

$${\perp \perp \perp }_{T}1={\displaystyle \sum _{k\in {\mathbb{Z}}^n}{\delta }_{kT}}={\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }}_T\delta .$$

(15)

Moreover, 1 and δ are unitary elements with respect to multiplication and convolution in ${\mathcal{S}}^{\prime }$, respectively. They are also a Fourier pair, more precisely $ℱ$1 = δ and $ℱ$δ = 1. Also note that the Shah symbol III in Equation (4) is called the sampling or replicating symbol in [28] because it can be used for either sampling (discretizing) or replicating (periodizing) a function. However, instead of III we now have either $\perp \perp \perp 1$ or, alternatively, $\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta$ which allows us to switch from discretization to periodization or from periodization to discretization (needed in proof of Theorem 1).

Dirac Comb Fourier Transform. We also need that $ℱ(\perp \perp \perp 1)=\perp \perp \perp 1$ and, accordingly,

$$ℱ(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta )=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta \mathrm{in}{\mathcal{S}}^{\prime }.$$

(16)

Omitting Brackets. A very convenient property of both operators is that brackets can be omitted. For reasons of brevity, we move this proof to Appendix A.

Lemma 2. Let$\alpha ,\beta \in {\mathcal{O}}_M$ and$g,f\in {\mathcal{O}}_C{}^{\prime }$. Then

$$\alpha \cdot ({\perp \perp \perp }_T\beta )={\perp \perp \perp }_T(\alpha \beta )=({\perp \perp \perp }_T\alpha )\cdot \beta and$$

(17)

$$g\ast ({\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }}_{T}f)={\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }}_T(g\ast f)=({\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }}_{T}g)\ast fin{\mathcal{S}}^{\prime }.$$

(18)

In particular, with $\perp \perp \perp 1=\text{III}=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta$, additionally let us identify $\perp \perp \perp 1\equiv \perp \perp \perp$ and $\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta \equiv \mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }$, with Equations (17) and (18) we obtain relationships published in Bracewell [28]

$$\perp \perp \perp \alpha =\perp \perp \perp 1\cdot \alpha =\perp \perp \perp \cdot \alpha =\text{III}\cdot \alpha$$

(19)

$$\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }f=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta \ast f=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\ast f=\text{III}\ast f.$$

(20)

It means that discretization is realized via multiplication and periodization is realized via convolution with III. Note that replacing III by operations $\perp \perp \perp$, $\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }$ is the central proposal in this paper.

Multiplication and Convolution. Recall that multiplication or convolution products do not necessarily exist in ${\mathcal{S}}^{\prime }$. We must rather restrict our operator arguments to suitable subspaces of ${\mathcal{S}}^{\prime }$ (see operator definitions), i.e., to ${\mathcal{O}}_M$ and ${\mathcal{O}}_C{}^{\prime }$ respectively.

Lemma 3 (Multiplication and Convolution). Let $\alpha \in {\mathcal{O}}_M,$$g\in {\mathcal{O}}_C{}^{\prime }$ and $f\in {\mathcal{S}}^{\prime }$. Then

$$ℱ(\alpha \cdot f)=ℱ\alpha \ast ℱfand$$

(21)

$$ℱ(g\ast f)=ℱg\cdot ℱfin{\mathcal{S}}^{\prime }.$$

(22)

A detailed treatment of multiplication and convolution in ${\mathcal{S}}^{\prime }$ including a proof of this lemma is given in [21], Théorème XV, p. 124. Notice that ${\mathcal{O}}_M$ can rarely be found in the literature ([30,53–56]) while ${\mathcal{O}}_C{}^{\prime }$ is better known. A description of interactions of ${\mathcal{O}}_M$ with ${\mathcal{O}}_C{}^{\prime }$, aside from [21], is even more seldom in the literature, e.g., [57,58] describing the Fourier transform as an algebra isomorphism $ℱ:({\mathcal{O}}_C{}^{\prime },\ast )\to ({\mathcal{O}}_M,\cdot )$.

7. The Discretization-Periodization Theorem

For the sake of simplicity, we first consider only increments of T_ν = 1 in all dimensions 1 ⩽ ν ⩽ n and then generalize these results in a corollary below.

7.1. Unitary Increments

Everything is prepared now to present a discretization - periodization theorem in ${\mathcal{S}}^{\prime }$. It consists of two formulas very closely related to Poisson’s Summation Formula starting from discretization and from periodization, respectively. Compared to classical versions of Poisson’s summation formula we simply hide one sum in $\perp \perp \perp$ and the other in $\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }$, such that these formulas become better understandable.

Theorem 1 (Discretization vs. Periodization, unitary case). Let$\alpha \in {\mathcal{O}}_M$ and$f\in {\mathcal{O}}_C{}^{\prime }$. Then

$$ℱ(\perp \perp \perp \alpha )=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }(ℱ\alpha )and$$

(23)

$$ℱ(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }f)=\perp \perp \perp (ℱf)in{\mathcal{S}}^{\prime }.$$

(24)

Note that, in contrast to $\alpha \in {\mathcal{O}}_M$ and $f\in {\mathcal{O}}_C{}^{\prime }$, both formulas hold for Schwartz functions $\phi \in \mathcal{S}$ understood as rapidly decreasing tempered distributions because $\phi \in \mathcal{S}\subset {\mathcal{O}}_M\subset {\mathcal{S}}^{\prime }$ on the one hand, and $\phi \in \mathcal{S}\subset ℱ({\mathcal{O}}_M)={\mathcal{O}}_C{}^{\prime }\subset {\mathcal{S}}^{\prime }$ on the other. Hence, it proves Equation (10) in particular (see Appendix B).

Furthermore, recall that $ℱ(\perp \perp \perp \alpha )$ and $\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }(ℱ\alpha )$ are the Fourier series $ℱ$_S of α according to Equation (7). It is, in other words, the Fourier transform of discrete functions $ℱ$_S. And the second equation corresponds to the Fourier transform of periodic functions $ℱ$_P (Figure 3). See one-page summaries: Figure 3.31 in [12] or Prolog II in [16], for example, embracing all four different Fourier transforms and Fourier series including their (either integral or discrete) inversion formulas.

Proof. Formally, according to the calculation rules shown above the following equalities hold

$$\begin{array}{l}ℱ(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }f)=ℱ\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }(\delta \ast f)=ℱ(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta \ast f)=ℱ(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta )\cdot ℱf=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta \cdot ℱf\\ =\perp \perp \perp 1\cdot ℱf=\perp \perp \perp (1\cdot ℱ)=\perp \perp \perp (ℱf)\end{array}$$

in ${\mathcal{S}}^{\prime }$. We start using f = δ ∗ f because $\delta \in {\mathcal{O}}_C{}^{\prime }$ is the unitary element with respect to convolution in ${\mathcal{O}}_C{}^{\prime }$. Then we apply Equations (18), (22), (16), (15) and (17), in this order. Finally, let $\alpha :=ℱf\in {\mathcal{O}}_M$, we use α = 1·α because $1\in {\mathcal{O}}_M$ is the unitary element with respect to multiplication in ${\mathcal{O}}_M$ to show the second formula in an analogous manner. □

To demonstrate the usefulness of the theorem, we use Equations (23), (24) and (15) to prove Equation (16) by

$$\begin{array}{cc}ℱ(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta )=\perp \perp \perp (ℱ\delta )=\perp \perp \perp 1=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta & \text{and}\\ ℱ(\perp \perp \perp 1)=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }(ℱ1)=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta =\perp \perp \perp 1& \text{in}{\mathrm{S}}^{\prime }\end{array}$$

and identifying $\perp \perp \perp 1\equiv \perp \perp \perp$ and $\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\delta \equiv \mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }$ we obtain $ℱ(\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta })=\perp \perp \perp$ and $ℱ(\perp \perp \perp )=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }$.

Finally, we use the theorem to conclude that Equation (8) is complemented having

$$ℱ\circ \perp \perp \perp ={ℱ}_s=\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }\circ ℱ$$

(25)

in the operations sense : ${\mathcal{O}}_M\to {\mathcal{S}}^{\prime }$. Hence, Fourier series $ℱ$_S either correspond to discretization followed by the Fourier transform or, equivalently, they correspond to the Fourier transform followed by periodization. Accordingly, for the second Poisson Summation Formula (24) we obtain

$$ℱ\circ \mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }={ℱ}_P=\perp \perp \perp \circ ℱ$$

(26)

in the operations sense : ${\mathcal{O}}_C{}^{\prime }\to {\mathcal{S}}^{\prime }$.

7.2. Arbitrary Increments

In our Equations (1), (3) and (4) as well as in Equations (16), (23) and (24) we used periodic functions with periods of T_ν = 1 in all dimensions 1 ⩽ ν ⩽ n, which is convenient but not the general case. The following lemma helps to generalize our results to arbitrary periods and increments.

Lemma 4 (Reciprocity). The Fourier transform of a stretched/compressed Dirac impulse train is a compressed/stretched Dirac impulse train. Formally, let$T=[T_1,T_2,\dots ,T_n]\in {ℝ}_{+}^n$ then

$$ℱ({\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }}_T\delta )=\frac{1}{T_p}{\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }}_{\frac{1}{T}}\delta in{\mathcal{S}}^{\prime }$$

(27)

with $\frac{1}{T}:=[\frac{1}{T_1},\frac{1}{T_2},\dots ,\frac{1}{T_n}]\in {ℝ}_{+}^n$ and T_p :T₁T₂…T_n ∈ ℝ₊

A proof of this lemma is straight forward from what is known in the literature (see for example [16,32,40,49]). We will omit it here for the sake of conciseness. Let us now see the theorem in the arbitrary increments case.

Corollary 1 (Discretization vs. Periodization, general case). Let$\alpha \in {\mathcal{O}}_M$ and$f\in {\mathcal{O}}_C{}^{\prime }$ and let$T=[T_1,T_2,\dots ,T_n]\in {ℝ}_{+}^{n}and\frac{1}{T}:=[\frac{1}{T_1},\frac{1}{T_2},\dots ,\frac{1}{T_n}]\in {ℝ}_{+}^n$ then

$$ℱ({\perp \perp \perp }_{\frac{1}{T}}\alpha )=T_p{\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }}_T(ℱ\alpha )and$$

(28)

$$ℱ({\mathrm{\Delta }\mathrm{\Delta }\mathrm{\Delta }}_{\frac{1}{T}}f)=T_p{\perp \perp \perp }_T(ℱf)in{\mathcal{S}}^{\prime }.$$

(29)

where T_p := T₁T₂…T_n ∈ ℝ₊.

This is instantly verified replacing Equation (16) by Equation (27) in the above proof.

8. Conclusions

We have seen that, in the generalized functions sense, there is a (Fourier transform) duality between discrete and periodic functions. The theorem states that the generalized function being discretized must not grow faster than polynomials and the generalized function being periodized must rapidly decay to zero in order to obtain convergence on both sides of the equations in the generalized functions sense. Furthermore, it is shown that both formulas in this theorem are closely related to the classical Poisson Summation Formula. This means that these conditions will have impact on the validity of Poisson Summation Formula versions. We have, furthermore, seen that one formula in this theorem corresponds to Fourier series and the other formula corresponds to the Fourier transform of periodic functions. Finally, by choosing two similar symbols for discretization and periodization, we showed that an easy-to-use symbolic calculation scheme is obtained.

9. Outlook

The theorem above is indisputably connected to the classical sampling theorem, see, e.g., Woodward [1] or Benedetto and Zimmermann [3]. An all-embracing theory including the Sampling Theorem will, however, require to have two more operations, one reversing discretization and one reversing periodization, i.e., interpolation of discrete functions and restriction of a periodic function to one period. Surprisingly, S^′ has been suitable to model discretization and periodization but will not be suitable to model their inverses. Further studies are required.