Definition
Let be any ring, let be an integer, and let be a principal nth root of unity, defined by:
- for
The discrete Fourier transform maps an n-tuple of elements of to another n-tuple of elements of according to the following formula:
By convention, the tuple is said to be in the time domain and the index is called time. The tuple is said to be in the frequency domain and the index 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 (1) by:
- for
Proof: take with . Since, giving:
where the sum matches (1). 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: (1) may be replaced by .
Read more about this topic: Discrete Fourier Transform (general)
Famous quotes containing the word definition:
“Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
—Walter Pater (1839–1894)
“The physicians say, they are not materialists; but they are:MSpirit is matter reduced to an extreme thinness: O so thin!—But the definition of spiritual should be, that which is its own evidence. What notions do they attach to love! what to religion! One would not willingly pronounce these words in their hearing, and give them the occasion to profane them.”
—Ralph Waldo Emerson (1803–1882)
“It’s a rare parent who can see his or her child clearly and objectively. At a school board meeting I attended . . . the only definition of a gifted child on which everyone in the audience could agree was “mine.””
—Jane Adams (20th century)