Split-radix FFT algorithm - Revision history

JohnnyBflat: Adding short description: "Fast Fourier transform algorithm"

2023-08-12T02:05:58Z

Adding short description: "Fast Fourier transform algorithm"

← Previous revision		Revision as of 02:05, 12 August 2023
Line 1:		Line 1:
			{{Short description\|Fast Fourier transform algorithm}}
	The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968)[https://dl.acm.org/profile/81387609872] and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley–Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.		The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968)[https://dl.acm.org/profile/81387609872] and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley–Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.

Andormaybe: add a link to acm.org profile for author R. Yavne and link to cited publication.

2023-03-09T19:00:43Z

add a link to acm.org profile for author R. Yavne and link to cited publication.

← Previous revision		Revision as of 19:00, 9 March 2023
Line 1:		Line 1:
	The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968) and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley–Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.		The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968)[https://dl.acm.org/profile/81387609872] and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley–Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.

	The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required [[real number\|real]] additions and multiplications) to compute a DFT of [[power of two\|power-of-two]] sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 [http://groups.google.com/group/comp.dsp/msg/9e002292accb8a8b] [https://web.archive.org/web/20061130110013/http://home.comcast.net/~kmbtib/]), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a [[computer]], the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)		The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required [[real number\|real]] additions and multiplications) to compute a DFT of [[power of two\|power-of-two]] sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 [http://groups.google.com/group/comp.dsp/msg/9e002292accb8a8b] [https://web.archive.org/web/20061130110013/http://home.comcast.net/~kmbtib/]), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a [[computer]], the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)
Line 45:		Line 45:

	==References==		==References==
	* R. Yavne, "An economical method for calculating the discrete Fourier transform," in ''Proc. AFIPS Fall Joint Computer Conf.'' '''33''', 115–125 (1968).		* R. Yavne, "[https://dl.acm.org/doi/10.1145/1476589.1476610 An economical method for calculating the discrete Fourier transform]," in ''Proc. AFIPS Fall Joint Computer Conf.'' '''33''', 115–125 (1968).
	* P. Duhamel and H. Hollmann, "Split-radix FFT algorithm," ''Electron. Lett.'' '''20''' (1), 14–16 (1984).		* P. Duhamel and H. Hollmann, "Split-radix FFT algorithm," ''Electron. Lett.'' '''20''' (1), 14–16 (1984).
	* M. Vetterli and H. J. Nussbaumer, "Simple FFT and DCT algorithms with reduced number of operations," ''Signal Processing'' '''6''' (4), 267–278 (1984).		* M. Vetterli and H. J. Nussbaumer, "Simple FFT and DCT algorithms with reduced number of operations," ''Signal Processing'' '''6''' (4), 267–278 (1984).

134.134.137.85: The periodicity that is relevant is in N/4 (i.e., the denominator in W), not k.

2022-09-07T22:42:53Z

The periodicity that is relevant is in N/4 (i.e., the denominator in W), not k.

← Previous revision		Revision as of 22:42, 7 September 2022
Line 28:		Line 28:
	:<math>X_k = U_k + \omega_N^k Z_k + \omega_N^{3k} Z'_k.</math>		:<math>X_k = U_k + \omega_N^k Z_k + \omega_N^{3k} Z'_k.</math>

	This, however, performs unnecessary calculations, since <math>k \geq N/4</math> turn out to share many calculations with <math>k < N/4</math>. In particular, if we add ''N''/4 to ''k'', the size-''N''/4 DFTs are not changed (because they are periodic in ''k''), while the size-''N''/2 DFT is unchanged if we add ''N''/2 to ''k''. So, the only things that change are the <math>\omega_N^k</math> and <math>\omega_N^{3k}</math> terms, known as [[twiddle factor]]s. Here, we use the identities:		This, however, performs unnecessary calculations, since <math>k \geq N/4</math> turn out to share many calculations with <math>k < N/4</math>. In particular, if we add ''N''/4 to ''k'', the size-''N''/4 DFTs are not changed (because they are periodic in ''N''/4), while the size-''N''/2 DFT is unchanged if we add ''N''/2 to ''k''. So, the only things that change are the <math>\omega_N^k</math> and <math>\omega_N^{3k}</math> terms, known as [[twiddle factor]]s. Here, we use the identities:
	:<math>\omega_N^{k+N/4} = -i \omega_N^k</math>		:<math>\omega_N^{k+N/4} = -i \omega_N^k</math>
	:<math>\omega_N^{3(k+N/4)} = i \omega_N^{3k}</math>		:<math>\omega_N^{3(k+N/4)} = i \omega_N^{3k}</math>

JCW-CleanerBot: /* References */task, replaced: IEEE Trans. Signal Processing → IEEE Trans. Signal Process.

2018-10-28T19:41:20Z

References: task, replaced: IEEE Trans. Signal Processing → IEEE Trans. Signal Process.

← Previous revision		Revision as of 19:41, 28 October 2018
Line 50:		Line 50:
	* J. B. Martens, "Recursive cyclotomic factorization—a new algorithm for calculating the discrete Fourier transform," ''IEEE Trans. Acoust., Speech, Signal Processing'' '''32''' (4), 750–761 (1984).		* J. B. Martens, "Recursive cyclotomic factorization—a new algorithm for calculating the discrete Fourier transform," ''IEEE Trans. Acoust., Speech, Signal Processing'' '''32''' (4), 750–761 (1984).
	* P. Duhamel and M. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art," ''Signal Processing'' '''19''', 259–299 (1990).		* P. Duhamel and M. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art," ''Signal Processing'' '''19''', 259–299 (1990).
	* S. G. Johnson and M. Frigo, "[http://www.fftw.org/newsplit.pdf A modified split-radix FFT with fewer arithmetic operations]," ''IEEE Trans. Signal ~~Processing~~'' '''55''' (1), 111–119 (2007).		* S. G. Johnson and M. Frigo, "[http://www.fftw.org/newsplit.pdf A modified split-radix FFT with fewer arithmetic operations]," ''IEEE Trans. Signal Process.'' '''55''' (1), 111–119 (2007).
	* Douglas L. Jones, "[http://cnx.org/content/m12031/latest/ Split-radix FFT algorithms]," ''[http://cnx.org/ Connexions]'' web site (Nov. 2, 2006).		* Douglas L. Jones, "[http://cnx.org/content/m12031/latest/ Split-radix FFT algorithms]," ''[http://cnx.org/ Connexions]'' web site (Nov. 2, 2006).
	* H. V. Sorensen, M. T. Heideman, and C. S. Burrus, "On computing the split-radix FFT", ''IEEE Trans. Acoust., Speech, Signal Processing'' '''34''' (1), 152–156 (1986).		* H. V. Sorensen, M. T. Heideman, and C. S. Burrus, "On computing the split-radix FFT", ''IEEE Trans. Acoust., Speech, Signal Processing'' '''34''' (1), 152–156 (1986).

InternetArchiveBot: Rescuing 1 sources and tagging 0 as dead. #IABot (v1.6.5)

2018-05-27T15:45:31Z

Rescuing 1 sources and tagging 0 as dead. #IABot (v1.6.5)

← Previous revision		Revision as of 15:45, 27 May 2018
Line 1:		Line 1:
	The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968) and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley–Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.		The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968) and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley–Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.

	The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required [[real number\|real]] additions and multiplications) to compute a DFT of [[power of two\|power-of-two]] sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 [http://groups.google.com/group/comp.dsp/msg/9e002292accb8a8b] [https://web.archive.org/web/20061130110013/http://home.comcast.net~~:80~~/~kmbtib/]), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a [[computer]], the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)		The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required [[real number\|real]] additions and multiplications) to compute a DFT of [[power of two\|power-of-two]] sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 [http://groups.google.com/group/comp.dsp/msg/9e002292accb8a8b] [https://web.archive.org/web/20061130110013/http://home.comcast.net/~kmbtib/]), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a [[computer]], the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)

	The split-radix algorithm can only be applied when ''N'' is a multiple of 4, but since it breaks a DFT into smaller DFTs it can be combined with any other FFT algorithm as desired.		The split-radix algorithm can only be applied when ''N'' is a multiple of 4, but since it breaks a DFT into smaller DFTs it can be combined with any other FFT algorithm as desired.

Cherkash: fixed dashes using a script

2018-05-01T11:01:31Z

fixed dashes using a script

77.179.220.188: /* Split-radix decomposition */ fix typo

2018-02-16T10:40:03Z

Split-radix decomposition: fix typo

← Previous revision		Revision as of 10:40, 16 February 2018
Line 10:		Line 10:
	where <math>k</math> is an integer ranging from <math>0</math> to <math>N-1</math> and <math>\omega_N</math> denotes the primitive [[root of unity]]:		where <math>k</math> is an integer ranging from <math>0</math> to <math>N-1</math> and <math>\omega_N</math> denotes the primitive [[root of unity]]:
	:<math>\omega_N = e^{-\frac{2\pi i}{N}},</math>		:<math>\omega_N = e^{-\frac{2\pi i}{N}},</math>
	and thus :<math>\omega_N^N = 1</math>.		and thus: <math>\omega_N^N = 1</math>.

	The split-radix algorithm works by expressing this summation in terms of three smaller summations. (Here, we give the "decimation in time" version of the split-radix FFT; the dual decimation in frequency version is essentially just the reverse of these steps.)		The split-radix algorithm works by expressing this summation in terms of three smaller summations. (Here, we give the "decimation in time" version of the split-radix FFT; the dual decimation in frequency version is essentially just the reverse of these steps.)

InternetArchiveBot: Rescuing 1 sources and tagging 0 as dead. #IABot (v1.2.7.1)

2016-12-30T06:56:16Z

Rescuing 1 sources and tagging 0 as dead. #IABot (v1.2.7.1)

← Previous revision		Revision as of 06:56, 30 December 2016
Line 1:		Line 1:
	The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968) and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley-Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.		The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968) and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley-Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.

	The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required [[real number\|real]] additions and multiplications) to compute a DFT of [[power of two\|power-of-two]] sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 [http://groups.google.com/group/comp.dsp/msg/9e002292accb8a8b] [http://home.comcast.net/~kmbtib/]~~{{Dead link\|date=September 2016}}~~), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a [[computer]], the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)		The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required [[real number\|real]] additions and multiplications) to compute a DFT of [[power of two\|power-of-two]] sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 [http://groups.google.com/group/comp.dsp/msg/9e002292accb8a8b] [https://web.archive.org/web/20061130110013/http://home.comcast.net:80/~kmbtib/]), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a [[computer]], the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)

	The split-radix algorithm can only be applied when ''N'' is a multiple of 4, but since it breaks a DFT into smaller DFTs it can be combined with any other FFT algorithm as desired.		The split-radix algorithm can only be applied when ''N'' is a multiple of 4, but since it breaks a DFT into smaller DFTs it can be combined with any other FFT algorithm as desired.

131.155.220.150 at 09:09, 23 September 2016

2016-09-23T09:09:39Z

← Previous revision		Revision as of 09:09, 23 September 2016
Line 1:		Line 1:
	The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968) and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley-Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.		The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968) and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley-Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.

	The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required [[real number\|real]] additions and multiplications) to compute a DFT of [[power of two\|power-of-two]] sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 [http://groups.google.com/group/comp.dsp/msg/9e002292accb8a8b] [http://home.comcast.net/~kmbtib/]), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a [[computer]], the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)		The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required [[real number\|real]] additions and multiplications) to compute a DFT of [[power of two\|power-of-two]] sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 [http://groups.google.com/group/comp.dsp/msg/9e002292accb8a8b] [http://home.comcast.net/~kmbtib/]{{Dead link\|date=September 2016}}), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a [[computer]], the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)

	The split-radix algorithm can only be applied when ''N'' is a multiple of 4, but since it breaks a DFT into smaller DFTs it can be combined with any other FFT algorithm as desired.		The split-radix algorithm can only be applied when ''N'' is a multiple of 4, but since it breaks a DFT into smaller DFTs it can be combined with any other FFT algorithm as desired.

Myasuda: capitalization

2015-09-13T01:25:36Z

capitalization

← Previous revision		Revision as of 01:25, 13 September 2015
Line 1:		Line 1:
	The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete ~~fourier~~ transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968) and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley-Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.		The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968) and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley-Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.

	The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required [[real number\|real]] additions and multiplications) to compute a DFT of [[power of two\|power-of-two]] sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 [http://groups.google.com/group/comp.dsp/msg/9e002292accb8a8b] [http://home.comcast.net/~kmbtib/]), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a [[computer]], the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)		The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required [[real number\|real]] additions and multiplications) to compute a DFT of [[power of two\|power-of-two]] sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 [http://groups.google.com/group/comp.dsp/msg/9e002292accb8a8b] [http://home.comcast.net/~kmbtib/]), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a [[computer]], the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)

← Previous revision		Revision as of 11:01, 1 May 2018
Line 1:		Line 1:
	The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968) and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[~~Cooley-Tukey~~ FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.		The '''split-radix FFT''' is a [[fast Fourier transform]] (FFT) algorithm for computing the [[discrete Fourier transform]] (DFT), and was first described in an initially little-appreciated paper by [[R. Yavne]] (1968) and subsequently rediscovered simultaneously by various authors in 1984. (The name "split radix" was coined by two of these reinventors, [[Pierre Duhamel\|P. Duhamel]] and [[Henk D. L. Hollmann\|H. Hollmann]].) In particular, split radix is a variant of the [[Cooley–Tukey FFT algorithm]] that uses a blend of radices 2 and 4: it [[recursion\|recursively]] expresses a DFT of length ''N'' in terms of one smaller DFT of length ''N''/2 and two smaller DFTs of length ''N''/4.

	The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required [[real number\|real]] additions and multiplications) to compute a DFT of [[power of two\|power-of-two]] sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 [http://groups.google.com/group/comp.dsp/msg/9e002292accb8a8b] [https://web.archive.org/web/20061130110013/http://home.comcast.net:80/~kmbtib/]), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a [[computer]], the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)		The split-radix FFT, along with its variations, long had the distinction of achieving the lowest published arithmetic operation count (total exact number of required [[real number\|real]] additions and multiplications) to compute a DFT of [[power of two\|power-of-two]] sizes ''N''. The arithmetic count of the original split-radix algorithm was improved upon in 2004 (with the initial gains made in unpublished work by J. Van Buskirk via hand optimization for ''N''=64 [http://groups.google.com/group/comp.dsp/msg/9e002292accb8a8b] [https://web.archive.org/web/20061130110013/http://home.comcast.net:80/~kmbtib/]), but it turns out that one can still achieve the new lowest count by a modification of split radix (Johnson and Frigo, 2007). Although the number of arithmetic operations is not the sole factor (or even necessarily the dominant factor) in determining the time required to compute a DFT on a [[computer]], the question of the minimum possible count is of longstanding theoretical interest. (No tight lower bound on the operation count has currently been proven.)
Line 21:		Line 21:
	</math>		</math>

	where we have used the fact that <math>\omega_N^{m n k} = \omega_{N/m}^{n k}</math>. These three sums correspond to ''portions'' of [[~~Cooley-Tukey~~ FFT algorithm#The radix-2 DIT case\|radix-2]] (size ''N''/2) and radix-4 (size ''N''/4) ~~Cooley-Tukey~~ steps, respectively. (The underlying idea is that the even-index subtransform of radix-2 has no multiplicative factor in front of it, so it should be left as-is, while the odd-index subtransform of radix-2 benefits by combining a second recursive subdivision.)		where we have used the fact that <math>\omega_N^{m n k} = \omega_{N/m}^{n k}</math>. These three sums correspond to ''portions'' of [[Cooley–Tukey FFT algorithm#The radix-2 DIT case\|radix-2]] (size ''N''/2) and radix-4 (size ''N''/4) Cooley–Tukey steps, respectively. (The underlying idea is that the even-index subtransform of radix-2 has no multiplicative factor in front of it, so it should be left as-is, while the odd-index subtransform of radix-2 benefits by combining a second recursive subdivision.)

	These smaller summations are now exactly DFTs of length ''N''/2 and ''N''/4, which can be performed recursively and then recombined.		These smaller summations are now exactly DFTs of length ''N''/2 and ''N''/4, which can be performed recursively and then recombined.
Line 49:		Line 49:
	* M. Vetterli and H. J. Nussbaumer, "Simple FFT and DCT algorithms with reduced number of operations," ''Signal Processing'' '''6''' (4), 267–278 (1984).		* M. Vetterli and H. J. Nussbaumer, "Simple FFT and DCT algorithms with reduced number of operations," ''Signal Processing'' '''6''' (4), 267–278 (1984).
	* J. B. Martens, "Recursive cyclotomic factorization—a new algorithm for calculating the discrete Fourier transform," ''IEEE Trans. Acoust., Speech, Signal Processing'' '''32''' (4), 750–761 (1984).		* J. B. Martens, "Recursive cyclotomic factorization—a new algorithm for calculating the discrete Fourier transform," ''IEEE Trans. Acoust., Speech, Signal Processing'' '''32''' (4), 750–761 (1984).
	* P. Duhamel and M. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art," ''Signal Processing'' '''19''', ~~259–299~~ (1990).		* P. Duhamel and M. Vetterli, "Fast Fourier transforms: a tutorial review and a state of the art," ''Signal Processing'' '''19''', 259–299 (1990).
	* S. G. Johnson and M. Frigo, "[http://www.fftw.org/newsplit.pdf A modified split-radix FFT with fewer arithmetic operations]," ''IEEE Trans. Signal Processing'' '''55''' (1), 111–119 (2007).		* S. G. Johnson and M. Frigo, "[http://www.fftw.org/newsplit.pdf A modified split-radix FFT with fewer arithmetic operations]," ''IEEE Trans. Signal Processing'' '''55''' (1), 111–119 (2007).
	* Douglas L. Jones, "[http://cnx.org/content/m12031/latest/ Split-radix FFT algorithms]," ''[http://cnx.org/ Connexions]'' web site (Nov. 2, 2006).		* Douglas L. Jones, "[http://cnx.org/content/m12031/latest/ Split-radix FFT algorithms]," ''[http://cnx.org/ Connexions]'' web site (Nov. 2, 2006).
	* H. V. Sorensen, M. T. Heideman, and C. S. Burrus, "On computing the split-radix FFT", ''IEEE Trans. Acoust., Speech, Signal Processing'' '''34''' (1), ~~152-156~~ (1986).		* H. V. Sorensen, M. T. Heideman, and C. S. Burrus, "On computing the split-radix FFT", ''IEEE Trans. Acoust., Speech, Signal Processing'' '''34''' (1), 152–156 (1986).

	[[Category:FFT algorithms]]		[[Category:FFT algorithms]]