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.

Definition

Let R be any ring, let ${\displaystyle n\geq 1}$ be an integer, and let ${\displaystyle \alpha \in R}$ be a principal nth root of unity, defined by:^[1]

${\displaystyle {\begin{aligned}&\alpha ^{n}=1\\&\sum _{j=0}^{n-1}\alpha ^{jk}=0{\text{ for }}1\leq k<n\end{aligned}}}$

(1)

The discrete Fourier transform maps an n-tuple ${\displaystyle (v_{0},\ldots ,v_{n-1})}$ of elements of R to another n-tuple ${\displaystyle (f_{0},\ldots ,f_{n-1})}$ of elements of R according to the following formula:

${\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}\alpha ^{jk}.}$

(2)

By convention, the tuple ${\displaystyle (v_{0},\ldots ,v_{n-1})}$ is said to be in the time domain and the index j is called time. The tuple ${\displaystyle (f_{0},\ldots ,f_{n-1})}$ is said to be in the frequency domain and the index k is called frequency. The tuple ${\displaystyle (f_{0},\ldots ,f_{n-1})}$ is also called the spectrum of ${\displaystyle (v_{0},\ldots ,v_{n-1})}$. 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 ${\displaystyle \alpha }$ as a primitive nth root of unity, which replaces the condition (1) by:^[1]

${\displaystyle \alpha ^{k}\neq 1}$ for ${\displaystyle 1\leq k<n}$

Another simple condition applies in the case where n is a power of two: (1) may be replaced by ${\displaystyle \alpha ^{n/2}=-1}$.^[1]

Inverse

The inverse of the discrete Fourier transform is given as:

${\displaystyle v_{j}={\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}.}$

(3)

where ${\displaystyle 1/n}$ is the multiplicative inverse of n in R (if this inverse does not exist, the DFT cannot be inverted).

www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk