Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Discrete Fourier transform over a ring
Summary
In mathematics, the discrete Fourier transform over a ring generalizes the discrete Fourier transform (DFT), of a function whose values are commonly complex numbers, over an arbitrary ring.
Let R be any ring, let be an integer, and let be a principal nth root of unity, defined by:
The discrete Fourier transform maps an n-tuple of elements of R to another n-tuple of elements of R according to the following formula:
By convention, the tuple is said to be in the time domain and the index j is called time. The tuple is said to be in the frequency domain and the index k is called frequency. The tuple is also called the spectrum of . This terminology derives from the applications of Fourier transforms in signal processing.
If R is an integral domain (which includes fields), it is sufficient to choose as a primitive nth root of unity, which replaces the condition () by:
for
Take with . Since , , giving:
where the sum matches (). Since is a primitive root of unity, . Since R is an integral domain, the sum must be zero. ∎
Another simple condition applies in the case where n is a power of two: () may be replaced by .
The inverse of the discrete Fourier transform is given as:
where is the multiplicative inverse of n in R (if this inverse does not exist, the DFT cannot be inverted).
Substituting () into the right-hand-side of (), we get
This is exactly equal to , because
when (by () with ), and
when . ∎
Since the discrete Fourier transform is a linear operator, it can be described by matrix multiplication. In matrix notation, the discrete Fourier transform is expressed as follows:
The matrix for this transformation is called the DFT matrix.
Similarly, the matrix notation for the inverse Fourier transform is
Sometimes it is convenient to identify an n-tuple with a formal polynomial
By writing out the summation in the definition of the discrete Fourier transform (), we obtain:
This means that is just the value of the polynomial for , i.e.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.