Rader's FFT algorithm

Rader's algorithm (1968), named for Charles M. Rader of MIT Lincoln Laboratory, is a fast Fourier transform (FFT) algorithm that computes the discrete Fourier transform (DFT) of prime sizes by re-expressing the DFT as a cyclic convolution (the other algorithm for FFTs of prime sizes, Bluestein's algorithm, also works by rewriting the DFT as a convolution). ^[1]

Ask AI

Table of Contents

1. 26 relations: Big O notation, Bijection, Chirp Z-transform, Composite number, Convolution, Convolution theorem, Cooley–Tukey FFT algorithm, Cunningham chain, Discrete Fourier transform, Discrete Fourier transform over a ring, Discrete Hartley transform, Euler's identity, Fast Fourier transform, Generating set of a group, Group (mathematics), MIT Lincoln Laboratory, Modular arithmetic, Modular multiplicative inverse, Number theory, Power of two, Prime number, Primitive root modulo n, Recursion, Recursion (computer science), Safe and Sophie Germain primes, Steven G. Johnson.

2. FFT algorithms

Big O notation

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity.

See Rader's FFT algorithm and Big O notation

Bijection

A bijection, bijective function, or one-to-one correspondence between two mathematical sets is a function such that each element of the first set (the domain) is mapped to exactly one element of the second set (the codomain).

See Rader's FFT algorithm and Bijection

Chirp Z-transform

The chirp Z-transform (CZT) is a generalization of the discrete Fourier transform (DFT). Rader's FFT algorithm and chirp Z-transform are FFT algorithms.

See Rader's FFT algorithm and Chirp Z-transform

Composite number

A composite number is a positive integer that can be formed by multiplying two smaller positive integers.

See Rader's FFT algorithm and Composite number

Convolution

In mathematics (in particular, functional analysis), convolution is a mathematical operation on two functions (f and g) that produces a third function (f*g).

See Rader's FFT algorithm and Convolution

Convolution theorem

In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions (or signals) is the pointwise product of their Fourier transforms.

See Rader's FFT algorithm and Convolution theorem

Cooley–Tukey FFT algorithm

The Cooley–Tukey algorithm, named after J. W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. Rader's FFT algorithm and Cooley–Tukey FFT algorithm are FFT algorithms.

See Rader's FFT algorithm and Cooley–Tukey FFT algorithm

Cunningham chain

In mathematics, a Cunningham chain is a certain sequence of prime numbers.

See Rader's FFT algorithm and Cunningham chain

Discrete Fourier transform

In mathematics, the discrete Fourier transform (DFT) converts a finite sequence of equally-spaced samples of a function into a same-length sequence of equally-spaced samples of the discrete-time Fourier transform (DTFT), which is a complex-valued function of frequency.

See Rader's FFT algorithm and Discrete Fourier transform

Discrete Fourier transform over a ring

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.

See Rader's FFT algorithm and Discrete Fourier transform over a ring

Discrete Hartley transform

A discrete Hartley transform (DHT) is a Fourier-related transform of discrete, periodic data similar to the discrete Fourier transform (DFT), with analogous applications in signal processing and related fields.

See Rader's FFT algorithm and Discrete Hartley transform

Euler's identity

In mathematics, Euler's identity (also known as Euler's equation) is the equality e^ + 1.

See Rader's FFT algorithm and Euler's identity

Fast Fourier transform

A fast Fourier transform (FFT) is an algorithm that computes the Discrete Fourier Transform (DFT) of a sequence, or its inverse (IDFT). Rader's FFT algorithm and fast Fourier transform are FFT algorithms.

See Rader's FFT algorithm and Fast Fourier transform

Generating set of a group

In abstract algebra, a generating set of a group is a subset of the group set such that every element of the group can be expressed as a combination (under the group operation) of finitely many elements of the subset and their inverses.

See Rader's FFT algorithm and Generating set of a group

Group (mathematics)

