Transform of a Product

Define $F$ such that
$$
f(x) = \frac{1}{\sqrt {2 \pi}}  \int{F(k) e^{ikx} {dk}}
$$

and therefore

$$
 F(k) = \frac{1}{\sqrt {2 \pi}} \int {f(x) e^{-ikx}}
$$

Then we have

$$
\int{f(x) g(x) {dx} }  =  \int{F(k)G(-k) {dk} }
$$

Since $ G^\star(-k) \iff g^*(x)$, we have

$$
\int{f(x) g^\star(x) {dx} } = \int {F(k) G^*(k)  {dk}}
$$


Since $g(x) e^{-i \alpha x}  \iff G(k + \alpha)$, a similar manipulation gives

\begin{align}
\int{ f(x) [g(x) e^{-ikx}] {dx} } &= \int{ F(k') G( - k'+ k) ) {dk'}} \\
&= \int{ F(k') G( k - k') ) {dk'}}
\end{align}

Fourier Integral and Periodic Functions

Consider a function $f(t)$, sufficiently well-behaved such that

\begin{align}
f(t) = &\int_{-\infty}^{\infty} {F(\omega) e^{i \omega t} d{\omega }}\\
F(\omega) = \frac 1 {2 \pi} &\int_{-\infty}^{\infty}{f(t) e^{-i \omega t} dt} 
\end{align}

Periodic Function

What does the transform $F(\omega)$ look like for a periodic function?  Let $f(t)$ be periodic: $f(t)$ = $ \sum_n {f_0(t-nT) } $  where $f_0$ is a time-limited function defined over the interval $[0, T]$.

Compute $F(\omega)$:

\begin{align}

F(\omega) &= \frac 1 {2 \pi} \int_{-\infty}^{\infty}{ \sum_{n=-\infty}^{\infty} f_0(t-nT) e^{-i \omega t} {dt} }\\

 &= \sum_{n=-\infty}^{\infty} \frac 1 {2 \pi} \int_{-\infty}^{\infty}{  f_0(t-nT) e^{-i \omega t} {dt} } \\

 &= \sum_{n=-\infty}^{\infty} \frac 1 {2 \pi} \int_{-\infty}^{\infty}{  f_0(t) e^{-i \omega t}e^{-i \omega nT} {dt}} \\

 &= \bbox[ border:2px solid yellow ]{\left( \sum_{n=-\infty}^{\infty} e^{-i \omega nT} \right)}  \bbox[ border:2px solid cyan]{\left(   \frac 1 {2 \pi} \int_0^T{  f_0(t) e^{-i \omega t}{dt} } \right)}

\end{align}


The yellow box is  ${\Omega} \sum_{n=-\infty}^{\infty} \delta (\omega-n \Omega)$, where $\Omega = \frac {2 \pi} T$

So we end up with
\begin{align*}
F(\omega) &= \Omega \sum_{n=-\infty}^{\infty} \delta (\omega-n \Omega)  F_0(\omega) \\
&= \Omega \sum_{n=-\infty}^{\infty} \delta (\omega-n \Omega)  F_0(n \Omega)
\end{align*}

$F(\omega)$ is just a sampled version of the transform of $f_0(t)$.

Sampled Function

Working the other way now, let's transform a sampled function.

Let $F$ be the transform of $f$:

$$
F(k) =   \frac 1 {2 \pi} \int_{-\infty}^{\infty}{f(x) e^{-i k x} dx}
$$
$f(x)$ is a sampled version of $g(x)$: 
$$
f(x) = \sum_{n=-\infty}^{\infty} \delta(x - nL) g(x)
$$

The result is immediate:
$$
F(k) =  \frac 1 {2 \pi} \int_{-\infty}^{\infty}{  \left(  \sum_{n=-\infty}^{\infty} \delta(x - nL) \right) g(x)  e^{-i k x} dx}
$$

This looks like a transform of a product, which resolves to a convolution product of the individual transforms. Since $\sum_{n=-\infty}^{\infty} \delta(x - nL) \iff   \bbox[ border:2px solid yellow ]{\frac {\Omega} {2 \pi}  \sum_ {n=-\infty}^{\infty}\delta(k - n\Omega)}$, we can write

\begin{align}
F(k)  &=  \int_{-\infty}^{\infty} {  \left(  \frac {\Omega} {2 \pi} \sum_{n=-\infty}^{\infty} \delta(k - k^{'} - n\Omega) \right) G(k^{'})  dk^{'} } \label{ISI} \\
&=  \frac {\Omega} {2 \pi} \sum_{n=-\infty}^{\infty}  G(k - n \Omega)
\end{align}

This is a set of shifted copies of the transform of $g$, which might be a mess unless $g$ is zero outside the interval controlled by the sample rate $\Omega$.  Although, we will return to this later with an interesting example of when the overlap works out nicely.

Periodic, Sampled Function

Finally, let's work out the transform of a periodic, sampled function.

\begin{align}
F(\omega) &= \frac {1}{2 \pi} \int f(t) e^{-i \omega t} {dt} \\
&=\frac {1}{2 \pi} \int \sum_{m=-\infty}^{\infty} \sum_{n=0}^{L-1} d_n \delta(t-mP-nT) e^{-i \omega t} {dt}\\
&=\frac {1}{2 \pi}\sum_m \sum_{n=0}^{L-1} d_n e^{-i \omega m P} e^{-i \omega n T}\\
&=\frac {1}{2 \pi}\bbox[ border:2px solid yellow ]{\sum_m e^{-i \omega m P}} \sum_{n=0}^{L-1} d_n e^{-i \omega n T} \\
&= \frac {1}{P}\sum_m \delta(\omega - \frac {m 2 \pi}{P}) \sum_{n=0}^{L-1} d_n e^{-i \omega n T} \\
&= \sum_m \delta(\omega - \frac {m 2 \pi}{P}) \frac {1}{P} \sum_{n=0}^{L-1} d_n e^{-i 2 \pi m n  \frac {T}{P} } \\
&= \sum_m \delta(\omega -  m \Omega) \frac {\Omega}{2 \pi} \sum_{n=0}^{L-1} d_n e^{-i 2 \pi m \frac {n} L }  \\
&= \sum_m \delta(\omega -  m \Omega)  c_m
\end{align}

We used $\Omega P = 2 \pi$ and $P \equiv T L$, and defined

\begin{align*}
c_m &= \frac {\Omega}{2 \pi} \sum_{n=0}^{L-1} d_n e^{-i 2 \pi m \frac {n} L } \\
&= \left({1 \over T}\right)  \left({1 \over L} \sum_{n=0}^{L-1} d_n e^{-i 2 \pi m \frac {n} L }\right)
\end{align*}

In general, the transform of a periodic function is discrete, the transform of a discrete function is periodic, and the transform of a periodic and discrete function is periodic and discrete.

The Nysquist Criterion for Avoiding ISI

Returning to equation \eqref{ISI}, consider the following system

$$ y(t) = \sum_n c_n h(t-nT)   $$

Sampled at intervals $t-kT=0$, this looks like

\begin{align*}
y(kT) &= \sum_n c_n h(kT-nT) \\
\hat y(k) &= \sum_n c_n  \hat h(k-n)
\end{align*}

We would like to investigate the situation where $\hat y(k)$ is just $c_k$.  That is, $\hat h(k)$ are all zero with one exception: $\hat h(k) = \delta_k$.  So let's look at the Fourier analysis of a discrete version of $h(t)$:

\begin{align*}

\sum_{n=-\infty}^{\infty} \delta(t - nT) h(t) &= \int \frac {\Omega} {2 \pi} \sum_{n=-\infty}^{\infty}  H(\omega - n \Omega) e^{i \omega t} {d\omega} \\

\delta(t) &=  \int \frac {\Omega} {2 \pi} \sum_{n=-\infty}^{\infty}  H(\omega - n \Omega) e^{i \omega t} {d\omega}

\end{align*}

So we must have
$$
\Omega \sum_{n=-\infty}^{\infty}  H(\omega - n \Omega) = 1
$$

In the study of communication in bandlimited channels, this is known as the Nyquist Criterion for the elimination of inter-symbol interference.

Homomorphism

Group

Let $G$ be a group with elements ${g}$, and $H$ is a homomorphism of $G$. The set of elements mapped by $H$ to the identity is the kernel $K$ of $H$. $K$ is a normal subgroup of G, and the cosets of $K$ form another group ${G \over K}$, called a factor group.

Ring

Let $R$ be a ring, and $H$ is a homomorphism of $R$. The kernel $K$ of $H$ is an ideal of $R$, somewhat analogous to the normal subgroup discussed above. The cosets of the ideal $K$ form a factor ring (sometimes: quotient ring) ${R \over K}$. We would like to know how the properties of an ideal $K$ determine the properties of the associated factor ring. We will let our rings be commutative and have identity.

Elements that multiply to zero are called zero divisors. In $Z_6$ (the integers modulo 6), 2 and 3 multiply to zero, so they are zero divisors. If $n$ is not prime, $Z_n$ will have zero-divisors. A ring with no zero divisors is an integral domain. In an integral domain, $ab=0 \implies a=0$ or $b=0$

The elements that have inverses are called units.  The units form a group.  The group of units in $Z_6$ are {1,5}.

A ring in which every element has a multiplicative inverse is a field. A field is necessarily an integral domain. If $ab =0$ , and $a \neq 0$, then multiply by $a^{-1}$ and conclude $b=0$. That the integers $Z$ is not a field shows the reverse is not true. It is true, however, that every finite integral domain is a field.

Principal Ideal

The ideal $(b)$ consisting of all multiples of an element $b$ of $R$ is a principal ideal. This is the smallest ideal containing $b$. If it's unclear how an ideal might *not* be principal, consider a polynomial in two variables over the complex numbers. The ideal generated by x and y is not principal, because if it's principal there's a generator, and if there's a generator, say $p$, this divides every element of the ideal, but that must be a constant (non-zero). Yet there are no constants in the ideal, contradiction.

We can have an ideal generated by a subset, but this is a principal ideal only if the subset is a single element.

Prime Ideal

An ideal $K$ is prime if and only if $ab$ in $K$ implies $a$ or $b$ is in $K$. If $K$ is a prime ideal, the factor ring ${R \over K}$ is an integral domain.

Maximal Ideal

An ideal $K$ is maximal if the only ideal containing $K$ is $R$. If $K$ is a maximal ideal, ${R \over K}$ is a field. A maximal ideal must be prime, but the reverse is not true: a prime ideal might not be maximal.