In mathematics, a group is a set with an operation that associates an element of the set to every pair of elements of the set (as does every binary operation) and satisfies the following constraints: the operation is associative, it has an identity element, and every element of the set has an inverse element.

See Rader's FFT algorithm and Group (mathematics)

MIT Lincoln Laboratory

The MIT Lincoln Laboratory, located in Lexington, Massachusetts, is a United States Department of Defense federally funded research and development center chartered to apply advanced technology to problems of national security.

See Rader's FFT algorithm and MIT Lincoln Laboratory

Modular arithmetic

In mathematics, modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" when reaching a certain value, called the modulus.

See Rader's FFT algorithm and Modular arithmetic

Modular multiplicative inverse

In mathematics, particularly in the area of arithmetic, a modular multiplicative inverse of an integer is an integer such that the product is congruent to 1 with respect to the modulus.

See Rader's FFT algorithm and Modular multiplicative inverse

Number theory

Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions.

See Rader's FFT algorithm and Number theory

Power of two

A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent.

See Rader's FFT algorithm and Power of two

Prime number

A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers.

See Rader's FFT algorithm and Prime number

Primitive root modulo n

In modular arithmetic, a number is a primitive root modulo if every number coprime to is congruent to a power of modulo.

See Rader's FFT algorithm and Primitive root modulo n

Recursion

Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself.

See Rader's FFT algorithm and Recursion

Recursion (computer science)

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem.

See Rader's FFT algorithm and Recursion (computer science)

Safe and Sophie Germain primes

In number theory, a prime number p is a Sophie Germain prime if 2p + 1 is also prime.

See Rader's FFT algorithm and Safe and Sophie Germain primes

Steven G. Johnson

Steven Glenn Johnson (born 1973) is an American mathematician known for being a co-creator of the FFTW library for software-based fast Fourier transforms and for his work on photonic crystals.

See Rader's FFT algorithm and Steven G. Johnson

See also

FFT algorithms

• Bailey's FFT algorithm
• Bit-reversal permutation
• Bruun's FFT algorithm
• Butterfly diagram
• Chirp Z-transform
• Cooley–Tukey FFT algorithm
• Cyclotomic fast Fourier transform
• FFTPACK
• FFTW
• Fast Fourier transform
• Goertzel algorithm
• Irrational base discrete weighted transform
• Prime-factor FFT algorithm
• Rader's FFT algorithm
• Sliding DFT
• Split-radix FFT algorithm
• Twiddle factor
• Vector-radix FFT algorithm

References

[1] https://en.wikipedia.org/wiki/Rader's_FFT_algorithm

Also known as Rader FFT algorithm.

Unionpedia is a concept map or semantic network organized like an encyclopedia – dictionary. It gives a brief definition of each concept and its relationships.

This is a giant online mental map that serves as a basis for concept diagrams. It's free to use and each article or document can be downloaded. It's a tool, resource or reference for study, research, education, learning or teaching, that can be used by teachers, educators, pupils or students; for the academic world: for school, primary, secondary, high school, middle, technical degree, college, university, undergraduate, master's or doctoral degrees; for papers, reports, projects, ideas, documentation, surveys, summaries, or thesis. Here is the definition, explanation, description, or the meaning of each significant on which you need information, and a list of their associated concepts as a glossary. Available in English, Spanish, Portuguese, Japanese, Chinese, French, German, Italian, Polish, Dutch, Russian, Arabic, Hindi, Swedish, Ukrainian, Hungarian, Catalan, Czech, Hebrew, Danish, Finnish, Indonesian, Norwegian, Romanian, Turkish, Vietnamese, Korean, Thai, Greek, Bulgarian, Croatian, Slovak, Lithuanian, Filipino, Latvian, Estonian and Slovenian. More languages soon.

The information is based on Wikipedia articles and other Wikimedia projects, and it's available under the Creative Commons Attribution-ShareAlike License.

Unionpedia is not endorsed by or affiliated with the Wikimedia Foundation.

Google Play, Android and the Google Play logo are trademarks of Google Inc.

Privacy Policy